|
 |
| ARTICLE |
|
|
|
| Year : 2011 | Volume
: 57
| Issue : 3 | Page : 286-293 |
|
|
Adaptive Corner Detection Algorithm and its Extension using Window-based Approach for Gray-scale Images
Ambar Dutta1, Avijit Kar2, BN Chatterji3
1 Department of Computer Science & Engineering, Birla Institute of Technology, Mesra, Kolkata Campus, Kolkata, India
2 Jadavpur University, Kolkata, India
3 Department of Electronics & Communication Engineering, B. P. Poddar Institute of Management and Technology, Kolkata, India
| Date of Web Publication | 9-Aug-2011 |
Correspondence Address:
Ambar Dutta
Department of Computer Science & Engineering, Birla Institute of Technology, Mesra, Kolkata Campus, Kolkata
India
 DOI: 10.4103/0377-2063.83651
 Abstract | | |
In computer vision, the corners of an object play an important role in shape representation and analysis. In this paper, we carried out a dozen popular and most cited corner detection algorithms and studied their performances based on several performance measures proposed by us as well as in the literature over a varied range of images and categorized the corner detectors based on different image types and rank their performances with suitable threshold ranges corresponding to different image types. After obtaining a suitable corner detector for a given type of images, the paper describes a new approach to corner detection in a digital image based on the assumption that corners are those image points with high information content, and hence corners in an image exist in those regions having considerably high-intensity variation. Consequently, a complex corner response function is computed only within those regions with considerable high-intensity variation instead of entire image, reducing the computational cost of the whole procedure. Experiments conducted with the help of a few images showed the efficiency of the technique, both in terms of execution time and false-positive corners. Keywords: Adaptive, Corner, Tri-modal histogram, Threshold, Window selection
How to cite this article:
Dutta A, Kar A, Chatterji B N. Adaptive Corner Detection Algorithm and its Extension using Window-based Approach for Gray-scale Images. IETE J Res 2011;57:286-93 |
How to cite this URL:
Dutta A, Kar A, Chatterji B N. Adaptive Corner Detection Algorithm and its Extension using Window-based Approach for Gray-scale Images. IETE J Res [serial online] 2011 [cited 2013 May 21];57:286-93. Available from: http://www.jr.ietejournals.org/text.asp?2011/57/3/286/83651 |
| 1. Introduction | |  |
For many years, feature detection has played a key role in computer vision. Feature detection consists of the following three main activities: Region detection, edge detection, and corner detection. Here, we focus on the last activity. Corner detection in images is essential for many tasks in machine vision, including scene analysis, motion and structure from motion analysis, image registration, image matching, object recognition, etc. Corners in an image are the points that show a strong two-dimensional intensity change, and are hence well distinguished from neighboring points. Corner detection is an essential part of low-level image processing and computer vision. Since information about a shape is concentrated at the corners and corners can be considered to be descriptive primitives in shape representation and image interpretation, corner detection is useful in many vision applications.
It is desirable for a corner detector to satisfy a number of criteria:
- All true corners should be detected and no false corners should be detected.
- Corner points should be well localized. Localization refers to how accurately the position of a corner is found. This is critical in applications requiring the precise alignment of multiple images (for example, in registration of video frames).
- The detector should have a high repeatability rate.
- Since noise in images is unavoidable in most applications, a corner detector must be robust against it. The corner detector should not incorrectly identify noise as corner points and noise should have minimal effect on the localization ability of the detector.
- The detector should be computationally efficient with respect to time.
An extensive number of corner detection algorithms have been reported by vision researchers. Corner detection algorithms can be broadly divided into two classes-boundary-and intensity-based. Boundary-based methods rely on extraction of contours of regions either by edge detection or by segmenting the image into regions followed by boundary finding. Thus, these methods largely depend on the prior segmentation process. On the other hand, the intensity-based methods estimate a measure to detect corners directly from the Gray values of the original images without a prior segmentation. Rutkowski et al. [1], Heyden and Rohr [2], Zheng et al. [3], Schmid et al. [4], Rockett [5], Tissainayagam and Suter [6], Mokhtarian and Mohanna [7], Sebe et al. [8], and Dutta et al. [9] provided good literature survey on the existing corner detection algorithms and evaluated their performances.
Our novel contribution is two-fold. First of all, we suggested the suitable corner detection algorithms, based on the nature of images, along with the appropriate range of threshold values for different cornerness measures used by the algorithms. Using this, one can easily be able to adapt a suitable corner detection algorithm just by seeing the image and understanding its type. Second, we included the concept of window (or region)-based corner detection. Corner detection algorithms will be carried on those regions only in which significant intensity variations among the pixels are present, rather than on the entire image. This approach will be useful to reduce the number of false-positive corner detection which is one of the key requirements in corner matching. Moreover, since complex calculations of corner response function (CRF) involving intensity values of pixels are done only on a few of the selected regions, not on the entire image, this approach will be computationally efficient.
The rest of the paper is organized as follows. In Section 2, we present the related research and in Section 3, we propose to adapt appropriate corner detection algorithms for different categories of images with suitable range of one or more threshold(s). In section 4, we briefly discuss our proposed window-based approach. Experimental results are then presented and compared with the original version of the algorithms in Section 5. We, finally, draw our conclusions in Section 6.
| 2. Related Research | | |
Since 1977, when Moravec gave his idea of "points of interest" to find the corners, vision researchers have developed a large number of intensity-based corner detection algorithms in the last three decades. We have identified and implemented 12 most popular and most cited algorithms as a representative set of these algorithms and observed their performance across various kinds of test images. Each of these algorithms relies on calculating a CRF based on pixel intensity values of an image and their derivatives. Local maximum of this measure followed by non-maximum suppression isolates the corners.
Moravec [10] detected corners at the locations where a significantly high-intensity variation is found in all directions. Beaudet [11] presented a determinant operator, which has large values near the corners. Kitchen and Rosenfeld [12] derived a cornerness measure by applying differential operators consisting of first- and second-order partial derivatives of an image to detect corners. Zuniga and Haralick [13] proposed a facet model-based corner detector. Harris and Stephens [14] estimated the cornerness measure based on local autocorrelation using first-order derivatives. Shi and Tomasi [15] proposed a method for feature selection, a tracking algorithm based on a model of affine image changes, and a technique for monitoring features during tracking. Wang and Brady [16] proposed a corner detection algorithm based on the cornerness measurement of the total surface curvature. Smith and Brady [17] proposed SUSAN corner detector using the concept that each image point is associated with a local area of similar brightness. Trajkovic and Hedley [18] presented a fast corner detector using a multigrid approach. Laganiere [19] presented a morphological corner detector. Zitova et al. [20] proposed a two-stage method for detecting the feature points in which all possible candidates are found first and then the desirable number of resulting significant points is selected among them by maximizing the weight function. Zheng et al. [3] presented an extended version of Plessey corner detector. Lv and Zhou [21] modified the cornerness measure of Kitchen-Rosenfeld detector based on the perception of human vision system to make the detector effective in variable illumination scenes. Golightly and Jones [22] presented an algorithm for both corner detection and matching for visual tracking of power line inspection. Mikolajczyk and Schmid [23] proposed a scale and affine invariant corner detector. Alkaabi and Deravi [24] presented a fast corner detection algorithm based on pruning candidate corners. Vincent and Laganiere [25] proposed a new feature point detector which first performs a simple segmentation based on the intensity values found in the vicinity of each considered point, and then, it tries to fit a simple wedge corner model to the resulting segmented area. Rosten and Drummond [26] used machine learning for fast and high quality corner detection. Coleman, Scotney and Kerr [27] adopted an existing edge detection method and extended this work to corner detection using the Linear Gaussian product operator. Sebe et al. [8] compared four different algorithms in terms of invariance and distinctiveness of the extracted regions and computational complexity; and proposed a color-based corner detection algorithm.
| 3. Performance Measures | | |
Many performance measures for corner detection algorithms can be found in the literature. We also proposed [9],[28] three new measures, detection gradient (DG), false-positive ratio (FPR), and false-negative ratio (FNR) to compare the efficacy of the algorithms.
where NA, ND, NM and NF denote the total number of corners present in the image, the number of true corners detected, the number of missed (false-negative) corners and number of extraneous (false-positive) corners detected in the image, respectively. In the best case, the value of the DG is zero, which signifies that all the corners are correctly detected without any missed or false corners; the same is true for FPR and FNR. We used our proposed measures in conjunction with four existing measures, Golightly and Jones's [23] detection ratio (DR) and error ratio (ER) and Mokhtarian and Mohanna's [7] accuracy (ACCU) and consistency of corner numbers (CCN) measures.
The value of DR, ER, and ACCU should be close to 1, 0, and 100, respectively, for efficient corner detectors.
| 4. Corner Detection Toward Adaptiveness | | |
Of the two different categories-intensity-based and boundary-based-of corner detection algorithms, we selected the first category for the following reasons. Any boundary-based corner detection algorithm consists of finding the boundary from an image, by following and closing the boundary at every step, which always requires some manual intervention resulting in high computational time. In addition, for real images, it is not always possible to find the exact boundary resulting in poor localization of corners. We have identified and implemented 12 corner detection algorithms listed below in [Table 1] as a representative set of these algorithms and observed their performance across various kinds of test images.
We have classified the set of test images into two categories-synthetic image and real image. Real images are further divided into two subcategories-natural scene and human face. Within each of the categories, we have considered three variations of the images-in original, with uniform or Gaussian noise, and reduced brightness. Performance of the 12 corner detection algorithms over a large number of test images of different categories is observed and noted with respect to different performance measures described in section 3.
4.1 Results
We have observed that different corner detection algorithms performed differently over various categories of images [Figure 1]−synthetic and real images (natural scene and human face) over different ranges of thresholds. We have omitted the table for synthetic images with reduced brightness consciously, because in synthetic images, when we reduced brightness of test images, the performance of corner detectors remains unchanged. In the [Table 2], [Table 3], [Table 4], [Table 5], [Table 6], [Table 7], [Table 8] and [Table 9], we have listed best-performing three corner detection algorithms of the 12 given in [Table 1] for each type of images according to descending order of their performances.
| 5. New Window-Based Approach | | |
Once an appropriate corner detection algorithm with suitable range of thresholds is obtained for a given type of image, our next objective is to improve the performance of the existing algorithm. Any corner detection algorithm, when applied on real, noisy scenes with many other features present in the image along with the object of interest, will produce a large number of false-positive corners unless we consider the object of interest only in the image which is the objective of many applications. In such applications, if corner detection algorithm is performed on the entire image instead of the object of interest, then it will detect a number of extra undesirable corners. Moreover, since a complex CRF containing image intensities and their derivatives is required to be calculated on the whole image instead of the small region of interest, it will take longer computational time. But, in order to deal with these kinds of applications, it is extremely essential to identify the region of interest properly. Otherwise, either we shall miss a few valid corners, or obtain a few extra corners. Since corners are those image points with high information content, corners in an image exist in those regions having considerably high-intensity variation. So, after dividing the entire image into a number of regions, we considered only those regions which have high variations in intensities. Moreover, corners are obtained at the intersections of at least two edges or straight line segments in the image. Therefore, after separating the regions with high variations, we further checked the existence of at least two edges in those regions to obtain the final set of regions on which we have to apply the corner detection algorithm.
5.1 Gray-level Histogram
Gray-level histogram is one of the simplest and most useful tools in digital image processing. This function summarizes the Gray-level content of an image, which shows for each Gray level, the number of pixels in the image having that Gray level, but it gives no hint as to where those pixels are located within the image. A histogram can be computed by using an array data structure and a very simple procedure. The histogram of a digital image typically has many local minima and maxima, that is, a histogram of an image can be bi-modal or multi-modal. From the two modes of a bi-modal histogram of an image, a suitable threshold may be calculated which will divide the image into two regions. Thus, a bi-modal histogram may generate two regions separated by an edge. Since corners are formed at the intersection of two or more edges, three or more regions may be formed around the neighborhood of a corner. So, if a region contains a corner, then the histogram of that region will contain at least tri-modal histogram [Figure 2].
5.2 Algorithm
The proposed algorithm is as follows:
- The whole image I into a number of n non-overlapping mutually exclusive regions R1, R2, …….., Rn of equal size, where the value for n will be determined from the size of the image I.
- Calculate the standard deviation σ of the intensity values of the pixels within each region Ri , i=1, 2, ……., n.
- The histogram H(Ri) of the region Ri is obtained and it is examined for the existence of at least three well-separated modes in the histogram within those regions only for which the standard deviation σ is greater than a suitable threshold. If at least a tri-modal histogram is obtained, go to step 4; otherwise, that region is ignored from further processing.
- The region is further examined whether its size can be reduced, that is, its size is greater than allowable window size. The region is divided into four equal parts and the standard deviation of the reduced region is computed.
- If the standard deviation of the intensity values of the pixels in the reduced region is still greater than the previous threshold, then go to step 4; otherwise, that region is prohibited from further reduction.
- Perform corner detection algorithm on the reduced region.
In step 3, in the histograms of each region, well-separated modes are desirable, but not compulsory. If the modes are well-separated, then a more suitable threshold and hence more appropriate edge can be obtained. Otherwise, edges will not be prominent and therefore, proper corners will not be obtained, since corner is the intersection of two or more edges.
5.3 Results with Extended Algorithm
To describe the efficiency of our window-based approach, experiments are conducted on a large number of synthetic and real images. In [Figure 1], some representative images are listed. In each of the images, the brightness is artificially reduced, uniform (or Gaussian) noise is added, and geometric transformation (translation and rotation) is applied, and experiments are conducted to test the accuracy and consistency of the extended corner detection algorithm. Performances of original corner detection algorithms are observed and it can be seen from the [Figure 3], [Figure 4], [Figure 5] and [Figure 6] that original corner detectors detect a number of false-positive (extra) corners which is not desirable when corner detectors are used in feature matching problem. It is also observed that proposed window-based approach to corner detection is computationally more efficient compared with original corner detectors as window-based approach to corner detection is applied on smaller regions in which there are significant high-intensity variations.
In case of window-based approach, we reduced the size of the window based on the intensity variations within the window and existence of at least tri-modal histogram there and on that reduced window, we applied an existing corner detector to obtain an improved set of corners. Improvement of the window-based corner detection algorithm can also be seen from the [Figure 7], [Figure 8] and [Figure 9]. On the other hand, since original corner detectors involved in calculation of a complex CRF containing image intensities and their derivatives on the whole image instead of the small region of interest, they will take longer computational time. Improvement in the efficiency with respect to the computational time is observed from [Figure 10] where we plotted average computational time taken by original algorithm and window-based algorithm across different test images of various categories. For different types of images, we first calculated the computational time of all the original algorithms [Table 1] and our extended algorithm (with the concerned original algorithm in step 6) and finally calculated their average. Then, we plotted this average computational time with respect to different types of images. | Figure 7: Improvement of window-based corner detector with respect to detection gradient.
Click here to view |
 | Figure 8: Improvement of window-based corner detector with respect to false-positive ratio.
Click here to view |
 | Figure 9: Improvement of window-based corner detector with respect to Mokhtarian's accuracy measure.
Click here to view |
 | Figure 10: Improvement of window-based corner detector with respect to computational time.
Click here to view |
| 6. Conclusion | | |
In this paper, we compared the performance of 12 existing intensity-based corner detection algorithms with the help of a significant number of test images of different categories and listed the best three algorithms for each type of images with suitable range of threshold(s) that should be used. It will help in determining the appropriate corner detection algorithms according to the input image on which the algorithm is to be applied. In a way, we adapted an appropriate corner detector based on the type of the image. After getting an appropriate corner detector for a given type of image, we presented an extension using the concept of window splitting to existing corner detection algorithms. Before applying any corner detector to a given image, the image is at first divided into a number of regions and those regions are investigated for significant intensity variations, as a corner is an image point with high contrast along all the directions. Moreover, it may be assumed that a region containing at least one corner should have at least two edges forming more than two subregions which are resolved with the help of a histogram technique. Corner detection algorithm was then applied to the smallest possible regions in order to improve computational efficiency and to reduce the number of false-positive corners in the image which will be one of the necessary requirements for feature (corner) matching problem. The performance of the algorithm depends on the threshold that indicates how much variations we are allowing in the region containing corners and what is the minimum size of a window after which we shall prohibit further subdivisions. We are working on these thresholds.
| References | | |
| 1. | W S Rutkowski, and A Rosenfeld, "A comparison of corner detection techniques for chain-coded curves", Technique Report TR-623, Computer Science Center, University of Maryland, 1978. 
|
| 2. | Heyden, and K Rohr, "Evaluation of Corner Extraction Schemes Using Invariance Methods", in Proceedings of International Conference on Pattern Recognition, Vienna, Austria, pp. 895-9, 1996.
|
| 3. | Z Zheng, H Wang, and E K Toeh, "Analysis of Gray Level Corner Detection", Pattern Recognition Letters, vol. 20, pp. 149-62, 1999.
|
| 4. | C Schmid, R Mohr, and C Bauckhage, "Evaluation of Interest Point Detectors", Int J Comp Vis, vol. 37, no. 2, pp. 151-72, 2000.
|
| 5. | P I Rockett, "Performance Assessment of Feature Detection Algorithms: A Methodology and Case Study on Corner Detectors", IEEE Tran. on Image Process., vol. 12, no. 12, pp. 1668-76, 2003.
|
| 6. | P Tissainayagam, and D Suter, "Assessing the performance of corner detectors for point feature tracking applications", Image and Vision Computing, vol. 2, pp. 663-79, 2004.
|
| 7. | F Mokhtarian, and F Mohanna, "Performance Evaluation of Corner Detectors using Consistency And Accuracy Measures", Computer Vision and Image Understanding, vol. 102, pp. 81-94, 2006.
|
| 8. | N Sebe, T Gevers, S Dijkstra, and J van de Weijer, "Evaluation of intensity and color corner detectors for affine invariant salient regions", Proceedings of the 2006 Conference on Computer Vision and Pattern Recognition Workshop (CVPRW'06), Washington, USA, 2007.
|
| 9. | A Dutta, A Kar, and B N Chatterji, "Corner Detection Algorithms for Digital Images in Last Three Decades", IETE Tech Rev, vol. 25, no 3, pp. 123-34, 2008.
|
| 10. | H P Moravec, "Towards Automatic Visual Obstacle Avoidance", Proceedings of 5th International Joint Conference on Artificial Intelligence, Cambridge, Massachusetts, pp. 584, 1977.
|
| 11. | P R Beaudet, "Rotationally Invariant Image Operators", Proceedings of International Joint Conference on Pattern Recognition, Kyoto, pp. 579-83, 1978.
|
| 12. | L Kitchen, and A Rosenfeld, "Gray Level Corner Detection", Pattern Recognition Letters, vol. 1, no. 2, pp. 95-102, 1982.
|
| 13. | O A Zuniga, and R M Haralick, "Corner Detection using the Facet Model", Proceedings of Conference on Computer Vision and Pattern Recognition, Washington, USA, pp. 30-7, 1983.
|
| 14. | C Harris, and M Stephens, "A Combined Corner and Edge Detector", 4th Alvey Vision Conference, Manchester, UK, pp. 147-51, 1988.
|
| 15. | J Shi, and C Tomasi, "Good Features to Track", in Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, Seattle, CA, USA, pp. 593 - 600, June 1994.
|
| 16. | H Wang, and M Brady, "Real-Time Corner Detection Algorithm for Motion Estimation", Image and Vision Computing, vol. 13, no. 9, pp. 695-703, 1995.
|
| 17. | S M Smith, and J M Brady, SUSAN - A New Approach to Low-Level Image Processing, "Int J Comp Vision", vol. 23, no. 1, pp. 45-78, 1997.
|
| 18. | M Trajkovic, and M Hedley, "Fast Corner Detection", Image and Vision Computing, vol. 16, no. 2, pp. 75-87, 1998.
|
| 19. | R Laganiere, "A Morphological Operator for Corner Detection", Pattern Recognition, vol. 31, no. 11, pp. 1643-52, 1998.
|
| 20. | B Zitova, J Kautsky, G Peters, and J Flusser, "Robust Detection of Significant Points in Multiframe Images", Pattern Recognition Letters, vol. 20, pp. 199-206, 1999.
|
| 21. | X Lv, and J Zhou, "Robust Corner Detection under Varying Illumination", in Proceedings of International Conference on Information Intelligence and Systems, Bethesda, MD, USA, pp.396-8, 1999.
|
| 22. | Golightly, and D Jones, "Corner Detection and Matching for Visual Tracking during Power Line Inspection", Image and Vision Computing, vol. 21, pp. 827-40, 2003.
|
| 23. | Mikolajczyk, and C Schmid, "Scale and Affine Invariant Interest Point Detectors", International Journal of Computer Vision, vol. 60, no. 1, pp. 63-86, 2004.
|
| 24. | S Alkaabi, and F Deravi, "Candidate Pruning for Fast Corner Detection", Electronic Letters, vol. 40, no. 1, pp. 18-9, 2004.
|
| 25. | E Vincent, and R Laganiere, "Detecting and Matching Feature Points", Journal of Visual Communication and Image Representation, vol. 16, pp. 38-54, 2005.
|
| 26. | E Rosten, and T Drummond, "Machine Learning for High-Speed Corner Detection", in Proceedings of European Conference on Computer Vision, Graz, Austria, pp. 430-43, 2006.
|
| 27. | S Coleman, B Scotney, and D Kerr, "Integrated Edge and Corner Detection", in Proceedings of 14th International Conference on Image Analysis and Processing (ICIAP 2007), Modena, Italy, pp.653-8, 2007.
|
| 28. | A Dutta, B N Chatterji, and A Kar, "Comparing and Evaluating Intensity Based Spatial Domain Corner Detectors", International Journal on Information Processing, vol. 2, no. 4, pp. 48-55, 2008.
|
| Authors | | |
Ambar Dutta did his B.Sc. (Honors) in Mathematics from Presidency College, Kolkata in 1999 and MCA from Jadavpur University, Kolkata in 2002. He is working as a Assistant Professor in the department of Computer Science and Engineering, Birla Institute of Technology, Mesra, Kolkata Campus. He submitted his PhD thesis in Jadavpur University, Kolkata in the area of image processing (corner detection and matching). His research interest includes Image Processing, Pattern Recognition, Data Mining and Soft Computing.
Avijit Kar did his M.Sc. and Ph.D in 1980 and 1984 respectively from IIT Kharagpur. He is currently a professor in the department of Computer Science and Engineering in Jadavpur University, Kolkata. He has supervised several PhD theses and is actively involved in many R & D activities and IT related consultancy for Government of India and the private sector. His research interest includes biomedical imaging as well as SAR imaging. He is also into computer systems reliability. He is involved in a large number of industry sponsored development projects.
B. N. Chatterji obtained BTech (Hons) (1965) and Phd (1970) in Electronics and Electrical Communication Engineering of IIT, Kharagpur. He did Post Doctoral work at University of Erlangen-Nurenberg, Germany during 1972 - 73. Worked with Telerad Pvt Ltd, Bombay (1965), Central Electronics Research Institute, Pilani (1966) and IIT, Kharagpur as faculty member during 1967 - 2005. He was Professor during 1980 - 2005, Head of the Department during 1987 - 1991, Dean Academic Affairs during 1994 - 1997 and Member of Board of Governors of IIT, Kharagpur during 1998 - 2000. He has published about 150 journal papers, 200 conference papers and four books. He was Chairman of four International Conferences and ten National Conferences. He has coordinated 25 short-term courses and was the chief investigator of 24 Sponsored Projects. He is the Fellow/Life Member/Member of eight Professional Societies. He has received ten National Awards on the basis of his Academic/Research contributions. His areas of interests are Pattern Recognition, Image Processing, Signal Processing, Parallel Processing and Control Systems.
[Figure 1], [Figure 2], [Figure 3], [Figure 4], [Figure 5], [Figure 6], [Figure 7], [Figure 8], [Figure 9], [Figure 10]
[Table 1], [Table 2], [Table 3], [Table 4], [Table 5], [Table 6], [Table 7], [Table 8], [Table 9]
|
