1440 C-M.Song et aL Signal Processing:Image Communication 28 (2013)1435-1447 b metric is adopted.It can distinguish two situations only. 000⊕111 i.e,match and mismatch.Nevertheless,the number of matching situations is more than two when N>1.This implies that DPC cannot well exploit the information 1 011⊕100 provided by high bit-resolution pixels. 11⊕00 The BXOR metric was also researched [59,67].This metric can be regarded as an operation on two N-dimen- 10⊕01 sional vectors in a duality field(0,1,⊕，⑧)where“⊕" 00 10 and "denote "Exclusive-OR"and "AND"operations. Fig.2.Inaccurate matching evaluation by BXOR metric.(a)Two-bit BXOR respectively.Unfortunately,the output of BXOR does not metric.(b)Three-bit BXOR metric. completely conform to the real difference between the two pixel values.For example,if two pixels'representations are Table 1 separately "01"and "10",the metric output is "11"(Fig.2 Test video sequences and formats. (a))which means that their difference is three.Obviously. the correct difference equals one.In such a case,the BXOR Sequence name Format Resolution Frame rate(fps) metric cannot distinguish between(01,10)and(00.11). Flower CIF 352×288 30 Actually,(01,10)is a better match than (00,11).For three- Football CIF 352×288 30 bit matching.BXOR metric presents the same matter as Mobile CIF 352×288 30 shown in Fig.2(b). Paris CIF 352×288 30 We believe that SAD is still the accurate and efficient Stefan CIF 352×288 30 Tennis CIF 352×288 30 matching metric for low bit-resolution motion estimation. Tempete CIF 352×288 30 In our study.we adopt a bit-truncation SAD [23]defined as City 4CIF 704×576 30 s-1S-1 Crew 4CIF 704×576 30 h(u,v)= +N-1(x.y)-+N-1(x+u.y+v)l. Harbour 4CIF 704×576 30 X=0y=0 Carphone QCIF 176×144 30 (16 Grandma QCIF 176×144 30 in which Ic(,)and I(,)are separately pixel values of the current and reference frames.q:q+N-1 indicates that computed using 256 multiplications and 255 additions. operations are only executed on from the g-th to the Solving e-needs 255 comparison operations.Note that, (g+N-1)-th bit of each byte.On one hand,we could when N>R,the histogram equalization is not required,so store multiple pixel values in one byte,available for are the above operations. parallel processing.On the other hand,we are able to Second,threshold refinement.The mean value #c andr create a table in memory to save the matching errors of the current and reference frames are computed by total under all situations to realize metric (16)with low com- 2 x(w x h-1)additions.In order to calculate the variance putational cost.Using+N-1(x.y)and+N-1(x+u. r and f.2 x wx h multiplications and 2 x wx h addi- y+v)as an offset,we then employ the XLAT instruction tions are required.Furthermore,one addition,one abso- of the assembly language to locate the matching error in lute conversion,and one square root operations are the aforementioned table.This method requires less clock needed to obtain o+.Afterwards,Step 2 of cycles than sequentially performing subtraction and abso- lute conversion operations. Algorithm 2 executes at most 2N+additions and 2x (2N-1)+2 multiplications.Step 4 is composed of 3x 5.2.Fuzzy quantization based low bit-resolution motion (2N-1)additions and 2 x (2N-1)multiplications.In addi- estimation tion,quantizing each pixel needs at most (2N-1) comparisons. On the basis of the concept mentioned above,we present a low bit-resolution motion estimation approach 5.Low bit-resolution motion estimation based on fuzzy quantization.The current and reference frames are first processed by the bit transform proposed in This section first talks over the matching metric sui- Sections 3 and 4,respectively.Next,one of the conven- table for low bit-resolution motion estimation.A novel tional search strategies,e.g.full search,is applied for motion estimation approach is then developed. motion estimation using h as the matching metric.This approach is summarized in Algorithm 3. 5.1.Matching metric for low bit-resolution motion Algorithm 3 (Low bit-resolution motion estimation). estimation 1.Separately compute the mean pixel values #=Ellc]and An efficient matching metric is one of the important r=E[lr]of the current and reference frames,and their components for motion estimation.Bahari et al.59 found variance od E[l2]-E [lc]and =E[F]-E[l]. that DPC and BXOR metrics show good performance in the 2.Carry out the histogram equalization (see Eq.(6))on low bit-resolution motion estimation.Among most low reference frame to obtain g'. bit-resolution motion estimation algorithms,the DPC 3.Uniformly quantize g'and determine (T'j).computed using 256 multiplications and 255 additions. Solving e1 needs 255 comparison operations. Note that, when NZR, the histogram equalization is not required, so are the above operations. Second, threshold refinement. The mean value μc and μr of the current and reference frames are computed by total 2 ðw h1Þ additions. In order to calculate the variance s2 cf and s2 rf , 2 w h multiplications and 2 w h addi￾tions are required. Furthermore, one addition, one abso￾lute conversion, and one square root operations are needed to obtain ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi s2 c þs2 d q . Afterwards, Step 2 of Algorithm 2 executes at most 2ðN þ1Þ additions and 2 ð2N 1Þþ2 multiplications. Step 4 is composed of 3 ð2N 1Þ additions and 2 ð2N 1Þ multiplications. In addi￾tion, quantizing each pixel needs at most ð2N 1Þ comparisons. 5. Low bit-resolution motion estimation This section first talks over the matching metric sui￾table for low bit-resolution motion estimation. A novel motion estimation approach is then developed. 5.1. Matching metric for low bit-resolution motion estimation An efficient matching metric is one of the important components for motion estimation. Bahari et al. [59] found that DPC and BXOR metrics show good performance in the low bit-resolution motion estimation. Among most low bit-resolution motion estimation algorithms, the DPC metric is adopted. It can distinguish two situations only, i.e, match and mismatch. Nevertheless, the number of matching situations is more than two when N41. This implies that DPC cannot well exploit the information provided by high bit-resolution pixels. The BXOR metric was also researched [59,67]. This metric can be regarded as an operation on two N-dimen￾sional vectors in a duality field ðf0; 1g; ;  Þ where “” and “” denote “Exclusive-OR” and “AND” operations, respectively. Unfortunately, the output of BXOR does not completely conform to the real difference between the two pixel values. For example, if two pixels' representations are separately “01” and “10”, the metric output is “11” (Fig. 2 (a)) which means that their difference is three. Obviously, the correct difference equals one. In such a case, the BXOR metric cannot distinguish between (01, 10) and (00, 11). Actually, (01, 10) is a better match than (00, 11). For three￾bit matching, BXOR metric presents the same matter as shown in Fig. 2(b). We believe that SAD is still the accurate and efficient matching metric for low bit-resolution motion estimation. In our study, we adopt a bit-truncation SAD [23] defined as hðu; vÞ ¼ ∑ S1 x ¼ 0 ∑ S1 y ¼ 0 jI q:qþN 1 c ðx; yÞI q:qþN 1 r ðxþu; yþvÞj; ð16Þ in which Icð; Þ and Irð; Þ are separately pixel values of the current and reference frames. q : qþN1 indicates that operations are only executed on from the q-th to the ðqþN1Þth bit of each byte. On one hand, we could store multiple pixel values in one byte, available for parallel processing. On the other hand, we are able to create a table in memory to save the matching errors under all situations to realize metric (16) with low com￾putational cost. Using I q:qþN 1 c ðx; yÞ and I q:qþN 1 r ðxþu; yþvÞ as an offset, we then employ the XLAT instruction of the assembly language to locate the matching error in the aforementioned table. This method requires less clock cycles than sequentially performing subtraction and abso￾lute conversion operations. 5.2. Fuzzy quantization based low bit-resolution motion estimation On the basis of the concept mentioned above, we present a low bit-resolution motion estimation approach based on fuzzy quantization. The current and reference frames are first processed by the bit transform proposed in Sections 3 and 4, respectively. Next, one of the conven￾tional search strategies, e.g., full search, is applied for motion estimation using h as the matching metric. This approach is summarized in Algorithm 3. Algorithm 3 (Low bit-resolution motion estimation). 1. Separately compute the mean pixel values μc ¼ E½Ic and μr ¼ E½Ir of the current and reference frames, and their variance s2 cf ¼ E½I 2 c E2½Ic and s2 rf ¼ E½I 2 r E2½Ir. 2. Carry out the histogram equalization (see Eq. (6)) on reference frame to obtain g′. 3. Uniformly quantize g′ and determine fT′jg. Fig. 2. Inaccurate matching evaluation by BXOR metric. (a) Two-bit BXOR metric. (b) Three-bit BXOR metric. Table 1 Test video sequences and formats. Sequence name Format Resolution Frame rate (fps) Flower CIF 352 288 30 Football CIF 352 288 30 Mobile CIF 352 288 30 Paris CIF 352 288 30 Stefan CIF 352 288 30 Tennis CIF 352 288 30 Tempete CIF 352 288 30 City 4CIF 704 576 30 Crew 4CIF 704 576 30 Harbour 4CIF 704 576 30 Carphone QCIF 176 144 30 Grandma QCIF 176 144 30 1440 C.-M. Song et al. / Signal Processing: Image Communication 28 (2013) 1435–1447