TWI430204B - Codebook generating method - Google Patents

Description

Codebook generation method

The present invention relates to a codebook generation method, and more particularly to a codebook generation method for image compression technology.

Generally, in the image compression technology, a codebook is usually generated by a codebook generation method, and then the original input image is replaced by a smaller codebook when the image is saved and the image is transferred. The purpose of compression; conversely, when decompressing, the codebook is restored to a plurality of restoration blocks by a decoding algorithm, and finally these reduction blocks are combined into a reconstructed image, that is, the step of decompressing is completed.

The conventional codebook generation method generally performs a "cutting" on an original input image, and cuts the original input image into smaller and larger number of original blocks, and the vector is quantized by a vector quantization (VQ, Vector Quantization) technique. These original blocks are converted to the original vector. The original vectors are processed by a coding algorithm to obtain a representative number of codewords that can represent the original input image to form the codebook through the representative blocks.

Conventional coding algorithms, such as the LBG algorithm, were proposed in 1980 by Linde, Buzo, and Gray. The concept is similar to the K-means method in the data grouping method. The first step is to perform a first step of presetting a distortion degree parameter ε and a group number k to be grouped; then performing a second step of randomly selecting k original vectors from the original vectors as centroid points; and then performing a third The step performs Euclidean distance operations on each of the original vectors and all the centroid points to group the original vectors into the corresponding centroid points; and then performs a fourth step to obtain the quality of the original vectors in each group. The heart is taken as a new centroid point; then a fifth step is performed to calculate the difference between the new centroid point and the old centroid point, that is, the degree of distortion, and if the distortion is not less than the distortion parameter ε, repeat the In the third step, if the difference is greater than the distortion parameter ε, the training is completed, and the obtained centroid point can be used as the representative block to form the codebook.

In general, the above LBG algorithm is performed in a random initial manner, and the number of original vectors is large and complicated. Therefore, the result obtained by the LBG method is not stable, which has the disadvantage of poor quality. .

Another conventional coding algorithm, such as the Self-Organizing Map (SOM) method, as shown in FIG. 1, is a first step of converting a number of pixels (pixels) in an image into numbers. Input sample 8; then perform a second step to preset N neurons 9 and randomly select N input samples as the initial position of the N neurons 9; then perform a third step to randomly select an input sample 8 And the input sample 8 is respectively subjected to a Euclidean distance operation with all the neurons 9; then a fourth step is performed to select the neuron 9 having the shortest distance as a superior neuron 91, and the superior neuron 91 and the distance are adjusted. The superior neuron 91 is adjacent to the adjacent neuron 92 in the radius R, causing the superior neuron 91 and the adjacent neuron 92 to shift to the one input sample 8. Then, a fifth step is performed to determine whether all the input samples 8 are completed. The Euclidean distance calculation, if not, the third step is performed, and if so, the training is completed, and the adjacent radius R is reduced according to a certain ratio, and then the next training is performed until the number of iterations reaches After the predetermined number of iterations, the neural network can be obtained from this plurality of FIG. 9 composed of neurons. Thus, the obtained neurons 9 can be applied as an encoder to image compression technology.

The above conventional coding algorithm can obtain a satisfactory neural network map because a large number of operations are required, and the more the number of the neurons 9 or the more the input samples 8, the longer the operation time is required. Therefore, it takes a lot of time to perform calculations, resulting in its inefficiency.

Another conventional coding algorithm, such as the Fast SOMs method, is based on the self-organizing map method described above, which first divides the input samples into N groups by the K-means algorithm, and the N system and the The number of neurons is the same; then the group points of the N group are used as the initial positions of the N neurons, so that a preliminary neural network map can be obtained; and then the self-organizing map method is used for the operation. , can shorten the operation time of the self-organizing map method.

However, the above Fast SOMs method is not suitable for the processing of high-dimensional data because the initial position of the neuron utilizes the concept of two-dimensional space.

Another conventional coding algorithm, such as the hierarchical self-organizing map (HSOM) method, the main concept is to divide the calculus process of the self-organizing map method into two layers, for example, if the neurons in the original self-organizing map method The default is 16 × 16 = 256, the time complexity will be higher, and this rule is to use 16 first-level neurons, after using the self-organizing map method to complete the first layer of training, then the number The input samples are grouped into the 16 first-level neurons to be divided into 16 groups of input samples; 16 second-level neurons are respectively input to each group of input samples, and the second layer training is completed by using the self-organizing map method. After that, 16 second-level neurons can be obtained from the input samples of each group, so that 16×16=256 second-layer neurons can be obtained. In this way, the time complexity of the self-organizing map method can be reduced.

However, due to the hierarchical self-organizing map method, the number of neurons in the first layer and the second layer are trained by the SOM algorithm, and the training time is longer; and the number of input samples in each group is different. Each group performs the training of the second layer of neurons with the same number of neurons. The same cannot describe the true distribution of the input samples, which makes it have the disadvantage of poor training accuracy. Moreover, during the SOM training process, It may be that some neurons have poor initial positions, which cause the neurons to never become superior neurons during training, and the neurons cannot accurately describe the true distribution of the input samples.

For the above reasons, it is necessary to further improve the above-described conventional codebook generation method.

The present invention is to improve the above disadvantages to provide a method for generating a codebook for the purpose of reducing the time cost of generating a codebook.

The second object of the present invention is to provide a method for generating a code book, which can improve the compression quality of image data.

Still another object of the present invention is to provide a method for generating a codebook which can improve the accuracy of distribution of neurons.

The method for generating a codebook according to the present invention comprises: a cutting conversion step of dividing an original input image into a plurality of original blocks, converting each original block into an original vector, and setting a size of the code book; In the preliminary grouping step, the plurality of original vectors are grouped by a split clustering algorithm to obtain a plurality of first centroid points, and the original vectors are separately grouped to the closest first centroid point to obtain a number Clustering; a neuron allocation step of assigning the number of neurons in each cluster according to the degree of distortion, and then selecting a plurality of original vectors as the neurons in each cluster according to the distribution result, wherein the total number of the neurons is The codebook has the same size; a neuron training step takes the original vector in each cluster as a sample, and uses a self-organizing map (SOM) algorithm to train the neurons in each cluster to obtain the number. a final neuron; an idle neuron decision step, selecting one of the clusters, and defining the final neuron in the cluster that has never been the winner as a idle neuron; In the substitution step, the original vector in the cluster is grouped by a split clustering algorithm to obtain a second centroid point corresponding to the number of idle neurons, and the idle heart is replaced by the second centroid as the final nerve A termination step determines whether all the idle neurons of the cluster have been replaced. If the determination is "No", the idle neuron determination step is re-executed. If the determination is "Yes", then the final The vectors corresponding to the neurons are stored together in the codebook.

The above and other objects, features and advantages of the present invention will become more <RTIgt; The codebook generating method of the preferred embodiment of the present invention comprises a cutting conversion step S1, a preliminary grouping step S2, a neuron allocation step S3, a neuron training step S4, an idle neuron determining step S5, and a substitution step. S6 and a termination determination step S7.

Referring to FIG. 2, the codebook generating method of the present invention connects at least one database as an execution architecture by using a computer system, wherein at least one original input image is stored in the database, and the original input image is Consists of several pixels.

Referring to Figures 2 and 3, the cutting conversion step S1 of the present invention divides an original input image into a plurality of original blocks, converts each original block into an original vector 11, and sets the size of an encoded book. For example, if the image data is a 512×512 image file, the original input image can be cut into 16384 original 4×4 blocks, and each original block will contain 16 pixels, and then the vector will be transmitted. The quantization (VQ, Vector Quantization) technique converts the pixels in the 16384 original blocks into the original vector 11 and stores them in the database. The size of the codebook refers to the number of vectors stored in the codebook. For example, if the user finally wants to represent the original input image in 1024 representative blocks, the size of the codebook is 1024 to accommodate 1024. A vector used to convert to the representative blocks. For example, the codebook size of this embodiment is set to 1024.

Referring to FIGS. 2 and 4, the preliminary grouping step S2 of the present invention groups the plurality of original vectors 11 by a split grouping algorithm to obtain a plurality of first centroid points 12, and the original vectors are 11 is grouped separately to the closest first centroid point 12 to obtain a plurality of clusters 2. In more detail, in the embodiment, the split algorithm is selected as an LBG grouping algorithm, wherein the LBG method is detailed as follows: the first step of the LBG method is to first set the number k of groups to be grouped, The square of the group number k is preferably equal to the size of the codebook. Continuing the above example, the size of the codebook is 1024=k ² , then the number k of the group is And then performing the second step of the LBG method, randomly selecting 32 initial positions of the initial centroid points from the original vectors 11; and then performing the third step of the LBG method, respectively, the original vectors 11 and the initial centroids The points are subjected to a Euclidean distance operation to group the original original vectors 11 to the corresponding initial centroid points; then the fourth step of the LBG method is performed to find the centroid of the original vector 11 in each group as a new centroid point; then performing the fifth step of the LBG method to calculate the distortion, which is the difference between the new initial centroid point and the old initial centroid point, if the distortion is not less than the distortion For the parameter, the third step of the LBG method is repeated. If the difference is greater than the distortion parameter, the training is completed and 32 first centroid points 12 are obtained. Each of the original vectors 11 is then subjected to a Euclidean distance operation with all of the first centroid points 12, and the original vectors 11 are grouped to the nearest first centroid point 12. Continuing the above example, the number of the first centroids 12 is 32, so that the original vectors 11 can be divided into 32 clusters 2. Wherein, the distortion is estimated by Mean Square Error (MSE), as shown in equation (a):

In the formula (a), W means the width of the image; H means the height of the image; Refers to the difference between the ( x , y )th pixel in the original image and the bit depth of the ( x , y ) pixel in the compressed image, and finds the MSE of two consecutive times, namely MSE ( t ) and MSE ( t + 1), and then find the variation of the average distortion △ If the Δ MSE is greater than the preset convergence threshold, the process proceeds to the next iteration, and vice versa. The convergence threshold of the LBG method in this embodiment is set to 0.0001. In this way, a large number of original vectors 11 can be initially grouped by a split algorithm to reduce the complexity of subsequent training, thereby greatly reducing the computation time.

Referring to Figures 2 and 5, the neuron allocation step S3 of the preferred embodiment of the present invention allocates the number of neurons 13 in each cluster 2 according to the degree of distortion, and then selects several clusters 2 according to the distribution result. The original vector 11 is used as the neuron 13, wherein the total number of the neurons 13 is the same as the size of the codebook. More specifically, continuing the above example, if the codebook size of the present invention is set to 1024 and the number of the first centroids 12 is 32, the number of neurons 16 in each cluster 2 should be configured to be 32. The size of the codebook is reached by 32×32=1024. However, the original vectors 11 in each cluster 2 are not the same, and the cluster 2 with more original vectors 11 should be configured with more neurons 13 and trained to more accurately express the distribution of the original vectors 11 of the region. Therefore, in this embodiment, the distribution of the neurons 13 is configured according to the degree of distortion of each cluster 2, which mainly transmits each sample (original vector 11) of each cluster 2 to the first corresponding to each cluster 2 through the formula (d). The sum of the distances of the centroid points 12, the formula (b) is as follows:

In equation (b), d is the sum of distances; x _ir is the rth dimension of the i-th sample; and c _r is the position of the first centroid 12 corresponding to the sample. Then, the number of neurons 13 to be placed in each cluster 2 is obtained by the equation (c), and if it is found that the _Ng value is 0, it is set to 1. Equation (c) is as follows:

N _g in the formula (c) refers to the number of neurons 13 to be disposed in the _g- th group, and the symbol [] is rounded off. In this way, more neurons 13 can be placed in the cluster 2 with a larger distance sum value to match the true distribution of the samples.

Referring to Figures 2 and 5 to 8, the neuron training step S4 of the present invention takes the original vector 11 in each cluster 2 as a sample, and uses a self-organizing map (SOM) algorithm for each cluster 2 The inner neuron 13 is trained to obtain a number of final neurons 14. More specifically, continuing the above example, as shown in FIG. 5, a plurality of original vectors 11 are randomly selected from the cluster 2 as initial positions of the neurons 13, and then through the self-organizing map algorithm to the cluster 2 The original vector 11 trains the plurality of neurons 13 as samples. The self-organizing map algorithm of this embodiment is detailed as follows: First, as shown in FIGS. 6 to 8, the first step of the SOM method is to use the formula (d) to associate one of the original vectors 11' in the cluster 2 with The neuron 13 corresponding to the assigned number performs the Euclidean distance calculation, and the neuron 13 closest to the original vector 11' is selected as the winning neuron 15. Equation (d) is as follows:

In the formula (d), w ^* _n is the superior neuron 15; the y _m is the position of the mth original vector 11, m = 1, 2... k, and w _n (t) is the nth neuron 13 The position at the tth time.

Next, as shown in FIG. 7, the second step of the SOM method adjusts the position of the neighboring neuron 16 in the vicinity S of the winning neuron 15 and the superior neuron 15 by the formula (e), and the formula (e) is as follows Shown as follows:

In the formula (e), η(t) is the learning rate of the tth time; r is the relative position of the neuron 13, and is represented by r : ∥ nn ^* ;; R is the radius of the adjacent region; in this embodiment, η(0)=1, radius of adjacent area .

Then, the first step and the second step of the SOM method are repeated until all the original vectors 11 complete the distance calculation.

Then performing the third step of the SOM method, updating the neighboring region radius R(t) and the learning rate η(t), where R(t+1)=R(t)×0.95, if R(t+1) <0.1, then R(t+1)=0.1; η(t+1)=η(t)×0.975, and if η(t+1)<0.01, η(t+1)=0.01.

Finally, the fourth step of the SOM method is performed to determine whether the average distortion rate is greater than a threshold. If the determination is yes, the first step to the third step of the SOM method are repeated; if the determination is no, the termination is terminated. SOM method. The calculation of the average distortion rate is detailed as follows: First, the sum of the distances of all samples (original vector 11) and their corresponding neurons is calculated by equation (f):

In the formula (f), x _ir is the rth dimension of the i-th sample; c _r is the position of the neuron corresponding to the sample. Further, the average distortion is obtained by dividing the sum of the distances by the number of samples (the denominator in the formula (g)) as shown in the formula (g).

Then, the average distortion rate is calculated by the equation (h), and it can be determined whether the average distortion rate is greater than the threshold value. The threshold value of the embodiment is set to 0.0001.

As described above, the difference between the SOM method and the conventional SOM method adopted by the present invention is that the conventional SOM method uses the preset number of iterations as the termination condition, so even if the training process is fairly close to the correct distribution, the preset must be reached. The number of iterations can be terminated, and it is not possible to properly adjust the samples with large differences in distribution, and it will take too much time to perform redundant operations. The present invention is improved, and the average distortion rate is used as a basis for determining the termination conditions, so that it can be used for various samples. The distribution is differentiated to avoid unnecessary time costs. At this point, the neuron training step S4 is completed and a plurality of final neurons 14 are obtained, as shown in FIG.

Referring to Figures 2, 6 and 9, the idle neuron determining step S5 of the preferred embodiment of the present invention selects one of the clusters 2' and the winner of the cluster 2' never becomes the winner. Neuron 14 is defined as an idle neuron 17. More specifically, in the neuron training step S4 described above, some of the neurons 13 may never become the winning neuron 15 during the SOM training process, and become the final neuron 14 directly after the SOM training is completed. The waste of the neurons 13 is so defined in the idle neuron determination step S5 that the final neuron 14 which has never become the superior neuron 15 in the cluster 2' is defined as the idle neuron 17, and the substitution step S6 is performed.

Referring to Figures 2, 9 and 10, the substitution step S6 of the preferred embodiment of the present invention groups the original vectors 11 in the cluster 2' by a split-group algorithm to obtain corresponding idle neurons 17 The second centroid point 18 is replaced by the second centroid 18 as the final neuron. More specifically, as shown in FIG. 9, if there are three idle neurons 17 in the cluster 2', the original vector 11 in the cluster 2' is grouped by a split algorithm, and this embodiment selects The LBG clustering algorithm is used to perform grouping to obtain three second centroid points 18 corresponding to the number of idle neurons 17, and replace the three idle neurons 17 with the three second centroids 18, such as the tenth The figure is shown to avoid that the idle neurons 17 cannot truly express the distribution of the original vector 11.

Referring to Figures 2, 10 and 11, the termination determining step S7 of the preferred embodiment of the present invention determines whether all of the idle neurons 17 of the cluster 2 have been replaced. If the determination is "No", the In the idle neuron determination step S5, if the determination is YES, the vectors corresponding to the final neurons 14 are collectively stored in the codebook. More specifically, it is then determined whether all of the idle neurons 17 of the cluster 2 have been replaced by the second centroid 18, and if the idle neurons 17 in the cluster 2 have not been replaced, the idle nerves are re-executed. The element judges step S5; if all the idle neurons 17 in the cluster 2 have been replaced, the vector corresponding to the obtained final neuron 14 is stored in the codebook, and the codebook generating method of the present invention can be completed.

The vector in the codebook obtained through the above steps of the present invention can be converted into a plurality of representative blocks, and each of the representative blocks has a corresponding code. In this way, the original block in the original input image can be compared with the representative blocks, and the code of the nearest representative block is used as an index to represent the original block, so that the code book with smaller capacity can be used. Represents the original input image for compression purposes.

Conversely, when decompressing, the codebook is used to restore a plurality of restored blocks through the index, and finally the restored blocks are combined into a reconstructed image, that is, the step of decompressing is completed. .

Referring to Table 1, in order to verify the compression quality and compression time of the present invention, six sets of image pictures are tested. The six sets of image pictures are Lena, Airplane, Peppers and Boat, and executed? Independent calculations to obtain average test results. The 6 sets of image pictures are pre-cut by a block size of 4×4. Among them, because the HSOM method can't handle the size of the codebook that cannot be squared, some fields in the test table have no test data (N/A, Not Available). PSNR (Peak Signal-to-Noise Ratio) is a formula commonly used to evaluate compression quality. The higher the PSNR, the better the compression quality, as shown in equation (i):

The MSE in the formula (i) is as shown in the formula (a).

Among them, the INTSOM in Table 1 refers to a method of compressing the codebook generated by the present invention. As can be seen from the results of Table 1, the codebook generation method of the present invention (INTSOM) is better than the conventional LBG, SOM, and HSOM methods in terms of compression quality (PSNR) and computation time.

The present invention provides a codebook generation method for preliminary grouping the original vectors 11 through the preliminary grouping step S2 to reduce training complexity.

The present invention provides a codebook generation method for determining the number of neurons 13 arranged in each cluster 2 according to the degree of distortion, so that the neurons 13 can more realistically represent the distribution of the original vectors 11.

The invention provides a codebook generation method, which uses the average distortion rate as a termination condition judgment criterion of a self-organizing map (SOM) algorithm, and can be differentially trained according to groups of different sample distributions, thereby avoiding cost Unnecessary time costs for training.

The present invention provides a codebook generation method that replaces the idle neurons 17 with the second centroids 18 to avoid waste of the neurons 17.

While the invention has been described in connection with the preferred embodiments described above, it is not intended to limit the scope of the invention. The technical scope of the invention is protected, and therefore the scope of the invention is defined by the scope of the appended claims.

[this invention]

11. . . Primitive vector

11’. . . Primitive vector

12. . . First centroid

13. . . Neurons

14. . . Ultimate neuron

15. . . Winning neuron

16. . . Adjacent neurons

17. . . Idle neurons

18. . . Second centroid

2. . . Cluster

2'. . . Cluster

R. . . Adjacent area radius

[customary]

8. . . Input sample

9. . . Neurons

91. . . Winning neuron

92. . . Adjacent neurons

Figure 1: Schematic diagram of a conventional coding algorithm.

Fig. 2 is a flow chart showing a method of generating a codebook of the present invention.

Figure 3 is a diagram showing the original vector distribution of the codebook generation method of the present invention.

Figure 4 is a schematic illustration of the preliminary grouping steps of the codebook generation method of the present invention.

Figure 5: Initial schematic diagram of neurons performing SOM in the neuron training step of the present invention.

Fig. 6 is a schematic view showing the superior neurons of the SOM in the neuron training step of the present invention.

Figure 7 is a schematic diagram showing the position of the SOM adjusting neuron in the neuron training step of the present invention.

Figure 8: A partial schematic view of the completion of the neuron training procedure of the present invention.

Figure 9: Schematic diagram of the completion of the neuron training steps of the present invention.

Fig. 10 is a view showing the steps of judging the idle neurons of the present invention.

Figure 11: Schematic representation of the substitution steps of the invention.

Claims (5)

A codebook generating method includes: a cutting conversion step of dividing an original input image into a plurality of original blocks, converting each original block into an original vector, and setting a size of an encoding book; a preliminary grouping step, The plurality of original centroids are grouped by a split clustering algorithm to obtain a plurality of first centroid points, and the original vectors are respectively grouped to the closest first centroid point to obtain a plurality of clusters; The neuron allocation step allocates the number of neurons in each cluster according to the degree of distortion, and then selects a plurality of original vectors as the neurons in each cluster according to the distribution result, wherein the total number of the neurons is associated with the codebook The same size; a neuron training step, taking the original vector in each cluster as a sample, and using the self-organizing map (SOM) algorithm to train the neurons in each cluster to obtain several final neurons. An idle neuron judging step, selecting one of the clusters, and defining the final neuron in the cluster that has never been the winner as an idle neuron; a step of grouping the original vectors in the cluster by a split clustering algorithm to obtain a second centroid point corresponding to the number of idle neurons, and replacing the idle neurons with the second centroid as the final neuron As soon as the judgment step is terminated, it is determined whether all the idle neurons of the cluster have been replaced. If the determination is "No", the idle neuron determination step is re-executed. If the determination is "Yes", the final nerves are determined. The vectors corresponding to the elements are stored together in the code book. The method for generating a codebook according to claim 1, wherein in the neuron allocation step, the number of neurons configured in each cluster is determined according to the degree of distortion according to the formula (c); Where _dl is the sum of the distances between the original vectors in the gth cluster and the center of the cluster. The method for generating a codebook according to claim 1, wherein the self-organizing map algorithm in the neuron training step is based on whether the average distortion rate is lower than a threshold value, or whether the training frequency is equal to a predetermined number of times. Judgment basis for termination conditions. The method for generating a codebook according to item 3 of the patent application scope, wherein the threshold value is 0.0001. The method for generating a codebook according to claim 1, wherein the split clustering algorithm is an LBG algorithm.