Bobkov A.V. - Image registration in the real time applications (779134), страница 19
Текст из файла (страница 19)
Dependence of line amount from the angle discretezation step873.7.4. Minimal object size that can be approximated by linesegmentsOne more important characteristic of the line detector is a minimal size ofobject, which still can be approximated by a set of line segments. To determine thiscritical size it is possible to use an artificial test image shown on Fig.3.17.Fig.3.17 contains a set of figures of periodically increasing size – circles andsquares of different orientation. Number under the figure row means its size.
Theimage shows that critical size for figures with straight edges is 8 pixels, and edgeorientation is not affected to this critical size. In the case of arcs, the critical radiusis 11 pixels. In this case the arc image will have straight segments of 8 or morepixels, which can be approximated by a line segments.Right part of the test image contains a circle of large radius in order to showthe algorithm ability to correctly approximate arcs and curves.A)B)Fig.3.17. Critical size for different objectsA) Source imageB) Presentation provided by a set of line segments3.8. ConclusionThis chapter describes the Extended HT concept, and the new line segmentdetection method is developed based on it.
The Extended HT allows separating theidentification and description parameters of line segments. This allows selectingthose parameters, which provide, on the one hand, high reliability and simplecomputation scheme of the detection, and on the other hand – provide accuratedescription and determination of additional characteristics with minimalcomputations (e.g. brightness gradient direction and line pixel density).88Described line detection algorithm has significantly better characteristicsthan classical approach can provide. It is faster, since it used simple computationscheme, does not require complex indexation of accumulator array, and uses onlyone pass.
Algorithm does not require lot of memory since it uses two-dimensionalaccumulator array instead of four-dimensional. The parameterisation that uses theline segment end co-ordinates allows reaching one-pixel accuracy, which isunreachable by other methods, and allows using relatively simple and fast linemerging algorithms.In such a way, the developed algorithm is faster, more reliable and accurate.It can work in real time scale and can process real images. The methodcharacteristics make it possible further image registration by matching of linesegments, which are extracted by proposed method.It must be noted that proposed concept of Extended HT could besuccessfully applied for the detection of other features like circles, arcs, curves,polygons etc.
However, the discussion of this task is outside the boundaries of thecurrent research and is the subject of further research.89Chapter 4. IMAGE REGISTRATIONThis chapter is devoted to image registration using their representation as aset of line segments. Different methods of registration by line segments will beoverviewed and analysed.4.1. IntroductionThis chapter is devoted to image registration using their representation as aset of line segments. Chapter examines both known and novel image registrationmethods, based on Hough Transformation, investigates their characteristics andcompares each other in order to produce recommendations for proper methodselection to be used in practical applications.4.2.
Statement of the problemIn the previous chapter an algorithm was described that allowsrepresentation of each image In as an appropriate list of line segments Sn. Thefollowing information is available for each segment:- Co-ordinates of ends;- Direction and the average value of a brightness gradient along the segmentpoints (it is determined during the line segment extraction procedure);- The normal parameters (they are unambiguously defined via end coordinates, however they are usually known as a side result of segment extractionprocedure)- Length of a segment.So there are two images presented as a set of line segments. The task is toestimate parameters p of transformation L(p) that passes one image S1 into anotherS2 and produces maximum coinciding of both sets, i.e.
maximises some qualityfunctional max J(p)=J{L(p,S1),S2}.A set of possible transformations L(p) will be limited by simple translation(∆x, ∆y), or – where it will be marked specially – it can contains also rotation φ andscaling m.The quality functional J will be either amount of line segments or amount ofpixels in all line segments that will match on both images when transformationL(p) is implemented. First variant is less accurate, but allow reducing the amountof computations in several methods.904.3.
Image registration strategiesAs it was reviewed in chapter 2, there are three slightly different imageregistration strategies – exhaustive search, graph matching and Houghtransformation.Exhaustive search and its variations are usually used in area-based methods,where a number of elements to be compared are greater than amount of possiblepositions. In feature-based methods, an exhaustive search produces a lot of voidpasses and thus requires too many computations.Most popular strategies of feature-based image registration methods arebased on graph matching.
Their main disadvantage is significant computationaccuracy, but they require a lot of computations. This makes them difficult toimplement in real time applications.Alternative to a graph approach is strategy based on Hough transformation.This approach has promising characteristics (high performance, in first of all).However, it is poorly investigated, and known implementations have lowreliability.
So HT strategy is rarely used in a practice.Here a short description of these strategies.4.3.1. Exhaustive searchFor each possible position of the current frame on the base frame the amountof matching elements are calculated. The maximum amount corresponds to a mostprobable position of the current frame on the base frame.A disadvantage of this strategy is a huge amount of calculations, because itprocess large amount of position that is proportional to image area in pixels.
Theamount of operations is proportional to amount of all possible positions of oneimage on another. So it can be used only in a limited set of applications where thesize and dimension of search space are small. This strategy is well investigated andapproaches to reduce the size of searching parameter space are known (first of all –hierarchical, or pyramidal search). However, significant reducing of computationsis still unreachable, so other strategies must be used.Another approach is to compare lines instead of checking for all possiblepositions.
Two variants how to do this are known – graph-to-graph mapping andHT for the point features. Since the small amount of lines (or other elements) isused instead of large amount of positions, these strategies are much faster.4.3.2. Graph matchingThis approach can be described as follows. Each pair of features thatprobably can correspond to each other produces a space transformation, whichtransforms one feature to another. So it is required to find a transformation that91leads to matching of maximum amount of features. A systematic way to representthis is to construct a match graph, in which the nodes represent featureassignments, and the arcs joining nodes represent pair-wise compatibility betweenassignments.
To find the best match it is necessary to find regions of the matchgraph where the cross-linkages are maximum.A complete sub graph, where arcs connect all pairs of nodes, is called clique.Hence, the maximum cliques are taken as they lead to the most reliable matchesbetween the sample and observed image.The main problem of matching graph approach is an exponential growth ofrequired computations in dependence on feature amount. A quantity of all possiblefeature combinations that define a search tree depends exponentially on amount ofstructural elements. The task of looking for sub graph in a graph belongs to NPcomplete tasks class (like a travelling salesman task).
For such tasks, there is noknown means of ensuring that they are executed in polynomial time. Thus, given agraph of n nodes, it is not known how to find the maximum cliques in a time that isbounded by a polynomial of n, current indications being that it is at leastexponential in n. For example, to process a graph of n nodes, it is required to checkabout 2n nodes in it. So the exhaustive search is acceptable only in a limited groupof tasks. More popular searching methods are the stochastic methods or finitesearching methods like dynamical programming, annealing methods, geneticalgorithms etc.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
