A unified scheme for detecting fundamental curves in binary edge images

We present a unified scheme for detecting digital components of various pla nar curves in a binary edge image. A digital component of a curve is the se t of input edge points from each of which the horizontal or vertical distan ce to the curve is at most 0.5. Our algorithm outputs all curve components containing at least k points (k is a given threshold) in O(n(d)) time (if d greater than or equal to 2) and linear space, where n is the number of points, and d is a measure that ref lects the complexity of a family of curves; for example, d = 2, 3 and 5 for lines, circles and ellipses, respectively. For most of the popular familie s of curves, our only primitive operations are algebraic operations of boun ded degree and comparisons. We also propose an approximate algorithm for co mputing an approximation solution with error ratio epsilon = 1 - alpha (cal led an or-sensitive solution), whose time complexity is O((t/epsilon)(d-1) n), which is very efficient if the threshold-ratio t = n/k is small. (C) 20 01 Elsevier Science B.V. All rights reserved.