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

The amount of computations in this case is P2=O(N1*N2). This issignificantly lesser. However, LSC method requires additional operations to buildtrapezoids in the search space instead of simple points for LSPC method.Relation between object amount and method performance is shown onFig.4.10.

It can be seen that both methods provide the same results when amountof lines in frame is small (50 and lesser): higher computation complexity of LSPCmethod is compensated by trapezoid building in LSC. Furthermore, larger part ofcomputation is related with line detection process. However, the situationsignificantly changes when amount of lines is above hundred: LSPC methodbecomes in more than ten times slower than LSC due to its higher computationalcomplexity.Table 2. Relation between number of objects and performance of the algorithmNumber of lines in frameSegment comparison, ms per framePair comparison, ms per frame5640.164.46842.292.58045.1149.79249.124911454.153213659.6846111Fig.4.10.

Relation between object amount and method performance112Let us look more thoroughly for the separate stages of the line-based imageregistration in order to determine the part of computation they taken in differentconditions.Image registration algorithm with line matching includes severalheterogeneous components. The fraction of computation time taken by each stagedepends on slightly different factors that indirectly affect one to another.In common case line-based image registration includes two general stages –line detection and line matching.

The amount of computations on the lineextraction stage depends firstly on the size of image to be processed. Otherimportant characteristics are amount of edge pixels found and their spatialdistribution. They depend on the image type and detection parameters (filtrationand thresholding parameters etc.) and can be neither set nor known priory.The amount of computation on the line matching stage depends mainly onthe amount of lines used for matching. The dependence on other factors like imagesize and type is indirect and sophisticated. This makes a direct research ofcomputation time ratios a hard taskTo solve this task, the following way can be used.

We will change theamount of edge pixels on the image, and mark the amount of lines found. Theamount of edge pixels affects directly to the duration of the line detection stage,whereas amount of lines affects to the duration of the line matching stage (when alllines are used for matching). Since the dependence of lines found on amount ofedge pixels is monotonous, it can be inverted. This allows investigating thedependence of line matching and line detection duration from line amounts bycontrol the amount of edge pixels.The dependence of line detection and line matching computations fromamount of lines found is shown on Fig.4.11. The ratio of computation times indetection and matching stages is shown on Fig.4.12.

All time measurements wereperformed for computer system based on Duron™ 750 processor.It can be seen that line detection takes insignificant part of computations inLSPC method, and this part quickly decreases with growth of line amounts andimage size. This happens since LSPC method has a relatively high computationalcomplexity.The situation is different in the LSC method. The line detection stage takeslarger part of computations.

This part slowly decreases with growth of lineamount; however, it still prevails.113Fig.4.11. Computation time of the stages of line-based image registration methodsFig.4.12. Fraction of line segment detection stage in common computation time1144.9.2.

AccuracyTo investigate the accuracy, the same image was taken as both images, butthe line amount was limited. Three characteristics were reviewed: amount offailures (when the position was found incorrectly with error larger than a givenlimit – seven pixels), maximum error value (failures was not taken into account)and standard deviation. The measurement results are placed into Table 3.The amount of lines on second image (the map) was constant (217), andamount of lines in a frame was changed from 15 to 70.

The amount of frames inone measurement is 23168.Table 3. Dependence of reliability and accuracy from number of linesLineamount1520303540507015203035405070Max. error VarianceVarianceFailuresEmaxDxDyamountLine segment pair comparison0,1080,35835500,05660,273126530,04140,2217620,04930,2282220,05850,2371520,06870,2441520,06950,24515Line segment comparison0,04960,14720900,01740,057969630,004680,02562440,002910,0172210,001610,00853210,0005730,00271210,0003640,002242Failures,%18%7%0%0%0%0%0%11%4%0%0%0%0%0%115A)B)Fig.4.13.

Comparison of accuracy and reliabilityA) Dependence of faults from line amount;B) Dependence of the error distribution variance from the line amount.It can be seen that line segment comparison method has a lesser deviation (in2 and more times), lesser maximum error (1 pixel instead of 2) and lesser amountof faults (in 1,5 and more times).The interesting fact that the line pairs comparison method has a higheraccuracy if the line amount is limited by about 30 lines per frame (Fig.4.13,B).However, the reliability is monotonous function, and it is higher for the larger lineamounts (Fig.4.13,A)4.9.3.

ReliabilityTo compare the method reliability, another group of experiments has beendone. The source image was rotated and scaled, divided into 128x128 pixel frames,and frames position was looking for on the original image. The angle and scalecorrection was disabled for both methods, and they could operate by translationsonly. The measurement results are shown on Table 4.It can be seen that although line segment comparison method shows higherreliability on original and turned images, it appears less reliable on scaling. Theaccuracy of line segment comparison methods appears higher in all cases.116Table 4.Comparison of reliability and accuracy of tested algorithms in thepresence of geometric distortions1.Original image2.Rotation on 1о3.

Rotation on 5о4.Scaling 90%5. Scaling 110%6. Scaling 125%Line segment pair comparisonDxDyEmaxN0,0318 0,11625(<1%)0,7571,735291(1%)3,944,1475040(26%)31,438,361380(7%)22,532,2115291(27%)-Line segment pair comparisonDxDyEmaxN0,00287 0,0503217(<1%)0,00287 0,0503217(<1%)1,281,3374499(23%)53,529,182418(12%)34,214,1125550(28%)12638(65%)4.10. ConclusionIn this chapter possible methods of image registration using presentation in aform of line set are examined. This method in common has a highest performance,on one or two degrees higher than other methods allow. To this moment, themethod accuracy and reliability was poorly investigated.

This chapter proposestwo methods – line segments comparison and line segment pair comparison –which have a high ratio of performance, accuracy and reliability. This allows usingthese methods in a wide range of practical applications.Another interesting fact is that the reliable method – line segmentscomparison – can have computation complicity of O(n2). This looks like atheoretically achievable limit. All existing approaches known to this momentprovide larger computation complexity [Brown, 1992].Nevertheless, all reviewed methods have a disadvantage: they require thatimage must contain direct lines.

There are number of important situation whendirect lines are absent on the image. In this case, a line comparison algorithm mustbe combined with another methods, for example – area-based correlation.117CHAPTER 5. DISCUSSIONThe method of image registration by line comparison, which was proposedand analysed in previous chapter, has significant advantage in comparison withknown image registration techniques: it requires significantly lesser amount ofcomputations. This effect is even more sensitive when larger images are processed.This happens because the computational complexity of the algorithm is O(n2)while known methods requires more computations (e.g.

dynamical programmingprovide only O(n3)). So the method can be considered as a good alternative to beused in real time systems.However, the method has its own disadvantages and unsolved problems,which is either specific for the whole class of feature-based methods, for the HTapproach or for proposed method itself.Class-specific problems are associated with reduced reliability and accuracyof feature-based image registration in comparison to area-based exhaustive searchmethods. Some problems arise on the feature detection stage, and also related withfeature extraction accuracy and reliability for the low quality images. Anotherimportant problem is significant memory requirements to keep the results of HT.This chapter provides comparison of proposed method with known ones inorder to determine the area of application.

Proposed method can be divided intotwo important parts – image registration itself and feature detection. Since anoriginal algorithm is used, it is also necessary to compare its characteristics withcharacteristics of known algorithms. It is important because quality of linedetection plays key role in a whole image registration algorithm, and moresensitive to a changing of image type.5.1.

Characteristics of image registration methods5.1.1. Performance considerationsAmount of computations in the proposed algorithm of line-based imageregistration depends on several parameters such as the image size, the amount ofedge pixels found, the amount of line segments found, the amount of line segmentsselected for matching, the ability of priory vectorisation of one image and others.These parameters affect to the amount of computations in separate stages of wholealgorithm and to the ratio of these computations.The proposed algorithm contains three large stages: pre-filtration, linesegment extraction and line matching.118Pre-filtrationThe pre-filtration stage is necessary for the images of low quality, which isnot enough to reliable and accurate vectorisation and further image registration.Pre-filtration includes noise suppression, brightness and contrast balancing.