THE UNIVERSITY OF MICHIGAN COMPUTING RESEARCH LABORATORY DETECTING TIME-VARYING CORNERS Mubarak A. Shah and Ramesh Jain CRL-TR-34-83 NOVEMBER 1983 Room 1079. East Engineering Building Ann Arbor, Michigan 48109 USA Tel: (313) 763-8000

DETECTING TIME-VARYING CORNERS Mubarak A. Shah and Ramesh Jain Department of Electrical and Computer Engineering University of Michigan Ann Arbor, Mi 48109 ABSTRACT The algorithms for structure from motion require solution of the correspondence problem. By detecting only time-varying tokens, the problem may be significantly simplified. In this paper, a time varying corner detector is described which is based on the and operation between the cornerness and the temporal derivative. It is shown that the corner detectors by Zuniga and Haralick, Kitchen and Rosenfeld, and Dreschler and Nagel are equivalent. In our time-varying corner detector, we use Zuniga and Haralick corner detector for finding the cornerness at a point and use absolute value of difference in intensity at a point to approximate the temporal derivative. The results of the time varying corner detector for the the real scenes and the synthetic images with random background and random object are shown. 1

1. Introduction The time varying features play an important role in dynamic scene analysis. The biological systems are capable of detecting features in the environment which are changing with the time. The features may be varying either due to the motion of an object or the observer. The human vision system utilizes both of these means to perceive the world. Certain objects become clear when we move our eyes, head or the body [Gib79 ]. Similarly the perception is improved when the objects move. It is well known that the structure of an object can be determined from its motion. In various approaches to structure from motion [U1179, RoA80, TsH821, correespondence of N points in M frames is required. The correspondence problem is solved by detecting interesting points in frames. Corners are considered good candidates for establishing correspondence [DrN79]. In the proposed approaches for structure from motion the corners are detected in each frame. Since each frame may contain many stationary corners, in addition to a few moving corners, the correspndence becomes more difficult. If only moving corners could be detected, then the matching of corners from frame to frame may become more tractable and computationally efficient. Our efforts to use corners in each frame to determine motion parameters [JeJ831 showed the difficulty in working with corner detectors and encouraged us to investigate possibility of detecting only time-varying corners. Another application of time-varying corners may be in optical flow computation in conjunction with Nagel's approach. Nagel showed that displacement vectors may be computed, using only local intensity values, at grey level corners [Nag83J. This is not surprising because at the corners the aperture problem does not exist. As shown in Figure 1, it is possible to use local methods to compute displacement components at a corner. Nagel also developed a method to propagate displacement vectors at corners to other points in the image. The computation of displacement vectors may be more efficient and correct if only time-varying corners are used in the computation. 2

Haynes and Jain [HaJ83I proposed a time-varying edge detector, which is simple, fast and noise insensitive. The time-varying edge detector should find the points which are edges and which are moving. Therefore, they proposed that and operator be used to combine edginess and motion, which is equivalent to the multiplication. The operator is given as follows: EAzy,t) = y) G(Azy,t)) at Where Ax,y,t) is a frame at time t, Et is the time varying edginess, G is any edge operator (e.g. 3 x 3 Sobel ) and -f is temporal derivative. An important property of this operator is that it can detect the edges which are weak but have significant motion and the edges which are strong but have weak motion. Efficacy of this edge operator was demonstrated using several scenes. In this paper we present a time varying corner detector which gives good results even in images having the random background and random object environment. In the next section we will discuss three gray level corner detectors proposed in the recent years and we will show that all three are essentially equivalent. In section 3 the time varying corner detector is described. In section 4 we present the results for the real and synthetic scenes with the random background and random object. 2. Corner Detection Many corner detector have been reported in the literature[RuR78]. In the earlier approaches, first the image is segmented and then the curvature of the boundary of the object is computed. If that curvature is above some threshold then that point is declared as the corner point. Since the segmentation is far from being perfect, these approaches do not seem to work properly with real scenes. Recently, gray level based corner detectors have been reported which give good results. The attractive point in the gray level based corner detector is that they do not rely on the prior segmentation. Instead the segmentation can be made easy by using corners thus 3

detected [KiR82]. First effort to detect the corners based on the gray levels was made by Baudet[Baud781. Baudet used the DET operator to detect the saddle points at which the gray level function g(x,y) is neither maximum nor minimum. Baudet considers the second order taylor series of function g(x,y) to compute the following: DET = g,: g - (1) This operator finds the corners on the both sides of the edge. The three popular gray level corner detectors are: Zuniga and Haralick[ZuH83], Kitchen and Rosenfeld[KiR831, and Dreschler and Nagel [DrN811. It can be shown that all three corner detectors are equivalent. In fact Nagel[Nag83] has shown that Kitchen and Rosenfeld corner detector is similar to Dreschler and Nagel corner detector. We will show here that, in principle, KitchenRosenfeld corner detector is equivalent to the Zuniga-Haralick corner detector. 2.1. Zunlga-Harallck Corner Detector Zuniga-Haralick corner detector is based on Haralick and Waston' s gray level facet model [HW81]. In this model they fit the bi cubic polynomial to the gray level function. The polynomial used by them is: g(, y) = kl+k2z+ k3y+ k42+ k6zy+ kiy2+ k7z3+ ksz2y+ kzy2+ kjoy (2) Haralick and Waston consider the n*n neighborhood around each pixel and use a least square fit to find the coefficients k,'s in (2). For each pixel they find out the first and second directional derivatives of function g(x,y). The derivatives are taken in the direction (ggy) which is equal to the gradient direction. The pixel is declared an edge point if the first derivative is above some threshold and the second derivative is zero. The corner detector works as follows: at each pixel location the rate aeof change of the gradient angle of the fitted function g(x,y) is computed, which gives a measure of the cornerness. If at any pixel location this cornerness value is above a preset threshold and that point is an edge 4

point then that pixel is declared as a corner. The gradient angle e is given by tang = 9 (3) gy Zuniga and Haralick find the directional derivative of (3) in the direction a equal to (-gy,p) which is orthogonal to the gradient direction (g2,gy). Evaluating the derivative for 9 at origin and using the eq (2) for the function g(x,y) they get the following expression: -2(k2kk-k2k3k6+ k 2k4) (4) ^ -— W^P ~ (4) Where K is the rate of change of 9 which gives the measure of cornerness at the point (z,y). 2.2. KItchen-Rosenfeld Corner Detector Kitchen and Rosenfeld [KiR83J project the change of gradient direction vector (9,,9y) along an edge and multiply the result by the local gradient magnitude. Kitchen and Rosenfeld give the following expression for cornerness: g 9 gy2 + gyy g9 - 2gry ggy K ----- (5) 9s + gy Kitchen and Rosenfeld consider the quadratic polynomial for the gray level fuction g(x,y),but for the sake of the comparision let us consider the bi cubic polynomial as considered by Haralick and Waston. If we now evaluate all the terms in (5) considering the polynomial given in equation (2) at (0,0) and subsititue back in (5), we get the following expression for the cornerness: K=-2(ke - 2k3k + k2k)( (k22 + 42) (6) 5

2.3. Dreschler-Nagel Corner Detector Dreschler and Nagel also consider the function g(x,y) and approximate it with the second order taylor expansion. They use Baudet's operator as given in equation (1). Since Baudet's operator gives corners on both sides of the edge therefore Dreschler and Nagel apply following algorithm to eliminate the false corners: (i) Determine ggyy called Gaussian curvature. (ii) Select locations of extremal -positive as well as negative - Gaussian curvature (iii) Match a location of maximum maximum positive Gaussian curvature such as P with a location of extreme negative Gaussian curvature such as B provided that the directions of those principal curvatures i.e.g,, and gyy which have opposite sign at B and P are approximately aligned. (iv) Select point T where the principal curvature crosses zero. This correspond to the corner point. 2.4. Equivalence of Three Corner Detectors Nagel[Nag83j has shown that their corner detector is equivalent to the Kitchen-Rosenfeld corner detector. We will show in this section that Zuniga-Haralick and Kitchen-Rosenfeld methods are essentially equivalent. Only difference between two expressions for cornerness K, given by Zuniga and Haralick and Kithcen and Rosenfeld, in (4) and (5) respectively, is the factor (gf2 + y2)0.6 which is the gradient magnitude. The gradient magnitude can be considered as the measure of the edginess. By multiplying the rate of change of gradient direction with the gradient magnitude Kitchen and Rosenfeld introduce the and operation between cornerness and edginess. In Zuniga-Haralick corner detector the edginess condition is expilict i.e.the point is declared as a corner if: 1. cornerness is above some threshold and 2. it is an edge point. 6

In other words, Zuniga and Haralick first detect the edges then they compute the cornerness at each point and apply the above two conditions to detect the corners. Important point to note here is that due to condition 2 Zuniga-Haralick corner detector eliminates all false corners in the background which might appear due to noise. But the other two corner detectors might not be able to eliminate those false corners. Kitchen and Rosenfeld discuss that the gradient magnitude gave them problem when the edge near the corner is blurred. In such a situation, The corner detector responds all the way across the edge. They solve this problem by using the heuristics of nonmaximum suppression to edge magnitudes. Since Haralick and Waston's zero crossing edge detector based on their facet model gives significantly better results than the gradient edge operator, Zuniga-Haralick corner detector does not have problems with the blurring. Thus we can conclude that as far as the cornerness measure is concerned KitchenRosenfeld and Zuniga-Haralick corner detectors are same in principle, they differ only with respect to the edginess measure and steps in implementation. Zuniga and Haralick get significantly better results due to the high quality of edges obtained by using the facet model and the fact that first edges are determined and then the cornerness is computed only at edge points. 3. Time Varying Corners The time varying corner detector is based on the and operation between the cornerness and the temporal derivative as given below. Ct= C* V where Ct is the time varying cornerness,C, is static cornerness and V is a measure of the temporal variations at the point. Consider two frames fl and f2 of a sequence. There are some objects which are displaced in the frame f2 with respect to fl. The aim is to detect the corners of the objects that have been displaced. We apply the Zuniga and Haralick corner detector to fl which gives C,, the cornerness at each pixel. The time varying operator V finds the regions in fl which have changed in the 7

gray level characteristics. For time varying operator V there are two approaches: Temporal derivative and Likelihood Ratio which we will discuss below. After applying some threshold to the product Ct the time varying corners can be detected. 3.1. Likelihood Ratio The likelihood ratio gives an idea about the change in the gray level distribution around some given neighborhood of a pixel location. This can be used to detect the changes, due to moving objects, in the gray levels between two frames. The likelihood ratio X is defined as follows: ((( 2 )+ (( 2 ))( 2 _ 2 (7) (Ol Va2) Where al,a2,l1,J2 are variance and mean in the frame 1, variance and mean of the corresponding pixels in the frame 2 respectively. Consider figure 2 where we have shown two frames fl and f2. The object is represented by the gray level 100 while background by 255. It is shown that object has moved in frame f2 with respect to fl. Now let us find X at corner point c and the point a next to it by considering 3 x 3 neighborhood as shown in the figure 3 (a) and (b). In the considered neighborhood of point c in frame fl, there are four pixels which have gray levels equal to 100 while remining five pixels have gray level equal to 255. In frame f2 all the pixels in the neighborhood coressponding to the location of c have value equal to 255. Now consider the 3 x 3 neighborhood around the point a close to point c in frame 1 and 2. It is easy to see that six pixels in fl have value 100 while remaining three have value 255. In f2 each pixel in the corresponding neighborhood is equal to 255. It is clear from the above that there is more change in the gray level distribution at point a than at the corner point c. Therefore the X for a will be greater than c. Since Cs for points c and a do not differ much, after multiplying with X it will be hard to distinguish between points c and a. 8

Therefore if likelihood ratio is used then it will be hard to eliminate the false corner point. This implies that the likelihood ratio is not suitable for the time varying corner detection; it will give blurred corners. 3.2. Temporal Derivative The derivative in the discrete domain can be approximated by the difference operation. Consider two frames fl and f2 as we considered in the previous section.Temporal derivative is approximated by taking the difference between the gray level of a pixel in fl and the corresponding gray level of pixel in f2. The picture thus obtained is called the difference picture. As it is easy to see that the entries in the difference picture will be significant only at the pixel location where the object has moved. Moreover this difference is same for each object pixel. It should be mentioned here that better results may be obtained by computing the temporal derivative from more than two frames. In this paper, we report our experiments with only two frames of a sequence, however. Note the difference between the temporal derivative and the likelihood ratio. In the difference picture each pixel contribute to it self only. While in the likelihood ratio many neighborhood pixels also contribute. Due to this fact there is always competition between the corner points and the points close to them in the likelihood ratio approach. But this problem is not encountered in the temporal derivative approach. 4. Results In order to study the efficacy of the proposed corner detector, we applied it to several synthetic and laboratory generated scenes. The synthetic scenes had object and background with random texture and significant amount of noise added. We report here results for one of the more difficult scenes. Our experiments with less noisy scenes showed very good determination of moving corner points. The results of time varying corner detector are shown in figures 3-5. In figure 3 the pictures considered are made of the random background and the random object. We added 30% random 9

noise to both the background and the object. The background gray level is a random number between 0 to 255 and the object gray level is between 0 to 80. Due to the added noise and non uniform object and the background the time varying corners detected by our operator are expanded to +-1 pixels around their actual locations. As is clear from the Figure 3, even in case of such extreme noise, good time-varying corners were detected by this approach. In another experiment with a synthetic scene, both the background and the moving square were drawn from the same range of random numbers. The random background and the random object reminds us of the famous Bradick's Illusion. In our experiments we have verified this illusion by simulating the random object and the background in two frames with object displaced in the second frame (see figure 4). From one display it is impossible to tell where the object is. But the location of the object becomes obvious when the two frames are displayed successively. Our corner detector gives time-varying corners in this case as shown in Figure 4. Note that several corners are detected within the square also. These are the points of the background that are gray value corners and their intensity has changed due to the displacement of the random object. These points are correct time-varying, though not moving, corner points. The results of the time varying corner detector for laboratory generated scenes are shown in fig 5. In this scene we placed 3 blocks on a table top, two blocks were stationary. Though the blocks were of uniform reflectance material, due to illumination, the intensity variations for each block were significant. Several corners are detected on the moving object, only one false timevarying corner was detected. There are several time-varying corners on the moving object due to abrupt intensity variations at those points; these points are indeed the static corners whose intensity has changed. 5. Conclusion In this paper, we proposed a time varying corner detector which gives good results even in the random noise and the random object environment with significant noise. We have shown that though the corner detectors by Zuniga and Haralick, Dreschler and Nagel, and Kitchen and Rosenfeld are equivalent in principle, the Zuniga and Haralick corner detector gives better results 10

due to a powerful edginess measure. We believe that the correspondence problem in structure from motion will be significantly simplified using this corner detector. It appears that the time-varying corners may also be useful in Nagel's approach for the computation of optical flow. Though we have not yet integrated our corner detector in a system for recovering structure from motion, we intend to do experiments to see the effectiveness of time-varying corners in real world dynamic scene analysis. 6. References [Bea78] Baudet,P.R." Rotational invariant image operators" International Joint Conference on Pattern Recognition,pp [DrN811 Dreschler, L. and Nagel, "Volumetric model and 3-D trajectory of a moving car derived from monocular TV-frame sequence of a street scene," Proceedings of IJCAI a981, pp.692-697. [Gib791 Gibson,J.J. Ecological Approach to Visual Perception Hougton Mifflen, Boston,1979. [HaJ831 S.M.Haynes and Ramesh Jain Computer Vision,Graphics,and Image Processing 1983 vol 21,pp 345-367. [HW811 Haralick R.M.,Waston L., "A facet model for image data " Computer Graphics and Image processing vol 15, 1981,pp. 113-129. [JeJ831 Jerian, C.P. and R.Jain, "Determining motion parameters for scenes with translation and rotation ", Proc. Workshop on Motion: Representation and Control, April 4-6, Toronto,1983. [KiRo82] Les Kitchen and A.Rosenfeld "Gray-Level Corner Detection", Pattern RecognitionLetters I (1982) 95-102. Pattern Recognition Letters vol I pp. 95-102. [Nag831 Hans H.Nagel "Displacement vectors from Second order variations", Computer Vision,graphics 11

and Image processing vol 21,pp. 85-117. [RoA801 Roach,J.W. and J.K.Aggrawal, Determining the movement of objects from a sequence of images " IEEE Trans.on PAMI,vol. PAMI-2,No.6,Nov. 1980, pp 554-562. [RuR78] Rutkowsko, W.S., Rosenfeld,A., "A comparaision of Corner Detectection Techniques for Chain -coded curves " Technical Report 623, [TsH811 Tsai, R. Y. and T.S. Huang, "Estimating three-dimensional motion parameters of a rigid planar patch " Proc of PRIP, pp. 94-97, 1981. [U11791 Ullman.S., The Interpretation of visual motion Cammbridge,Mass,MIT Press, 1979. [ZuH831 O.A.Zuniga,Robert Haralick "Corner Detection Using Facet Model", CHI891 -1/83 IEEE. 12

c I 1 Fig 1: Aperture Problem Local information at point A is not sufficient to give the displacement information. At B the local information is sufficient to give the displacement of the object.

255 255 255 255 25 255 2255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 1005 C 100 100 100 255 255 255 255 255 255 255 255 100 100 100 100 255 255 255 255 255 255 255 255 100 100 100 100 255 255 255 255 255 255 255 255 100 100 100 100 255 255 255 255 255 255 255 255 100 100 100 100 255 255 255 255 255 255 255 5 2551 1 1 255 255 255 255 25 2255 255 255 255 255 255 255 255255 2 55 2 55 25 5 2 55 25 5 2 255 255 2 55 2 55 255 255 255 255 255 255 255 255 255 255 25 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 2255 25 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 Figure 2(a): Frame fl 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255[ 255' 255 255 100 100 100 100 255 255 255 255 255 255 255 255 100 100 100 100 255 255 255 255 255 255 255 255 100 100 100 100 255 255 255 25 255 255 255 255 100 100 100 100 255 255 255 255 255 255 255 255 100 100 100 100 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 25 55 252 55 255 255 255 255 255 255 255 2 2552 255 255 255 255 255 255 255 255 255 25 5 25 5 255 25 255 2 2 55 2 55 25 2 Figure 2 (b): Frame f2 The 3*3 neighborhood around the actual corner c in frame fl contains 4 pixels having value 100 while around point a there are 8 pixels having value equal to 100. Therefore the change,in graylevel distribution, at point a in frame f2, with respect to frame fl, Is more than the change at point c..........r ():Frmef The 3 as nehoroo ars un tss acsua 2 o$. c~ infam 1cotis 4~, pLssl havs valu 100s whil aroun poss as ther are 6 px s havin ~ssu ~ss t 0. hr ~oetecanei rylae ltrb....a on i rm 2,wt epett rm n, s more than thes chang at s~ poin c.'~s s, s

B - - -m L1 I I I Lf U I I t~ m - l1 * I 1 I _* I Im a _. a a -.u_.m- -J 8 aC 4 v r.. 4 I. r!|~~~~~~~~ -L:.-. - L -. - -;lm-; - iI l 1 1. 1 i Ai * Figure 3 LEFT: Frame f,background is a random number betwveen 0 to 255 and object is between 0 to 80. The uniform noise equal to 30 % is added to the background and the object. MIDDLE: Frame f2,the object moves 20 * 20 pixels RIGHT: The time varying corners superimposed on the edge image.

)parqo aqj pue punojS9piq aqi ua^Mlaq lsinSupsrp ol alqce si Joojado aq Ing par fqo axis apis uT sjauJozo as{Gj aonos arj aiaq)' ioqejiado aqj Xq papajap siauJoo Bu!XJsa aml aqU j:~LHOIH siax!d ~,g saAOULU arqo aqjL:aaGaIvi'SSg o 0 uaoaq jaqtunu umopuuJ x! si poafqo eqt puc punoOJxp3)ql' Ij auiwja a 3jnM.J. r: r,,; 3 - r 4 ^ e J, r- i U- T\ *' W ^ it! r * *,: t -n " * _: U i r *.*^ -**'*' r E.. "..- <'ft."!' <;, ~ E t * - f(, T',~ ~ *' t. i!. -" ".,.:. t,,_ I. -! r. t..' a ^ _ *~?' - * f " - * 1 ly t^t: vk 1C r >^-t? " r U U & i'* k ~.* r. _ I * \. -... ^-~ i, --.- i *. r _ ig r ct. ~~3, E *~~~ -..';' e ~ l. t,. * e! I &. I r-P _ i ir * _~ a- t -. * _ S w w * r - *r ^.' J W r. i ~ I'~~~~~~ ~;..', L — M f' t' - _ _. _ = ~ l -. j'iJ -' -:K t * I "..;. - ^ l ^ * *. i. * I m —- -

a2unl aSpa aq uo pasodtu!.wdns sEJUJOD Bu!iJcA aui, paAouw s!:afrqo alpp!lu aqg: A auiaj u^Aoqs aBe sagarqo aajq: U otuIJ, S an-mSnl, +r - c~~~~~~~~~~~, ~- - - - - - - - - - I~~~~~~~~~~~ F"- %~ MM~~~~~~~~~~:Bi7~ 1, t-,j i l- ~" hC= 0-s I -_

L. - A~~ Figure 3 LEFT: Frame fl,background is a random number between 0 to 255 and object is between 0 to 80. The uniform noise equal to 30 % is added to the background and the object. to 80. The unif~orm noise equal 4L,. I iU~3U-C c sc, MIDDLE: Frame f2,the object moves 20 * 20 pixels RIGHT: The time varying corners superimposed on the edge image. ~~~~~~~~..-;...-:t?!~.:.:...;..:.:::l:;.....*:.::;'!-.... t I..: *-;;l;-iiii;; i- s*,^Fli.:............................ i-j2-i''-'~~~~~~~~~~~~~~~~~.:-..............?:~;."..:!.:?~v r:.F..;.....::;~!!:-! t.................:z'.z.!- d;.s.2,:!7:.i: 1~ ~mhip-i~.-...-.~.-. ~...;:.,:a:-,.~.::,;.-.,-:~.':....-'.- -.-~ ~: Figure 4 Frame fl,background and the object'i a random number between 0 to 255. MIDDLE: ~it.} r.'~: }|:i: i:=~ _;_.. -............. _=. j-o-t 1; Xt-*' *' x' - *t igi........... 4:-t:. -*F,* 1?k;1j, L_;,.;:.;-:-..Fs. The object moves 3*3 pixels RIGHT: The time varying corners detected by the operator,there are some false corners in side the object. But the operator is able to distinguish between the background and the object.