Bobkov A.V. - Image registration in the real time applications (779134), страница 17
Текст из файла (страница 17)
So the exact direction of a pixel can be usedinstead the approximate gradient direction. The main drawback of this approach isthat the several pixel pairs can be processed instead of one gradient value, butgrowth of accuracy is significant, and such an approach can be used in practicalapplications.76Fig.3.9. Counter cell structureThe modified algorithm of line segment extraction will look as follows.There are map of gradient magnitude |G| and phase F, empty list L of detected linesegments and array C[ρ,ϕ] of detector cells. Each cell is a structure with a fieldshown on Fig.3.9.
At the first moment all fields filled by zeros.I.For the each pixel (x,y) with brightness gradient (gx,gy):1.Determine the sector on image, where the some other pixels of a currentline probably can be found.2.For each edge pixel (x1,y1) from this sector:2.1.Calculate the line parameters (ρ,ϕ) and look for counter cell C[ρ,ϕ]2.2.If the cell is free, store current pixel (x,y) as a begin and end of a newsegment, and go to step 2.2.3.If the current pixel (x,y) is near to one of stored segment ends, this endmust be corrected, and counter field increased; then go to step 2.772.4.If the current pixel (x,y) is far from any stored segment ends, then thecell content must be moved into list L, if the segment is long enough, and currentpixel (x,y) stored as a begin and end of new segment.
Then go to step 2.II. Move all long segments from detector cells C to a list L.III. ”Turning” the segments with direction in quarters I and III:if L[i ].ϕ ∈ [0..π 2] ∪ [π .. 3π 2] then exchange L[i].Ymin and L[i].Ymax3.6.3. Performance of proposed algorithmCalculation time is easy to determine from the algorithm scheme. For eachedge pixel a line parameter <ρ,ϕ> must be calculated, and this pixel must bechecked if it is a new segment end. According to (3) and (4), calculation of ρ andϕ requires:- An integer operations: 4 multiplication, 2 addition and 1 dividing;- Float point operations: 4 multiplication and 2 addition;- Transcendental functions: 1 arctangents and 1 square root;Ends processing require 4 integer comparisons;For processor that was used1 (Durontm750, 100MIPS/2MFLOPS, virtual8086 mode) total calculation time would be:T1 = 2.54*10-5 – time of ρ and ϕ calculation per each pixel;T2 = 0.4*10-7 – time for ends comparison per each pixel;ε = 100% * T2 / (T1+T2) = 0.15% – fraction of comparison in totalcalculation time.3.6.4.
Gluing of line segmentsAs was noted before, the parameter space discretezation produces somenegative effects. One of them is line splitting. If the line direction cannot bepresented exactly in the parameter space, such a line would be splintered into oneor several sets of parallel lines with rounded value of the normal angle (Fig.3.10).The same problem can arise also due to contour curvature (when contour is reallynot a direct line but it is required to approximate it) or when contour width is morethan one pixel (or, more generally, when contour pixels cannot be exactlyapproximated by a single line).1This processor was available at the early beginning of this work, and now it is looks old and slow.
Furtherwe have used more powerful hardware; however, all results were rescaled for this processor to represent data in acommon basis. It is impossible to predict the speed of progress; so we placed the results in a form suitable forextrapolation to any system of known performance.78Fig.3.10. Example of line splittingThe problem is that the restoration of a source line from a set of splits is avery inexact when the normal representation of a line segments is used.
But theproposed approach operates with end co-ordinate representation, and this allowsthe development of an accurate and effective gluing algorithm for splits.All line splits can be classified in two groups. The first group is splits ofdirection near to an original line. This group contains most important information.All other splits form a second group. They are less important and can be ignored.The use of normal parameters will not provide an ability to look for splitssince segments of same parameters can be situated in different parts of the image.Instead of this, an approach based on line segment end co-ordinates can be used.The two splits that belong to one line can be displaced one from another inperpendicular and co-axial directions.
The shift in coaxial direction can berelatively large, and can be caused by gaps on a contour, which is caused byoverlapping by another object, bad image quality or missing a part of a contour atthe thresholding stage. The shift in perpendicular direction is limited by values of2-3 pixels. This shift can be estimated via the distances from the ends of the shorterline segment (split) to a line passing through the larger segment (base line):L=a2 −(a 2 − b 2 + c 2 ) 24c 2where a and b are the distances from end of split to a appropriated ends ofbase line segment,c is the length of the base line segment.If the distance L is less than the critical value of 3 pixels the current segmentis considered as a split of the base line.The shift value S in coaxial direction can be estimated as a projection ofmaximum end shifts to a direction of the base line:S 2 = ∆ X 2 + ∆ Y 2 − L2where ∆ X and ∆ Y are the difference between co-ordinates of appropriateends of the current and base line segments.Due to a strict limitation to L value, it can be avoided:S2 ≈ ∆ X 2 + ∆ Y2Another principal question is whether the current line segment is a split ofbase line, or it is the far coaxial separate line segment.
The segment is consideredto be a split if one of its ends situated between the ends of the base line segment(with precision ε ), and the following condition must be true for the any of the endsor for both of them:79where (X,Y) is a end co-ordinate of a current segment,( X 1 , Y1 ) and ( X 2 , Y2 ) are the minimum and maximum co-ordinates of a basesegment.The gluing algorithm can be described as follows.- The first pass is a first group processing. The line list must be sortedaccording to line length (or alternatively, according to amount of edge pixels thatbelong to the line, if this statistics is available). Then each line of the list isprocessed. Potential splits for each line are found, checked and glued, if required.The glued segments, of course, are removed from the list.
In such a way, eachsegment pair that has equal brightness gradient direction γ and normal length ρ iscompared. If one of the end pairs is situated nearer than the required distance,such a pair considered as one broken line with end co-ordinates equal toappropriate maximum or minimum from both sets. If both ends coincide then aline splitting is considered.
The correcting procedure is the same.- The second pass is processing of the second group. For each line from listpotential splits are looked for. The line is a split of the selected line if it has near γparameters and its line ends situated near from the main line. Such splits must besimply removed.The main known problem of the described gluing algorithm appears whenthere is an object on the image that produces line sets similar to the splittingpicture (i.e. set of long parallel lines). In this case a whole set of parallel lineswould be replaced by one line of the same direction in the middle position.
Sincethe values of maximum and minimum end co-ordinates are used to restore anoriginal line, all restored lines will look like rotated by a small angle: both endswill be shifted by a couple of pixels, but in different directions.The gluing operation allows reducing the amount of segments to 20-45%without loss of information. Gluing effectiveness depends mainly on the type ofimage, quality of contour pixel detection and the total amount of lines extracted.3.7. ExperimentsIn order to determine the characteristics of the proposed method of linesegment detection, a series of experiments have been undertaken.
The task is toexamine both common characteristics (performance, accuracy and reliability), andadditional characteristics that is specific for this method (metrics selection andminimal curvature radius that can be approximated by lines).803.7.1. Performance analysisOne of the most important characteristics of line detector is a performance.The x86 family processors will be used to calculate the ratio of differentoperations.An “equivalent operation” term will be used as a measure value. It considersall operations that require the same computation time as integer summationoperation – e.g. subtraction, comparison, shift and logical operations. For the x86family an integer multiplication and division requires ten times more computationtime.To simplify the total time calculation, the amount of computations per onepixel will be found at first, and then the results will be obtained for a whole image.As it was described above, the line segment detector must include thefollowing iterations (Fig.3.11).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
