A Formal Description for Two-Dimensional Patterns

Charles T. Zahn Jr.

In his 1969 paper, C. T. Zahn introduced a foundational framework for computer vision and pattern recognition. The work proposes a mathematically rigorous method to transform a grid of binary pixels into structured, one-dimensional "contour lines." By focusing on boundaries and curvature, Zahn’s method reduces 2D data into a format that is computationally efficient, rotation-invariant, and aligned with biological visual perception.

Addressing the Scaling Problem in Image Processing

In the late 1960s, digital image processing faced a significant scaling challenge: a $1000 \times 1000$ pixel image contains a million data points, and doubling resolution quadruples the data. Furthermore, raw pixel grids lack inherent knowledge of the difference between an object and a hole, making them difficult to manipulate for shape recognition under rotation or resizing.

Zahn sought a "formal description" that met three criteria:

  1. Compactness: Reducing the quadratic growth of 2D data to linear growth.
  2. Mathematical Rigor: Ensuring a one-to-one correspondence between the pixel grid and the description to allow perfect reconstruction.
  3. Perceptual Relevance: Mimicking biological visual systems that prioritize edges and angles over raw intensity.

Methodology: From Matrix to Contour

The pipeline for generating a "structural description" involves several key steps:

  • Triangulation and Contouring: The square pixel grid is subdivided into triangles. A continuous function $F(x,y)$ is defined where black pixels equal 1 and white pixels equal 0. The object edges are defined as the 0.5 contour lines of this function.
  • Curvaturepoint Extraction: Using a sliding window and Boolean logic, the algorithm identifies "curvaturepoints"—the vertices where the contour line changes direction.
  • Smoothing (Inflection Removal): To handle digitization noise, Zahn introduced a technique to delete adjacent bends of opposite signs (inflections) if they are very close. This can reduce data by up to 40% without losing the shape's essence.
  • Bend Groups: Adjacent curvaturepoints of the same sign are merged into "bend groups" to create a compact signature of the shape.
Figure 6: Triangulation rules and curvaturepoint extraction from a matrix pattern.

Key Insights and Structural Hierarchy

A major contribution of this work is the identification of a structural hierarchy. The method does not merely find edges; it identifies "objects" (clockwise curves) and "holes" (counter-clockwise curves), recording how they are nested within one another. This allows for a linguistic representation where shapes can be defined using formal phrase-structure grammars (e.g., defining a "chromosome" as a specific string of primitives).

Figure 1: A complex structural description showing the hierarchy of nested objects and holes.

Results and Mathematical Completeness

Zahn successfully demonstrated a unique one-to-one correspondence between a binary pattern and its structural description. Using the Jordan Curve Theorem and a vertical scan-line approach, the original binary matrix can be mechanically recovered from the contour description, proving no information is lost.

Furthermore, the resulting "bend signatures" are naturally invariant to translation and rotation, solving a major hurdle in early pattern recognition. While 2D pixel data grows quadratically ($N^2$), contour information grows linearly ($N$) with resolution, making the method highly scalable for high-resolution imagery.

Limitations and Legacy

Despite its strengths, the core method is limited to black-and-white images. While Zahn suggested that grayscale images could be processed via multiple thresholds, this significantly increases complexity. Additionally, the smoothing and bend-grouping algorithms require manual tuning of distance thresholds. At the time, the computational demands were such that Zahn proposed implementing curvaturepoint extraction in specialized hardware rather than general-purpose computers. Nevertheless, this work remains a cornerstone in the formalization of shape analysis.

Summary updated

BibTeX
@inproceedings{jr1969formal,
  author = {Charles T. Zahn Jr.},
  title = {{A Formal Description for Two-Dimensional Patterns}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1969},
}
Figure