Advanced
Region-based Corner Detection by Radial Projection
Region-based Corner Detection by Radial Projection
Journal of the Optical Society of Korea. 2011. Jun, 15(2): 152-154
Copyright ©2011, Optical Society of Korea
  • Received : February 02, 2011
  • Accepted : April 04, 2011
  • Published : June 25, 2011
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Daeho Lee
nize@khu.ac.kr
SeungGwan Lee
Jin Hyuk Choi
Abstract
We propose a novel method which detects convex and concave corners using radial projection. The sum of two neighbors’ differences at the local maxima or minima of the radial projection is compared with the angle threshold for detecting corners. In addition, the use of oriented bounding box trees and partial circles makes it possible to detect the corners of complex shapes. The experimental results show that the proposed method can separately detect the convex and concave corners, and that this method is scale invariant.
Keywords
I. INTRODUCTION
Pattern recognition is widely used for various applications in the fields of medicine, industry, meteorology, and more [1 - 3] . Shape analysis methods play an important role in pattern recognition, matching, registration, and analysis [4] .Shape analysis can be classified into two methods: boundary based or internal (i.e., region) based approaches. The boundary based methods generally use the scale-space filters [ 5 , 6 ] or Fourier transforms [ 7 , 8 ] of the boundary, while the internal based methods use the moment [ 5 , 9 ] and projection [ 10 - 12 ] of the object regions.
The methods which use the Fourier transforms and moments are used to classify the type of object, while the methods which use the scale-space filters and projections are used to find the dominant points and boundary locations. The shapes which can be located by the projections are flat or rectangular boundaries because those functions are generally based on the Cartesian coordinates. However, the projection functions based on polar coordinates may be used for other applications. The ring projection function, which is defined as the accumulated values of the image along a specific radius, can be used as a rotation-invariant feature [11] . The radial projection function, which is defined as the accumulated values of the image at a specific angle, can be used as a feature for topographical shapes [12] .
In this paper, we propose a novel method which can separately detect convex and concave corners by using radial projection. This method is scale invariant.
II. RADIAL PROJECTION FOR CORNER DETECTION
The radial projection function based on polar coordinates is defined, as follows:
PPT Slide
Lager Image
where P rad ( θ ) is the radially accumulated value at a specific angle, θ . To calculate the radial projection function, the origin of the shape is first estimated to be the centroid of the shape.The radial projection is the function of the angles, so that the function can be represented by the discrete angle variables,as follows:
PPT Slide
Lager Image
where P rad ( θ i ) should be expressed within the range [0, 2 π ),so that the difference between the angles is
PPT Slide
Lager Image
PPT Slide
Lager Image
Radial projection for corner detection.
To detect the corners from the computed P rad ( θ i ), the local maximum and minimum positions are assigned as the convex and concave corner directions, respectively, and then the corner angles are computed by the sum of the two neighbor differences ( α 1 and α 2 ), as shown in Fig. 1 ,where the one angle is calculated by
PPT Slide
Lager Image
where c is
PPT Slide
Lager Image
and where k is the neighborhood angle size for detecting corner angles.
As shown in Fig. 1 , if the corner angle ( α 1 + α 2 ) of θ i is concave, then it is less than π . Otherwise, the corner angle ( β 1 + β 2 ) is concave, and it equals 2 π -( α 1 + α 2 ).
III. RADIAL PROJECTION OF COMPLEX SHAPES
It is impossible to analyze a complex shape with only one origin. Thus, we separate the shape into partial regions using tight-fitting oriented bounding box trees (OBB Trees) [13] .The partial shapes then become slab-sided shapes bounded by rectangles, and the corners of each shape are detected using the elliptic mod el.
Ellipses each have a major axis and a minor axis. The direction of the major axis of the approximated is calculated as the average angle from the centroid by
PPT Slide
Lager Image
where ( c x , c y ) denotes the original origin, S denotes a
PPT Slide
Lager Image
Radial projection of slab-sided shapes.
slab-sided shape, and - π / 2 π ≤ φ < π / 2 .
After detecting φ , we shift the original origin in the direction of n =(cos φ , sin φ ). The shifted length ( d ) may be determined using the local axis lengths ( a i and b i ) of the ellipse, as follows:
PPT Slide
Lager Image
where a i ; and b i denote the transverse diameter and the conjugate diameter of the half region with respect to the shifted direction, respectively, and κ denotes a scaling factor for a partial circle. By using the shifted origin, the radial projection is calculated within a limited angle range ( τ θ ),as shown in Fig. 2 , where τ θ ; may be determined by d .
The origin may be shifted in the directions parallel to and perpendicular to n, so that four partial circles are generated,as shown in Fig. 2 .
IV. EXPERIMENTAL RESULTS
To evaluate the proposed method, we tested it using six images, as shown in Fig. 3 . The test was performed for N =180 and k =10, and corners with angles less than 2 π /3 were detected. In Fig. 3 , the origins are marked with red crosses, the convex corners are marked with large dots, the concave corners are marked with small dots.
For the six shapes tested, we calculate the MSE (mean square error), which is defined by
PPT Slide
Lager Image
where
PPT Slide
Lager Image
and
PPT Slide
Lager Image
are the calculated angle and the ground truth angle of the i-th corner (in radians), respectively, and n is the number of corners detected. The MSEs of the six shapes tested are very low, as shown in Table 1 .
To evaluate the performance with regard to the scale invariant measure, we tested the images with a zoom of 2x and 4x with the same parameters ( N and k ) and then calculated the standard deviations of the detected corners.The average of the standard deviation
PPT Slide
Lager Image
of the tested
PPT Slide
Lager Image
Corner detection results.
MSE of the tested six shapes
PPT Slide
Lager Image
MSE of the tested six shapes
of the tested six shapes
PPT Slide
Lager Image
of the tested six shapes
PPT Slide
Lager Image
Fingertip and finger valley detection results.
shapes is very low, as shown in Table 2 . Previous methods,however, were very sensitive to scale parameters, so that the corners could not be reliably detected.
To evaluate the performance for complex shapes, we tested our method for fingertip detection. The original images were binarized using color differences. The partial circles were generated using κ =1.7, the radial projections were calculated for N =180 and k =5 within Γ θ < 3π/ 2, and corners with angles less than 2π / 3 were detected. The results are shown in Fig. 4 , where the bright (gray) crosses indicate the original origins, and the dark (red) crosses indicate the shifted origins. The proposed method detected the convex and concave corners separately, so that the fingers and the finger valleys were correctly detected.
V. CONCLUSIONS
This paper proposes a novel method which detects convex and concave corners by using radial projection. The corner angle is calculated using the sum of two neighbor differences at the local maxima or minima of the radial projection function. The use of oriented bounding box trees and partial circles enables the detection of the corners of complex shapes. Moreover, this method can detect the same corners of scaled and rotated images with the same parameters.Therefore, the proposed method may play a strong role in corner detection, image matching, and other applications.
References
Zhenjiang M 2000 Zernike moment-based image shape analysis and its application Patt. Recogn. Lett. 21 169 - 177
Lee D , Choi J. H 2010 Precise detection of car license plates by locating main characters J. Opt. Soc. Korea 14 376 - 382
Kim M. K 2010 Adaptive thresholding technique for binarization of license plate image J. Opt. Soc. Korea 14 368 - 375
Loncaric S 1998 A survey of shape analysis techniques Patt. Recogn. 31 983 - 1001
Pei S , Lin C 1992 The detection of dominant points on digital curves by scale-space filtering Patt. Recogn. 25 1307 - 1314
The C , Chin R. T 1989 On the detection of dominant points on digital curves IEEE Trans. Patt. Anal. Mach. Intell. 11 859 - 872
Zahn C. T , Roskies R. Z 1972 Fourier descriptors for plane closed curves IEEE Trans. Comp. 21 269 - 281
Granlund G. H 1972 Fourier preprocessing for hand print character recognition IEEE Trans. Comp. 21 195 - 201
Hu M 1962 Visual pattern recognition by moment invariants IRE Trans. Inf. Theory 8 179 - 187
Zhou Z , Geng X 2004 Projection functions for eye detection Patt. Recogn. 37 1049 - 1056
Tsai D , Tsai Y 2002 Rotation-invariant pattern matching with color ring-projection Patt. Recogn. 35 131 - 141
Kwon Y , Park H , Liu J , Nascimento M. A 2005 Radial projection: a feature extraction method for topographical shapes LNCS 3769 582 - 593
Gottschalk S , Lin M. C , Manocha D “OBB tree: ahierarchical structure for rapid interference detection” in Proc. Int. Conf. on Computer Graphics and InteractiveTechniques (New Orleans USA Aug. 1996) 171 - 180