Fingerprint Compression Based on Sparse Representation- Matlab project

Fingerprint based personal identification is used widely in forensics, attendance systems etc. Storage of these fingerprint image databases needs allocation of huge memory space.  Efficient data compression techniques will reduce the memory requirement. Fingerprint compression technique purely based on sparse representation is introduced here. Sparse matrix means a matrix in which most of the elements are zero. Sparse concept is mainly applicable to natural images. Natural images will possess similarity in one domain (like, the sky is blue).In fingerprint also there are similar areas. So, sparse representation can be used to effectively compress the fingerprint images. The algorithm includes construction of the dictionary, compression of a given new fingerprint, quantization and coding and analyzing complexity of the algorithm.

SPARSE MODELING:

Dictionary (D) is the first element of sparse modeling. It will be an NxK matrix, where K is the size of the dictionary. Each column of the dictionary is called as an atom. It’s a set of prototype of signals.  Instead of one signal we have multiple signals say X. Each signal represents each column of X. i.e. each column is an image patch. We have one dictionary that we are going to train for all images and then every one of these images or signals has its own sparse representation i.e. represented by matrix A. The number of non-zero entries of the vector A is very small. Since there are only few non-zero entries in vector A, this obtained vector will be sparse and thus called sparse modeling.

Given the dictionary, we construct sparse code for every signal. Next step is the dictionary updating. Pick all the signals that have used by an atom. Based on those signals, we will update the dictionary.

Matching pursuit is a sparse approximation algorithm which involves finding the best matching projections of the data onto an over-complete dictionary D. MP is a greedy algorithm that finds one best atom at a time.

1. Find the one atom that best matches with the signal, once if it’s selected keep that atom, i.e. why it is called greedy approach. Check the error. If the error is below what we wanted, then stop the process.

2. If error is not below the threshold value, then pick another atom that makes the error the smallest possible value. Add that atom to our collection. Given the previously found atoms, find the next one to best fit the residual.

3. The algorithm stops when the error satisfies the threshold.

Quantization, in image processing, is a compression technique achieved by compressing a range of values to a single quantum value. Lloyd’s algorithm is used for quantization of the sparse matrix.

Lloyd’s algorithm:

1. Get probability density function (pdf) of the image.

2. Next pdf is divided into M intervals

3. Apply the necessary centroid/threshold condition

4. Apply minimize MSE condition

5. Iteration process: Step 3 and step 4 are repeated until no further decrease in the total MSE

6. Apply quantization on image.

After quantization, encoding of the quantization coefficients is performed. Coding is carried out by arithmetic encoders. Arithmetic coding is a data compression technique that encodes data by creating a code string which represents a value on the number line between 0 and 1.

A sample of original image and its compressed fingerprint image is shown above. Sparse representation of fingerprint images provides a better compression ratio compared to other existing compression techniques.