Fast multiresolution motion estimation algorithms for wavelet-based scalable video coding

Motion estimation and compensation in wavelet domain have received much attention recently. To overcome the inefficiency of motion estimation in critically sampled wavelet domain, the low-band-shift (LBS) method and the complete-to-overcomplete discrete wavelet transform (CODWT) method are proposed for motion estimation in shift-invariant wavelet domain. However, a major disadvantage of these methods is the computational complexity. Although the CODWT method has reduced the computational complexity by skipping the inverse wavelet transform and making the direct link between the critically sampled subbands and the shift-invariant subbands, the full search algorithm (FSA) increases it. In this paper, we proposed two fast multiresolution motion estimation algorithms in shift-invariant wavelet domain: one is the wavelet matching error characteristic based partial distortion search (WMEC-PDS) algorithm, which improves computational efficiency of conventional partial distortion search algorithms while keeping the same estimate accuracy as the FSA; another is the anisotropic double cross search (ADCS) algorithm using multiresolution-spatio-temporal context, which provides a significantly computational load reduction while only introducing negligible distortion compared with the FSA. Due to the multiresolution nature, both the proposed approaches can be applied to wavelet-based scalable video coding. Experimental results show the superiority of the proposed fast motion estimation algorithms against other fast algorithms in terms of speed-up and quality.     

Fast and efficient motion estimation using diamond zonal-based algorithms

Motion estimation has always been an important part of video encoding systems because it can reduce temporal redundancy effectively and thus has significant impact on the bit rate and the output visual quality of the encoded sequence. Unfortunately, when using the brute-force full search algorithm, motion estimation consumes a very large portion of the encoding time. Previously, several algorithms have been proposed which try to reduce complexity, usually, with a significant loss in visual quality. Based on the diamond zonal search framework we introduced recently, we propose in this paper a novel algorithm called advanced diamond zonal search (ADZS), which was submitted to and well received by the Moving Pictures Experts Group (MPEG) standard committee for possible inclusion as an encoder optimization tool. ADZS was criticized in MPEG for using fixed thresholds, which may not be suitable for all video sequences. To address this issue, we further propose a threshold-adaptive version called threshold-adaptive advanced diamond zonal search (TAADZS). Simulation results verify the superior performance of ADZS and TAADZS over other fast algorithms and the robustness of TAADZS over ADZS.This project has been supported by the Research Grants Council of the Hong Kong Special Administrative Region, China (project no. HKUST6057/99E) and the Hong Kong Telecom Institute of Information Technology. Parts of this paper have been previously published in conference proceedings.     

Fast motion estimation algorithm based on spatio-temporal correlation and direction of motion vectors

Suggested is a simple scheme that includes spatio-temporal neighbourhood information for obtaining better estimates of motion vectors. The estimated motion vector is chosen as initial search centre which is found closer to the global minimum. The final search pattern is adaptive and is based on the direction of the predicted motion vector. Experimental results show that the proposed algorithm enhances the accuracy of the predicted image and reduces the computational requirement compared to other approaches     

Fast algorithms for single frequency estimation

In this paper, some new estimators of the frequency of a single complex sinusoid are presented. The rotate-add-decimate (RAD) method of Crozier is first refined to more closely approach the Cramer-Rao Bound (CRB). An additional modification yields an unbiased estimator (ERAD) that essentially achieves the CRB above a signal-to-noise ratio (SNR) threshold comparable to that of RAD. In addition, this estimator is proven to achieve the CRB for high SNR. The ERAD method requires approximately 2N complex multiply-adds and log/sub 2/N arctangents. A modified ERAD (MERAD) is proposed that matches the SNR threshold and computational complexity of the RAD method (approximately 3N complex multiply-adds and log/sub 2/N arctangents) but achieves the CRB for high SNR.     

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.     

运动估计算法分析

对常用的运动补偿图像算法（如全搜索法、三步法、共轭方向搜索法、两维对数下降法等）从各个方面进行了比较,最终选出最快、最准确的算法-两步搜索法。     

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     

Fast motion estimation for H.264

Several specific features have been incorporated into Motion estimation (ME) in H.264 coding standard to improve its coding efficiency. However, they result in very high computational load. In this paper, a fast ME algorithm is proposed to reduce the computational complexity. First, a mode discriminant method is used to free the encoder from checking the small block size modes in homogeneous regions. Second, a condensed hierarchical block matching method and a spatial neighbor searching scheme are employed to find the best full-pixel motion vector. Finally, direction-based selection rule is utilized to reduce the searching range in sub-pixel ME process. Experimental results on commonly used QCIF and CIF format test sequences have shown that the proposed algorithm achieves a reduction of 88% ME process time on average, while incurring only 0.033 dB loss in PSNR and 0.50% increment on the total bit rate compared with that of exhaustive ME process, which is a default approach adopted in the JM reference software.     

Fast motion estimation for surveillance video compression

In this article, novel approaches to perform efficient motion estimation specific to surveillance video compression are proposed. These includes (i) selective (ii) tracker-based and (iii) multi-frame-based motion estimation. In selective approach, motion vector search is performed for only those frames that contain some motion activity. In another approach, contrary to performing motion estimation on the encoder side, motion vectors are calculated using information of a surveillance video tracker. This approach is quicker but for some scenarios it degrades the visual perception of the video compared with selective approach. In an effort to speed up multi-frame motion estimation, we propose a fast multiple reference frames-based motion estimation technique for surveillance videos. Experimental evaluation shows that significant reduction in computational complexity can be achieved by applying the proposed strategies.     

Image motion estimation algorithms using cumulants

A class of algorithms is presented that estimates the displacement vector from two successive image frames consisting of signal plus noise. In the model, the signals are assumed to be either non-Gaussian or (quasistationary) deterministic; and, via a consistency result for cumulant estimators, the authors unify the stochastic and deterministic signal viewpoints. The noise sources are assumed to be Gaussian (perhaps spatially and temporally correlated) and of unknown covariance. Viewing image motion estimation as a 2D time delay estimation problem, the displacement vector of a moving object is estimated by solving linear equations involving third-order auto-cumulants and cross-cumulants. Additionally, a block-matching algorithm is developed that follows from a cumulant-error optimality criterion. Finally, the displacement vector for each pel is estimated using a recursive algorithm that minimizes a mean 2D fourth-order cumulant criterion. Simulation results are presented and discussed.     

快速稳健的背景运动场估计方法

从运动背景中检测与跟踪运行目标是计算机视觉研究领域的热点,其中的困难之一是消除运动背景的影响,提出一种基于均匀稀疏采样减少仿射变换参数估计计量的快速方法,并且利用Huber函数对误差的敏感度不同的特性,使得背景的仿射参数估计过程只对背景像素点敏感,减少了前景运动物体对参数估计造成的误差,提高参数估计的精度。     

Fast capacity estimation algorithms for manets using directional antennas

In this letter,capacity estimation for Mobile Ad hoc NETworks (MANETs) using direc- tional antennas are studied.Two Matrix-based Fast Calculation Algorithms (MFCAs) are proposed to estimate the network capacity in a network scenario in which there is no channel sharing among multiple sessions and traffic is sensitive to delay with an end-to-end delay constraint.The first algo- rithm MFCA-1 is used to estimate network capacity in a situation where all links have the same delay. It estimates the maximum number of k-hop sessions in a network based on the k-hop adjacency matrix of the network.The second algorithm MFCA-2 is used to estimate network capacity in a situation where different links may have different delays.It calculates the maximum number of sessions in a network with an end-to-end delay constraint based on the adjacency matrix and the link-delay matrix of the network.Numerical and simulation results show that both MFCA-1 and MFCA-2 can calculate network capacity much faster than the well-known Brute-Force Search Algorithm (BFSA) but with the same accuracy.     

A dynamic search pattern motion estimation algorithm using prioritized motion vectors

Motion estimation is one of the critical parts in video compression standards with a high computational load. Many motion estimation algorithms have been developed to reduce the number of search points compared to a full-search algorithm without losing the quality considerably. Most of them use fixed search patterns in their first step which may suffer from trapping into local minima or searching unnecessary blocks due to inappropriate size and type of search patterns. In this paper, a new dynamic search pattern using motion vectors of spatial and temporal neighboring blocks is proposed. The motion vectors of neighboring blocks are prioritized, in order to efficiently use of halfway stop technique. The simulation results indicate that proposed algorithm is very close to the full-search algorithm in quality, compared to other rivals. Moreover, the average number of searches is often less than other algorithms.     

一种适用于AVS-M的自适应快速运动估计算法

为了减小移动视频编码标准(AVS-M)中运动估计模块的复杂度,提出了一种快速、有效的块匹配运动估计算法.该算法充分利用了视频图像中运动矢量场的中心偏置特性和时空相关性,根据运动类型自适应的选择搜索起点和搜索策略,结合改进的搜索模板和高效搜索中止准则,有效地降低了运动估计的运算量.实验结果表明,该算法在保证搜索精度的同时,大大减少了搜索点数.     

Fast adaptive algorithms for AR parameters estimation using higherorder statistics

Time-varying statistics in linear filtering and linear estimation problems necessitate the use of adaptive or time-varying filters in the solution. With the rapid availability of vast and inexpensive computation power, models which are non-Gaussian even nonstationary are being investigated at increasing intensity. Statistical tools used in such investigations usually involve higher order statistics (HOS). The classical instrumental variable (IV) principle has been widely used to develop adaptive algorithms for the estimation of ARMA processes. Despite, the great number of IV methods developed in the literature, the cumulant-based procedures for pure autoregressive (AR) processes are almost nonexistent, except lattice versions of IV algorithms. This paper deals with the derivation and the properties of fast transversal algorithms. Hence, by establishing a relationship between classical (IV) methods and cumulant-based AR estimation problems, new fast adaptive algorithms, (fast transversal recursive instrumental variable-FTRIV) and (generalized least mean squares-GLMS), are proposed for the estimation of AR processes. The algorithms are seen to have better performance in terms of convergence speed and misadjustment even in low SNR. The extra computational complexity is negligible. The performance of the algorithms, as well as some illustrative tracking comparisons with the existing adaptive ones in the literature, are verified via simulations. The conditions of convergence are investigated for the GLMS     

Fast motion estimation using bidirectional gradient methods

Gradient-based motion estimation methods (GMs) are considered to be in the heart of state-of-the-art registration algorithms, being able to account for both pixel and subpixel registration and to handle various motion models (translation, rotation, affine, and projective). These methods estimate the motion between two images based on the local changes in the image intensities while assuming image smoothness. This paper offers two main contributions. The first is enhancement of the GM technique by introducing two new bidirectional formulations of the GM. These improve the convergence properties for large motions. The second is that we present an analytical convergence analysis of the GM and its properties. Experimental results demonstrate the applicability of these algorithms to real images.     

Fast multi-frame motion estimation for H264/AVC system

Advanced video compression standard, H264/AVC, with multi-frame motion estimation, can offer better motion-compensation than the previous coding standards. However, the implementation of real-time multi-frame estimation for an H264/AVC system is difficult due to heavy computations. In this paper, a fast algorithm is proposed in an effort to reduce the searching computation for motion estimation with five reference frames. The fast multi-frame motion estimation consists of the adaptive full-search, three-step search, and diamond search methods using the content adaptive control process. Efficient control flow is proposed to select the searching algorithm dependent on video features. The adaptive algorithm can achieve better rate-distortion and lower computation for H264/AVC coding. The experiments indicate that the speed-up is 6–15 times compared with the full search method, while the image quality slightly degrades.     

小数像素运动估计快速算法

高精度的匹配和补偿可以减少预测误差，提高压缩视频图像的质量。提出了一种小数像素精度视频运动估计的快速算法，根据半像素精度运动估计的中间结果，直接推算出最高精度的运动估计。根据该算法可以快速得到任意小数像素精度的运动估计。     

Fast algorithms for continuous estimation of mean value of a random variable

Three algorithms for the continuous computation of the mean value (first moment) of a random variable are investigated. These algorithms are suitable for implementation in a minicomputer or in a hard-wired special-purpose processor. It is shown that, if an extra storage register is available in the system, the confidence limit in the measured mean value can be improved considerably with little increase in the total computation time.     

Fast LV motion estimation using subspace approximation techniques

Cardiac motion estimation is very important in understanding cardiac dynamics and in noninvasive diagnosis of heart disease. Magnetic resonance (MR) imaging tagging is a technique for measuring heart deformations. In cardiac tagged MR images, a set of dark lines are noninvasively encoded within myocardial tissue providing the means for measurement of deformations of the heart. The points along tag lines measured in different frames and in different directions carry important information for determining the three-dimensional nonrigid movement of left ventricle. However, these measurements are sparse and, therefore, multidimensional interpolation techniques are needed to reconstruct a dense displacement field. In this paper, a novel subspace approximation technique is used to accomplish this task. We formulate the displacement estimation as a variational problem and then project the solution into spline subspaces. Efficient numerical methods are derived by taking advantages of B-spline properties. The proposed technique significantly improves our previous results reported in [3] with respect to computational time. The method is applied to a temporal sequence of two-dimensional images and is validated with simulated and in vivo heart data.