C.-M.Song et aL Signal Processing:Image Communication 28 (2013)1435-1447 1445 inaccurate interval partitioning of pixel values,deteriorat- 2BT,and AQ-2BT in average.This illustrates that our non- ing the best-matched block and subsequent inter-frame uniform interval partitioning is an effective solution to the prediction accuracy.Our non-uniform quantization based bit transform.On the other hand,we can find in Tables 2 bit transform (NUQ-2BT)exploits optimum quantization and 3 that the NUQ-2BT is inefficient for complex videos theory and histogram equalization to reduce the informa- with high spatial details or fast motion,e.g.."Flower"and tion loss due to bit-resolution decrease.On one hand,it "Football"sequences.The reason is that such videos tend provides satisfying motion estimation performances for to present higher inter-frame noises than those with low most of the test sequences,although it only produces a details or slow motion,especially after a lossy coding.In suboptimal solution.The NUQ-2BT achieves 0.87 dB. this case the NUQ-2BT method would be seriously 0.31 dB,and 0.14 dB higher PSNR than those of 1BT,MT- affected,resulting in inaccurate motion estimation as discussed in Section 4.To address this issue,our FQ-2BT method uses a membership function working in a fuzzy 8BT -◆1BT manner to effectively alleviate the negative impact of -MT-2BT encoder's quantization noises.Additionally,it uses uni- 29 -A0-2BT NUQ-2BT form threshold for the current and reference frames.This 28 oFQ-ZB1 avoids both the discontinuity at macroblock's boundary occurred in MT-2BT and repeatedly calculating quantiza- 27 tion thresholds in AQ-2BT for each search window.There- fore,the proposed bit transform and motion estimation obtain superior coding performance to several represen- 25 tative methods.whose PSNR is 0.24 dB.0.42 dB.0.98 dB. 24 and 0.10 dB higher than those of AQ-2BT,MT-2BT,1BT,and NUQ-2BT,respectively. 20 30 405060 70 80 90 Frame Number Fig.7.PSNR performance comparison among different motion estima- 6.3.Computational complexity comparison tion algorithms for "Harbour"at the bit-rate of 1500 kbps.The macro- block size is 16 x 16 pixels. The computational complexity is one of the key factors for evaluating motion estimation efficiency.In this sub- section,we will analyze the computational complexity of 34 each algorithm in terms of two stages,namely bit trans- 0-8BT form stage and motion estimation stage.Table 4 lists +-MT-28T average operation numbers per pixel by various motion ￥-AQ-2BT 32 号-NUQ-2BT estimation algorithms for CIF format videos with a search -FQ-2BT range of+16 pixels and a block size of 16x 16 pixels.As 31 can be found in Table 4,our algorithm performs less operations than 1BT,MT-2BT,and AQ-2BT at bit transform 30 stage.While at the motion estimation stage,the proposed 29 FQ-2BT algorithm still requires lower computational cost than three low bit-resolution methods,since the bit- 28 truncation SAD metric h is able to be implemented by the XLAT instruction of assembly language.The complexity 30 40 50 of each kind of operation depends on device's hardware Frame Number implementation and instruction set,which is beyond the Fig.8.PSNR performance comparison among different motion estima- scope of our study.We will not discuss the quantitative tion algorithms for "Grandma"at the bit-rate of 64 kbps.The macroblock comparisons among several algorithms.In general,the size is16×16 pixels. computational cost of FQ-2BT is lower than 1BT,MT-2BT, Table 4 Average operation numbers per pixel by various motion estimation algorithms Stage Operation 8BT 1BT MT-2BT AQ-2BT FQ-2BT Bit transform Addition 0 24 2.8438 15 1.2513 Multiplication 0 1 1.0625 5.8594×10-3 0.5013 Comparison 0 1 3 7.5 3.0013 Absolute conversion 0 0.5 49322×10-6 Square root 0 0 0 0 49322×10-6 Motion estimation Addition 2048 1024 1024 1024 1024 Absolute conversion 1024 0 0 0 0 Bit-wise operation 0 1024 3072 3072 0 XLAT instruction 0 0 0 0 1024inaccurate interval partitioning of pixel values, deteriorat￾ing the best-matched block and subsequent inter-frame prediction accuracy. Our non-uniform quantization based bit transform (NUQ-2BT) exploits optimum quantization theory and histogram equalization to reduce the informa￾tion loss due to bit-resolution decrease. On one hand, it provides satisfying motion estimation performances for most of the test sequences, although it only produces a suboptimal solution. The NUQ-2BT achieves 0.87 dB, 0.31 dB, and 0.14 dB higher PSNR than those of 1BT, MT- 2BT, and AQ-2BT in average. This illustrates that our non￾uniform interval partitioning is an effective solution to the bit transform. On the other hand, we can find in Tables 2 and 3 that the NUQ-2BT is inefficient for complex videos with high spatial details or fast motion, e.g., “Flower” and “Football” sequences. The reason is that such videos tend to present higher inter-frame noises than those with low details or slow motion, especially after a lossy coding. In this case the NUQ-2BT method would be seriously affected, resulting in inaccurate motion estimation as discussed in Section 4. To address this issue, our FQ-2BT method uses a membership function working in a fuzzy manner to effectively alleviate the negative impact of encoder's quantization noises. Additionally, it uses uni￾form threshold for the current and reference frames. This avoids both the discontinuity at macroblock's boundary occurred in MT-2BT and repeatedly calculating quantiza￾tion thresholds in AQ-2BT for each search window. There￾fore, the proposed bit transform and motion estimation obtain superior coding performance to several represen￾tative methods, whose PSNR is 0.24 dB, 0.42 dB, 0.98 dB, and 0.10 dB higher than those of AQ-2BT, MT-2BT, 1BT, and NUQ-2BT, respectively. 6.3. Computational complexity comparison The computational complexity is one of the key factors for evaluating motion estimation efficiency. In this sub￾section, we will analyze the computational complexity of each algorithm in terms of two stages, namely bit trans￾form stage and motion estimation stage. Table 4 lists average operation numbers per pixel by various motion estimation algorithms for CIF format videos with a search range of 716 pixels and a block size of 16 16 pixels. As can be found in Table 4, our algorithm performs less operations than 1BT, MT-2BT, and AQ-2BT at bit transform stage. While at the motion estimation stage, the proposed FQ-2BT algorithm still requires lower computational cost than three low bit-resolution methods, since the bit￾truncation SAD metric h is able to be implemented by the XLAT instruction of assembly language. The complexity of each kind of operation depends on device's hardware implementation and instruction set, which is beyond the scope of our study. We will not discuss the quantitative comparisons among several algorithms. In general, the computational cost of FQ-2BT is lower than 1BT, MT-2BT, Fig. 7. PSNR performance comparison among different motion estima￾tion algorithms for “Harbour” at the bit-rate of 1500 kbps. The macro￾block size is 16 16 pixels. Fig. 8. PSNR performance comparison among different motion estima￾tion algorithms for “Grandma” at the bit-rate of 64 kbps. The macroblock size is 16 16 pixels. Table 4 Average operation numbers per pixel by various motion estimation algorithms. Stage Operation 8BT 1BT MT-2BT AQ-2BT FQ-2BT Bit transform Addition 0 24 2.8438 1.5 1.2513 Multiplication 0 1 1.0625 5.8594 103 0.5013 Comparison 0 1 3 7.5 3.0013 Absolute conversion 0 0 0 0.5 4.9322 106 Square root 0 0 0 0 4.9322 106 Motion estimation Addition 2048 1024 1024 1024 1024 Absolute conversion 1024 0 0 0 0 Bit-wise operation 0 1024 3072 3072 0 XLAT instruction 0 0 0 0 1024 C.-M. Song et al. / Signal Processing: Image Communication 28 (2013) 1435–1447 1445