A Multi-Scale Bilateral Structure Tensor

A Multi-Scale Bilateral Structure Tensor Based Corner Detector Lin Zhang, Lei Zhang1 and David Zhang Biometrics Research Center, Department of Computing The Hong Kong Polytechnic University Hong Kong, China {cslinzhang, cslzhang, csdzhang}@comp.polyu.edu.hk Abstract. In this paper, a novel multi-scale nonlinear structure tensor based corner detection algorithm is proposed to improve effectively the classical Har- ris corner detector. By considering both the spatial and gradient distances of neighboring pixels, a nonlinear bilateral structure tensor is constructed to ex- amine the image local pattern. It can be seen that the linear structure tensor used in the original Harris corner detector is a special case of the proposed bila- teral one by considering only the spatial distance. Moreover, a multi-scale fil- tering scheme is developed to tell the trivial structures from true corners based on their different characteristics in multiple scales. The comparison between the proposed approach and four representative and state-of-the-art corner detec- tors shows that our method has much better performance in terms of both detec- tion rate and localization accuracy. Keywords: Harris, corner detector, bilateral structure tensor 1 Introduction Corner detection is a critical task in various machine vision and image processing systems because corners play an important role in describing object unique features for recognition and identification. Applications that rely on corners include motion tracking, object recognition, 3D object modeling, and stereo matching, etc. Considerable research has been carried out on corner detection. One of the earliest successful corner detectors can be Harris corner detector [1]. Harris et al. [1] calcu- lated the first-order derivatives of the image along horizontal and vertical directions, with which a 22 structure tensor was formed. The corner detection was accom- plished by analyzing the eigenvalues of the structure tensor at each pixel. However, computing derivatives is sensitive to noise, and the Harris corner detector has poor localization performance because it needs to smooth the derivatives for noise reduc- tion. Thus, several methods [2-3] have been proposed to improve its performance. 1 Corresponding author. Email: cslzhang@comp.polyu.edu.hk. Tel: 852-27667355. Apart from Harris corner detector and its variants, many other corner detectors have also been proposed by researchers. Kitchen and Rosenfeld [4] proposed a cor- nerness measure based on the change of gradient direction along an edge contour multiplied by the local gradient magnitude. Smith and Brady [5] proposed the SUSAN scheme. In SUSAN, a circular mask is taken around the examined pixel and this pixel is considered as the nucleus of the mask. Then “USAN” (Univalue Segment Assimilating Nucleus) is defined as an area of the mask which has the similar bright- ness as the nucleus. Smith et al. [5] assumed that the USAN would reach a minimum when the nucleus lies on a corner point. Wang and Brady [6] proposed a corner de- tection algorithm based on the measurement of surface curvature. In [7] and [8], Mokhtarian et al. proposed two CSS (Curvature Scale Space) based corner detectors. In these two algorithms, edge contours are first extracted and then corners are de- tected as the positions with high curvatures on edge contours. In [9], Zheng et al.’s cornerness measure was simply the gradient module of the image gradient direction. This paper presents a novel effective evolution of the classical Harris corner detec- tor. In the original Harris corner detector, an isotropic Gaussian kernel is used to smooth each of the four elements in the 22 structure tensor over a local window before calculating the eigenvalues. Such a smoothing operation will have two disad- vantages. First, some weak corners will be smoothed out. Second, the localization accuracy is much degraded. Inspired by the success of bilateral filters [10] in image denoising, which consider both the spatial and the intensity similarities in averaging neighboring pixels for noise removal, in this paper we construct a nonlinear bilateral structure tensor and use it to detect corner points. The basic idea of the proposed method lies in that both the spatial and gradient dis- tances should be involved in smoothing the structure tensor elements. The neighbor- ing pixels that have shorter spatial and gradient distances to the given one should have higher weights in the averaging. In this way, a nonlinear structure tensor, which is adaptive to image local structures, could be constructed and hence the image local pattern could be better distinguished. It can be seen that the classical Harris corner detector is a special case of the proposed method by exploiting only the spatial dis- tance in the structure tensor smoothing. However, the proposed nonlinear structure tensor has much higher sensitivity to corner-like fine structures than the linear struc- ture tensor. Therefore, it may respond strongly to some trivial feature points in the image. In order to get rid of the possible false corners detected at fine image scales, we propose a multi-scale filtering scheme based on the different characteristics of true corners and trivial structures in multiple scales. The rest of the paper is organized as follows. Section 2 briefly reviews the Harris corner detector. Section 3 presents the new corner detector in detail. Experimental results are presented in section 4 and the conclusion is made in section 5. 2 Harris Corner Detector Harris corner detector [1] has been very widely used in machine vision applications. Consider a 2D gray-scale image I. Denote by W∈I an image patch centered on (x0, y0). The sum of square differences between W and a shifted window W(△x, △y) is calcu- lated as 2 ( , ) ( ( , ) ( , )) i i i i i i x y W S I x y I x x y y        (1) By approximating the shifted patch using a Taylor expansion truncated to the first order terms, we have:  , xS x y A y        (2) where 2 ( , ) ( , ) 2 ( , ) ( , ) ( ) ( ) i i i i i i i i h h v i i i x y W x y W v h v i i i x y W x y W A                    and hi and vi represent the first order partial derivatives of image I along horizontal and vertical directions at pixel (xi, yi). In practice matrix A is computed by averaging the tensor product I I   ( I denotes the gradient image of I) over the window W with a weighting function K , i.e. 2 ( , ) ( , ) 2 ( , ) ( , ) ( )( ) ( ) ( ) ( )( ) i i i i i i i i h h v i i i x y W x y W v h v i i i x y W x y W K i K i A K i K i                         (3) Usually K is set as a Gaussian function 2 2 1( ) exp 22 idK i        , where 2 2 2 0 0( ) ( )i i id x x y y    and ρ is the standard deviation of the Gaussian kernel. Aρ is symmetric and positive semi-definite. Its main modes of variation correspond to the partial derivatives in orthogonal directions and they are reflected by the eigen- values λ1 and λ2 of Aρ. The two eigenvalues can form a rotation-invariant description of the local pattern. Under the situation of corner detection, three distinct cases are considered. 1) Both the eigenvalues are small. This means that the local area is flat around the examined pixel. 2) One eigenvalue is large and the other one is small. The local neighborhood is ridge-shaped. 3) Both the eigenvalues are rather large. This indicates that a small shift in any direction can cause significant change of the image at the examined pixel. Thus a corner is detected at this pixel. Harris suggested that the exact eigenvalue computation can be avoided by calcu- lating the response function 2( ) ( ) ( )R A det A k trace A     (4) where det(Aρ) is the determinant of Aρ, trace(Aρ) is the trace of Aρ, and k is a tunable parameter. 3 Bilateral Structure Tensor Based Corner Detection This section presents the proposed multi-scale nonlinear bilateral structure tensor based corner detector in detail. Our algorithm differs from the original Harris corner detector mainly in two aspects. First, a nonlinear structure tensor is constructed to substitute for the linear one used in the Harris corner detector; second, a multi-scale filtering scheme is proposed to filter out the false and trivial corners detected at small scales. 3.1 Construction of the Bilateral Structure Tensor The structure tensor for a gray level image I is a 22 symmetric matrix that contains in each element the orientation and intensity information in a local area. Denote by I the gradient image of I. The initial matrix field can be computed as the tensor product 0J I I    . To incorporate the neighboring structural information into the given position, an averaging kernel could be used to smooth each element of J0. Usually a Gaussian kernel Kρ with standard deviation  is employed for this purpose: 0*J K J  (5) where symbol “*” means convolution. Since convolution is a linear operator, the structure tensor Jρ is referred to as linear structure tensor [11]. It is a symmetric, posi- tive semi-definite matrix. Comparing Eq. (3) with Eq. (5), we see that the matrix Aρ in Harris corner detector is actually the linear structure tensor Jρ at pixel (x0, y0). In Harris corner detector [1], the “cornerness” of a pixel (x,y) is totally determined by its local structure tensor Jρ(x,y). However, the smoothing kernel Kρ has two prob- lems. First, the isotropic smoothing operation will smooth some weak corner features out so that the detection capability is decreased. Second, the localization accuracy of detected corner points will be reduced, which is a well-known problem of the Harris corner detector. Intuitively, if the local structure tensor can better preserve the local structural information at (x,y), the cornerness measured from it should be more relia- ble and accurate. Fig. 1: Weight distributions in a neighborhood of a corner pixel. (a) An artificial image with an ideal corner (red circle); (b) weights distribution by using the Gaussian kernel Kρ; (c) weights distribution by using the proposed bilateral weighting function Nρ,σ. As an early denoising technique, Gaussian smoothing is simple but it will over- blur the image details. The Gaussian weighting kernel only uses the notation of spa- tial location in the weights assignment. The greater the spatial distance from a neigh- boring pixel to the central pixel, the smaller the averaging weight will be assigned. The intensity similarity between the pixels is not exploited in Gaussian smoothing. In [10], the bilateral filter was proposed, which employs both the spatial and intensity similarities between pixels in averaging weight design. It has been shown that bilater- al filtering could significantly improve the edge structure preservation while remov- ing noise [10]. Inspired by the success of bilateral filters in image denoising, in this paper we construct a bilateral structure tensor for better corner detection performance. There are two basic factors in the formation of a local pattern: the relative positions between neighboring pixels and the intensity variations between them. Therefore, in the smoothing of J0, we should consider both the spatial distance and the gradient dis- tance in the averaging weight assignment. In the original Harris corner detector, only the spatial distance is considered by applying a Gaussian smoothing kernel Kρ to I I   . In this paper, we will also involve the gradient distance in the smoothing of I I   . Here, the gradient distance from the position (xi, yi) to the central position (x0, y0) is defined as:    2 20 0g h h v vi i id       (6) The spatial distance from (xi, yi) to (x0, y0) is the same as in the original Harris corner detector:    2 20 0si i id x x y y    (7) By considering both the spatial and gradient distances into the assignment of averag- ing weight, we define the following bilateral weighting function for each pixel (xi, yi) ∈W: 2 2 , 2 2 , 1 ( ) ( )( ) exp exp 2 2 s g i id dN i C                   (8) where  and  are the parameters to control the decaying speeds over spatial and gradient distances, and 2 2 , 2 2 ( ) ( )exp exp 2 2 s g i i W d dC                 (9) is the normalization factor. Fig. 1 shows an example to illustrate the weight distributions by using the Gaus- sian kernel Kρ and the proposed function Nρ,σ. Fig. 1-a is an artificial image with an ideal corner in the center, which is marked by a red circle. The size of local window W for smoothing is set as 2121. Figs. 1-b and 1-c illustrate the weight distributions for the pixels within W by using the Gaussian kernel Kρ and the proposed bilateral weighting function Nρ,σ, respectively. It is clearly seen that Kρ is isotropic and is inde- pendent of the image local structure, while Nρ,σ is anisotropic and is adaptive to the image local pattern. In this example, the edge pixels have higher weights than the non-edge pixels because they are more similar to the examined corner pixel in terms of gradient. Meanwhile, for the pixels lying on the same edge, the ones near to the corner pixel have higher weights than the others because they have shorter spatial distances to the corner point. With the nonlinear bilateral weighting function Nρ,σ, the nonlinear bilateral struc- ture tensor is defined as: 2 , , ( , ) ( , ) , 2 , , ( , ) ( , ) ( )( ) ( ) i i i i i i i i h h v i i i x y W x y W v h v i i i x y W x y W N i N A N N                              (10) The corner detection is based on the analysis of the above defined nonlinear bilateral structure tensor Aρ,σ. Similar to the original Harris corner detector, we calculate the response function R(Aρ,σ) = det(Aρ,σ)−k·trace2(Aρ,σ) to determine if a corner point exists in the current position. 3.2 Multi-scale Filtering Because the proposed nonlinear bilateral structure tensor Aρ,σ incorporates the local gradient information in the structure tensor construction, it could achieve much high- er true detection and localization accuracies than the linear structure tensor used in the original Harris corner detector. However, it is also sensitive to some trivial struc- tures. Due to digitization in the square grid, in discrete images often the ramp edges will show corner-like trivial structures in a fine scale. Those trivial structures will be enhanced by the proposed nonlinear structure tensor Aρ,σ and they may be falsely detected as true corners. Fig. 2-a shows an example. We can see many false detec- tions along the ramp edge by using Aρ,σ. To solve this problem, we propose a multi- scale filtering scheme to filter out those small scale trivial structures. (a) (b) (c) Fig. 2: (a) Corner candidates before multi-scale filtering; (b) final corner detection result after multi-scale filtering; (c) Relative cornerness ratio (RCR) curves of two true corners (blue curves) and two trivial corners (red curves); Suppose that we have obtained some corner candidates with the proposed nonli- near structure tensor. We will distinguish the trivial corner-like structures from the true corners by their different cornerness characteristics at multiple image scales. The images at different scales can be obtained by smoothing the original image I with a series of Gaussian kernels Kς with different standard deviations ς. By increasing the values of ς, a fine to coarse scale space can be formed. The underlying principle for our multi-scale filtering scheme is as follows. If a trivial structure is detected as a corner at a fine scale, the cornerness of this point should decrease rapidly with the increase of scale ς because it will be smoothed out by Kς. On the contrary, if a true corner point is detected at a fine scale, the cornerness of it will decrease smoothly with the increase of ς because it will appear in a wide range of scales. Denote by R0 the cornerness of a corner candidate measured by Eq. (4) at the fin- est scale 0, and by Rς its cornerness measured at scale ς. We define the relative cor- nerness ratio (RCR) as 0/r R R  (11) Fig. 2-c shows the RCR curves of two true corner points (blue curves) and two trivial corner points (red curves). From this figure we can clearly see that the RCR of false corners will decay much faster than the RCR of true corners. Based on the different behaviors of true corners and trivial corners in the scale space, we are able to tell them to remove false and trivial corners. Suppose we use L scales in the multi-scale filtering. A candidate corner point is recognized as a true corner point if 1 ( ) L l r l T   (12) where T is a threshold. Fig. 2-b shows the final corner detection result after multi- scale filtering (L=3). We see that many false corners detected in Fig. 2-a are removed in Fig. 2-b without affecting the true corners. 4 Experimental Results The experiments were performed on 3 standard test images. The ground truth corner points were manually labeled. For the artificial test image (refer to Fig. 4-a3), it is easy to identify these reference corners and the locations of corners can be accurately located. However, for real test images blocks (refer to Fig. 4-a1) and house (refer to Fig. 4-a2), it is nearly impossible to give absolutely accurate corner locations. There- fore, we only computed the localization accuracy for the artificial test image, while computed the detection accuracy for all the three test images. The code of the pro- posed algorithm can be found at http://www.comp.polyu.edu.hk/~cslzhang/MBST_CD/. The proposed corner detector was compared with four representative algorithms: Harris [1], SUSAN [5], Enhanced CSS [8] and the nonlinear structure tensor based method [11]. In [11], the authors proposed two different ways to construct a nonlinear structure tensor: one is by isotropic diffusion and the other is by anisotropic diffusion. In this paper, we compared the result given by the isotropic diffusion because it achieves similar result to that by anisotropic diffusion but has much less computa- tional cost. We refer to it as INLST for short in the following. For the four methods used in comparison, we tuned the parameters so that the best corner detection results were obtained. The proposed method has several parameters. The parameter ρ (referring to Eq. (8)) is adaptively determined based on the size of window W, i.e. the spatial range, according to the 3-sigma principle of Gaussian function. Similarly, the parameter σ (referring to Eq. (8)) is fixed by the range of dg i (referring to Eq. (6)), i.e. the gradient range, according to the 3-sigma principle. In the multi-scale filtering, we empirically find that it is insensitive to the scale selection and usually 3~5 scales are enough. Thus, in our experiments we used 3 scales and the same threshold for all the test im- ages: ς1=0.6, ς2=1.0, ς3=1.4 and T=1.0 (referring to Eq. (11) and Eq. (12)). Finally, the parameters left to set are the window size W and coefficient k (referring to Eq. (4)). In this paper they were set as follows: for the artificial test image, W=55 and k=0.04; for the blocks test image, W=2121 and k=0.02; and for the house test image, W=1313 and k=0.02. Denote by Cref the set of reference (ground truth) corners and by Cdet the set of de- tected corners by a particular detector. Denote by dm