Block-matching algorithm based on differential evolution for motion estimation

Motion estimation is one of the major problems in developing video coding applications. Among all motion estimation approaches, block-matching (BM) algorithms are the most popular methods due to their effectiveness and simplicity for both software and hardware implementations. A BM approach assumes that the movement of pixels within a defined region of the current frame (macro block, MB) can be modeled as a translation of pixels contained in the previous frame. In this procedure, the motion vector is obtained by minimizing the sum of absolute differences (SAD) produced by the MB of the current frame over a determined search window from the previous frame. The SAD evaluation is computationally expensive and represents the most consuming operation in the BM process. The most straightforward BM method is the full search algorithm (FSA), which finds the most accurate motion vector, exhaustively calculating the SAD values for all the elements of the search window. Over this decade, several fast BM algorithms have been proposed to reduce the number of SAD operations by calculating only a fixed subset of search locations at the cost of poor accuracy. In this paper, a new algorithm based on differential evolution (DE) is proposed to reduce the number of search locations in the BM process. To avoid computing several search locations, the algorithm estimates the SAD values (fitness) for some locations using the SAD values of previously calculated neighboring positions. As the proposed algorithm does not consider any fixed search pattern or any other different assumption, a high probability for finding the true minimum (accurate motion vector) is expected. In comparison with other fast BM algorithms, the proposed method deploys more accurate motion vectors, yet delivering competitive time rates.     

Block matching algorithm for motion estimation based on Artificial Bee Colony (ABC)

Block matching (BM) motion estimation plays a very important role in video coding. In a BM approach, image frames in a video sequence are divided into blocks. For each block in the current frame, the best matching block is identified inside a region of the previous frame, aiming to minimize the sum of absolute differences (SAD). Unfortunately, the SAD evaluation is computationally expensive and represents the most consuming operation in the BM process. Therefore, BM motion estimation can be approached as an optimization problem, where the goal is to find the best matching block within a search space. The simplest available BM method is the full search algorithm (FSA) which finds the most accurate motion vector through an exhaustive computation of SAD values for all elements of the search window. Recently, several fast BM algorithms have been proposed to reduce the number of SAD operations by calculating only a fixed subset of search locations at the price of poor accuracy. In this paper, a new algorithm based on Artificial Bee Colony (ABC) optimization is proposed to reduce the number of search locations in the BM process. In our algorithm, the computation of search locations is drastically reduced by considering a fitness calculation strategy which indicates when it is feasible to calculate or only estimate new search locations. Since the proposed algorithm does not consider any fixed search pattern or any other movement assumption as most of other BM approaches do, a high probability for finding the true minimum (accurate motion vector) is expected. Conducted simulations show that the proposed method achieves the best balance over other fast BM algorithms, in terms of both estimation accuracy and computational cost.     

An efficient multi-layer reference frame motion estimation for video coding

Most of the fast search motion estimation algorithms reduce the computational complexity of motion estimation (ME) greatly by checking only a few search points inside the search area. In this paper, we propose a new algorithm—multi-layer motion estimation (MME) which reduces the computational complexity of each distortion measure instead of reducing the number of search points. The conventional fast search motion estimation algorithms perform ME on the reference frame with full distortion measure; on the contrary, the MME performs ME on the layers with partial distortion measures to enhance the computational speed of ME. A layer is an image which is derived from the reference frame; each macro-pixel value in the layer represents the sum of the values of the corresponding pixels in the reference frame. A hierarchical quad-tree structure is employed in this paper to construct multiple layers from the reference frame. Experimental results on different video sequences show evidence that many motion vectors have been found similar both in the reference frame and the layers. The effectiveness of the proposed MME algorithm is compared with that of some state-of-the-art fast block matching algorithms with respect to speed and motion prediction quality. Experimental results on a wide variety of video sequences show that the proposed algorithm outperforms the other popular conventional fast search motion estimation algorithms computationally while maintaining the motion prediction quality very close to the full-search algorithm. Moreover, the proposed algorithm can achieve a maximum of 97.99 % speed-improvement rate against the fast full-search motion estimation algorithms which are based on hierarchical block matching process. The proposed MME performs the motion estimation on the layers by using three types of search patterns. The derivation of these search patterns exploits the characteristic of the center-biased motion vector distribution and that of less intensive block distortion measurement of the layers.     

一种针对MPEG-4 AVC/JVT/H.264的快速多帧运动估计算法

在H．264标准中，运动估计的编码运算量非常复杂。通过重新使用上一参考帧中的运动矢量信息，论文提出了一种效率较高的搜索算法，即无需在全部的参考帧中搜索，只使用存储的运动矢量来组成当前的运动矢量。这种算法还可以结合其他快速的搜寻算法以进一步减少运动估计的运算复杂度。     

一种适用于H．264的基于自适应搜索范围的快速运动估计算法

块匹配运动估计在视频编码中有着举足轻重的地位，其性能的优劣在很大程度上影响着输出码流的质量。全搜索是效果最好的运动估计算法，但其巨大的运算量是实际应用，特别是实时应用无法承受的。为解决这一问题，各种快速算法不断涌现。本文提出了一种适用于最新视频编码标准——H．264／MPEG4-AVC的快速运动估计算法。该算法基于自适应搜索范围，利用视频图像序列的帧间统计特性以及运动向量时域、空域的相关性，在保证PSNR性能的同时，使运动估计部分的运算复杂度大为降低。实验仿真表明，该算法适用面广，对大运动与小运动序列都有很强的自适应能力。在保持与全搜索相同PSNR的同时，平均速度超过全搜索280倍有余，超过三步法1．8倍，性能明显优于新三步法、四步法等经典快速运动估计算法。     

All-layer search algorithm using mean inequality and improved checkerboard partial distortion search for fast motion estimation

Block-matching motion estimation algorithm is used in many video compression coding systems because it could greatly reduce the temporal redundancy between the consequent video sequences. In this paper, an all-layer search algorithm using mean inequality and improved checkerboard partial distortion search scheme for fast block-matching motion estimation is proposed. A layer in the proposed method refers to a processed image which is derived from the reference frame or the adjacent lower layer. Firstly, the proposed algorithm constructs all layers from the reference frame or the adjacent lower layer by summing up all pixels over a sub-block. Then, a new mean inequality elimination method is introduced to reject a lot of unnecessary candidate search points on the top layers before calculating the real block matching distortion. Finally, the proposed algorithm utilizes an improved checkerboard partial distortion search scheme in the process of the real block distortion calculation on the following layers to further reduce the amount of computation. Experimental results show that the proposed algorithm can effectively reduce the computational complexity of motion estimation meanwhile guarantee the matching quality compared to other motion estimation algorithms. Compared to the full search algorithm, the proposed algorithm can reduce 97.30 % computational complexity with a negligible degradation of the peak signal to noise ratio (PSNR). Compared to the diamond search algorithm, directional gradient descent search algorithm, partial distortion search algorithm, transform-domain successive elimination algorithm and two-layer motion estimation algorithm, the proposed algorithm can also save 63.56 %, 52.73 %, 92.87 %, 85.77 % and 33.96 % computational complexity, respectively.     

视频标准帧速率上变换的自适应运动补偿方案

提出了一种自适应的运动补偿方案，首先利用预测三步搜索算法进行运动估计，由于此运动估计算法能够很好地利用运动向量的时空相关性．从而能得到更加平滑的运动向量场。其次．为了能够抑制运动向量场中个别奇异向量以及块匹配算法所固有的块效应问题，对向量场进行中值滤波，并采用了一种特殊的向量分配算法。方案的最后一个环节是运动补偿插值，它综合考虑插值帧的局部图像质量以及全局图像质量，利用一种白适应性较强的中值滤波操作来达到一定的综合效果。实验结果证明，此算法与运动补偿时间插值(MCTI)算法相比，插值得到的图像更加平滑，而且，两者的信噪比指标对比也充分说明了本算法的优越性。     

An adaptive block-based matching algorithm for crowd motion sequences

For crowd analytics and surveillance systems, motion estimation is an essential first step. Lots of crowd motion estimation algorithms have been presented in the last years comprising pedestrian motion. However, algorithms based on optical flow and background subtraction have numerous limitations such as the complexity of the computation in the presence of high dense crowd and sudden motion changes. Therefore, a novel estimation algorithm is proposed to measure the motion of crowd with less computational complexity and satisfy the real time requirements. The proposed algorithm is based on block-based matching, particle advection, and social force model. By the block-based matching, the motion is estimated in each frame, and the corresponding motion field is created. The particle advection process provides more information about the behavior of pedestrians groups, their tracked trajectories and the boundary of each group segment. Relying on the social force model, a predicted direction of the motion vectors (MV) could be measured significantly. Subsequently, the block-based technique is combined with the social force model to obtain the accurate motion vector with the less possible number of search points. The experimental results indicate that the proposed method achieves high performance by reducing the search points, particularly when many collision situations or obstacles exist in the scenes. Considering the reduction in the computational complexity, the quality of degradation is very low. In all cases, average PSNR degradation of the proposed algorithm is only 0.09.     

非对称双十字形运动估计搜索算法研究与实现

视频序列运动矢量分布的中心偏移特性在运动估计中发挥重要的作用，但忽视了运动矢量分布的方向性。该文提出了非对称双十字形搜索(UDCS)算法，给出了在搜索的初始阶段使用小十字搜索模型对小的运动矢量搜索并在相继的搜索过程中使用具有方向性的十字形搜索模型对大运动矢量进行搜索的步骤。介绍了该算法的实现结构，并分析了该算法搜索性能。     

一种基于新型遗传算法的块运动估计算法

提出了一种基于新型遗传算法的块匹配运动估计算法。该算法把块运动向量作为遗传染色体,经过选择变异等操作,将随机搜索与特定目标搜索相结合,解决了以往快速搜索算法易陷于局部最优的问题,同时该算法中所带的模糊评价函数使得对个体的评价更合理、客观,该算法还将运动矢量空间偏置特性用于初始种群的选取,进一步提高了算法性能。实验结果表明,该算法性能上接近于FSA,速度却接近于TSS。     

一种改进的有效运动估计方法—准菱形搜索法

根据基于对象的MPEG－4视频标准[1]，以对象宏块的运动矢量作类似的多边形匹配，利用相邻帧中运动矢量和图象像素的相关性，提出了一种“准菱形”搜索运动估计方法，该方法在图象运动复杂的情况下，不仅能根据方向选择来扩大搜索范围，而且能有效地降低搜索点数和搜索次数，该算法利用C语言编程，结合Matlab数学工具来处理典型图象序列，其结果表明，该方法与菱形搜索，六角形搜索相比，具有既能够有效地保持图象质量又能降低计算的复杂度等优点。     

基于主动网络的网络故障管理研究及实现

视频序列运动矢量分布的中心偏移特性在运动估计中发挥重要的作用，但忽视了运动矢量分布的方向性。该文提出了非对称双十字形搜索（UDCS）算法，给出了在搜索的初始阶段使用小十字搜索模型对小的运动矢量搜索并在相继的搜索过程中使用具有方向性的十字形搜索模型对大运动矢量进行搜索的步聚。介绍了该算法的实现结构，并分析了该算法搜索性能。     

一种视频转码快速运动估计算法

提出一种基于输入码流信息的视频转码快速运动估计算法。该算法利用输入码流的运动矢量和系数信息合成预测运动矢量,分析当前宏块对应转码前区域宏块运动矢量的一致性,结合图像的运动活跃性,自适应地调整编码运动估计的搜索策略。实验结果表明,与菱形搜索算法相比,该算法能够降低20%以上的编码时间,同时保持良好的图像质量;与AMVR-DIM算法相比,其运算性能和图像质量均有所提高。     

Simple and efficient motion estimation algorithm by continuum search

Motion estimation plays a vital role in reducing temporal correlation in video codecs but it requires high computational complexity. Different algorithms have tried to reduce this complexity. However these reduced-complexity routines are not as regular as the full search algorithm (FSA). Also, regularity of an algorithm is very important in order to have a hardware implementation of that algorithm even if it leads to more complexity burden. The goal of this paper is to develop an efficient and regular algorithm which mimics FSA by searching a small area exhaustively. Our proposed algorithm is designed based on two observations. The first observation is that the motion vector of a block falls within a specific rectangular area designated by the prediction vectors. The second observation is that in most cases, this rectangular area is smaller than one fourth of the FSA’s search area. Therefore, the search area of the proposed method is adaptively found for each block of a frame. To find the search area, the temporal and spatial correlations among motion vectors of blocks are exploited. Based on these correlations, a rectangular search area is determined and the best matching block in this area is selected. The proposed algorithm is similar to FSA in terms of regularity but requires less computational complexity due to its smaller search area. Also, the suggested algorithm is as simple as FSA in terms of implementation and is comparable with many of the existing fast search algorithms. Simulation results show the claimed performance and efficiency of the algorithm.     

一种基于块分割结构的运动估计新算法

运动估计是剔除视频压缩中的时间冗余的关键,现有算法大都是基于全搜索策略的SAD匹配算法,这些算法虽然压缩性能很好,但计算复杂,实时性差。提出一种快速运动估计新算法,将块分割成多个子块,计算每个子块的灰度值之和与灰度值的平方和,将其整体作为一个参数再结合提出的三个匹配准则,求出当前帧和候选帧之间的最优运动估计。通过实验表明,采用该算法后计算的复杂度明显减小,实时性得到较大提高,其压缩性能却非常接近基于全搜索策略的SAD算法。     

一种改进遗传搜索块匹配运动估计算法

运动估计是帧间视频编码中的关键技术,但现有的快速搜索算法中大都是次优算法,且易陷于局部极小点。针对此问题,提出了一种改进型遗传算法应用于块运动估计中的遗传搜索块匹配运动估计算法(MGSAME)。该方法把块运动向量作为遗传染色体,经过杂交、变异等操作,以便得到全局意义上的最优解,并与经典的全局搜索法、三步搜索法和传统遗传算法(SGA)进行了比较。实验结果显示,该算法不仅有效地解决了局部极小问题,而且计算量也较少。     

Fast multiframe motion estimation algorithms by motion vector composition for the MPEG-4/AVC/H.264 standard

The MPEG-4/AVC/H.264 video coding standard adopts various coding schemes such as multiple reference frames and variable block sizes for motion estimation. Hence, MPEG-4/AVC/H.264 provides gains in compression efficiency of up to 50% over a wide range of bit rates and video resolutions compared to previous standards. However, these features result in a considerable increase in encoder complexity, mainly regarding to mode decision and motion estimation. The proposed algorithms use the stored motion vectors to compose the motion vector without performing the full search in each reference frame. Therefore, the proposed algorithms can obtain an average speed up ratio of four for encoding, thus benefiting from the prediction of the motion vector for the reference frames in advance and maintaining good performance. Any fast search algorithm can be utilized to further largely reduce the computational load.     

反向学习全局和声搜索算法

提出一种反向学习全局和声搜索(OLGHS)算法.基于反向学习技术初始化和声记忆库,提高初始和声向量的质量;通过当前最差和声向当前最优和声学习进化,提高算法的全局搜索性能;通过其他和声向量之间不断回溯交互的随机学习策略,提高算法局部搜索性能;用由两种不同学习策略随机交叉动态产生的新和声与反向和声二者较优的个体更新和声记忆库,提高算法的搜索性能.将OLGHS算法与其他启发式优化算法以及目前文献中较优的改进HS算法进行性能测试,测试结果表明OLGHS算法具有较高的寻优精度和较快的收敛速度.     

A pixel-based outlier-free motion estimation algorithm for scalable video quality enhancement

Scalable video quality enhancement refers to the process of enhancing low quality frames using high quality ones in scalable video bitstreams with time-varying qualities. A key problem in the enhancement is how to search for correspondence between high quality and low quality frames. Previous algorithms usually use block-based motion estimation to search for correspondences. Such an approach can hardly estimate scale and rotation transforms and always introduces outliers to the motion estimation results. In this paper, we propose a pixel-based outlier-free motion estimation algorithm to solve this problem. In our algorithm, the motion vector for each pixel is calculated with respect to estimate translation, scale, and rotation transforms. The motion relationships between neighboring pixels are considered via the Markov random field model to improve the motion estimation accuracy. Outliers are detected and avoided by taking both blocking effects and matching percentage in scaleinvariant feature transform field into consideration. Experiments are conducted in two scenarios that exhibit spatial scalability and quality scalability, respectively. Experimental results demonstrate that, in comparison with previous algorithms, the proposed algorithm achieves better correspondence and avoids the simultaneous introduction of outliers, especially for videos with scale and rotation transforms.     

一种基于补偿融合的帧频提升方法

研究经典的单向运动估计算法,提出一种基于补偿融合的帧频提升方法。通过融合前后向运动估计的补偿帧减少空洞数量,并采用规则块二次估计算法填补空洞。在匹配准则中加入运动矢量相关性因子和边缘匹配误差,从而提高运动估计的准确性。实验结果表明,该方法计算简单,能够取得较好的插帧效果。