基于块金字塔的快速块匹配算法

在运动图象编码中，块匹配技术有着非常广泛的应用。在众多的匹配算法中，金字塔算法(blocks sum pyramid algorithm，BSPA)由于速度较快、算法比较简单而得到了广泛的应用。在金字塔算法的基础上，本文提出一种新的基于块金字塔的块匹配算法(NBSPA)。算法采用了预测初始中心，行更新等技术，实验结果表明，新的算法有效地降低了运算量。     

A rate-constrained fast full-search algorithm based on block sum pyramid.

This paper presents a fast full-search algorithm (FSA) for rate-constrained motion estimation. The proposed algorithm, which is based on the block sum pyramid frame structure, successively eliminates unnecessary search positions according to rate-constrained criterion. This algorithm provides the identical estimation performance to a conventional FSA having rate constraint, while achieving considerable reduction in computation.     

一种粗到精分块金字塔预测连续排除算法

提出一种粗到精分块金字塔连续排除算法用于减少块匹配运动估计所需计算量.金字塔可以方便地从当前搜索窗的积分帧构建,连续的排除从金字塔顶层到底层逐级进行,将最小SAD值与金字塔提供的一系列越来越紧的界值相比较,可以跳过不必要的SAD计算.这样,算法在保证获得与全搜索算法相同精度的前提下,计算复杂度大大降低.仿真实验结果验证了本文算法与全搜索算法和几种快速搜索算法相结合的有效性.     

Efficient multilevel successive elimination algorithms for block matching motion estimation

The authors present fast algorithms to reduce the computations of block matching algorithms, for motion estimation in video coding. Efficient multilevel successive elimination algorithms are based on the multilevel successive elimination. Efficient multilevel successive elimination algorithms consist of four algorithms. The first algorithm is given by the sum of absolute difference between the sum norms of sub-blocks in a multilevel successive elimination algorithm (MSEA) using the partial distortion elimination technique. By using the first algorithm, computations of MSEA can be reduced further. In the second algorithm, the sum of absolute difference (SAD) is calculated adaptively from large value to small value according to the absolute difference values between pixels of blocks. By using the second algorithm, the partial distortion elimination in the SAD calculation can occur early, therefore the computations of MSEA can be reduced. The second algorithm is useful not only with MSEA, but also with all kinds of block matching algorithms. In the third algorithm, the elimination level of the MSEA can be estimated. Accordingly, the computations of the MSEA related to the level lower than the estimated level can be reduced. The fourth algorithm is, first of all, to search the motion vector over the half sampled search points. At the second search, the authors search the unsampled search points around the tested search points where the motion vector may exist from the first search results. The motion estimation accuracy of the fourth algorithm is nearly 100% and the computations can be greatly reduced.     

A multilevel successive elimination algorithm for block matchingmotion estimation

An efficient algorithm is proposed to reduce the computation cost of block matching algorithms for motion estimation in video coding. Based on a new insight in block matching algorithms, we extend the successive elimination algorithm to a multilevel case. By using the sum norms of the blocks and the subblocks, tighter and tighter decision boundaries can be obtained for eliminating the search positions. The efficiency of the proposed algorithm combined with the full search algorithm and several fast search algorithms is verified by simulation results.     

Fast Multi-reference Motion Estimation via Enhanced Downhill Simplex Search

Block motion estimation can be regarded as a function minimization problem in a finite-dimensional space. Therefore, fast block motion estimation can be achieved by using an efficient function minimization algorithm instead of a predefined search pattern, such as diamond search. Downhill simplex search is an efficient derivative-free function minimization algorithm. In this paper, we proposed a fast block motion estimation algorithm based on applying the downhill simplex search for function minimization. Several enhanced schemes are proposed to improve the efficiency and accuracy, including a new initialization process, a special rounding scheme, and an early-stop error function evaluation procedure. We also extend the downhill simplex search for the multi-reference frame motion estimation problem. Experimental results show superior performance of the proposed algorithm over some existing fast block matching methods on several benchmarking video sequences.     

Efficient, robust, and fast global motion estimation for videocoding

In this paper, we propose an efficient, robust, and fast method for the estimation of global motion from image sequences. The method is generic in that it can accommodate various global motion models, from a simple translation to an eight-parameter perspective model. The algorithm is hierarchical and consists of three stages. In the first stage, a low-pass image pyramid is built. Then, an initial translation is estimated with full-pixel precision at the top of the pyramid using a modified n-step search matching. In the third stage, a gradient descent is executed at each level of the pyramid starting from the initial translation at the coarsest level. Due to the coarse initial estimation and the hierarchical implementation, the method is very fast. To increase robustness to outliers, we replace the usual formulation based on a quadratic error criterion with a truncated quadratic function. We have applied the algorithm to various test sequences within an MPEG-4 coding system. From the experimental results we conclude that global motion estimation provides significant performance gains for video material with camera zoom and/or pan. The gains result from a reduced prediction error and a more compact representation of motion. We also conclude that the robust error criterion can introduce additional performance gains without increasing computational complexity.     

一种基于硬件实现的快速运动估计半像素级搜索算法

研究了在绝对差和准则下的整像素级块匹配和半像素级块匹配的联系，对绝对差和进行了合理的数学曲线拟合，通过数学曲线来预测最小绝对差和所在半像素位置，从而得到半像素级最佳匹配矢量。分析了三种不同的凹函数预测模型，提出了一种适合硬件实现的运动估计快速半像素级搜索算法。该算法直接根据整像素级运动估计的结果来推算半像素级运动估计结果，在很大程度上降低了半像素级运动估计的运算复杂度，从而利用低码率视频编码的实时实现。试验结果表明该算法可获得较好的重建图像质量。该算法利于硬件实现，可以方便地集成到现有的视频编码器中，具有较好的实用价值。     

H.264中运动估计算法的一种硬件实现架构

提出了一种适用于H.264标准中可变块大小运动估计算法的硬件实现架构.架构中采用一维处理单元(PE)阵列来实现运动估计算法中匹配块的搜索,通过对较小子块的块间误差(SAD)的复用来计算不同大小块的块间误差.与传统的处理一个运动矢量的架构相比,这种架构在一定的时钟周期内最多可处理41个运动矢量,并且具有面积小、速度快的特点.     

VLSI Architecture of Block Matching Algorithms for Motion Estimation in High Efficiency Video Coding

High-efficiency video coding (HEVC) is a latest video coding standard and the motion estimation unit is the most important block. The work presents the different types of Matching Criteria for Block-Based Motion Estimation technique in HEVC standard. HEVC requires fast motion estimation algorithms to have better real time performance. The hardware implementation of motion estimation helps to achieve high speed though parallel processing. An improved block matching technique is designed with reduced blocks for HEVC. The proposed method has less execution time where only blocks having motion are compared for prediction computation. The searching time complexity is dependent on the number of blocks that are having motion. The searching time of frame having small motion can be reduced to 80–85% as compared to the traditional full search algorithm. In the paper, sum of absolute difference, mean square error and mean absolute difference are computed to find the best matching algorithm for HEVC. However, SAD has less computational complexity with compare to other matching criteria. The results suggest that proposed motion estimation algorithm has better performance with compare to similar previous work.

     

FPGA architecture of the LDPS Motion Estimation for H.264/AVC Video Coding

Motion estimation is a highly computational demanding operation during video compression process and significantly affects the output quality of an encoded sequence. Special hardware architectures are required to achieve real-time compression performance. Many fast search block matching motion estimation (BMME) algorithms have been developed in order to minimize search positions and speed up computation but they do not take into account how they can be effectively implemented by hardware. In this paper, we propose three new hardware architectures of fast search block matching motion estimation algorithm using Line Diamond Parallel Search (LDPS) for H.264/AVC video coding system. These architectures use pipeline and parallel processing techniques and present minimum latency, maximum throughput and full utilization of hardware resources. The VHDL code has been tested and can work at high frequency in a Xilinx Virtex-5 FPGA circuit for the three proposed architectures.     

一种改进的快速块匹配运动估计算法

为了提高运动向量估计算法的速度和精度,提出了一种改进的快速块匹配运动估计算法:依据之前宏块的运动向量,估计当前宏块各可能的运动向量对应的概率值,组成和搜索窗口同样大小的概率矩阵,并根据概率大小限制搜索的次数。仿真结果表明:与标准菱形搜索法相比,在精度略有提高的同时,有效的提高了搜索效率。     

Efficient tree structured motion estimation using successive elimination

In H.264/AVC, tree structured motion estimation enhances the coding efficiency significantly while dramatically increasing the computational complexity of block matching. In the paper, a successive elimination algorithm (SEA) is implemented in tree structured motion estimation with a simple and effective method to determine the initial motion vector, which exploits the strong correlation among the partially overlapped variable-size blocks. With identical performance to a full search algorithm, computations for block matching can be reduced to 1%-20%. Further, the SEA can be improved by incorporating two early termination conditions, then named 'Quick SEA'. Finally, a novel fast motion estimation algorithm, successive elimination diamond search (SEDS), is proposed by efficiently integrating the Quick SEA and a modified diamond search pattern. Simulation results show that the proposed Quick SEA can reduce the computational complexity of block matching by 3-5 times compared to the basic SEA. SEDS further reduces by about one-half the computations of Quick SEA. With similar rate distortion performance, 0.2%-1% block matching distortion is calculated for SEDS with corresponding speed-up factors of 100 to 500 in comparison with the full search algorithm.     

Cramer–Rao Bound for MIMO Radar Target Localization With Phase Errors

A new template matching method accelerated by an integral image is proposed. In contrast to the conventional winner-update template matching algorithm, the proposed scheme uses an integral image instead of a block sum pyramid to represent the search area. When an integral image is used, block sums on the lowest level are evaluated very fast. As a result, the speed with which nonbest candidates are rejected is nearly double that of the conventional scheme. Moreover, the proposed scheme needs less memory than the conventional approach to maintain block sums of candidates and can be easily extended to nonsquare (rectanglar) template matching.      

一种用于视频编码的块运动估计算法——块特征匹配预测搜索算法

本文提出了一种块特征匹配预测搜索ＢＦＭＰＳ算法,可以用于视频压缩的一些国际标准,如Ｈ．２６１,Ｈ．２６３,ＭＰＥＧ１,ＭＰＥＧ２,ＨＤＴＶ中,ＢＦＭＰＳ算法充分利用了序列图像的实际矢量与预测矢量之间距离的空间分布特征,中心偏置分布特性和时间上的相关特性,并采用了中止判决准则,可以明显地减少了运动搜索复杂度,ＢＦＭＰＳ算法在匹配运算中采用 简单有交的块特征匹配准则函数,相应的块匹配计算复杂度,数据读     

A Multi-Pass True Motion Estimation Scheme With Motion Vector Propagation for Frame Rate Up-Conversion Applications

This paper presents a robust true motion estimation algorithm, designated as MPMVP (Multi-pass and Motion Vector Propagation), to enhance the accuracy of the motion vector fields in frame rate up-conversion applications. The MPMVP uses a multi-pass scheme to progressively refine approximate motion vectors to true motion vectors based upon the motion information acquired in previous passes. The multi-pass motion estimation process uses a large block size to detect the motion vectors within the objects themselves and small block sizes to detect the motion vectors along the object boundaries. Actually, the block size is progressively reduced during the search process. When the motion vector of a block is considered to be sufficiently accurate for motion estimation purposes, the block is said to be converged and the local motion vector search process terminates. A novel technique, referred to as motion vector propagation, is then applied to propagate the motion vector of the converged block to its neighboring blocks. This technique not only ensures that neighboring motion vectors within the same object have a high degree of spatial correlation, but also accelerates the convergence of the motion vectors in the neighboring blocks and therefore reduces the overall computational time and expense of the multi-pass motion vector search procedure. A novel distortion criterion is proposed to enhance the tolerance of the traditional sum-of-absolute-difference measurement technique applied in the motion estimation scheme to noise and shadow effects. The experimental results demonstrate that the proposed true motion estimation algorithm outperforms the traditional full search, 3DRS and TCSBP algorithms in terms of both the smoothness of the generated motion vector fields and the visual quality of the up-converted frames.     

A fast exhaustive search algorithm for rate-constrained motionestimation

A fast exhaustive search algorithm for rate-constrained motion estimation is presented. The motion vectors are selected from a search window based on a rate-distortion criterion by successively eliminating the search positions depending on the rate constraint. The estimation performance of the proposed algorithm is identical to the performance of the rate-constrained full search algorithm, with considerable reduction in computation. Simulation results indicate that the number of matching calculations decreases as the constraint on the rate increases.     

A fuzzy search algorithm for the estimation of motion vectors

The block motion estimation/compensation techniques are efficient methods to reduce the required bitrate by eliminating temporal redundancy of the image sequence. In this paper, an efficient search algorithm for block motion estimation is presented. By using the inter-block and inter-frame fuzzy prediction, the algorithm can determine the motion vectors of image blocks quickly and correctly. According to the experimental results, our algorithm performs better than other search algorithms, such as TSS, NTSS, FSS, BBGDS, SES, PSA, GPS, and FPS in terms of seven different measures     

基于对象快速自适应的混合搜索运动估计方法

提出一种基于对象的快速自适应的混合运动估计方法，利用同一对象的运动矢量之间的相关性，根据搜索过程中块匹配的程度，减小或增大搜索范围，实验表明，该算法既降低计算量，又保持了较好的图像质量。     

Efficient Hierarchical Motion Estimation Algorithm and Its VLSI Architecture

This paper addresses the development and hardware implementation of an efficient hierarchical motion estimation algorithm, HMEA, using multiresolution frames to reduce the computational complexity. Excellent estimation performance is ensured using an averaging filter to downsample the original image. At the smallest resolution, the least two motion vector candidates are selected using a full-search block matching algorithm. At the middle level, these two candidate motion vectors are employed as the center points for small range local searches. Then, at the original resolution, the final motion vector is obtained by performing a local search around the single candidate from the middle level. HMEA exhibits regular data flow and is suitable for hardware implementation. An efficient VLSI architecture that includes an averaging filter to downsample the image and two 2-D semisystolic processing element arrays to determine the sum of absolute difference in pipeline is also presented. Simulation results indicate that HMEA is more area-efficient and faster than many full-search and multiresolution architectures while maintaining high video quality. This architecture with 59K gates and 1393 bytes of RAM is implemented for a search range of [ $-$16.0, $+$15.5].