CONTOURS in Software

Maker Universal Product Code version A in Software CONTOURS

1 5

41515151515

15 15

3 3 3 1 1

5 7 7

the limited set of directions used to represent the tangent at a point This limitation can be removed by using one of the curve representations presented in the following sections Once a curve has been fitted to the list of edges, any of the geometric quantities presented in Section 61 can be computed from the mathematical formula for the curve

The slope representation of a contour, also called the W-s plot, is like a continuous version of the chain code We want to represent a contour using arbitrary tangent directions, rather than the limited set of tangent directions allowed by the chain code Suppose that we start at the beginning of the edge list and compute the tangent and arc length using the formulas presented for digital curves We may plot the tangent W versus arc length s to obtain a representation for the contour in the W-s space The W-s plot is a representation of the shape of the contour For example, a contour that consists of line segments and circular arcs will look like a sequence of line segments in the W-s plot Horizontal line segments in the w-s plot correspond to line segments in the contour; line segments at other orientations in the w-s plot correspond to circular arcs Portions of the w-s plot that are not straight lines correspond to other curve primitives The contour may be split into straight lines and circular arcs by segmenting the w-s plot into straight lines This method has been used by many researchers, and there are several versions of this approach for splitting a contour into segments One may use the w-s plot as a compact description of the shape of the original contour In Figure 63, we show a contour and its w-s plot For a closed contour, the w-s plot is periodic

The slope density function is the histogram of the slopes (tangent angles) along a contour This can be a useful descriptor for recognition Correlating the slope density function of a model contour with the slope density function for a contour extracted from an image allows the orientation of the object to be determined This also provides a means for object recognition

45 -+---,,

-45

1-----+:

: : : -90o --------------":-----------------------------------------------------------------------------

The rest of this chapter will cover four curve models and the methods for fitting the models to edge points The models include: Line segments Circular arcs Conic sections Cubic splines Any fitting algorithm must address two questions: 1 What method is used to fit the curve to the edges 2 How is the closeness of the fit measured Sections 64 through 67 will cover techniques for fitting curve models to edges with the assumption that the edge locations are sufficiently accurate that selected edge points can be used to determine the fit Section 68 will present successively more powerful methods that can handle errors in the edge locations

Let di be the distance of edge point i from a line There are several measures of the goodness of fit of a curve to the candidate edge points All of them depend on the error between the fitted curve and the candidate points forming the curve Some commonly used methods follow Maximum absolute error measures how much the points deviate from the curve in the worst case: MAE = max Idil (65)

Mean squared error gives an overall measure of the deviation of the curve from the edge points:

(66)

Normalized maximum error is the ratio of the maximum absolute error to the length of the curve:

(67)

N umber of sign changes in the error is a good indicator of the appropriateness of the curve as a model for the edges in the contour Ratio of curve length to end point distance is a good measure of the complexity of the curve The normalized maximum error provides a unitless measure of error independent of the length of the curve In other words, a given amount of deviation from a curve may be equally significant, in some applications, as twice as much deviation from a curve that is twice as long If the curve model is a line segment, then it is not necessary to compute the arc length; the distance D between the end points can be used:

(68)

Sign changes are a very useful indication of goodness of fit Fit a list of edge points with a straight line and examine the number of sign changes One sign change indicates that the list of edges may be modeled by a line segment, two sign changes indicate that the edges should be modeled by a quadratic curve, three sign changes indicate a cubic curve, and so on Numerous sign