Detection of elliptical shapes via cross-entropy clustering

Jacek Tabor, Krzysztof Misztal

Abstract

The problem of finding elliptical shapes in an image will be considered. We discuss the solution which uses cross-entropy clustering. The proposed method allows the search for ellipses with predefined sizes and position in the space. Moreover, it works well for search of ellipsoids in higher dimensions.

Introduction

Ellipse detection is a fundamental task in computer vision, essential for applications ranging from medical imaging to industrial quality control. However, identifying ellipses is computationally challenging due to their five degrees of freedom: center coordinates, two axes, and orientation.

Traditional methods like the Hough Transform suffer from "the curse of dimensionality"—as the number of parameters grows, memory and time requirements explode. Conversely, the Expectation-Maximization (EM) algorithm, while mathematically elegant, often gets bogged down in complex "M-step" calculations and numerical minimizations, making it too slow for large datasets or real-time applications. This paper introduces Cross-Entropy Clustering (CEC) as a robust alternative that combines the efficiency of k-means with the statistical modeling capabilities of Gaussian distributions.

Methodology

The core of the proposed approach is Cross-Entropy Clustering (CEC). CEC functions by minimizing an energy function based on the cross-entropy between the observed data and a family of Gaussian densities.

Synthetic examples of circle and ellipse detection using different Gaussian subfamilies.

Key features of the CEC framework include:

  • Gaussian Subfamilies: Users can "tune" the algorithm by choosing different Gaussian models. For example, one can search specifically for circles of a fixed radius, axis-aligned ellipses, or general ellipsoids with any orientation.
  • Efficient Optimization: By adopting a Hartigan-style iterative update, the method avoids the computationally expensive "M-step" found in traditional EM algorithms. This allows for fast updates similar to the Hartigan algorithm for k-means.
  • Automatic Model Selection: CEC inherently penalizes the creation of unnecessary clusters. Every cluster has an inherent "cost" associated with it. If the statistical benefit of adding a new ellipse (measured by the reduction in cross-entropy) does not outweigh the cost of the cluster itself, the algorithm will not create it. This prevents the over-fitting common in EM and allows the algorithm to automatically determine the optimal number of objects in a scene.

Experiments and Data

The algorithm was evaluated using both synthetic geometric data and real-world case studies. Synthetic tests involved black-and-white images with varying numbers of circles and ellipses to verify basic detection capabilities.

Segmentation of toothpicks: (a) original image, (b) binary mask, (c) final detection results.

Real-world testing utilized photographs of everyday objects, such as coins and toothpicks. These images tested the algorithm's robustness against noise, blur, and overlapping objects. In the toothpick example, the algorithm successfully identified elongated shapes by using a statistical prior based on a single template object's covariance matrix. This demonstrates how shape can be used as a statistical prior to guide the search process.

Key Results and Discussion

The CEC method demonstrates several advantages:

  • Robustness: The detection remains stable despite common image disturbances like blurring, contrast changes, or modifications in illumination.
  • Simultaneous Detection: The framework can search for multiple object types (e.g., circular coins and elongated toothpicks) in a single pass.
  • Computational Efficiency: By reducing the search from all possible symmetric matrices to just the set of eigenvalues, the authors significantly simplify the optimization problem. This reduction makes the algorithm much faster than standard Maximum Likelihood Estimation (MLE) approaches.
  • Scalability: The underlying mathematics naturally extend to N-dimensional space, facilitating the detection of ellipsoids in 3D point clouds or higher-dimensional data structures.

Conclusion

While highly effective for elliptical shapes, the current CEC implementation assumes a relatively clean environment where the primary geometries are ellipse-like. If an image contains a mix of ellipses and other distinct geometries like rectangles, the basic model might struggle. Future research will focus on enhancing robustness against non-elliptical noise and integrating the method into more general-purpose object discovery pipelines for complex scenes.

Summary updated

Abstract

The problem of finding elliptical shapes in an image will be considered. We discuss the solution which uses cross-entropy clustering. The proposed method allows the search for ellipses with predefined sizes and position in the space. Moreover, it works well for search of ellipsoids in higher dimensions.
BibTeX
@inproceedings{tabor2013detection,
  author = {Jacek Tabor and Krzysztof Misztal},
  title = {{Detection of elliptical shapes via cross-entropy clustering}},
  booktitle = {IbPRIA},
  year = {2013},
  url = {https://openreview.net/forum?id=3N3GPB4k5W},
}
Figure