J. Cent. South Univ. (2012) 19: 2528-2533
DOI: 10.1007/s11771-012-1306-9
High-speed corner detection based on fuzzy ID3 decision tree
DUAN Ru-jiao(段汝娇)1, ZHAO Wei(赵伟)1, HUANG Song-ling(黄松岭)1, HAO Kuan-sheng(郝宽胜)2
1. State Key Laboratory of Power Systems (Department of Electrical Engineering, Tsinghua University), Beijing 100084, China;
2. Economic Planning Research Institute of Ministry of Railway, Beijing 100033, China
? Central South University Press and Springer-Verlag Berlin Heidelberg 2012
Abstract: A high-speed corner detection algorithm based on fuzzy ID3 decision tree was proposed. In the algorithm, the Bresenham circle with 3-pixel radius was used as the test mask, overlapping the candidate corners with the nucleus. Connected pixels on the circle were applied to compare the intensity value with the nucleus, with the membership function used to give the fuzzy result. The pixel with maximum information gain was chosen as the parent node to build a binary decision tree. Thus, the corner detector was derived. The pictures taken in Fengtai Railway Station in Beijing were used to test the method. The experimental results show that when the number of pixels on the test mask is chosen to be 9, best result can be obtained. The corner detector significantly outperforms existing detector in computational efficiency without sacrificing the quality and the method also provides high performance against Poisson noise and Gaussian blur.
Key words: corner detector; fuzzy ID3 algorithm; decision tree; computation efficiency; real-time
1 Introduction
The corners in an image are the points that change rapidly in directions, often in the form of the locally maximal curvature of a curve, the place two lines meet at an angle, isolated points and so on. Corners always have a well-defined position and can be robustly detected in an image and therefore usually perform as the initial step in a wide variety of applications for computer vision, including motion detection, image matching, tracking, 3D modeling and many other tasks [1-3].
Numerous methods for finding corners are presented. These corner detectors can be divided into the following classes: 1) Corner detectors by computing the corner response function across the image. HARRIS and STEPHENS [4] introduced a function designed to detect both corners and edges based on a linear combination of the determinant, which is the revision of detector proposed by MORAVEC [5]. SHI and TOMASI [6] calculated the minimum of the eigenvalue decomposition of the structure tensor function. In Ref. [7], a new cornerness formula for the Harris corner detector was proposed, which was used to analyse the corner angle range detected by the Harris detector for some applications and find out the actual corner angle. In Ref. [8], a novel method for multi-scale corner analysis and detection was presented. This multi-scale transform was used jointly with the Harris corner indicator to build a new multi-scale corner detector. A corner selection strategy based on the Harris approach was described in Ref. [9]. The main idea of this approach is to search only the corners near enhanced edges, and by a z-score normalisation, to avoid the introduction of the linear combination coefficient. 2) Corner detectors based on edge detection. KITCHEN and ROSENFELD [10] proposed a method on the gradient magnitude of the boundary. HE and YUNG [11] proposed a curvature-based corner detector that detected both fine and coarse features accurately at low computational cost. ZHANG et al [12] discussed the gradient feature distribution of planar curves and constructed gradient correlation matrics over the region of support of these planar curves. 3) Corner detectors by examining the small patches in an image. SMITH and BRADY [13] used a circular mask over the pixel to test and find the corners in which no derivatives were used. JEON et al [14] proposed a corner point detection algorithm using extreme value from gray level image which was derived from SUSAN approach. A similar idea was explored in Ref. [15], where pixels on a circle were considered and compared to the center of a patch.
Since second derivatives are not required for the third class, these corner detectors are computationally efficient compared to the detectors in the other two classes. However, they are still not suitable for real-time application. In the recent years, one method using machine learning to partition corner candidates as corners or non-corners has been proposed, which has significant performance promotion for real-time application. In Ref. [16], a three-layer neural network is trained to recognize corners, but it should be applied to image after edge detection and thinning. In the context of real-time detection, VIOLA and JONES [17] suggested to use integral images, which allow for very fast computation of Haar wavelets or any box-type convolution filter. In Ref. [18] a corner detection approach FAST was introduced, which is a modification of the SUSAN corner detector, but the approach has some drawbacks on over-fitting and error propagation.
In this work, a novel corner detection algorithm based on the fuzzy ID3 (iterative dichotomiser 3) decision tree was proposed, aiming to improve the detection speed and work for the real-time applications. First, a Bresenham’s circle test mask with 3-pixel radius was used, overlapping the candidate corner with the nucleus. Second, pixels on the circle were compared with the nucleus of the intensity value, with the membership function used to give the fuzzy result. Third, a classification rule was defined, according to the fact that the pixels with maximum information gain were chosen to be the parent nodes. Last, a binary decision tree was built as the corner detector to partition the corners and non-corners.
2 Fuzzy ID3 decision tree
The decision tree is a decision support tool that uses a tree-like graph or model of decisions and their possible consequences. In decision tree learning, ID3 is an algorithm used to generate a decision tree invented by QUINLAN [19]. The algorithm builds a decision tree from relatively small training set of data to organize and process very large data sets. ID3 algorithm is a greedy algorithm that selects the next attribute based on the information gain associated with the attributes and the information gain is measured by entropy. Fuzzy ID3 decision tree [20] is an extension of ID3 decision tree and an effective method to extract knowledge in uncertain classification problems. It is more appropriate for dealing with the problem of the vagueness and ambiguity associated with human thinking and perception. Basic concepts for fuzzy ID3 algorithm are presented.
Definition 1: Considering that a universe of objects S is classified by a set of classes Ci (i=1, 2, …, n), and SCi is the subset of S, which belongs to class Ci, then the proportion Pi representing Ci is
(1)
where T(S) is the cardinality measure of the fuzzy set S, which is the summation of the membership values.
Definition 2: The fuzziness of the fuzzy set S is defined by
(2)
Definition 3: Given an internal node with a fuzzy data set D, described by a collection of attributes {A1, A2, …, Am}, with each attribute Ai having ki linguistic terms, we can partition the data set D into subsets Dij (j=1, 2,…, ki) based on the domain (linguistic values) of attribute Ai . The fuzzy entropy of data set D according to attribute Ai is measured by the following entropy:
(3)
The definition of information gain for an attribute Ai related to the set D is
(4)
3 Corner detection based on fuzzy ID3 decision tree
3.1 Problem description
A Bresenham circle with radius of 3 pixels which has been considered as a test mask is illustrated in Fig. 1. The test mask is used to move over the image and overlap the nucleus with the corner candidates. If there exists a set of N contiguous pixels in 16 circle pixels, which are all in the ‘brighter intensity’ interval or all in the ‘darker intensity’ interval compared with the nucleus pixel intensity, then the nucleus point is classified as a corner. But as to which pixels on the circle should be compared first and so forth. Obviously, different choice leads to a difference in speed. In this work, a decision tree based on fuzzy ID3 algorithm is built to solve this problem.
Fig. 1 Test mask
3.2 Data set fuzzification
Because the image intensity is a continuous domain but not discretization, it is hard to define the boundary of the intensity between bright and dark. Therefore, the fuzzy concept is quoted to substitute the sample data with the fuzzy expression. Then, the dataset would be partitioned into three fuzzy classes, “bright”, “similar”, “dark”, by using the membership function as follows.
1) Bright: Using S-shaped curve membership function:
(5)
where a and b are constants.
2) Dark: Using Z-shaped curve membership function:
(6)
3) Similar: Using Π-shaped curve membership function:
(7)
The membership function used here is illustrated in Fig. 2.
Fig. 2 Membership function
3.3 Building of decision tree
Here, a binary decision tree is built using fuzzy ID3 algorithm, which is more efficient and more generic. The general idea is as follows: For each location xi (i=1, 2, …, 16) on the circle mask, the intensity of the pixel at that position relative to the nucleus pixel would have five states “darker”, “not darker”, “similar”, “brighter” and “not brighter”, which is assigned as Eq. (8). Once a pixel xi (i=1, 2, …, 16) has been chosen, this comparison is then conducted to evaluate for this given pixel, and the response will be used to decide the following pixel and comparison question to query:
(8)
where Ix is the intensity of a pixel; SId is the intensity region of “darker”, and SIb is the intensity region of “brighter”; μd, μs, μb are the degrees of membership belonging to corresponding regions.
The steps of corner detection based on fuzzy ID3 decision tree are as follows, and the corners could be searched by traversing the tree.
Step 1: Equation (8) is computed for each pixel xi (i=1, 2, …, 16) for comparing all the candidate corners c∈C, where C is the set of candidate corners. And μd, μs, μb are computed according to Eqs. (5)-(7).
Step 2: Calculate the information gain G according to Eqs. (1)-(4) for each xi (i=1, 2, …, 16) with attribute Ad (darker), As (similar) and Ab (brighter).
Step 3: Select the pixel xi that can obtain Gmax.
Step 4: If Gmax≤0, then judge the node according to the following conditions; stop expanding the tree if it satisfies at less one, then admit it as a leaf-node.
1) The proportion of one class is greater than or equal to a threshold α.
2) The number of a data set for a child-node is less than a threshold β.
3) There are no attributes for more classifications.
Step 5: If Gmax>0, then it is a parent node, and divide corner set C into subset Ci (i=d, s, b) according to attribute Ai (i=d, s, b).
Step 6: Replace C by Ci (i=d, s, b) and repeat from Step 2 recursively for the rest xi pixels.
4 Experimental results and validity verification
A good corner detector must satisfy a number of criteria, including distinguishing true corners from accidental ones, reliably detecting in the presence of realistic image noise, and precisely and accurately determining the corner locations, and finally it should be possible to implement the detector efficiently enough that it can be utilized in real-time application. In this section, implementation details were present for the detector included in our comparison. First, the proposed method was evaluated on image with changing the pixels number N on test mask. Then, the robustness was tested with Poisson noise and Gaussian noise. Finally, the proposed method was compared with the state-of-the-art methods.
4.1 Detection ability and algorithm robustness
To verify the validity of the proposed algorithm, the detection experiments were performed on the real images of high-speed electric locomotive power supply catenary positioning device which was used for detection method research in project J2008X011.
Figure 3 shows the experimental results tested by the method proposed here for varying the test number N of pixels on test circle. The image tested is the registration assembly of a contact line, which was taken in Beijing’s Fengtai Railway Station in Beijing with a resolution of 963×816 pixels. All the numerical values for N from one to sixteen have been tested. The results indicate that when N is chosen to be nine, the method admits for both high-speed and good quality. For the trend is significant, only two numerical values beside N=9 on each sides are selected. The performances are shown in Figs. 4(a)-(e). It can be obviously observed that, with the changing of N, the detection accuracy decreases for both sides around N=9. And the timing test of five different numerical values given in Table 1 also indicates that it performs better when N=9.
The performance of the corner detector is shown in Fig. 4 when adding Poison noise and Gaussian blur (σ=15, 20) in the image. The proposed method performs very well against the Poison noise and does not have mass fault detected corners until σ=20 of Gaussian blur. The experimental results illustrate the robustness of the method proposed and can locate quite reliably under a wide range of illuminating conditions.
4.2 Comparison with state-of-the-art methods
Harris algorithm and SUSAN algorithm are chosen as references, which are the most widely-used and well-developed corner detectors. As discussed above, when N=9, our method can achieve the best performance. These three algorithms are applied on both artificial images and real images, as shown in Fig. 5. The performance of the proposed corner detector is better than the other two on the artificial image. As to the real image, our method successfully eliminates the error detection corners on the edge. Timing test is also performed on the images, as listed in Table 2. Our algorithm offers considerably higher performance than the other two. Thus, it is more suitable for real-time applications.
Fig. 3 Performances with different numerical values of N: (a) N=7; (b) N=8; (c) N=9; (d) N=10; (e) N=11
Table 1 Computational time with different numerical values of N
Fig. 4 Test against noise: (a) N=9; (b) Poison noise; (c) Gaussian blur (σ=15); (d) Gaussian blur (σ=20)
Fig. 5 Artificial test images (a1-c1) and real test images (a2-c2)
Table 2 Computation time
5 Conclusions
1) The membership function is used to fuzzify the sample data which is more accommodated to vagueness and ambiguity in human thinking and perception.
2) A Bresenham circle with 3-pixel radius is used as the test mask and a comparative rule is designed. The only amount of calculation is the comparison of the intensity between the pixels on the circle with the nucleus without the computation of the second derivative, which is much faster and can ensure the high speed.
3) A binary decision tree is built according to the fuzzy ID3 algorithm, which is the corner detector by traversing the whole binary decision tree. The experimental results show that the proposed detector is many times faster than other two widely used corner detectors and also has high detection quality and robustness.
References
[1] CHANG Liu, PONG C Y, GUO Ping-qiu. Object motion detection using information theoretic spatio-temporal saliency [J]. Pattern Recognition, 2009, 42(11): 2897-2906.
[2] MIYAZAWA K, ITO K, AOKI K, KOBAYASHI K, NAKAJIMA H. An effective approach for iris recognition using phase-based image matching [J]. IEEE Trans Pattern Analysis and Machine Intelligence, 2008, 30(10): 1741-1756.
[3] GINGOLD Y, IGARASHI T, ZORIN D. Structured annotations for 2D-to-3D modeling [J]. ACM Transactions on Graphics, 2009, 28(5): 148-157.
[4] HARRIS C, STEPHENS M. A combined corner and edge detector [C]// Proceedings of the 4th Alvey Vision Conference. Manchester: 1988: 147-151.
[5] MORAVEC H. Obstacle avoidance and navigation in the real world by a seeing robot rover [D]. CMU-RI-TR-80-03. Robotics Institute, Carnegie Mellon University, 1980.
[6] SHI J, TOMASI C. Good features to track [C]// Proceedings of the 9th IEEE Conference on Computer Vision and Pattern Recognition. Seattle, 1994: 593-600.
[7] RYU J B, LEE C G, PARK H H. Formula for Harris corner detector [J]. Electronic Letters, 2011, 47(3): 180-181.
[8] GUEGUEN L, PESARESI M. Multi-scale Harris corner detector based on differential morphological decomposition [J]. Pattern Recognition Letters, 2011, 32(14): 1714-1719.
[9] BELLAVIA F, TEGOLO D, VALENTI C. Improving Harris corner selection strategy [J]. Computer Vision, 2011, 5(2): 87-96.
[10] KITCHEN L, ROSENFELD A. Gray level corner detection [J]. Pattern Recognition Letters, 1982, 1(2): 95-102.
[11] HE Xiao-chen, YUNG N H C. Corner detector based on global and local curvature properties [J]. Optical Engineering, 2008, 47(5): 057008-1-057008-12.
[12] ZHANG Xiao-hong, WANG Hong-xing, SMITH A W B, LOVELL B C. Corner detection based on gradient correlation matrices of planar curves [J]. Pattern Recognition, 2010, 43(4): 1207-1223.
[13] SMITH S M, BRADY J M. SUSAN, a new approach to low level image processing [J]. International Journal of Computer, 1997, 23: 45-78.
[14] JEON B S, WOO D G, MO Y H, LIM M T. An improved corner point detection using extreme value of SUSAN method for measuring a displacement [C]// ICCAS-SICE. Fukuoka, 2009: 18-21.
[15] LEPETIT V, FUA P. Key point recognition using randomized trees [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006, 28(9): 1465-1479.
[16] DIAS P, KASSIM A, SRINIVASAN V. A neural network based corner detection method [C]// IEEE International Conference on Neural Networks. Perth: 1995: 2116-2120.
[17] VIOLA P, JONES M. Rapid object detection using a boosted cascade of simple features [C]// Proceedings of the Conference on Computer Vision and Pattern Recognition. Kauai: 2001: 511-518.
[18] ROSTEN E, DRUMMOND T. Machine learning for high-speed corner detection [C]// Proceedings of the 9th European Conference on Computer Vision-Volume Part I. Graz, 2006: 430-443.
[19] QUINLAN J R. Learning efficient classification procedures and their application to chess end games [M]// Machine learning: An artificial intelligence approach. Springer: Palo alto, 1983: 463-482.
[20] CHANG Zhi-peng. Export textile products anti-dumping early-warning system based on fuzzy decision tree [J]. Computer Engineering and Application, 2009,45(25): 234-237.
(Edited by YANG Bing)
Foundation item: Project(J2008X011) supported by the Natural Science Foundation of Ministry of Railway and Tsinghua University, China
Received date: 2011-08-25; Accepted date: 2011-12-06
Corresponding author: DUAN Ru-jiao, PhD Candidate; Tel: +86-10-62773070; E-mail: drj08@mails.tsinghua.edu.cn
