1438 C.-M.Song et aL Signal Processing:Image Communication 28(2013)1435-1447 this is unpractical with respect to the computational may have Me(x,y)>Tj and Mc(x,y≤Ti,orMc(xy)≤T complexity. and Mc(x.y)>Tj.At this moment,Me(x,y)and Mc(x.y)will As we know,the uniform quantization is the optimum be mapped to different intervals and produce matching quantizer if a signal's PDF is a uniform distribution.This errors.For low bit-resolution motion estimation,the match- conclusion enlightens us on an efficient solution to the ing error of a pixel is usually small.For example,the interval partitioning.Provided that we can find a trans- maximum matching error is just four in the case of two- form e from g to a random variable g'e (0.1,2.....255) bit motion estimation.This indicates that an inaccurate satisfying g'~U(0,255),we will easily obtain the optimum interval mapping brings about 25%matching deviation at thresholds of g'.Afterwards,the interval partitioning of g least.Such a large deviation will inevitably lead to a false can be realized through inversely transforming the com- motion vector.In contrast,the maximum matching error of puted thresholds using e-1.Based on this idea,we present full bit-resolution motion estimation is 255,thus small our method below. matching error,e.g.one,takes up a negligible deviation. This is the reason why low bit-resolution motion estima- Algorithm 1 (Non-uniform interval partitioning). tion,especially one-or two-bit motion estimation,is sensitive to the threshold selection.To summarize,a bit 1.Calculate histogram p of the input frame. transform is unfavorable for motion estimation when ignor- 2.Employ histogram equalization to map g to g',namely ing inter-frame noises and pixel changes. e(g) 255×pk) (6) 4.1.Membership function 3.Uniformly quantize to obtain threshold To find optimum motion vectors,it is necessary to T=28-j-1. estimate the probability that each pixel value within a 4.Compute T by an inverse transform e-1,ie.. certain distance from initial threshold belongs to its Tj=e-1(T'j).Since e is not an one-to-one mapping. current interval.If the probability is low,modify the initial there does not exist an inverse transform.Here,we threshold such that each pixel value around it is positioned define e-1 as in the right interval.In our study.we use a membership e-1(T)=min(k)s.te(k≥T,k∈{0,1,2，，255 function to describe the probability of a pixel value (7) belonging to each interval. Definition.(T1,T2...Tw gives an initial interval par- After the non-uniform interval partitioning above, titioning of G.obtaining 2N intervals namely Zo.Z..... Eq.(5)is utilized again to compute (ri). Z2w_1 We define the probability that g is in Zj as member- Algorithm 1 is able to handle video frames obeying any ship whose value depends on a membership function.The PDF with low computational complexity.It should be membership function is described as follows: noted that,however,Algorithm 1 only offers a suboptimal solution because histogram equalization cannot produce M1(g) p(s)ds (9) an ideal uniform distribution for discrete pixel values. Substitute (ri)into Eq.(2).and combine it with Eq.(1). Then we map the current and reference frames to B,on M(g)=1 Pi1(s)ds. pi(s)ds. (10) which the low bit-resolution motion estimation is exe- cuted.Now,our bit transform still adopts a hard threshold- ing manner.But [35]observed that the hard thresholding M(g)= P2w(s)ds, (11) always leads to performance degradation.We will analyze the reason in the next subsection.Afterwards,we will where M(g)denotes the membership function.Py is the introduce a fuzzy logic into the bit transform. probability density function of Tj.which relates to inter- frame noises and video signal itself.In this study.we assume that the inter-frame noises are caused by camera 4.Threshold refinement using fuzzy logic capability and coding distortion,and they are independent Block-based motion estimation generally assumes that of each other and Mc(x,y).Since the light condition a pixel and its correspondence in a successive frame have changes between successive frames could be ignored,we the same value.Indeed,it is not the case.Due to camera do not take it into consideration.Further,suppose that the capability,coding distortion,light changes,etc.,the cur- noises due to camera capability and coding distortion rent macroblock is usually different from its best matched follow normal distributions,namely N(0,2)and N(O,) macroblock.Let Me and M,be the macroblocks separately in respectively.then we define py as current and reference frames,respectively.M denotes the 1 6-T)2 optimal prediction of the current macroblock.Then we have Pi(S)= exp (12) 2(c2+o) 2(c2+) M=M(x+u.y+v)=Mc(x.y)+n(x.y). (8) Fig.1 depicts the membership function in the case of N=4. where (u,v)and n(,)are motion vector and random noises, Note that different probability density functions can also respectively.Under this condition,M(x,y)Mc(x,y)holds be accepted for different Ti according to the application for most pixels(xy).If we employ a hard threshold T.we scenarios.this is unpractical with respect to the computational complexity. As we know, the uniform quantization is the optimum quantizer if a signal's PDF is a uniform distribution. This conclusion enlightens us on an efficient solution to the interval partitioning. Provided that we can find a trans￾form e from g to a random variable g′Af0; 1; 2; …; 255g satisfying g′  Uð0; 255Þ, we will easily obtain the optimum thresholds of g′. Afterwards, the interval partitioning of g can be realized through inversely transforming the com￾puted thresholds using e1 . Based on this idea, we present our method below. Algorithm 1 (Non-uniform interval partitioning). 1. Calculate histogram p of the input frame. 2. Employ histogram equalization to map g to g′, namely eðgÞ ¼ ∑ g k ¼ 0 255 pðkÞ $ %: ð6Þ 3. Uniformly quantize g′ to obtain threshold T′j ¼ 28Nj1. 4. Compute Tj by an inverse transform e1, i.e., Tj ¼ e1ðT′jÞ. Since e is not an one-to-one mapping, there does not exist an inverse transform. Here, we define e1 as e1ðT′jÞ ¼ minfkg s:t: eðkÞZT′j; kAf0; 1; 2; …; 255g: ð7Þ After the non-uniform interval partitioning above, Eq. (5) is utilized again to compute frig. Algorithm 1 is able to handle video frames obeying any PDF with low computational complexity. It should be noted that, however, Algorithm 1 only offers a suboptimal solution because histogram equalization cannot produce an ideal uniform distribution for discrete pixel values. Substitute frig into Eq. (2), and combine it with Eq. (1). Then we map the current and reference frames to B, on which the low bit-resolution motion estimation is exe￾cuted. Now, our bit transform still adopts a hard threshold￾ing manner. But [35] observed that the hard thresholding always leads to performance degradation. We will analyze the reason in the next subsection. Afterwards, we will introduce a fuzzy logic into the bit transform. 4. Threshold refinement using fuzzy logic Block-based motion estimation generally assumes that a pixel and its correspondence in a successive frame have the same value. Indeed, it is not the case. Due to camera capability, coding distortion, light changes, etc., the cur￾rent macroblock is usually different from its best matched macroblock. Let Mc and Mr be the macroblocks separately in current and reference frames, respectively. M^ n c denotes the optimal prediction of the current macroblock. Then we have M^ n c ¼ Mrðxþu; yþvÞ ¼ Mcðx; yÞþnðx; yÞ; ð8Þ where (u,v) and nð; Þ are motion vector and random noises, respectively. Under this condition, M^ n c ðx; yÞaMcðx; yÞ holds for most pixels (x,y). If we employ a hard threshold Tj, we may have M^ n c ðx; yÞ4Tj and Mcðx; yÞrTj, or M^ n c ðx; yÞrTj and Mcðx; yÞ4Tj. At this moment, M^ n c ðx; yÞ and Mcðx; yÞ will be mapped to different intervals and produce matching errors. For low bit-resolution motion estimation, the match￾ing error of a pixel is usually small. For example, the maximum matching error is just four in the case of two￾bit motion estimation. This indicates that an inaccurate interval mapping brings about 25% matching deviation at least. Such a large deviation will inevitably lead to a false motion vector. In contrast, the maximum matching error of full bit-resolution motion estimation is 255, thus small matching error, e.g., one, takes up a negligible deviation. This is the reason why low bit-resolution motion estima￾tion, especially one- or two-bit motion estimation, is sensitive to the threshold selection. To summarize, a bit transform is unfavorable for motion estimation when ignor￾ing inter-frame noises and pixel changes. 4.1. Membership function To find optimum motion vectors, it is necessary to estimate the probability that each pixel value within a certain distance from initial threshold belongs to its current interval. If the probability is low, modify the initial threshold such that each pixel value around it is positioned in the right interval. In our study, we use a membership function to describe the probability of a pixel value belonging to each interval. Definition. fT1; T2;…; T2N 1g gives an initial interval par￾titioning of G, obtaining 2N intervals namely Z0, Z1, …, Z2N 1. We define the probability that g is in Zj as member￾ship whose value depends on a membership function. The membership function is described as follows: M1ðgÞ ¼ Z þ1 g p1ðsÞ ds; ð9Þ MjðgÞ ¼ 1 Z þ1 g pj1ðsÞ ds Z g 1 pjðsÞ ds; ð10Þ M2N ðgÞ ¼ Z g 1 p2N 1ðsÞ ds; ð11Þ where Mi(g) denotes the membership function. pj is the probability density function of Tj, which relates to inter￾frame noises and video signal itself. In this study, we assume that the inter-frame noises are caused by camera capability and coding distortion, and they are independent of each other and Mcðx; yÞ. Since the light condition changes between successive frames could be ignored, we do not take it into consideration. Further, suppose that the noises due to camera capability and coding distortion follow normal distributions, namely Nð0; s2 c Þ and Nð0; s2 dÞ, respectively, then we define pj as pjð Þ¼s 1 ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi 2πðs2 c þs2 dÞ q exp ðsTjÞ 2 2ðs2 c þs2 dÞ " #: ð12Þ Fig. 1 depicts the membership function in the case of N¼4. Note that different probability density functions can also be accepted for different Tj according to the application scenarios. 1438 C.-M. Song et al. / Signal Processing: Image Communication 28 (2013) 1435–1447