Object Tracking Using Filtering and Optimized Sum of Absolute Difference

Object Tracking Using Filtering and Optimized Sum of Absolute Difference

Greeshma A

Dept of Computer Engineering College of Engineering, Chengannur Alappuzha, India

Renu George

Assistant Professor, Dept of Computer Engineering College of Engineering, Chengannur

Alappuzha, India

Abstract The moving object tracking has attracted a great deal of interest in computer vision. Object tracking is an indispensable first step for navigation systems and surveillance systems. We present an object tracking algorithm that includes image preprocessing, moving object detection, target selection and target matching, four-step processing. The image preprocessing is used for noise removal. Then from the time- series images moving objects are identified. The reference target is selected from the first frame as a user defined area. In the target matching procedure the optimized sum of absolute difference between template and each region identified as moving object in the input frame is computed and select minimum valued region as matched. In this work a simple object tracking method for fast moving object is proposed.

KeywordsSum of Absolute Difference; template;

1. INTRODUCTION

   Object tracking is an important task within the field of computer vision. Object tracking can be defined as the problem of estimating the trajectory of an object in the sequence of frames. Generally every object tracking methods uses three key steps: detection of moving object, tracking of such object from frame to frame, and analysis of object track to recognize their behavior. There exist many techniques for tracking objects, color based tracking with kernel density estimation has high popularity due to its robustness to appearance changes[2]. Tracking based on the use of global appearance model e.g. in terms of colors have also been proposed.

   Another approach to track a region by use of optical flow method because of its accuracy [11]. The mean shift algorithm was proposed by Fukunaga and Hostetler for clustering data. This theory became popular among vision community after its successful application to image segmentation and tracking by Comaniciu and Meer [3]. For various applications many variants of the mean-shift algorithm were proposed. It is widely used because of its accuracy with relatively small object displacement, but its performance is not guarantied when the object move fast. The correlation based object tracking is widely used due to its simplicity[4]. This method fails with illumination changes.

   In the remote sensing context object tracking has tremendous applications like vehicle navigation, ship tracking etc. To demonstrate vehicle tracking using low-rate video or visible imagery sequences collected by sensors on aircraft, various algorithms have been developed[5,6]. In remote sensing platforms to track vehicles airborne spectral imagery

   [7] as well as spectral combined with polarimetric imaging [8] have also been used. Algorithms have been developed to track ships in the ocean[9] other satellite imagery data sources. Object tracking based on regional feature matching operator using high resolution satellite imagery have been developed [10].

   In this work, we propose an object tracking algorithm for use with satellite imagery. Fast moving object can be tracked accurately. The proposed algorithm is simple and accurate with illumination changes.

2. OBJECT TRACKING PROBLEM FORMULATION

   The proposed object tracking algorithm is illustrated in Fig. 1 . The algorithm consists of four steps, which are image pre-processing, moving object detection, target selection and target matching. Image pre-processing is used for noise removal in each input frame. Then moving objects are identified based on time-series images. The target template is selected from the first frame as user specified region. Finally the optimized sum of absolute difference is computed between user defined template and each region in the frame that is identified as moving object. The minimum valued region is selected as matched region. The algorithm is introduced below in detail.

   Input frames

   Pre-processing

   Object Detection

   Object Tracking

   Movement Trajectory

   Fig. 1. Steps for tracking

   A. Image Preprocessing

   The preprocessing of image sequences is necessary for noise removal. The median filter is applied for this purpose. The moving object detection is performed from this pre- processed input frames.

   Step 3: Calculate the frame difference pixel by pixel with other frames.

   Step 4: If the difference is greater than a specified value increment ADI (x) = ADI(x) + 1 else go to step 5

   Step 5: Set ADI(x) = ADI(x)

   Step 6: Apply another threshold , that is a count < N to ADI Step 7: Resulted ADI image is the Binary Mask image that highlight the moving object

   Step 8: Increment i = i+1 and repeat 2-7 until i<= N

   In this work by using each frame as reference image the moving object detection is performed on all the frames iteratively.

   C. Target Selection

   The target is defined as the interested object to be tracked. The reference target can be represented by user- defined region R (window ) in the first frame f(x,1). Then the target model is represented by its spatial feature. The spatial feature is defined as the geometric area of the target region that is selected by the user[10]. The pixel count is computed as follows

   Fig. 2. Proposed object tracking system.

   B. Moving Object Detection

   For moving object detection frame differencing method is used. Consider a sequence of image frames taken at time

   1, 2 and represented as f(x, 1)..f(x, ). Let the first image frame f(x, 1) be the reference image. An Accumulative Difference Image(ADI) is obtained by comparing the reference image with every subsequent image frames. If the difference is greater than some threshold value the ADI count is incremented. The ADI can be calculated as [1]

   (x) = 1 + 1 , , >

   1 ,

   Where R(x) is the reference image on which we want to find the moving object and T is the threshold, which is approximately 15% – 20% of the maximum image difference between the jth image and reference image. In the reference image any pixel with large ADI value is highly likely to be a moving object. Finally a threshold is applied to the ADI to remove the background pixels and the resultant image is the Binary Mask Image(BMI). The BMI highlight the moving object, so only that region is need to be compared in the template matching step. The object detection algorithm is described as follows

   Input: N frames

   Output: Binary Mask Images

   Step 1: Initialize i = 1, ADI = 0

   Step 2: Set ith frame as reference frame

   = ((, 1))

   Where pixc is the pixel count function and is defined as

   1, < 0

   = 0, = 0

   1, > 0

   1. Target Matching

      The target matching is the most important step in object tracking. Target matching performs a pixel intensity comparison between a predefined template image and sub region of the image. In this work template matching can be performed using optimized sum of absolute difference (OSAD) similarity measure between the template and the candidate of interest.

      After template selection then target candidate windows are selected for comparison. The target candidate windows are those centered on potential moving objects identified in the Binary Mask Image(BMI) and are also represented using spatial feture. It requires small number of comparison because only highlighted region in the Binary Mask Image is selected as candidate window. Then the OSAD algorithm will be used to show which image window will be either equal to zero or near to zero. Then the location of this window will be determined and extracted from the image to give the object location.

      To understand the methodology of that we need to define the meaning of the difference in the different spaces, and then explain OSAD algorithm. Moreover, we need to explain the optimum image window in order to minimize the error rate and be able to increase the accuracy of image window determination. To explain the meaning of the

      difference, a number of mathematical definitions based on the space of the representation can be given as follows

      • In one dimension the difference between two points can be formulated as

        d(A,B) = | x1 x2 |

      • In two dimension the difference between two points can be formulated as

        d(A,B) = (1 2)2 +(1 2)2

      • The difference between two functions f(x) and g(x) can be formulated as

        d(A,B) = |f(x) g(x)| dx

      • The difference between two matrices A and B and it can be formulated as

   d(A,B) = A B

   The SAD algorithm is widely used because its simple and easy to implement in order to find the similarity between two image windows. The idea is that calculating the difference between each point in the image window that is identified as moving object region in binary masked image and the corresponding point in the template window will be used for comparison. Then, these differences will be added together to measure the similarity between two images. There are many applications for SAD such as motion estimation, object recognition and video compression. This is illustrated with the following example:

   In the example the value of SAD is 5+1+3+2+0+5+1+1+8=26. If two image windows have almost same SAD, this method is not accurate. So to improve this algorithm we need to normalize the above equation to find the optimum image window that contained the template. The following equation gives Optimized SAD (OSAD):

   d(A,B) = , ,

   , , ,

   In the proposed work after selecting candidate window, the spatial feature is extracted. The object region has almost same pixel count as that of the template area. In case of large difference we discard that region from OSAD calculation. Otherwise OSAD is computed and select minimum valued region as matched.

   Thus the algorithm for object tracking is given as follows: Input: Binary images, Input frames, Target model, Nt Output: Object movement trajectory

   1. The target candidate windows are those centered on potential moving objects identified in the binary images. N = number of candidate window.

   2. Set i = 1st candidate window.

   3. Calculate Spatial feature of ith candidate window Nc.

   4. If Nc is almost similar to Nt go to step 5 else go to step 6.

   5. Calculate Optimized Sum of Absolute Difference between target model and candidate window and save the result.

   6. Increment i = i+1 go to step 3

   7. Select the minimum valued candidate window as matched region.

   8. Plot the location of the object in the corresponding input frame.

      Fig Two matrixes A and B

      Fig Difference between matrix A and matrix B

      In the resultant matrix there are some negative values. So we will take the absolute value of all matrix elements and then sum up these elements. This gives the SAD value between template window and candidate window. The equation for SAD is

      d(A,B) = | , (, )|

3. RESULTS

   To validate the object tracking algorithm, a set of satellite images provided by NASA 2012 Venus transit data has been used. The image subsets are collected at different times.

   1. (b)

   (c) (d)

   Fig. 3. Subset of five frames collected by NASA at different times: (a) 13:09:23, (b) 13:09:24, (c) 13:09:25, and (d) 13:09:26.

   1. (b)

      Fig.4. Intermediate results of target matching. (a) RGB image after pre- processing. (b) Binary Mask Image that highlight the moving object

      To better explain the methodology of object tracking some intermediate results of target matching in the first frame are presented in Fig. 4. The noise removed first frame is shown in Fig. 4(a). The Fig. 4(b) shows binary masked image that highlight the moving object. The performance of the proposed algorithm is analyzed on a per pixel basis by the accuracy. The accuracy can be calculated as

      Accuracy = Number of frames with correctly detected object

      Total number of frames

      The gray image of the first frame is shown in Fig. 5(a). Our task was to track the object shown within the white outline. The estimated trajectory of the object movement based on the proposed object tracking algorithm is shown in Fig. 5(b).

      1. (b)

   Fig. 5. Object tracking. (a) Gray image, where the object is within white outline. (b) Object movement trajectory.

   In this work comparison between Normalized Cross Correlation(NCC) and OSAD method is shown in table 3. Here 25 plane images are tested. In case of NCC, there is a significant increase in the error rate and that is due to the shade input image. The pixels values of the shade parts are smaller than the parts of the image and this case has a high percentage of NCC between the template image and input image which will determine a wrong location. The NCC fails if both object and background is lighter/darker and illumination changes in images. As compared to cross- correlation proposed method has high accuracy in both of the cases.

   TABLE I. COMPARISON BETWEEN NCC AND OSAD

   Number of frames	Using NCC	Proposed method
   25	80	96

   In this work small number of template matching is required because moving object region is identified in the binary masked images so that small number of region is need to be compared.

4. CONCLUSION

We have presented an object tracking algorithm using satellite imagery. The object tracking algorithm that includes image preprocessing, moving object detection, target selection and target matching, four-step processing. The image preprocessing is used for noise removal. Then from the time-series images moving objects are identified. The reference target is selected from the first frame as a user defined area. In the target matching procedure the optimized sum of absolute difference between template and each region identified as moving object in each frame is computed and select minimum valued region as matched.

This algorithm is simple and easy to implement. The applications in other research areas include object velocity estimation, and track control. As compared to normalized cross correlation, Optimized Sum of Absolute Difference method is simple and accurate with variation in illumination and clutter background. In future there may possible improvements that will broaden the scope of this work. Future work will focus on video tracking that have many applications.

REFERENCES

1. R.C. Gonzalez and R. E. Woods, Digital Image Processing, 3rd ed. Upper Saddle River, NJ: Prentice-Hall, 2006.

2. D. Comaniciu, V. Ramesh, P. Meer, Real-time tracking of non-rigid objects using mean shift, in: Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, Hilton Head, SC, 2000.

3. D. Comaniciu and P.Meer, Mean shift: A robust approach toward feature space analysis, IEEE Trans.Pattern Anal.Machine Intell, vol. 24,no.5,no. 10,pp. 603-619, 2002.

4. N. Prabhakar, V. Vaithiyanathan, Akshaya Prakash Sharma and Anurag Sing, Object Tracking Using Frame Differencing an Template matching , in: Proceedings of ISSN Journal of Applied Sciences, Maxwell Scientific Organization, 2012.

5. I. Szottka and M. Butenuth, Tracking multiple vehicles in airborne image sequences of complex urban environments, in Proc. 2011 Joint Urban Remote Sensing Event (JURSE), Apr, 2011, pp. 13-16.

6. J. Xiao, H. Cheng, H. Sawhney, and F. Han, Vehicle detection and tracking in wide field of-view aerial video, in proc. 2010 IEEE conf. Computer Vision and Pattern Recognition (CVPR), Jun. 2010, pp. 679-684.

7. J. Kerekes, M. Muldowney, K. Strackerhan, L.Smith, and B. Leahy, Vehicle tracking with multi-temporal hyperspectral imagery, in Proc. SPIE, 2006, vol. 6233, p. 62330C.

8. M. Presnar, A. Raisanen, D. Pogorzala, J. Kerekes, and A. Rice, Dynamic scene generation, multimodal sensor design, and target tracking demonstration for hyperspectral polarimetric performance- driven sensing, in Proc. SPIE, 2010, vol. 7672, p. 76720T.

9. A. Liu, C. Peng, and S. Chang, Wavelet analysis of satellite images for coastal watch, IEEE J. Ocean. Eng, vol. 22,no. 1, pp. 9-17,jan. 1997.

10. Lingfei meng and John P. Kerekes, Object Tracking Using High Resolution Satellite Imagery, in: Proceeding IEEE journel of selected topics in applied earth observations and remote sensing, vol. 5, No 1,2012.

11. J. Barron, D. Fleet, and S.Beauchemin, Performance of optical flow techniques, in: Proceeding International Journal of Computer Vision, pp. 43-77, 1994.