iDocSlide.Com

Free Online Documents. Like!

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

Tags

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

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