8 April 2013 Modified one-bit transform method with dynamic search range
J. of Electronic Imaging, 22(2), 023001 (2013). doi:10.1117/1.JEI.22.2.023001
Abstract
Here, a new low-complexity block motion estimation method is presented. The proposed method significantly reduces the computational complexity by checking only one of two search areas in the conventional hybrid method when the two search centers are close to each other. It also improves the performance by efficiently making use of the motion vector information of the co-located macroblock. The proposed techniques can be easily applied to many hybrid motion estimation methods.
Lim, Kim, and Yu: Modified one-bit transform method with dynamic search range

## Introduction

Motion estimation is an essential part of most video coding standards. Although the full search (FS) method gives the best performance, it incurs enormous computational complexity. Thus, many low-complexity motion estimation algorithms have been proposed, including the one-bit transform (1BT), two-bit transform (2BT), and constrained 1BT (C1BT) methods.12.3 These low-complexity methods greatly reduce the complexity, but they lead to very low peak signal-to-noise ratio (PSNR) values. In order to solve this problem, many hybrid methods have been proposed that combine the low-complexity methods with the FS method. For example, the modified 1BT (M1BT) method combines the 1BT method with the FS method.4 The modified 2BT (M2BT) and modified C1BT (MC1BT) methods also combine low-complexity methods with the FS method.5,6 This paper proposes an efficient search scheme that not only reduces the complexity, but also improves the performance of these conventional hybrid methods.

## Conventional Hybrid Methods

The FS method is based on the sum of absolute differences (SAD) measure, which is defined as follows:

## (1)

$\mathrm{SAD}\left(m,n\right)=\sum _{i=0}^{N-1}\sum _{j=0}^{N-1}|I\left(i,j\right)-{I}_{\mathrm{ref}}\left(i+m,j+n\right)|,$
where $I\left(·\right)$ and ${I}_{\mathrm{ref}}\left(·\right)$ represent the current and reference images, respectively, $N$ is the size of a macroblock, and $\left(m,n\right)$ represents the motion vector. The 1BT method has been proposed to reduce the high computational complexity of the FS method.1 It uses a filter kernel to filter the original image $I\left(i,j\right)$ and to obtain a filtered image ${I}_{F}\left(i,j\right)$.7,8 The filtered image is compared with the original image to obtain a binary image $B\left(i,j\right)$ as follows:

## (2)

$B\left(i,j\right)=\left\{\begin{array}{cc}1& I\left(i,j\right)\ge {I}_{F}\left(i,j\right)\\ 0& \text{otherwise}\end{array}.$

Instead of using the SAD measure, the 1BT method uses the number of non-matching points (NNMP) measure, which is defined as follows:

## (3)

$\mathrm{NNMP}\left(m,n\right)=\sum _{i=0}^{N-1}\sum _{j=0}^{N-1}\left[B\left(i,j\right)\oplus {B}_{\mathrm{ref}}\left(i+m,j+n\right)\right]\phantom{\rule{0ex}{0ex}}-s\le m,n\le s,$
where $B\left(·\right)$ and ${B}_{\mathrm{ref}}\left(·\right)$ represent the current and reference binary images, respectively, $\oplus$ represents the 1-bit XOR operation, and $s$ determines the search range. The 2BT and C1BT methods are also based on 1-bit operations although they use slightly different NNMP measures.2,3 Although the 1BT, 2BT, and C1BT methods are all low-complexity solutions, they lead to relatively very low PSNR values when compared with the FS method.

Thus, Ref. 4 proposed a hybrid method, called the M1BT algorithm, which combines the low-complexity 1BT algorithm with the high-accuracy FS algorithm. In the first stage of the M1BT method, two motion vectors, $m{v}_{1}$ and $m{v}_{2}$, are selected, which have the lowest and second lowest NNMP values. Then, the SAD of the motion vector $m{v}_{1}$ is computed. If it is less than a threshold value ${T}_{1}$, $m{v}_{1}$ is selected as the final motion vector. Otherwise, the SAD of the second motion vector $\left(m{v}_{2}\right)$ is computed. If it is smaller than ${T}_{1}$, $m{v}_{2}$ is selected as the final motion vector. If not, the search process goes on to the second stage.

The second stage consists of two steps, as shown in Fig. 1. In the first step of the second stage, the SAD values of four additional points (in addition to the center point) are computed, and then the point with the minimum SAD is selected as the center point for the second step. In the second step, the SAD values of eight additional points (i.e., the square-shaped points in Fig. 1) are computed. The two steps are applied for $m{v}_{1}$ and $m{v}_{2}$, and the point with the minimum SAD is selected as the final motion vector.

## Fig. 1

Two-step search in the M1BT method.

The M1BT method leads to a good tradeoff between performance and complexity, and as a result, several similar approaches have been proposed. For example, the 2BT and C1BT methods have been combined with the FS method to yield the M2BT5 and MC1BT6 methods, respectively.

## Proposed Method

The SAD computation in Eq. (1) requires relatively complex full-bit operations, whereas the NNMP computation in Eq. (3) uses only simple 1-bit operations. In order to reduce the complexity of the SAD operation, it is possible to use some subsampled SAD (SSAD) measures as follows:4

## (4)

${D}_{1}=\sum _{\left(i\text{\hspace{0.17em}}\mathrm{mod}\text{\hspace{0.17em}}2\right)=}\sum _{\left(j\text{\hspace{0.17em}}\mathrm{mod}\text{\hspace{0.17em}}2\right)}|I\left(i,j\right)-{I}_{\mathrm{ref}}\left(i+m,j+n\right)|\phantom{\rule{0ex}{0ex}}{D}_{2}=\sum _{\left(i\text{\hspace{0.17em}}\mathrm{mod}\text{\hspace{0.17em}}2\right)=0,}\sum _{\left(j\text{\hspace{0.17em}}\mathrm{mod}\text{\hspace{0.17em}}2\right)=0}|I\left(i,j\right)-{I}_{\mathrm{ref}}\left(i+m,j+n\right)|.$

The SSAD computation, however, is still much more complex than the NNMP computation. Thus, it is important to reduce the number of search points that require SAD (or SSAD) computations.

It is possible to use only one of $m{v}_{1}$ or $m{v}_{2}$ in order to reduce the number of search points, but this will lead to considerable performance degradation. However, after analyzing extensive simulation results, we found that $m{v}_{1}$ and $m{v}_{2}$ are, in most cases, located very close to each other. Table 1 shows the probability distribution of Euclidean distance (ED) between $m{v}_{1}$ and $m{v}_{2}$ for various video sequences. As can be seen from the table, $\mathrm{ED}\left(m{v}_{1},m{v}_{2}\right)$ is very small in most cases.

## Table 1

Euclidean distance between mv1 and mv2 in M1BT.

ED(mv1,mv2)123456+
Probability75.1%8.9%2.4%1.5%1.2%10.9%

Here, it is important to note that the search areas around $m{v}_{1}$ and $m{v}_{2}$ mostly overlap when $\mathrm{ED}\left(m{v}_{1},m{v}_{2}\right)$ is very small. Thus, the proposed method will search only one search area without checking the other one if $\mathrm{ED}\left(m{v}_{1},\phantom{\rule{0ex}{0ex}}m{v}_{2}\right)$ is less than or equal to 4. To be more precise, the proposed method will check only the search points around $m{v}_{X}$, where $m{v}_{X}$ represents either $m{v}_{1}$ or $m{v}_{2}$, whichever has a smaller SAD value (it should be noted that the SAD of $m{v}_{2}$ may be smaller than that of $m{v}_{1}$, even though the NNMP of $m{v}_{1}$ is always smaller than that of $m{v}_{2}$). This new scheme will significantly decrease the number of search points at the expense of slight PSNR degradation, and the simulation results will be given in the next section.

The M1BT method performs well when either $m{v}_{1}$ or $m{v}_{2}$ is located near $m{v}_{_\mathrm{FS}}$, where $m{v}_{_FS}$ represents the optimal motion vector determined by the FS method. This is usually the case, but sometimes, both $\mathrm{ED}\left(m{v}_{1},m{v}_{_\mathrm{FS}}\right)$ and $\mathrm{ED}\left(m{v}_{2},m{v}_{_\mathrm{FS}}\right)$ can become quite large. On the other hand, all of the search points in the M1BT method are located within very small areas around $m{v}_{1}$ and $m{v}_{2}$. To be more precise, for every search point $X$ around $m{v}_{1}$, $\mathrm{ED}\left(m{v}_{1},X\right)$ is always less than or equal to 4, as can be seen in Fig. 1. The same is true for $m{v}_{2}$ and every search point around $m{v}_{2}$. Thus, when both $\mathrm{ED}\left(m{v}_{1},m{v}_{_\mathrm{FS}}\right)$ and $\mathrm{ED}\left(m{v}_{2},m{v}_{_\mathrm{FS}}\right)$ are quite large, $\mathrm{ED}\left(m{v}_{_\mathrm{M}1\mathrm{BT}}m{v}_{_\mathrm{FS}}\right)$ will also be quite large, leading to significant PSNR degradation, where $m{v}_{_\mathrm{M}1\mathrm{BT}}$ represents the final motion vector determined by the M1BT method.

After analyzing diverse simulation results, we found that $\mathrm{ED}\left(m{v}_{1},m{v}_{_\mathrm{FS}}\right)$ and $\mathrm{ED}\left(m{v}_{2},m{v}_{_\mathrm{FS}}\right)$ are quite large when the area around the current macroblock contains high motion. Thus, the proposed method will adaptively determine ${d}_{1}$ and ${d}_{2}$ (in Fig. 1), based on the degree of motion (it should be mentioned that ${d}_{1}$ and ${d}_{2}$ are fixed to 2 and 1, respectively, in the original M1BT method). In order to account for the degree of motion, we use the information of the co-located macroblock (i.e., the macroblock at the same position in the previous frame) as follows:

## (5)

${d}_{1}=\text{median}\left[\mathrm{LB},{k}_{1}\left(|m{v}_{x}|+|m{v}_{y}|\right),\mathrm{UB}\right],$
where $\left(m{v}_{x},m{v}_{y}\right)$ represents the motion vector of the co-located macroblock, ${k}_{1}$ is a scaling constant, and LB and UB represent the lower and upper bounds for ${d}_{1}$. The values of ${k}_{1}$, LB, and UB in Eq. (5) have been determined to be 6, 3, and 24, respectively, based on extensive simulation results. After ${d}_{1}$ is decided, we will determine ${d}_{2}$ (i.e., the $\mathrm{ED}$ between search points) in such a way that all of the search points are located evenly within the search area. Thus, we determine ${d}_{2}$ as follows:

## (6)

${d}_{2}=\text{round}\left({d}_{1}/3\right).$

It should be emphasized that the proposed dynamic search range method does not increase the number of search points even if ${d}_{1}$ and ${d}_{2}$ are larger than the original values. Instead, it just checks a different set of search points. In other words, the proposed method skips some of the search points around the search center, but checks some additional search points that are far from the search center (when ${d}_{1}$ and ${d}_{2}$ are large). Finally, it should be noted that there are some frames that do not have motion vector information for the co-located macroblocks. For example, the first two frames in a video sequence with an IPPP… structure are such cases. For frames like this, ${d}_{1}=9$ and ${d}_{2}=3$ will be used, which are values that have also been determined based on extensive simulation results. We will call the proposed method the dynamic M1BT (DM1BT) method since the number of search points and the search area are dynamically determined.

## Comparison with the Conventional Methods

Table 2 compares the proposed DM1BT method with the conventional 1BT and M1BT methods in terms of the PSNR and the total number of search points that require SSAD computation. Both the macroblock size $N$ and the search range $s$ were set to 16, and the ${D}_{2}$ SSAD measure in Eq. (4) was used in the simulation. As mentioned in the previous section, the DM1BT method is based on two techniques. First, it reduces the complexity by checking only one of two neighboring search areas. Second, it improves the performance by adaptively deciding ${d}_{1}$ and ${d}_{2}$. In order to examine the effect of each technique, Table 2 shows three kinds of results for the proposed method, where the ${\mathrm{DM}1\mathrm{BT}}_{1}$ method uses only the first technique, the ${\mathrm{DM}1\mathrm{BT}}_{2}$ method uses only the second technique, and the DM1BT method uses both techniques.

## Table 2

Comparison with the 1BT and M1BT methods.

Video sequence (format)1BTM1BTDM1BT1DM1BT2DM1BT
PSNR (dB)PSNR (dB)# of search pointsPSNR (dB)# of search pointsHit RatePSNR (dB)# of search pointsPSNR (dB)# of search pointsHit rate
Foreman (CIF)30.6830.89704,695 (100%)30.89445,860 (63.3%)99.2%31.34692,244 (98.2%)31.33439,067 (62.3%)98.3%
Bus (CIF)23.7824.14815,624 (100%)24.13513,091 (62.9%)98.8%24.52789,266 (96.8%)24.51497,513 (61.0%)97.3%
News (CIF)35.4036.02281,999 (100%)36.01209,170 (74.2%)99.8%36.22281,908 (100.0%)36.19209,120 (74.2%)99.5%
Football (CIF)23.4524.301,349,431 (100%)24.28814,486 (60.4%)96.9%25.151,313,936 (97.4%)25.09794,950 (58.9%)92.7%
Tempete (CIF)26.1426.471,324,429 (100%)26.46760,006 (57.4%)99.3%26.591,318,707 (99.6%)26.58756,909 (57.1%)98.4%
Carphone (QCIF)29.9430.45203,708 (100%)30.44132,248 (64.9%)99.3%30.76195,403 (95.9%)30.73127,398 (62.5%)98.8%

First of all, we can see that the ${\mathrm{DM}1\mathrm{BT}}_{1}$ method uses a much smaller number of search points than M1BT. As mentioned, this is because the ${\mathrm{DM}1\mathrm{BT}}_{1}$ method checks only one of the two search areas when the distance between $m{v}_{1}$ and $m{v}_{2}$ is small. On average, the ${\mathrm{DM}1\mathrm{BT}}_{1}$ method reduces the number of search points by 36.1%. On the other hand, the PSNR degradation is negligible. This is because the final motion vectors of ${\mathrm{DM}1\mathrm{BT}}_{1}$ are, in most cases, the same as those of M1BT. The hit rate in Table 2 represents the probability that the final motion vectors of ${\mathrm{DM}1\mathrm{BT}}_{1}$ and M1BT are the same. As can be seen, the hit rates of the ${\mathrm{DM}1\mathrm{BT}}_{1}$ method for various test sequences are quite high. Table 2 also shows that the ${\mathrm{DM}1\mathrm{BT}}_{2}$ method significantly improves the PSNR performance of the M1BT method. As explained in the previous section, this is because the ${\mathrm{DM}1\mathrm{BT}}_{2}$ method adaptively increases the search range when a video sequence contains high motion. It should be noted that the ${\mathrm{DM}1\mathrm{BT}}_{2}$ method uses a slightly smaller number of search points than the M1BT method. This is because some of the candidate search points in the ${\mathrm{DM}1\mathrm{BT}}_{2}$ method go beyond the boundary of the frame when ${d}_{1}$ and ${d}_{2}$ are large.

As expected, we can see that the DM1BT method, which is based on both techniques, not only decreases the number of search points, but also improves the PSNR performance. On average, the DM1BT method increases the PSNR of M1BT by 0.36dB and reduces the number of search points by 37.3%. It can also be seen that the hit rates of DM1BT (as compared with ${\mathrm{DM}1\mathrm{BT}}_{2}$) are very high although they are slightly smaller than the hit rates of ${\mathrm{DM}1\mathrm{BT}}_{1}$ (as compared with M1BT).

Finally, it should be mentioned that the proposed search scheme can be easily applied to other hybrid search methods, such as the M2BT5 and MC1BT6 methods, which also use two search centers and fixed search ranges. Table 3 compares the proposed DM2BT method with the conventional 2BT and M2BT methods, whereas Table 4 compares the proposed DMC1BT method with the conventional C1BT and MC1BT methods. As can be seen, the DM2BT and DMC1BT methods also efficiently enhance the conventional M2BT and MC1BT methods in terms of both PSNR performance and computational complexity.

## Table 3

Comparison with the 2BT and M2BT methods.

Video sequence (format)2BTM2BTDM2BT1DM2BT2DM2BT
PSNR (dB)PSNR (dB)# of search pointsPSNR (dB)# of search pointsHit ratePSNR (dB)# of search pointsPSNR (dB)# of search pointsHit rate
Foreman (CIF)30.7131.34720,754 (100%)31.32453,415 (62.9%)99.1%31.39706,998 (98.1%)31.36445,867 (61.9%)98.3%
Bus (CIF)24.3524.52833,291 (100%)24.52523,829 (62.9%)98.6%24.66807,013 (96.8%)24.64508,556 (61.0%)96.9%
News (CIF)35.8836.35283,032 (100%)36.35209,693 (74.1%)99.7%36.38282,950 (100.0%)36.35209,653 (74.1%)99.5%
Football (CIF)24.3024.961,353,316 (100%)24.94813,979 (60.1%)96.7%25.251,317,692 (97.4%)25.19794,374 (58.7%)93.6%
Tempete (CIF)26.4126.621,306,869 (100%)26.62745,594 (57.1%)99.4%26.661,301,947 (99.6%)26.64743,050 (56.9%)98.8%
Carphone (QCIF)30.5130.90199,361 (100%)30.90128,967 (64.7%)97.8%30.97192,367 (96.5%)30.96124,952 (62.7%)98.7%

## Table 4

Comparison with the C1BT and MC1BT methods.

Video Sequence (Format)C1BTMC1BTDMC1BT1DMC1BT2DMC1BT
PSNR (dB)PSNR (dB)# of Search pointsPSNR (dB)# of Search pointsHit ratePSNR (dB)# of Search pointsPSNR (dB)# of Search pointsHit rate
Foreman (CIF)31.0231.40699,790 (100%)31.39442,384 (63.2%)99.3%31.62687,784 (98.3%)31.60435,762 (62.3%)98.4%
Bus (CIF)24.3524.48807,258 (100%)24.47508,174 (63.0%)99.1%24.69781,731 (96.8%)24.67492,953 (61.1%)97.7%
News (CIF)36.0936.43275,743 (100%)36.42206,088 (74.7%)99.8%36.49275,658 (100.0%)36.48206,042 (74.7%)99.6%
Football (CIF)24.0224.611,350,827 (100%)24.60823,101 (60.9%)97.1%25.221,317,920 (97.6%)25.17804,675 (59.6%)93.7%
Tempete (CIF)26.4726.631,301,353 (100%)26.63744,666 (57.2%)99.5%26.671,296,774 (99.6%)26.67742,301 (57.0%)98.9%
Carphone (QCIF)30.2230.61196,581 (100%)30.61127,794 (65.0%)99.4%30.95188,765 (96.0%)30.94123,171 (62.7%)99.0%

## Conclusions

We proposed a new low-complexity block motion estimation method. Using the fact that the two search centers are closely located in most cases, the proposed method significantly reduces the number of search points and hence the overall complexity. It also improves the PSNR performance by using an adaptive search scheme based on the motion vector information of the co-located macroblock. The proposed search scheme can be easily applied to many hybrid motion estimation methods.

## Acknowledgments

This research was supported by the Chung-Ang University excellent freshman scholarship grants in 2012, the Ministry of Knowledge Economy (MKE), Korea, under the Information Technology Research Center support program (NIPA-2012-H0301-12-4004) supervised by the National IT Industry Promotion Agency, and the Human Resources Development of the Korea Institute of Energy Technology Evaluation and Planning grant funded by the Korea government MKE (No. 20104010100570).

## References

1.

B. NatarajanV. BhaskaranK. Konstantinides, “Low-complexity block-based motion estimation via one-bit transform,” IEEE Trans. Circ. Syst. Video Tech. 7(4), 702–706 (1997).ITCTEM1051-8215http://dx.doi.org/10.1109/76.611181Google Scholar

2.

A. ErtürkS. Ertürk, “Two-bit transform for binary block motion estimation,” IEEE Trans. Circ. Syst. Video Tech. 15(7), 938–946 (2005).ITCTEM1051-8215http://dx.doi.org/10.1109/TCSVT.2005.848340Google Scholar

3.

O. Urhan, “Constrained one-bit transform for low complexity block motion estimation,” IEEE Trans. Circ. Syst. Video Tech. 17(4), 478–482 (2007).ITCTEM1051-8215http://dx.doi.org/10.1109/TCSVT.2007.893828Google Scholar

4.

P. H. W. WongO. C. Au, “Modified one-bit transform for motion estimation,” IEEE Trans. Circ. Syst. Video Tech. 9(7), 1020–1024 (1999).ITCTEM1051-8215http://dx.doi.org/10.1109/76.795055Google Scholar

5.

B. DemirS. Ertürk, “Block motion estimation using modified two-bit transform,” Lect. Notes Comput. Sci. 4263, 522–531 (2006).LNCSD90302-9743http://dx.doi.org/10.1007/11902140Google Scholar

6.

H. Y. Ohet al., “Modified constrained one-bit transform based fast block motion estimation,” IEEE Trans. Consum. Electron. 53(3), 1093–1097 (2007).ITCEDA0098-3063http://dx.doi.org/10.1109/TCE.2007.4341590Google Scholar

7.

O. Urhan, “Constrained one-bit transform-based motion estimation using predictive hexagonal pattern,” J. Electron. Imag. 16(3), 033019 (2007).JEIME51017-9909http://dx.doi.org/10.1117/1.2769321Google Scholar

8.

S. Ertürk, “Multiplication-free one-bit transform for low-complexity block-based motion estimation,” IEEE Signal Proc. Lett. 14(2), 109–112 (2007).IESPEJ1070-9908http://dx.doi.org/10.1109/LSP.2006.882088Google Scholar

## Biography

Sojeong Lim received her BS degree in electrical and electronics engineering from Chung-Ang University, Seoul, Korea in 2012. She is currently working toward an MS degree in electrical and electronics engineering from Chung-Ang University. Her research interests include video compression algorithms for H.264/AVC and HEVC.

Jungwoo Kim received his BS degree in electrical and electronics engineering from Chung-Ang University, Seoul, Korea in 2012. He is currently working toward an MS degree in electrical and electronics engineering from Chung-Ang University. His research interests include video compression algorithms for H.264/AVC and HEVC.

Sungwook Yu received his BS degree in electrical engineering from Seoul National University, Seoul, Korea, in 1992. He received his MS and PhD degrees in electrical and computer engineering from the University of Texas at Austin, in 1996 and 2000, respectively. From 1999 to 2000, he worked at SiLogiX in Austin, TX, and from 2000 to 2004, he worked at Intel Corp. in Austin, TX. He worked for a year at Samsung Semiconductor Inc. in Korea before joining the faculty of electrical and electronics engineering department in Chung-Ang University, Seoul, Korea in 2005. His research interests are in the area of ASIC design for image and video processing applications.

Sojeong Lim, Jungwoo Kim, Sungwook Yu, "Modified one-bit transform method with dynamic search range," Journal of Electronic Imaging 22(2), 023001 (8 April 2013). http://dx.doi.org/10.1117/1.JEI.22.2.023001
JOURNAL ARTICLE
6 PAGES

SHARE
KEYWORDS
Motion estimation

Image filtering

Video

Information technology

Binary data

Computer simulations

Motion measurement

##### Show All Keywords
RELATED CONTENT

Comparing-block-matching-algorithms
Proceedings of SPIE (August 30 2002)