Perceptual Significance Hierarchy: A Computer Vision Theory for Color Separation

Deborah Walters, Ganapathy KrishnanAAAI 1987

Introduction

In the late 1980s, as the printing industry transitioned to electronic systems, "fake color separation"—the process of coloring black-and-white line art, such as Sunday comics—remained a significant bottleneck. While standard computer graphics tools offered "seed-fill" (paint bucket) algorithms, these tools were "perceptually blind." They failed to account for the nuances of hand-drawn art in four critical ways:

  1. Extra lines: Internal textures forced users to manually fill dozens of tiny sub-regions.
  2. Intersecting lines: Foreground objects (like a flower stem) would break background regions into separate pieces.
  3. Gaps: Tiny gaps in hand-drawn lines caused color to "leak" across the entire page.
  4. Illusory contours: Computers failed to recognize shapes that humans see even when lines are missing.

This paper, originally presented at AAAI in 1987, proposes a computer vision theory called the Perceptual Significance Hierarchy (PSH). By mimicking how the human brain prioritizes boundaries over texture, the authors developed a system to automate the tedious manual retouching previously required for commercial art.

The Perceptual Significance Hierarchy (PSH)

The core of the proposed system is a 10-level ranking of lines based on their "perceptual significance." The authors hypothesized that a line's importance is largely determined by its local geometry, specifically its "end connections."

Classification of line end types (A, B, C, and D) used to determine perceptual significance.

As shown in the figure above, line ends are categorized into four primary types:

  • Type A: Corners or junctions of major boundaries, representing the highest level of significance.
  • Type B: Simple line terminations, which often indicate internal texture or shading rather than a structural boundary.
  • Type C & D: Various forms of intersections and crossings.

By filtering for high-significance lines (primarily Type A), the computer can "see" the main container of an object while ignoring the "noise" of interior textures. This allows a single "fill" operation to cover a whole perceptual region rather than requiring the user to click every sub-segment.

Computational Implementation: Rho-space

To process these lines effectively, the authors utilized a 3D computational environment called rho-space, which represents X, Y coordinates along with local orientation ($\theta$). Within this space, they applied parallel algorithms inspired by the human visual cortex to refine the image:

  • Lateral Inhibition: This process removes spurious "noise" responses from edge detectors, ensuring only the most relevant edges are processed.
  • Linear Excitation: This algorithm automatically bridges small gaps in lines, "healing" hand-drawn strokes that might otherwise cause color leaks.
  • Illusory Contour Generation: The system creates "virtual" lines where the geometry suggests a boundary exists, even if no physical ink is present, mimicking human gestalt perception.

Key Results and Evaluation

The system was evaluated using custom line art designed to "stress-test" the vision algorithms, such as complex floral drawings featuring intersecting lines and dense internal textures.

The 10-level PSH process applied to a complex line drawing, showing the progressive segmentation of the image from basic shapes to the final detailed art.

The authors estimated that these vision algorithms could automate approximately 80% of the tasks that previously required manual human retouching. By moving heavy computations—such as convolutions and rho-space processing—to a non-interactive preprocessing stage, the final interactive coloring experience remained fast and responsive for the user. The system successfully ignored internal textures and bridged gaps, enabling a much "smarter" paint bucket tool that aligns with human visual expectations.

Limitations and Future Work

Despite its success, the PSH theory has limitations. In 1987, rho-space computations were described as "computationally intensive," though they were manageable as a preprocessing step. The system also faces challenges with highly ambiguous intersections (like the classic vase/face illusion) where human perception itself is multi-stable and subjective. Furthermore, the theory relies on the "semantics of line art"—the assumption that artists use lines in ways that align with human visual evolution. Consequently, it might struggle with abstract or non-traditional art styles that intentionally subvert these perceptual rules.

Summary updated

BibTeX
@inproceedings{walters1987perceptual,
  author = {Deborah Walters and Ganapathy Krishnan},
  title = {{Perceptual Significance Hierarchy: A Computer Vision Theory for Color Separation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1987},
}
Figure