Efficient image compression based on side match vector quantization and digital inpainting

Abstract

In this paper, we propose two efficient compression schemes for digital images using an adaptive selection mechanism for vector quantization (VQ), side match vector quantization (SMVQ), and image inpainting. On the sender side, after the original image is divided into blocks, the compression is implemented block by block. In both schemes, blocks in pre-specified locations are first compressed by VQ. For each remaining block, the optimal compression method (for the first scheme, including VQ or inpainting, and for the second scheme, including VQ, SMVQ, and inpainting) is determined by computing the mean square error (MSE) between the original block and its inpainted result and then comparing it with a predefined threshold. If MSE is greater than the threshold, image inpainting continues to be used to compress the current block. Otherwise, the compression mode of VQ or SMVQ is selected to substitute image inpainting to maintain higher visual quality. With the assistance of transmitted indicator flags, the receiver side can execute the image inpainting and decompression successfully. Experimental results demonstrate the effectiveness and superiority of two proposed schemes.

1 Introduction

With the rapid development of Internet, more and more multimedia data needs to be stored in the memory or transmitted through the network, which brings about traffic jam for the channel with limited bandwidth. Accordingly, before data transmitting, lossless or lossy compression, i.e., source coding, can be performed on the sender side to increase transmission efficiency [1,2,3,4] under the condition that the distortion on the data after decompression can be tolerated by the receiver. An ideal lossy compression scheme should achieve both satisfactory compression ratio and reconstruction fidelity for the sender and receiver sides, respectively. However, these two aspects, i.e., compression ratio and reconstruction fidelity, are obviously contradictory with each other. In other words, higher compression ratio often leads to poorer reconstruction fidelity. Digital images, as the important information carrier, are widely used and transmitted through Internet in our daily life, therefore, how to design an effective compression scheme for digital images deserves in-depth investigation.

Among state-of-the-art image-compression techniques, vector quantization (VQ) has been widely studied due to its satisfactory rate-distortion performance and high efficiency in real-time implementation [5,6,7,8,9] and has been applied in fields of image watermarking [10] and image data hiding [11]. In addition, block truncation coding (BTC) is widely used to compress digital image and generate encoded bits [12, 13], whose working mechanism is similar to the VQ compression method. In VQ compression, the encoder and the decoder both have the same codebook, which consists of a number of codewords. During compression, the original image is processed in a block-wise manner. The Euclidean distance is calculated to evaluate the similarity between the current image block and all codewords in the codebook; then, the index of codewords with the smallest distance is regarded as the compressed data of the current image block. After all nonoverlapping blocks are represented by the index values of codewords, an index table consisting of all index values is produced as the VQ compressed code of the image. Because only index values rather than all pixel values of the image are used as the encoded result, VQ compression is an effective algorithm. During VQ decompression, because each index value in the received index table corresponds to an image block, a simple operation of lookup table can be performed in the codebook to find the codeword that corresponds to the index value; then, the found codeword is regarded as reconstructed pixel values of the image block. Note that the length of the binary representation for the largest index value is the length of the compressed code for each block; that is to say, the size of the codebook can influence the compression ratio and the reconstruction quality simultaneously. In addition, the greatest weakness of VQ encoding is the neglect of the relationships between neighboring image blocks.

In order to improve the defects of VQ and further enhance its performance of compression, side match vector quantization (SMVQ) was designed as an improvement of VQ [14], which considers the correlation between neighboring image blocks effectively. Differently than VQ, the codebook and the sub-codebooks are used to generate the index values in an SMVQ encoding procedure (details of SMVQ are given in Sect. 2.1). In recent years, many researchers have studied novel image compression schemes based on SMVQ [15,16,17] and applied SMVQ in extended fields such as image data hiding [18]. In [15], the sender segmented the original image into a series of nonoverlapping blocks and encoded the leftmost and upmost blocks through VQ. The residual smooth blocks were compressed through SMVQ, and the complex blocks were compressed through VQ. In [16], an adaptive block classification was presented to achieve lower distortions. A remedy scheme was proposed in [17] to solve the problem in that the error of the current block may be diffused to the following blocks.

In this paper, we propose two efficient compression schemes for digital images using an adaptive selection mechanism for VQ, SMVQ, and image inpainting. The main purpose of the proposed schemes is to achieve a higher compression rate while maintaining a reasonable visual quality. In both of our schemes, image blocks at the pre-specified partial regions are first compressed by VQ. For each remaining block, the optimal compression method (for the first scheme, including VQ or inpainting and for the second scheme, including VQ, SMVQ, and inpainting) is determined by computing the mean square error (MSE) between the original block and its inpainted result and then comparing it with a predefined threshold. If MSE is greater than the threshold, image inpainting continues to be used to compress the current block. Otherwise, another compression mode (VQ for the first scheme, and VQ or SMVQ alternatively for the second scheme) is selected to replace image impainting to maintain higher visual quality.

The rest of this paper is organized as follows: Section 2 introduces the preliminary knowledge of SMVQ and image inpainting. Section 3 describes two proposed schemes in detail. Experimental results and comparisons are given in Sect. 4. Section 5 concludes this paper.

2 Preliminary knowledge

2.1 SMVQ

SMVQ is designed to minimize the block effect caused by VQ. For original image I_o with the size of M × N, blocks with the size of B × B in the top row and in the leftmost column are regarded as specific regions and first encoded by VQ; the remaining blocks with the same size of B × B are treated as regular regions and encoded by SMVQ in a raster-scanning order. Take the encoding process of one regular block as an example: the current to-be-encoded block is denoted as B_{i, j}, where subscripts i and j indicate the row and column indices of the block in the entire image, respectively, and 2 ≤ i ≤ M/B, 2 ≤ j ≤ N/B. Note that, for ease of description, we assume both M and N here are divisible by B. The left and upper adjacent blocks of B_i,j, i.e., B_i,j−1 and B_i−1,j, respectively, are used to generate a reference vector. As shown in Fig. 1, c_1,1, {c_p,1, 2 ≤ p ≤ B}, and {c_1,q, 2 ≤ q ≤ B} are the top left corner pixel, left border, and upper border of B_i,j, respectively. In addition, the B pixels in the bottom border of B_i−1,j are denoted as {u_B,q, 1 ≤ q ≤ B}, and B pixels in the right border of B_i,j−1 are denoted as {l_p,B, 1 ≤ p ≤ B}. The pixel values of c_1,1, {c_p,1}, and {c_1,q} are predicted as.

Fig. 1

Prediction process of SMVQ

$$\left\{ {\begin{array}{*{20}{l}} {{{\hat {c}}_{1,{\text{ }}1}}={\text{ }}({u_B}_{{,{\text{ }}1}}+{l_{1,B}})/2{\text{ }}} \\ {{{\hat {c}}_{p,1}}={l_p}_{{,B}}{\text{ }}} \\ {{{\hat {c}}_{1,q}}={u_B}_{{,q}}{\text{ }}} \end{array}} \right.$$

(1)

Then, a reference vector composed by $\{ {\hat {c}_{p,1}},{\hat {c}_{1,1}},{\hat {c}_{1,q}}\}$ is generated to search the predefined codebook Ψ to extract a sub-codebook Ψ_S, which includes S closest codewords. Specifically, for a codebook Ψ with W codewords {C^w, 0 ≤ w ≤ W − 1}, the horizontal and vertical side-match distortion (SMD), denoted as $H_{{{\text{SMD}}}}^{w}$ and $V_{{{\text{SMD}}}}^{w}$, respectively, between the reference vector and each codeword can be calculated by

$$\left\{ {\begin{array}{*{20}{l}} {H_{{{\text{SMD}}}}^{w}=\sum\nolimits_{{p=1}}^{B} {{{({{\hat {c}}_{p,1}} - c_{{p,1}}^{w})}^2}} } \\ {V_{{{\text{SMD}}}}^{w}=\sum\nolimits_{{q=1}}^{B} {{{({{\hat {c}}_{1,q}} - c_{{1,q}}^{w})}^2}} } \end{array}} \right.,$$

(2)

where $c_{{p,1}}^{w}$ and $c_{{1,q}}^{w}$ are the corresponding elements of ${\hat {c}_{p,1}}$ and ${\hat {c}_{1,q}}$in C^w. Thus, the total SMD of the codeword can be calculated as:

$${E^w}=H_{{{\text{SMD}}}}^{w}+V_{{{\text{SMD}}}}^{w}.$$

(3)

After E^w of all codewords in codebook Ψ are calculated, the S codewords with the smallest E^w are selected and composed together to generate the sub-codebook Ψ_s, and the index value of the closest codeword in Ψ_s is regarded as SMVQ-encoded data.

2.2 Image inpainting

Nowadays, the image inpainting technique is widely used to amend an image whose partial region is missing [19, 20]. Currently, there are three main categories of inpainting methods based on different strategies: interpolation-based methods, patch-based methods, and partial differential equation (PDE)-based methods. Compared with the former two categories, PDE-based methods have better performance in patching, especially for image structure information. Therefore, in this work, a PDE-based image inpainting technique is exploited to obtain the reconstructed image using a total variation (TV) model [21, 22], which is essentially an anisotropic diffusion method. By transmitting adjacent gray-scale information along the vertical direction of the gradient, the image structure information in the target area can be effectively restored, and the iterative repair process is stopped when the gray-scale value in the calculation domain reaches a stable state [see Eq. (4)]:

$$\frac{\partial }{{\partial t}}{\mathbf{I}_d}(m,n)={\text{div}}\left[ {\frac{{\nabla {\mathbf{I}_{\text{d}}}(m,n)}}{{|\nabla {\mathbf{I}_{\text{d}}}(m,n)|}}} \right],\quad \forall (m,n) \in {\Theta ^+},$$

(4)

where ∇I_d(m, n) represents the gradient at the image pixel I_d(m, n), t is the time index, div(·) is the divergence operator, and Θ⁺ denotes the region consisting of all the to-be-amended pixels Θ and their close neighborhood ∂Θ in the current image I_d. By using the finite difference method, we can obtain a discretized iteration algorithm to solve the PDE in Eq. (4). For more details of TV-model-based image inpainting, please refer to [22].

3 Proposed scheme

In this section, we propose two novel image compression schemes using two different adaptive selection mechanisms for VQ, SMVQ, and image inpainting. In scheme I, an original image is divided into nonoverlapping blocks, and the image compression is conducted block by block; moreover, blocks in predetermined specific regions are compressed by VQ, and an optimal compression method (inpainting or VQ) is adaptively determined for the remaining blocks according to the MSE between the original block and its candidate decompression result. In order to further decrease the compression ratio and overcome the block effect, scheme II is proposed as an improvement of scheme I, specifically, an original image is divided into overlapping blocks with a designated rule, and compression is conducted block by block. For the current block for compression, boundary sub-blocks are compressed by VQ, and an optimal compression method (inpainting, SMVQ, or VQ) is adaptively determined for nonboundary sub-blocks according to the MSE between the original sub-block and its candidate reconstructed result. After receiving the compressed codes of the image, decompression and TV-inpainting techniques are used to obtain a reconstructed image. Details of the proposed schemes are presented in the following.

3.1 Proposed scheme I

As denoted above, I_o is an original gray-scale image sized M × N. In order to compress I_o, we first divide original image I_o into a series of nonoverlapping blocks sized B × B with a raster-scanning order, i.e., {B_{i, j}, i = 1, 2, …, M/B, j = 1, 2, …, N/B}. Then, blocks located at all four boarders of the image, and the blocks with the indices i and j being even or odd at the same time, which are marked by gray blocks (as shown in Fig. 2) and are compressed by VQ with codebook Ψ. In scheme I, because all blocks are compressed using two strategies, i.e., VQ and image inpainting alternatively, to decompress each block during the receiver side, a flag to indicate the specific compression mode is set and transmitted. For gray blocks, the flag for each block is set as a binary number 0₂; then, the index of the most similar codeword in Ψ is regarded as the compression data for the current block. The remaining white blocks in Fig. 2 are compressed with an adaptive strategy, as Fig. 3 shows.

Fig. 2

Diagram of to-be-compressed blocks using scheme I. Gray blocks for VQ compression and white for an adaptive selection mechanism for VQ and image inpainting

Fig. 3

Flowchart of compression for remaining blocks in scheme I

Denote the current to-be-compressed remaining block as B_i,j, where 2 ≤ i ≤ (M/B − 1), 2 ≤ j ≤ (N/B − 1), and both i and j cannot be the odd or even numbers at the same time. Then, predict the value of B_i,j through conducting the image inpainting operation as described in Sect. 2.2. The MSE between B_i,j and its predicted version is denoted as E_i,j and calculated as:

$${E_{i,j}}=\frac{{\sum\nolimits_{{q=1}}^{B} {\sum\nolimits_{{p=1}}^{B} {{{({c_{p,q}}+{{\tilde {c}}_{p,q}})}^2}} } }}{{B \times B}},$$

(5)

where c_p,q is the pixel value in block B_i,j, ${\tilde {c}_{p,q}}$ is its corresponding prediction value. Next, we set a threshold T, if E_i,j > T, it implies that block B_i,j is a relatively complex region and cannot be well represented without using its own data; in this case, VQ is used to compress block B_i,j, and the corresponding flag is set as 0₂. Otherwise, if E_i,j ≤ T, it implies block B_i,j is in a relatively smooth region and can be reconstructed with high quality through merely using its neighboring blocks; thus, in this case, B_i,j is compressed using an inpainting technique, and its flag is set as 1₂. Finally, all encoded data by VQ and the flag table are transmitted to the receiver.

When receiving the encoded data and the flag table, the receiver, who has the same codebook Ψ, performs VQ decoding on blocks when the corresponding flag is 0₂; specifically, a table lookup operation according to the index could obtain the corresponding codeword in Ψ; then, put the codeword into a vacant corresponding block to obtain a reconstructed block. Otherwise, TV inpainting is performed on blocks when the corresponding flag is 1₂. After the implementation of TV inpainting, the final decompressed image I_r can be reconstructed.

3.2 Proposed scheme II

To further seek a higher compression ratio, a more sophisticated adaptive compression strategy is used in scheme II. First, an original image I_o is divided into K × K-sized overlapping larger blocks, where K is divisible by B. Thus, a block-sized K × K contains (K/B) × (K/B) sub-blocks sized B × B. We denote a K × K block as κ_t, where t is the block label. Note that the overlapping area between two adjacent larger blocks is mandatorily set at B × K or K × B. That is to say, the B × B-sized sub-blocks located at the boundary of block κ_t are exactly the overlapping areas. Figure 4 shows the diagram of a pair of overlapping blocks, i.e., κ_t and κ_t+1. It is easy to imagine that the greater the value of K/B, the more non-edge sub-blocks (white sub-blocks as shown in Fig. 4) may be compressed by other higher-efficiency compression modes, such as SMVQ or TV inpainting; thus, the higher compression ratio will be obtained. However, a higher compression ratio may result in a worse recovery quality; in scheme II, we sought a balance between the compression ratio and the recovery quality and set K/B at 8. Take the compression process of κ_t as an example: to guarantee the compression quality, first, all boundary sub-blocks of κ_t are compressed by VQ, and flags are set as 0₂, which are marked with a gray color, as shown in Fig. 4. Next, the remaining 36 nonboundary sub-blocks are denoted as {${\mathbf{B}}_{h}^{t}$, h = 1, 2, …, 36}, where t and h are the indices of the K × K-sized block and B × B-sized sub-block, respectively. A flow chart of compression of block κ_t is shown in Fig. 5.

Fig. 4

Diagram of two adjacent overlapping blocks κ_t and κ_t+1

Fig. 5

Flowchart of compression of block κ_t using scheme II

As Fig. 5 shows, for current processing block κ_t, the TV-inpainting technique is first conducted on all nonboundary sub-blocks B_h^t (h = 1, 2, …, 36) with the assistance of the decompressed boundary sub-blocks, and the total MSE E_t between the predicted values of nonboundary sub-blocks, and its corresponding original pixel values is calculated according to Eq. (5) to judge whether the block is a smooth region. If E_t ≤ T, it implies that block κ_t is a relatively smooth region and can be recovered with satisfactory quality merely using its boundary sub-blocks; thus, all sub-blocks B_h^t (h = 1, 2, …, 36) can be compressed using an inpainting technique and set flags of B_h^t (h = 1, 2, …, 36) as 11₂. Otherwise, if E_t > T, it implies the block κ_t is a relatively complex region and cannot be well represented merely using the inpainting result; thus, all nonboundary sub-blocks are processed one by one in a raster-scanning order, and an optimal compression method is determined to compress B_h^t. Specifically, compress the first uncompressed sub-block B_h^t using SMVQ and calculate its distortion E^t_h according to Eq. (5); if E_h^t ≤ T, keep using SMVQ to compress current sub-block B_h^t and set the flag as 10₂; otherwise, use VQ to compress current sub-block B_h^t and set the flag as 0₂. After B_h^t is compressed, perform the TV-inpainting operation circularly on the sub-blocks not yet compressed in κ_t with the reference of all boundary sub-blocks and already processed nonboundary sub-blocks. Note that all reference sub-blocks for inpainting are their decompressed versions. If E_t is still larger than T, compress the next unprocessed sub-block B_h+1^t and select an optimal compression method for it. Close the above loop until all nonboundary sub-blocks have been compressed or E_t ≤ T; then, process the next block κ_t+1 in the same way.

It is worth noting that, with all K × K-sized overlapping blocks processed, if there are remaining border areas smaller than K × K, so that they cannot be processed by the scheme shown in Fig. 5, we deal with these areas using a specific method. If the remaining areas can be divided into B × B sub-blocks, use SMVQ to encode the remaining sub-blocks and calculate the MSE between the decoded version and its corresponding original version, if MSE is equal to or less than the predefined threshold T, keep using SMVQ to encode the sub-block and set the flag as 10₂; if MSE is greater than T, change to use VQ to encode the sub-block and set the flag as 0₂. If the remaining area cannot be further divided into B × B-sized sub-blocks, the original pixel values of the remaining area are kept unchanged and transmit the original pixel values. Finally, all compressed data of sub-blocks, pixel values of remaining area without compression, and the flag table are regarded as final compressed data and transmitted to the receiver side.

At the receiver side, decompression is performed based on the flag table and remaining data to obtain reconstructed image I_r. Also take the decompression of κ_t as an example: for each B × B sub-block, if its flag is 10₂ or 0₂, SMVQ or VQ decompression is applied for reconstruction, respectively, and the codewords obtained from decompression are put into corresponding vacant sub-blocks of I_r to obtain the reconstructed sub-blocks. Then, the TV-inpainting technique is used for sub-blocks with the flag of 11₂; for the residual area, which is smaller than B × B, it can be recovered by the transmitted uncompressed data with no error. After all sub-blocks and the residual area are reconstructed, the final version I_r is reconstructed at this point.

4 Experimental results and analysis

Experiments were conducted on six standard gray-scale images to verify the effectiveness and superiority of the two proposed schemes. All experiments were implemented on a personal computer with a 3.30 GHz Intel i3 processor, 4.00 GB memory, and Windows 7 operating system, and the programming environment was Matlab 7. Figure 6 illustrates six standard test images sized 512 × 512, including Milk, Boat, Airplane, Peppers, Tiffany and Man.

Fig. 6

Six standard test images. a Milk, b Boat, c Airplane, d Peppers, e Tiffany, f Man

4.1 Results of image compression and reconstruction

The size of the divided nonoverlapping image blocks in scheme I are 4×4, i.e., B = 4. In the experiment of proposed scheme II, the size of the divided overlapping image blocks in scheme II were 32 × 32 and sub-blocks were 4 × 4, i.e., K = 32 and B = 4. Therefore, the length of each codeword C^w in the predefined VQ codebook Ψ was 16. Figures 7 and 8 show the reconstructed images using the parameters of T = 52 and W = 512 by schemes I and II, respectively.

Fig. 7

Reconstructed images of proposed scheme I with codebook size W = 512 and threshold T = 52. a Milk with P_SNR = 31.85 dB, b Boat with P_SNR = 29.54 dB, c Airplane with P_SNR = 30.62 dB, d Peppers with P_SNR = 31.74 dB, e Tiffany with P_SNR = 31.50 dB, f Man with P_SNR = 29.22 dB

Fig. 8

Reconstructed images of proposed scheme II with codebook size W = 512 and threshold T = 52. a Milk with P_SNR = 31.37 dB, b Boat with P_SNR = 29.44 dB, c Airplane with P_SNR = 30.38 dB, d Peppers with P_SNR = 31.17 dB, e Tiffany with P_SNR = 31.40 dB, f Man with P_SNR = 29.15 dB

The compression ratio C_R and the peak signal-to-noise ratio (PSNR) value P_SNR are applied to evaluate the performance of the proposed schemes. C_R and P_SNR can be calculated as:

$$\left\{\begin{array}{l} {C_{\text{R}}} =\frac{{8 \times M \times N}}{{{L_{\text{c}}}}} \\ {P_{{\text{SNR}}}} =10 \times {\log _{10}}\frac{{{{255}^2} \times M \times N}}{{\sum\nolimits_{{m=1}}^{M} {\sum\nolimits_{{n=1}}^{N} {{{[{\mathbf{I}_{\text{o}}}(m,n) - {\mathbf{I}_{\text{r}}}(m,n)]}^2}} } }}, \end{array} \right.$$

(6)

where L_c is the length of compressed codes, which includes bits of the flag table, and I_o(m, n) and I_r(m, n) are pixel values at location (x, y) of the original image I_o and the reconstructed image I_r, respectively.

The numerical values of the experimental results in Figs. 7 and 8 are listed merged together in Table 1. The percentages of B × B sized blocks compressed by VQ, SMVQ and image inpainting are represented by τ₁, τ₂ and τ₃, respectively, and are listed in the second to the fourth columns of Table 1. The fifth to the sixth columns show the compression ratios C_R and the PSNR values of reconstructed image I_r after TV-based image inpainting with respect to original plaintext images, which were calculated by Eq. (6). As can be seen from Table 1, the PSNR for one image of scheme I and scheme II are almost the same, but the compression ratio of scheme II is higher than that of scheme I. The reason for this improvement is probable due to that a part of blocks compressed by VQ in scheme I are compressed by SMVQ or inpainting in scheme II, which not only produces a good compression ratio, but also reduces the block effect caused by VQ.

Table 1 Performance of the proposed schemes with the parameters of T = 52 and W = 512

4.2 Influence of parameters of T and W

In order to analyze the influence of parameters on the compression performance, we conducted experiments with the different setting of two main parameters of our schemes, i.e., T and W. Variation in the setting of T and W may lead to different performances of compression ratio and qualities of the reconstructed image. Specifically, a larger threshold T may lead to more blocks compressed by inpainting and owing to the fact that inpainting-based compression can save more space than VQ and SMVQ; thus, a larger compression ratio can be achieved. On the other hand, a larger value of W implies there are more codewords in the codebook, and we can choose a more precise one to replace the current block and obtain a higher reconstructed quality. Tables 2 and 3 list the compression ratios C_R and PSNR of reconstructed images with the different setting of T and W by using the proposed schemes, from which we can see that larger T results in a higher compression ratio and lower PSNR value, while larger W leads to lower compression ratio and higher PSNR value. However, when W is a constant, the compression ratio converges with the increase of T. For example, when W = 256 and T is big enough to make all white blocks in Fig. 2 compressed by inpainting, we can obtain the limit of C_R = 24.98 of scheme I. Similarly, the limit of C_R = 31.87 of scheme II.

Table 2 Compression ratio C_R and PSNR (dB) of reconstructed image I_r in proposed scheme I

Table 3 Compression ratio C_R and PSNR (dB) of reconstructed image I_r in proposed scheme II

4.3 Performance comparison

We compared our schemes with the standard VQ, SMVQ methods, and the search-order coding (SOC) method [23]. To make a fair comparison, when the qualities of the reconstructed images are almost the same, Table 4 shows the compression ratios of different methods, where, in both of our proposed schemes, T and W were set at 44 and 256, respectively. In the other comparison methods, the codebook size was set at 256; for [23], the number of neighbor searching indicates m = 17.

Table 4 Compression ratio C_R and PSNR (dB) of different methods

As observed in Table 4, under the same codebook size, and yet maintaining a nearly coherent decompression visual quality, the compression ratios of both proposed schemes outperform standard VQ, SMVQ, and SOC methods. Specifically, scheme II has the highest compression ratio, which results in a slightly lower PSNR for complex images. It is probably due to the fact that the TV-inpainting technique limits complex images with high compression ratios. However, both of the PSNR values and compression ratios of proposed scheme I are better than those of the standard methods. Therefore, we can conclude that, if we are pursuing high compression ratios and do not care about the slight difference in quality of reconstructed images, we could choose scheme II; if we want to take a trade-off between compression ratio and quality of reconstructed image, we can take a compromise to choose scheme I.

4.4 Analysis of computation complexity

The complexity of our proposed scheme I mainly depends on partitioning, VQ coding, and inpainting. Concretely, a partition is addition and VQ coding in the table look-up operation, which are simple operations with low computation complexity. Encoding time of scheme I mainly resides on the complexity of inpainting, which relates to the number of iterations. The decoding time of scheme I not only relates to the number of iterations but also relates to the number of block B compressed by inpainting. In our simulation, when the number of iterations is set as 2000, and codebook size W is set as 256, the total time of encoding and decoding does not exceed 1 min, and the average total time of six standard test images, i.e., Milk, Boat, Airplane, Peppers, Tiffany, Man, with different parameters T are listed in Table 5.

Table 5 Average total time of scheme I for six standard images with different parameters T

Similarly, the main factors affecting the complexity of scheme II are partitioning, VQ and SMVQ coding, and inpainting. Different from scheme I, the encoding time of scheme II resides on not only the complexity of inpainting but also on the texture feature of each block κ_t. The encoding time for complex blocks is longer than that for smooth blocks because complex blocks have more loops than smooth blocks. Table 6 lists the total time of encoding and decoding for each standard test image with the setting of parameters T = 68 and W = 256, where the running time of complex images, e.g., Boat and Man, is longer than that of smooth images, e.g., Milk and Tiffany.

Table 6 Total time of scheme II for six standard images

4.5 Discussion on the performance of two schemes

For there is spatial correlation of digital images, the closer of the VQ decompressed blocks, the better inpainting quality is. In scheme I, the VQ decompressed blocks using for inpainting are at four neighboring directions. However, the VQ decompressed blocks in scheme II are not neighboring blocks for current processing block, therefore, its inpainting quality are worse than that of scheme I. The time of scheme II is longer than that of scheme I just because the loop mechanism shown as Fig. 5, only when all sub-blocks are processed or the evaluation is smaller than threshold T, the loop will come to the end, and then start to process the next block κ_t+1. There is no loop mechanism in scheme I, so its computation complexity is better than scheme II.

5 Conclusions

In this paper, we propose two compression schemes for a digital gray-scale image using VQ, SMVQ, and image inpainting. For all blocks, except for those located in predesignated regions, an optimal compression mode (including VQ, SMVQ, or inpainting) is determined through an adaptive selection mechanism. The MSE between the original block and its inpainted result is measured and then compared with a predetermined threshold T. If MSE is smaller than T, the current block is compressed by inpainting technique. Otherwise, for scheme I, it is compressed by VQ directly, while for scheme II, the compression mode SMVQ or VQ is once again alternatively selected by a comparison between MSE and threshold T. With the help of transmitted flags, the receiver side can decompress the image successfully.

Experimental results demonstrate the effectiveness and superiority of the two proposed schemes, and both schemes have their advantages. Scheme I has a lower computational complexity than scheme II, while the latter scheme provides a higher compression ratio than the former. For a relatively complex image, with a comprehensive consideration of compression ratio, quality of reconstructed image and computational time, scheme I is suggested to be applied to compress the image. For a smooth image, if we pursue a high compression ratio that exceeds the compression ratio limit of scheme I, we can choose scheme II, which can achieve a higher compression ratio and better reconstructed quality.