Fuzzy Logic Based Four Step Search Algorithm for Motion Vector Estimation

Published Online May 2012 in MECS

Visual information is very much important for human to perceive, recognize and understand the surrounding world. As we live in the age of multimedia video sequences are very useful to us for providing information. Video refers to the sequence of image frames. Video involves a huge amount of data. So large amount of storage is required to store a video sequence and a huge bandwidth required to transmit a video sequence. But practically this is not possible to provide a large storage or huge bandwidth for every video sequence. So video compression is a necessary step to reduce video size. Video compression refers to a process in which the amount of data used to represent the video is reduced to meet the bandwidth requirement of the network or space requirement. The ISO Moving Picture Experts Group (MPEG) video coding standards is for compressed video storage in physical media like hard disk, and International Tele-communications Union (ITU) [13] addresses the real time point to point or multipoint communication over a network. But the compression and decompression process for both the cases is almost same. Figure 1 shows the video compression process.

Figure 1. Video Compression Block Diagram

The motion compensation is the most computational expensive process in the whole video compression process. In motion estimation, it is assumed that change in successive frame due to translational moving of the objects. The effects of camera zoom, and object rotations are not considered. Occlusion effects are also neglected. Motion estimation examines the movement of the object in sequence to try to obtain the vectors representing the estimated motion. Encoder side estimates the motion of the current frame with respect to previous frame. A motion compensated image of the current frame is then created. Motion vector is then transmitted to decoder. Decoder reverses the whole process and creates a full frame. This way motion compensation uses the knowledge of object motion to achieve data compression. There are two techniques for motion compensated coding

• •    Pel-Recursive Algorithm (PRA)

• •   Block Matching Algorithm (BMA)

Pel-Recursive Algorithm (PRA) [11] introduced by Netravali and Robbins, defines motion vector for every pixel which comprises the location of the pixel of the current frame in the previous frame. Block matching algorithm is the simple and straight forward technique for Motion vector Estimation. So far this technique is the most utilized technique in video compression and adopted by all the international video coding standards like ISO MPEG1, ISO MPEG2 and ITU H.264 etc. In block matching algorithm every image is partitioned into fixed size non overlapped small rectangular blocks as proposed by jain and jain [ ]. It was assumed that all the pixels within a block have same motion activity. So for every block only one motion vector is estimated. Smaller block size leads to accurate approximation but also increase the computational complexity. So a tradeoff between the accuracy and computational complexity required. So 16X16 can be used as standard block size. But some time for finer estimation 8X8 block size is used The matching of one macro block with another is based on the output of a cost function. The macro block that results in the least cost is the one that matches the closest to current block. There are various cost functions, of which the most popular and less computationally expensive is Mean Absolute Difference (MAD) [9] given by equation (1).Another cost function is Mean Squared Error (MSE) [9] given by equation (2).

MAD = 1/ N2 N^ NNT| cufra(i,_ j) - refra(i,. j) | i =0 j=0                                      (1)

N - 1 N - 1

MSE = 1 / N ² ^^ ( cufra(i i, j ) - refra( i , j ))²

i = 0 j = 0

N= Size of the macro block.

cufra(i, j) = Intensity value for the current frame.

refra(i,j) = Intensity value for the reference frame

Signal to Noise ratio (SNR) is widely used in quality measurement. SNR can be calculated using equation (3).

SNR =10

. /Sk=o ^o1 img out(k,iy log ------------------------- VH.MSE^

In image quality measurement another closely related term is Peak Signal to Noise Ratio (PSNR) which is a modification of SNR. PSNR characterizes the motion compensated image that is created by using motion vectors and macro blocks from the reference image. PSNR can be calculated using equation (4).

PSNR = 10 log

( PtoP )² MSE

PtoP=peak to peak signal MSE=Mean square error

f igure 2. Block Matching of a 16x16 macro Block within a search area of 7 pixels.

Block matching algorithm for motion estimation is accepted in all the video coding standards proposed till date. It is easy to implement in hardware and real time motion estimation and prediction is possible. Exhaustive search (Full Search) is the most time and computationally expensive algorithm. Later the other algorithms implemented to reduce the computation cost are Three Step Search (TSS), Four Step Search (FSS), New Three Step Search (NTSS), Diamond Search (DS), and Adaptive Rood Pattern Search (ARPS) etc. In this paper we propose to implement Fuzzy logic based Four Step Search Algorithm.

Section I is a brief introduction about the motion vector estimation and video compression. Section II is a short review on the different research works about motion compensation. Section III describes the Four Step Search algorithm. Section IV presents our proposed algorithm. In Section V the performance of our proposed algorithm is compared with different block matching algorithms.

• II.   Literature Review

Pel-recursive algorithm, is the first algorithm developed by Robbins and Netravali, defines motion vector for every pixel with the help of steepest decent method. Bargman [14] proposed to use Newton Raphson method instead of using steepest descent method. Walker and Rao [10] introduced a variable step size for steepest descent method.

For block matching algorithms, Full search or Exhaustive search provides best result. Later different algorithms were developed to reduce the computation cost of Full search algorithms. Earlier square search pattern of different length was adopted. Algorithms like Three Step Search [2], New Three Step Search [3], Four Step Search [4], Block Based Gradient Descent Search [5], Simple and Efficient Search [12] etc have adopted the square search pattern. The square search pattern can be classified in ‘+’ and ‘x’ pattern. Two dimensional logarithmic search [1] has adopted the ‘+’ search pattern where cross search algorithm [17] has adopted ‘x’ search pattern.

Then diamond type search pattern minimizes the process time. Different algorithms adopted the diamond search pattern as unrestricted center biased diamond search algorithm [8], New Diamond Search Algorithm [6] etc. Adaptive Rood Pattern Search [16] uses the motion vector of the macro block to its immediate left to predict the motion vector of the current macro block. This algorithm uses the diamond type search pattern. But ARPS performs better than other algorithms. Recent studies show that other patterns like hexagon [7], octagon [15] provides better result than diamond pattern. Other approaches to reduce the computation cost of Full search are Fast full search algorithm [19] and Successive elimination algorithm [18] etc.

• III.   Four Step Search Algorithm

  In the year 1996 four step search algorithm proposed based on the center biased motion vector distribution characteristics by LaiMan Po and Wing-Chung Ma. The Four Step Search (FSS) algorithm can be summarized as follows-

• [1]    Set search parameter 7. As shown in figure 3a, pick nine points from 5X5 window located at previous frame to start search for the best match. [2]    Measure the block distortion with any of the cost function between the block in the current frame and the block to be search for best match at the previous frame. [3]    Find the block with minimum distortion. [4]    If the minimum distortion is at the center. Then go to step 8. [5]    Else the search continues. Search window remains 5X5. The search pattern depends on the position of previous minimum distortion point.

Step A, If the minimum distortion point is at the corner then five additional points need to be search as shown in figure 3b.

Step B, Else the minimum distortion point is at the middle of the vertical or horizontal axis then three additional points need to be search as shown in figure 3c.

• [6]    If the minimum distortion point is at center then go to step 8 else go to next step.

• [7]    The search process is same like step 5 and step 6. The process continues to step 8.

• [8]    Search window reduced to 3X3 as shown in figure 3d. Additional eight points need to be search. The minimum distortion point from these nine points is the best match.

If the minimum distortion point is at the center then The intermediate step of the algorithm may be skipped and we can move to final step. So, computational requirement can be reduced. Total no of checking points varies from 17 to 27.

Figure 3. Search Patterns for FSS (a) Step one and two (b) Step Five A (c) Step Five B (d) Step Eight

• IV.   Proposed Algorithm

Four step search algorithm searches all the four side of a macro block. But some time search at all the four side is not necessary. The change from dark intensity to light intensity is called edge region in an image. A macro block in one side of an edge need not be search for its best match at the other side of the edge. If the macro block is at the lighter side of the edge then search at the darker side for best match is not necessary. According to proposed algorithm a fuzzy membership value introduced according to intensity for every block. From the intensity values of the pixels within a macro block a value is calculated which defines whether the macro block is in darker or lighter region. Search can only continue if the fuzzy membership value of the macro block of the reference frame is in the allowable range of macro block of the current frame. The search pattern and other step is similar like four step search.

• [1]    Calculate fuzzy membership value for every block in the previous frame

• [2]    Calculate fuzzy membership value for every block      in      the      current      block.

• [3]    Set the search location at center of search window and set search window parameter 7.

• [4]    Pick nine points from the 5X5 window located at previous frame to start search for the best match.

• [5]    Whether the fuzzy membership value of the block of reference frame going to be search is in the allowable range with the fuzzy membership value of the present frame.

• [6]    If yes then calculate the block measure distortion for that macro block else skip the calculation.

• [7]    Find the minimum block distortion between those macro blocks whose block distortion has been calculated.

• [8]    If the minimum distortion is at the center then go to step 14.

• [9]    Else search continues. Search window remains 5X5. The search pattern depends on previous minimum distortion point.

Step A,      If the point is at the corner then pick five additional points as shown in figure 3b.

Step B,     If  the minimum  distortion point is at the middle of the vertical or horizontal axis then pick three additional points as shown in figure 3c.

• [10]    The search process will continue for the additional points only if the condition stated at step five is yes. Else skip the search for that macro block.

• [11]    Find the minimum block distortion between those macro blocks whose block distortion has been calculated.

• [12]    If the minimum distortion is at the center then go to step 14. Else go to next step.

• [13]    The search process is same like step nine, ten and eleven. Process continues to step 14.

• [14]    Search window reduced to 3X3. Pick additional eight points.

• [15]    Search process only continues if the condition stated in step five valid for the points else we skip the search.

• [16]    From the calculated block distortion measure, the block with minimum distortion is the best match.

Calculated motion vector saved for transmission. Same as four step search if the minimum distortion point is at the center then the intermediate steps can be skipped. In this whole process by adding the additional fuzzy membership value those calculations can be skipped which are not necessary. The fuzzy membership value can be anything that defines whether the block is lighter or darker. The mean of the intensity values of macro blocks can be used as fuzzy membership value. The mean value is normalized between 0 to 1.

N - 1 N - 1

Mean = 1/(255 * N2)^^ frame(i, j) i=0 j =0                     (5)

N= Size of the Macro Block frame(i,j)= intensity value at i,j.

As 255 is the maximum intensity for an image. So this value is needed to normalize the value of mean between 0 to 1.

This algorithm has a worst computational requirement is 27. But the unnecessary computations can be skipped using the fuzzy membership value. So minimum required computation can be reduced than four step search algorithm. This will increase the speed of the process. The speed of the process and the quality of the reconstructed image can be controlled by controlling the allowable range. For higher speed a narrow range is required and for good quality wider range need to set.

• V.    Simulation

Proposed algorithm simulated using first six frames of the foreman sequence. The performance of the proposed algorithm is then compared with the performance of other block matching algorithm as Three Step Search (TSS), New Three Step Search (NTSS), Four Step Search (FSS) etc. In the simulation procedure MSE is used as cost function to determine the block distortion. Search window parameter is 7. In the video compression after few frames one frame is need to be sent in original. But here we use only siz frames so first frame is sent in original. Figure 4,5,6,shows the 4th no of frame in original, reconstructed after FSS procedure and reconstructed after proposed algorithm.

Figure 4. Original foreman sequence 4th frame.

psnr

No of Frames

Figure 7. PSNR performance by different algorithms

Figure 5. After FSS procedure reconstructed foreman Sequence 4th frame.

Figure 8. Total Computation required by different algorithms

In Figure 7, 8, 9 we compare the performance of the proposed algorithm with other block matching algorithms. It shows with almost same picture quality

Figure 6. After Fuzzy logic based FSS procedure reconstructed foreman sequence 4th frame.

Figure 9. Total time in Seconds required for different algorithms

proposed algorithm performs better than other block matching algorithm in terms of Time and computation.

proposed algorithm ves yes

"" Minimu m distortion

-"Search completed" jot all macro blocks?

icints completed?-

Minim um distortion at the cornet point?

iearch at all the-loinis complete

^/-"Fuzzy membership""--..

value of the selected block in me\. previous frame is within the allowable range of the fuzzy membership value of the block in the ///

"--.. present frame

^/Fuzzy membership

....--'"value of the selected block in the""--... "previous frame is within the allowable range -...^ of the fuzzy membership value of the block in the ..,--"'

^^-present frame/"

/-fuzzymembership "/.

./-"value of the selected block in the'"--, "previous frame is within the allowable range -/. of the frizzy member ship value of the block in the

" - .. present frame/'

Set step size S=2 and Pick 9 points from the search window as show in figure 3a.

Calculate the block distortion for that macro block

Find file minimu m block distortion between all the calculated blocks

Flow chart of the

Increase Counter by 1

( Step j

Pick the position of the current macro block from the present frame and set ±e search location center at the same position in the previous macro block. Set a rectangular search window around that macro block at a distance of 7 pixels.

Calculate the fuzzy membership value every block in the previous fr ame

Calculate the fuzzy member^up value every block in thF current frame

Find the minimum block distortion between all the ^ v calculated blocks

—--■   Xlimmum distortion          ___

*  -—----at center?—__——’   Yi

___________2£NO__________

Move the search location center at the minimum distortion point and step size is same

Find the minimum block distortion between all the calculated blocks and that is the best match

Reduce the step size 8=1 and pick 9 point-: as shown in figure 3d

Calculate the block distortion tot that macro block

Calculate the block distortion for that macro block

Move the search location center at the minimu m distortion point and step size is same

Pick 5 additional points as in figure 3b

Pick 3 additional points as in figure 3c

• VI.    Conclusion

Fuzzy logic based four step search algorithm reduces the computation. As the computation reduced the whole process becomes faster. In this algorithm the speed of the process and the quality of the reconstructed image can be controlled. This concept can be applicable for other block matching algorithms.