一种方向延伸的快速运动搜索算法

利用图像块运动的方向特性,减小帧间编码中运动估计的运算量.该算法利用小模板钻石搜索,先确定中心检测点到最小块失真检测点为搜索方向,然后在此方向上不断延伸一个检测点进行块失真匹配,直至下一个检测点的块失真大于当前检测点的块失真.接着以当前检测点作为中心检测点,重复以上操作,直至中心检测点为最优检测点,结束搜索.搜索中利用自适应门限提前退出搜索.搜索速度比钻石搜索算法提高了20%～60%.     

引入搜索预测与阈值决策的改进菱形运动估计算法

为了提高视频的压缩效率,在传统菱形搜索算法基础上提出一种改进菱形搜索算法.该算法通过引入动态阈值,在起始搜索点预测、菱形搜索模式和搜索中止算法方面进行了优化,减少了SAD计算的内部冗余和搜索区域中不相关的块匹配计算,同时采用自适应搜索模式选择技术减少运输复杂度.实验结果表明:提出的改进菱形搜索算法适合各种运动类型的视频序列,特别适用于运动变化剧烈的序列,相比于FS算法,能够在PSNR值和码率值极其接近于FS算法的情况下对所有序列的MET减少约95％,大大减少运动估计时间.     

基于DS-CDS的改进运动估计算法及实验

为了提高视频的压缩效率,在菱形搜索算法和十字菱形搜索算法的基础上,结合实际运动图像中的运动向量以水平方向向量为主的特点,提出了一种利用偏水平十字模板搜索与偏向双菱形模板搜索相结合的改进搜索算法。为检验本文改进算法的效果进行了对比实验,结果表明:本文提出的基于偏水平十字及偏向双菱形搜索法适合各种运动类型的视频序列,更适用于运动变化剧烈的序列,并且能够在PSNR值和BR值接近最优水平时,大大减少运动估计时间,相比于FS算法,对QCIF格式图像的运动估计时间减少约95%,对CIF格式图像的运动估计时间减小约94%。     

基于H.264的改进运动估计算法及其性能对比实验研究

为提高视频压缩效率,在传统搜索算法的基础上,结合实际运动图像中的运动向量,以水平方向向量为主要特点,提出一种利用偏水平十字模板搜索与偏向双菱形模板搜索相结合的改进搜索算法。该改进算法可以根据运动向量的特点来减少模板的搜索点数,达到提高视频压缩效率、节省运动估计时间的目的。性能对比实验结果表明:该改进算法适合各种运动类型的视频序列,尤其适用于运动变化剧烈的序列,并且能够在PSNR值和码率值极其接近FS算法的情况下,对QCIF格式图像的运动估计时间(MET)减少约95%,对CIF格式图像的运动估计时间(MET)减小约94.5%,大大减少运动估计时间。     

基于半八边形模板的运动估计算法?

H.264视频编码标准中,运动估计占用了编码器极大的运算量.针对 H.264快速块匹配,本文提出了一种基于半八边形搜索模板的运动估计算法.该方法使用一个十字形模板来预测搜索方向,依据绝对差和(Sum of Absolute Differences, SAD)分布的方向性自适应地选取半八边形模板进行搜索,在搜索过程中,判断 SAD 值下降最快的方向精确定位匹配点,减少搜索点之间的冗余,提高搜索速度.理论分析表明该算法同经典六边形算法相比可以减少搜索点数.实验结果显示,在重建图像质量接近全搜索的同时,新算法减少了运动估计20%–30%的运算量.     

一种改进的菱形搜索算法

DS (Diamond Search,DS)算法曾被MPEG4标准采用,是目前公认的一种较好的搜索算法.但当运动矢量较小时,菱形搜索算法速度较慢.提出了一种改进的菱形搜索(Improved Diamond Search,IDS)算法,加入了粗定位和强化的半路停止操作.大量的车辆跟踪实验表明,IDS算法在保证搜索性能的基础上增加了搜索速度,为模板匹配提供了更加有效的技术支持.更有对比实验揭示了该算法对轨迹突变的不敏感性.     

MPEG-4形状编码中的自适应二值运动估计算法

运动估计占据TMPEG-4形状编码90％以上的运算量，本文依据MPEG-4中形状信息的自身特性，提出了自适应二值运动估计算法。算法首先扫描参考帧，得出其有效搜索区域——边界掩模。在匹配运算时使用1bit的异或运算代替原有的加法运算。在搜索中根据二值Alpha块的运动特性自适应的采用不同的搜索模板进行搜索，对于静止点直接中止搜索。兼顾了搜索速度和精度。实验结果表明，在码字长度相仿的情况下，本算法的平均搜索点数仅相当于MPEG-4原有搜索算法的5％，有效提高了形状编码速度。     

基于快速运动估计算法UMHexagonS的研究

UMHexagonS算法已经被视频编码标准H.264正式采纳作为整像素的快速运动估计算法。该算法的运算量相对于快速全搜索算法可节约90%以上,同时能够保持较好的率失真性能。本文结合JM10.2的源代码对UMHexagonS算法进行了分析,并对该算法进行了改进。通过利用运动矢量间的相关性,采用一种新的自适应的非对称十字形模板来代替原算法中的非对称十字形模板,并将改进的算法在JM10.2测试模型上进行了验证。实验结果表明,本文建议的方法在保证编码性能的同时,可以有效减少运动估计所需要的时间。     

自适应六边形-菱形运动估计算法及其在H.264中应用

运动估计是视频图像编码中运算量很大的部分,也是影响系统实时性能的瓶颈。为了减少图像编码的运算量,文章介绍和分析了用于视频编码标准H.264的基于六边形的搜索算法(HS),在此基础上根据H.264多模式的运动估计提出自适应六边形-菱形整像素算法,它体现了粗定位和准确定位的并行处理思想,仿真结果表明在获得与HS快速算法相当的图像质量和信噪比的情况下,可提高H.264视频编码的速度和效率。     

面向运动估计器硬件实现的加权块匹配检测算法

在各种视频处理算法中，运动补偿型算法大大提高了各种视频处理效果。运动估计器的硬件实现是各种运动补偿视频处理算法在实际系统中运用的关键。由于块匹配运动估计算法较低的运算复杂度和硬件实现难度以及块匹配检测标准函数很高的调用频率，已经广泛应用到各种实际系统中。文中提出了加权最小最大误差的匹配检测标准，能够降低运动估计器的运算复杂度，减少估计器的硬件面积，提高硬件速度，而且能够降低递归搜索块匹配运动估计算法固有误差传递带来的负面影响。     

A new fast block matching algorithm based on complexity‐distortion optimization

Most fast block matching algorithms ignore the efficiency in motion compensation within each checking step. In order to achieve better‐compensated performance, the limited computational complexity should be allocated more carefully into each block. It means that the fast block matching algorithm can be viewed as a kind of rate‐distortion optimization problem. The complexity‐distortion optimal fast block matching algorithm should find the maximized quality of the compensated image under a target computational complexity. In order to approach the optimal complexity‐distortion solution, some strategies are developed. For example, a domination‐based motion vector prediction technique is developed to set the initial motion vector for each block. A predictive complexity‐distortion benefit list is established to predict the compensated benefit for each block. Also, a three‐level pattern searching is employed to check the candidate motion vector. Experimental results show that our proposed algorithm outperforms significantly the three‐step search. For example, in “Salesman,” the average checkpoints for one block is 33 by using the three‐step search. The average checkpoint is 1.75 by using our proposal algorithm under the same average PSNR condition. © 2002 Wiley Periodicals, Inc. Int J Imaging Syst Technol 12, 63–67, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ima.10012     

Efficient architecture for global elimination algorithm for H.264 motion estimation

This paper presents a fast block matching motion esti mation algorithm and its architecture. The proposed architecture is based on Global Elimination (GE) Algorithm, which uses pixel averaging to reduce complexity of motion search while keeping performance close to that of full search. GE uses a preprocessing stage which can skip unnecessary Sum Absolute Difference (SAD) calculations by comparing minimum SAD with sub-sampled SAD (SSAD). In the second stage SAD is computed at roughly matched candidate positions. GE algorithm uses fixed sub-block sizes and shapes to compute SSAD values in preprocessing stage. Complexity of this GE algorithm is further reduced by adaptively changing the sub-block sizes depending on the macro-block features. In this paper adaptive Global Elimination algorithm has been implemented which reduces the computational complexity of motion estimation algorithm and thus resulted in low power dissipation. Proposed architecture achieved 60% less number of computations compared to existing full search architecture and 50% high throughput compared to existing fixed Global Elimination Architecture.     

Adaptive Order Cross–Square–Hexagonal search and fuzzy tangential-weighted trade-off for H.264 in motion estimation

In recent years, various algorithms have been proposed to attain low computational complexity in motion estimation of the image sequence coding based on block matching. This paper presents an Adaptive Order Cross–Square–Hexagon (AOCSH) search algorithm, which employs a smaller cross-shaped pattern before the first step of a square pattern and replaces the square-shaped pattern with the hexagon search patterns in subsequent steps. The proposed search patterns aid in finding the best matching block, without much consideration of the vast number of search points. Here, fuzzy tangent-weighted function is also proposed to evaluate the matching points using the rate and the distortion parameters. The proposed methods are effectively applied to the block estimation process to handle the objectives of visual quality and distortion. The performance of the proposed AOCSH approach is compared to the existing methods, such as AOSH, H.264 and elastic models, using the structural similarity index (SSIM) and the peak signal to noise ratio (PSNR). From the analysis, it can be seen that the proposed approach attains the maximum SSIM of 0.99 and maximum PSNR of 40. 92 dB with reduced computation time of 3.28 s.     

Novel fast block motion estimation using diamond‐arc‐hexagon search patterns

Abstract

This work presents a novel block motion estimation (ME) approach, diamond‐arc‐hexagon search (DAHS), which uses diamond, arc, and hexagon search patterns to accomplish the fast searching process. According to the characteristic of the center‐based motion vector distribution for the real‐world video sequence, DAHS employs a small diamond pattern extended hexagon search to refine the central area search. Furthermore for estimation in large motion situations, the strategy of the large diamond‐to‐arc search can preserve good performance. Experimental results indicate that DAHS is suitable for both (quasi‐) stationary and large motion searches. DAHS outperforms the efficient three‐step (E3SS) and hexagon‐based search (HEXBS) in prediction quality, and improves the searching speed about 9% compared to E3SS. The proposed algorithm was tested using several sequences and delivered excellent performance in search speed and prediction of video quality. The DAHS can be applied to real‐time video processes, such as H.264/MPEG‐4 advanced video coding (AVC) and scalable video coding (SVC).     

VLSI design for MPEG-4 shape coding using a contour-based binary motion estimation algorithm

An efficient architecture with the fast algorithm for MPEG-4 shape coding is proposed. The authors apply the fast shape coding algorithm, with contour-based binary motion estimation (CBBME), which is based on the properties of a boundary mask. By using the block-matching motion estimation and the extended approach on centre-biased motion vector distribution with shrinking of the search range, a large number of search points in BME can be skipped. Based on this algorithm, a dedicated architecture design using the proposed CBBME algorithm is developed. With certain optimisation and design considerations, the memory access and processing cycles can be reduced. The average number of clock cycles for the processing of one binary alpha block is only 1708, which is only 56% of the previous design. In addition, a prototyping chip for shape coding is implemented and verified. The die area is 2.4 x 2.4 mm² with TSMC 0.18 μm CMOS technology and the maximum clock frequency is 53 MHz.     

Reused sad for partial search area in efficient three‐step search algorithm

Abstract

In real‐time applications, three‐step search (TSS) is always preferred because it has a regular search pattern. However, it may lose its performance in coding video sequences with small motion. To overcome this drawback, some fast search algorithms are proposed, for example, new three‐step search (NTSS) and efficient three step search (ETSS). In this paper, a more effective fast search algorithm called region‐split three‐step search (RSTSS) is proposed. In addition to the feature of a regular search pattern, the RSTSS splits the search region into four sub‐regions and enters only one of the sub‐regions to search for the best motion vector. The main idea used in the RSTSS is to reuse the sum of absolute difference (SAD) values of the 9 points on a 9 ×9 grid. Experimental results show that the RSTSS performs better than the ETSS in terms of the number of checking points. It can reduce the number of checking points nearly 19% on average and sacrifices only a little mean squared error. Most of all, the RSTSS retains a regular searching pattern that is suitable for hardware implementation.     

一种复杂背景下扩展目标搜索方法

目标搜索的关键在于捕获到感兴趣的目标。在复杂背景下,利用灰度特征、区域特征、纹理特征难以对目标进行有效搜索,而运动特征是可利用的有效特征。提出了一种基于运动矢量分类的扩展目标搜索算法,将前一帧图像均匀分块,对每块在其周围与当前帧图像块匹配,得到每块的运动矢量,依据目标块与背景块的运动方向差异剔除背景块,再依据目标块的集中性及其运动矢量的相等特性提取目标块,目标块中心的平均即为目标的近似形心。实验表明,该方法能够有效地对复杂背号下扩展目标进行搜索。     

Finding a cluster of points and the grey pattern quadratic assignment problem

In this paper we propose a model which aims at selecting a tight cluster from a set of points. The same formulation applies also to the grey pattern problem where the objective is to find a set of black dots in a rectangular grid with a given density so that the dots are spread as evenly as possible. A branch and bound algorithm and five heuristic approaches are proposed. Computational results demonstrate the efficiency of these approaches. Seven grey pattern problems are solved to optimality and for eight additional grey pattern problems the best known solution is improved. The cluster problem on a network is solved for 40 problems with the number of points ranging between 100 and 900 and the size of the cluster ranging between 5 and 200. Twenty one problems were solved optimally and the remaining 19 problems were heuristically solved in a very short computer time with excellent results.     

Classified variable-block-size motion estimation algorithm for image sequence coding

In recent years, the variable-block-size (VBS) motion estimation technique has been widely employed to improve the performance of the block-matching algorithm (BMA). In VBS, the block size is varied according to the type of motion. The VBS is known to be very efficient for areas containing complex motions. However, it requires a large number of computations. In this article, a new VBS motion estimation algorithm, called the classified variable block size (CVBS), is proposed to overcome this problem. The algorithm classifies the input blocks into three categories: background, shade motion and edge motion. According to the characteristics of the classified blocks, various motion estimation techniques are then used to improve the coding performance. The performance of VBS and CVBS based on the coding efficiency is investigated. It is shown that the CVBS algorithm requires about one fifth to one seventh of the computations needed by the conventional VBS algorithm. © 1996 John Wiley & Sons, Inc.