NTW Logo (Black)

About IEEE

IEEE Membership

Products and Services


IEEE Organizations


IEEE Nav Bar




IEEE SCV Signal Processing Society Distinguished Lecture 2008

Jointly sponsored with IEEE SCV Circuits and Systems Society

Date:  Feb 11, 2008

Title: Simplified Fast Motion Estimation: Simplified and Unified Multi-Hexagon Search (SUMH) with Context Adaptive Lagrange Multiplier (CALM)

Speaker: Prof. Nam Ling, Department of Computer Engineering, Santa Clara University


Abstract: Fast motion estimations are especially important to speed up the time-consuming encoding processes for H.264 video encoding. In this talk, we first present our simplified fast motion estimation method, called Simplified and Unified Multi-Hexagon Search (SUMH), that produces a significant speed-up as compared with today's fast motion estimations, yet encounters only a small PSNR degradation when compared to that of full search. In addition, we present a novel method to refine the Lagrange multiplier, called Context Adaptive Lagrange Multiplier (CALM), for rate-constrained motion estimation. Both our methods were recently adopted into the H.264/MPEG-4 AVC video coding international standard (including the text document and the JM reference software).

Our SUMH is based on two principles, partial distortion search (PDS) and dual-halfway-stop (DHS) algorithms. PDS generally produces less video quality degradation of the predicted images than those of conventional fast block matching algorithms (BMAs). However, the speedup gain of PDS algorithms is usually limited. In this talk, we present an enhancement over a normalized PDS (NPDS) algorithm to further reduce block matching motion estimation complexity and improve video fidelity. The novelty of our algorithm is that, in addition to the halfway-stop technique in NPDS, a dual-halfway-stop (DHS) method, which is based on a dynamic threshold, is proposed so that block matching is not performed against all searching points. The dynamic threshold is obtained via a linear model utilizing already computed distortion statistics. An adaptive search range mechanism based on inter block distortion further constrains the searching process. Experimental results show that our proposed method reduces the encoding time by about 55% on the average when compared to those of the state-of-the-art methods, with similar rate-distortion performances. Our SUMH algorithm, making use of DHS-NPDS, consists of two parts, an integer-pel fast search and a sub-pel fast search.

To extend motion estimation further, we propose a new simple and efficient method to adjust Lagrange multipliers based on the context (CALM), which improves the accuracy for the detection of true motion vectors as well as the most efficient encoding modes for luma, which are used for deriving the motion vectors and modes for chroma. Simulation results show that the chroma bit rates can be reduced by 4.36% and 4.80% (on the average) for U- and V- chroma components, respectively, when compared with that of the recent JM reference software. In addition, the coding efficiency improvement is comparable to the more complicated rate-distortion optimized (RDO) mode decision techniques.

A recorded version of Prof. Ling's seminar, which he presented at another venue, can be viewed at this link for those who are interested. [Simplified fast motion estimation (SFME) with context adaptive lagrange multiplier (CALM), by Prof. Nam Ling, 21 June 2007 ]



Prof. Nam Ling received a B.Eng. degree in Electrical Engineering from the National University of Singapore (NUS). He received M.S. and Ph.D. degrees, both in Computer Engineering, from the University of Louisiana at Lafayette, U.S.A. Prof. Ling is currently a full Professor with the Department of Computer Engineering and the Associate Dean (Research and Faculty Development) for the School of Engineering at Santa Clara University (SCU), California, U.S.A. He is also a Consulting Professor to the National University of Singapore (NUS Overseas Colleges) and a Guest Professor of Shanghai Jiao Tong University (China). He has served as Visiting Professor/Consultant/Scientist/Scholar to institutions such as the Institute for Infocomm Research (I2R) (Singapore), Nanyang Technological University (Singapore), National Dong Hwa University (Taiwan), and National Chiao Tung University (Taiwan).

Prof. Ling has more than 130 publications in the fields of video/image coding, video decoder design, video communications, and systolic arrays. He is the primary author of the book entitled Specification and Verification of Systolic Arrays. He and his team's proposal on Simplified and Unified Multi-Hexagon Search (SUMH) (previously called simplified fast motion estimation or SFME) was adopted in 2005, and their Context Adaptive Lagrange Multiplier (CALM) method was adopted in 2006, both into the H.264/MPEG-4 AVC video coding international standard. Prof. Ling received the Arthur Vining Davis Junior Faculty Fellowship in 1991 and the SCU Outstanding Achievement Award in Teaching, Research, and Service, in 1992. Prof. Ling was named 1999 Researcher of the Year by SCU Engineering. He received the University Award for Recent Achievement in Scholarship in 2002, the SCU President's Recognition Award in 2005, and the University Award for Sustained Excellence in Scholarship in 2007. He was named IEEE Distinguished Lecturer (Circuits and Systems) for 2002-2003 and 2007-2008. Prof. Ling also received the 2003 IEEE ICCE Best Paper Award (First Place Winner) for his work on MPEG-4 face animation. Prof. Ling became an IEEE Fellow effective January 2008 for contributions to video coding algorithms and architectures.

Prof. Ling served as an Associate Editor for the IEEE Transactions on Circuits and Systems - I in 2002-03. He was a Guest Editor for the Journal of VLSI Signal Processing Systems special issue in 2006. In 1993 - 1995, Prof. Ling served as the Chair of the IEEE Computer Society Technical Committee (TC) on Microprocessors and Microcomputers. Currently, he serves as the Chair of the IEEE Circuits and Systems Society Circuits and Systems for Communications Technical Committee. He is also a member of the VSPC TC (IEEE Circuits and Systems Society) and a member of the DISPS TC (IEEE Signal Processing Society). Prof. Ling was the General Chair for the IEEE Hot Chips Symposium in 1995. He was Technical Program Co-Chair for ISCAS'07, SiPS'07, DCV'02, and SiPS'00. He was Track Co-Chair for ISCAS'04, ISCAS'05, and ISCAS'06. Prof. Ling served in program committees, organizing committees, and as session chairs for many IEEE conferences. He has delivered more than 80 invited/distinguished/keynote colloquia in eight different countries.

Back to main page