INTRODUCTION
|
| The growth of computer memory and processor speed has caused the expansion of automated systems for everyday life applications. Computer vision systems is one example of such intensive computations systems, whose use becomes more feasible with the advances in computing power. The area of computer vision aims at processing visual information, which in general, is characterized by large size and complex structure. Another reason that hinders the development of computer vision is the lack of complete understanding of the way human beings process visual information. Motion detection was initially developed for video encoding. Motion vectors can be used to predict changes in the scene between two or more video frames. The size of video data is reduced by encoding only the current frame and the motion vectors,. Block Matching Algorithm (BMA) is used here and it is a way of locating matching blocks in a sequence of digital video frames for the purposes of estimation. The purpose of a block matching algorithm is to find a matching block from a frame . The goal of our experiments is two-fold: (1) to explore the abilities of the block matching algorithm on low resolution and low frame rate video and (2) to improve the motion detection performance by the use of different search techniques during the process of block matching |
SUM OF ABSOLUTE DIFFERENCE
|
| Sum of absolute differences (SAD) is a widely used, extremely simple algorithm for measuring the similarity between image blocks. |
| It works by taking the absolute difference between each pixel in the original block and the corresponding pixel in the block being used for comparison. These differences are summed to create a simple metric of block similarity This example uses the sum of absolute differences to identify which part of a search image is most similar to a template image. In this example, the template image is 3 by 3 pixels in size, while the search image is 3 by 5 pixels in size. Each pixel is represented by a single integer from 0 to 9. |
| Template Search image 2 5 5 2 7 5 8 6 4 0 7 1 7 4 2 7 7 5 9 8 4 6 8 5 |
| There are exactly three unique locations within the search image where the template may fit: the left side of the image, the center of the image, and the right side of the image. To calculate the SAD values, the absolute value of the difference between each corresponding pair of pixels is used: the difference between 2 and 2 is 0, 4 and 1 is 3, 7 and 8 is 1, and so forth. |
| Calculating the SAD values for each of these locations gives the following blocks gives the so-called motion vector (MV), which needs to be computed and transmitted. |
| For each of these three image patches, the absolute differences are added together, giving a SAD value of 20, 25, and 17, respectively. From these SAD values, it is apparent that the right side of the search image is the most similar to the template image, because it has the least difference as compared to the other locations |
MOTION ESTIMATION ALGORITHMS
|
| Motion estimation is the process of determining motion vectors that describe the transformation from one 2D image to another; usually from adjacent frames in a video sequence. It is an ill-posed problem as the motion is in three dimensions but the images are a projection of the 3D scene onto a 2D plane. The motion vectors may relate to the whole image (global motion estimation) or specific parts, such as rectangular blocks, arbitrary shaped patches or even per pixel. The motion vectors may be represented by a translational model or many other models that can approximate the motion of a real video camera, such as rotation and translation in all three dimensions and zoom. |
| Applying the motion vectors to an image to synthesize the transformation to the next image is called motion compensation. The combination of motion estimation and motion compensation is a key part of video compression as used by MPEG 1, 2 and 4 as well as many other video codecs. |
| Types of algorithms used in the object tracking are |
| 1. Different Motion Analysis (DMA) |
| 2. Block Matching Algorithm (BMA) |
BLOCK MATCHING ALGORITHM:
|
| The block matching algorithm is a standard technique for encoding motion in video sequences. BMA is a way of locating matching blocks in a sequence of digital video frames for the purposes of motion estimation.It aims at detecting the motion between two images in a block-wise sense. The blocks are usually defined by dividing the image frame into nonoverlapping square parts. Each block from the current frame is matched into a block in the destination frame by shifting the current block over a predefined neighbourhood of pixels in the destination frame. . 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. |
SIMPLE AND EFFICIENT SEARCH (SES)
|
| SES is another extension to TSS and exploits the assumption of unimodal error surface. The main idea behind the algorithm is that for a unimodal surface there cannot be two minimums in opposite directions and hence the 8 point fixed pattern search of TSS can be changed to incorporate this and save on computations. |
| The algorithm still has three steps like TSS, but the innovation is that each step has further two phases. The search area is divided into four quadrants and the algorithm checks three locations A,B and C as shown in Figure Y. A is at the origin and B and C are S = 4 locations away from A in orthogonal directions. Depending on certain weight distribution amongst the three the second phase selects few additional points (Fig 5). The rules for determining a search quadrant for seconds phase are as follows: |
| If SAD(A) _ SAD(B) and SAD(A) _ SAD(C), select (b); |
| If SAD(A) _ SAD(B) and SAD(A) _ SAD(C), select (c); |
| If SAD(A) < SAD(B) and SAD(A) < SAD(C), select (d); |
| If SAD(A) < SAD(B) and SAD(A) _ SAD(C), select (e); |
| Three Step Search block matching: Big circles are checking points in the first step of TSS and the squares are the extra 8 points added in the first step of NTSS. Triangles and diamonds are second step of NTSS showing 3 points and 5 points being checked when least weight in first step is at one of the 8 neighbours of window center. |
RESULTS
|
| Computation time, Motion analysis time and time for SAD are calculated for the different searches and the results are plotted in the graph and observed that the simple and efficient search is the most efficient search for tracking the object. |
| In order to detect an object at first an background without an object is taken as reference |
 |
| Screenshot of input without object in the background |
 |
| Screenshot of coordinates of the ball tracked. |
| After subtraction of the two images the coordinates of the ball is obtained to where it has moved with respect to the reference .The coordinates of the ball in the above frame is added with the motion vector to get position of the tracked image |
CONCLUSION
|
| A new fast full-search block-matching algorithm is presented in this paper. It runs much faster than the traditional fullsearch BMA, while the optimal accuracy of motion estimation is guaranteed. This improvement of speed is based on the fact that multiple matching errors which have different levels of computation complexity are available on each position tobe searched. The relationships among the multiple matching errors of a candidate position are utilized to construct three test conditions which can be employed during block matchingto avoid the time-consuming computations of MSE or MAE measurements. With the experiments, the proposed method can give a great amount of savings of computations, and thus can be well suited for a wide range of applications, such as videotelephony, videoconferencing, and HDTV. |
Figures at a glance
|
 |
 |
 |
| Figure 1 |
Figure 2 |
Figure 3 |
|
References
|
- Keane, B., Mettler, E., Tsoi, V., &Kellman, P. (2011). Attentional signatures of perception: Multiple object tracking reveals the automaticity of contour interpolation. Journal of Experimental Psychology: Human Perception &Performance, 37, 685-698.
- Franconeri, S., Jonathan, S., &Scimeca, J. (2010). Tracking multiple objects is limited only by object spacing, not speed, time, or capacity. Psychological Science, 21, 920-925
- S.A. El-Azim, I, Ismail, and H.A. El-Latiff, “An efficient object tracking technique using block-matching algorithm,” Proc. Of the Nineteen National, Radio Science Conf., pp.427-433,2002.
- Y.L., Chan and W.C. Siu, “New adaptive pixel decimation for block motion vector estimation”, IEEE Trans. Circuit and Systems fro Video Tech., vol. 4, no 4, Aug. 1994.
- R. Li, B.ZengandM.Liou, “A new three step search algorithm for block motion estimation”, IEEE Trans. Circuit and Systems fro Video Tech. vol. 6.no 1, Aug. 1994
|
Menu