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

All points belonging to the direct line l produces aset of direct lines in the dual space. These lines have the common interceptionpoint that is the vote of original line l.The primary disadvantage is that the k and b parameters approach infinityfor vertical lines. Kultanen in [Kultanen 1990] proposed possible solution isseparate detecting of vertical and horizontal lines. Another disadvantage issignificant non-linearity of parameter space: the accuracy of description dependson line position and orientation. For this moment a scheme found a very limitedapplication.Normal line representation was proposed by Duda and Hart [Duda et al1972]: ρ = x cosϕ + y sinϕ, where ρ is a length of normal to a line, and ϕ is aslope angle of the normal.

This parameterisation allows representation of a lineinsuspective of direction in a limited parameter space. The main disadvantage ofthis representation is that it is a computationally extensive (perhaps the highestamong other representation used in practice). Furthermore, each edge pixel33provides a sine in the dual parameter space instead of a direct line as in slopeintercept case. So building of exact sine line requires additional computations.Nevertheless, there are number of approaches that can reduce the amount ofcomputation required. So this approach remains a most popular scheme andusually referred as Standard Hough Transform (SHT).Foot-of-the normal representation proposed by Davies [Davies, 1990].

Afoot of normal is used to describe the line instead of normal length and slope angle.The scheme is faster, but has a singularity for the lines that pass through the origin:these lines have a same foot of normal (0, 0) and cannot be detected. In Davies[Davies, 2003] perspectives of practical usage of this scheme are analysed.A Modified Hough Transform [Wallace R.S. 1985] (also known as a MuffTransform) is another well-known parameterisation. It is a bounded straight lineparameterisation that uses the two intersection points of a line with the perimeterof the image. Muff Transform is used in [Shpilman and Brailovsky, 1999] for linesegment detection. The major advantage is that the resolution of the linesrepresented is uniform and matches exactly the set of lines, which can be drawnacross the image.Each of parameterisation has its own advantages and drawbacks.

They havedifferent complexity, different accuracy and different singularities. And one of theimportant tasks is to unite advantages of different methods without significantamount of computations.1.3.2. Reducing the parameter spaceA larger size of parameter space requires not only more memory but alsoadditional computation, related to initialisation, indexation for random access andsearching for significant votes and filtering operations. The situation is especiallycritical when a shape with many parameters is detected and the parameter spacebecomes dimensionally large. So reducing parameter space size without significantloss of accuracy is an actual problem.

One possible approach is to use differentquantisation for different areas of parameter space: areas of higher density to havelesser quantisation and a higher amount of counter cells in order to providesignificant accuracy, while empty areas have rough quantisation with a smallnumber of cells.One of the first such approaches is Fast HT [Li et al, 1985]. Li’s approachstarts with rough quantisation, and then to decrease the quantisation step inquadrants which obtain an amount of votes higher than a selected threshold level.The disadvantage is significant line splitting.Another approach is Adaptive HT proposed in Illingworth [Illingworth,1987].

It provides a special mechanism to focus attention on significant responsesto prevent line splitting.A comparison of dynamical quantisation techniques is given by Princen[Princen et al 1989]. Princen concludes that a main disadvantage of suchtechniques is the indexation complexity. As a result the increase in performancebecomes insignificant, and the algorithm although more complex is less reliable.34Other considerations as how to reduce parameter space size is given byDavies [Davies, 2003]: this paper determines the parts of the parameter space thatare not used for transformations and therefore can be eliminated.1.3.3.

Parameter space decompositionThe idea of parameter space decomposition approach is to decompose theparameter space of Tn elements into n separate one-dimensional spaces of Telements [Illingworth et al 1987], each of them being a projection of the wholeparameter space to the appropriate axis. This allows significant reduction in acomputation and memory requirements, but produces unreliable results whenamount of features to be detected is large. This happens because several featurescan produce the same projection and became inextricable. The presence of noisealso makes this scheme very unreliable.1.3.4. Using additional informationThe simplest source of additional information is edge orientation. If it isknown, each edge pixel will produce a single vote in the parameter space insteadof whole curve.

This is important because it leads to a significant reduction incomputational load. Davies [Davies 1990] proposes approach to use edge directioninformation and it is referred as the Generalised Hough Transform (GHT). Theproblem is that the exact edge orientation is often impossible to obtain due topresence of noise [Leavers, 1993]. Another approach uses gradient direction tosignificantly reduce sine length. A further approach discussed in the presentresearch is to use information about local point distribution.1.3.5. Using different analysing ordersIn order to get additional information about each boundary pixel aprogressive analysing order can be modified.

The idea is that every other boundarypoint belonging to the same detected shape allows a reduction in the amount ofparameters to be calculated by one. In such a way, when n pixels of a shape areknown, it is possible to mark a single point in parameter space instead of drawingn-1 dimensional hyper-surface.The problem of this approach is that the amount of n point combinationsgrows exponentially with n, and it is impossible to process all of thesecombinations. The one of possible solution is to choose randomly an amount ofpixel combination that can be processed in a given time, and find their vote.

Suchan approach is known as Probabilistic Hough Transform (PHT) – see [Kiryati et al1991], [Bergen et al 1991], [Xu et al 1990], [Califano et al 1989]. A comparison ofdifferent PHT techniques is given in [Kiryati et al 2000].A further development of this approach for complex shape detection isDynamic Generalised Hough Transform (DGHT). The DGHT variant proposed byLeavers [Leavers 1990] includes random selection of boundary pixels35combination, decomposition of parameter space and removing detected featuresfrom the source boundary data.The PHT approaches provide a good reliability when significant noise ispresent.

The main disadvantage is the complexity of the algorithm parameterdetermination. At the current time, this approach is the one of the most promisingdirections of HT theory development. Another disadvantage of PHT is itsprobabilistic characters that do not guarantee the same results for the same originaldata.The proposed research analyses another way to use additional informationby combining the edge orientation information with the distribution of boundarypoints in a local area. This allows limiting amount of combinations and increasingperformance but provides lower resistance to a noise.1.3.6.

Line splitting problemOne of serious problems in HT theory is the problem of feature splitting.Due to the discrete nature of the HT itself, feature parameters must be quantized.In this case a vote in parameter space that corresponds to one line has a chance tobe divided into several votes of significantly lesser magnitude. Such votes can belost among of the noise. Conditions exist when a segment of any large size willproduce a set of votes of fixed and low magnitude that do not depended onsegment size. In this case a whole long segment will be lost.The problem of vote splitting is most thoroughly investigated for the case ofdirect lines and line segments.Leavers [Leavers 1992] proposed a further approach to prevent splitting byusing of post-filtration. Split votes are placed in parameter space not chaoticallybut in a specific order.

If normal parameterisation is used, the votes produce abutterfly-like shape (central cluster with the sinusoidal “wings”). This makes itpossible to detect the “butterflies” in order to separate line splits from the noise andto merge them into an original line. The design of butterfly filter is described in[Leavers 1992].The butterfly filter is the low-level filter that deals with separate pixels, so itsize is limited by performance requirements.

A common filter size is 3x3 or morerarely 5x5, so it can process only tight split clusters. If splits are situated somedistance within the parameter space, this filter cannot merge them.A more complex butterfly filter that allows separate neighbour lines withsignificantly overlapped butterflies is proposed by Atiquzzaman [Atiquzzaman andAkhtar 1994] and further, by Kamat [Kamat and Ganesan, 1998].If line segments are used instead of unbounded lines, then more intelligentalgorithms are available – for example, the one proposed by Lagunovskiy[Lagunovskiy et. al. 1997]. In this case splits can be compared in the originalspatial space instead of parameter space, so the splits can be found and mergedregardless of their parameters.