Real-time Object Image Tracking Based on Block-Matching Algorithm Hsiang-Kuo Tang( [email protected] ), Tai-Hsuan Wu ( [email protected] ), Ying-Tien Lin ( [email protected] ) I. Introduction Among various research topics of image processing, how to efficiently track moving targets in the observation scope has become an important issue. Recently, there are a lot of commercial applications embedded with simple or complicated motion tracking techniques, such as Robotic Vision, Electrical Pet, Traffic Monitoring, etc. In these applications, the objective of tracking functions is to achieve better resolution with data transmissions and computations as low as possible. As a result, different video coding techniques effectively utilized to compute continuous images under limited resources have been developed. For example, in H.264 video coding standard the tree-structured block partition is used to estimate various motion vectors and to track moving tendencies of objects. The critical factor for current video coding techniques is to look for the temporal redundancy between successive video frames. To exploit this temporal redundancy, the Block-Matching Algorithm (BMA) is proposed for correcting the error of tracking. From the implementation perspectives, two critical questions that affect the performance of tracking techniques are computation-intensive and full scale image processing. In this project, we would discuss all the issues mentioned above. Finally, the motion tracking algorithm has been applied in PLX architecture and a T1-DSP-like chip (ET44M210) so that the parallel processing optimization and real-time performance can be tested and verified, and then the feasibility of this object-tracking method on commercial DSP processors can also be examined.II. Object-Tracking Algorithm In this section, the tracking algorithm used in this project is introduced. Traditionally, the different motion analysis (DMA) method is applied to track the moving object because of simplicity. When we start to perform this algorithm, a background frame without any moving object is captured. Later when a moving object enters the observation scope, the second picture is recorded. By subtracting the second picture from the first picture (background), the difference between two images is obtained and the position of moving object can be obtained. By computing the summation of absolute difference (SAD) between adjacent frames and setting a threshold value for filtering out smaller variations, the moving object can be tracked more accurately. The procedures of DMA method are provided in Figure 1. Figure 1. Procedures for the different motion analysis method (a) Background (b) Moving object into the image (c) After subtracting, the moving object is obtained.However, when the moving object exists in both adjacent frames, the tracking area of moving object would be overestimated (as shown in Figure.2). In order to overcome this disadvantage of DMA method, the Block-Matching Algorithm (BMA), in which motion estimation is utilized to adjust the size of tracking area, is used. Figure 2. The disadvantage of different motion analysis method The basic idea of BMA (see Fig. 3) is to divide the current frame in video sequence into equal-sized small blocks. For each block, we try to find the corresponding block from the search area of previous frame, which “matches” most closely to the current block. Therefore, this “best-matching” block from the previous is chosen as the motion source of the current block. The relative position of these two blocks gives the so-called motion vector (MV), which needs to be computed and transmitted. When all motion vectors of the blocks in tracking area have been found, the motion vector happened (a) Background (b) Next image (c) After subtracting, the tracking area is larger than the moving object sizemost frequently is chosen for the correction of tracking area size. Figure 3. BMA is used to correct the size of tracking area Typically, the sum of absolute difference (SAD) is selected to measure how closely two blocks match with each other, because the SAD doesn’t require multiplications; in other words, less computation time and resources are needed. For the current frame, we denote the intensity of the pixel with coordinate (I,j) by I(i,j) . For a block of N with coordinate (i,j) , we represent it as (, )nIij. We refer a block of NN× pixels by the coordinate (k,l) of its upper left corner. Then, the SAD between the block (k,l) of the current frame n, and the block (k+x,l+y) of the previous frame n-1 can be written as: ()( )11(,) 100,,NNkl n nijSAD I k i l j I k x i l y j−−−===++−++++∑∑ The motion vector u(k,l) of the block (k,l) is then given as: (,) (,)(,) arg min (,)xy klukl SAD xy= (a) Background (b) Next image (c)The tracking area size can be corrected by the motion vectorThere are several methods used to find out the best matching block. The basic one is the full-search (FS) method. Assume that the frame size is 320×240 pixels, and each block is 16×16 pixels, there are 20×15 = 300 blocks for each frame. Therefore, total computational amount for the min MAD with ± 16 search area will be 17×17×300=86700 subtractions, 17× 17× 299=86411 additions, and 17×17=289 comparisons. These operations, however, cost a very large computation complexity and transmission capacity. Hence, many economical searching algorithms have been developed. Among them the three-step-search (TSS) is very popular due to its speed, regularity in the search pattern, and the ease in hardware implementation. The TSS algorithm employs a halfway stop technique to reduce the number of checking points (CPs), thus decreasing the computational complexity. It is worth noting that such algorithm is useful only for a small motion sequence. It is thus very likely to make the search trapped at some certain local minimum value. As a result, in order to compromise the mean square error (MSE) and computational complexity (speed), the 41SW/BPD algorithm developed by A. C.K.Ng and B. Zeng is applied with some modifications in our project. This algorithm employs two techniques, namely, (1) 4-to-1 search window sub-sampling (41SWS) and (2) object boundary pixel decimation (BPD). In the first part of algorithm, a FS-like search pattern that covers more globally the whole search window is shown in Figure 4. This part can be regarded as a two-step process: 1.
View Full Document
Unlocking...