1436 C-M.Song et aL Signal Processing:Image Communication 28 (2013)1435-1447 Various fast algorithms have been proposed so far to quantization based motion estimation is discussed in lower motion estimation cost.They can be roughly classi- Section 5.We examine the proposed approach in Section 6 fied into four categories. and conclude the paper in the last section. The first category of algorithms searches for motion vector in a subset of possible candidate vectors,reducing the number of search locations per macroblock.Represen- 2.Related works tative algorithms include three-step search [6].diamond search [7].cross-diamond-hexagonal search [8],hexagon- A considerable amount of research has been done on based search [9],unsymmetrical-cross multi-hexagon-grid bit transforms during the last decade.State-of-the-art search [5.motion estimation using dynamic models [10. transforms are mainly based on three approaches. adaptive neighborhood elimination algorithm [11].adap- The first approach is filtering.Feng et al.25 trans- tive motion search range prediction [12].and fast sub- formed an eight-bit pixel to its one-bit representation by pixel motion estimation 13. comparing the pixel against the mean value.Mizuki et al. The main concept of the second category is to compute [26,27]obtained the binary representation by an edge matching errors using a fraction of pixels,reducing operation detection procedure.Natarajan et al.[28,52,38]employed number per matching.Typical algorithms involve partial a 2-D multi-bandpass filter of size 17 x 17 to implement distortion search [14],multiresolution motion estimation the one-bit transform.Erturk et al.[29-31,33]proposed a [15-17],block matching with an adaptive pattern [18,191. novel filter kernel using shift operation instead of multi- and advanced spatial hierarchical motion estimation[20. plication in [28].Lee et al.[37,39,49-51]detected a zero- Low-complexity matching metrics are the core of the cross phase with mean as the DC bias and used the binary third category.Commonly used matching metrics include phase deviation as the bit transform result.Luo et al.[34] sum of absolute differences(SAD).pel difference classifi- proposed a linear and symmetric filter to better register cation (PDC)[21],minimized maximum error(MiniMax) average spatial characteristics and to facilitate a more [22].different pixel counts(DPC).bit exclusive-OR(BXOR) accurate binary representation.Although many improve- [23].and mean-predicted sum of absolute differences [24]. ments have been contributed,these algorithms always The fourth category of algorithms performs motion involve convolution operations and high computational estimation on low bit-resolution pixels whose values are overhead as a result. mapped to from eight bit-resolution pixels [25-61].These Some studies exploit frequency-domain techniques for algorithms contribute to simple hardware implementa- less computation.Wu et al.[32]presented a gradient- tion,low power consumption,and memory bandwidth. based thresholding in the discrete cosine transform(DCT) A cost-effective and real-time video codec can thus be domain.As video coders always work in the DCT domain. realized on a low-power device with limited capabilities. this method incurs little overhead.Erturk et al.[47]carried In this study.we focus on the last category of algo- out the binarization in wavelet domain by only retaining rithms,considering their potential in computational cap- filtered lowest frequency coefficients. ability constraint devices.Our main contribution is a bit Another limitation of filtering-based bit transforms is transform method which maps eight-bit values to those that they are only adequate for one-bit motion estimation. with lower bit-resolution.It is the crucial component of In the case of higher bit-resolution,the filtering is required low bit-resolution motion estimation,determining the executing for multiple times. codec performance.We first formalize bit transform by The second approach is pixel truncation.Baek et al.43 interval partitioning and interval mapping.Through presented a criterion,named reduced bits mean absolute exploiting quantization theory,we then find an initial difference,which only uses the most n significant bits to solution to interval partitioning.To resolve false partition- compute the matching errors when the bit-resolution is n. ing caused by inter-frame noises,a membership function is He et al.44,57,60,59,58 truncated the least significant employed to refine the initial thresholds. bits to realize the pixel resolution reduction.The number Our approach has the following benefits: of truncated bits can be fixed or adaptively defined. Nevertheless,Patras et al.[62]stated that motion- 1.Bit transform is bound to result in pixels'accuracy loss compensated differences follow an independent Laplacian as well as performance degradation of motion estima- distribution.It indicates that the matching errors always tion.Addressing bit transform by quantization enables occur on insignificant bits.If these bits are truncated, us to better utilize existing theory.This facilitates pixels in the area around the best-matched macroblock reducing as much accuracy loss as possible so as to could be converted into the same low-resolution values. guarantee motion estimation efficiency. The resulting matching errors corresponding to all candi- 2.Membership function achieves good robustness to date vectors in this area will be a constant,disabled from coding distortions,camera noises,etc.It can effectively distinguishing the optimal motion vector.Moshnyaga61 eliminate the mismatch due to hard thresholding.and addressed this issue by adaptively truncating the most improve prediction quality of complex videos with high significant bits according to the data variation. spatial details or fast motion. Truncating the least significant bits tends to influence the motion estimation performance for sequences with The remainder of this paper is organized as follows. low spatial detail or low amount of movement,and vice Section 2 gives an overview of previous works.Sections 3 versa.Therefore,the least significant bit truncation and and 4 describe the fuzzy quantization approach.A fuzzy the most significant bit truncation should be skillfullyVarious fast algorithms have been proposed so far to lower motion estimation cost. They can be roughly classi￾fied into four categories. The first category of algorithms searches for motion vector in a subset of possible candidate vectors, reducing the number of search locations per macroblock. Represen￾tative algorithms include three-step search [6], diamond search [7], cross-diamond-hexagonal search [8], hexagon￾based search [9], unsymmetrical-cross multi-hexagon-grid search [5], motion estimation using dynamic models [10], adaptive neighborhood elimination algorithm [11], adap￾tive motion search range prediction [12], and fast sub￾pixel motion estimation [13]. The main concept of the second category is to compute matching errors using a fraction of pixels, reducing operation number per matching. Typical algorithms involve partial distortion search [14], multiresolution motion estimation [15–17], block matching with an adaptive pattern [18,19], and advanced spatial hierarchical motion estimation [20]. Low-complexity matching metrics are the core of the third category. Commonly used matching metrics include sum of absolute differences (SAD), pel difference classifi￾cation (PDC) [21], minimized maximum error (MiniMax) [22], different pixel counts (DPC), bit exclusive-OR (BXOR) [23], and mean-predicted sum of absolute differences [24]. The fourth category of algorithms performs motion estimation on low bit-resolution pixels whose values are mapped to from eight bit-resolution pixels [25–61]. These algorithms contribute to simple hardware implementa￾tion, low power consumption, and memory bandwidth. A cost-effective and real-time video codec can thus be realized on a low-power device with limited capabilities. In this study, we focus on the last category of algo￾rithms, considering their potential in computational cap￾ability constraint devices. Our main contribution is a bit transform method which maps eight-bit values to those with lower bit-resolution. It is the crucial component of low bit-resolution motion estimation, determining the codec performance. We first formalize bit transform by interval partitioning and interval mapping. Through exploiting quantization theory, we then find an initial solution to interval partitioning. To resolve false partition￾ing caused by inter-frame noises, a membership function is employed to refine the initial thresholds. Our approach has the following benefits: 1. Bit transform is bound to result in pixels' accuracy loss as well as performance degradation of motion estima￾tion. Addressing bit transform by quantization enables us to better utilize existing theory. This facilitates reducing as much accuracy loss as possible so as to guarantee motion estimation efficiency. 2. Membership function achieves good robustness to coding distortions, camera noises, etc. It can effectively eliminate the mismatch due to hard thresholding, and improve prediction quality of complex videos with high spatial details or fast motion. The remainder of this paper is organized as follows. Section 2 gives an overview of previous works. Sections 3 and 4 describe the fuzzy quantization approach. A fuzzy quantization based motion estimation is discussed in Section 5. We examine the proposed approach in Section 6 and conclude the paper in the last section. 2. Related works A considerable amount of research has been done on bit transforms during the last decade. State-of-the-art transforms are mainly based on three approaches. The first approach is filtering. Feng et al. [25] trans￾formed an eight-bit pixel to its one-bit representation by comparing the pixel against the mean value. Mizuki et al. [26,27] obtained the binary representation by an edge detection procedure. Natarajan et al. [28,52,38] employed a 2-D multi-bandpass filter of size 17 17 to implement the one-bit transform. Ertürk et al. [29–31,33] proposed a novel filter kernel using shift operation instead of multi￾plication in [28]. Lee et al. [37,39,49–51] detected a zero￾cross phase with mean as the DC bias and used the binary phase deviation as the bit transform result. Luo et al. [34] proposed a linear and symmetric filter to better register average spatial characteristics and to facilitate a more accurate binary representation. Although many improve￾ments have been contributed, these algorithms always involve convolution operations and high computational overhead as a result. Some studies exploit frequency-domain techniques for less computation. Wu et al. [32] presented a gradient￾based thresholding in the discrete cosine transform (DCT) domain. As video coders always work in the DCT domain, this method incurs little overhead. Ertürk et al. [47] carried out the binarization in wavelet domain by only retaining filtered lowest frequency coefficients. Another limitation of filtering-based bit transforms is that they are only adequate for one-bit motion estimation. In the case of higher bit-resolution, the filtering is required executing for multiple times. The second approach is pixel truncation. Baek et al. [43] presented a criterion, named reduced bits mean absolute difference, which only uses the most n significant bits to compute the matching errors when the bit-resolution is n. He et al. [44,57,60,59,58] truncated the least significant bits to realize the pixel resolution reduction. The number of truncated bits can be fixed or adaptively defined. Nevertheless, Patras et al. [62] stated that motion￾compensated differences follow an independent Laplacian distribution. It indicates that the matching errors always occur on insignificant bits. If these bits are truncated, pixels in the area around the best-matched macroblock could be converted into the same low-resolution values. The resulting matching errors corresponding to all candi￾date vectors in this area will be a constant, disabled from distinguishing the optimal motion vector. Moshnyaga [61] addressed this issue by adaptively truncating the most significant bits according to the data variation. Truncating the least significant bits tends to influence the motion estimation performance for sequences with low spatial detail or low amount of movement, and vice versa. Therefore, the least significant bit truncation and the most significant bit truncation should be skillfully 1436 C.-M. Song et al. / Signal Processing: Image Communication 28 (2013) 1435–1447