Screenplays & Play

4 pages
11 views

Block matching algorithm based on local codirectionality of blocks

Please download to get full document.

View again

of 4
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Description
Block matching algorithm based on local codirectionality of blocks
Transcript
  BLOCK MATCHING ALGORITHM BASED ON LOCAL CODIRECTIONALITY OF BLOCKS S.M.R. Soroushmehr  1  , S. Samavi 1, 2  , S. Shirani 2 1 Isfahan University of Technology, Iran 2 McMaster University, Canada ABSTRACT In this paper based on statistical analysis performed on a number of video sequences with different motion characteristics, we show that strong correlation exists  between the direction of motion of a block and those of its neighboring blocks. Secondly, we show that a block moves in the same direction as a neighboring block that its  prediction vector produces least distortion. Based on these findings an algorithm is proposed which adaptively determines the direction of motion of a block based on the motion direction of its neighboring blocks. The algorithm almost always avoids trapping into local minima. Test results show that in terms of speed and performance the  proposed algorithm is superior to many of the existing fast algorithms.  Index Terms—  motion estimation, motion vector, block matching, direction prediction .1. INTRODUCTION Digital video requires large memory space for storage and requires wide bandwidth for transmission. Nowadays, video ranks first, in terms of volume, among all types of  produced data [1]. Compression of video image sequences could be effective in reducing the required storage and transmission bandwidth. During the recent years numerous compression standards such as H.261/263/264, and MPEG1/2/4 for different video applications have been introduced. Many of these standards use block matching algorithms for their motion estimation (ME) part. The full search (FS) algorithm is a straightforward algorithm that finds the best matched block in ME part. Though simple, this algorithm is very computationally demanding. To alleviate this shortcoming numerous algorithms have been devised for fast search and real time implementation. Three step search (3SS) [2] and four step search (4SS) [3] are two of many algorithms  proposed to speed up the search process. These algorithms assume that the block matching error increases monotonicallyas the search moves away from the position of global minimum error. Because this assumption is not always true [4], in some algorithms initially the motion vector is predicted and then the search is performed around the predicted vector [4- 10]. In this paper an algorithm is proposed which predicts a motion vector based on the correlation among the direction of a block and that of its neighbors. What we mean by the “direction of a block” is the direction of movement of a  block. The proposed algorithm unlike those of [5] and [7]  based on the direction of a block’s neighbors adaptively decides which prediction vector to use among a number of contender vectors. The paper is organized such that in section 2 we explain the concept of codirectionality. In section 3 a criterion that determines the direction of a block is closer to which one of its neighbors is discussed. The details of determining the direction of a block without computing the angle of movement are discussed in section 4. In section 5 the  proposed algorithm is explained. The simulation results are  presented in section 6. Concluding remarks appear in section 7 of the paper. 2. LOCAL CODIRECTIONALITY OF BLOCKS In this section based on statistical analysis we show that there is a strong correlation between the direction of a block and its neighbors. These analyses were performed on a number of standard video sequences with different movement characteristics. First of all we mention a brief introduction. Figure 1 shows the current block,   , and its four neighboring blocks of   ,    ,    , and   . Not shown in Figure 1 is    in the reference frame which has the same location as    . The motion vector for any of the mentioned indexed blocks is expressed by       ,      where   is the block index number. Figure 1. Current block,   , and its neighbors. We quantize the direction of a block into 9 possible directions as shown in Figure 2. Direction zero not shown in Figure 2 corresponds to motion vector of (0, 0). 1 Soroushmehr, S. M. R., Samavi, S., & Shirani, S.,"Block matching algorithm based on local codirectionality of blocks," In IEEE International Conference on  Multimedia and Expo (ICME),pp. 201-204, June 2009 .  Figure 2. Suggested segmentation of the plane into 8 regions. The segmentation of Figure 2 could be achieved by drawing 4 lines according to Equations (1).             (1)Each direction shown in Figure 2 consists of a set of angles which is defined according to the following equation.                     (2)The value of     and     in Equation (2) are defined in Table1. Table 1. Coverage of each direction in degrees.          26.56 -26.56 0   63.43 26.56 1   116.56 63.43 2   153.43 116.56 3   206.56 153.43 4   243.43 206.56 5   296.56 243.43 6   333.43 296.56 7 In the followings it is intended to use the full search algorithm on the standard sequences and gather statistics on the behavior of the motion vectors. The likelihood of the  block motion direction being close to one of its neighboring  blocks will be studied. Based on the statistical observations we will layout our algorithm. Let us first present a number of definitions. The event            consists of the outcomes that the movement of    with the angle    belongs to the set   . Similarly            consists of the outcomes that    moves with the angle    which  belongs to the set   . Let the conditional  probability               define the probability of the event     given that the movement of    is defined by    for all   from 0 to 8. Table 2 shows the value of    computed for 6 different video sequences with standard CIF format. Table 2. Percentage of codirectionality between    and   . Sequence name                Susie 57.19 65.44 61.14 62.81 70.18 Garden 92.72 92.71 92.11 93.18 94.71 Tennis 71.15 74.68 65.79 79.62 90.28 Football 65.68 72.48 65.57 71.33 51.32 Salesman 60.91 64.35 58.39 68.07 81.68 Average 69.53 73.93 68.60 75.00 77.63 For example in Tennis sequence in 79.69 percent of cases the direction of a block has been same as the block to its left,    . In average, for example, in 73.93 percent of cases a  block is codirectional with the movement of its    neighbor. This table reveals the strong correlation between the direction of a block and its neighbors. 3. SELECTING THE BLOCK WITH HIGHEST CODIRECTIONALITY In the previous section we showed the existence of codirectionality between neighboring blocks. In this section we show that the best codirectional block is the one that results in least distortion. In Equation (3) six indices corresponding to the block numbers are generated, which based on their resulted distortions, are listed in an ascending order. (3)                             In this equation     indicates the distortion when comparing the current block with a block in the reference frame which has a displacement measured by    vector. Hence,    is the index of the block which has produced the least amount of distortion and    is the block index whose motion vector, when used as a prediction vector, results in the largest distortion. For example, if the motion vector of    results the least distortion then    would be equal to 3. In order to demonstrate the correlation between the  produced distortion and the direction of a block we define the conditional probability of    in the following equation. (4)                In Equation (4), for example    is the percentage of cases that    is codirectional with the block that produces least distortion. Table 3 shows   for different values of   for a number of video sequences. For example in Susie sequence    is about 72.63 percents while    is about 23 percents lower at 49.56. The probability    shows the percentage of cases where a  block moves in the direction of a neighboring block that  produces the most distortion. It can be seen that in most cases increasing distortion means reduction in codirectionality. 2  Table 3. Codirectionality with neighboring blocks sorted based onthe produced distortions. Sequence name r=1 r=2 r=3 r=4 r=5 Susie 72.63 70.70 64.82 59.04 49.56 Garden 95.46 95.41 94.61 92.66 87.30 Tennis 85.93 84.68 76.44 70.39 64.07  Football  74.01 72.97 70.61 65.73 43.04 Salesman 71.65 73.54 69.68 65.19 53.33 Average79.94 79.46 75.23 70.60 59.46 4. DETERMINING DIRECTION OF MOVEMENT In section 2 the correlation between directions of blocks was discussed. In this section we offer a method for determining the direction that a block is moving and we compare our method with that of reference [5]. In the proposed method having the angle of the motion vector is not necessary. A simple comparison between   ,the  -component of the motion vector, and the shifted   can give the direction of the block. Table 4 presents a set of simple comparisons that are required for finding out the direction. Table 4. Determining direction from magnitude of  s. Direction Condition 0       ,        1       ,            2       ,         ,               3       ,           4       ,       ,                5       ,            6       ,               7       ,          8       ,               For example if the x-component of a motion vector is  positive (      ) and the magnitude of the y-component is smaller than half of the  -component               then the motion vector’s angle must be in the range of    to   . This is equivalent to direction 1 of Figure 3. In case of hardware implementation of the suggested algorithm, Table 4 can easily be realized by 2 comparators and simple combinational circuit. The hardware realization of Table 4 is presented in [7]. In reference [5] Equation (5) is used to find out the direction of a block. (5)                    where the    is the angle that the motion vector makes with the  -axis. The value of  , depending on the value of   and    , can be 0, 1, or 2. The hardware implementation of this method is extremely difficult due to need for transcendental computations. The algorithm that we  propose can easily be implemented in hardware. 5. PROPOSED MOTION ESTIMATION METHOD In this section, based on the findings of previous section, we propose a motion estimation method which is called codirectionality assisted predicted search  (CAPS). The algorithm is explained in the followings. 1) The motion vectors of blocks    to    are used as  prediction vectors. The distortions of these blocks are computed and sorted in an ascending manner. 2) The   of the block with index   , using Table 4, indicates the predicted direction. Along this direction,     number of search points are picked, where   is the width of the search window. These points have offsets that are even multiples of the directionalunit vectors  shown in Table 5. For example if a block is predicted to move in direction 3 and   is set to 7 then the points  ,  , and   are searched first. The vector that  produces the minimum distortion is used as an initial search  point for step 3. Table 5. List of directional unit vectors.    Unit vectors 0(0,0) 1(1,0)2(1,-1)3(0,-1)4(-1,-1)5(-1,0)6(-1,1)7(0,1)8(1,1) 3) A     search window is established around the initial search vector. Hence, 9 blocks are examined. 4) If minimum error is produced by a block which is located at the center of the search window, then step 6 of the algorithm is performed otherwise step 5 will be carried out. 5) The minimum point of step 4 will be the new search center. If the maximum number of iterations,   , has not  been reached then step 3 will be executed, otherwise, step 6 will gets activated. 6) The motion vector produced minimum distortion is stored as the motion vector of the block. 6. SIMULATION RESULTS We used 30 frames from sequences of Susie, Garden, Tennis, Salesman , and  Football   which had CIF format. Maximum displacement of 15 pixels and block size of     were considered. The matching process used SAE as the criterion of choice. Also the maximum iteration (   ) of 13 was selected. Since the algorithm uses the vector which produces the least distortion we could use a min  function in step 1 of the algorithm which only returns the index of the block with minimum distortion. Table 6 shows the average  PSNR  when the proposed CAPS algorithm was compared with FS, 3SS, 4SS, and APDSA [5] algorithms. In terms of average  PSNR  the proposed algorithm has a  better performance with respect to all of the compared algorithms. In Tennis sequence, as an example,  PSNR  of CAPS algorithm is about 2.22 dB better than 3SS and about 3  0.59 dB better than APDSA. In addition, for the same sequence, the average number of search points (  NSP  )required by CAPS is about 49% that of required by 3SS algorithm. Table 7 shows the average number of search  points required by an algorithm. Table 6. Average  PSNR  (dB) for different algorithms Sequence nameFS3SS4SSAPDSACAPS Susie 33.8432.64 32.82 33.30 33.59  Football  23.6122.63 22.66 22.79 23.18 Tennis 27.7524.89 26.12 26.52 27.11 Garden 24.2421.41 23.77 24.14 24.16 Salesman 34.8134.59 34.69 34.74 34.74 Average28.85 27.23 28.01 28.30 28.56 Table 7. Average number of search points for different algorithms. Sequence nameFS3SS 4SSAPDSACAPS Susie 859.45 30.56 19.80 16.11 12.2  Football  859.45 30.47 16.59 16.16 14.36 Tennis 859.45 30.78 20.58 13.84 15.34 Garden 859.45 30.71 19.00 11.52 13.12 Salesman 859.45 31.14 16.63 9.94 9.36 (a) Susie  video sequence (b) Tennis  video sequence Figure 3.  PSNR (dB) of different algorithms for 30 frames.   For the Tennis  sequence, the average  NSP   of the proposed algorithm is higher than that of APDSA. But for the sequence, CAPS produces better average  PSNR  than APDSA. The findings of Tables 6 and 7 indicate that the search in the direction that is suggested by CAPS results in faster finding of a matched block and also results in better  PSNR  values in comparison with other search algorithms. It can be deduced that the chance of trapping in local minima has been reduced  by the proposed algorithm especially for sequences with fast movements. In Figures 3(a) and 3(b)  PSNR  is plotted in terms of dB for 30 consecutive frames from Susie and Tennis sequences for different algorithms. For most of the frames the plot of CAPS is the closest to that of FS. 7. CONCLUSION In this paper based on statistical analysis performed on a number of standard video sequences with different characteristics, we showed that there is a strong codirectionality among neighboring blocks. We also showed that, in average, codirectionality and distortion are inversely proportional. Based on these observations, an algorithm was proposed which adaptively determined the direction of a block based on the direction of its neighboring  blocks. A simple method was offered for predicting the direction of a block. According to the predicted direction an initial search point was selected and the search was  performed around the predicted vector. Simulation results showed that the proposed algorithm is superior to many of the existing fast algorithms in terms of complexity and  performance. 8. REFERENCES [1] I. E. G. Richardson, Video codec design , John Wiley & Sons, England, 2002. [2] T. Koga, et al., “Motion compensated interframe coding for video conferencing,”  Proc. NTC81 , New Orleans, LA, pp. C9.6.1-9.6.5, Nov. 1981. [3] L. M. Po, W. C. Ma, “A novel four-step search algorithm for fast block motion estimation, ” IEEE Trans. Circuits Syst. Video Techno. , Vol. 6, No. 3, pp. 313-317, June. 1996. [4] G. Sorwar, M. Murshed, L. Dooley, “A fully adaptive distance-dependent thresholding search (FADTS) algorithm for  performance management motion estimation, ” IEEE Trans. Circuits Sys. Video Technol  ., Vol. 17, No. 4, pp. 429-440, April. 2007.[5] J. Y. Nam, J. S Seo, J. S. Kwak, M. H. Lee, and Y. H. Ha, “New fast search algorithm for block matching motion estimation using temporal and spatial correlation of motion vector, ” IEEE Trans. Consumer Electronics , Vol. 46, No. 4, pp. 934-942, Nov. 2000.[6] P. Y. Chen, J. M. Jou, “An efficient blocking matching algorithm based on fuzzy reasoning,”  IEEE Trans Syst, Man, Cybern.-Part B , Vol. 31, No. 2, pp. 253-259, Apr. 2001. [7] S. M. R Soroushmehr, S. Samavi, S. Shirani, H. Tafazoli , “Motion estimation by segmentation and prediction of direction,”  Proceeding of the IEEE CCECE  , pp. 1955-1958, May 2005. [8] S. M. R Soroushmehr, S. Samavi, “An adaptive block matching algorithm for motion estimation,”  proceedings of the IEEE CCECE  , pp. 331-334, May 2008. [9] I. Ahmad, W. Zheng, J. Luo, M. Liou, “A fast adaptive motion estimation algorithm, ” IEEE Trans. Circuits Sys. Video Technol  ., Vol. 16, No. 3, pp. 420-438, March. 2006. [10] J. Luo, I. Ahmad, Y. Liang, V. Swaminathan, “Motion estimation for content adaptive video compression,”  IEEE Trans. Circuits Sys. Video Technol  ., Vol. 18, No. 7, pp. 900-909, July 2008. 4
Related Documents
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x