You get a bonus - 1 coin for daily activity. Now you have 1 coin

6.2. QUANTIZATION OF VECTOR VALUES

Lecture



Usually, quantization of a set of samples is performed sequentially. Each sample is treated as a scalar and quantized independently of the other samples using the methods described in the previous section. However, it is often possible to reduce the quantization error if all samples are quantized together.

Consider the signal 6.2.  QUANTIZATION OF VECTOR VALUES representing the size vector 6.2.  QUANTIZATION OF VECTOR VALUES . We assume that this vector is an implementation of a random vector with 6.2.  QUANTIZATION OF VECTOR VALUES -dimensional probability density

6.2.  QUANTIZATION OF VECTOR VALUES . (6.2.1)

When quantizing a vector 6.2.  QUANTIZATION OF VECTOR VALUES6.2.  QUANTIZATION OF VECTOR VALUES -dimensional vector space is divided into 6.2.  QUANTIZATION OF VECTOR VALUES quantization cells 6.2.  QUANTIZATION OF VECTOR VALUES each of which corresponds to one of 6.2.  QUANTIZATION OF VECTOR VALUES quantized vectors. Vector signal 6.2.  QUANTIZATION OF VECTOR VALUES replaced by a quantized vector 6.2.  QUANTIZATION OF VECTOR VALUES if a 6.2.  QUANTIZATION OF VECTOR VALUES falls into the cell 6.2.  QUANTIZATION OF VECTOR VALUES . In fig. 6.2.1 shows examples of vector quantization in one-, two-, and three-dimensional spaces. In a similar general formulation of the vector quantization problem, the vector signal 6.2.  QUANTIZATION OF VECTOR VALUES converted to vector 6.2.  QUANTIZATION OF VECTOR VALUES but vector components 6.2.  QUANTIZATION OF VECTOR VALUES however, they will not necessarily be quantized separately over a set of discrete threshold levels.

6.2.  QUANTIZATION OF VECTOR VALUES

Fig. 6.2.1. Quantization cells in vector space: a - one-dimensional space; b - two-dimensional space; in - three-dimensional space.

The rms error of vector quantization can be represented as a sum

6.2.  QUANTIZATION OF VECTOR VALUES (6.2.2)

Optimal position of quantized vectors 6.2.  QUANTIZATION OF VECTOR VALUES for fixed boundaries of quantization cells, one can find by equating to zero the partial derivatives of quantization errors with respect to the vectors 6.2.  QUANTIZATION OF VECTOR VALUES . The result is a system of integral equations.

6.2.  QUANTIZATION OF VECTOR VALUES (6.2.3)

After transformations we find

6.2.  QUANTIZATION OF VECTOR VALUES (6.2.4)

Equality (6.2.4) defines the conditional expectation of a vector 6.2.  QUANTIZATION OF VECTOR VALUES when it enters the cell:

6.2.  QUANTIZATION OF VECTOR VALUES . (6.2.5)

In this case, the minimum mean square quantization error is

6.2.  QUANTIZATION OF VECTOR VALUES , (6.2.6)

Where 6.2.  QUANTIZATION OF VECTOR VALUES - vector correlation matrix 6.2.  QUANTIZATION OF VECTOR VALUES . Note that when 6.2.  QUANTIZATION OF VECTOR VALUES formula (6.2.4) is reduced to (6.1.11), and the expression for quantization error (6.2.6) goes into formula (6.1.12).

Optimal positions of quantized vectors 6.2.  QUANTIZATION OF VECTOR VALUES with fixed quantization cells 6.2.  QUANTIZATION OF VECTOR VALUES impossible to determine without knowing the joint probability density 6.2.  QUANTIZATION OF VECTOR VALUES . However, this information is often not available. Another significant difficulty is related to the actual calculation of the integrals in formula (6.2.4). Therefore, it is often necessary to simplify the procedure of vector quantization. So, you can quantize all the components of the vector 6.2.  QUANTIZATION OF VECTOR VALUES separately, but set quantized vectors 6.2.  QUANTIZATION OF VECTOR VALUES using quantization cells 6.2.  QUANTIZATION OF VECTOR VALUES . Then in the three-dimensional space of the cell 6.2.  QUANTIZATION OF VECTOR VALUES turn into rectangular parallelepipeds. If at the same time the components of the vector 6.2.  QUANTIZATION OF VECTOR VALUES uncorrelated, then vector quantization reduces to sequential quantization of scalar quantities. However, if the samples are correlated, then the problem of determining the optimal vector 6.2.  QUANTIZATION OF VECTOR VALUES As a rule, it cannot be solved without introducing additional simplifying assumptions. Carey [4] obtained solutions for joint Gaussian densities when quantizing cells 6.2.  QUANTIZATION OF VECTOR VALUES are small enough. Huns [5] investigated a recurrent method for solving such a problem, when each component of a vector is determined using successive approximations based on the remaining quantized components of a vector. This method allows you to find a solution to the problem for many different probability densities: in part 6, it is considered as a means of reducing quantization errors in systems using PCM and transformation coding.

Let us now try to find such a set of quantization cells. 6.2.  QUANTIZATION OF VECTOR VALUES at which the mean square quantization error is minimized. Bruce [6] developed a method for solving this problem based on dynamic programming. However, in the general case, optimal forms of quantization cells are complex and very difficult to determine. Therefore, in most vector quantization methods, a suboptimal approach is used, when for each component of the vector a fixed number of quantization levels is specified. 6.2.  QUANTIZATION OF VECTOR VALUES where 6.2.  QUANTIZATION OF VECTOR VALUES and all components are quantized independently. The optimization problem is reduced in this case to the choice of values 6.2.  QUANTIZATION OF VECTOR VALUES whose work

6.2.  QUANTIZATION OF VECTOR VALUES (6.2.7)

there is a fixed number of quantization levels for a given vector. Quantization error 6.2.  QUANTIZATION OF VECTOR VALUES th reference equals

. 6.2.  QUANTIZATION OF VECTOR VALUES . (6.2.8)

In systems with digital coding, the number of quantization levels is usually chosen equal to the binary number.

6.2.  QUANTIZATION OF VECTOR VALUES , (6.2.9)

Where 6.2.  QUANTIZATION OF VECTOR VALUES - integer number of code bits (bits) for 6.2.  QUANTIZATION OF VECTOR VALUES th components of the vector. The total number of code bits must be constant and equal to

6.2.  QUANTIZATION OF VECTOR VALUES . (6.2.10)

This method of quantization is called block.

Several experts [7-9] have developed algorithms for the distribution of the number of digits. 6.2.  QUANTIZATION OF VECTOR VALUES with fixed 6.2.  QUANTIZATION OF VECTOR VALUES to minimize the root mean square quantization error. When using the algorithm proposed by Redi and Winz [9] and used to quantize independent Gaussian values ​​using the Max method, the following operations should be performed:

1. To calculate the distribution of the number of digits by the formula

6.2.  QUANTIZATION OF VECTOR VALUES , (6.2.11)

Where 6.2.  QUANTIZATION OF VECTOR VALUES - dispersion 6.2.  QUANTIZATION OF VECTOR VALUES -th countdown.

2. Round each of the numbers. 6.2.  QUANTIZATION OF VECTOR VALUES to the nearest integer.

3. Change the distribution obtained until condition (6.2.10) is satisfied

The derivation of relation (6.2.11) is based on the exponential approximation of the dependence (6.1.12), which relates the quantization error 6.2.  QUANTIZATION OF VECTOR VALUES of reference and the number of digits given to it 6.2.  QUANTIZATION OF VECTOR VALUES . If a 6.2.  QUANTIZATION OF VECTOR VALUES is small, then this approximation turns out to be rather coarse. More reliable results can be obtained using the minimal error method developed by Pratt [10]. Here the digits are successively retracted to the samples that have the largest differential error (6.2.8). When quantizing values ​​with zero mean, the algorithm consists of the following steps:

Step 1. Determination of the initial conditions:

6.2.  QUANTIZATION OF VECTOR VALUES - the total number of digits in the code combination block,

6.2.  QUANTIZATION OF VECTOR VALUES - block length

6.2.  QUANTIZATION OF VECTOR VALUES - dispersion components

6.2.  QUANTIZATION OF VECTOR VALUES - the probability density of the components

6.2.  QUANTIZATION OF VECTOR VALUES - discharge index (zero first).

Step 2. Calculate and remember the differential error coefficients.

6.2.  QUANTIZATION OF VECTOR VALUES ,

Where 6.2.  QUANTIZATION OF VECTOR VALUES and the amount

6.2.  QUANTIZATION OF VECTOR VALUES

determines the error rate for random variables with unit variance, with the tilde sign (~) marked by quantization levels and threshold levels related to such quantities.

Step 3. Allocate one digit to the component for which the product 6.2.  QUANTIZATION OF VECTOR VALUES has the greatest value; increase by one 6.2.  QUANTIZATION OF VECTOR VALUES and 6.2.  QUANTIZATION OF VECTOR VALUES .

Step 4. If 6.2.  QUANTIZATION OF VECTOR VALUES , finish the procedure; otherwise repeat step 3.

Differential Error Ratios 6.2.  QUANTIZATION OF VECTOR VALUES necessary for this algorithm can be calculated in advance and stored as a table from 6.2.  QUANTIZATION OF VECTOR VALUES numbers In this case, the algorithm reduces to 6.2.  QUANTIZATION OF VECTOR VALUES sequential bit allocation operations. The advantages of the algorithm are that it does not require cumbersome calculations, and there are no approximation and rounding errors characteristic of the algorithm with the calculation of the logarithms of the variances. In addition, the minimum error method relies on a probability density model and, therefore, it can be effectively used for the distribution of discharges at different sample probability densities.

See also


Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Digital image processing

Terms: Digital image processing