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

However, they have significant limitations. Adifferentiation operation highlights spatial high-frequency elements, so it amplifiesnoise as well. The common solution is smoothing pre-filtration. However, it candisplace edge points from their original location and rounds sharp corners, so it isoften unwanted.A detailed analysis of differential filters design can be found, for example, in[Davies, 1990].There are two widely known approaches to brightness gradient calculation –template matching (TM) and differential gradient (DG) methods.TM methods are based on the look for a maximum replay among replays ofthe filter set (masks).

Usually the set contains from 8 to 12 masks. When the maskis applied to the image in a current area, the reply can be found as a sum:Rk =nn∑∑i= 1 j= 1I [ x + i − n / 2, y + j − n / 2 ] ⋅ M k [ i, j ]40where Rk is reply to a mask, I is a image and M k is a k mask from the set.Each mask corresponds to one of gradient directions. The direction k* whichproduces a maximum reply Rk* can be taken as the gradient direction estimate. Thereply value Rk* can be taken as a gradient magnitude estimate.There are number of methods which allow increasing of the gradientestimate accuracy either by increasing the number of masks used (and byappropriate decrease angle quantization step) or by taking into account severalnear-the-optimal replays.TM filters were historically one of the first methods of edge detection.

Itmust be noted that each response Rk is the projection of the brightness gradient tothe appropriate direction. However, two projections are required to calculate anoriginal gradient vector. This property is used in DG filters.DG methods, unlike the template matching, require only two masks, whichcorrespond to the two orthogonal directions. In the simplest case one mask M xcorrespond to the axis x direction and another, M y – to the y.

Response Rx to themask M x is the estimate of brightness derivative in the x direction, response R y tothe mask M y – in the y direction.The magnitude of the local gradient can be found from the responses Rx andRy :| G |= R( M x )2 + R( M y )2The gradient orientation can be found as follows:arg(G ) = arctg ( R( M y ) / R ( M x ))The DG approach produces higher accuracy. The DG approach uses onlytwo responses instead of 8-12 as in TM, but it requires additional calculations fortangent and square root calculation. In practical applications an approximateformula for root calculation and table of arctangent values are usually used tospeed up computations.The DG method based on Sobel 3x3 filter is still the most popular choice formost of practical applications.–Statistical methods. Statistical methods allow avoiding the severaldisadvantages of differential methods.

They work as follows. The statistics of thepixel brightness distribution is calculated in a local image area. This statistics isused to determine the amount of modes in the distribution. If the selected area hasno contours, the distribution will have a single mode. Otherwise, if the areacontains contours, the distribution will have two or more modes: one modecorresponds to brightness of the main object, and others modes correspond to edgepixels and lesser objects. In this case the main mode must be separated fromothers, and pixels of other modes must be marked as required contour pixels.Statistical methods are more reliable to noise in comparison to differentialmethods. They also do not misplace the contour pixels from its original location.This is important feature for several applications.

However, there are kinds of41noise that make statistical methods work significantly less reliable, and requiremore thoroughly tuning. The properties of statistical methods are investigatedmuch poorer then one for differential methods.A more detailed survey of edge detection techniques can be found in [Ziou,1998].1.4.2. Edge labellingDifferential filters are most popular as tools for edge detection. However,they require additional operations for localising edges and increasing signal-tonoise ratio by suppression of false edges. This operation is referred as edgelabelling, or edge procession.

The type of edge labelling depends on the edgedetector used.If gradient methods are used, edges can be found as areas of local maximumof gradient magnitude. Earlier methods used a thresholding operation with afollowing skeletonization. In [Canny, 1983] another approach was proposed – nonmaximum suppression.

The idea of this method is to extract local maximum in thegradient direction by suppressing pixels with gradient magnitude lower than thoseneighbour pixels have.Second-order filters require edge labelling as well: it is required to find thepoint of zero crossing.

The simplest approach is to compare each pixel with its leftand lower neighbour. If they have different signs, the pixel is marked as an edgepoint. However, this simple algorithm will produce phantom edges. For example,pixels of minimum gradient will also produce a second order derivative zerocrossing, however, they cannot contain edges.Another common operation of edge labelling is edge cleaning. It includeselimination of noise and false edges. The problem is that not only objectboundaries produce gradient local maximum and second-order zero crossing. Suchfactors as texture and non-smooth stair-like colour changing also produce them.The most common approach is to remove responses that have a weakgradient magnitude. As a rule, object boundaries produce higher contrast withbackground, than texture elements inside the object.

So different thresholdingapproaches can help to solve this task.In such a way, two operations are commonly used for edge labelling – edgethinning and thresholding.1.4.2.1. Edge thinningIn most cases a contour of one pixel width is required for reliable featuredetection. Since most popular edge detectors cannot provide one-pixel widthboundary additional processing is required.Two common approaches are used for edge thinning: skeletonization andnon-maximum suppression.421.4.2.1.1.

SkeletonizationSkeletonization produces a middle line (usually referred as symmetry axis)of the thick edge. The prairie fire algorithm is a well-known skeletonizationmethod. The boundary pixels of the shape to be thinned are marked as a fired.Each next pass marks shape pixels around fired ones – a distribution of wildfire.Pixels where fire waves meet each other produce the required skeletal line.The main disadvantage of prairie fire algorithm is that it is iterative, and itcan require large, and an unknown number of iterations.

In [Choy et al, 1995]another skeletonization method is proposed that requires only two passes.1.4.2.1.2. Non-maximum suppressionAnother approach to edge labelling is the non-maximum suppression (NMS)approach. It was introduced into wide practice of image processing by [Canny,1983].The idea of NMS is finding local maximum of the brightness gradientmagnitude in the gradient direction, and suppressing all other pixels of nonmaximum gradient magnitude. The remaining pixels then produce a requiredcontour of single width.The algorithm of NMS is quite simple: for each pixel of non-zero gradientmagnitude, the neighbour pixels in the gradient direction are analysed.

If one ofthem has a greater magnitude of the gradient, the current pixel is marked. After allare marked, non-maximum pixels are removed, the remaining pixels produces acontours of single width.The original Canny’s filter also contains a restoration of pixels in thecontour direction (orthogonal to brightness gradient) in order to suppress possiblegaps in the contour line.NMS is one-pass algorithm with low amount of computation per pixel, so itis significantly faster than other edge labelling algorithms like skeletonization.However, it is critical to the brightness gradient accuracy determination, andrequires additional filtration and thresholding to suppress noise, texture elementsand insignificant detail.

In comparison to non-maximum suppression, theskeletonization does not use information about edge orientation and thus it is lesssusceptible to the noise.1.4.2.2. ThresholdingThe task of thresholding is to eliminate pixels with a small value ofbrightness gradient magnitude and to separate contour pixels from texture elementsand noise. These items can also produce local maximums of brightness gradient,and it is required to separate them from object boundary pixels. Since these itemscommonly have less contrast than the object and background, they have abrightness gradient of lesser magnitude.

So the common approach of edgethresholding is to eliminate pixels with small value of brightness gradientmagnitude.Edge thresholding is less simple task than raw image thresholding, since thegradient magnitude distribution in a local area is either unimodal (when no edges43are in the area and thresholding is not required) or bimodal (when edge pixelsproduce a second mode), so the task is to determine which pixel belongs to each oftwo modes.The simplest method is to select a constant threshold value and eliminatepixels with a gradient magnitude less than threshold value. The main problem inthe threshold level calculation is that the threshold must be different for differentimages and even for the different areas of the same image.To avoid this difficulty it is possible to use the adaptive thresholdcalculation.

Adaptive thresholding uses additional information about, for example,gradient magnitude distribution, in order to select proper threshold level. Adaptivethresholding can use either global or local image characteristics. For the laster, it ispossible to apply different thresholds for the differently illuminated regions of thesame image.The thresholding problem is one of the common problems within imageprocessing applications, and it has no universal satisfactory solution to date. Asurvey of known thresholding methods can be found in [Davies 1990].1.5.

SummaryImage registration based on HT strategy is an interesting and promisingtechnique. It provides a good ratio of performance, accuracy and reliability that ishard to achieve by other methods. The development of HT techniques hasaccelerated over the recent years, new techniques have been found that allowsmoderating of the limitations of this approach. A technique such as featureconsensus allows not only rigid transformation but also local distortion processing.Parameter space decomposition allows reducing the dimensionality of searchspace.