一种菱形运动估计搜索方法

摘要

一种新型的菱形搜索方法，首先用小模式进行预搜索，找到最小块匹配失真(MBD)点，以MBD为中心构造大搜索模式，找到MBD；然后以大模式的MBD为中心，开始菱形搜索：首先搜索大菱形，如果MBD在中心，以小菱形方式搜索，找到的MBD点即为最终的块匹配失真点。否则继续大菱形搜索。菱形还采用了中途停止技术，对静止和半静止块的搜索速度有显著的提高。改进的部分失真准则在不影响失真度的情况下大大降低了计算复杂度。实验结果表明：新型菱形搜索方法比菱形搜索方法和菱形搜索方法在信噪比降低很少甚至不降低的情况下，分别节省41％和16％的搜索点，和其它流行的块匹配运动估计方法相比，本方法有更快的搜索速度和更小的失真度。

主权项

一种十字菱形运动估计搜索方法，其特征在于包括以下步骤：(1)在小十字模式的5个搜索点中，搜索最小块失真MBD所在点，如果最小块失真MBD点在小十字模式的中心，则一步搜索停止，得到最终要求的运动矢量MV(0，0)；否则，进入步骤(2)；(2)以步骤(1)所搜索的最小块失真MBD点为中心构造新的小十字模式，搜寻3个新的搜索点，找出新的最小块失真MBD点，如果该点在小十字模式的中心，则二步搜索停止，得到最终要求的运动矢量MV(±1，0)或(0，±1)；否则，进入步骤(3)；(3)以步骤(1)中小十字模式的中心为中心构造大十字搜索模式，搜索大十字模式3个还没有搜索到的点，找出最小块失真MBD点，以作为下一步搜索的中心；(4)以步骤(3)中的最小块失真MBD点为中心，构造大菱形搜索模式，找出新的最小块失真MBD点，如果该点在大菱形的中心，进入步骤(5)；否则，继续步骤(4)；(5)以步骤(4)所搜索到的最小块失真MBD点为中心，构造小菱形搜索模式，找出新的最小块失真MBD点，该点所对应的向量即为最终要求的运动矢量；其中，采用改进的部分块失真准则搜索所述的最小块失真MBD点，改进的部分块失真准则具体如下：定义块的大小为16×16，第n帧左上角坐标为(m，n)的块与第n‑1帧左上角坐标为(m+p，n+q)的块间的失真度量SAD由下式给出： SAD ( m , n ; p , q ) = Σ i = 0 15 Σ j = 0 15 | f n ( m + i , n + j ) - f n - 1 ( m + p + i , n + q + j ) | 其中，fn(m+i，n+j)表示第n帧坐标为(m+i，n+j)像素点的像素值；将失真度量SAD(m，n；p，q)分成16个部分失真度量sadk(m，n；p，q)，其中k＝1，2，…，16，第k个部分失真度量的定义如下式所示： sad k ( m , n ; p , q ) = Σ i = 0 3 Σ j = 0 3 | f n ( m + 4 i + s k , n + 4 j + t k ) - f n - 1 ( m + p + 4 i + s k , n + q + 4 j + t k ) | 其中sk，tk分别为第k个部分失真度量所用左上角像素点相对于块左上角的水平和垂直偏移，第k次累加部分失真度量的定义如下式所示： SAD k ( m , n ; p , q ) = Σ i = 1 k sad i ( m , n ; p , q ) 如果第k次累加部分失真度量满足16×SADk(m，n；p，q)＞k×min(SAD)其中min(SAD)是搜索过程中当前得到的最小失真，k为自己设定的整数，取值范围为：3≤k≤16，则认为该点不可能为匹配点；否则，继续计算第k+1次累加部分失真度量SADk+1(m，n；p，q)，再进行比较。