VQ is the original coding scheme which solves the constrained optimization problem as follows:

The constraint || y_{;}^_{0} = 1 denotes that there is only one non-zero element in y_{; }and || y_{;} = 1, y_{;} > 0 indicates that the weight for each descriptor is equal to

1. In practice, (4.1) means that each descriptor x_{;} is assigned to its closest visual word of the predefined codebook with activation equal to 1. It is also known as Hard assignment or Hard quantization.

Soft Assignment Coding

To relieve the quantization error of VQ, SA coding method [14, 15] assigns a local feature to all of the visual words. The code of corresponding local feature represents the membership of the local feature to each visual word.

The j th coding coefficient represents the degree of membership of a local feature x_{;} to the j th visual word:

where в is the smoothing factor controlling the softness of assignment.

The SA coding method is computationally efficient and conceptually simple, which only needs to compute the distance from a local feature to each word. It employs the kernel function of distance as the encoding representation and uses multiple visual words for coding, which can improve the accuracy of probability density estimation. However, it cannot give excellent classification performance as the sparse or local coding methods, probably because it does not take the manifold structure of local features into account. Therefore, LSC [16] is proposed, which only considers the k nearest neighbors while coding a local feature.

LSC computes the jth coding coefficient of a local feature x_{;} as follows:

where d(x_{;}, bj) is the local version of d(x_{;}, bj) and N_{k}(x_{;}) defines the k nearest neighbors of x; in codebook.

The SA coding method improves the accuracy of probability density estimation compared with VQ method, because it employs the kernel function about distance to represent the codes instead of the vector with binary elements used in VQ. Furthermore, it uses multiple visual words while VQ method only considers the closest one visual word.

Locality-Constrained Linear Coding

Next, LLC [2] is a novel and practical coding scheme which transforms each input feature into a linear combination of the basis in a given codebook utilizing the locality constraint.

LLC uses the following criteria [2]:

where О is element-wise multiplication, e_{;} e R^{M} is the locality adaptor that measures the similarity between the input descriptor x; and codebook entities, and it is defined as follow:

where a is used to adjust weight decay speed for locality adaptor.

LLC generates a more accurate image representation and offers an analytical solution. After LLC process, nonlinear feature representations are obtained which can work better with linear classifiers.