A fast, memory-efficient and parallelizable arc/circle segmentation algorithm

This paper presents a fast parallelizable arc/circle segmentation method with small memory cost. Firstly the proposed method extracts the edge and skeleton information in image space, records every line fragment in a multi-fork tree as a node which can be processed concurrently. For simplifying the computation, every line fragment is approximated by its piecewise linear polygon (PLG). After that local discrete curvature of each dominant point (DP) on the PLG is calculated and used to estimate the local arc's existence approximately, the arc's parameters are calculated simultaneously. Finally the inveracious arcs would be erased according to the results of arc verification and the arc fragments would be jointed by the arc combination and tracking. This proposed method can deal with the edge rupture, intersection and overlapping conditions. Furthermore it requires small memory space and the parallel processing technology can be implemented to make it faster.