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

Probabilistic approaches allow managing an amount of feature combinationsto be used for image comparison in order to reduce the amount of computation.Hierarchical schemes, adaptive and hashing techniques allow a “squeezing” thesearch space in order to reduce memory requirements.

All these factors make theHT approaches to be promising in tasks where it is required to find matching oflarge images with insignificant distortions for a very short time.One promising feature to provide image registration is line segments. Incomparison to point features, line matching requires more sophisticatedregistration algorithm, that has received little research interest to the date. But theimage representation has significant advantages like universality and detectionsimplicity, which makes them more promising in the processing of a wide range ofimages of different content, structure and visual conditions.If it is required and if it is possible, the registration based on linear featurescan be easily enhanced using other features like clusters and arcs to obtain more acomplete and more reliable image description.

This can either accelerate thecomputations if these additional features are easy to find on compared images, orincrease reliability in the case of low observing conditions.44Chapter 2. Image contour extractionContours play a very important role in the task of image matching. Contourpixels may be considered as control points that can be used directly for imageregistration. Furthermore, larger and more general features like angles, lines andstripes are a combination of contour pixels.

To extract them an additional stage isrequired – the contour extraction.Contour extraction is deeply researched but very important stage. If theimportant details are lost on this stage, it is impossible to correct the situationfurther. So this chapter is completely devoted to the proper selection of the blocksfor the correct contour detection algorithm.The stages of the contour extraction algorithm are shown on Fig.2.1. Thereare edge detection, binarisation and edge thinning.Two algorithms of edge detection will be tested – differential gradientmethod and statistical method – in order to find best suited for our task.

For thebinarisation we will compare static and dynamic binarisation. The Canny’s nonmaximum suppression method is selected for the final edge thinning because it hasno good alternative on performance.Classical approach usually includes additional stages – image pre filtration(smoothing) and contour enclosing. It was decided to remove these stages by thefollowing reasons.

Parameters of pre filtrations mainly depend on characteristics ofused camera and must be selected separately in each case. There is no any“universal” pre filtration. The contour enclosing is not used because the linedetection algorithm is insensitive to the gaps in the contour, and thiscomputationally extensive stage is not necessary.The primary characteristics of contour extraction algorithm quality are listedbelow (beginning from the more important characteristics):1.

Algorithm performance.2. Reliability, i.e. ability to extract the edge pixels correctly on the images oflow quality – noised, blurred, with geometric distortion etc.3. Precision (many popular algorithms produce misplaced pixels)4. Contour width. In the most of cases a contour of one pixel width isrequired. If the width is greater than one pixel, it is required to apply additionalalgorithms of edge thinning.5. Enclosed contour. In some cases the contour extracted must be enclosedand contain no gaps.The integral characteristic of the contour detector quality is a quality ofsubsequent extraction of larger contour elements – lines and angles, i.e.

amount ofcorrectly and incorrectly extracted elements. This characteristic is more importantthan quality characteristics described above, and indirectly depends on them. So itis important to compare algorithms of contour pixel detection by this integralcharacteristic.45a) original imageb) results of edge detectionc) results of binarisationd) results of edge thinningFig.2.1. Contour extraction stages:a) original image,b) results of edge detection,c) results of binarisation,d) results of edge thinning – the contour462.1. Differential methodDifferential gradient (DG) method requires two masks, which correspond tothe two orthogonal directions.

In the simplest case one mask Mx correspond to theaxis x direction and another, My – to the y. Replay Rx to the mask Mx is the estimateof brightness derivative in the x direction, replay Ry to the mask My – in the ydirection.The magnitude of the local gradient can be found from the replays Rx and Ry:| G |=2Rx + R y2The gradient orientation can be foundas follows:arg(G ) = arctg ( Ry / Rx )The DG approach requires computations of the root and arctangent, but itprovides high accuracy. The following approximations can significantly reduce theamount of computations:| G |≈ | Rx | + | Ry |or| G |≈ max(| Rx |, | R y |)Both formulas provide the same relative error:ε = 1 − cos 45 o ≈ 0,29To increase the accuracy another approximation can be used:| G |≈12(| Rx| + | Ry | + max(| Rx |, | R y ) )The relative error is:ε = 1 − cos 22,5 o ≈ 0,076Such an accuracy is enough for a most of practical applications.The value of arctangent function can be calculated from tabulated values.The problem is that the argument of arctangent must change from -∞ to +∞, andcannot be tabulated directly.

One of the possible solutions to find the arctg ( y / x)value is the following.There are two tables: one for the argument value greater than 1, andanother – less than 1.When |x|≥|y|, the argument value R=y/x belongs to a [-1..1] Interval, andarctangent value can be found from the table T1: arctg(R)=T1[R].When |x|<|y|, the additional argument R*=1/R=x/y is introduced. It is alsobelongs to a (-1..1) interval.

Arctangent value can be found from the table T2:arctg(R)=T2[R*].In such a way, values in the tables T1 and T2 can be tabulated in the intervalof (-1..+1) with any desired step, and the arctangent value can be calculated withany required precision for the any integer values of x and y. The algorithm requiresone integer division and one integer comparison to compute one arctangent value.The problems of the differential detector development are examined in[Davies, 1990].

The most popular detector wide used in the practice is the Sobelfilter with a mask size of 3x3. It provides high enough accuracy (about 3o for the47edge orientation) and requires relatively small amounts of computation. Anotheruseful feature of this detector is the symmetry in relation to a central pixel.Filters with a larger mask (e.g.

5x5) require in a 2,8 times morecomputations and provide an accuracy of 1o, but in much of cases such an accuracyis useless since non-instrumental component of the error is significantly greater.Filters with a lesser mask (e.g. Roberts filter size of 2x2) are too sensitive tonoise and image granularity and cannot give the reliable results.Sobel filter masks are shown on Fig.2.2.-101-1-3-1-303000-101131Fig.2.2.

The Sobel filter masksThe DG methods have the following specifics:- Differential methods by itself cannot find a local gradient maximum, andprovides a contour width greater than 1. So after the gradient is found, additionaloperations to reduce a contour width are required.- Differential methods use the derivative computation, so they highlighthigh-frequency elements: noise, corners, tiny details and texture.- Differential methods always misplace the gradient maximum by one pixelfrom the real position of edge pixels.2.2. Statistical methodsStatistical methods allow avoiding the several disadvantages of differentialmethods.

They work as follows.The statistics of the pixel brightness distribution is calculated in a localimage area. This statistic is used to determine the amount of modes in thedistribution. If the selected area has no contours, the distribution will have a singlemode. Otherwise, if the area contains contours, the distribution will have two ormore modes: one mode corresponds to brightness of the main object, and othermodes correspond to edge pixels and lesser objects. In this case the main modemust be separated from others, and pixels of other modes must be marked asrequired contour pixels.To develop a statistical detector, a following task must be solved:48-Determine the image local area size that will be used to collect astatistics,Develop the algorithm to determine amount of modes in thedistribution,Develop the algorithm to determine threshold to separate main modefrom others.2.2.1.

How to select the area size for a statistics collectingThe brightness difference between the object and background is often not aconstant value neither for different images obtained at different times, nor even fordifferent areas within the same image. So it must be determined for the each localarea. The lesser an area size, the more accurate the brightness threshold will bedetermined.

On the other hand, tiny areas cannot provide enough data to determinethe number of modes and the threshold value. The best accuracy in the thresholdcalculation can be obtained for the local area size of 4x4.An alternative approach is based on the fact that areas for statisticscollection and for the contour detection must not be the same. For example, thestatistics can be calculated for the area 4x4 and used to detect contours in the lesserarea size of 2x2.

The accuracy of edge detection significantly increases, thecontour width reduces from 4 to 2 pixels, but the amount of computation increasesby 4 times.2.2.2. How to determine a threshold and amount of modesThere are many methods to find the amount of modes in the brightnessdistribution, which differ both by quality provided and by performance. One of thefast methods is the following.After collecting data in a local area, the histogram consisting of three rows isbuilt. The central row corresponds to an average value. If the distribution isunimodal, the central row will be greater than any other: G1+G3<2G2. If thedistribution is multimodal, this condition is wrong, and threshold can be foundbetween mass centers of the main and additional modes.The contour extraction algorithm can be described as follows.1.For the each local area:1.1.Find average value Iav of pixel brightness in a current area.1.2.Find average value I1 for the pixels with brightness less than Iav1.3.Find average value I2 for the pixels with brightness greater than Iav1.4.Select threshold value It between I1 and I2 values1.5.Find amount of pixels G1,G2 and G3 in diapasons [0 ...