Circular Arc Segmentation

(Based on Discrete Curvature)

Algorithm

S. Pal, R. Dutta, and P. Bhowmick: Circular Arc Segmentation by Curvature Estimation and Geometric Validation, International Journal of Image and Graphics, Vol. 12(4), 24 pages, 2012.

The Idea

The algorithm is based on discrete curvature estimated for the constituent points of digital curve segments, followed by a fast geometric analysis. The curvature information is used in the initial stage to find the potentially circular segments. In the final stage, the circular arcs are merged and maximized in length using the radius and center information of the potentially circular segments. Triplets of longer segments are given higher priorities; doublets and singleton arcs are processed at the end. Detailed experimental results on benchmark datasets demonstrate its efficiency and robustness.



Our Contribution

  • An improved technique is used for estimation of discrete curvature based on characterization of singular and non-singular characters. Such a characterization is achieved by analyzing certain periodic properties (in the chain code composition) of digital straightness.
  • A preliminary (and small) subset of object points is first prepared based on estimated curvature. The arc segments in this preliminary subset are considered as potentially circular, as they stand a high chance to constitute circular arcs. It is based on the fact that the non-circular (or almost straight) curve segments will possess low curvature values, whereas the circular ones will have significantly high curvature estimates.
  • A final stage of geometric analysis is applied to lengthen the circular arcs (in the preliminary set) over the original point set. It relies on higher credential of longer circular arcs than smaller ones, as obtained by curvature estimation. Empirical tolerances are considered to obtain the desired output for real-world images.


Discrete curvature estimated by our algorithm for a typical curve segment which is partly circular and partly straight.

Cropped portion from an image. Estimated discrete curvatures (for k=32) shown as vertical sticks.


Some Results


Input image
(click to see the original size)

Thinned image
(click to see the original size)

Detected segments (endpoints in red)
(click to see the original size)

Points with high curvature (shown in red)
(click to see the original size)

Circular arcs (in red) detected on thinned image
(click to see the original size)

Final output with circular arcs shown in red
(click to see the original size)


Input image
(click to see the original size)

Thinned image
(click to see the original size)

Detected segments (endpoints in red)
(click to see the original size)

Points with high curvature (shown in red)
(click to see the original size)

Circular arcs (in red) detected on thinned image
(click to see the original size)

Final output with circular arcs shown in red
(click to see the original size)


Input image
(click to see the original size)

Thinned image
(click to see the original size)

Detected segments (endpoints in red)
(click to see the original size)

Points with high curvature (shown in red)
(click to see the original size)

Circular arcs (in red) detected on thinned image
(click to see the original size)

Final output with circular arcs shown in red
(click to see the original size)


Input image
(click to see the original size)

After binarization
(click to see the original size)

Thinned image
(click to see the original size)

Detected segments (endpoints in red)
(click to see the original size)

Points with high curvature (shown in red)
(click to see the original size)

Circular arcs (in red) detected on thinned image
(click to see the original size)

Final output with circular arcs shown in red
(click to see the original size)


© Partha Bhowmick (August 2012)