In what follows, we elaborate on the underlying compression-decompression mechanism based on sampling and fuzzy encoding completed on a basis of coordinated-based membership degrees. This will help us stress a systematic and coherent development process being proposed in this study as well as highlight the novelty along with the proposed mechanism. The algorithm is run for some specific values of setting-namely, the value of sampling ratio, the number of prototypes for reconstructing one pixel and the fuzzification coefficient. The effect of these values on the quality of the reconstruction will be studied later.

*A. Segmentation of image*

Before an image could be processed, it needs to be digitalized, encoded and stored. Grayscale images could be defined as a two-dimensional function, *f*(*x*, *y*), where *x* and *y* are spatial coordinate in horizontal and vertical directions, respectively. The gray level (brightness) of the image at any point (*x*, *y*) is denoted by its amplitude *f*. A sample of the image at a certain point is usually referred to as a pixel. An image consists of a finite number of pixels, each of which has a particular location and a gray-level value. There are several different ways of coding the values of gray-level at each point depending on the number of bits to represent one pixel. More bits are used to represent one pixel, more colors could be represented, and more memory and wider bandwidth are demanded when being processed. 8-bit color image is the most commonly one, which allows up to 256 colors (gray levels). A continuous digital representation of image is transformed into digital format and the values of gray-level of each square could be arranged in a two dimensional matrix.

Suppose that the original image is represented by a matrix of pixels of size *M*×*N*, and the gray level of each pixel is stored as an 8-bit integer value which therefore allows for 256 different shades of brightness ranging from 0 to 255. We set value 0 to black, 255 to white and distribute the gray scale linearly in between. The first step is to partition an image into a number of non-overlapping blocks which are adjacent to each other. Each block is a rectangle with a fixed-size *m*×*n* where *m*<<*M* and *n*<<*N*, as shown in Fig. 2. Note that the sizes of the blocks on the right or the bottom of the image may be smaller than *m*×*n*. These blocks are treated in the same way as others for uniformity. The choice of suitable values of m and n requires some attention. If the size of a block is too large, we may face the problem of explosion of search space. On the other hand, undersized block may hinder the visual quality of reconstructed image, especially in the areas near the boundaries of the blocks.

*B. Selection of prototypes*

In each block, we randomly pick up a sample of pixels, say *g* pixels; we will refer to them as prototypes and call them v1, v2, …, v*g*. The coordinates of these points are marked as (*x*1, *y*1), (*x*2, *y*2), …, (*x**g*, *y**g*) while the values of their gray levels are denoted as *f*(*x*1, *y*1), *f* (*x*2, *y*2), …, *f* (*x**g*, *y**g*), respectively. These sampling points are treated as “anchor” points based on which the block is reconstructed. The sampling ratio is described as the number of sampling points to the total number of pixels in this block and then forms the following expression *p* = *g*/(*m*×*n*). The sampling percentage *p* influences the quality of the reconstruction and compression ratio. As there is an inherent factor of randomness, the whole process is repeated a certain number of iterations and the prototypes producing the lowest reconstruction error are treated as representatives of current block. As to the sampling ratio, one option is to adopt the same sampling ratio in each sub-block; another option worth considering is to choose different values of sampling ratio for different blocks depending upon the level of details presented in the given block and this ratio could be determined based on the reconstruction criterion.

*C. Determination of membership degrees*

Let us assume that for each block of pixels, we are provided a collection of prototypes *v*1, *v*2, …, *v**g*, as shown in Fig. 3. For any pixel *s* located at coordinates (*a*, *b*) in this block that is not designated as prototype, we calculate its membership degrees to the *c* nearest prototypes among *v*1, *v*2, …, *v**g*, which are marked as *v*’1, *v*’2, …, *v*’*c*. The corresponding coordinates of these *c* prototypes are marked as (*x’*1, *y’*1), (*x’*2, *y’*2), …, (*x’**c*, *y’**c*). The choice of parameter *c* will influence the visual quality of the reconstructed image. The values of membership degrees are determined in the same manner as for Fuzzy C-Means (FCM) clustering method [23][24][28]

$${u_i}(s)=\frac{1}{{\sum\limits_{{j=1}}^{c} {{{\left( {\frac{{||s - v{'_i}||}}{{||s - v{'_j}||}}} \right)}^{2/(m - 1)}}} }}$$

1

where *u**i*(*s*) stands for the value of membership degree of pixel *s* to prototype *v*’*i*. Here ||.|| denotes a certain distance function (we use a Manhattan distance in this study, any other form of the distance could also be considered), namely, \(||s - v{'_i}||={\text{|}}a - x{'_i}{\text{|}}+{\text{|}}b - y{'_i}{\text{|}}\). In any image, each pixel of an image can be identified by its *x* and *y* coordinates. Given a number of prototypes *v*1, *v*2, …, *v**g* and a specific pixel *s* (*a, b*), the vector of membership grades [*u*1(*s*), *u*2(*s*),…, *u**c*(*s*)] of this pixel to the *c* prototypes that are closest to it do not need to be stored since their values could be calculated on the fly. The values of membership degree in this vector depend upon a number of parameters, such as *m* and *c*. The values of *m* (fuzzification coefficient in the FCM method) influence membership values. The most commonly used value of *m* is equal to 2 while higher values that 2 make the resulting membership functions become “spiky” and lower values of fuzzification coefficient produce Boolean-like (binary) membership regions [10].

*D. Reconstruction of image through fuzzy decoding*

Having a collection of pixels which are considered as prototypes, we can formulate a reconstruction problem: determine the value of gray level of each pixel in the block given a group of prototypes *v*1, *v*2, …, *v**g*. We identify two categories of pixels: (a) Pixels that have been identified as prototypes. Since the values of their gray levels have been stored in advance, the reconstruction doesn’t require any specialized handing. (b) Pixels that are not selected as prototypes, denoted as *s*, whose coordinate is represented as (*a*, *b*) and the gray level of the reconstructed pixel is denoted as F(*a*, *b*). The reconstruction problem is solved in the same way as in the FCM thus the reconstruction result (value of gray level) is determined as:

$$F(a,b)=\frac{{\sum\limits_{{i=1}}^{c} {{u_i}{{(s)}^m}f(x{'_i},y{'_i})} }}{{\sum\limits_{{i=1}}^{c} {{u_{^{i}}}{{(s)}^m}} }}$$

2

where (*x*’*i*, *y*’*i*), *i*=1, 2, …, *c*, represents the coordinate of the prototype used for reconstructing *s*(*a*, *b*). The quality of the compression-decompression depends on a number of parameters and they can be optimized. In general, we could regard compression-decompression problem as an optimization of selection of prototypes guided by a minimization of some certain performance index which quantifies a departure of the values of gray level of the reconstructed pixels from their original ones, namely \((F({x_s},{y_s}) - f({x_s},{y_s}))\) where *s* denotes the pixel in current block. The performance index of the mean squared error (MSE) considered here comes in the following form.

$${\text{MS}}{{\text{E}}_{{\text{block}}}}{\text{=}}\frac{1}{{m \times n}}{\sum\limits_{{s \in current{\text{ }}block}} {(F({x_s},{y_s}) - f({x_s},{y_s}))} ^2}$$

3

*E. Reconstruction of the overall image*

One the prototypes for each block have been determined, they form a backbone of the basis for the reconstruction of the overall image. The reconstruction the overall image is processed block by block. After the prototypes for each sub-block have been determined, for the pixels in each block that have not been identified as prototypes, the decompression (reconstruction) process consists of three steps: (a) determination of the *c* nearest prototypes *v*’1, *v*’2, …, *v*’*c* from the prototypes that represent current block according to the distances of this pixel to the prototypes, (b) calculation of membership degrees (matching levels) of this pixel to the selected *c* nearest prototypes and (c) aggregation of the gray levels of the selected prototypes weighted by the membership degrees.