A Comparison Between the Standard Hough Transform and the Mahalanobis Distance Hough Transform

Chengping Xu, Sergio A. VelastinECCV 1994 · DOI

Introduction

The Standard Hough Transform (SHT) is a cornerstone of computer vision, widely used for detecting geometric primitives like lines and circles. Despite its popularity, SHT faces a significant engineering challenge: the trade-off between precision and resource consumption. Achieving high-resolution parameter estimation typically requires a massive accumulator array, leading to high memory and computational costs. Additionally, SHT's rigid voting mechanism often struggles with digitization noise and high feature density.

This paper presents the Mahalanobis Distance Hough Transform (MDHT), a stochastic evolution of the classic transform. By explicitly modeling measurement and model noise and incorporating Extended Kalman Filter (EKF) refinement, the MDHT achieves superior accuracy and robustness while drastically reducing memory requirements.

Methodology

The MDHT introduces two primary innovations to the standard pipeline:

  1. Stochastic Voting: Unlike the binary "hit-or-miss" voting of SHT, MDHT uses a Mahalanobis distance measure. This incorporates a formal statistical model accounting for measurement noise (image resolution) and model noise (parameter space resolution). It performs a hypothesis test for every point, allowing for "fuzzy" voting that is more resilient to noise.
  2. EKF Refinement: To decouple precision from accumulator resolution, an Extended Kalman Filter is applied as a post-processing step. The EKF "polishes" the initial peak estimates from the MDHT. This "coarse-to-fine" approach allows the system to use a low-resolution, memory-efficient accumulator while still achieving high-precision results.

To maintain computational efficiency, complex matrix operations are pre-calculated into Look-up Tables (LUTs), transforming the online process into a fast matching task.

Experimental Results

The researchers evaluated the MDHT/EKF framework against the SHT using both synthetic datasets (containing 1 to 20 lines) and real-world polygon images.

Detection Performance and Robustness

The MDHT/EKF combination consistently outperformed SHT in both detection rate and false alarm suppression, particularly as the complexity of the scene increased.

Figure 4: Detection Rate (%) and False Alarm Rate (%) as a function of line density for SHT, MDHT, and MDHT/EKF.

As shown in the performance plots, the MDHT/EKF maintains a higher detection rate and a significantly lower false alarm rate compared to SHT as the number of lines per image increases.

Precision and Memory Efficiency

One of the most significant advantages of the MDHT/EKF approach is its ability to achieve high accuracy with minimal memory. The authors demonstrated that the system could use an accumulator array 12.5 times smaller than standard methods while improving parameter estimation.

Figure 6: Comparison of estimated line parameters (θ, ρ) between MDHT/EKF and MDHT against ground truth values.

The table above highlights the precision gains. In statistical tests, the MDHT/EKF consistently showed lower average errors in parameter estimation. For instance, in single-line scenarios, the angular error was reduced from 0.414° (SHT) to just 0.069°.

Conclusion

The Mahalanobis Distance Hough Transform, enhanced by EKF refinement, addresses the fundamental limitations of the Standard Hough Transform. By shifting from a deterministic to a stochastic voting model, the MDHT provides a robust, high-precision, and memory-efficient solution for shape detection in complex and noisy environments. Future work involves further parallelization to enable real-time applications in industrial inspection and robotic control.

Summary updated

BibTeX
@inproceedings{xu1994comparison,
  author = {Chengping Xu and Sergio A. Velastin},
  title = {{A Comparison Between the Standard Hough Transform and the Mahalanobis Distance Hough Transform}},
  booktitle = {European Conference on Computer Vision},
  year = {1994},
  doi = {10.1007/3-540-57956-7\_9},
}

Loading related content...

Figure