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

Insome cases more sophisticated operations are required, for example – partial imagerestoration. Current research does not analyse the pre-filtration stage since it iswell investigated, and images used have enough quality to skip the pre-filtration.However, practical applications often require it, and appropriate computationsmust be included into total amount of computations.

The main parameter affectedto the computational time is the image size, i.e. total amount of pixels. The amountof computations for the typical approaches is well known and can be easilyestimated. One of the most popular solutions to implement the pre-filtration ismask filter.

Their computational complexity linearly depends on amount of imagepixels, and it is usually required about 10% of whole vectorisation time. However,in the several cases more expensive filtration is required.Line segment extractionThe amount of computations on this stage depends on several parameters,such as image size, amount of edge pixels, amount of lines found.

The image sizeis primary parameter since it is determined by developer and does not depend onthe image content. Other parameters depend both on image type and on tuningparameters like thresholding level and minimal line size. As it can be concludedfrom Chapters 2 and 3, amount of computations on this stage linearly depends onthe image size. The dependence of computations from other parameters can be alsoeasily obtained but it is useless due to the difficulty of the parameter estimation.Line matchingAs it was shown in the previous chapter, the computational complexity ofproposed line matching algorithm is proportional to n1*n2, where n1 and n2 areline amounts on both images to be compared.

Theoretically, it is enough to knowonly two lines on each image. However, additional influences make this ruleincorrect. For example, line on one image can be absent on another, since it can besituated outside the visual field, can be noised, distorted or overlapped bysomething. Furthermore, image can contain several lines that look simultaneously,which makes uniform matching impossible. Another case is the curveapproximated by direct lines: there are several ways to do this, depending ofdetalisation level and even curve orientation on the digital image.

So in a practicethe more lines are used the better results will be obtained. The more lines in theimage description, the better chances to find matching line pairs.On the other hand, increasing of line amount lead to increasing amount ofcomputations, so only limited amount of lines can be used. Amount of lines in theimage description can play a role of regulator to set balance between reliability andperformance, and can be considered as a tuning parameter.119As it was showed in Chapter 4, the amount of lines involved in registrationprocess determine the ratio of computation times in line extraction and linematching processes. When amount of lines is relatively small (100 or lesser), thelarger part of computation is spent to a line extraction.

This amount of computationis proportional to amount of pixel on images. The situation became simple if oneimage can be converted in a set of lines in off-line mode, and vectorisation of onlyone image is required in real time. This can be, for example, when one of image isa priori known map in visual navigation tasks, or when there is a set of a prioryknown samples in image recognition tasks. Furthermore, in these tasks a larger setof images can be vectorized in off-line mode.In such a way, proposed algorithm of image registration contains threecomponents – pre-filtration, vectorisation and line matching. Amount ofcomputations in pre-filtration and vectorisation stage depends linearly on imagepixel amount, whenever amount of computations in line matching is proportionalto multiplication of line amounts on both images.Existing area-based algorithms of image registration in common case requirethe amount of computations that is proportional to (p12p22), where p1 and p2 –amounts of pixels on first and second images.

Using the pyramidal scheme canreduce this amount to (p1p2log(p1)log(p2)), however, it is critical to the imagequality. Using of correlation via fast Fourier transformation gives the same result,but it has its own specific problems.Best of feature-based graph matching methods requires amount ofcomputation that is proportional to third order of line amount.

They are alsorequires the same computations for vectorisation and pre-filtration.In such a way, the proposed algorithm of line matching has significantadvantages in performance when dealing with images of large area and highdetalization (large amount of lines, required for correct image description).

Thiscan be, for example, in a task of image position determination on the map in thevisual navigation task, when relatively small video frame is compared with a largemap, which is vectorized in off-line mode.When the image size is relatively small, the advantages in performance arereduced significantly due to overwhelming of vectorisation computations over linematching, and classical methods became more preferable here.5.1.2. Memory requirementsPrimary disadvantage of HT-based image registration methods is significantmemory requirements.

Memory is required to keep accumulator array, whichrepresents the search space. The size of accumulator array is proportional to anumber of all possible positions of one image on another – i.e. amount of all120possible combinations of transformation parameters with required discretizationstep.When the number of parameters to be determined is small, the memoryrequirements are acceptable. For example, it is often required to determine the puretranslation value only. In this case the accumulator array size is approximatelyequal to a larger image. So if one of images is a map of 10.000x10.000 pixel size,the accumulator array will require about 200Mb (if each cell is represented by twobytes) to achieve one-pixel accuracy.However, situation changes dramatically when additional parameters areadded. These parameters are usually rotation angle and scale.

For example, if it isrequired to determine the rotation with one degree accuracy, the memoryrequirements will grow in 360 times (about 72Gb for the previous example). If it isalso required to determine scale in the typical small range ±25% with a step of 1%,the memory requirements will be increased in 50 more times – about 3.6 Tb. It isclear that such a huge value is unacceptable not to on-board computers but evenmost powerful of existing machines.The search space is significantly rarefied, so traditional methods can be usedto reduce memory requirements.One of the most popular techniques is hashing with losses. It allows keepinghuge virtual array in a significantly lesser physical memory by ignoring void cellsand insignificant responses.

But the price of hashing is significant growth ofcomputation to perform an array addressing operation. The more complexalgorithm is used and more the memory compression level, the more additionalcomputation will be required.Another approach is iterative search with reducing the search area andincreasing accuracy on each step. Since algorithm begins from roughdiscretezation step, the accumulator array size can be significantly reduced.However, the specifics of HT-based strategies is that the reducing of the searcharea or parameter determination accuracy does not lead to significant reducing ofrequired computations (unlike to area-based methods).

So amount of computationsis growing proportionally to amount of iterations.Popular alternative to a hashing and iterative search is search spacedecomposition. This method decomposes the search space to a set of subspaces oflesser dimensionality. Instead of marking each response in a search space, now it isneeded to mark its projection to appropriate subspaces. The traditional solution isto use subspace of pure translation and rotation-scaling subspace.

In this case theamount of memory in the example above will be only 200Mb + 72Kb. So thedecomposition provides a most effective memory usage. However, ourexperiments show that using of decomposed search space leads to significantreduction of reliability. This happens because different cluster situated far onefrom another in initial search space can be projected into a same area in subspaces,and will produce false responses. The effect will be greater for a lesser subspacedimensionality. So this approach cannot be recommended for use in practicalapplications.121In such a way, significant disadvantage of HT-based image registrationmethod is significant memory requirements.