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

The shapes described in such a way are known as ribbons. A goodcomparison of ribbon-like techniques is given in [Rosenfield, 1986] and [Ponce,1990].The MAT approach is computationally realistic, and it produces perceptuallymeaningful primitives. The main disadvantage is that the generation of thesymmetry axes is not a straight forward process and it is not easy to specify how todefine a set of generator shapes.Decomposition. Decomposition is a shape representation as a set ofelementary shapes, for example – triangles, circles or simple ribbon-like objects.Decomposition allows representing the shape as a hierarchical set of elementaryshapes.

The disadvantages are the large amount of objects required to obtain anexact description and the low performance. Decomposition also cannot provideinformation about object texture.Areas of interest. Areas of interest are the specific windows having localmaximum variances, line interceptions, points of local maximum curvature oncontours [Goshtasby, 1988]. Areas of interest include most important informationabout the image, and can be successfully used for image description and shapematching. The main disadvantage of this approach is the problem with a sharp and26uniformly defining the area of interest: an appropriately the same images can havedifferent areas of interest.1.2.2.2.4.

Summary on image representationOne of the most interesting and promising directions of the shaperepresentation is the representation in a form of line segments. The most importantcharacteristics of line set representation are:- Line segments are one of the most common and universal objects thatallow representation of a wide range of shape boundaries.- A shape representation in a form of a line segment set can provide simpleand fast feature extraction and matching algorithms.

This makes it possible to usethe approach in real time systems.- Representation is invariant both for brightness and rigid geometrictransformations. The representation is independent on image brightness since onlycontour shape information is used. The shape information is contained in mutualposition of lines, which makes the description invariant to the rotation, translationand scaling.- Representation provides uniform geometric and spatial relations: Oneshape has only one representation, and vice versa – one description corresponds toonly one shape.- Representation allows description of both image similarity and significantdifferences.- Lines can be used both to bring essential information about shape and todescribe shape details.- And finally, this kind of representation can process noisy and incompletedata.

On the one hand, existing line detection techniques allow the finding of lineseven in low quality images with significant noise. On the other hand, line matchingtechniques provide reliable image registration even when a significant part of thelines are distorted or lost.However, line representation has its own problems that must be solved toprovide fast, accurate and reliable image registration.Extraction of a set of linear features usually requires the additional step ofboundary pixel detection. This is a critical step. On the one hand, its precision andreliability directly affect line extraction and matching.

So if the precision orreliability is lost on this stage, it is impossible to restore them at a further stage. Onthe other hand, edge detection can deal with an intensive raw image of large size,so only a limited selection of tools is available to provide real-time processing.Another problem is providing an acceptable trade-off between accuracy andperformance at the line detection stage. Exact methods have a low performancewhereas fast methods cannot provide enough accuracy. So it is required to select abalance between accuracy and performance of the line detector.Final problem is the performance of the line matching algorithm.

The linematching approach provides good performance in comparison with other methods,27but the amount of computation grows fast with an increasing amount of lines in thedescription. The problem is that lines are non-point features, as is required formatching. To obtain a point feature, lines must be combined into pairs to provide areference point (for example – line joining and crossing point), but it is possible forthe amount of line pairs to be too large. So it is required to search for a moreeffective line matching method.1.2.2.3. Optimisation strategyAn optimising strategy can consists of two elements – the quality criterion ofimage matching (optimality criterion) and an optimising algorithm whichdetermines a search order in parameter space.1.2.2.3.1.

Optimality criterionAn optimality criterion depends on selected key elements. The aim foreffective optimality criterion selection is to reduce the influence of brightness andgeometric distortions.Since the main parameters of the elements are co-ordinates, the least-squaresmethod is often used (1.4). This equation can have additional items, if structuralelements have also non-co-ordinate characteristics, e.g. the size or orientation.Furthermore, since some elements on the image can have no pair, an optimisingcriterion must include a special item to count a number of matching items.If the key elements are contour pixel, the optimality criterion can be taken asa distance map.

Distance map D(x) is a reflection of contour pixels to an imagespace:D( x′ ) = min{|| x′ − xi′ ||}x∈ I1,(1.7)and appropriate optimality criterion is:C3 ( x ) =N∑i= 1D 2 ( g ( x))(1.8)The criterion (1.8) can be generalised for the case when the edge orientationin contour pixels is known. Edge orientation can be obtained from the brightnessgradient direction in that point.

This allows finding a real space transformationmore accurate and reliable.If the proper feature-specific is selected or features are point-like, the leastsquare or correlation criteria can also be used.A least-squares criterion is widely used in the area-based methods. In thiscase the sum of brightness difference squares is minimised (1.2).Instead of a least-square criterion, a cross-correlation function is often used[Pratt 1978]. The maximum position of cross-correlation function defines theoptimal translation between images, and provides a pair of control points toperform matching.

The main advantage of such an approach is the ability to28calculate a cross-correlation function using fast Fourier transformation. Theamount of operations required will be reduced from N2 in the case of least squaresto N*log2N.1.2.2.3.2. Optimisation algorithmSince the optimisation criterion has a many local extremes, it is required toproduce an optimisation algorithm able to find a global extreme.

In the commoncase, the global extreme can be found by reviewing all its values. This iscomputationally extensive procedure; so other methods must be used wheneverpossible.If the optimising criterion has a correlation nature, then gradient methodscan be used. A set of partial derivatives are calculated at the current point, thedirection of quality increasing is determined, and the next point on this directionbecame a new current point. Such an approach allows examining only a smallnumber of pixels, but it requires a criterion for which the gradient can becalculated.

Furthermore, it requires a start point to be situated near to the globalextreme position. If this condition fails, the local extreme can be found instead.The optimisation algorithm must provide a compromise betweenperformance and probability of reaching the global extreme. One way to do this isto use methods of changing resolution, or pyramidal methods. The idea of thesemethods is to use a whole set of images with resolution growing from rough tosharp.

Each iteration uses results of the previous iteration. Since the number ofpixels on the rough image is significantly lower, searching requires less time. Onthe more sharp images a search space is examined only near the point found on theprevious step. Furthermore, since noise usually has a high-frequency spectrum, it issuppressed on the low-resolution images, so the reliability of image registrationincreases.Using additional characteristics of structural elements can also provide asearch limitation.