Fast closest codeword search algorithms for vector quantisation

One of the most serious problems for vector quantisation is the high computational complexity of searching for the closest codeword in the codebook design and encoding phases. The authors present a fast algorithm to search for the closest codeword. The proposed algorithm uses two significant features of a vector, mean value and variance, to reject many unlikely codewords and saves a great deal of computation time. Since the proposed algorithm rejects those codewords that are impossible to be the closest codeword, this algorithm introduces no extra distortion than conventional full search method. The results obtained confirm the effectiveness of the proposed algorithm     

Fast codeword search algorithm for real-time codebook generation inadaptive VQ

Adaptive vector quantisation is used in image sequence coding where the code-book is updated continuously to keep track with the changing source statistics. Hence, for real-time video coding applications, both the processes of quantising the input vectors and updating the codebook are required to be fast. Since the nearest codeword search is involved in both these processes, a fast codeword search algorithm can make the coding process time efficient. The authors describe a proposed codeword search algorithm with reduced search space. The algorithm uses the mean value and the sum of the absolute differences as the two criteria to reject unlikely codewords, thereby saving a great deal of computational time, while introducing no more distortion than the conventional full search algorithm. Simulation results obtained confirm the effectiveness of the proposed algorithm in terms of computational complexity     

Fast codeword search algorithm using wavelet transform and partialdistance search techniques

A new fast codeword search algorithm for vector quantisers is presented. This algorithm performs a fast search in the wavelet domain of codewords using the partial distance search technique. Simulation results show that the algorithm has only 2% of the arithmetic complexity of the exhaustive search method     

Fast codeword search algorithm for image coding based onmean-variance pyramids of codewords

The fast codeword search algorithm based on the mean pyramids of codewords is currently used in image coding applications. A more efficient algorithm is presented for fast codeword searching which is based on the use of mean-variance pyramids of codewords. Experimental results confirm the effectiveness of the proposed method     

Fast fractal image encoding based on adaptive search

This paper presents a new adaptive search approach to reduce the computational complexity of fractal encoding. A simple but very efficient adaptive necessary condition is introduced to exclude a large number of unqualified domain blocks so as to speed-up fractal image compression. Furthermore, we analyzed an unconventional affine parameter that has better properties than the conventional luminance offset. Specifically, we formulated an optimal bit allocation scheme for the simultaneous quantizations of the usual scaling and the aforementioned unconventional affine parameter. Experiments on standard images showed that our adaptive search method yields superior performance over conventional fractal encoding.     

Fast full search equivalent encoding algorithms for imagecompression using vector quantization

Three fast search routines to be used in the encoding phase of vector quantization (VQ) image compression systems are presented. These routines, which are based on geometric considerations, provide the same results as an exhaustive (or full) search. Examples show that the proposed algorithms need only 3-20% of the number of mathematical operations required by a full search and fewer than 50% of the operations required by recently proposed alternatives.     

Efficient codeword search algorithm based on Hadamard transform

A new fast codeword search algorithm for image vector quantisation (VQ) is introduced. This algorithm performs a fast codeword search in the Hadamard transform (HT) domain using the partial distance search (PDS) technique. Experimental results show that the algorithm needs only 2-3% of the distortion calculations of the exhaustive search method     

Optimisation of quantisers in the frequency domain

The author presents a procedure for optimising the scalar quantiser, based on the power spectrum density of the quantisation noise. The input signal is assumed to be stationary in the wide sense, but no restriction is made concerning its probability density function     

Fast orthogonal search for direction finding

An efficient modelling algorithm known as fast orthogonal search (FOS) is applied to the estimation of the directions of plane waves incident on an array of sensors. An iterative approach which decreases the mean-squared error of the original FOS model is introduced. The methods are demonstrated and compared with Root-MUSIC in computer simulations.<>     

Fast search algorithm for vector quantisation

A tree structure for the fast nearest neighbour search algorithm for vector quantisation is presented. Using the new algorithm a remarkable reduction in the number of multiplications, additions and comparisons is achieved.<>     

In search of the optimal searching sequence for VQ encoding

The codeword searching sequence is sometimes very vital to the efficiency of a vector quantization (VQ) encoding algorithm. In this paper, we evaluate some necessary criteria for the derivation of an optimal searching sequence and derive the optimal searching sequence based on such criteria     

Fast encoding techniques for Multiview Video Coding

Multiview Video Coding (MVC) is a technique that permits efficient compression of multiview video. MVC uses variable block size motion and disparity estimation for block matching. This requires an exhaustive search process that involves all possible macroblock partition sizes. We analyze the time complexity of MVC and the methods that have been proposed to speed up motion and disparity estimation. We then propose two new methods: Previous Disparity Vector Disparity Estimation (PDV-DE) and Stereo-Motion Consistency Constraint Motion and Disparity Estimation (SMCC-MDE). PDV-DE exploits the correlation between temporal levels and disparity vectors to speed up the disparity estimation process while SMCC-MDE exploits the geometrical relationship of consecutive frame pairs to speed up motion and disparity estimation. We build a complete low complexity MVC encoding solution that combines our two methods with complementary previous methods to speed up motion and disparity search. We evaluate the complexity of our solution in terms of encoding time and number of search points. Our experimental results show that our solution can reduce the encoding time and number of search points of the standard MVC implementation (JMVM 6.0) using the fast TZ search mode up to 93.7% and 96.9%, respectively, with negligible degradation in the rate-distortion performance. Compared to the best published results, this is an improvement of up to 11% and 7%, respectively.     

Fast tree-structured nearest neighbor encoding for vectorquantization

This work examines the nearest neighbor encoding problem with an unstructured codebook of arbitrary size and vector dimension. We propose a new tree-structured nearest neighbor encoding method that significantly reduces the complexity of the full-search method without any performance degradation in terms of distortion. Our method consists of efficient algorithms for constructing a binary tree for the codebook and nearest neighbor encoding by using this tree. Numerical experiments are given to demonstrate the performance of the proposed method.     

Fast codebook search algorithm for unconstrained vectorquantisation

Vector quantisation (VQ) is a well known data compression technique which maps an ordered set of real numbers into a single integer. However, it is difficult to achieve accurate compression with the use of unconstrained Voronoi VQ when the codebook level and vector dimensionality are very large, due to the extremely high real-time computational complexity involved in full codebook search. To overcome this difficulty, a classified pre-selection method is proposed. Compared to the conventional full search method, the algorithm reduces the computational complexity involved in the code vector selection procedure by 70%~90% with almost no loss in coder performance, at the cost of only a slight increase in the storage requirement     

Comparison of 1-bit adaptive quantisers for speech coding

A 1-bit version of the recently proposed generalised hybrid adaptive quantiser (GHAQ) is compared with two other 1-bit adaptive quantisers, in terms of the signal-to-noise ratio obtained when coding speech in delta modulators. The GHAQ is found to have a clear advantage, particularly when the speech is acquired by a telephone microphone. It is also shown that the optimum coefficients of the predictor can be influenced substantially by the design of the adaptive quantiser, and a technique for finding suitable coefficients in this context is described.<>     

Divisors of codeword weights

The exponent of a nonzero linear code over a finite field of characteristic p is the exponent in the highest power of p dividing the weights of all the codewords. If the code is a right ideal in a group algebra the exponent is related to invariant multilinear forms on the code. This expository paper presents recent results obtained from that relation, extending earlier work of Delsarte and McEliece.     

Efficient search algorithm for fast encoding of images using vectorquantisation

A fast algorithm for image coding using vector quantisation which exploits the spatial redundancies in the image is proposed. The algorithm speeds up the codeword search phase required for nearest neighbour encoding, by utilising the high amount of intravector and intervector correlations. A novel prediction mechanism is used to exploit the intervector correlations and a mean pyramid representation is used for exploiting the intravector correlations. The prediction mechanism also enables a further reduction in bit rate compared to ordinary vector quantisation. Simulation results show the effectiveness of the proposed method     

一种改进的矢量量化码字搜索算法

该文利用图像矢量的平均值和方差,结合了最近邻域搜索算法,构造了一种新的快速矢量量化编码算法。将一个输入矢量分为两个子矢量,分别计算原始矢量、两个子矢量的和以及方差值,利用在这些数值基础上建立的一组三角不等式来排除不可能的码字。仿真结果表明新算法在所需时间和计算复杂度方面优于改进的EENNS算法,为矢量量化算法的研究提供了一种新的思路。     

Fast orthogonal search for array processing and spectrum estimation

An efficient, general purpose modelling algorithm known as fast orthogonal search (FOS) is applied to the problem of estimating the angles of arrival of multiple plane waves incident on an array of sensors and to the related problem of estimating the temporal frequencies of narrowband signals in noise. An iterative version of the algorithm (IFOS), which approaches a minimum in the mean squared error between observed and modelled data, is introduced. A modification to the array steering vector model which is beneficial when the incident signals are coherent is described. FOS and IFOS are compared with MUSIC and root MUSIC in computer simulations     

Fast search for best representations in multitree dictionaries.

We address the best basis problem--or, more generally, the best representation problem: Given a signal, a dictionary of representations, and an additive cost function, the aim is to select the representation from the dictionary which minimizes the cost for the given signal. We develop a new framework of multitree dictionaries, which includes some previously proposed dictionaries as special cases. We show how to efficiently find the best representation in a multitree dictionary using a recursive tree-pruning algorithm. We illustrate our framework through several examples, including a novel block image coder, which significantly outperforms both the standard JPEG and quadtree-based methods and is comparable to embedded coders such as JPEG2000 and SPIHT.