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

The scheme with a differential edge detector isconsidered.- frame capture and pre-processing. This iteration provides a framecapture and copy into operative memory. The pre-processing is extraction of oddand even half-frames, and it can be included into frame copying, and do not requirean additional time.- edge pixel extraction. The Sobel filter size of 3x3 requires 20 additions(ten for each mask) per each edge pixel. It is also requires two module calculationsand one division. The value of arctangent can be tabulated as it was describedabove, and one more integer division and comparison are required.

So the totalamount of 20+2+2*10+1=43 operations to process each image pixel.- edge thinning and thresholding. The adaptive thresholding with a blocksize of 12x12 requires one addition and one comparison per pixel. It is alsorequires one multiplication for an each block, or 10/144=0.07 equivalentoperations per pixel. So the thresholding requires 2.07 equivalent operations perimage pixel. On the edge thinning procedure each pixel must be compared withtwo neighbours and one logical “AND” to pixel suppression. In such a way, fiveequivalent operations must be performed to process one image pixel.- line segment extraction. As it was found above, it requires about 500equivalent operations per edge pixel.

Since the edge pixels are about 25% of totalimage pixels, the approximate value of 500*0.25=125 operations must beperformed to process one image pixel.- segment gluing. The time required for a gluing operation depends on thetotal splits amount, and cannot be easy recalculated in a term of the operation perimage pixel. But since the gluing operation deal with small amount of lines, itrequires a relatively small amount of operations, and can be neglected.81Fig.3.11. Scheme of line segment detector82The full detection procedure without line gluing will require 43+5+125=173equivalent operations per image pixel. For the Duron(tm)750 processor in thevirtual 8086 mode (96 MIPS) one frame size of 128x128 will be processed for aT=0.033 seconds (without time for image capturing – 0.04 seconds for standardvideo systems).Results of experimental measurements of performance are shown onFig.3.12.In such a way, the performance of the proposed algorithm is high enough touse it as a base step for a wide range of practical applications.Fig.3.12.

Results of experimental performance measurements3.7.2. A metrics problemWhen the image is captured by hardware, a series of discretization processesare performed. The some of them, e.g. discretization by a time and by a signallevel – are well known in an engineering practice and thoroughly investigated. Butthere is another process – a discretization by a position on the image – must bekept in mind.The image capturing performed by a sequentially obtaining pixel rows andwriting them into a two-directional array.

So each brightness value is banded toplace in the rectangular grid of the digitized image.The several problems arise due to such kind of discretization when detectingthe object edges (Fig.3.13). One of them is that only the lines of 0, 45 and 90 slopeangles can be accurately presented. All other geometric lines will have gaps sincethey cannot pass through the neighbour pixels. If the arctangent of a lineinclination angle is an irrational value (e.g.

30 degrees angle), such a line willexactly pass through only one image pixel (and of course cannot be detected). It83must be noted that the original line can be geometrically straight, but it can be acurve on the image.To avoid this problem, the “line” term is extended: the image line is actuallythe set (may be even infinite set) of geometric lines, and the distance between theline set is less than one pixel. For example, middle line on the Fig.3.13 actually theset of two parallel lines (they are marked by a different brightness). Such anapproach allows detecting the line of any orientation.

Actually the line presentationas a set of geometric lines will raise a line splitting problem, but it can be easysolved.Another problem is that line segments of same size will has a differentamount of pixels (Fig.3.13). The horizontal line segment size of 16 pixels consistsof 16 pixels, while the diagonal segment of the same size will have only 11 pixels (16 / 2 = 11.23 ≈ 11 pixels). The solution of this problem is use of chessboard distanceinstead of Euclidean metrics in all formulas of line detection:L=max(X,Y)In this case all line segments of the same size will have the same amount ofpixels, and detection will be anisotropic.

The Fig.3.14 shows the differencebetween different metrics for a line detector.It must be noted that the space anisotropy problem exists only on the linedetection stage. When the image is already presented as a set of lines, the problemdisappears, and all operation (e.g. line gluing) must use Euclidean metric.Fig.3.13.

An illustration to a metrics selection problem84A)B)C)Fig.3.14. Line detection in different metricsA) Source imageB) Euclidian metric. Lines of horizontal and vertical directions arehighlighted while all other lines are suppressed or brokenC) Chessboard metric is used. Lines of all directions represented uniformly.(Both images contain about 350 of line segments detected)3.7.3. An optimal discretization step selectionThe discretezation step of line normal parameters play a primary role indetection algorithm characteristics, and first of all – to its performance andaccuracy.

So the correct selection of discretezation step is a very important task.The problem of discretezation step selection can be described as follows.The larger the discretization step, the lesser an accuracy of normal parameter85determination, and several different line segments will be detected as one line. Onthe other hand, the lesser discretezation step, the larger computation time, but aftersome level the accuracy grows insignificantly. The small discretezation step causesa line splitting effect: one line splits into a several ones. The danger is that if thesplits are too short they all will be skipped and whole line will be missedregardless of its size.One way to estimate the minimal discretezation step is to examine thenormal parameter space in rectangle co-ordinate system instead of polar system:X 0 = ρ CosϕY0 = ρ Sin ϕThis parameterisation is known as foot-of-the normal scheme [Davies,1990]. This scheme provides better performance and accuracy, but the accuracygoes down near the (0,0) point.

The (0,0) point is a singularity point: it isimpossible to determine a line direction if its normal co-ordinates are zero. It iseasy to see that (ρ=0,ϕ=0) allows to determine a line, while (Xo=0,Yo=0) does not.The normal parameter space in rectangular form will be looks as it shown onFig.3.15. Due to discrete nature of parameter space, the lines will be placed nonuniformly. They will be located on several rays. The amount of rays depends onthe contour detector type.

For the used detectors described in chapter 2 (Sobel 3x3filter and statistical detector) the amount of rays will be 96. The amount of rays isequal to a maximum possible amount of normal angle gradations that providesmaximum accuracy. In the case of 96 rays the angle discretezation step will be360o/96=3.75o.The experimental result of different angle discretezation step using is shownon Fig.3.16. Image on Fig.3.16,A was used as a source. The minimal discretezationstep of 3.75o causes the loss of several lines due to splitting effect. Thediscretezation step of 7.5o is looks as best variant: it allows detecting all significantlines while the splitting effect is minimal.

Larger discretezation step 15o does notproduce any new lines and splits existing lines. Larger steps – 30o and 60o – causeappearance of false lines. The last case, where discretezation step is a huge valueof 120o is shows that method still works correctly and detects enough amounts ofreal lines.For the ρ parameter representation, the best solution is to select thediscretezation step of one pixel.

The experiments show that lesser step causessignificant line splitting, and some lines will be missed. Larger step value reducesthe accuracy without any positive effect.86Fig.3.15. A parameter space of normal parameters in rectangular coordinate systemStep=3.75o, 217 linesStep=7.5o, 234 linesStep=15o, 258 linesStep=30o, 308 linesStep=60o, 353 linesStep=120o, 218 linesFig.3.16.