A Corner Finding Algorithm for Image Analysis and Registration

Jia-Qi Fang, Thomas S. HuangAAAI 1982

Abstract

This paper presents a mathematically rigorous approach to corner detection for image analysis and registration. By defining a "cornerness" measure based on the gradient of the gradient direction, the authors establish a formal criterion for identifying interest points. To enhance robustness against noise and discretization artifacts, the method incorporates post-processing filters, specifically Median Filtering and a modified Hough Transform. Experimental results on geometric shapes, model planes, and robot arms demonstrate the algorithm's effectiveness in isolating reliable corners for interframe matching and motion analysis.

Introduction

In the early 1980s, computer vision researchers were grappling with the "correspondence problem"—how to match the same point across different images, such as stereo pairs or video frames. To do this efficiently, one needs to find "interest points" or corners that are distinct and easy to track. While earlier operators like Moravec’s existed, many were heuristic and prone to "false corners" caused by image noise or discretization errors. Fang and Huang (1982) sought to put corner detection on a solid mathematical footing and develop filters to separate true geometric corners from the "noise" of digital artifacts.

Methodology

The authors' approach is divided into two main stages: detection and distillation.

The Corner Detector

The core innovation lies in analyzing the behavior of the grey-level gradient. Specifically, they look at the gradient of $\theta$ (the gradient direction). They prove mathematically that the product of the gradient magnitude ($\rho$) and the change in gradient direction reaches a local maximum at a corner. For digital images, the standard Sobel operator is used to approximate these derivatives.

Mathematical model of a corner and its vicinity used to derive the detection criteria.

Distinguishing Corners from Noise

Because the raw detector is sensitive to noise, the authors propose two secondary filtering methods:

  • Median Filtering: A separable median filter is applied to the corner candidates to remove isolated "spikes" or highlights caused by sensor noise.
  • Modified Hough Transform: This more sophisticated approach adapts the O'Gorman and Clowes method to look for the intersection of edges. By using thinned gradient maps and considering a range of angles, it confirms if a candidate point actually sits at the intersection of two distinct lines.

Experimental Evaluation

The paper uses three pairs of custom-captured laboratory images for evaluation:

  • Polyhedra: Simple geometric shapes to test basic accuracy.
  • Model Planes: To test performance on flat, textured surfaces.
  • Robot Arms: To test the algorithm's ability to track moving objects across frames (interframe matching).

Key Insights and Ideas

  • Mathematical Rigor: The formal proof showing that for an ideal corner, the gradient of the gradient direction is zero along straight edges but spikes at the tip moved the field away from heuristic detection toward mathematical definition.
  • The Hough Advantage: The authors found that while Median Filtering is fast, the Hough Transform is far superior at eliminating "near-edge error points"—false positives that appear along straight lines due to pixel alignment.
  • Parallelism: The authors noted that their formulas were simple enough to be evaluated in parallel, making the algorithm a candidate for future multi-processor systems.

Key Results

The proposed filtering methods eliminated 90-95% of noise points, leaving behind a clean set of true corners. The algorithm successfully matched corner points between stereo pairs and moving robot arms, proving its utility for image registration and motion analysis.

Experimental results comparing Hough and Median filtering methods for corner detection on robot arm sequences.

Qualitatively, the Hough Transform approach was found to be more robust than Median Filtering in almost all cases, though it came with a higher computational cost.

Limitations and Future Work

The algorithm has some notable limitations. The Hough Transform approach proved sensitive to "line-shaped noise" caused by camera sensor saturation. Additionally, the Hough Transform is significantly more time-consuming than simple filtering. Finally, the algorithm was primarily tested on indoor, man-made scenes; applying it to natural scenes or more complex objects remains a challenge due to the lack of clear, straight edges.

Summary updated

BibTeX
@inproceedings{fang1982corner,
  author = {Jia-Qi Fang and Thomas S. Huang},
  title = {{A Corner Finding Algorithm for Image Analysis and Registration}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1982},
}
Figure