关于图像处理中的几种运动估计算法

这个学期，还花了点时间做了一下运动估计方面的事情，主要是用matlab实现了一些各种运动估计的算法。后来做了一次英文的presentation。其实本来想贴代码的，后来看了看，太长乐，所以我就贴一下presentation好了。有些东西是中文翻译成英文，翻译的挺烂的~~本来PPT上还做了几张图片的，传上来太麻烦了。不过，谁要是想看代码和图片的话直接找我要好了~~
Contents of the Work：
This work is to compress a series of motional images, of which some have strong correlation, while some others do not have.

Thinking:
·To reduce the redundancy between neighboring frames, we can use Motion Estimation that would be introduced in detail later.
·To reduce the redundancy in the same frame, we can adopt other methods like DCT and Entropy Coding, which is similar to JPEG to some extent.

 

Motion Estimation:
·There is a lot of algorithms about Motion Estimation (ME).
·I choose some of them, and realize them in my homework.
·I also propose some algorithms designed by myself.
·We can see the differences in efficiency and effect among them later.

 

Algorithms of ME：
·Full Search method (FS) (全搜索法)
·FS with threshold (阈值全搜索法)
·Two-Dimensional Logarithmic (TDL)  (二维对数法)
·Three Step Search (TSS) (三步搜索法)
·Cross Search Algorithm (CSA) (交叉法)
·Diamond Search (DS) (菱形搜索法)

 

Full Search method (FS):
·Thinking:
 -Start from the origin. Search the position with MAD (Minim of Abstract Difference) clockwise from near to far gradually.
·Performance
 -Its result is the optimum one of all algorithms, but it is the worst efficient algorithm.

 

How to improve the efficiency: 
·The disadvantages of FS:
 -Some part of its computation is meaningless.
 -Some direction in its searching is meaningless.
·Thinking One: Set a threshold for MAD
·Thinking Two: Search in the most probable direction.

 

FS with threshold:
·The feature of motional images with strong correlation:
 -The position with MAD is usually near the origin.
 -The MAD is relatively small.
·If we find the MAD position, later searches are no longer needed.
·But MAD is unknown, we have to set a threshold. If MAD is below the threshold, we take that position as the MAD position.
·If threshold is too high, the position may  be not the best position. If threshold is too low, the efficiency would not be improved obviously.

 

Two-Dimensional Logarithmic (TDL):
·Proposed by J. R. Jain and A. K. Jain
·Thinking:
 -Start from the origin. Search the position in the pattern of “+” and find the most probable direction, continue the search and diminish the length of step gradually until the length of step is one pixel. Then search all eight point around it.
 
Three Step Search (TSS):
·Similar to the TDL
·Thinking:
 -Start from the origin. Search the eight point all around the origin in the distance of the length of a step. Find the most probable direction. Then diminish the length of step gradually, until the length of step is 1 pixel.

 

Cross Search Algorithm (CSA):
·Proposed by Ghanbari in 1990.
·Similar to TDL
·Thinking:
 -Start from the origin. Search the position in the pattern of “X” and find the most probable direction, continue the search and diminish the length of step gradually until the length of step is one pixel. Then search all eight point around it.

 

Diamond Search (DS):
·Proposed by Shan Zhu and Kai-kuang Ma.
·Thinking:
 -Use two sets of template. One is designed for direction. The other one is designed for localization.
 
My Idea:
·How to determine the start position?

 

How to differentiate two frame of weak correlation:
·Calculate the distribution of MAD, and set a threshold, if distribution is blew the threshold, then use JPEG to reduce the redundancy in frame directly, else take motion estimation.

 

个人感觉是，FS算法是根本，衍生出FS with Threshold，主要思想遵循思路一，主要是基于减少无意义的后续运算。其他的方法主要遵循思路二，减少无意义方向上的运算。这其中，钱集中TDL,TSS,CSA都不是很精确，尽管速度很快，而且对相对于耗时相同的FS with Threshold而言，方向性明显的图片用这几种方法有很好的效果。FS with Threshold则可以根据要求改变效果和时间。个人认为这里面最好的是DS算法，在效果跟阈值很低时的FS with Threshold相差无几，但是耗时间非常少。记得看到bbs上说，有人的程序都算了很久还算不出来，我觉得可能是算法的问题。我这里面最耗时的算法FS在IBM T23(PIII 1G)上也只需要20 seconds就完成了。我想应该没有比FS更耗时的算法了吧~~ : )