block matching algorithm is the most popular motion estimation technique, due to its simplicity of implementation and effectiveness. However, the algorithm suffers from a long computation time which affects its genera...
详细信息
block matching algorithm is the most popular motion estimation technique, due to its simplicity of implementation and effectiveness. However, the algorithm suffers from a long computation time which affects its general performance. In order to achieve faster motion estimation, a new block matching algorithm based on stochastic fractal search, SFS, is proposed in this paper. SFS is a metaheuristic technique used to solve hard optimization problems in minimal time. In this work, two main contributions are presented. The first one consists of computing the motion vectors in a parallel structure as opposed to the other hierarchical metaheuristic block matching algorithms. When the video sequence frame is divided into blocks, a multi-population model of SFS is used to estimate the motion vectors of all blocks simultaneously. As a second contribution, the proposed algorithm is modified in order to enhance the results. In this modified version, four ideas are investigated. The random initialization, usually used in metaheuristics, is replaced by a fixed pattern. The initialized solutions are evaluated using a new fitness function that combines two matching criteria. The considered search space is controlled by a new adaptive window size strategy. A modified version of the fitness approximation method, which is known to reduce computation time but causes some degradation in the estimation accuracy, is proposed to balance between computation time and estimation accuracy. These ideas are evaluated in nine video sequences and the percentage improvement of each idea, in terms of estimation accuracy and computational complexity, is reported. The presented algorithms are then compared with other well-known block matching algorithms. The experimental results indicate that the proposed ideas improve the blockmatching performance, and show that the proposed algorithm outperforms many state-of-the-art methods.
Time-varying mesh, which is attracting a lot of attention as a new multimedia representation method, is a sequence of 3-D models that are composed of vertices, edges, and some attribute components such as color. Among...
详细信息
Time-varying mesh, which is attracting a lot of attention as a new multimedia representation method, is a sequence of 3-D models that are composed of vertices, edges, and some attribute components such as color. Among these components, vertices require large storage space. In conventional 2-D video compression algorithms, motion compensation (MC) using a block matching algorithm is frequently employed to reduce temporal redundancy between consecutive frames. However, there has been no such technology for 3-D time-varying mesh so far. Therefore, in this paper, we have developed an extended block matching algorithm (EBMA) to reduce the temporal redundancy of the geometry information in the time-varying mesh by extending the idea of the 2-D block matching algorithm to 3-D space. In our EBMA, a cubic block is used as a matching unit. MC in the 3-D space is achieved efficiently by matching the mean normal vectors calculated from partial surfaces in cubic blocks, which our experiments showed to be a suboptimal matching criterion. After MC, residuals are transformed by the discrete cosine transform, uniformly quantized, and then encoded. The extracted motion vectors are also entropy coded after differential pulse code modulation. As a result of our experiments, 10%-18% compression has been achieved.
Genetic algorithm is well known for searching global optimum. It has been demonstrated its capability for block Motion Estimation with performance close to exhaustive full search using fewer search steps. However, it ...
详细信息
Genetic algorithm is well known for searching global optimum. It has been demonstrated its capability for block Motion Estimation with performance close to exhaustive full search using fewer search steps. However, it is computational expensive. A Genetic Four-Step Search is developed to alleviate the problem. It has a mean square error performance close to full search and much computational efficient than the traditional genetic algorithm. A FPGA implementation of the proposed algorithm is realized. The architecture is simple and suitable for valuable applications in the development of low cost multimedia products.
Several VLSI architectures for the full-search block matching algorithm have been proposed in recent years due to its computation and I/O-intensive nature and its importance in various computer vision and image proces...
详细信息
Several VLSI architectures for the full-search block matching algorithm have been proposed in recent years due to its computation and I/O-intensive nature and its importance in various computer vision and image processing applications, This paper presents a new coarse grained reconfigurable coprocessor which is suitable for integration with general purpose microprocessors. The 180 000 transistor custom VLSI design was implemented in 0.6 mu m CMOS on a 4.12 mm x 2.59 mm die and has been fully tested up to 33 MHz. For a typical image database search application, a sample system consisting of four coprocessors interfaced through a 33 MHz PCI bus will provide a speedup of 320x over an 80486 DX2/66 MHz and 64x over a 150-MHz Pentium running fully optimized assembly code.
In this paper, we propose an expert-system based parallel multi-1-dimensional block matching algorithm (ESPM-1D-BMA) for motion estimation (ME). Instead of the conventional 2D blockmatching, we employ the parallel mu...
详细信息
In this paper, we propose an expert-system based parallel multi-1-dimensional block matching algorithm (ESPM-1D-BMA) for motion estimation (ME). Instead of the conventional 2D blockmatching, we employ the parallel multi-1D blocks matching to improve the computing speed. To improve the ME accuracy, we design a knowledge base and inference engine to determine the true motion vector (MV) from the results of parallel multi-1D blocks matching. To speed up the computing speed further, we present a hardware architecture for implementing the ESPM-1D-BMA. We have demonstrated that the MV estimation accuracy achieved by the proposed ESPM-1D-BMA is much better than the comparing fast block matching algorithms and is close to the 2 dimensional full search block matching algorithm (2D-FSBMA). We also demonstrate that the computing speed of the proposed ESPM-1D-BMA is about two times as fast as the mixed-signal 2D-FSBMA (MS-2D-FSBMA). (C) 2011 Elsevier Ltd. All rights reserved.
An important problem when using the block matching algorithm to track objects is how to update the reference block to take account of the changing target appearance. A variety of update strategies are reported and com...
详细信息
An important problem when using the block matching algorithm to track objects is how to update the reference block to take account of the changing target appearance. A variety of update strategies are reported and compared.
作者：
Kim, JNByun, SAhn, BKBS
Tech Res Inst Yongdeungpo Gu Seoul 150790 South Korea K JIST
Dept Mechatron Puk Gu Kwangju 500712 South Korea
In this letter we propose a new fast matchingalgorithm that has no degradation of predicted images such as found in the conventional full search (FS) algorithm, so as to reduce the amount of computation of the FS alg...
详细信息
In this letter we propose a new fast matchingalgorithm that has no degradation of predicted images such as found in the conventional full search (FS) algorithm, so as to reduce the amount of computation of the FS algorithm for motion estimation in real-time video coding applications. That is, our proposing algorithm reduces only unnecessary computations in the process of motion estimation without decreasing the prediction quality compared to the conventional FS algorithm. The computational reduction comes from rapid elimination of impossible motion vectors. In comparison to the FS algorithm, we obtained faster elimination of inappropriate candidate motion vectors using efficient matching units based on image complexity. Experimentally, we demonstrated that the unnecessary computations were removed by about 30% as compared to the other fast FS algorithms.
This paper deals with the block-based disparity map estimation of a stereoscopic image. While most existing algorithms estimate this map by minimizing a dissimilarity metric, the proposed optimization algorithm aims a...
详细信息
ISBN:
(纸本)9781509004805
This paper deals with the block-based disparity map estimation of a stereoscopic image. While most existing algorithms estimate this map by minimizing a dissimilarity metric, the proposed optimization algorithm aims at minimizing the rate distortion compromise using the disparity map yielded by the traditional block matching algorithm as an initial reference map. The developed algorithm analyzes the performance impact of the permutation of each disparity of the reference map with all possible disparities. The retained disparity is one that improves the joint rate-distortion metric. This process is repeated as long as improvements are observed. Moreover, a particular attention is given to the updating process of the joint metric so that the algorithm computational cost is not affected. Simulation results clearly show that our approach achieves better performance than the traditional block matching algorithm in terms of rate-distortion compromise.
A new hierarchical block matching algorithm specially proper for a large search area, is proposed. The algorithm utilizes the spatial motion vector correlation under the fixed hierarchical search structure. Motion vec...
详细信息
ISBN:
(纸本)0819424358
A new hierarchical block matching algorithm specially proper for a large search area, is proposed. The algorithm utilizes the spatial motion vector correlation under the fixed hierarchical search structure. Motion vectors of the causally neighboring blocks can be used to predict the motion vector of the current block, if the spatial motion vector correlation is strong. However, they are not helpful for searching complex or random motion. The proposed algorithm consists of two level searching steps. The higher one selects two initial estimates, one obtained by using motion vector correlation for continuous-motion, the other by using minimum mean absolute difference (MAD) for random or complex motion among rectangularly-sampled motion vector candidates in the search area, and the lower one is for the final motion vector refinement. Compared with previous hierarchical block matching algorithms, the scheme improves the accuracy of the estimated motion vector for random/complex motion as well as continuous motion. It is also proper for hardware implementation because of simple, fast, and regular search procedure. Simulation results show that the proposed algorithm drastically reduces the computational complexity to 5.0% of that of full search block matching algorithm, with the minor PSNR degradation of 0.4 dB even in the worst case.
This paper addresses two issues related to motion estimation using the block matching algorithms (BMA): (1) determining the reliability of the motion vectors of each block, and (2) imposing smoothness constraint to th...
详细信息
ISBN:
(纸本)0819452114
This paper addresses two issues related to motion estimation using the block matching algorithms (BMA): (1) determining the reliability of the motion vectors of each block, and (2) imposing smoothness constraint to the motion vector field. We introduce a new robust reliability measure to represent the confidence level of the motion vector from the cost function distribution and propose a novel algorithm that incorporates smoothness constraint into the motion vector field evaluation by implementing a priority queue structure based on the reliability measure. In this framework, a smooth motion vector field is evaluated in a single pass without going through iterations typical of many existing optical flow estimation algorithms. Hence it is fast and can easily be incorporated into real-time applications for video compression as well as image segmentation.
暂无评论