本論文提出一個適用於影像編碼中運動補償的運算複雜度控制機制，使編碼端能依照解碼端的硬體限制選取適合的預測模式。為了使編碼端能考慮複雜度，我們把運動補償的複雜度加入到位元率-失真最佳化當中，擴展成位元率-失真-複雜度最佳化。除此之外，在編碼中我們以一個巨區塊為編碼單元，藉由調整拉格朗日乘數分配每個編碼單元合適的複雜度，達到目標複雜度的限制。由實驗結果可知，我們提出的複雜度控制演算法在不同複雜度限制與不同位元率限制底下，都能提供一個精確而穩定的控制結果，相較於參考的演算法有更好的控制精準度，平均控制誤差為1.16%。在運動補償的複雜度減少一半的情形下，我們平均PSNR下降了0.248 dB。跟參考的演算法降低1.167dB相比，我們的演算法能提供更好的影像品質。

This paper proposes a complexity control of motion compensation for the video encoder to choose suitable prediction mode that fits the hardware constraint of the decoder. In order to take the complexity into consideration, we combine the complexity term of motion compensation with the conventional rate-distortion optimization (RDO), and extend the equation to rate-distortion-complexity optimization (RDCO). Furthermore, we use a macroblock (MB) as a coding unit. In order to meet the target complexity, the Lagrange multiplier is updated for each coding unit to allocate appropriate computing complexity. In experimental result, the average control error is 1.16% under difference complexity and bitrate constrains for our proposed. It means our algorithm provides more accurate and stable control than reference. The average PSNR drop is 0.248 dB by reducing 50% complexity of motion compensation. Comparing to 1.167 dB PSNR drop of reference algorithm, our algorithm can provide better video quality.

[1] T. Wiegand, G.J. Sullivan, G. Bjontegaard and A.Luthra, “Overview of the H.264/AVC Video Coding Standard” IEEE Trans. on Circuits and Systems for Video Technology, vol. 13, no. 7, pp. 560-576, July 2003.
[2] Y, Hu, Q. Li, S. Ma and C.-C. Jay Kuo, “Joint Rate-Distortion-Complexity Optimization for H.264 Motion Search,” IEEE International Conference on Multimedia and Expo, July 2006.
[3] V. Lappalainen, A. Hallapuro and T. D. Hamalainen, “Complexity of Optimized H.26L Video Decoder Implementation,” IEEE Trans. on Circuits and Systems for Video Technology, vol. 13, no. 7, pp. 717-725, July 2003.
[4] M. Horowitz, A.Joch, F. Kossentini and A. Hallapuro, “H.264/AVC Baseline Profile Decoder Complexity Analysis, ” IEEE Trans. on Circuits and Systems for Video Technology, vol. 13, no. 7, pp. 704-716, July 2003.
[5] Q. Xe, J. Liu, S. Wang and J. Zhao, “H.264/AVC Baseline Profile Decoder Optimization on Independent Platform,” International Conference on Wireless Communications Networking and Mobile Computing, vol.2, Sep. 2005, pp. 1253-1256.
[6] Iain E.G. Richardson, H.264 and MPEG-4 Viseo Compression, Wiley, 2003.
[7] G. J. Sullivan and T. Wiegand, “Rate-Distortion Optimization for Video Compression,” IEEE Signal Processing Magazine, vol. 15, no. 6, pp. 74-90, Nov. 1998
[8] S. W. Lee and C. -C. Jay Kuo “Complexity Modeling for Motion Compensation in H.264/AVC Decoder,” IEEE International Conference on Image Processing, vol. 5, Oct. 2007, pp. 313-316.
[9] S. W. Lee and C. -C. Jay Kuo “Motion Compensation Complexity for Decoder-Friendly H.264 System Design,” IEEE International Conference on Multimedia Signal Processing, Oct. 2007, pp. 119-122.
[10] S. W. Lee and C. –C Jay Kuo “Complexity Modeling of Spatial and Temporal Compensations in H.264/AVC Decoding,” IEEE International Conference on Image Processing, Oct. 2008, pp. 2504-2507.
[11] S. W. Lee and C. –C Jay Kuo “Complexity Modeling of Spatial and Temporal Compensations in H.264/AVC Decoding,” IEEE Transaction on Circuits and Systems for Video Technology, vol 20, no. 5, pp. 706-720, May 2010.
[12] M. Semsarzadeh, M. J. Langroodi, M. RezaHashemi and S. Shirmohammadi, “Complexity Modeling of the MotionCompensation Process of the H.264/AVC Video Coding Standard,” IEEE International Conference on Multimedia and Expo, Oct. 2012, pp. 925-930.
[13] K. Ugur, J. Lainema, A. Hallapuro and M. Gabbouj,“Generating H.264/AVC Compliant Bitstreams for Lightweight Decoding Operation Suitable for Mobile Multimedia Systems,” IEEE International Conference on Acoustics Speech and Signal Processing, vol. 2, May 2006.
[14] P. J. Cordeiro, G. P. Juan and P. A. Assuncao, “Low decoding complexity video streams for portable video players,” IEEE International Symposium on Consumer Electronics, April 2008.
[15] Y. Wang and S. F. Chang, “Motion Estimation and Mode Decision for Low-Complexity H.264 Decoder,” Tech. Rep. 201-2005-4, Columbia University DVMM Group, 2005.
[16] Y. Wang and S. F. Chang, “Complexity Adaptive H.264 Encoding for Light Weight Streams,” IEEE International Conference on Acoustics, Speech and Signal Processing, vol. 2, May 2006.
[17] Z. G. Li, F. Pan, K. P. Lim, G. Feng, X. Lin, and S. Rahardja, “Adaptive basic unit layer rate control for JVT,” present at the 7th JVT Meeting, Pattaya II JVT-G012-r1 Thailand, Mar. 2003.
[18] JM18.0 [Online] Availabl:http://iphome.hhi.de/suehring/tml/download/old_jm/
[19] Intel VTune Amplifier XE. [Online] Availabl:http://software.intel.com/en-us/articles/intel-vtune-amplifier-xe/