Bobkov A.V. - Image registration in the real time applications, страница 6

Now the edge-based shape matching is a widely usedapproach with well-developed theory – see, for example, [Nack, 1997] and[Mediony and Nevatia 1984].Chain codes. Another simple form of boundary representation are chaincodes, proposed by Freeman [Freeman,1974]. Chain codes allow approximatingthe contour by a sequence of horizontal, vertical and diagonal steps. Beginningfrom a starting point on the contour, a nearest edge pixel is selected and includedto the encoding. When these points are joined together, they form a polygonalapproximation of the shape boundary – a chain.

The chain is completely specifiedby a starting point and the sequence of directions required to follow the chain.A more complex form of chain codes was proposed by Parui and Majumer[Parui et al, 1983] in order to perform a symmetry analysis. The shape boundary is23represented in hierarchy: higher level is rough description of lower number ofelements while a lower layer provides a more sharp and exact description.Chain codes find a wide application in computer graphics systems since theyprovide good shape approximation. But chain codes are not used in a real worldapplication since they have a lot of disadvantages. Chain codes provide a widedescription that is hard to use and process.

The description is non-uniform since itdepends on a start point selection. The whole code is sensitive to noise andrequires an enclosed contour.Boundary approximation techniques. Another representation that is similarto chain codes is a piecewise linear approximation of a boundary [Pavlidis,1975],[Ramer, 1972] [Rosenfield et al 1973], [Davis, 1977]. Approximation can be doneeither by looking for the boundary segments that are well fitted by lines, or bylooking for break points as boundary segments of high curvature.

A furtherdevelopment of piecewise linear approximation is given, for example, in[Bengtsson and Eklundh 1991]. Another paper, [Lagunovskiy, 1997] proposes anapproximation-based approach that allows uniting the linear pieces into globallinear features.And further popular method is approximation by splines. An overview ofthis method is given in [Ikebe and Miyamoto 1982]. Splines provide a moresmooth approximation.The disadvantages of approximation techniques are appropriately the sameas chain codes: the same shape can have a significantly different descriptions; thedescription size is still large and contains a mix of global and local features.Salient features.

An approach that has no such a disadvantages is a boundaryshape presentation as a set of global features: line segments, arcs, polynomialcurves etc.. Such a presentation is less exact, but it provides robust and uniformshape representation that is easy to obtain process and analyse. The representationhas no exact information for the backward shape restoration, but it providescompact and reliable shape description.Representation as a set of global linear features may be obtained either bycollecting small line pieces into one or by global detection. The line detection willbe examined further.

Global lines seem to provide good representation due to itsuniversality (many objects have linear features or features that can be roughlyapproximated by lines) and ease of obtaining and using the description.Representation by circles and arcs is more complicated since the arc is amore complex object than lines. This representation is usually used if it is knownthat an image will always have such features. This presentation is more exact, buttypically the algorithm of arc detection is slower and less robust than that of linedetection. This representation can be a good addition to a line set representation.One more feature that can be used in boundary representation is a highpower curve such as a parabola or Bezier curve. This can provide an exact contourapproximation by a small number of curves, but it cannot provide a uniformpresentation: one object can be described in a many ways, so it will be hard tocompare or distinguish objects.24Point features.

Another object group that can be used for representation ispoint-like features. There are, for example, centres of arcs and circles, points ofmaximum contour curvature, line crossing points and some application-specificobjects, for example – special marker that is used in cartography and medicalimaging etc. These features do not preserve all the information about an originalshape, but allow simple and reliable image registration.One of the most important point features are corners.

Corners can beconsidered either as points of maximum boundary curvature or curve interceptionpoints. Corners provide very simple and reliable image registration algorithms. Asurvey of corner detection techniques is given in [Rohr, 1994].The main disadvantage of an approach based on point feature matching isthat the point features are not universal and they may be simply absent on animage.Elementary shapes. It is possible to present the boundary by more complexprimitives – as a set of corners, stripes and rectangles etc. These features can beeasily detected and processed.

The main disadvantage of such an approach is itslow universality: a selected feature can simply be absent on the image, or it canpresent in a qualities that is not robust enough for further processing. Nevertheless,these features can be described as a combination of global lines and can be usedsuccessfully as additional to a linear representation.1.2.2.2.3. Region-based representationThe region-based representation uses information about both object shapeand object colour (brightness, texture etc.). This representation is less compact buthas significant advantages on high noise image processing, when reliable edgedetection becomes almost impossible.

The region-based representation is bettersuited to represent objects like buildings [Huertas et al 1988], [Hsieh et al 1992],forests, town areas [Roux, 1996], lakes [Ghostasby et al, 1985], [Holm 1991] andso on.One of the main problems of the global shape representation is objectseparation each from other.

This is a complex task when colour, shape and positionof objects are unknown. Objects can be overlapped or can drop shadows on eachother. A comprehensive review of image segmentation methods is given in [Pal,1993].One popular technique to separate objects from each other is clustering[Duda et al, 1989]. It allows solution of the task by collecting information aboutthe distribution of pixel position and brightness.

It determines which pixel belongsto an object by minimizing some measure, for example – minimal square error.Clustering by itself contains a number of difficult problems. For example, itrequires knowledge of the number of objects in the image, the relation betweenlarger object and its parts etc. At the present, these problems are under severeinvestigation.25Moments. Use of moments for shape description was initiated by Hu[Hu,1962].

The zero-order moment is the shape area; first-order moments can beused to determine the shape mass centre; second-order moments (moments ofinertia) can be used to determine the principal axes of the shape. In his paper, Huproposed to use invariant moments that do not depend on the position, orientationand scale of the shape. The advantage of moment methods is that they aremathematically compact. The disadvantage is that it is difficult to correlate highorder moments with a shape features. Furthermore, local information and shapefeatures cannot be detected. Targets having an irregular structure require thecomputation of high order moments for recognition, which require a lot ofcomputations and cannot provide a high accuracy. Another important disadvantageis that if the shape is partially occluded, then the moments of the resulting imageare considerably different from those of the unoccluded shape.Fourier transform.

The 2D spatial Fourier transform is another well-knownmethod of the shape representation, which has a highly developed theory and muchwell tested software. Fourier shape models can be made rotation, translation andscale invariant, and it can be good alternative to the moment approach. Thedisadvantage is computational extensiveness and impossibility to describe localfeatures of the shape.

As in a moment approach, Fourier transform of partiallyoccluded shape radically differs from the unoccluded shape.Ribbons. The most popular and the most studied global space domainmethod is the Medial Axis Transform (MAT), also known as prairie fire transformand skeleton transform. MAT method was originally proposed by Blum [Blum1967]. The idea of this approach is to represent the shape using a graph and hopethat the important shape features are preserved in the graph. The MAT descriptionincludes the shape symmetric axis (a skeleton) and generating object. The centre ofthe generating object moves along the axis and changes in size, producing anoriginal shape.