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

However, line segment detection requires more acomplex detection algorithm in comparison to unbounded lines. Line segment36requires at least 4 parameters to be described, so it requires 4-dimentionalparameter space if standard approaches are invoked.1.3.7. Line segment detectionA line segment can be considered as a curve and can be detected by HT. Aline segment requires four parameters to be uniquely described. The mostcomfortable form is a form of co-ordinates of both ends, but it cannot be used withHT since separate edge pixels contain no information about line segment ends.

Soless comfortable and less accurate forms are used. One of the most popular formsis a set of appropriate line parameters (for example, normal parameters), segmentcentre position of this line and segment length.The primary problem of such an approach is that the line segment isconsidered to have at least 4 parameters to be properly described, and they requirea 4-dimensional parameter space. This causes a huge amount of required memoryto implement detection, and significant amount of computation as well.Another problem is the accuracy of line segment detection.

An accuracy ofline segment detection with this parameterisation depends directly ondiscretezation step and accuracy of the gradient direction detection. Maximumaccuracy that can be obtained using differential filters of practical suitable size isabout 10 but due to the influence of such factors as image retrace withdiscretezation, natural curvature contour, texture influence etc. is over an orderhigher.Since the line segments are nice candidates to a fast, universal and completedescription of an image, there are lots of papers that investigate line segmentdetection problems and propose different techniques to avoid them.

In [Davies,1990] the GHT is used to extract line segments that become a classical approach tothe segment detection. Shpilman and Brailovsky [Shpilman and Brailovsky 1999]used a MUFF parameterisation scheme to determine line segment ends asinterception points of line and window frame. Kamat and Ganesan [Kamat andGanesan, 1998] show that the line segment ends coordinates can be extracted frombutterfly-shape vote distribution in the parameter space. In [Foresti, 2000] afocusing algorithm is used in order to reduce the size and dimensionality of searchspace. This approach provides additional information about line segmentdistribution that can be used for more complex and exact detection.

In the [Ching,2001] the iterative technique proposed that allows avoiding a line splitting. Thisapproach cannot provide high performance but it produces high accuracy.All these approaches allow to moderate primary line segment detectionproblems, however, the price is either significant loss of performance or loss ofreliability in the complex or noised images.371.4. Contour detectionContour detection is a necessary stage of almost all feature-basedtechniques.

The most important and salient features describe object boundaries, oredge pixels; hence, they contain the most important information about objectshape.The theory of edge detection is well researched, and many different toolsand techniques are available. However, the demands of real-time application createexacting requirements on edge detection properties and limit the number ofmethods that can be effectively used. These requirements are:- Performance. The edge detection stage processes the raw intensive imagesand has to deal with a significant volume of information.

Hence, global techniquescannot be used to process the whole image, and local area techniques are usedinstead. Such approaches can increase performance; however, they may beconstrained by their operation on an incomplete set of image information and raisesensitivity.- Reliability. This is the ability to extract edge pixels correctly on images oflow quality – noisy, blurred, with geometric distortion etc. Since the reliability andperformance are always mutually exclusive requirements, each practicalapplication can provide their own trade-off between these characteristics.- Precision.

Many popular edge detectors produce misplaced edge pixels asthe price for noise filtration. This causes distortions in object feature locations andcreates additional problems on the feature matching stage. Furthermore, to obtainmore exact position of edge pixels, more complex – and thus slower – algorithmsmust be used. Precision is one more components in the performance-reliabilityprecision triad of mutually exclusive requirements.- Contour width. In the most of cases a contour of one pixel width isrequired for reliable feature detection. If the width is greater than one pixel, it isrequired to apply additional algorithms of edge thinning.- Enclosed contour.

In some cases the contour extracted must be enclosedand contain no gaps. However, a number of techniques are known that do notrequired enclosed contours for reliable feature detection, and HT is one of them.- Edge orientation information. Edges can provide information not onlyabout the contour pixel position, but also about the edge orientation in these pixels.The edge orientation is usually found from the direction of brightness gradient inthe edge pixels.

The edge orientation is an important property for a further featuredetection stage. The more exact information about edge orientation that is availablethe faster feature detection can be performed. However, the precision of edgedetection is limited both by local area size used for edge orientation computation,and by the level of noise suppression. Increasing the computation area significantlyslows down the computations whereas noise suppression displaces the edge pixelposition. So the edge orientation precision is often a parameter that requiresaccurate tuning.38- Insignificant details suppression. Usually the edge detector produces notonly salient contours but also other edges that can be caused by noise, texture, tinydetails, unsmooth colour changing etc.

These items are not desired within featuredetection since they can distort results and slow down the process, and in certaincircumstates can be eliminated. The main parameter that allows distinguishingthese items from the real contours is lower brightness gradient magnitude. So themost popular technique of detail suppression is thresholding, or binarization – anelimination of all pixels with lower gradient magnitude than given threshold.However, proper selection of threshold value and the algorithm itself is a complexand still challenging task.A contour detection algorithm must contain three stages: edge detection,thresholding and edge thinning.1.4.1. Edge detectorThe most widely used edge detectors can be classified in following groups inrelation to the principle used:–Tracing methods. These methods use bypassing to the perimeter of uniformareas.

The trace goes through the contour pixels required. The simplest tracingalgorithm is a “bug algorithm” (Fig.1.2). “Bug” begins moving from white area indirection to the black. As soon as it have reached the black pixel it turn to the leftand goes to the next pixel. If this pixel is white, bug turns to the right, if white – tothe left, and so on until it returns to the original point. Co-ordinates of passagefrom black to white pixels describe an object contour.Tracing methods can be implemented to a binary image only, which containsonly black or white pixels; hence a thresholding procedure has to be applied to thesource image. Thresholding itself is a complex problem that has no universalsolution.The advantages of tracing methods include high precision, one pixel contourwidth and enclosed contour.

Disadvantages are the low performance and lowstability. Due to these disadvantages tracing methods are rarely used in real timeapplications. Their main application area is computer graphics and CAD systems.39Fig.1.2. Contour tracing by the bug algorithm–Differential methods. These methods use numeral spatial differentiation. Afirst or second derivative is usually used (however, in [Mathieu et al 2003]methods are discussed that use derivative of fractional dimensionality). Firstderivative has a local maximum in the areas of maximum spatial speed ofbrightness changing, so the position of local maximums can be accepted as objectboundaries.

Second derivative crosses a zero in the areas of curvature changing, sothe zero crossing points can be also accepted as edges. These properties allowbuilding a detector, based on derivative estimation by calculating finite differencesin the area around selected point. Second-order methods allow simplifying edgesearching, since zero-crossing areas are easy to obtain. First-order methods allowobtaining information about both brightness gradient and edge orientation, and lesssusceptible to noise, but an additional operation of local maximum searching isrequired (it is usually referred as edge thinning).Numerical differentiation operation can be performed as an imageconvolution with a special matrix (mask), like other filtration operation, sodifferentiation operation is commonly referred as filtration.Differential filters are widely used due to their simplicity, relatively highperformance and reliability.