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

This increases the reliably, but in any case anadditional investigation is required. Nevertheless, this simple method shows thatinvoking a line segment end co-ordinates in an image registration process allowsobtaining significant advantages in comparison to endless line usage.4.8. METHODS BASED ON LINE SEGMENT COMPARISONLine segments, in comparison to lines, provide additional information – coordinates of ends – that can be used both for more exact selection of correspondingpairs and for reducing a search space size. This allows significant increasing ofperformance, reliability and even accuracy.4.8.1.

Image registration by line segment pairsThis method will be further referred as Line Segment Pair Comparison(LSPC). The idea of this method is the same as in line pair comparison method:two pair of corresponding line segments on both images produces a pair ofreference points and provides information about projection of translation vector ontwo directions – direction which orthogonal to corresponding pair direction. Ifthese directions are not parallel, it is possible to reconstruct a whole translationvector.When translation vector for the current pair is found, an appropriate counterin parameter space is increased.

When all pairs are processed, the indexes ofcounter with maximum value are most probable co-ordinates of real translation.In such a way, the algorithm of image registration will look as follows:1.Build a list of possible line segment pairs: eachpair consists of line segment on the first image andanother line segment on second image that probablycorresponds to it (each line segment can correspond toseveral line segments on another).2.For each couple of non-parallel line segmentpair:- Calculate the translation vector co-ordinates,- Mark it in the search space.3.Look for a counter in search space that hold amaximum value.

The indexes of this counter are theestimate of the real translation parameters.102Let us examine the algorithm stages more thoroughly.4.8.1.1. Looking for a line pairsThe following notation will be used. Objects of the first image will bemarked by an asterisk «*» symbol. Values that relate to first line pair will bemarked by one prime, to second – by two primes. And the lower index will be usedto mark one of the line segment ends (1 for left and 2 for right). Lower zeroindexes will be used for line normal parameters.

A delta (∆) will mark a differencein co-ordinates of line segment ends, or, in application to normal parameters –difference in appropriate normal parameters of one line segment pair.The line segments of one pair must obey following requirements:1.Requirement of equal direction of the brightness gradient: γ ≈ γ*. Thiscondition means also an equal orientation of line segments.2.Requirement of length equality: (x2*–x1*)2+(y2*–y1*)2 ≈ (x2–x1)2+(y2–y1)2.3.Requirement of pixel amount equality: m* ≈ m. Amount of edge pixels inline segment is determined on the line segment extraction stage.4.Limitations to a translation value.

These limitations are determined frompriory knowledge about task. For example if it is known that the first image iscontained into another, the translation value can be positive only and limited bydifferences in image sizes. In this case lines of one pair must obey the followingconditions: x1* + x2* ≤ x1 + x2, y1* + y2* ≤ y1 + y24.8.1.2. Matching pairsTwo line segment pair suitable for the computation of translation vectormust obey the following conditions:1.Lines must have a cross point. Two parallel pairs cannot provideinformation about translation component that is orthogonal to line direction, andsuch pairs must be skipped. Furthermore, if the angle between lines is not a zero,but it is small, the accuracy of translation vector computation will be low.

In such away it would be better to take into account only pairs with angle between lines ininterval of 300...1500.2.Bindness condition. The correspondence of line positions must remain thesame for both images. The simplest way to check this condition is to use centralpoints of line segments: ∆x2’+∆x1’ ≈ ∆x2’’+∆x1’’, ∆y2’+∆y1’ ≈ ∆y2’’+∆y1’’, where∆y and ∆x are differences of appropriate line segment end co-ordinates. The linespassing through line segments must coincide when translation is performed. Toprovide a line segment overlapping that is not less than a half of its length, it isrequired that the centre of lesser segment pass in position between ends of greatersegment:X1 – (X2*+X1*)/2 > Sx > X2 – (X2*+X1*)/2,Y1 – (Y2*+Y1*)/2 > Sy > Y2 – (Y2*+Y1*)/2,where (Sx,Sy) are the translation co-ordinates.1034.8.1.3. The translation value computationAs in the case of line pair comparison, there is a two line couples (l*’, l’)and (l*’’, l’’).

When translated, line l* goes to l*’, and l” goes to l*”. Then linecrossing point C goes to point D, and translation value is CD (Fig.4.6).If the co-ordinate system origin is placed into point C, then translation vectoris determined by point D co-ordinates, i.e. crossing of lines l’ and l” in the new coordinate system. Equations of these lines in the new co-ordinate system will belook like that:l’ : ∆ρ’ = x Cos ϕ’ + y Cos ϕ’,l’’: ∆ρ’’= x Cos ϕ’’+ y Cos ϕ’’,where ∆ρ = ρ – ρ* is the difference of normal length, ϕ – normal inclinationangle (since appropriate lines of two frames are parallel a priory, both lines hasequal ϕ).a)b)Fig.4.6.

Translation parameter determination using two line pairsIf ∆ρ’ ≠ 0 and ∆ρ" ≠ 0, both line equations can be multiplied by ∆ρ’ and ∆ρ" appropriately:l’ :∆ρ’2 = x ∆ρ’Cos ϕ’ + y ∆ρ’Cos ϕ’,l":∆ρ"2= x ∆ρ"Cos ϕ"+ y ∆ρ"Cos ϕ",Since ∆ρCos ϕ = ∆X0, ∆ρCos ϕ = ∆Y0, ∆ρ2=∆X02+∆Y02, where ∆X0= X0–X0*, ∆Y0= Y0–Y0* – appropriate foot of normal coordinate (X0,Y0)differences, a follow system can be obtained for the line crossing point D(xu,yu): ∆ X 0'2 + ∆ Y0'2 = xu ∆ X 0' + yu ∆ Y0'(4.0) ∆ X 0' '2 + ∆ Y0' '2 = xu ∆ X 0' ' + yu ∆ Y0''The solution of this system will be:104xu =∆ Y0 ' ' (∆ X ' 02 + ∆ Y ' 02 ) − ∆ Y0 ' ' (∆ X ' ' 02 + ∆ Y ' ' 02 )∆ X 0 ' ∆ Y0 ' '− ∆ X ' '0 ∆ Y ' 0yu =∆ X 0 ' (∆ X ' ' + ∆ Y ' ' ) − ∆ X 0 ' ' (∆ X ' + ∆ Y ' )∆ X 0 ' ∆ Y0 ' '− ∆ X ' ' 0 ∆ Y ' 0202020(4.0)20(4.0)This is a desired translation co-ordinate that obeys the conditions ∆ρ’ ≠ 0and ∆ρ" ≠ 0.

Denominators of (4.6) and (4.7) becomes zero either lines l’ and l”are parallel, or one of ∆ρ is zero.In order to raise computation accuracy, these formulas can be rewritten vialine ends co-ordinates instead of normal parameters. The normal co-ordinates canbe expressed from line ends co-ordinates by the following way.For each line segment, a scalar multiplication of normal vector and (∆X,∆Y)vector must be equal to zero since these vectors are orthogonal.

Since the end ofnormal (X0,Y0) belongs to line segment, then for each line segment points – forexample, for the left end (X1,Y1) – the scalar multiplication of normal vector to a(X0-X1 ,Y0-Y1) vector must be zero also (Fig.4.7). In such a way, the equationsystem for normal co-ordinates (X0,Y0) is obtained: ∆ X ⋅ X 0 + ∆ Y ⋅ Y0 = 0 ∆ Y ⋅ X 0 − ∆ X ⋅ Y0 = X 1 ∆ Y − X 1 ∆ YThe solution is:where ν =X 1 ∆ Y − Y1 ∆ X∆X2 + ∆Y2X0 = ∆Y·νY0 = -∆X·ν,(4.0)Fig.4.7.

Scheme of normal parameter calculation using line segment end coordinatesIf line segments inside the pair is supposed to be exactly parallel. Then ∆X* = C ∆X, ∆Y* = C ∆Y, where C is non-zero coefficient. Then:105 X ∆ Y − Y1 ∆ XX * C∆ Y − Y1 * C∆ X  =∆ X 0 = X 0 − X 0 * = ∆ Y ⋅ ν − C∆ Y ⋅ ν * = ∆ Y  1 2−C 12(∆ X 2 + ∆ Y 2 )C 2  ∆X + ∆Y( X − X 1 *)∆ Y − (Y1 − Y1 *)∆ X= ∆Y 1∆X2 + ∆Y2 X ∆ Y − Y1 ∆ XX * C∆ Y − Y1 * C∆ X  =∆ Y0 = Y0 − Y0 * = − ∆ X ⋅ ν + C∆ X ⋅ ν * = − ∆ X  1 2−C 12222∆X+∆Y(∆X+∆Y)C( X 1 − X 1 *)∆ Y − (Y1 − Y1 *)∆ X∆X2 + ∆Y2( X − X 1 *)∆ Y − (Y1 − Y1 *)∆ XDenote: ∆ ν = 1∆X2 + ∆Y2= −∆XThen:∆ X 0 = ∆ Y∆ ⋅ ν ,∆ Y0 = − ∆ X ⋅ ∆ ν(4.0)If the formulas (4.8) and (4.9) are inserted in (4.6) and (4.7), the followingformulae for the translation vector would be obtained:∆ X ′′λ ′ −∆ X ′′∆ Y ′ −∆ Y ′′λ ′ −yu =∆ X ′′∆ Y ′ −xu =pair.∆ X ′λ ′′∆ X ′∆ Y ′′∆ Y ′λ ′′∆ X ′∆ Y ′′(4.0),(4.0),where λ = (X1–X1*)∆Y–(Y1–Y1*)∆X appropriately for the first and secondThe formulas (4.10) and (4.11) depends on line segment ends only.

Thelimitations ∆ρ’ ≠ 0, ∆ρ’’ ≠ 0 are eliminated, and formulas can be used for the linesegments of any position. Other limitation – a line from different pairs must benon-parallel (if lines are parallel, the denominator becomes zero) – is processed onthe previous stage.4.8.1.4. Method characteristicsIn common, the method provides relatively high performance and accuracy.It is also much more reliable than methods described above.