A fast partial distortion search algorithm for motion estimation based on the multi-traps assumption

CORC > 光电技术研究所 > 中国科学院光电技术研究所 > 光电传感技术研究室（六室）

	A fast partial distortion search algorithm for motion estimation based on the multi-traps assumption
	Xia, Xiao-Peng 1; Liu, En-Hai 1; Qin, Jun-Ju 2
刊名	Signal Processing: Image Communication
	2015
卷号	31 页码:25-33
ISSN号	0923-5965
通讯作者	Xia, Xiao-Peng
中文摘要	Full search has the best matching accuracy but costs the most time, while fast search algorithms can achieve a high speed but are easy to be trapped in local minimums. To compensate the shortcomings of the existing algorithms, this paper proposes a fast partial distortion motion estimation algorithm based on the multi-traps assumption (MT-PDS). It mainly consists of three steps: (1) estimate the number of traps in the search area, (2) obtain the positions of the traps by using the k-th (k=0,1,2,...15) partial distortion, which contributes most to the true sum of absolute difference (SAD), to perform the coarse search, and (3) get the positions of the deepest traps and search around them to get the global minimum. Besides, the proposed algorithm also introduces an adaptive search method and a sparse search pattern, which further reduce the computations. Experimental results show that the proposed MT-PDS is about 160 times faster than the full search on average; and the speed-up can achieve over 180 times for the low motion contents. What is more, it only degrades the quality by -0.0178 dB and slightly increases the bit rate by 0.735%, which can be considered ignorable. Those advantages make the MT-PDS a very useful tool in real time applications, such as video compression, pattern recognition, target tracking, etc. © 2014 Elsevier B.V. All rights reserved.
英文摘要	Full search has the best matching accuracy but costs the most time, while fast search algorithms can achieve a high speed but are easy to be trapped in local minimums. To compensate the shortcomings of the existing algorithms, this paper proposes a fast partial distortion motion estimation algorithm based on the multi-traps assumption (MT-PDS). It mainly consists of three steps: (1) estimate the number of traps in the search area, (2) obtain the positions of the traps by using the k-th (k=0,1,2,...15) partial distortion, which contributes most to the true sum of absolute difference (SAD), to perform the coarse search, and (3) get the positions of the deepest traps and search around them to get the global minimum. Besides, the proposed algorithm also introduces an adaptive search method and a sparse search pattern, which further reduce the computations. Experimental results show that the proposed MT-PDS is about 160 times faster than the full search on average; and the speed-up can achieve over 180 times for the low motion contents. What is more, it only degrades the quality by -0.0178 dB and slightly increases the bit rate by 0.735%, which can be considered ignorable. Those advantages make the MT-PDS a very useful tool in real time applications, such as video compression, pattern recognition, target tracking, etc. © 2014 Elsevier B.V. All rights reserved.
学科主题	Algorithms - Learning algorithms - Pattern recognition - Target tracking
收录类别	SCI ; EI
语种	英语
WOS记录号	WOS:000350078800003
内容类型	期刊论文
源URL	[http://ir.ioe.ac.cn/handle/181551/5142]
专题	光电技术研究所_光电传感技术研究室（六室）
作者单位	1.Institute of Optics and Electronics, Chinese Academy of Sciences, Mailbox 350, Chengdu City, Sichuan Province, China 2.Chengdu Normal University, Chengdu, China
推荐引用方式 GB/T 7714	Xia, Xiao-Peng,Liu, En-Hai,Qin, Jun-Ju. A fast partial distortion search algorithm for motion estimation based on the multi-traps assumption[J]. Signal Processing: Image Communication,2015,31:25-33.
APA	Xia, Xiao-Peng,Liu, En-Hai,&Qin, Jun-Ju.(2015).A fast partial distortion search algorithm for motion estimation based on the multi-traps assumption.Signal Processing: Image Communication,31,25-33.
MLA	Xia, Xiao-Peng,et al."A fast partial distortion search algorithm for motion estimation based on the multi-traps assumption".Signal Processing: Image Communication 31(2015):25-33.