Automatic Spline Fitting of Digital Contours at Multiple Scales
This demo presents a novel method based on the Curvature Scale Space technique for automatic fitting of digital contours. It utilises the CSS method to recover curvature zero-crossings and tangent vectors at those zero-crossings which are then used for Hermite curve fitting. Each pair of adjacent curvature zero-crossings are used as control points for each Hermite segment. The tangent vector directions are estimated from a smoothed contour to remove the influence of noise. The tangent vector lengths are estimated through an iterative procedure which stops when the distance between the contour segment and the approximating spline is minimized.
Applications of this technique include efficient contour data compression as well as Computer Aided Design. It is usually assumed in CAD work that the user will supply all the control points required to generate the desired shapes. In this case, the user will have to start the design work from scratch. However, often the user may wish to start from a known shape which exists in digital form and modify that to obtain the final desired shape. The proposed technique will enable the user to obtain a spline approximation to that starting digital shape. The control points can then be adjusted by the user to produce the desired shape.
As the CSS method generates a multi-scale description of a 2-D contour, the spline fitting can also take place at multiple scales.
In the multi-figure below (Africa), the upper-left figure corresponds to sigma = 3, the upper-right figure corresponds to sigma = 6, the lower-left figure corresponds to sigma = 12, and the lower-right figure corresponds to sigma = 25.
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
When all Hermite curve segments have been fitted, the total Approximation Error is defined as the mean of the average distances for all the Hermite curve segments. Furthermore, Compression Ratio is defined as the size of the data after compression divided by the size of the original data.
Contour data compression can be carried out at multiple scales. This allows the user to find an appropriate trade-off between approximation error and compression ratio. Clearly, reducing the approximation error would also result in less compression and more accuracy whereas allowing the approximation error to rise would result in more compression and less accuracy.
The graph of compression ratio as a function of approximation error can be smoothed to remove noise and small fluctuations. The bending point of that function after smoothing can then be defined as the largest maximum of its second derivative. The bending point can be considered as the boundary between the mostly vertical and the mostly horizontal segments of the graph. It can be used for automatic selection of an optimal scale for contour data reconstruction. As a result, the user will not have to set any parameters in order to use this technique.
The figure below shows the graph of compression-ratio as a function of approximation-error for the spline reconstruction of Africa.
The figure below shows the graph of compression-ratio as a function of approximation-error for the spline reconstruction of Hokaido.
The figure below shows the graph of compression-ratio as a function of approximation-error for the spline reconstruction of carpet design.
For further details about this work, see: Proc Eurographics-2000 and Proc ICASSP-2000.
F.Mokhtarian@ee.surrey.ac.uk Dec 2001