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

For example, in the case of line segments these characteristicsare line orientation and size. This allows putting additional limitations to a possiblematching of structural elements (e.g. line orientation and size provides limitationon possible values of rotation and scale).When the image structural elements are used to estimate the matchingquality (1.4), the possible correspondence between elements of both images canprovide additional information to speed up the image matching process.In the common case, it is required to know only one pair of appropriatepoint-like features on both images to estimate the position of one image onanother, whereas two feature pairs provide additional information about rotationand scale.

But this approach does not work in practice, because each feature canhave more than one candidate feature on the other image (features, usually, cannotbe uniformly identified), some of features can be invisible on the image and othershave no pair (if a feature is occluded by another object or cannot be detected due to29low brightness or poor visibility conditions).

So the matching process must takeinto account as many features as possible.There are three common searching strategies known for the feature matching[Brown 1992]:-Exhaustive search-Graph matching approaches-Clustering approach, or search using Hough transform (HT)1.2.2.3.3. Exhaustive searchIn this case, for each possible set of transformation parameters, the image istransformed and then the criterion of matching quality is calculated. The maximumquality criterion value is looked for, and its parameters are the desired objectposition.This approach is simple and very reliable, but it requires significant amountsof computation, which depend both on the image size (via quality criterioncalculation) and on the search space volume.

The approach can be useful when theamount of possible positions is small, or images are small, or the quality criterioncan be easily obtained – for example, if the image is binary.The approach is widely used in observe extreme-correlation systems, whenthe space transformation is limited by parallel shift group and special devices areused to compute a correlation quality criterion. If other transformations are present,or image size is significant, this approach proves difficult to work in real time.1.2.2.3.4. Graph-oriented searchAn alternative to the exhaustive search is a graph-based approach. It can bedescribed as follows.

Let us suppose both the observed image and sample arepresented as a set of features. Each pair of features that correspond to each otherproduces a space transformation, which transforms one feature to another. So it isrequired to find a transformation that leads to the deriving of the maximummatching of features. A systematic way to represent this is to construct a matchgraph, in which the nodes represent feature assignments, and the arcs joining nodesrepresent pairwise compatibility between assignments.

To find the best match it isnecessary to find regions of the match graph where the cross-linkages are maximal.A complete subgraph, where all pairs of nodes are connected by arcs, iscalled clique. Hence, the maximum cliques are taken as it leads to the most reliablematches between the sample and observed image. One of the first approaches ofgraph-based feature matching was proposed in [Marr et al, 1979].A main problem of the matching graph approach is that there is anexponential growth of required computations as the number of features increases.The quantity of all possible feature combinations that define a search tree dependsexponentially on the amount of structural elements. The task of looking for a30subgraph in a graph belongs to NP-complete tasks class (like a travelling salesmantask).

For such tasks, there is no known means of ensuring that they are executedin polynomial time. Thus, given a graph of n nodes, it is not known how to find themaximum cliques in a time that is bounded by a polynomial of n, currentindications being that it is at least exponential in n. For example, to process a graphof n nodes, it is required to check about 2n nodes in it. So the exhaustive search isacceptable only in a limited group of tasks.More popular searching methods are the stochastic methods or finitesearching methods like dynamical programming, annealing methods, geneticalgorithms etc.In [Barnard et al 1980] a solution to the correspondence problem based onthe relaxation algorithm is proposed.

Further, the shape registration problem hasbeen formulated as optimisation models and solved by appropriate mathematicaltechniques. An example can be Lagrangian relaxation [Mundy et al. 1992], [Nobleet al 1992], [Ventura et al, 1995], gradient-based descending [Chen and Ventura,1995], [Ponce et al. 1992].In [Ullman 1979] the correspondence problem is converted into the problemof finding the maximum weighted cover of bipartite graph, and linearprogramming methods are applied to this graph problem.In [Medioni et al 1984] the matching algorithm is applied to the set of linearfeatures.

Pong [Pong et al 1989] proposed a hierarchical approach based onBarnard’s scheme, which operates in a two stages. Image matching based oncorner points is performed first, providing information for further solving of theambiguities for the correspondence of the edge points.Another popular approach in image registration is dynamic programming. Itallows solving a problem by dividing it to sub-problems. Larger problems aresolved using the best solutions of sub-problem and avoiding redundantcalculations. An example of this approach is [Maitre and Wu 1987] – forregistration of geographic contour with a map, [Milios, 1989] – for shapematching. Dynamic programming requires that data on both images must have thesame intrinsic order, so it can be used in a limited number of applications.All these methods perform cutting of unresponsive search branches toincrease performance.

However, this can lead to the selection of non-optimaltransformation.At the current time the matching graph approach appears to be the maindirection of image matching method development.1.2.2.3.5. Hough Transform strategyThis strategy uses the transformation similar to the HT for figure positionsearch referred above. Feature space is mapped into parameter space. Each featurepair produces a subset of votes in the parameter space, so vote clusters in theparameter space can be used to estimate the transformation parameters.Each pair of corresponding elements on both frames produces a curve in theparameter space.

The interception point of the curves indicates the possible31position of one image on another. The interception point that belongs to mostcurves will have the same co-ordinates as the co-ordinates of the sample positionon the image.If the parameter space has more than two co-ordinates, each pair ofcorresponding elements produce a surface (or hyper-surface), and the amount ofcalculations increases.

However, the amount of computation remains a linearfunction of the number of elements.Such an approach originally appeared in [Ballard, 1982], where HT strategywas applied for edge matching. In further works like [Stockman et al, 1982],[Goshtasby and Stockman, 1985] and further, in [Davies, 1992] the method wasextended for point-like features.Shekhar in [Shekhar et al, 1999] proposes a feature consensus mechanism.The idea of this approach is to collect votes in parameter space separately for eachfeature. The feature consensus mechanism extends the capabilities of HT methodssuch that complex non-rigid local transformations can be dealt with.A comparison of graph-based and HT-based strategies is given in [Davies,1991].

Davies shows that HT strategy is robust and significantly faster, since it haslinear computation complexity in comparison to exponential complexity of graphmatching strategy. However, HT strategy has some limitations. The votes inparameter space forms spread clusters that are hard to process. So the overallaccuracy is low due to a low accuracy in the cluster location. Since all calculationsare performed in the image-like discrete parameter space, additional specificproblems arise related to quantization and cell value splitting. Another problem isthe production of significant amount of false responses.Another, at present unsolved problem is the growth of required computationwhen the number of parameters to be determined is high. The problemdimensionality is equal to the number of transformation parameters.

Davies[Davies, 1990] shows that the problem can be solved by parameter spacedecomposition, but this caused significant loss of reliability and can only be usedin a limited number of applications.However, the fast development of HT theory in the recent past makes itpossible to re-examine the characteristics of these methods by applying newtheoretical results to them.1.3. Line and curve extractionThere are two common approaches to line and curve detection [Leavers1992]. On of them is generating curves from elementary line segments andmerging them into one.

This approach provides high quality contour representationand is widely used in computer graphics and CAD-systems. Another area tracingmethod application is cartography and geographic information systems. Tracing is32a common technique for extraction of some kinds of features from aerial and spaceimages in order to obtain an electronic vectored map. These features can be roads,buildings, agricultural fields, rivers, lakes and even lesser objects like separatecars.The common disadvantage of tracing methods is its low performance andhigh dependence on the image quality.

So tracing techniques are rarely used in realtime applications, and other methods – faster and reliable – should be used instead.Another approach for feature extraction is the use of a global integraltransformation that transforms the image space into a space of curve parameters.After such a transformation a curve transforms into a separate pixel the brightnessof which is equal to amount of points in that curve.

This kind of transformation isknown as the Hough Transformation. This approach provides faster and morereliable feature detection but it has a less accuracy of contour representation.The main directions in which modern development of HT theory occursreflect practical problems that arise in feature detection area. This is a problem ofproper representation selection, reducing of parameter space size anddimensionality, selection of authentic responses in parameter space and someother.1.3.1. Parameterisation scheme selectionThe choice of parameterisation scheme used can directly affects algorithmperformance, since computations for parameter determination take a significantpart of the computation time.

Furthermore, it can also affects to the accuracy ofparameter determination – the size and shape of parameter space, the accuracydistribution in the different parts of parameter space, and, finally, to the ease offurther use for selected presentation.Historically the first parameterisation was a slope-intercept parametricrepresentation [Hough,1962]: y=kx+b. The k and b parameters generates the dualparameter space so that each line l in original (x,y) space produces one point (the“vote”) in the dual (k,b) space.