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

However, they are not guaranteed that the best image fitting (i.e.real position) would be found.This strategy and its variations became especially popular in the last time, soits description it is not included in the current research.4.3.3. Hough Transform strategyThe basic idea of HT strategy, or clustering, for the case of point-likefeatures was proposed in [Davies, 1992], and can be briefly described as follows.There is two images presented as sets of point features (specific points,corners, line crossings, circle centres etc.), and it is required to estimate translationof one image in relation to another. In this case, the search space has twodimensions, and can be represented by two-dimensional array of accumulator cells.Each pair of corresponding features on one and another r images producesuniformly defined translation vector (∆X=X2-X1, ∆Y=Y2-Y1) that can be marked insearch space by increasing the accumulator cell A[∆X, ∆Y] value.

Different featurepairs can produce different translation vectors (since inappropriate pairs of featuresare also taken into account), but commonly these elementary translations will begrouped in a tight cluster around the real translation value. So this cluster can beeasily located and its centre can be considered as a desired translation value.Unlike the graph approach, the strategy requires polynomial amount ofcomputation, and it is significantly faster. Amount of computations is proportionalto n2k, where n is amount of features in image representation and k is number offeatures required to produce point feature. In the case when image represented as a92set of point features, k is one. If the lines are used, k will be 2 for pure translation,3 for translation and rotation, and so on.Generic disadvantage of HT-based strategies is significant amount ofmemory required to hold accumulator array.

So direct use of HT is possible onlyfor the case of translation. In the case when complex transformations are present,different methods of a search space reducing can be used. It can be, for example,multi-resolution methods like pyramid approach, or hashing of accumulator array.They can reduce memory requirements, however, they are also require manyadditional computations.4.4.

Hough Transform strategy variationsBasic HT strategy can be easily expanded for the case of non-point features,or case when image deformation differs from simple translation. There are severalways to do this. In this chapter a following extensions will be taken into account.4.4.1. Point features formed from non-point onesThis approach considers forming a multi-dimensional composite pointfeatures from basic non-point features in order to use them according the basicalgorithm. If the lines used as an image representation features, point features canbe formed as a line combination – line pair crossing.

In the case of line segmentstwo more point features became available – corners and line segment middles (linesegment ends cannot be used as point features due to low detection accuracy).It must be also noted that the point feature can be selected in such a way thatit will have no clear geometric interpretation. For example, any line pair willproduce point feature with three co-ordinates (for example – crossing point coordinates and angle between lines), three lines produce four-dimensional object,and so on. Furthermore, these lines can belong to different images. So differentline combinations will produce different registration strategies with differentcharacteristics. Theoretically, it is possible to extend this approach for the anynumber of deformation parameters. However, the amount of objects that can beformed by n lines from the set of N is Nn, and image registration computationalcomplexity became O(N2n).

This is too large for a many real-time applications, andother strategies must be kept in mind.934.4.2. The search space decompositionThis approach considers reducing the search space dimensionality by itsdecomposition. The example of this strategy is our stripe comparison methoddescribed further.

This is a fastest possible strategy, since search spaceautomatically decomposed into a set of one-dimensional subspaces. However, theknown disadvantage of search space decomposition is significant reducingreliability, so the examination of this direction was limited by only one method –stripes comparison.4.4.3. Standard Hough Transformation approachThis approach considers direct usage of non-point features that will producenon-point responses in a search space. Since it is looks like the Standard HoughTransformation (SHT) scheme for feature detection (not for image registrationitself), it will be referred as SHT-strategy.The idea of this strategy is similar to a HT. Each pair of correspondingelements on the both images produce a whole curve in the parameter space insteadof one response, as it was in previous case.

The interception point of curves meansthe possible position of one image on another. The interception point that belongsto most of curves is a most probable coordinates of image position on anotherimage, and it corresponds to an accumulator cell with maximum value.If the parameter space has more than two coordinates, each pair ofcorresponding elements produce a surface (or hyper-surface), and amount ofcalculations also increases, but the amount of computations remains linear functionof elements amount.In comparison to previous case, this strategy requires only n2 computations,and it must be faster for the larger images with larger n values.The known disadvantage of this strategy is a low accuracy due to a lowaccuracy in the curve interception point location.

Since all calculations performedin the image-like discrete parameter space, specific problems arise. Theseproblems have the same nature as ones described in the previous chapter, and theywill be thoroughly analysed.944.5. Exhaustive searchThe simplest solution is based on looking for maximum of quality functionalby exhaustive searching in the shift and rotation parameter space, taking intoaccount the limitations related to the aspects of the object dynamics.The algorithm looks as follows:J*  0;For each admissible rotation φ:For each admissible horizontal shift dx:For each admissible vertical shift dy:- Calculate object parameters St (φ, dx,dy) of the current frame for rotation φ andshift (dx, dy);- Calculate a functional of quality J (So,St);- If a calculated functional is greaterthan current maximum J*, then store a shiftand rotation values (φ*, dx*, dy*), and set acalculated value J (So, St) as current J*.It is values (φ*,dx*,dy*) found which are shift and rotation parameters of thecurrent frame in relation to the basic frame.The advantage of this method, apart from its obvious simplicity, is amaximum possible accuracy; the methods described below are less accurate, buthave greater speed.The main disadvantage of this method is the significant amount of surpluscalculations: in the most points J(φ,dx,dy)=0 (no matching objects).4.6.

METHODS OF ENDLESS LINE COMPARISON4.6.1. Line matching based on Hough transformIt is considered that there is a line l1 from the basic frame and an appropriateline l2 from the current frame. The passage l1 l2 generates the whole set ofpossible values of a translation vector L (Fig.4.1).95Fig.4.1. A calculation scheme of translation parametersThus, in the space of translation parameters each pair of lines of the basicand current frames will generate some curve L(p,w) =(p/Cos(w); w).

The crosspoint of a maximum amount of such curves will give a required translation value.Such a method is simple and fast enough and it proves itself in anotherapplications. However, experiments show a curious phenomenon, the idea ofwhich is the following.Due to the discrete nature of the parameter space, axioms of Euclideangeometry are not applicable to discrete lines. For example, distinct parallel linescan intersect, and nonparallel lines can have no cross point (Fig.4.2).

As a result,images with lines of dominant direction will produce maximums at the point ofdominant parallel lines “crossing” instead of crossing points of other lines. Tosolve this problem, another approach of line drawing must be used: each cell,which contains current line, must be marked by a number that is proportional tolength of line segment inside the cell. This process is generally called as aliasing.However, the aliasing still does not allow separating neighbour parallel lines, andthey still will be crossing in some points.The problem becomes especially complex when curves are present insteadof direct lines, as in the current algorithm.

The proper aliasing for curve requiresmany additional computations, and gives less effect.However, this problem can be moderated by proper selection of parametersrepresentation. Further when line segment matching will be discussed, therectangular coordinates for translation parameter representation instead of polarwill be used. They transforms the arctangent curves into direct lines, that alloweasily find the cross points.96Fig.4.2.