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.     

Edge oriented block motion estimation for video coding

Intensity-based block motion estimation and compensation algorithms are widely used to exploit temporal redundancies in video coding, although they suffer from several drawbacks. One of the problems is that blocks located on boundaries of moving objects are not estimated accurately. It causes poor motion-compensated prediction along the moving edges to which the human visual system is very sensitive. By considering the characteristics of block motions for typical image sequences, an intelligent classifier is proposed to separate blocks containing moving edges to improve on conventional intensity-based block matching approaches. The motion vectors of these blocks are computed using edge matching techniques, so that the motion-compensated frames are tied more closely to the physical features. The proposed method can then make use of this accurate motion information for edge blocks to compute the remaining non-edged blocks. Consequently, a fast and efficient block motion estimation algorithm is developed. Experimental results show that this approach gives a significant improvement in accuracy for motion-compensated frames and computational complexity, in comparison with the traditional intensity-based block motion estimation methods     

Background foreground boundary aware efficient motion search for surveillance videos

The huge amount of data in surveillance video coding demands high compression rates with lower computational requirements for efficient storage and archival. The motion estimation is a very time-consuming process in the traditional video coding framework, and hence reducing computational complexity is a pressing task, especially for surveillance videos. The presence of significant background proportion in surveillance videos makes its special case for coding. The existing surveillance video coding methods propose separate search mechanisms for background and foreground regions. However, they still suffer from misclassification and inefficient search strategies since it does not consider the inherent motion characteristics of the foreground regions. In this paper, a background-foreground-boundary aware block matching algorithm is proposed to exploit special characteristics of the surveillance videos. A novel three-step framework is proposed for boundary aware block matching process. For this, firstly, the blocks are categorized into three classes, namely, background, foreground, and boundary blocks. Secondly, the motion search is performed by employing different search strategies for each class. The zero-motion vector-based search is employed for background blocks. Whereas, to exploit fast and directional motion characteristics of the boundary and foreground blocks, the eight rotating uni-wing diamond search patterns are proposed. Thirdly, the speed-up is achieved through the novel region-based sub-sampled structure. The experimental results demonstrate that two to four times speed-up over existing methods can be achieved through this scheme while maintaining better matching accuracy.     

H.264视频编码系统中多参考帧的选择算法研究

H.264/MPEG-4 AVC中引入多参考帧运动补偿来提高视频编码性能,由此产生的多参考帧运动估计(MRF-ME)却带来了巨大的运算代价.本文提出一种基于快速分层特征匹配的运动估计策略(HFM-ME)来加速多参考帧的匹配过程.HFM-ME策略通过引入一种符号截断特征(STF)将块匹配被分解为均值匹配和二进制相位匹配.实验结果表明,与传统的块匹配ME相比,HFM-ME在保持匹配性能的同时显著提高了运算速度.     

机动目标的逆合成孔径雷达成像原理与算法

对于非合作的机动目标,由于目标相对于雷达射线的姿态和转速难以测定,而且是时变的,因而给逆合成孔径雷达(ISAR)成像造成较大困难.本文讨论了这种情况下成像的一般原理,并对机动性不太大,散射点子回波多普勒变化满足一阶近似条件时,提出了实用算法.实测数据的处理结果说明新算法是可行的.     

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.

     

Content-based image retrieval using block-constrained fractalcoding and nona-tree decomposition

Fractal coding has been proved useful for image compression. In fractal coding, an image is represented by a number of self-transformations (fractal code) by which an approximation of the original image can be reconstructed. The authors present a block-constrained fractal coding scheme and a nona-tree decomposition based matching strategy for content-based image retrieval. In the coding scheme, an image is partitioned into non-overlapped blocks with a size close to that of a query iconic image. The fractal code is generated for each block independently. In the similarity measure of the fractal code, an improved nona-tree decomposition scheme is adopted to avoid matching the fractal code globally in order to reduce computational complexity. The experimental results show that the authors' coding scheme and matching strategy are useful for image retrieval, and compare favourably with two other methods tested in terms of storage usage and computing time     

Fast full search motion estimation algorithm using early detection of impossible candidate vectors

To reduce the amount of computations for a full search (FS) algorithm for fast motion estimation, we propose a new and fast FS motion estimation algorithm. The computational reduction of our FS motion estimation algorithm comes from fast elimination of impossible motion vectors. We obtain faster elimination of inappropriate motion vectors using efficient matching units from localization of a complex area in image data. In this paper, we show three properties in block matching of motion estimation. We suggest two fast matching scan algorithms: one from adaptive matching scan and the other from fixed dithering order. Experimentally, we remove the unnecessary computations by about 30% with our proposed algorithm compared with the conventional fast FS algorithms.     

Fast full search motion estimation algorithm using various matchingscans in video coding

To reduce the amount of computation in a full search (FS) algorithm for fast motion estimation, we propose a novel and fast FS motion estimation algorithm. The computational reduction without any degradation in the predicted image comes from fast elimination of impossible motion vectors. We obtain faster elimination of inappropriate motion vectors using efficient matching units from localization of the complex area in image data. We show three properties in block matching of motion estimation. We suggest two fast matching scan algorithms, one from adaptive matching scan and the other from fixed dithering order. Experimentally, we remove the unnecessary computations by about 30% with our proposed algorithm compared to conventional fast matching scan algorithms     

Video Block Motion Estimation Based on Gray-Code Kernels

Motion in modern video coders is estimated using a block matching algorithm that calculates the distance and direction of motion on a block-by-block basis. In this paper, a novel fast block-based motion estimation algorithm is proposed. This algorithm uses an efficient projection framework that bounds the distance between a template block and candidate blocks. Fast projection is performed using a family of highly efficient filter kernels-the gray-code kernels-requiring only 2 operations per pixel per kernel. The projection framework is combined with a rejection scheme which allows rapid rejection of candidate blocks that are distant from the template block. The tradeoff between computational complexity and quality of results can be easily controlled in the proposed algorithm; thus, it enables adaptivity to image content to further improve the results. Experiments show that the proposed adaptive algorithm outperforms other popular fast motion estimation algorithms.     

An effective mesh-based motion compensation technique for video coding

The block-matching algorithm is the most popular motion compensation technique in video coding. However, it cannot provide acceptable quality at very low bit rate. In this paper, a new mesh-based motion compensation method is proposed to attack the problem. First, a regular non-uniform mesh, which has regular structure with variable patch size, is presented. The patch size is varied according to motion activity of a video sequence. Next, a weighted interpolation block matching is developed to improve the estimate accuracy of displacements of grid points. It utilizes the motion correlation between a grid point and its associated patches. Finally, based on the new mesh and motion estimation scheme, an efficient motion compensation algorithm is developed. When compared to the conventional motion compensation techniques, the proposed method improves performance significantly with lower computational complexity and overhead information bits.     

Motion-based region growing segmentation of image sequences

This paper proposes a motion-based region growing segmentation scheme for the object-based video coding, which segments an image into homogeneous regions characterized by a coherent motion. It adopts a block matching algorithm to estimate motion vectors and uses morphological tools such as open-close by reconstruction and the region-growing version of the watershed algorithm for spatial segmentation to improve the temporal segmentation. In order to determine the reliable motion vectors, this paper also proposes a change detection algorithm and a multi-candidate pro- screening motion estimation method. Preliminary simulation results demonstrate that the proposed scheme is feasible. The main advantage of the scheme is its low computational load.     

一种高效的运动补偿三维小波视频编码方案

该文提出了一种高效的运动补偿三维小波视频编码方案。该方案采用运动补偿时域分析技术,以有效去除视频序列中存在的时间冗余。然后,基于视频序列的运动特征,自适应确定帧组结构,在提高编码效率的同时降低内存需求和运算复杂度。最后,根据小波图像系数特性,采用基于四叉树分裂的小波图像编码方法对三维时/空子带进行编码,以获得更高的压缩效率。实验结果表明,与其它运动补偿三维小波视频编码方法相比,该文提出的编码方案能够获得更好的性能。     

数字稳像中的快速和鲁棒运动估计研究

 提出了一种用于数字图像稳定的快速和鲁棒运动估计方法.在图像的运动估计中,首先采用一种预判局部宏块的算法：在计算运动矢量前对宏块的梯度信息进行分析以避免误匹配,通过减少参与计算的宏块数目提高处理速度;其次,提出快速估计宏块运动矢量的方法,用改进的序贯相似性算法(SSDA)进行块匹配,以提高运动矢量的计算速度;然后采用LMedS估计法去除不精确的宏块运动向量,用最小二乘法求解出最优的模型参数.实验结果表明了该方法的精确性、快速性和鲁棒性.     

一种基于H．264的有效运动估计算法

运动估计算法是实时视频编解码技术的研究重点，高精度的匹配和补偿可以减少预测误差，提高视频图像的压缩效果．为降低在视频编码标准H．264中运动估计的高计算复杂度问题，提出了采用一种基于节点模型的可变形块匹配运动估计算法来搜索最佳运动矢量．该算法充分利用了H．264运动矢量的的统计特性和相关性，并采用基于像素差值分类的运动估计匹配准则．实验表明，在编码性能损失很小的条件下，该算法有效降低了视频压缩编码中运动估计的运算复杂度．     

Combining fractal image compression and vector quantization

In fractal image compression, the code is an efficient binary representation of a contractive mapping whose unique fixed point approximates the original image. The mapping is typically composed of affine transformations, each approximating a block of the image by another block (called domain block) selected from the same image. The search for a suitable domain block is time-consuming. Moreover, the rate distortion performance of most fractal image coders is not satisfactory. We show how a few fixed vectors designed from a set of training images by a clustering algorithm accelerates the search for the domain blocks and improves both the rate-distortion performance and the decoding speed of a pure fractal coder, when they are used as a supplementary vector quantization codebook. We implemented two quadtree-based schemes: a fast top-down heuristic technique and one optimized with a Lagrange multiplier method. For the 8 bits per pixel (bpp) luminance part of the 512kappa512 Lena image, our best scheme achieved a peak-signal-to-noise ratio of 32.50 dB at 0.25 bpp.     

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.     

一种快速分形图像编码算法

目前,分形图像编码技术最主要的缺点仍然是编码时间太长.因此,如何提高分形图像编码速度成为当前分形图像编码技术的研究热点.本文从分形图像编码通用公式推导出一个不等式,利用此不等式,可以预先排除大量不可能与值域块匹配的定义域块,从而减少值域块与定义域块的匹配计算,以此达到缩短编码时间的目的.实验结果表明,在解码图像质量基本不变情况下,本文的方法所使用的编码时间比Fisher方案所需的编码时间减少了很多.     

Isometry-Based Shape-Adaptive Fractal Coding for Images

Fractal image coding is an effective method to eliminate the image redundancy through piecewise self-transformability. The fractal code consists of a set of contractive affine transforms. To improve the performance when a range block experiences large error, we usually partition the range block into square or nonsquare subrange blocks for two- or multilevel fractal coding. In this paper, we find an inherent property of fractal coding that can be used to decide the edge orientation of a range block. Then this property is used for shape-adaptive fractal coding (SAFC). In SAFC, the top-level range block is partitioned into square or nonsquare (rectangle or triangle) subrange blocks for multilevel fractal encoding. Here, the maximum size of the range block can be the same as that of the whole image size while the minimum size is 4×4. In SAFC, no additional computations are required to obtain the edge orientation of a range block. Instead, we propose an edge-orientation detector, where the edge orientation of a range block is obtained during the fractal encoding process. According to our simulation results, SAFC can reduce the bit rate requirement of the conventional fractal coding scheme.     

Fast full-search block-matching algorithm for motion-compensatedvideo compression

This paper proposes a fast block-matching algorithm that uses three fast matching error measures, besides the conventional mean-absolute error (MAE) or mean-square error (MSE). An incoming reference block in the current frame is compared to candidate blocks within the search window using multiple matching criteria. These three fast matching error measures are established on the integral projections, having the advantages of being good block features and having simple complexity in measuring matching errors. Most of the candidate blocks can be rejected only by calculating one or more of the three fast matching error measures. The time-consuming computations of MSE or MAE are performed on only a few candidate blocks that first pass all three fast matching criteria. Simulation results show that a reduction of over 86% in computations is achieved after integrating the three fast matching criteria into the full-search algorithm, while ensuring optimal accuracy