In his classical article[3], J. Kiefer introduced the Fibonacci search as a direct optimal method. The optimality was proved under the restriction: the total number of tests is given in advance and fixed. To avoid thi...In his classical article[3], J. Kiefer introduced the Fibonacci search as a direct optimal method. The optimality was proved under the restriction: the total number of tests is given in advance and fixed. To avoid this restriction, some different concepts of optimality were proposed and some corresponding optimal methods were obtained in [1], [2], [5] and [6]. In particular, the even-block search was treated in [1]. This paper deals with the odd-block search. The main result is Theorem 1.15.展开更多
Block-matching motion estimation plays an important role in video coding. The simple and efficient fast block-matching algorithm using Variable Shape Search (VSS) proposed in this paper is based on diamond search and ...Block-matching motion estimation plays an important role in video coding. The simple and efficient fast block-matching algorithm using Variable Shape Search (VSS) proposed in this paper is based on diamond search and hexagon search. The initial big diamond search is designed to fit the directional centre-biased characteristics of the real-world video se- quence, and the directional hexagon search is designed to identify a small region where the best motion vector is expected to locate. Finally, the small diamond search is used to select the best motion vector in the located small region. Experimental results showed that the proposed VSS algorithm can significantly reduce the computational complexity, and provide competitive computational speedup with similar distortion performance as compared with the popular Diamond-based Search (DS) algorithm in the MPEG-4 Simple Profile.展开更多
Searching is frequently used in computer software design. The research of searching algorithms is always in an important position and many algorithms have been advanced. It is realized that the searching algorithm bas...Searching is frequently used in computer software design. The research of searching algorithms is always in an important position and many algorithms have been advanced. It is realized that the searching algorithm based on data comparison has the expected complexity of at least O(N log N ) (The complexity means the running time to search N data in a file of N data, the following complexity has the same meaning). Famous computer scientist D. E. Knuth made analysis and comparison for searching algorithms, and came to the conclusion that the binary search has the least complexity of O(N log N). Data processed in comput-展开更多
Motion estimation is an important part of the MPEG- 4 encoder, due to its significant impact on the bit rate and the output quality of the encoder sequence. Unfortunately this feature takes a significant part of the e...Motion estimation is an important part of the MPEG- 4 encoder, due to its significant impact on the bit rate and the output quality of the encoder sequence. Unfortunately this feature takes a significant part of the encoding time especially when the straightforward full search(FS) algorithm is used. In this paper, a new algorithm named diamond block based gradient descent search (DBBGDS) algorithm, which is significantly faster than FS and gives similar quality of the output sequence, is proposed. At the same time, some other algorithms, such as three step search (TSS), improved three step search (ITSS), new three step search (NTSS), four step search (4SS), cellular search (CS) , diamond search (DS) and block based gradient descent search (BBGDS), are adopted and compared with DBBGDS. As the experimental results show, DBBGDS has its own advantages. Although DS has been adopted by the MPEG- 4 VM, its output sequence quality is worse than that of the proposed algorithm while its complexity is similar to the proposed one. Compared with BBGDS, the proposed algorithm can achieve a better output quality.展开更多
Aiming at the shortcoming that certain existing blocking-matching algorithms,such as full search,three-step search,and diamond search algorithms,usually can not keep a good balance between high accuracy and low comput...Aiming at the shortcoming that certain existing blocking-matching algorithms,such as full search,three-step search,and diamond search algorithms,usually can not keep a good balance between high accuracy and low computational complexity,a block-matching motion estimation algorithm based on two-step search is proposed in this paper.According to the fact that the gray values of adjacent pixels will not vary fast,the algorithm employs an interlaced search pattern in the search window to estimate the motion vector of the object-block.Simulation and actual experiments demonstrate that the proposed algorithm greatly outperforms the well-known three-step search and diamond search algorithms,no matter the motion vector is large or small.Compared with the full search algorithm,the proposed one achieves similar performance but requires much less computation,therefore,the algorithm is well qualified for real-time video image processing.展开更多
A new faster block-matching algorithm （BMA） by using both search candidate and pixd sulzsamplings is proposed. Firstly a pixd-subsampling approach used in adjustable partial distortion search （APDS） is adjusted to...A new faster block-matching algorithm （BMA） by using both search candidate and pixd sulzsamplings is proposed. Firstly a pixd-subsampling approach used in adjustable partial distortion search （APDS） is adjusted to visit about half points of all search candidates by subsampling them, using a spiral-scanning path with one skip. Two sdected candidates that have minimal and second minimal block distortion measures are obtained. Then a fine-tune step is taken around them to find the best one. Some analyses are given to approve the rationality of the approach of this paper. Experimental results show that, as compared to APDS, the proposed algorithm can enhance the block-matching speed by about 30% while maintaining its MSE performance very close to that of it. And it performs much better than many other BMAs such as TSS, NTSS, UCDBS and NPDS.展开更多
Generation of a depth-map from 2D video is the kernel of DIBR (Depth Image Based Rendering) in 2D-3D video conversion systems. However it occupies over most of the system resource where the motion search module takes ...Generation of a depth-map from 2D video is the kernel of DIBR (Depth Image Based Rendering) in 2D-3D video conversion systems. However it occupies over most of the system resource where the motion search module takes up 90% time-consuming in typical motion estimation-based depth-map generation algorithms. In order to reduce the computational complexity, in this paper a new fast depth-map generation algorithm based on motion search is developed, in which a fast diamond search algorithm is adopted to decide whether a 16x16 or 4x4 block size is used based on Sobel operator in the motion search module to obtain a sub-depth-map. Then the sub-depth-map will be fused with the sub-depth-maps gotten from depth from color component Cr and depth from linear perspective modules to compensate and refine detail of the depth-map, finally obtain a better depth-map. The simulation results demonstrate that the new approach can greatly reduce over 50% computational complexity compared to other existing methods.展开更多
文摘In his classical article[3], J. Kiefer introduced the Fibonacci search as a direct optimal method. The optimality was proved under the restriction: the total number of tests is given in advance and fixed. To avoid this restriction, some different concepts of optimality were proposed and some corresponding optimal methods were obtained in [1], [2], [5] and [6]. In particular, the even-block search was treated in [1]. This paper deals with the odd-block search. The main result is Theorem 1.15.
文摘Block-matching motion estimation plays an important role in video coding. The simple and efficient fast block-matching algorithm using Variable Shape Search (VSS) proposed in this paper is based on diamond search and hexagon search. The initial big diamond search is designed to fit the directional centre-biased characteristics of the real-world video se- quence, and the directional hexagon search is designed to identify a small region where the best motion vector is expected to locate. Finally, the small diamond search is used to select the best motion vector in the located small region. Experimental results showed that the proposed VSS algorithm can significantly reduce the computational complexity, and provide competitive computational speedup with similar distortion performance as compared with the popular Diamond-based Search (DS) algorithm in the MPEG-4 Simple Profile.
文摘Searching is frequently used in computer software design. The research of searching algorithms is always in an important position and many algorithms have been advanced. It is realized that the searching algorithm based on data comparison has the expected complexity of at least O(N log N ) (The complexity means the running time to search N data in a file of N data, the following complexity has the same meaning). Famous computer scientist D. E. Knuth made analysis and comparison for searching algorithms, and came to the conclusion that the binary search has the least complexity of O(N log N). Data processed in comput-
文摘Motion estimation is an important part of the MPEG- 4 encoder, due to its significant impact on the bit rate and the output quality of the encoder sequence. Unfortunately this feature takes a significant part of the encoding time especially when the straightforward full search(FS) algorithm is used. In this paper, a new algorithm named diamond block based gradient descent search (DBBGDS) algorithm, which is significantly faster than FS and gives similar quality of the output sequence, is proposed. At the same time, some other algorithms, such as three step search (TSS), improved three step search (ITSS), new three step search (NTSS), four step search (4SS), cellular search (CS) , diamond search (DS) and block based gradient descent search (BBGDS), are adopted and compared with DBBGDS. As the experimental results show, DBBGDS has its own advantages. Although DS has been adopted by the MPEG- 4 VM, its output sequence quality is worse than that of the proposed algorithm while its complexity is similar to the proposed one. Compared with BBGDS, the proposed algorithm can achieve a better output quality.
基金supported by the Lab Open Fund of Beijing Microchemical Research Institute(P2008026EB)
文摘Aiming at the shortcoming that certain existing blocking-matching algorithms,such as full search,three-step search,and diamond search algorithms,usually can not keep a good balance between high accuracy and low computational complexity,a block-matching motion estimation algorithm based on two-step search is proposed in this paper.According to the fact that the gray values of adjacent pixels will not vary fast,the algorithm employs an interlaced search pattern in the search window to estimate the motion vector of the object-block.Simulation and actual experiments demonstrate that the proposed algorithm greatly outperforms the well-known three-step search and diamond search algorithms,no matter the motion vector is large or small.Compared with the full search algorithm,the proposed one achieves similar performance but requires much less computation,therefore,the algorithm is well qualified for real-time video image processing.
基金This project was supported by the National Natural Science Foundation of China (60272099) .
文摘A new faster block-matching algorithm （BMA） by using both search candidate and pixd sulzsamplings is proposed. Firstly a pixd-subsampling approach used in adjustable partial distortion search （APDS） is adjusted to visit about half points of all search candidates by subsampling them, using a spiral-scanning path with one skip. Two sdected candidates that have minimal and second minimal block distortion measures are obtained. Then a fine-tune step is taken around them to find the best one. Some analyses are given to approve the rationality of the approach of this paper. Experimental results show that, as compared to APDS, the proposed algorithm can enhance the block-matching speed by about 30% while maintaining its MSE performance very close to that of it. And it performs much better than many other BMAs such as TSS, NTSS, UCDBS and NPDS.
文摘Generation of a depth-map from 2D video is the kernel of DIBR (Depth Image Based Rendering) in 2D-3D video conversion systems. However it occupies over most of the system resource where the motion search module takes up 90% time-consuming in typical motion estimation-based depth-map generation algorithms. In order to reduce the computational complexity, in this paper a new fast depth-map generation algorithm based on motion search is developed, in which a fast diamond search algorithm is adopted to decide whether a 16x16 or 4x4 block size is used based on Sobel operator in the motion search module to obtain a sub-depth-map. Then the sub-depth-map will be fused with the sub-depth-maps gotten from depth from color component Cr and depth from linear perspective modules to compensate and refine detail of the depth-map, finally obtain a better depth-map. The simulation results demonstrate that the new approach can greatly reduce over 50% computational complexity compared to other existing methods.
