Morphological Corner Detection Robert Laganière School of Information Technology and Engineering University of Ottawa Ottawa, Ont. CANADA K1N 6N5 Abstract This paper presents a new operator for corner de- tection. This operator uses a variant of the morpholog- ical closing operator, which we have called asymmetri- cal closing. It consists of the successive application of different morphological tranformations using different structuring elements. Each of these structuring ele- ments used to probe the image under study is tuned to affect corners of different orientation and brightness. We found that this kind of approach, based on bright- ness comparisons, leads to better quality results than others and is achieved at a lower computational cost. 1 Introduction Corners constitute attractive 2D features, often used in computer vision for tasks such as stereovision, 3D interpretation, motion estimation, and structure from motion. They abound in indoor scenes where several polyhedral objects and intersecting planes (floor, walls, etc.) are present. Corners serve as points of interest in two-view matching algorithms [1][2][3]. Corner detection is also used in camera calibration for the localization of reference points on a calibration pattern ([4] for example). Corner detection is sometimes realized through the analysis of binary edge maps from which chain codes are extracted in order to find high curvature points [5][6][7]. However, most approaches work directly at the grayscale level [8]-[17]. These methods usually use local measurements in order to obtain a corner strength. Non-maxima suppression and thresholding lead then to a binary map showing where corners have been detected. These corner finder are usually char- acterized by an accuracy of few pixels and a relatively high level of false positives. Model-based approaches such as [18][19] also exist and allow corner localization at a subpixel accuracy. But these methods are more CPU-intensive and are only used after a first corner map has been obtained. One of the difficulties with corner detection lies in the corner definition itself. A restrictive description simply defines corners as the junction of two homoge- neous regions separated by a high-curvature boundary. This definition is incomplete since it does not include X, Y and T junctions that should also be categorized as corners since they might be the image of 3D corners (intersection of three planes). A less rigid definition assimilates corners to points with high derivatives in several directions. This is a very loose description of the term corner since since several “non-corner” points fall into this category. This paper proposes an approach to corner detec- tion based on mathematical morphology. The goal was to obtain a fast corner detector that is accurate, stable, selective and robust to noise. The next section is a short review of existing corner detectors. Section 3 presents some mathematical morphology concepts. Section 4 describes the proposed corner detector and Section 5 shows some comparative results. Section 6 is a conclusion. 2 Corner detection We review here the main corner detectors that work directly at the grayscale level. All these methods use local measurements in order to obtain a corner strength c(x, y) for each point of the image. Local non-maxima suppression and thresholding are then performed in order to extract points that will be re- ported as corners. The use of the Hessian determinant of the intensity surface to estimate corner strength has been proposed by Beaudet [8]. Kitchen and Rosenfeld [9] proposed to use the gradient magnitude and the rate of change of gradient direction along an edge contour. Very similar operators have also been proposed by Dreschler and Nagel [10] and Zuniga and Haralick [11]. Deriche and Girondon [12] proposed a scale-based approach that uses the Beaudet’s operator in conjunction with the Laplacian. Following the idea of points of interest developed by Moravec [13], the Plessey detector [14] is based on the following matrix: M(x, y) =   〈 ( δI(x,y) δx )2 〉 〈 δI(x,y) δx δI(x,y) δy 〉 〈 δI(x,y) δx δI(x,y) δy 〉 〈 ( δI(x,y) δx )2 〉   (1) where 〈I〉 denotes a smoothing operation on I. Cor- ner strength has been first defined by Noble [15] from which a slightly different version has been proposed by Harris and Stephen [16]: cHS(x, y) = Det ( M(x, y) ) − k Trace2(M(x, y)) (2) The role of the parameter k is to remove sensitivity to strong edges. All of the above methods are based on directional derivatives. They all suffer from the same drawback: local estimation of derivatives is very sensitive to noise and, when smoothing is applied, the corner localiza- tion precision is reduced. In addition, the computa- tional complexity of the smoothing operation, deriva- tive estimation and corner strength computation that are involved in such methods can be quite high. A simpler approach based on brightness compar- isons has been proposed by Smith and Brady [17]. The SUSAN corner detector is a modified version of the edge detector of the same name. It is based on the computation of the area of points inside a circular re- gion Nxy having a brightness similar to the one of the center point (x, y). This area is computed as follows: n(x, y) = ∑ (i,j)∈Nxy e−( I(i,j)−I(x,y) t )6 (3) The parameter t controls the sensitivity to noise, i.e. it defines the similarity between brightness values. The value of n(x, y) is therefore compared to a fixed thresh- old equal to nmax/2 where nmax is the maximum value that n() can take, that is: cS(x, y) = { nmax 2 − n(x, y) if n(x, y) < nmax 2 0 otherwise (4) The value of this function corresponds to the corner strength. In order to reduce the number of false pos- itives due to smooth boundary, thin lines and fine textures, two criteria must be added. The center of gravity of the circular region must be (1) located suf- ficiently far away from the center point and (2) all pixels lying in a straight line from the center point to the center of gravity must be of similar brightness. Because of their computational simplicity, methods based on brightness comparisons constitute an attrac- tive solution to the problem of corner detection. More- over, our experiments showed that this kind of ap- proach allied accurate corner localization with good robustness to noise. The corner detector we propose follows this approach and makes use of some basic morphological tools. 3 Mathematical morphology Mathematical morphology is a methodology for im- age analysis that has been widely used in computer vision. The principle of all basic morphological opera- tors is to probe the image under study with a structur- ing element. This structuring element is a set of pixels on which an origin is defined. To evaluate the results of a morphological operation on an image point, the structuring element is translated in such a way that its origin coincides with this image point. The shape of the structuring element defines a set ISE(x, y) that includes all pixels of the image hit by the structuring element. From this set, the elementary morphologi- cal operators erosion and dilation can now be defined. The erosion of an image I with a structuring element SE is given by: IεSE(x, y) = min ISE(x, y) (5) Similarly, the dilation of an image I with a structuring element SE is given by: IδSE(x, y) = max ISE(x, y) (6) Two morphological transformations are defined by the successive application of these operators. The opening of an image I by a structuring element SE is defined as an erosion followed by a dilation: IoSE = ( IεSE )δ ŠE (7) where ŠE is the symmetrical transposition of SE with respect to its origin. All image structures that cannot contain the structuring element are removed by the opening. Therefore, the shape and size of the struc- turing element must be set according to the informa- tion that is to be extracted. The closing of an image I by a structuring element SE is defined as a dilation followed by an erosion: IcSE = ( IδSE )ε ŠE (8) 4 Asymmetrical closing for corner de- tection In the context of corner detection, one interesting choice is to consider a cross-shaped structuring ele- ment (Figure 1(a)). Indeed, because of the particu- lar shape of this structuring element, the opening and closing operators alter mainly this kind of image struc- ture. However, these corner detectors suffer from three problems: 1. Opening affects only bright corners over dark background while closing affects only dark cor- ners over bright background. 2. Small image structures (including impulsive noise and thin lines) are also eliminated and thus can be wrongly assimilated to corners. 3. This kind of corner detection is not rotationally invariant. A concurrent application of opening and closing can solve the first problem, but we introduce a more effi- cient solution. We propose to perform what we call an asymmetrical closing, that is, the dilation of an image using a given structuring element followed by an erosion using another structuring element (note that asymmetrical opening could also have been con- sidered). The central idea is to make dilation and erosion complementary in terms of the type of cor- ners they affect. This can be realized by choosing a cross as the first structuring element and a lozenge for the second one (Figure 1(b)). We can then write the asymmetrical closing as: Ic+, = ( Iδ+ )ε  (9) and corner strength will be given by comparing the resulting image with the original one, that is: c+(I) = ∣∣I − Ic+,∣∣ (10) Basically, the value of c(x, y) corresponds to the brightness difference between the corner and its back- ground. Note that, as defined, the transformation pro- duces a three-pixel L-shaped response in the case of dark corners We also observed this kind of multiple- pixel response for real images. This must be inter- preted as a consequence of the fact that the precise lo- cation of smooth corners is not well defined. If needed, it is still possible to select only the central point in each set. Corners detected by c+ on a test image are shown in Figure 2(a) (for all experiments to follow, we used the structuring elements shown in Figure 1). Clearly, rotational invariance and small structure sen- sibility have not been solved. To detect the missing corners, the following operator can be used (which is a 45◦ rotated version of the preceding one): c×(I) = ∣∣I − Ic×,✷∣∣ (11) (b) (c) (d) (a) Figure 1: (a) structuring element +. (b) structuring element . (c) structuring element ×. (d) structuring element
. Figure 2(b) shows the corners detected by this oper- ator. Surprisingly, it appears that the two comple- mentary operators, c+ and c×, are sufficient to detect corners of almost any orientation. While these two op- erators are sensitive to corners of different orientation, they are both sensitive to the same small structures. Consequently, the combination of these two operators should make corner detection almost rotationally in- variant and insensitive to small image structures. This leads to the following operator: c+,×(I) = ∣∣Ic+, − Ic×,
∣∣ (12) Results obtained using this last operator are shown in Figure 2(c). This is the operator that we propose to use as a corner detector. To extract corners from the output of c+,×(I), it appeared to us that a sim- ple global thresholding is sufficient even if this leads to multiple-pixel response for some corners (i.e. oc- currence of a corner represented by a few connected pixels in the binary corner map). In fact, we found that non-maxima suppression, which is required in the other methods, does not improve the quality of the detection in the case of asymmetrical closing. In particular, non-maxima suppression does not rule out the multiple-pixel response mainly because the cor- ner strength at these location are nearly equal (to the brightness difference between the corner and its back- ground). However, this multiple pixel response be- havior is not problematic in most applications and the elimination of the non-maxima suppression process re- duces the computational load of the corner detection task. 5 Comparative results In order to test the validity of the operator c+,×(I) as a corner detector, a series of tests were performed. Comparisons were made with the Plessey corner de- tector and the SUSAN corner detector. Sensitivity to noise was tested by adding a gaussian noise to the test image. The comparative results are shown in Figure 3. These tests demonstrate the su- periority of methods based on brightness comparison (a) (b) (c) Figure 2: Corner detection by asymmetrical closing. (a) corner detected by c+. (b) corner detected by c×. (c) corner detected by c+,×. over differential detectors. This observation has also been made in [17]. The SUSAN operator has also been reported to be 10 times faster than the Plessey oper- ator. We observed that the method proposed here is about 2 times more efficient that the SUSAN operator. To evaluate the stability of these detectors, we used a test sequence of 4 images showing a table from dif- ferent points of view. The checkerboard pattern on the table creates 24 corners; the goal here is to test the ability of each operator to detect these 24 corners. Among these corners there are 4 L-junctions, 12 T- junctions and 8 X-junctions. All parameters in each method have been set in order to obtain the best possi- ble results and a comparable density of corner points. For each method, the same parameter values are used for all images of the sequence. For the SUSAN opera- tor and our operator based on asymmetrical closings, we have tested two different threshold values. Results are shown in Figure 4 where we show 2 of the 4 im- ages. Table 1 presents the number of corners that each method has detected. It is not surprising to find, from the analysis of these results, that a lower thresh- old leads to a higher number of detected corners. But, at the same time, the number of false positives grows rapidly. In order to estimate the number of false pos- itives that each method produced, we have counted the number of detected corners lying on the table in each image. The result of this analysis is presented in Table 2. These results demonstrate the reliability of the operator based on asymmetrical closings. It ap- pears to be more stable while producing fewer false positives. It is also interesting to note that, in the case of the operator proposed in this paper, several of the false positive detections are due to the fact that X-junctions tend to produce a two-corner response. 6 Conclusion We have presented a new operator for corner de- tection. It uses a variant of the morphological closing operator, which we have called asymmetrical closing. We found that this kind of approach, based on bright- ness comparisons, leads to better quality results than other approaches and is achieved at a lower computa- tional cost. Stable and accurate corner detection has been obtained using the operator presented in this pa- per. Because of its algorithmic simplicity, we believe that this operator is an efficient means of producing input points of interest for feature-based approaches to 3D structure and motion estimation problems. References [1] S.T. Barnard, W.B. Thompson, “Disparity analy- sis of images”, IEEE Trans. on PAMI, 2:333-340, 1980. [2] J. Weng, N. Ahuja, T.S. Huang, “Matching Two Perspective Views”, IEEE Trans. on PAMI, 14:806-825, 1992. [3] Z. Zhang, R. Deriche, O.D. Faugeras, Q.-T. Lu- ong, “A Robust Technique for Matching Two Un- calibrated Images Through the Recovery of the Unknown Epipolar”, Artificial Intelligence Jour- nal, 78:87-119, 1994. [4] N.A. Thacker, J.E.W. Mayhew, “Optimal combi- nation of stereo camera calibration from stereo images”, Image and vision computing, 9:27-32, 1991 [5] H. Assada, M. Brady, “The curvature primal sketch”, IEEE PAMI, 8(1):2-14, 1986. [6] G. Medioni, Y. Yasumoto, “Corner detection and curve representation using cubic B-splines”, CVGIP, 39:267-278, 1987. [7] R. Deriche, O.D. Faugeras, “2-D curves matching using high curvature points”, Proc. of the 10th IAPR, pp. 18-23, 1990. [8] P.R. Beaudet, “Rotational invariant image oper- ators”, Proc. Int. Conf on Pattern Recognition, pp. 579-583, 1978. [9] L. Kitchen, A. Rosenfeld, “Gray-level corner de- tection”, Pattern Recognition Letters, pp. 95-102, Dec. 1982. [10] L. Dreschler, H.H. Nagel, “Volumetric model and 3D trajectory of a moving car derived from monoculat TV frame sequences of a street scene”, CVGIP, 20:199-228, 1982. [11] O.A. Zuniga, R.M. Haralick, “Corner detection using the facet model”, Proc. Int. Conf. on Pat- tern Recognition, pp. 30-37, 1983. [12] R. Deriche, G. Giraudon, “Accurate corner de- tection: an analytical study”, Proc. Int. Conf. on Computer Vision, pp.66-70, 1990. [13] H.P. Moravec, “Towards automatic visual obsta- cle avoidance”, Proc. Int. Joint Conf. on AI, pp. 584-586, 1977. [14] C.G. Harris, “Determination of ego-motion from matched points”, Proc. Alvey Vision Conf., 1987. [15] J.A. Noble, “Finding corners”, Image and Vision Computing, 6:121-128, 1988. Plessey 87 SUSAN 88 (threshold = 12) SUSAN 90 (threshold = 11) asymmetrical closings 89 (threshold = 10) asymmetrical closings 95 (threshold = 8) Table 1: Number of corners correctly detected on the table. A total of 96 corners were considered in the test sequence, 24 in each image. Plessey 221 SUSAN 163 (threshold = 12) SUSAN 183 (threshold = 11) asymmetrical closings 119 (threshold = 10) asymmetrical closings 157 (threshold = 8) Table 2: Number of detected corners on the table. This number should be equal to 96 in the ideal case. [16] C. Harris, M. Stephens, “A combined corner and edge detector”, Proc. of 4th Alvey Vision Confer- ence, pp. 147-151, 1988. [17] S.M. Smith, J.M. Brady, “SUSAN - a new ap- proach to low level image processing”,Int. Jour- nal of Computer Vision, 1997. [18] R. Deriche, T. Blaszka, “Recovering and charac- terizing image features using an efficient model based approach”, Proc. of CVPR, pp. 530-535, 1993. [19] K. Rohr, “Modeling and identification of charac- teristic intensity variations”, Image and Vision Computing, 10(2):66-76, 1992. (a) (b) (c) Figure 3: Test image with gaussian noise of variance σ2 = 50. (a) Plessey. (b) SUSAN. (c) asymmetrical closing. (a) (b) Figure 4: Corner detection on the test sequence. (a) The SUSAN operator (threshold = 12). (b) Asym- metrical closing (threshold = 10).