C.-M.Song et aL Signal Processing:Image Communication 28 (2013)1435-1447 1439 simplify Eq.(13)to 2 256 - Mj(g) (15) From Eq.(15).T;is closely related to weights of the corresponding intervals.Large difference between Zj-1 and IZjl (suppose Zj-1>Z)indicates that the numbers T T of pixel values locating in Zj-1 and Z vary considerably. The probability is high that the pixel values within a Fig.1.General view of membership function. certain distance from threshold T belong to Zi.since these pixel values are much probably partitioned into Zi_1 due to noises.Hence,the T"should be moved toward Ti-1 from Tj.Based on this inference,we propose to adaptively 4.2.Initial threshold refinement refine T according to Zil.The procedure is shown in Algorithm 2. Upon defining the membership function,the optimum interval partitioning corresponds to (Ti....T)that Algorithm 2(Initial threshold refinement). maximizes 1.Set j=0. Mj(g)p(g)s.tTj-Tl≤Vo2+ (13) 2.f☑1≤2562/N.then let△=V02+后×256/ N-ZD/256/N=Vc2+1×(256-1Z1×N)/256, in which To=-1 and T>w =255.The last term in Eq.(13) IZ'jl=IZjl+A.Otherwise,set IZ'jl=IZjl.go to Step 4. constrains difference between (Tj}and (Tj).Otherwise, 3.Let j=j+1.If j=N.go to Step 4.Otherwise,go to (T;)may diverge from the suboptimal thresholds (Tj) Step 2. solved in Section 3.As we know about the normal 4.Let L=EilZ'jl.refine the length and threshold of distribution,nearly 70%of the random variation amplitude each interval by setting IZ'j=256 x IZ'jl/L,je is within one variance.Therefore,we seek T;around Ti in a 01,,2-1h.T0=-1,T2w=255,T=Ti-1+ range of one variance.In the following,we discuss our 1Z-1l-1,ie1,2,2w-1n. solution to Eq.(13)under two conditions. First,when p is the uniform distribution,p()can be In the Step 2 of the above algorithm,A is used to control extracted as a common factor from Eq.(13).Now,that Eq. (13)is maximum is equivalent to maximizing computational complexity.The small the 4 is,the less the complexity will be.Furthermore,(256/N-IZjD)/(256/N)= (256-lZ分×N/256 is to normalize△so that the length Mjg)st.T-T引≤Vo2+ (14) variation of each adjusted interval is within one variance j=1g=了-1+1 +as discussed in Eq.(13). The remaining question is how to compute2+ From Fig.1 we can find that the solution of Ti is the Since we assume the inter-frame noises are independent intersection of M and Mj+1.i.e..T.This tells us that of Me(x.y).we have=++where adr and o uniform quantization provides the optimal interval parti- denote separately the variances of pixel values in the tioning for uniform distribution,needing not to be refined. current and reference frames.respectively.We thus calcu- Second,p is non-uniform.Since most image pixels follow non-uniform distributions,video sequences are late a2+o匠by la2-o usually in this case.We could employ an optimization By substituting the computed (Ti]into Eqs.(1).(2)and method to resolve Eq.(14)for each frame.This will (3),we obtain the low bit-resolution representation B of consume considerable computational complexity.Here each frame.Before presenting our low complexity motion we present a compromise method for less computation. estimation approach on B.we discuss the computational Although the first condition can hardly be true for complexity of our bit transform. natural videos,its solution sheds a light on how to treat the second condition.The fundamental idea is to replace 4.3.Computational complexity of our bit transform p()of each interval using its average probability p so that Eq.(13)is transformed to a similar form to Eq.(14). Without particularly pointed out,addition and subtrac- Because T is computed by means of histogram equaliza- tion operations are generally called "addition"hereafter, tion,pixels'accumulate probability distribution in each and multiplication and division called "multiplication" Zi(ie(0,1.....2N-1))is approximately the same.Let The computational complexity of our proposed bit trans- Zil=Ti+1-Ti be the interval length.Then the smaller form depends on two steps. the Zil is,the higher its p will be.Furthermore,the interval First,histogram equalization.Assume that the size of length of a uniform distribution is 256/N,we thus use video frame is wx h pixels.Counting the histogram p of 256/(N x IZil)as a weight to roughly measure p and the current frame requires wx h additions.e can be4.2. Initial threshold refinement Upon defining the membership function, the optimum interval partitioning corresponds to fT″ 1; …; T″ 2N 1g that maximizes ∑ 2N j ¼ 1 ∑ T″ j g ¼ T″ j 1 þ1 MjðgÞpðgÞ s:t: jTj T″ j jr ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi s2 c þs2 d q ð13Þ in which T″ 0 ¼ 1 and T″ 2N ¼ 255. The last term in Eq. (13) constrains difference between fTjg and fT″ jg. Otherwise, fT″ jg may diverge from the suboptimal thresholds fTjg solved in Section 3. As we know about the normal distribution, nearly 70% of the random variation amplitude is within one variance. Therefore, we seek T″ j around Tj in a range of one variance. In the following, we discuss our solution to Eq. (13) under two conditions. First, when p is the uniform distribution, pðÞ can be extracted as a common factor from Eq. (13). Now, that Eq. (13) is maximum is equivalent to maximizing ∑ 2N j ¼ 1 ∑ T″ j g ¼ T″ j 1 þ1 MjðgÞ s:t: jTj T″ j jr ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi s2 c þs2 d q : ð14Þ From Fig. 1 we can find that the solution of T″ j is the intersection of Mj and Mjþ1, i.e., Tj. This tells us that uniform quantization provides the optimal interval parti￾tioning for uniform distribution, needing not to be refined. Second, p is non-uniform. Since most image pixels follow non-uniform distributions, video sequences are usually in this case. We could employ an optimization method to resolve Eq. (14) for each frame. This will consume considerable computational complexity. Here we present a compromise method for less computation. Although the first condition can hardly be true for natural videos, its solution sheds a light on how to treat the second condition. The fundamental idea is to replace pðÞ of each interval using its average probability p so that Eq. (13) is transformed to a similar form to Eq. (14). Because Tj is computed by means of histogram equaliza￾tion, pixels' accumulate probability distribution in each ZiðiAf0; 1;…; 2N 1gÞ is approximately the same. Let jZij ¼ Tiþ1 Ti be the interval length. Then the smaller the jZij is, the higher its p will be. Furthermore, the interval length of a uniform distribution is 256/N, we thus use 256=ðN jZijÞ as a weight to roughly measure p and simplify Eq. (13) to ∑ 2N j ¼ 1 256 ðTj Tj1ÞN ∑ T″ j g ¼ T″ j 1 þ1 Mjð Þ g 8 < : 9 = ;: ð15Þ From Eq. (15), T″ j is closely related to weights of the corresponding intervals. Large difference between jZj1j and jZjj (suppose jZj1j4jZjj) indicates that the numbers of pixel values locating in Zj1 and Zj vary considerably. The probability is high that the pixel values within a certain distance from threshold Tj belong to Zj, since these pixel values are much probably partitioned into Zj1 due to noises. Hence, the T″j should be moved toward Tj1 from Tj. Based on this inference, we propose to adaptively refine Tj according to jZij. The procedure is shown in Algorithm 2. Algorithm 2 (Initial threshold refinement). 1. Set j¼0. 2. If jZjjr256λ=N, then let Δ ¼ ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi s2 c þs2 d q ð256= NjZjjÞ=ð256=NÞ ¼ ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi s2 c þs2 d q ð256jZjj NÞ=256, jZ′jj¼jZjjþΔ. Otherwise, set jZ′jj¼jZjj, go to Step 4. 3. Let j ¼ jþ1. If j¼N, go to Step 4. Otherwise, go to Step 2. 4. Let L ¼ ∑jjZ′jj, refine the length and threshold of each interval by setting jZ′jj ¼ 256 jZ′jj=L, jA f0; 1; …; 2N 1g, T″ 0 ¼ 1, T″ 2N ¼ 255, T″ i ¼ T″ i1 þ jZ′i1j1, iAf1; 2; …; 2N 1gÞ. In the Step 2 of the above algorithm, λ is used to control computational complexity. The small the λ is, the less the complexity will be. Furthermore, ð256=NjZjjÞ=ð256=NÞ ¼ ð256jZjj NÞ=256 is to normalize Δ so that the length variation of each adjusted interval is within one variance ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi s2 c þs2 d q , as discussed in Eq. (13). The remaining question is how to compute ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi s2 c þs2 d q . Since we assume the inter-frame noises are independent of Mcðx; yÞ, we have s2 rf ¼ s2 c þs2 d þs2 cf where s2 cf and s2 rf denote separately the variances of pixel values in the current and reference frames. respectively. We thus calcu￾late ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi s2 c þs2 d q by ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi js2 cf s2 rf j q . By substituting the computed fT″ jg into Eqs. (1), (2) and (3), we obtain the low bit-resolution representation B of each frame. Before presenting our low complexity motion estimation approach on B, we discuss the computational complexity of our bit transform. 4.3. Computational complexity of our bit transform Without particularly pointed out, addition and subtrac￾tion operations are generally called “addition” hereafter, and multiplication and division called “multiplication”. The computational complexity of our proposed bit trans￾form depends on two steps. First, histogram equalization. Assume that the size of video frame is w h pixels. Counting the histogram p of the current frame requires w h additions. e can be Fig. 1. General view of membership function. C.-M. Song et al. / Signal Processing: Image Communication 28 (2013) 1435–1447 1439