Search

In the context of motion estimation for video coding, successive elimination algorithms (SEAs) significantly reduce the number of candidates evaluated during motion estimation without altering the resulting optimal motion vector. Nevertheless, SEA is often only used in conjunction with exhaustive search algorithms (e.g., full search). In this paper, we combine the multi-level successive elimination algorithm (ML-SEA) and the rate-constrained successive elimination algorithm (RCSEA) and show that they can be advantageously applied to suboptimal search algorithms. We demonstrate that the savings brought about by the new multi-level RCSEA (ML-RCSEA) outweigh the pre-computational costs of this approach for the Test Zonal (TZ) Search algorithm found in the HM reference encoder. We propose a novel multi-level composition pattern for performing RCSEA on an asymmetric partitioning. We introduce a double-check mechanism for RCSEA, and show that on average, it avoids computing 71% of motion vector (MV) costs. We also apply the proposed ML-RCSEA to bi-predictive refinement search and leverage a cost-based search ordering to remove 56% of error metric computations, on average. When compared to the HM reference encoder, our experiments show that the proposed solution reduces the TZ Search time by approximately 45%, contributing to an average encoding time reduction of about 7%, without increasing the Bjontegaard delta rate (BD-Rate).

Recently, many algorithms have been proposed for fast full search motion estimation. Among them, successive elimination algorithm (SEA) and its modified algorithms significantly speed up the performance of the full search algorithm. By introducing the inequality equation between the norm and the mean absolute difference (MAD) of two matching blocks, the SEA can successively eliminate invalid candidate blocks without any loss in estimation accuracy. In this paper, we propose a partial norm based early rejection algorithm (PNERA) for fast block motion estimation. The proposed algorithm employs the sum of partial norms from several subblocks of the block. Applying the sum of partial norms to the inequality equation, we can significantly reduce the computational complexity of the full search algorithm. In an attempt to reduce the computational load further, the modified algorithms using partial norm distortion elimination (PNDE) and subsampling methods are also proposed. Experimental results show that the proposed algorithm is about 4 to 9 times faster than the original exhaustive full search, and is about 3 to 4 times faster than the SEA.

A transform-domain successive elimination algorithm for block-based motion estimation (ME) is proposed. First, a method is introduced for calculating the sum of squared differences in the transform domain. Then, based on this method, a new transform-domain criterion is proposed to eliminate impossible candidates as early as possible. Experimental results show that the proposed algorithm speeds up the ME process by up to a factor of 10 compared with the conventional full search algorithm.

The new fast full search motion estimation algorithm for optimal motion estimation is proposed in this paper. The computational process of boundaries and possibility of early rejection of non best candidate blocks in Successive Elimination Algorithm (SEA), Multilevel Successive Elimination Algorithm (MSEA) and Fine Granularity Successive Elimination (FGSE) are theoretically and practically analyzed. Based on these analyzes, we present two methods. The first method is Fast Computing Method (FCM) which takes advantage of mathematical indications of redundancy to reduce the number of operations required to compute the boundaries. The second method is Best Initial Matching Error Predictive Method (BIMEPM) which predicts the best initial matching error. With these methods, the operation number for proposed motion estimation is reduced down to 1/52 of Full Search (FS). But MSEA and FGSE algorithms can reduce computations by 1/40 and 1/42 of FS.

In this paper, an efficient duplicate matching algorithm, called pruned multi-level successive elimination (PMSE), is proposed for TV commercial recognition. To enhance the efficiency of filtering out the irrelevant candidates from a sizable database, a felicitous pruning strategy is adapted to the multi-level successive elimination by exploiting the similarity relations of all candidates that can be constructed off-line. By progressively partitioning the signatures into finer granularity representation, more candidates can be eliminated with low computational complexity through pruning process at coarse granularity level. Moreover, a well-designed commercial content signature based on visual spatial correlation and LBP-like coding method, i.e. multi-scale local signature representation, is presented to robustly resist the visual perception distortion. The promising experimental results show the efficiency and effectiveness of the proposed strategy on large video data set.

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.

This paper presents an enhanced strict multilevel successive elimination algorithm (EMSEA) for fast block-matching motion estimation, which is based on the previous strict multilevel successive elimination algorithm (SMSEA) (Song et al., 2006). Different to the SMSEA algorithm with fixed parameters, in EMSEA algorithm, the whole search area is divided into two regions and each region has its own parameters. Therefore, the computation complexity of SMSEA algorithm can be further decreased. Experiments show that the proposed EMSEA algorithm can reduce 16.2% of the SMSEA computation and maintain almost the same image quality, which is better than the TSS and DS algorithms.

This paper presents a simple and effective method to further reduce the search points in multilevel successive elimination algorithm (MSEA). Because the calculated sea values of those best matching search points are much smaller than the current minimum SAD, we can simply increase the calculated sea values to increase the elimination ratio without much affecting the coding quality. Compared with the original MSEA algorithm, the proposed strict MSEA algorithm (SMSEA) can provide average 6.52 times speedup. Compared with other lossy fast ME algorithms such as TSS and DS, the proposed SMSEA can maintain more stable image quality. In practice, the proposed technique can also be used in the fine granularity SEA (FGSEA) algorithm and the calculation process is almost the same.

In this paper, we present a new fast motion estimation algorithm suitable for H.264/AVC encoding systems by combining a multilevel successive elimination algorithm with early termination (MSEAET). First, based on an insight in pyramid structure defined in the standard, we apply the multilevel successive elimination algorithm into blocks larger than 8times8 pixels. By using the sum norms of the blocks and the sub-blocks, tighter and tighter decision boundaries can be obtained for eliminating the unnecessary search positions. According to statistical analysis of the rate-distortion mode decision, an early termination principle is used to judge whether it is necessary to continue the searching process for the other blocks smaller than 8times8 pixels. The efficiency of the proposed algorithm compared with a full search algorithm and a fast search algorithm is verified by simulation results

In this paper, an algorithm, fine granularity successive elimination (FGSE), is proposed for fast optimal block matching in motion estimation. The FGSE is featured by providing a sequence of fine grained boundary levels in an aim to reject a checking candidate as early as possible, thus reducing computational load as much as possible. It is shown that the multilevel successive elimination algorithm (MSEA) is just a degraded case of FGSE with much coarser boundary levels. Comparative experiments are presented to verify the substantial speed-up gain of the proposed algorithm over the MSEA.

It is well known that a lot of computations are required for motion estimation in video encoding. Recently, the multilevel successive elimination algorithm (MSEA) has been proposed to reduce the computational complexity of block matching for motion estimation without degradation of estimation accuracy. In the MSEA, the block matching is hierarchically carried out and the invalid candidate block is successively eliminated. In this paper, we propose an improved MSEA based on a new efficient decision condition. The number of the calculations to eliminate the invalid block can be reduced by the new efficient decision condition in the proposed algorithm. The simulation results show that the proposed algorithm achieves about 30-40% computational saving as compared with the MSEA.

This paper presents a fast full search algorithm for motion estimation. The proposed method is a successive elimination algorithm (SEA) for multiple reference frame applications. We will show that motion estimation for the reference images temporally preceding the first reference image is less intensive in computation compared with that for the first reference image. Simulation results explain that our method reduces computation complexity although it has the same quality as the full search algorithm (FSA).

This paper presents a fast full search algorithm for motion estimation. The proposed method is an extended version of the rate constrained successive elimination algorithm (RSEA) for multiple reference frame applications. We will show that motion estimation for the reference images temporally preceding the first reference image can be less intensive in computation compared with that for the first reference image. For computational reduction, we will drive a new condition to lead the smaller number of candidate blocks for the best matched block. Simulation results explain that our method reduces computation complexity although it has the same quality as RSEA.

Distributed generation (DG) offers an attractive alternative to T&D expansion. Instead of expanding existing substations, building new transmission lines, and building new substations, DG can be used to accommodate new load growth and provide relief for overloaded components. Additional attractive features include: low capital cost, low fuel cost, low O&M cost, modularity, ease in siting and short lead times. This paper presents a successive elimination algorithm capable of identifying the number, size and location of distributed generators needed to optimally defer T&D expansion. This algorithm is applied to a utility test system and results are discussed.

We present fast algorithms to reduce the computation of block matching algorithms for motion estimation in video coding. Nobel successive elimination algorithms for the estimation of motion vectors are based on the successive elimination algorithm for motion estimation and fast algorithms for the estimation of motion vectors. Nobel successive elimination algorithms effectively eliminate the search points within the search window and thus decrease the number of matching evaluation that requires very intensive computations. The efficiency of each proposed algorithm was verified by experimental results.

Presents a very fast exhaustive search algorithm for motion estimation. This algorithm is based on successive elimination algorithm (SEA) and fast algorithms for the estimation of motion vectors [2]. A new motion estimation method called new fast successive elimination algorithm (NFSEA) finds the same motion vectors as exhaustive search algorithm with far fewer computational load. NFSEA effectively eliminates the search points within the search window and thus decreasing the number of matching evaluations that require very intensive computations. So, NFSEA dramatically reduces the number of operations for finding motion vectors. Experimental results show that NFSEA is a very efficient algorithm for the estimation of motion vectors.

We propose a fast block motion estimation algorithm using the sum of partial norms which finds the same motion vectors as the exhaustive full search algorithm with a reduced computational load. Experimental results show that the proposed algorithm is about 3 or 4 times faster than the original exhaustive full search, and is about 2 times faster than the successive elimination algorithm (SEA).

The computational process of the sum of the absolute difference (SAD) and the multilevel successive elimination algorithm (MSEA) are theoretically analyzed, and a new improved MSEA is proposed. The proposed algorithm reduces the computations required for judging invalid candidate blocks. The simulation results show that the proposed algorithm achieves a computational time savings of about 30 to 40% without additional hardware, compared to the MSEA.

A successive elimination algorithm for binary block matching motion estimation based on one-bit transform is presented. The principles of the proposed algorithm are mathematically formulated. Simulation result show that the proposed algorithm can significantly reduce the computation time without influencing the prediction performance.