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

Possible forms differ bydescription method performance, ease of further processing, descriptioncompleteness and the overall number of objects required for representation.The simplest way is to present a contour as a set of edge pixels. This wayprovides easy and fast method to obtain a contour description, but it operates withedge pixels and requires a lot of computation to compare two contours in this form.Another way is to present a contour as a set of curves, e.g. polynoms or arcs.Such a description provides a complete and exact description, uses a small amountof objects, and requires only an average amount of computation.

However, such arepresentation has the problem of non-unique representation: the same contourscan have different representations. This causes a significant complication whenattempting to compare contours.One more approach is to approximate the contour by a set of line segments.On the one hand, lines provide a unique contour representation, can be easydetected, processed and compared.

On the other hand, such contour representationis less accurate and less complete. For example, it would be hard to representimages that contain circles of small radius.Another approximation is to present a contour as a set of corners and linesconnecting them. The use of corners causes a significant increase in comparisonperformance due to corner properties and their small number. But thisrepresentation is even less accurate than line approximation. Another problem isthat a contour on the raw image can have small number of corners (or not evenone), and the comparison algorithm will fail.In such a way, curves and arcs are hard to detect, hard to compare, butprovide a most complete description.

Line segments are easy to detect, average tocompare, and provide average accurate description. Corners are easy to detect(when lines already found), easy to compare, but they provide poor description.So the contour representation as a set of line segments looks more preferablethan other methods.673.2.

Line detectionMany modern methods of line detection are based on the HT. Thistransformation allows converting the image pixel space to space of line parametersby such a way that local maximums in parameter space correspond to lines in theoriginal image. It is convenient to use a length ρ and angle ϕ of normal vector to aline as this line parameter. Appropriate line equation can be present in a form:ρ = x Cos ϕ +y Sin ϕwhere (x, y) are co-ordinates of points belonging to this line.A scheme of normal parameters (ρ,ϕ) calculation is shown on Fig.3.1.Fig.3.1. Scheme of calculation of normal parameters (ρ,ϕ) to a lineFig.3.2.

Scheme of line detection68Normal to a line which contains current point (x, y) with brightness gradient(gx, gy) crosses this line in point (x0, y0):x0 = ν * gx(3.1)y0 = ν * gy ,(3.2)22where ν = (x * gx + y * gy) / (gx + gy ).Then normal length ρ and angle ϕ is:ρ = (x * gx + y * gy) / (gx2 + gy2)½(3.3)ϕ = arctg (y0/x0)(3.4)The algorithm of line detection may be described as follows: for each edgepixel (x, y) with brightness gradient (gx, gy) according to (3.3) and (3.4) a normalparameters (ρ,ϕ) are calculated, and appropriate counter C[ρ,ϕ] is increased by one(Fig.3.2). After all pixels are processed, maximum counter values C*[ρi*,ϕi*] willrepresent line segments on the original image.

Once such maximums are found,their co-ordinates (ρi*,ϕi*) are considered as required line parameters.3.3. Arc and curve detectionObjects like arcs, curves and line segments can be also detected using GHT[Leavers, 1992 b]. In the common case, the GHT allows the detection of theparameters of any curve if its analytical description is known. The calculationscheme is the same: for each contour pixel, with known brightness gradient value,parameters of appropriate curve are calculated and accumulator call in parameterspace is increased. After that, greater values of accumulators will correspond tocurves to be detected.The main difference between lines and other curves is that the line requiresonly two parameters to be uniquely described while all other curves require threeor more.

Every edge pixel with known gradient provides information only abouttwo parameters. For example, each edge pixel provides information about a set ofcircles that can contain it. Circles can be of different radius, but their centres lie onone line (Fig.3.3).69Fig.3.3. Scheme of circle detection. Each edge pixel provides informationabout a set of circles that can contain it. Circles can be of different radius, but theircentres lie on one lineIn the case of lines, every edge pixel allows calculation of a point inparameter space that uniquely characterises the line passing through the pixel.

Inthe case of curves, every edge pixel does not allow the calculation of appropriatecurve parameters exactly. Instead of this, it provides information about a curve inparameter space, and one of the curve points is a parameter of the original curvepassing through the current edge pixel. When several edge pixels have beenprocessed, they produce a set of curves in parameter space.

If all pixels lie on theone curve, all curves in parameter space cross at one point, and the appropriatecounter in parameter space will be maximum value, and co-ordinates of this crosspoint are the parameters of the curve that has been detected.An algorithm of curve detection, based on GHT, must contain an additionalstep – generation of a curve in parameter space, so the performance is lower. Italso has lower accuracy, since the cross point in parameter space must be found.3.4. Corner detectionThere are two common approaches to corner detection. One of them is localfeature detection and uses the special filter.

It operates with separate pixels using aset of masks like differential or smoothing filters (Fig.3.4). Each mask provides thedetection of appropriate oriented angle [Bretschi, 1981]. Another approach is theglobal feature detection. It looks for corners as interception points of differentlines or curves (Fig.3.5). In the case of the line segments, if co-ordinates of linesegment ends are known, the corner position interception can be found asinterception point of two lines passed through an appropriate line segment.From the Fig.3.5, sincetgα =YA − YBY −Y= A EXA − XB XA − XE70tgβ =YC − YDY − YE= C,XC − X DXC − X Ethen: − X E (YA − YB ) + YE ( X A − X B ) = − X A (YA − YB ) + YA ( X A − X B ) − X E (YC − YD ) + YE ( X C − X D ) = − X C (YC − YD ) + YC ( X C − X D )is a system to determine an angle vertex (Xe,Ye). The solution is:[YA ( X A − X B ) − X A (YA − YB )]( X C − X D ) − [YC ( X C − X D ) − X C (YC − YD )]( X A − X B )( X A − X B )(YC − YD ) − (YA − YB )( X C − X D )[Y ( X − X B ) − X A (YA − YB )](YC − YD ) − [YC ( X C − X D ) − X C (YC − YD )](YA − YB )YE = A A( X A − X B )(YC − YD ) − (YA − YB )( X C − X D )XE =The results of global corner detection are shown on Fig.3.6.4445540o55454455445o54455455490o444555445444o135Fig.3.4.

Masks for local corner detectionFig.3.5. Scheme of global corner detection71Fig.3.6. Corners found on the imageThe first approach is faster and allows finding many of the local angles to befound. On the other hand, the second method is more accurate and reliable, and canprocess images of low quality. Usually a corner by itself cannot be used directly inthe tasks of image comparison or recognition. They serve as additional informationfor further processing.

So the presentation of image in a form of curve or line set isusually available for the stage of corner detection. In this case the second approachlooks more preferable.3.5. Line segment detectionA line segment can be considered as a curve and can be detected by GHT. Aline segment requires four parameters to be uniquely described. The mostcomfortable form is co-ordinates of both ends, but it cannot be used with GHTsince edge pixels have no information about line segment ends. So a lesscomfortable and less accurate form is used.

One of the most popular forms is a setof appropriate line parameters (ρ,ϕ), segment centre position k on this line, andsegment length l.Accuracy of line segment detection with this parameterisation dependsdirectly on discretization step and accuracy of the gradient direction detection.The maximum accuracy that can be obtained using differential filters of practicalsuitable size is about 10 but due to the influence of such factors as image retracewith discretization, natural contour curvature, texture influence etc. is significantlylesser.72Fig.3.7. Illustration of differential filter error originIn Fig.3.7 a sample of ideal edge processing by a 5x5 filter size is shown.For the undistorted edge at 18.42o (arctg 1/3) an exact angle value cannot becalculated at any point. For 2/3 edge points a value of 21.8 o (arctg 2/5) would becalculated – error is 3.38o. In other 1/3 points angle would be 11.31o – appropriateerror is 7.12 o.