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

Because filter size of 3x3 is usually used in practice and real edgesare far from ideal, the result can be much worse.The error of parameter ϕ determination depends directly on the error in thecalculation of brightness gradient direction and of error that appears due to anglediscretization. The error of ρ parameter calculation is less, and can usually beignored (it is less than one pixel and hence cannot affect the image processingresult).Fig.3.8.

Calculation of error in line segment ends positionFig.3.8 shows a calculation scheme of error in a line segment end position.Due to presence of error ε in normal angle determination, the real end of segmentA will be situated in point A'. Triangles OAB and OA'B' are equal (as rectangularwith both equal legs), so OA=OA'=R and ∠AOA'=∠BOB'=ε. Then the error, δλ,of a line segment end position can be found as the isosceles triangle AOA':73δλ=2R Sin(ε/2),(3.10)where ε is error in ϕ parameter determination,R is distance from co-ordinate centre to the end of segment.Thus, even the brightness gradient is calculated exactly, a shift of line endwould be relatively large (about 1 pixel on the segment size of 64 per each errordegree).

For example, if there is an error of 3o in edge orientation (as in theprevious example) for the images size of 128x128 a maximum error of the endsegment position will be 8 pixels even for an ideal image. For many practicalapplications this value is too large.The second disadvantage of the classical approach is related to the necessityof quantization. When the quantization step is large, an error of parameterdetermination is large too. If the quantization step is small, an interesting effect ofline splitting arises: instead of one separate line a set of parallel lines is detected.These lines have the same pixels but are geometrically different.

An additionalfactor that leads to the splitting can be seen on Fig.3.7: differential filter gives notone exact value of edge direction but a whole set. Each mode of this set wouldgenerate a separate set of parallel lines.The additional negative effect of splitting is the fact that it is impossible todetermine parameters of the original line by analysis of a split set. As a result, thedecreasing of the quantization step causes splitting instead of growing of parameterextraction accuracy.3.6. Proposed method of line segment detection3.6.1. Extended Hough transformationThe main problem of known line segment detectors is that the parametersused for line extraction provide poor line description and vice versa.

The solutionis to use different sets of parameters for the line segment identification and for thecomplete description.At a first look, it seems impossible since a parameter set is used to create adetector parameter space and must be the same both for identification anddescription. The classical approach requires that all description parameters must beincluded into the set of co-ordinates of the search space. This causes significantincreasing the dimension of search space and raises problems related with it, so inpractical applications the use of these additional parameters is usually avoided ifpossible.However, there is another way to take into account the set of additionalparameters. It is required to extend the accumulator cell in such a way that eachcell will keep not only accumulator value, but also all additional parameters relatedwith current line.74The detection procedure will be changed in a following way.

After thenormal parameters are calculated and an appropriate accumulator cell is found, theaccumulator value is increased, and all additional parameters are modified – thecurrent gradient direction value and line end co-ordinates are corrected.Line end correction is a very simple procedure. It is required to know thearea co-ordinates, which completely includes the line. These co-ordinates areminimal and maximum values among all line points of co-ordinate values x and y.The correction of the brightness gradient direction along the line is alsosimple.

A gradient vector is always orthogonal to line direction and parallel to thenormal vector. Its direction is either the same or opposite of the normal. Tocompute the gradient direction, it is enough to introduce a counter that willincrease each time gradient and normal directions are the same, and decrementwhen they are opposite. As a result, a value will be obtained which providesinformation about the prevailing gradient direction. It must be noted that obtainedvalue depends on co-ordinate centre position. So the calculations must use angle ofgradient direction instead of it to provide translation invariance.In such a way another parameters can be calculated – the arc start and endangle, amount and average length of gaps in a dotted lines, and other statistics thatcan simplify the shape detection on the image.We will refer to this approach as Extended Hough Transformation (EHT).

Itis equivalent to a group of HT-like transformations, when each of them correctsonly one line parameter – amount of pixels, one of the end co-ordinates and so on.However, the cell co-ordinates are common for all of them and are calculated onlyonce.What result is obtained? Instead of straight line detection, which isdescribed by the pair of parameters, a procedure of line segment detection isobtained. The classical approach requires 4-dimentional accumulator array,whereas extended HT uses only two dimensions. Reducing the parameter spacedimensionality becomes possible due to the following.

HT includes two processes– object identification and object description. These processes are similar but notequivalent. In the classical HT these processes are united in one, so theidentification feature is also used for object description. However, it is requiredsometimes to use different identification and description parameters. For example,line segment is usually presented in co-ordinate form (via segment end coordinates) instead of normal form, used in classical HT (normal vector, segmentlength and centre).

Normal form provides significantly less detection accuracy:small distortion in normal parameter determination can lead to significantdisplacement of a line segment. At the same time, small distortion in a segmentend co-ordinates cannot cause significant displacement, so co-ordinate form ispreferable. However, it is impossible to provide a HT scheme that can use segmentend co-ordinates as detection parameters, because they are not dependent on edgepixel co-ordinates and brightness gradient.753.6.2. Algorithm based on Extended Hough TransformTo produce a new line segment detection algorithm, two considerations ofExtended HT must be taken into account.The first is that the counter cell can keep not only a counter value (amount ofobject with current parameters) but also any other information that can characterisean object.

This additional information can be used for the accurate and completeobject description. It can be, for example, co-ordinates of segment ends. In practiceit is better to store the maximum and minimum co-ordinates of line segment pixelssince end co-ordinates can easily be obtained from them. In this case the maximumerror of a segment end position is dependent completely on the average width ofthe edge. Assuming that the edge width is one or two pixels, the accuracy of linesegment localisation will also be a two pixels and not dependent on the lineposition on the image, in contrast to existing HT based algorithms.The second idea is that the line segment on an image can be uniquelyidentified by less than four parameters.

For example, two crossing line segmentsthat belong to one line is one larger line segment. Non-crossing segments on thesame line are often one segment with a breakout. In such a way, in much of casesthe line segments on the one line can be considered as one segment and it can beidentified by appropriate line parameters.The problem of such approach arises when the different line segments (e.g.on the different sides of image) belongs to one line.

But another hidden parametercan be used – a number of calculation iteration. Since the image processing goes indefault order (e.g. from the left to right and from up to down), it can be used tomonitor separate segments, which belong to one line. The monitoring can be easyperformed by comparing current pixel co-ordinates and co-ordinates of segmentends stored in the counter cell. If the gap is large enough the current pixel belongsto a new segment and previous segment must be moved from the counter cell to alist of detected segments since all of its pixels are already processed.To increase detection accuracy a following method can be used. Since thegradient direction is known, it is possible to directly examine the pixels, whichprobably belong to a current line. Each gradient value corresponds to a sectorwhere such pixels can be found.