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

The method drawbackis that the amount of computations grows as a fourth degree of line segmentsamount for pure translation, sixth – for translation with rotation and eighth for awhole isometric group. When amount of lines is relatively small (about 100 perimage), the performance is high enough.

But it can be a serious problem whenlarger line amounts are processed or when additional transformation parametersmust be found.To avoid these problems, a next method was developed. It requires amountof operation growing only as a second order of line amount.1064.8.2. Image registration by line segmentsThis method will be further referred as Line Segment Comparison (LSC).The idea of this method can be described as follows. For each pair of probablymatching line segments, for each possible transformation, an amount of linesegment pixels are marked, which will match for this transformation.

When allpossible pairs and transformations are examined, the parameter space will be filledby amount of line pixels, which will match if the transformation with currentparameters would be performed. The parameters that provide a maximum amountof matching pixels, as before, are the most probable parameters of realtransformation.It is easy to note that most of transformations cannot provide common pixelsof two line segments, and only remaining transformations must be actually takeninto account.In such a way, for each pair of line segments (one – from first image andanother – on the second) following actions must be performed:-Determine,whethertheselinesegmentscancoincide, taking into account the limitations to thesearch space.-Determine the set of transformation parametersthat can cause the line segment matching.-Determine the amount of coinciding pixels of linesegments for transformation parameters found, and markthem in the search space.Let us examine these actions more thoroughly.The possibility of line segment matching is determined as it is describedfor previous method.4.8.2.1.

Determination of transformation parametersIt is easy to found that all translation parameters that provide line segmentmatching are situated on the line segment, which connects the AD and BC vectors(Fig.4.8). On the BC and AD translations the only one pixel pair will match(B=C or A=D appropriately). For other translations, belonging to this line segment,the number of matching pixels will be greater.In such a way, the task of translation parameters calculations can be reducedto a building of BC – AD line segment in search space.107Fig.4.8. Translation parameters calculationFig.4.9. Scheme of matching pixel amount calculation4.8.2.2. Determination of matching pixel amountFirstly the case AB<CD will be examined.

The point A moves from A1 toA4=D position (Fig.4.9).A1A2 segment: when AA1, the point B goes to point C and it is only onematching pixel. While point A moves to C, the amount of matching pixels growsuntil reaches a maximum – a size of AB. This happens when point A reaches pointC(A2 position).108A2A3 segment: when point A situated between A2 and A3, whole AB linesegment situated inside CD.

The amount of matching pixels is maximum and equalto AB size.A3A4: segment: when point A passes A3 position, point B passes the D andbecame outside the CD line segment. Amount of matching pixels begins reducinguntil reaches the minimum – one pixel. It happens when point A goes to D (A4position), and it is only one pair of matching pixels.For the case of AB>CD the calculations are appropriately the same, butintervals of pixel amount increasing and decreasing are changed. Amount of pixelgrows when point A moves from A1 to A2. At this time point B moves from C toD.

On the segment from A2 to A3 amount of pixels remains constant, till point Areaches C. On the segment from A3 to A4 (from C to D) amount of pixels decreasestill became one.In the case AB=CD the (A2,A3) interval is empty. This case can be reviewedas a particular case of any of the variants above.In such a way, the amount of pixels in search space is a trapezoid with awidth equal to size of lesser line segment.4.8.2.3. Drawing a trapezoid in the search spaceThe search space can be represented as a rectangular array. The arrayindexes are the translation parameters, and values are amounts of matching points.The base of trapezoid is a line segment that is build up on the AB and CD vectors.It is obviously impossible to exactly build any desired line in the search space ofthis type, and approximate methods must be used.

The task is to find array cellsnearest to desired line segment, and to fill them by values of matching pixels.There are two approaches for a line segment building on the orthogonalgrids: the Brezenham approach and using of independent parameter. TheBrezenham approach is faster, but less accurate. But in this case the accuracy willplay a primary role. Furthermore, the independent parameter can be also used forcomputation of pixel amount.The generation of line points based on independent argument can bedescribed by formulas:xi = x 0 + ∆ x ⋅ p iy i = y 0 + ∆ y ⋅ pi ,where ( x0 , y 0 ) is a co-ordinates of start point (point A1 in this case), pi isindependent argument.The diapason of argument p changing is diapason from zero to a maximumdifference of line segment end co-ordinates. In this case integer values of argumentwill generate a line without gaps and overlapping pixels (since one of co-ordinateswill be also integer value).The line segment building can be performed using recurrent formulas:xi + 1 = x i + ∆ xyi+ 1 = yi + ∆ yThe co-ordinates of drawing pixels are rounded to a nearest integer value.109The argument p can be also used for a trapezoid building:On the A1 A2 segment the following value is added to a segment cells:| AB |⋅ pimax(| x( A2 ) − x( A1 ) |, | y ( A2 ) − y ( A1 ) |)On the A2 A3 segment the constant value | AB | is added to a segment cells.And on the A1 A2 segment the following value is added to a segment cells:| AB |⋅ (max(| x( A4 ) − x( A1 ) |, | y ( A4 ) − y ( A1 ) |) − pi )max(| x( A2 ) − x( A1 ) |, | y ( A2 ) − y ( A1 ) |)4.8.2.4.

Method characteristicsThe method characteristics are appropriately the same as in previous case. Inthe series of experiments that are described below, the method shows itself as littlemore accurate, has the same reliability, but little slower.4.9. Method comparisonCharacteristics of all methods described above are placed into a Table 1. Themeasurements were performed on the following video sequences:Set 1: A moving rectangle. This is a base test, which is used mainly fordebugging purposes. All methods must process it as a necessary minimum.Set 2: The agricultural landscape (fields and a river), which contains a lot ofsimple objects and lines. This is a main set.Set 3: The town landscape (streets and buildings) that contains a lot of tinydetails and curve lines that cannot be approximated by line segments.

This set isuseful to test the algorithm reliability.It can be seen from the Table 1 that only method of line pair comparison andits assessors – line segment comparison and line segment pair comparison – can beused in practice since they provide enough reliability. All these methods have anaverage performance and accuracy. These characteristics can be amplified usingother methods – for example, by angle comparison.Since characteristics of two last methods are approximately the same, theadditional measurements were performed. The aim is investigate the primarycharacteristics of these methods: performance, accuracy and reliability in order tocompare with each other and with other popular methods.110Table 1.The performance and reliability of tested algorithmsMethodExhaustivesearchLine comparisonLine pairscomparisonCornerscomparisonStripescomparisonSegment middlescomparisonComparison ofline segmentpairsComparison ofline segmentsMax.time, s>10ReliabilitySet 1Set 2100 % 100%NotesSet 3100%0.30%––1.5100%90%80%1.2100%90%40%Maximum exactitude.

Unacceptablebecause of low performance.Extremely low reliability. Doesn’twork in the pure state.Acceptable ratio of efficiency andreliability.Doesn’t work for some image types0.5100%70%20%Low reliability0.5100%90%80%0.6100%100%100%High performance and accuracy.Low reliability.Acceptable ratio of efficiency andreliability.0.9100%100%100%Acceptable ratio of efficiency andreliability.4.9.1. PerformanceWhen the LSPC method is used, each line segment pair on first image iscompared with pair on another. The amount of computations in a first method isequal to P1=O(N12*N22), where N1 and N2 are amount of lines on first and secondimages appropriately.The LSC method requires each line segment to be compared with each oneon another image.