C.-M.Song et aL Signal Processing:Image Communication 28 (2013)1435-1447 1437 combined depending on the pixel distributions,instead of Divide f into two steps,namely interval partitioning independently used. t:G-G.gr and interval mapping m:G-B.rb,and The third approach is quantization.Lee et al.[40,41] then we have f(g)=m(t(g)).i.e.. utilized an adaptive quantization to implement a two-bit transform.Ertuirk and Erturk [4,42,53]proposed a multi- T1, -1<g≤T1 thresholding with mean value and approximated standard r2, T1<g≤T2 deviation.Furthermore,Kim et al.[54,55]made use of t(g)= r3. T2<g≤T3 (1) positive and negative second derivatives to improve [4,42,53].Wang et al.[48]selected a low-pass filtered T2"-1<g≤255 version of the current frame as a mid point,and then applied a uniform quantization with a pre-defined step and size to accomplish the bit transform. Both truncation and quantization approaches can be 0, r=r used for bit transform whose resolution is more than one 1, r=r2 bit.Their computational complexity is obviously lower m(r)= r=r3 (2) than that of the filtering approach.Moreover,the trunca- tion is equivalent to a uniform quantization in essence.The 2 T=Tw quantization thus provides an efficient strategy for bit transform The interval partitioning is a many-to-one mapping,while However,current quantization based methods compute the interval mapping is a one-to-one mapping.Hence the thresholds on macroblock basis.Since a search window former decides the threshold selection as well as motion compasses several macroblocks,the low bit-resolution estimation performance.To preserve as much important reference tends to display discontinuities along two adja- information as possible in the low bit-resolution repre- cent blocks if different thresholds are selected [32].The sentation,we need to find an optimal mapping t that motion estimation accuracy will be influenced by the minimizes blocking artifact.Even if a uniform threshold is adopted by the truncation-based approach,it cannot adapt to scene 255 D=Eg-tg)》]=∑pg)g-tg (3) changes and would fail to provide a fine grain scratch for low bit-resolution motion estimation. in which Ef.]and p()denote expectation operator and On the other hand,state-of-art bit transforms adopt a hard thresholding manner which regards pixel values probability distribution function (PDF)of pixel values, respectively.However,finding t is equivalent to simulta- lying on the opposite sides of the threshold as a mismatch even if their values are close.Because of camera noises, neously determining an optimal set of r and non-translational motion,quantization errors during cod- Tj(ie(1.2,....2N).je(1.2.....2N-1)).This is a nonlinear ing.etc..there always exist differences between two best problem and cannot be solved with any ease. matched macroblocks [63].Consequently,hard threshold- Assume that g is a discrete random variable whose PDF ing would take the best pair as a mismatch.Urhan et al. is p.As we know,optimum scalar quantization is to decide a set of thresholds and quanta that minimizes reconstruc- 35,36]counted the pixel values away from threshold tion errors.It has the same issue with interval partitioning. within a certain distance D as a match regardless of their This motivates us to recourse quantization theory to solve values.But they neglected adjusting D to video character- istics.Large D will ignore the pixel differences that should Egs.(1)and(3).According to the quantization theory.a have excluded invalid candidate vectors.On the contrary. uniform quantizer yields better approximation than a non- small D cannot resist inter-frame noises and is not able to uniform one at high resolution [64].and vice versa.We thus adopt different strategies to accomplish the interval avoid an improper match. In general,little attention has been payed to an adap- partitioning depending on the bit-resolution. In the case that bit-resolution is higher than a threshold tive uniform thresholding and its mechanism to deal with R,we use a set of uniform thresholds to define Ti as inter-frame noises,even though they will definitely con- tribute to performance improvement. T=28-Nj-1. (4) 3.A bit transform based on quantization Set To=-1,then we have ri=[(Ti+Ti-1)/2]. (5) Motion estimation with low bit-resolution is always inferior to that with full bit-resolution in terms of motion- When bit-resolution is lower than R,non-uniform compensated quality.The main reason is that the bit thresholds are employed.Max [65]and Lloyd [66]ever transform leads to a data loss.It is therefore crucial to proposed iterative trial-and-error procedures to adaptively reserve as much information of full resolution video as compute non-uniform quantization steps.They also gave a possible.In this section,we present a quantization based list of parameters for signals following uniform,Gaussian, bit transform to address this issue. and Laplacian distributions.Unfortunately,hardly video SetG={0,1,2,,2551.B={0,1,2,,2w-1.Then the signals obey any explicit and identical probability distribu- bit transform mapping eight-bit values to those with N bit- tion.This forces us to run their methods frame-wise resolution can be formalized by a map f:G-B.gb. to assign optimum thresholds for each frame.Obviously.combined depending on the pixel distributions, instead of independently used. The third approach is quantization. Lee et al. [40,41] utilized an adaptive quantization to implement a two-bit transform. Ertürk and Ertürk [4,42,53] proposed a multi￾thresholding with mean value and approximated standard deviation. Furthermore, Kim et al. [54,55] made use of positive and negative second derivatives to improve [4,42,53]. Wang et al. [48] selected a low-pass filtered version of the current frame as a mid point, and then applied a uniform quantization with a pre-defined step size to accomplish the bit transform. Both truncation and quantization approaches can be used for bit transform whose resolution is more than one bit. Their computational complexity is obviously lower than that of the filtering approach. Moreover, the trunca￾tion is equivalent to a uniform quantization in essence. The quantization thus provides an efficient strategy for bit transform. However, current quantization based methods compute thresholds on macroblock basis. Since a search window compasses several macroblocks, the low bit-resolution reference tends to display discontinuities along two adja￾cent blocks if different thresholds are selected [32]. The motion estimation accuracy will be influenced by the blocking artifact. Even if a uniform threshold is adopted by the truncation-based approach, it cannot adapt to scene changes and would fail to provide a fine grain scratch for low bit-resolution motion estimation. On the other hand, state-of-art bit transforms adopt a hard thresholding manner which regards pixel values lying on the opposite sides of the threshold as a mismatch even if their values are close. Because of camera noises, non-translational motion, quantization errors during cod￾ing, etc., there always exist differences between two best matched macroblocks [63]. Consequently, hard threshold￾ing would take the best pair as a mismatch. Urhan et al. [35,36] counted the pixel values away from threshold within a certain distance D as a match regardless of their values. But they neglected adjusting D to video character￾istics. Large D will ignore the pixel differences that should have excluded invalid candidate vectors. On the contrary, small D cannot resist inter-frame noises and is not able to avoid an improper match. In general, little attention has been payed to an adap￾tive uniform thresholding and its mechanism to deal with inter-frame noises, even though they will definitely con￾tribute to performance improvement. 3. A bit transform based on quantization Motion estimation with low bit-resolution is always inferior to that with full bit-resolution in terms of motion￾compensated quality. The main reason is that the bit transform leads to a data loss. It is therefore crucial to reserve as much information of full resolution video as possible. In this section, we present a quantization based bit transform to address this issue. Set G ¼ f0; 1; 2;…; 255g, B ¼ f0; 1; 2; …; 2N 1g. Then the bit transform mapping eight-bit values to those with N bit￾resolution can be formalized by a map f : G-B, g↦b. Divide f into two steps, namely interval partitioning t : G-G, g↦r and interval mapping m : G-B, r↦b, and then we have fðgÞ ¼ mðtðgÞÞ, i.e., tðgÞ ¼ r1; 1ogrT1 r2; T1ogrT2 r3; T2ogrT3 ⋮ r2N ; T2N 1ogr255 8 >>>>>>< >>>>>>: ; ð1Þ and mðrÞ ¼ 0; r ¼ r1 1; r ¼ r2 2; r ¼ r3 ⋮ 2N 1; r ¼ r2N 8 >>>>>>< >>>>>>: : ð2Þ The interval partitioning is a many-to-one mapping, while the interval mapping is a one-to-one mapping. Hence the former decides the threshold selection as well as motion estimation performance. To preserve as much important information as possible in the low bit-resolution repre￾sentation, we need to find an optimal mapping t that minimizes D ¼ E½ðgtðgÞÞ2 ¼ ∑ 255 g ¼ 0 pðgÞ½gtðgÞ2; ð3Þ in which E½ and pðÞ denote expectation operator and probability distribution function (PDF) of pixel values, respectively. However, finding t is equivalent to simulta￾neously determining an optimal set of ri and TjðiAf1; 2;…; 2Ng; jAf1; 2; …; 2N 1gÞ. This is a nonlinear problem and cannot be solved with any ease. Assume that g is a discrete random variable whose PDF is p. As we know, optimum scalar quantization is to decide a set of thresholds and quanta that minimizes reconstruc￾tion errors. It has the same issue with interval partitioning. This motivates us to recourse quantization theory to solve Eqs. (1) and (3). According to the quantization theory, a uniform quantizer yields better approximation than a non￾uniform one at high resolution [64], and vice versa. We thus adopt different strategies to accomplish the interval partitioning depending on the bit-resolution. In the case that bit-resolution is higher than a threshold R, we use a set of uniform thresholds to define Tj as Tj ¼ 28Nj1: ð4Þ Set T0 ¼ 1, then we have ri ¼ ⌊ðTi þTi1Þ=2⌋: ð5Þ When bit-resolution is lower than R, non-uniform thresholds are employed. Max [65] and Lloyd [66] ever proposed iterative trial-and-error procedures to adaptively compute non-uniform quantization steps. They also gave a list of parameters for signals following uniform, Gaussian, and Laplacian distributions. Unfortunately, hardly video signals obey any explicit and identical probability distribu￾tion. This forces us to run their methods frame-wise to assign optimum thresholds for each frame. Obviously, C.-M. Song et al. / Signal Processing: Image Communication 28 (2013) 1435–1447 1437