Target tracking method and device therefor

[0002] This application makes reference to, incorporates the same herein, and claims all benefits accruing under 35 U.S.C. §119 from an application entitled TARGET TRACKING METHOD AND DEVICE THEREFOR earlier filed in the Korean Industrial Property Office on Jun. 11, 1997, and there duly assigned Serial No. 97-24206 by that Office.

[0003] 1. Technical Field

[0004] The present invention relates to target tracking, and more particularly, to a method for tracking a target in an image which employs a block matching algorithm and a device therefor.

[0005] 2. Related Arts

[0006] In general, in an automatic target tracking method which is used in radar signal processing, a motion of a target is automatically tracked, in order to make a decision based on the tracking data.

[0007] The automatic target tracking may look similar to an image compression method used in video equipment. However, only the motion of a predetermined target is relevant in the automatic target tracking while all objects in the image are relevant in the image compression method.

[0008] One conventional automatic target tracking method is a centroid tracking method using the center of gravity of a target. In the centroid tracking method, an image signal value of each pixel is compared with a predetermined threshold, and pixels are divided into target pixels and background pixels according to the comparison result to calculate the center of gravity of the pixel corresponding to the target. If B(h,v,m) indicates a binary image signal in which a value of the pixel corresponding to the target is one and a value of the pixel corresponding to the background is zero, the center of gravity of the target is expressed by: $\begin{array}{cc}{C}_h=\frac{\Sigma B\left(h,v,m\right)\times h}{\Sigma B\left(h,v,m\right)},C_v=\frac{\Sigma B\left(h,v,m\right)\times v}{\Sigma B\left(h,v,m\right)}& \left(1\right)\end{array}$

[0009] In such a centroid tracking method, it is difficult to accurately calculate the center of gravity of the target if the background pixels are determined to be target pixels or vice versa. However, it is difficult to divide pixels in the image signal into a target pixels and background pixels since the image signal generally includes noise and the background changes. Accordingly, when the centroid tracking method is applied, it is difficult to repeatedly and accurately track the target.

[0010] Another conventional automatic target tracking method is a correlation coefficient tracking method. Here, a displacement of a moving target pixel is calculated from the correlation of temporal/spatial intensity differences of each pixel between two consecutive frames.

[0011] That is, when I(h,v,m) indicates an intensity function value of the pixel (h,v) in m-th frame, horizontal/vertical and temporal gradients which indicate intensity differences in a pixel unit is expressed by: $\begin{array}{cc}\nabla H\left(h,v,m\right)=\frac{I\left(h+1,v,m-1\right)-I\left(h-1,v,m-1\right)}{2}\nabla V\left(h,v,m\right)=\frac{I\left(h,v+1,m-1\right)-I\left(h,v-1,m-1\right)}{2}\nabla K\left(h,v,m\right)=I\left(h,v,m\right)-I\left(h,v,m-1\right)& \left(2\right)\end{array}$

[0012] Displacements Dh and Dv of a moving target in horizontal and vertical directions, respectively, between a (k−1)th frame and a k-th frame, are expressed by equation (3) by use of correlation coefficients of the gradients. $\begin{array}{cc}{D}_h=\frac{S_{\mathrm{hv}}{S}_{\mathrm{tv}}-S_{\mathrm{vv}}{S}_{\mathrm{th}}}{S_{\mathrm{vv}}{S}_{\mathrm{hh}}-S_{\mathrm{hv}}^2},D_v=\frac{S_{\mathrm{hv}}{S}_{\mathrm{th}}-S_{\mathrm{hh}}{S}_{\mathrm{tv}}}{S_{\mathrm{vv}}{S}_{\mathrm{hh}}-S_{\mathrm{hv}}^2}\mathrm{where},S_{\mathrm{xy}}=\Sigma \nabla X\left(h,v,m\right)\nabla Y\left(h,v,m\right)& \left(3\right)\end{array}$

[0013] In the above correlation coefficient tracking method, the temporal gradient is expressed in terms of the spatial gradient by Taylor series expansion. However, the tracking performance is deteriorated with respect to a target moving at high speed in the case that higher-order terms are ignored in calculating the Taylor series expansion. For example, it is difficult to track a target when the speed of the target is 2 pixels or more per frame. Also, when the image includes a background, the tracking performance is deteriorated due to the gradient caused by the background.

[0014] Still another automatic target tracking method is a block matching algorithm. In this method, a template including a target is formed in a frame, and a subsequent frame is searched in order to determine where the information included in the template of the previous frame is located in the subsequent frame. For the purpose, candidate templates are sequentially formed in a predetermined searching area of the subsequent frame to calculate the similarity between each candidate template and the template of the previous frame. Then, the position difference between the candidate template showing the maximum similarity and the template of the previous frame is determined as the displacement of the target.

[0015] Some measures of the similarity are a normalized correlation coefficient, a mean of absolute difference (MAD), mean of squared differences (MSD), and a normalized invariate moment equation. For example, the mean of absolute difference between the templates is calculated by: $\begin{array}{cc}Q\left(d_m\right)=\frac{\Sigma \left|I\left(s,m\right)-I\left(s+d_m,m-1\right)\right|}{M}& \left(4\right)\end{array}$

[0016] where s denotes a two-dimensional position vector, d_mdenotes a two-dimensional expected displacement of a target, and M denotes the total number of pixels. Here, the expected displacement d_mwhich results in the minimum of the mean of absolute difference is determined as the displacement of the target.

[0017] The block matching algorithm shows a stable performance even when an image signal includes noise. However, in case that the image signal includes a complex background component, the performance is deteriorated since the contribution of the difference in intensity function values of the background increases. Furthermore, it is difficult to implement a real-time system since a great deal of computation is involved.

[0018] Devices and methods for detecting and tracking objects are disclosed by U.S. Pat. No. 5,631,697 issued to Nishimura et al. entitled Video Camera Capable Of Automatic Target Tracking; U.S. Pat. No. 3,955,046 issued to Ingham et al. entitled Improvements Relating To Automatic Target Following Apparatus; U.S. Pat. No. 5,574,498 issued to Sakamoto et al. entitled Target Tracking System; U.S. Pat. No. 5,583,947 issued to Florent entitled Device For The Detection Of Objects In A Sequence Of Images; U.S. Pat. No. 4,644,405 issued to Roy et al. entitled Method And Apparatus For Scanning A Window In The Image Zone Of A Charge Transfer Device Of The Frame Transfer Type; U.S. Pat. No. 5,706,362 issued to Yabe entitled Image Tracking Apparatus; U.S. Pat. No. 5,757,422 issued to Matsumura entitled Tracking Area Determination Apparatus And Object Tracking Apparatus Utilizing The Same; and U.S. Pat. No. 5,729,338 issued to Houlberg et al. entitled Computer Controlled Optical Tracking System.

[0019] Although several devices and methods currently exist for tracking targets, I have discovered that an enhanced target tracking method and device would be desirable, in order to increase efficiency.

[0020] To solve the above problems, an object of the present invention is to provide a method of tracking a target in an image by a block matching algorithm which shows enhanced noise performance and stable tracking performance and reduces computation time so that a real-time system may be implemented.

[0021] Another object of the present invention is to provide a device for tracking a target in an image for implementing the above tracking method.

[0022] In a method for tracking a target to achieve one of the above objects, a first rectangular gate substantially including a target to be tracked is formed in an image of a first frame and a second rectangular gate is formed in an image of a second frame temporally sequential to the first frame.

[0023] Then, pixels commonly included in moving regions in the first and second rectangular gates are discriminated and a block matching level between the first and second rectangular gates is calculated by using only pixels of the moving region.

[0024] Afterwards, the second rectangular gate is changed in a predetermined area, and the block matching level is calculated.

[0025] Subsequently, the block matching level values are compared to determine a second rectangular gate which results in a maximum block matching level value, and a positional difference between the first rectangular gate and the second rectangular gate resulting in the maximum block matching level value is determined as a movement vector of the target.

[0026] To achieve another one of the above objects, the target tracking device is provided.

[0027] In the target tracking device, a frame memory receives an input image signal of a first frame, buffers such signal for one frame period, and outputs an image signal of a second frame delayed by one frame period;

[0028] An image difference generator receives the image signals of the first and second frames, generates a first rectangular gate substantially including a target to be tracked in the image of the first frame, forms a second rectangular gate in the image signal of the second frame, and calculates image difference between the first and second rectangular gates;

[0029] A moving region generator generates first and second moving templates by excluding pixels included in a target area, a background area or a foreground area from the first and second rectangular gates, respectively, based on the image difference output by said image difference generator.

[0030] A block matching unit calculates block matching levels between the first moving template and a plurality of the second moving templates, determines one of the second moving templates which results in a maximum block matching level value, and determines the spacial displacement of the second rectangular gate which corresponds to the second moving template resulting in the maximum block matching level value from the first rectangular gate as the motion vector of the target.

[0031] The present invention is more specifically described in the following paragraphs by reference to the drawings attached only by way of example.

[0032] A more complete appreciation of the present invention, and many of the attendant advantages thereof, will become readily apparent as the same becomes better understood by reference to the following detailed description when considered in conjunction with the accompanying drawings in which like reference symbols indicate the same or similar components, wherein:

[0033] FIG. 1A shows an image signal of one horizontal line included in a gate of (m−1)-th frame;

[0034] FIG. 1B shows an image signal of one horizontal line included in a gate of m-th frame positionally corresponding to the horizontal line of FIG. 1A in the case that an actual displacement of the target is ‘d’ and the gate of m-th frame is fixed in the position of the gate of the (m−1)-th frame;

[0035] FIG. 1C shows an image signal of a horizontal line in a gate of m-th frame positionally corresponding to the horizontal line of FIG. 1A in the case that an expected displacement of the target is dm and the gate of m-th frame is moved by the expected displacement of the target, dm, from the position of the gate of the (m−1)-th frame;

[0036] FIG. 2 is a block diagram of an embodiment of a target tracking device, according to the principles of the present invention;

[0037] FIG. 3 is a circuit diagram of a filter in a moving region generator of FIG. 2, according to the principles of the present invention;

[0038] FIG. 4 is a flowchart illustrating an embodiment of a target tracking method, according to the principles of the present invention;

[0039] FIGS. 5A, 5B, and 5C illustrate the formation of first and second moving templates pertaining to a moving target, according to the principles of the present invention;

[0040] FIG. 5A illustrates a first image of a target at a first moment in time, according to the principles of the present invention;

[0041] FIG. 5B illustrates a second image of the target of FIG. 5A at a second moment in time, according to the principles of the present invention; and

[0042] FIG. 5C illustrates the first image of the target shown in FIG. 5A superimposed over the second image of the target shown in FIG. 5B, thereby forming first and second moving templates, according to the principles of the present invention.

[0043] In a preferred embodiment of the present invention, it is assumed that the intensity function I(s,m), which describes the intensity of pixels in an image, is expressed as described by equation 5 shown below by the weighted sum of three terms: O(s,m) indicating a region corresponding to a target, B(s,m) indicating a background region, and F(s,m) indicating a foreground region. Here, the background means a portion of the image which surrounds the target, and the foreground means a portion which screens some part of the target such as clutter.

[0044] I(s,m)=F(s)+[1−UF(s)]O(s,m)+[1−UF(s)][1−UO(s,m)]B(s)  (5)

[0045] In this equation, UF(s) and UO(s,m) are unit step functions which have the value of 1 when F(s) and O(s,m) have a non-zero intensity value and which have the value of 0 otherwise. Also, the variable s denotes two-dimensional spatial coordinates, i.e., a position vector, and the variable m denotes a frame index. Meanwhile, it is further assumed that the background and the foreground are at fixed positions regardless of the movement of the target, so that the frame index m is not used for the components.

[0046] In the equation 5, in the case that the position vector s is in the foreground area, the second and third terms become zero and only the first term may have a non-zero value. Also, in the case that the position vector s is in the target area, the first and third terms become zero and only the second term may have a non-zero value. Similarly, in the case that the position vector s indicates the background, the first and second terms become zero and only the third term may have a non-zero value.

[0047] Accordingly, such a representation makes it possible to express the intensity of each pixel of the image in terms of functions of the foreground, target and background area, and reflect the effect of each area on the target tracking when the target moves in the image.

[0048] If an object moves by d between (m−1)th and m-th frames, the intensity function of the target area in the m-th frame is expressed as follows.

[0049] O(s,m)=O(s+d,m−1)  (6)

[0050] If there is no foreground in the image, the equation 5 is expressed simply as follows:

[0051] I(s,m)=O(s,m)+[1−UO(s,m)]B(s)  (7)

[0052] Here, mean of the absolute differences (MAD) with respect to pixels in a gate is expressed by: $\begin{array}{cc}Q\left(d_m\right)=\frac{\Sigma \left|O\left(s+d,m-1\right)+\left[1-\mathrm{UO}\left(s+d,m-1\right)\right]B\left(s\right)-O\left(s+d_m,m-1\right)-\left[1-\mathrm{UO}\left(s+d_m,m-1\right)\right]B\left(s+d_m\right)\right|}{M}& \left(8\right)\end{array}$

[0053] Here, the intensity function I(s,m-1) of the (m−1)th frame is replaced with the intensity function I(s,m) of the m-th frame using the equation 6.

[0054] In the equation 8, when Q(d_m) becomes a minimum, the expected displacement dm becomes actual displacement. At this time, the equation 8 will be simplified into equation 9. $\begin{array}{cc}Q\left(d_m\right)=\frac{\Sigma \left|\left[1-\mathrm{UO}\left(s+d,m-1\right)\right]\left[B\left(s\right)-B\left(s+d\right)\right]\right|}{M}& \left(9\right)\end{array}$

[0055] Also, it is more preferable that the value becomes smaller, i.e., closer to zero.

[0056] It is noted in the equation 9 that the mean of absolute differences between I(s,m) and I(s,m−1) becomes the intensity difference of the background area in the case that the expected displacement d_mis equal to the actual displacement d. Thus, if the background area is complicated, the term of the background area difference and the resultant magnitude of the mean of absolute differences become larger even when the expected displacement d_mis equal to the actual displacement d, becomes larger, which deteriorates the tracking performance. Therefore, it is desirable that the background area is excluded from the calculation of the mean of the absolute differences in order to enhance the tracking performance.

[0057] Meanwhile, similar is the case when the expected displacement d_mdiffers from the actual displacement d, which will be described with reference to FIGS. 1A through 1C. In such a case, the full representation of the equation 8 should be used.

[0058] Turn now to FIG. 1A, which shows an image signal of one horizontal line included in a gate of (m−1)-th frame. In addition, refer to FIG. 1B, which shows an image signal of one horizontal line included in a gate of m-th frame positionally corresponding to the horizontal line of FIG. 1A in the case that an actual displacement of the target is ‘d’ and the gate of m-th frame is fixed in the position of the gate of the (m−1)-th frame. Also, refer to FIG. 1C, which shows an image signal of a horizontal line in a gate of m-th frame positionally corresponding to the horizontal line of FIG. 1A in the case that an expected displacement of the target is d_mand the gate of m-th frame is moved by the expected displacement of the target, d_m, from the position of the gate of the (m−1)-th frame.

[0059] As shown in FIG. 1B, when a gate is fixed on image signals between the m-th and (m−1)-th frames, only the target signal moves its relative position between the frames while background signals of the two frames are maintained to be same. Also, as shown in FIG. 1C, if the expected displacement of the target between image signals between the m-th and (m−1)-th frames is d_m, both the background signal and the target signal moves their position in the gate between the frames.

[0060] Accordingly, in considering the difference between the intensity function I(s,m−1) of a pixel in the (m−1)-th frame and the intensity function I(s,m) in the m-th frame, all the pixels in the image may be divided into three categories: an Rbb region which includes pixels belonging to the background area commonly in both frames, an Rtb region which includes pixels belonging to the target area in one frame but to the background area in another frame, and an Rtt region which includes pixels belonging to the target area commonly in both frames.

[0061] As described above, the operation result of the equation 8 becomes smaller as the expected displacement dm becomes closer to the actual displacement d.

[0062] However, for the Rbb region, complication of the background area has more critical effect than the exactness of the expected displacement d_mon the operation result of the equation 8. For the Rtt region, the calculated value is almost constant regardless of the expected displacement d_mif we assume that the intensity of a surface of the target is constant. Meanwhile, for the Rtb region, the calculated value changes rapidly depending on how much the expected displacement d_mis closer to the actual displacement d. Furthermore, in the Rtb region, the calculated value becomes rapidly reduced if the expected displacement d_mapproaches the actual displacement d. Accordingly, if only the Rtb region is considered in the calculation of the equation 8, the tracking performance may be enhanced.

[0063] In the present invention, only the Rtb region is used for the calculation in the application of the block matching algorithm. The Rtb region, which is generated by the movement of the target is referred to as a moving region, hereinafter.

[0064] Meanwhile, the tracking performance may be deteriorated due to foreground area, also. In case that the foreground area exists in the image, the equation 5 will be expressed as follows. $\begin{array}{cc}Q\left(d_m\right)=\frac{\Sigma \left|F\left(s\right)-F\left(s+d\right)+\left[\mathrm{UF}\left(s+d\right)-\mathrm{UF}\left(s\right)\right]O\left(s+d,m-1\right)+\left\{\left[1-\mathrm{UF}\left(s\right)\right]B\left(s\right)-\left[1-\mathrm{UF}\left(s+d\right)\right]B\left(s+d\right)\right\}\left[1-\mathrm{UO}\left(s+d,m-1\right)\right]\right|}{M}& \left(10\right)\end{array}$

[0065] Here, the intensity function I(s,m−1) of a pixel in the (m−1)-th frame is replaced with the intensity function I(s,m) of a pixel in the m-th frame by using the equation 6.

[0066] According to a conventional block matching method, the absolute difference between I(s,d) and I(s+d,m−1) may be larger due to effect of the foreground area even in the case that the expected displacement d_mis equal exactly to the actual displacement d. Accordingly, the tracking performance may be deteriorated due to foreground area. However, when only the moving region of the image frame is used for calculating the similarity between the frames, the deterioration of tracking performance due to the foreground area may be prevented since the foreground area is not included into the calculation.

[0067] Hereinafter, preferred embodiments of the present invention will be described with reference to the attached drawings.

[0068] Turn now to FIG. 2, which is a block diagram of a target tracking device, according to the principles of the present invention. Hereinafter, h and v denote horizontal and vertical coordinates, respectively.

[0069] The device of FIG. 2 includes a frame memory 10, an image difference generator 20, a moving region generator 30, and a block matching unit 40.

[0070] The frame memory 10 receives digital image signals which are sequentially input and carries out buffering of such signals in a frame unit to output image signals delayed by one frame. Therefore, while the digital image signal of the m-th frame is being input to the frame memory 10, the image signal of the (m−1)-th frame is output by the frame memory 10. The image difference generator 20 receives the image signals of the (m−1)th and the m-th frames. Afterwards, the image difference generator 20 generates a first rectangular gate which substantially surrounds a target to be tracked in an image of the (m−1)-th frame, and a second rectangular gate in an image of the m-th frame. In the present embodiment, in the case that the (m−1)-th frame is an initial frame of consecutive input images, a user may generate the first rectangular gate by designating the boundary of the gate region by use of an input unit (not shown) such that the target to be tracked is substantially included in the gate. A mouse or a track ball can be used for the input unit.

[0071] However, in an alternative of the present embodiment, which is another embodiment of the present invention, the first rectangular gate for the initial input image may be generated automatically based on a prediction algorithm by a computer program or information stored in a database. For example, in the field of tracking flight using radar, the first rectangular gate may be generated such that the gate covers a predetermined area including an airbase when an airplane on a flight plan appears in the neighborhood of the airbase.

[0072] In the case that the first rectangular gate is generated for the input image of the initial frame, the second rectangular gate may be generated at a same position as that of the first rectangular gate or sequentially generated within a search area of a predetermined range from the position of the first rectangular gate. For next frames, the second rectangular gate is sequentially generated within a search area of a predetermined range from the position shifted from the first rectangular gate by a motion vector of the target estimated in the predetermined stage.

[0073] The frame difference generator 20 generates a frame difference FD for each pixel. The frame difference is calculated by an absolute difference in pixel values between a current frame and a previous frame as follows.

[0074] FD(h, v)=|I(h, v,m)−I(h, v,m−1)|  (11)

[0075] Here, the horizontal and vertical coordinates h and v refer to coordinates in the rectangular gates rather than in the whole frames.

[0076] The frame difference FD may be used as an index for dividing pixels into an Rbb region, an Rtb region and an Rtt region if it is assumed that there is a large difference in intensity function values between the target area, and the background or the foreground area and the movement vector of the target between consecutive frames or the estimated movement vector calculated by the device is not large.

[0077] The moving region generator 30 removes pixels belonging to target area in both the m-th and (m−1)-th frames from the first and second rectangular gates based on the frame difference output by the frame difference generator 20. Also, the moving region generator 30 removes pixels belonging to the background area in both the frames or those belonging to the foreground area in both the frames from the first and second rectangular gates. As a result, pixels which are changed from the target area into the background area and vice versa and pixels which are changed from the target area into the foreground area and vice versa remain in the rectangular gates. The sets of such pixels are referred to as first and second moving templates in the present invention.

[0078] The removing operation is performed by determining whether the frame difference of each pixel is larger than a predetermined frame difference threshold FDth or not. That is, a frame difference index (FDI) for indicating that a pixel is included in the moving templates without removing from the rectangular gates is obtained as follows: $\begin{array}{cc}\begin{array}{cc}\mathrm{FDI}\left(h,v\right)=0,& \mathrm{if}\mathrm{FD}\left(h,v\right)>\mathrm{FDth}\\ 1,& \mathrm{otherwise}\end{array}& \left(12\right)\end{array}$

[0079] In the equation 12, the frame difference threshold FDth is determined to be an appropriate value between zero and the maximum value. A pixel is included in the first and second moving templates if the frame difference index FDI for the pixel is zero. On the other hand, a pixel is excluded from the first and second moving templates if the frame difference index FDI for the pixel is one.

[0080] Turn now to FIGS. 5A, 5B, and 5C, which illustrate the formation of first and second moving templates pertaining to a moving target, according to the principles of the present invention. More particularly, FIG. 5A illustrates a first image of a target at a first moment in time, according to the principles of the present invention, FIG. 5B illustrates a second image of the target of FIG. 5A at a second moment in time, according to the principles of the present invention, and FIG. 5C illustrates the first image of the target shown in FIG. 5A superimposed over the second image of the target shown in FIG. 5B, thereby forming first and second moving templates, according to the principles of the present invention.

[0081] In FIG. 5A, a first frame 200 of a first image of a target 204ais shown. A first rectangular gate 202 is depicted substantially surrounding the target 204a.The target 204ashown in FIG. 5A is depicted in a position corresponding with a first moment in time.

[0082] At a second moment in time, the target 204ahas moved to a new location. The new location of target 204ais depicted in FIG. 5B. In FIG. 5B, a second frame 206 of a second image of a target 204bis shown. A second rectangular gate 208 is depicted substantially surrounding the target 204b.The target 204bshown in FIG. 5B is depicted in a position corresponding with a second moment in time, after the first moment in time of FIG. 5A. Target 204aand target 204brepresent the same object in two different locations.

[0083] In FIG. 5C, the first rectangular gate 202 is superimposed over the second rectangular gate 208. Similarly, the images contained within the first and second rectangular gates are superimposed over one another. More particularly, target 204ais superimposed over target 204b.The first moving template 210 is partly shaded. The second moving template 212 is partly shaded. The shaded areas of the first moving template 210 and of the second moving template 212 represent the pixels in transition. In other words, the only pixels in transition, in accordance with the principles of the present invention, are the pixels in the shaded regions shown in FIG. 5C. The shaded regions can also be referred to as moving regions and can also be referred to as the Rtb regions.

[0084] Importantly, the shaded regions in FIG. 5C include two types of pixels. The first type of pixels are those which are in the image of target 204abut which are not in the image of target 204b.The second type of pixels includes pixels which are in the image of target 204bbut which are not in the image of target 204a.In this manner, the pixels in transition are identified, in accordance with the principles of the present invention.

[0085] Only a portion of the first and second rectangular gates which is changed from the target area to the foreground or the background area and vice versa is selected to generate moving templates as shown in FIG. 5C. In FIG. 5C, the hatched portion indicate the first and second moving templates in the first and second rectangular gates, respectively.

[0086] Meanwhile, in the present embodiment, the moving region generator 30 includes a filter for removing pixels which remains in the first and second moving templates due to impulse noise from the moving templates.

[0087] Turn now to FIG. 3, which shows a circuit diagram of a filter included in the moving region generator 30 in this preferred embodiment. An 8-input AND gate 31 receives frame difference indices of eight neighboring pixels around a current pixel to perform an AND operation. An OR gate 32 receives the frame difference index FDI(h,v) of the current pixel through one input terminal thereof and the output data of the AND gate 31 through the other input terminal, performs OR operation with respect to such signals, and outputs an operation result as a moving index MI(h,v,m).

[0088] Therefore, in the case that the frame difference index FDI(h,v) of the current pixel has a value of one so that the current pixel is excluded from the moving templates, the value of the moving index MI(h,v,m) also has a value of one to indicate that the current pixel must be excluded from the moving template. Also, in the case that the frame difference index FDI(h,v) has a value of zero so that the moving templates include the current pixel, the moving index MI(h,v,m) also has a value of zero when the AND gate 31 outputs a value of zero to indicate that the frame difference index of at least one of neighboring pixels is larger than the threshold.

[0089] However, even though the frame difference index FDI(h,v) has a value of zero so that the moving templates include the current pixel, the OR gate 31 outputs the moving index MI(h,v,m) of one when the AND gate 31 outputs a value of one to indicate that the frame difference indices of all the neighboring pixels are less than the threshold. Accordingly, the current pixel, which is regarded to include an impulse noise, is excluded from the moving templates.

[0090] In another embodiment of the present invention, the filter may be implemented by use of a look-up table instead of logic gates.

[0091] Meanwhile, the block matching unit 40 of FIG. 2 receives the frame difference indices of each pixel in the first and second moving templates, and calculates the block matching levels sequentially between the first moving template and a plurality of second moving templates. The block matching level is calculated by use of conventional evaluation functions such as normalized correlation coefficients, mean of absolute difference (MAD), mean of squared difference and a normalized invariate moment equation. Afterwards, the block matching unit 40 determines which of the plurality of second moving templates results in the maximum block matching level. Then, a spatial displacement of the second rectangular gate corresponding to such second moving template from the first rectangular gate is determined to be the motion vector of the target.

[0092] Meanwhile, in another embodiment of the present invention, the block matching unit 40 may input the moving index MI of each pixel together with image signals of first and second rectangular gates to calculate the block matching level by using intensity function values of the pixels having moving indices MI zero.

[0093] Turn now to FIG. 4, which is a flowchart showing an embodiment of a method for tracking a target, according to the principles of the present invention.

[0094] At step S100, a first rectangular gate substantially surrounding a target to be tracked is formed in an image of a first frame. At step S110, a second rectangular gate is set at a position positionally corresponding to the first rectangular gate in an image of a second frame which follows the first frame. At step S120, first and second moving templates, which consist of pixels which are included in the moving region in first and second rectangular gates, respectively, are generated. For the purpose, the image of the first rectangular gate is subtracted from the image of the second rectangular gate and an absolute value of the subtraction result is calculated to obtain a frame difference index (FDI) in a pixel unit. Afterwards, a pixel is regarded to be commonly included in a target area, a background area or a foreground area in the two rectangular gates and excluded from the rectangular gates if the frame difference index of the pixel is smaller than a predetermined threshold, but maintained in the rectangular gates if the frame difference index of the pixel is larger than the threshold. Also, the pixels including impulse noise are excluded from the first and second moving templates, which was described above.

[0095] At step S130, the block matching level between the first and second rectangular gates is calculated by using only pixels included in the first and second moving templates.

[0096] At step S140, it is determined whether the block matching level is calculated for all the second rectangular gates which can be formed in the search area. In other words, at step S140 it is determined whether the search is completed. If the search is not completed, the steps S150, S120 and S130 are repeatedly carried out.

[0097] At step S140, if it is determined that the search is not completed, then step S150 is is performed. At step S150, the position of the second rectangular gate is changed in a predetermined search area, and the steps S120 and S130 are repeated to form the first and second moving templates in the first and second rectangular gates and obtain the block matching level between the first and second rectangular gates.

[0098] At step S140, if it is determined that the search is completed, then step S160 is performed. At step S160, the second rectangular gate which results in the maximum block matching level is determined. At step S170, a positional difference between the second and first rectangular gates is determined to be the movement vector of the target.

[0099] Afterwards, the tracking process is continued by replacing the first frame with the second frame, and inputting a third frame as a new second frame. In this stage, a movement vector of the target is estimated based on the target movement vector obtained from the previous stage, and a second rectangular gate is formed around a position shifted from the position corresponding to the first rectangular gate by an estimated movement vector. Then, the steps S120 through S170 are performed.

[0100] The method and device for tracking a target according to the present invention can be implemented in real-time since the block matching algorithm is realized by using some portion of pixels in a gate image and the calculation burden is small, which may. Also, noise performance is enhanced and tracking performance is stabilized since an impulse noise is filtered to be removed. Meanwhile, additional calculation burden in not incurred in generating a moving template since a frame difference signal used for calculating the block matching level is used for the purpose.

[0101] While there have been illustrated and described what are considered to be preferred embodiments of the present invention, it will be understood by those skilled in the art that various changes and modifications may be made, and equivalents may be substituted for elements thereof without departing from the true scope of the present invention. In addition, many modifications may be made to adapt a particular situation to the teaching of the present invention without departing from the central scope thereof. Therefore, it is intended that the present invention not be limited to the particular embodiment disclosed as the best mode contemplated for carrying out the present invention, but that the present invention includes all embodiments falling within the scope of the appended claims.