ASOD: Arbitrary shape object detection

Selim Mimaroglu, Ertunc ErdilEngineering Applications of AI 2011 · DOI

TL;DR

This paper introduces ASOD, a novel algorithm for detecting objects of arbitrary shapes in images. ASOD frames object detection as a clustering problem, effectively decomposing images into representative points and then grouping them to identify distinct objects, automatically determining the number of objects present.

What Problem Does This Paper Address?

Detecting objects with irregular or "arbitrary" shapes in images is a significant challenge in computer vision and image processing. Traditional object detection methods often struggle with non-standard shapes, and existing clustering techniques have historically faced limitations in accuracy and the need for pre-defined cluster counts. This paper aims to bridge this gap by proposing a robust and automated method for arbitrary shape object detection that overcomes these limitations.

Methods

The core of ASOD lies in its innovative approach to object detection as a clustering problem. The process begins by decomposing the input image into a set of representative data points. These points are then used to construct a distance graph where edges represent the Euclidean distance between points. A key step involves calculating an "attachment" value for each point, which reflects its connectivity to other points. The algorithm then iteratively builds clusters by selecting points with the lowest attachment values as "pivots" and expanding the clusters based on proximity. This method automatically determines the number of clusters (objects) without prior knowledge. ASOD is built upon COMUSA, an algorithm for combining multiple clusterings, but is specifically adapted for object detection. A "relaxation" parameter is also introduced to allow for more flexible cluster expansion, which can be beneficial for larger or more complex objects.

Datasets

The paper evaluates ASOD on a variety of synthetically generated and real-world datasets, including:

  • Synthetic Datasets: 1-spiral, 2-spiral, 2-half rings, 2-curve, Ch4C, and Ch5C. These datasets are used to demonstrate the algorithm's performance on various arbitrary shapes and densities.
  • 3D Datasets: 2Ring3D, Chair Cup & Box3D, and Helicopter. These datasets are used to test ASOD's capabilities in three-dimensional object detection, which is noted as being more challenging.

The paper does not introduce new benchmark datasets but rather uses existing ones to showcase ASOD's effectiveness compared to other methods.

Key Insights and Ideas

  • Object Detection as Clustering: Reframing arbitrary shape object detection as a clustering problem is a powerful insight. This allows ASOD to leverage the strengths of clustering algorithms while addressing the specific challenges of irregular shapes.
  • Automated Cluster Number Determination: A significant advantage of ASOD is its ability to automatically determine the number of objects (clusters) in an image. This eliminates a major hurdle faced by many traditional clustering algorithms.
  • Attachment Metric for Pivot Selection: The use of an "attachment" metric based on edge weights and degrees of freedom in the distance graph provides an intelligent way to select starting points for clusters, leading to more accurate object identification.
  • Relaxation Parameter for Flexibility: The introduction of a relaxation parameter offers a mechanism to tune the algorithm's sensitivity, allowing it to adapt to different object sizes and complexities, which is crucial for real-world applications.

Key Results

ASOD demonstrated highly accurate performance across a range of challenging synthetic and 3D datasets. The paper highlights that ASOD correctly identified arbitrary shape objects even on datasets where common clustering algorithms like k-means failed. For instance, on the Ch4C dataset, ASOD correctly identified all objects with only 11% relaxation. The algorithm also accurately determined the correct number of objects in all tested datasets. While ASOD is very fast on small to medium-sized datasets, k-means showed a speed advantage on very large datasets.

Limitations and Future Work

The authors acknowledge that working with datasets containing a very large number of representative points can increase ASOD's execution time. Future work aims to address this by potentially eliminating the input relaxation rate and by treating sets of points as single entities to potentially reduce execution times.

Summary updated

BibTeX
@article{mimaroglu2011asod,
  author = {Selim Mimaroglu and Ertunc Erdil},
  title = {{ASOD: Arbitrary shape object detection}},
  journal = {Engineering Applications of AI},
  year = {2011},
  doi = {10.1016/j.engappai.2011.07.005},
}
Figure