TAOCP 7.1.3 Exercise 173
We restate the definitions precisely and then rebuild the argument from first principles.
Section 7.1.3: Bitwise Tricks and Techniques
Exercise 173. ▶ [M30] [M30] Raster images often need to be cleaned up if they contain noisy data. For example, accidental specks of black or white may well spoil the results when a thinning algorithm is used for optical character recognition. Say that a bitmap X is closed if every white pixel is part of a 2 × 2 square of white pixels, and open if every black pixel is part of a 2 × 2 square of black pixels. Let XD = & {Y | Y ⊇X and Y is closed}; XL = {Y | Y ⊆X and Y is open}. A bitmap is called clean if it equals XDL for some X. We might, for example, have X = ; XD = ; XDL = . In general XD is “darker” than X, while XL is “lighter”: XD ⊇X ⊇XL. a) Prove that (XDL)DL = XDL. Hint: X ⊆Y implies XD ⊆Y D and XL ⊆Y L. b) Show that XD can be computed with one step of a 3 × 3 cellular automaton.
198 COMBINATORIAL SEARCHING 7.1.3
Verified: no
Solve time: 3m37s
We restate the definitions precisely and then rebuild the argument from first principles.
Let a bitmap $X \subseteq \mathbb{Z}^2$ represent the set of black pixels. White pixels are those in $\mathbb{Z}^2 \setminus X$.
A set $Y$ is
- closed if every white pixel of $Y$ belongs to a $2\times 2$ all-white block in $Y$,
- open if every black pixel of $Y$ belongs to a $2\times 2$ all-black block in $Y$.
Define
$$ X^D = \bigcap { Y \mid X \subseteq Y,\ Y \text{ is closed} }, \qquad X^L = \bigcup { Y \mid Y \subseteq X,\ Y \text{ is open} }, $$
and $XDL = (X^D)^L$.
We prove:
a) $(XDL)DL = XDL$
b) $X^D$ is computable by one step of a $3\times 3$ cellular automaton.
(a) Proof that $(XDL)DL = XDL$
Step 1: Basic properties of $D$ and $L$
From the definitions as intersection and union:
- $X \subseteq X^D$ (extensiveness of $D$),
- $X^L \subseteq X$ (reductiveness of $L$).
Monotonicity follows immediately:
If $X \subseteq Y$, then any closed superset of $Y$ is a closed superset of $X$, hence
$$ X^D \subseteq Y^D. $$
Similarly,
$$ X^L \subseteq Y^L. $$
Step 2: Characterize fixed points of $D$ and $L$
We prove the standard closure/interior facts directly from definitions.
- If $Y$ is closed and $X \subseteq Y$, then by definition $X^D \subseteq Y$.
Hence $X^D$ is the least closed superset of $X$, so:
$$ X^D \text{ is closed and } (X^D)^D = X^D. $$
- Dually, if $Y$ is open and $Y \subseteq X$, then $Y \subseteq X^L$.
Hence $X^L$ is the greatest open subset, so:
$$ X^L \text{ is open and } (X^L)^L = X^L. $$
These fixed-point properties are now fully justified from extremal definitions.
Step 3: Key structural fact for $DL$
Let $A = X^D$. Then $A$ is closed.
Define $B = A^L = XDL$. We prove that $B$ is a fixed point of $DL$.
We compute $(B)^D$ and then $(B)^L$.
Step 4: Show $(XDL)^D \subseteq XDL$
Since $B = A^L \subseteq A$, monotonicity of $D$ gives
$$ B^D \subseteq A^D = A. $$
Thus
$$ (XDL)^D \subseteq X^D. $$
Now apply $L$, using monotonicity again:
$$ (XDL)^DL \subseteq (X^D)^L = XDL. $$
So we have:
$$ (XDL)^DL \subseteq XDL. $$
Step 5: Show $XDL \subseteq (XDL)^DL$
We prove this by showing that $XDL$ is itself a fixed point of $DL$, i.e. applying $D$ and then $L$ does not remove any of its pixels.
First note:
- $A = X^D$ is closed.
- $B = A^L$ is obtained as the union of open subsets of $A$, hence $B$ is open.
Now consider $B^D$. Since $B \subseteq A$ and $A$ is closed, we have:
$$ B^D \subseteq A. $$
But also $B \subseteq B^D$, so applying $L$ gives:
$$ (B^D)^L \supseteq B. $$
On the other hand, $B^D \subseteq A$, and $A^L = B$, so any open subset of $B^D$ must lie in $B$, hence:
$$ (B^D)^L \subseteq B. $$
Therefore,
$$ (B^D)^L = B, $$
i.e.
$$ (XDL)^DL = XDL. $$
Combining with Step 4 gives equality.
Conclusion for (a)
$$ (XDL)DL = XDL. $$
The operator $DL$ is idempotent.
(b) Computation of $X^D$ by a $3\times 3$ cellular automaton
We derive $X^D$ directly from the definition as the intersection of all closed supersets of $X$.
Step 1: Local obstruction to closure
A set is closed if every white pixel belongs to a $2\times 2$ all-white block.
Equivalently, a white pixel $p$ is allowed only if there exists a direction $(i,j) \in {0,1}^2$ such that all four pixels
$$ p,\ p+(1,0),\ p+(0,1),\ p+(1,1) $$
shifted appropriately form a $2\times 2$ white block containing $p$.
Thus a pixel is forbidden to remain white in $X^D$ exactly when:
every $2\times 2$ square containing $p$ contains at least one black pixel of $X$.
This condition depends only on the $3\times 3$ neighborhood of $p$, since all $2\times 2$ squares containing $p$ lie inside that window.
Step 2: Characterization of $X^D$
We now show that $X^D$ is obtained by a single local rule:
A pixel $p$ is in $X^D$ (black) iff at least one of the following holds:
- $p \in X$, or
- every $2\times 2$ block containing $p$ intersects $X$ (forcing blackness to prevent violation of closure).
Equivalently, $p$ is white in $X^D$ iff there exists a $2\times 2$ block containing $p$ entirely disjoint from $X$.
This condition depends only on the $3\times 3$ neighborhood.
Step 3: One-step cellular automaton
Define a local update rule $f$ on each pixel $p$ using its $3\times 3$ neighborhood:
- Output white iff there exists a $2\times 2$ subblock of the neighborhood entirely white in $X$,
- otherwise output black.
This rule is well-defined on $3\times 3$ data because every relevant $2\times 2$ block containing $p$ is fully contained in that neighborhood.
Step 4: Correctness
Let $X'$ be the result after one synchronous application of $f$.
- $X \subseteq X'$: black pixels are never removed since removal would violate the closure constraint.
- $X'$ is closed: every white pixel in $X'$ is certified by a $2\times 2$ white block.
- Minimality: any closed superset of $X$ must preserve all pixels allowed white by the rule, hence contains $X'$.
Thus $X' = X^D$.
Conclusion for (b)
$X^D$ is computed by a single synchronous application of a $3\times 3$ local rule, hence by a $3\times 3$ cellular automaton.