Section 7.1.3: Bitwise Tricks and Techniques

Exercise 170. ▶ [21] [21] What result does the Guo–Hall thinning automaton produce when given a solid black rectangle of M rows and N columns? How long does it take?

Verified: no
Solve time: 4m27s

The previous argument fails because it models Guo–Hall thinning as uniform geometric erosion. The algorithm is not a morphological shrink operator on rectangles. It is a topology-preserving deletion process driven by local connectivity and directional transition constraints. The evolution quickly breaks rectangular structure and converges to a skeletal set determined by symmetry and connectivity, not by boundary stripping.

The correct behavior is obtained by reanalyzing symmetry, deletion constraints, and stability conditions directly.

1. Symmetry reduction of the problem

Let the initial image be the set of black pixels

$$ R_0={1,\dots,M}\times{1,\dots,N}. $$

The Guo–Hall thinning algorithm is:

translation invariant,
rotation symmetric (up to 90°),
reflection symmetric,
and topology preserving (it does not change connectivity or introduce holes).

Hence the evolution of a filled rectangle must preserve all symmetries of the initial configuration.

The initial rectangle is invariant under:

reflection about the horizontal centerline,
reflection about the vertical centerline.

Therefore, every intermediate stable pattern must also be invariant under these reflections.

This immediately implies:

the final skeleton is centered,
it is symmetric about both axes,
it cannot drift or tilt,
and it must be contained in the union of the two symmetry axes.

So the only possible limiting structure is a subset of:

the central row,
the central column.

Thus the final result must be either:

a single horizontal line,
a single vertical line,
or their union (a cross).

We now determine which occurs.

2. Elimination of all non-central pixels

Consider any pixel not lying on the central row or central column.

Such a pixel has an asymmetric neighborhood: one side is strictly closer to the boundary than the opposite side in at least one direction.

Under the Guo–Hall deletion conditions:

a pixel is deletable if removing it does not disconnect the foreground,
and if it satisfies the directional transition constraints in its 8-neighborhood.

For a solid rectangle, any pixel strictly away from both centerlines has redundant connectivity: it lies in a region where removal does not affect any shortest connection between opposite boundaries.

Hence:

all pixels strictly outside the central row and column are eventually deletable,
and once boundary peeling begins, deletion propagates inward from all four sides.

By symmetry, this process continues until only pixels that are essential for maintaining horizontal and vertical connectivity remain.

Those essential pixels are exactly those on:

the central row (connects left and right boundaries),
the central column (connects top and bottom boundaries).

3. Stability of central row and column

We now check why central pixels survive.

(a) Central row pixels

A pixel on the central row has:

symmetric top and bottom neighborhoods,
and lies on all left-right connectivity paths.

Deleting a central-row pixel would break connectivity between left and right halves once thinning has progressed sufficiently, because no alternative path of equal thickness remains after surrounding deletions.

Thus these pixels fail the Guo–Hall deletion test at stabilization.

(b) Central column pixels

By the same argument (rotated symmetry), central column pixels are protected by vertical connectivity.

(c) Intersection point

The center pixel (or 2×2 center block depending on parity) is never deletable because it is the unique articulation point of the limiting symmetric structure.

4. Final configuration

The algorithm converges to a 1-pixel-wide digital skeleton given by the union of central axes:

If pixels are indexed $1,\dots,M$, $1,\dots,N$, define

$$ i_0=\left\lceil \frac{M}{2} \right\rceil,\quad j_0=\left\lceil \frac{N}{2} \right\rceil. $$

Final set:

If both axes are retained (the generic case):

$$ S = ({i_0}\times{1,\dots,N}) ;\cup; ({1,\dots,M}\times{j_0}), $$

a cross-shaped skeleton.

If parity causes overlap (odd dimensions), the intersection is a single center pixel.

Thus the result is a 1-pixel-wide cross-shaped skeleton approximating the medial axis of the rectangle.

It is not a smaller rectangle and not a single segment unless one dimension is extremely small (degenerate cases $M=1$ or $N=1$).

5. Correct evolution picture

The evolution is not rectangular erosion. Instead:

Early iterations delete many boundary pixels in a staggered pattern.
Corners are removed in alternating subiterations.
The boundary becomes indented and non-convex immediately.
Deletion propagates inward until only the medial axis structure remains.

No intermediate state is a rectangle after the first pass.

6. Number of iterations

Each Guo–Hall iteration removes at least one layer of boundary pixels in all four directions, but not uniformly.

The limiting factor is the distance from the outer boundary to the medial axis:

vertically, depth is about $\lfloor M/2 \rfloor$,
horizontally, depth is about $\lfloor N/2 \rfloor$.

Thinning continues until both directions stabilize simultaneously at the medial axis.

Hence the number of iterations is proportional to the maximum radius of the shape:

$$ T = \Theta(\max(M,N)). $$

This is because the longest dimension determines how long endpoint and edge pixels continue to satisfy deletion conditions before stabilizing.

7. Running time

Each iteration scans the entire $M\times N$ array and applies local constant-time tests.

So:

cost per iteration: $\Theta(MN)$,
number of iterations: $\Theta(\max(M,N))$.

Total time:

$$ \Theta(MN\max(M,N)). $$

Final answer

The Guo–Hall thinning automaton applied to a solid $M\times N$ rectangle does not shrink it to a smaller rectangle. Instead, it produces a 1-pixel-wide skeletal cross consisting of the central row and central column (a discrete approximation of the rectangle’s medial axis):

$$ ({i_0}\times{1,\dots,N}) \cup ({1,\dots,M}\times{j_0}), \quad i_0=\left\lceil \frac{M}{2} \right\rceil,; j_0=\left\lceil \frac{N}{2} \right\rceil. $$

The process takes

$$ \Theta(\max(M,N)) $$

iterations, each costing $\Theta(MN)$, for a total running time of