Resolving overlapping convex objects in silhouette images by concavity analysis and Gaussian process

Sahar Zafari, Mariia Murashkina, Tuomas Eerola, Jouni Sampo, Heikki Kälviäinen, Heikki Haario

TL;DR

This paper introduces a robust framework for segmenting overlapping convex objects in silhouette images where internal texture is missing. By combining a novel parameter-free concave point detection method with Gaussian Process regression in polar coordinates, the authors accurately reconstruct full object contours from partial edge data, significantly outperforming existing state-of-the-art methods.

What Problem Does This Paper Address?

In fields like nanotechnology and biomedicine, researchers often need to analyze images of "cluttered" objects—think of a pile of nanoparticles or a cluster of cells. A major hurdle is that these images are often silhouettes: you can see the outer boundary of the cluster, but the internal edges where objects overlap are invisible.

Existing solutions like the Watershed transform often over-segment objects, while Ellipse fitting fails when the objects aren't perfectly oval. Deep learning (CNNs) can work but requires massive amounts of manually annotated data, which is often unavailable for specialized industrial or scientific datasets. This paper seeks a "geometry-first" approach that can resolve these overlaps using only the visible boundary information and the prior knowledge that the objects are generally convex.

Methods

The authors propose a three-step modular pipeline:

  1. Pre-processing: The image is binarized (using Otsu’s method) and edges are extracted (using a Canny detector) to create a silhouette map.
  2. Contour Evidence Extraction:
    • Concave Point Detection: The system identifies "pinch points" where two objects meet. The authors developed a parameter-free version of the Prasad+Zhang method, which automatically calculates thresholds based on the digital characteristics of the lines.
  3. Segment Grouping: Once the boundary is broken into segments at the concave points, the algorithm must decide which segments belong to the same object. This is treated as a combinatorial optimization problem and solved using a Branch and Bound (BB) algorithm.
  4. Contour Estimation (The "Secret Sauce"): This is the paper's primary contribution. They use Gaussian Process Regression in Polar Form (GP-PF). By transforming the partial segments into polar coordinates ($r, \theta$), they can treat the contour as a periodic function. The Gaussian Process then "fills in the blanks" for the occluded parts of the object without being restricted to a rigid shape like an ellipse.

Datasets

The method was evaluated on two distinct datasets:

  • Synthetic Dataset: 150 images containing overlapping ellipses with varying degrees of overlap (40%, 50%, and 60%). This allowed for controlled testing of the algorithm's limits.
  • Nanoparticle Dataset: A real-world dataset of 11 high-resolution Transmission Electron Microscopy (TEM) images containing approximately 2,200 manually annotated particles. This dataset is particularly challenging due to noisy boundaries and non-uniform shapes.

Key Insights and Ideas

  • The Power of Polar Coordinates: Moving from Cartesian ($x, y$) to Polar ($r, \theta$) coordinates for Gaussian Processes is a clever move. It naturally handles the "closed-loop" nature of object boundaries and simplifies the math for periodic interpolation.
  • Flexibility over Rigidity: Unlike Ellipse Fitting, which forces a specific geometry, the GP-PF approach is non-parametric. It learns the "style" of the contour from the visible evidence, allowing it to reconstruct objects that are "mostly convex" but have irregular bumps or flat sides.
  • Parameter-Free Robustness: By automating the threshold for concave point detection, the method becomes much more portable. It doesn't require a human to "tweak the knobs" every time the microscope's lighting or resolution changes.

Key Results

The proposed method was compared against three state-of-the-art approaches: SCC, NPA, and CECS.

  • Higher Accuracy: On the nanoparticle dataset, the proposed method achieved a True Positive Rate (TPR) of 87% and an Accuracy (ACC) of 74%, significantly higher than the next best method (SCC at 62%).
  • Precision in Shape: Qualitative results show that the GP-PF method produces much more realistic and precise boundaries for occluded objects compared to B-splines or Ellipse fitting, which often under- or over-estimate the hidden area.
  • Consistency: The method maintained its performance lead even when the "strictness" of the evaluation (the Jaccard Similarity threshold) was increased.

Limitations and Future Work

  • The Convexity Constraint: The entire pipeline relies on the assumption that objects are convex. If the target objects are naturally concave (like a crescent moon shape), the grouping and estimation logic would likely fail.
  • Computational Cost: The Branch and Bound algorithm used for segment grouping is computationally expensive. While fine for offline analysis of microscopy images, it might struggle with real-time video processing of high-density clusters.
  • Future Directions: The authors suggest that future work could involve extending the Gaussian Process model to handle non-convex shapes or integrating more complex prior shape information to handle even higher degrees of overlap.

Summary updated

Abstract

Segmentation of overlapping convex objects has various applications, for example, in nanoparticles and cell imaging. Often the segmentation method has to rely purely on edges between the background and foreground making the analyzed images essentially silhouette images. Therefore, to segment the objects, the method needs to be able to resolve the overlaps between multiple objects by utilizing prior information about the shape of the objects. This paper introduces a novel method for segmentation of clustered partially overlapping convex objects in silhouette images. The proposed method involves three main steps: pre-processing, contour evidence extraction, and contour estimation. Contour evidence extraction starts by recovering contour segments from a binarized image by detecting concave points. After this, the contour segments which belong to the same objects are grouped. The grouping is formulated as a combinatorial optimization problem and solved using the branch and bound algorithm. Finally, the full contours of the objects are estimated by a Gaussian process regression method. The experiments on a challenging dataset consisting of nanoparticles demonstrate that the proposed method outperforms three current state-of-art approaches in overlapping convex objects segmentation. The method relies only on edge information and can be applied to any segmentation problems where the objects are partially overlapping and have a convex shape.
BibTeX
@article{zafari2020resolving,
  author = {Sahar Zafari and Mariia Murashkina and Tuomas Eerola and Jouni Sampo and Heikki Kälviäinen and Heikki Haario},
  title = {{Resolving overlapping convex objects in silhouette images by concavity analysis and Gaussian process}},
  journal = {J. Vis. Commun. Image Represent.},
  year = {2020},
  url = {https://openreview.net/forum?id=QV8ikZrx3u},
}

Loading related content...

Figure