Dictionary Based Filtering

Abstract

    Digital image processing refers to the process of digital images by means of digital computer. The main application area in digital image processing is to enhance the pictorial data for human interpretation. In image some of the unwanted information is present that will be removed by several preprocessing techniques. Filtering helps to enhance the image by removing noise.Initially By creating Dictionary we will store two form of matrix. Now when We add new image in dictionary we don’t need to pass image from filter instead we will just Dictionary Learn form the Previous Dictionary and just map into.

Methodology

INTRODUCTION

    Basically the idea of Dictionary based filtering is instead of doing classical convolution every time,we directly take de–noise image from the dictionary using searching algorithm and time after time Learning of dictionary is also done by the same algorithm. We are planning to do low pass or high pass filtering to de–noise the noisy image. Low pass filter is used to remove salt and paper noise while high pass filter is used to separate of edges.We use OpenCV libraries and Python libraries to implement the low pass filter and to create blocks of image.

    Initially we take some training and filter them by using classical convolution.Both filtered and non-filtered images are divided into blocks which are stored in a dictionary.In the dictionary the key is noisy part of the image and the value is filtered part of the image.

LITERATURE REVIEW

• Sparse Dictionary Learning
  

    Sparse dictionary learning is a representation learning method which aims at finding a sparse representation of the input data (also known as sparse coding) in the form of a linear combination of basic elements as well as those basic elements themselves. These elements are called atoms and they compose a dictionary. Atoms in the dictionary are not required to be orthogonal, and they may be an over-complete spanning set. This problem setup also allows the dimensionality of the signals being represented to be higher than the one of the signals being observed.
    

    One of the key principles of dictionary learning is that the dictionary has to be inferred from the input data. The emer- gence of sparse dictionary learning methods was stimulated
by the fact that in signal processing one typically wants to represent the input data using as few components as possible.

    Different Algorithm for Sparse Dictionary Learning are as follow.

1. K-SVD
   

    Applications that use sparse representation are many and include compression, regularization in inverse problems, feature extraction, and more.Sparsity in over-complete dictionaries is the basis for a wide variety of highly effective signal and image processing techniques. Model: Given a dictionary D and a signal y,

Training Approach And Algorithm

    Train the dictionary directly based on the given examples, optimizing w.r.t. sparsity and other desired properties.

Output

OUR OWN APPROACH FOR DICTIONARY BASED
FILTERING

1. Input
   

    Salt-and-pepper noise is a form of noise sometimes seen on images. It presents itself as sparsely occurring white and black pixels. An effective noise reduction method for this type of noise is a median filter. We take a set of images with salt and pepper noise present at random positions.

    2. Algorithm

    An effective noise reduction method for this type of noise is a median filter. Like the mean filter, the median filter considers each pixel in the image in turn and looks at its nearby neighbors to decide whether or not it is representative of its surroundings. Instead of simply replacing the pixel value with the mean of neighboring pixel values, it replaces it with the median of those values. The median is calculated by first sorting all the pixel values from the surrounding neighborhood into numerical order and then replacing the pixel being considered with the middle pixel value.

Median Filter Conversion

    From the above illustration it is clear that the pixal value 128 is replaced by the median value 24 and the pixel value 172 is replaced by the median value 31. here the values 128 and 172 are entirely different from their neighboring pixels. when we take the median value,the pixel values which are totally different from their neighboring pixels are replaced by a value equal to the neighboring pixel value. We are using a Cross-correlation. It is a simple metrics which you can use for comparison of image areas. It is much more faster and robust than simple euclidean distances. We will need threshold to compare two image. It is very efficient while searching in a dictionary. First step of our algorithm is to take a set noisy images. Now, we divide the image in m x m chunks and store them. These chunks are now compare with our dictionary. If no image is present with normalize distance less than delta then we add present image in out dictionary. If image is present then replace with corresponding filtered image. We will repeat the above steps till we get chunks of filtered images. At the end
we will merge all the chunks.

First of all we have to take n x k training image.
Create m x m blocks.
Create dictionary using blocks.
Dictionary:
    Key - Noisy image
    value - filtered image
Search algorithm
if Nearest Possible Match then
    Noisy Patch Replaced with this Image
else
    Add to Dictionary
end
return Final Filtered Image

    3. Results:

Median Filter

Dictionary Based Filter for m=50,75,100

    We can infer form the output that median filters are much more accurate than low pass filter for image with salt and pepper noise.

Time Analysis

    Above analysis states that less the value of m more is the time taken to filter images. This is mainly due to size of dictionary. Less is the value of m, more is value of threshold and more is value of dictionary. It would take more time to search in a big dictionary. Here, time is exponentially varying with no. of images.

Here, more is the value of m, less is the percentage error.   

Conclusion

    While using dictionary based filtering for median filter we can conclude that more is the value of m, better is the performance. Direct approach is much more efficient than
dictionary based approach for median filter for lower no. of images. Dictionary based approach can be used with filters with higher polynomial terms.

Reference

[1] ”K-SVD”, En.wikipedia.org, 2017. [Online]. Available: https://en.
wikipedia.org/wiki/K-SVD. [Accessed: 03- Mar- 2017].
[2] ”Sparse dictionary learning”, En.wikipedia.org, 2017. [Online]. Avail-
able:https://en.wikipedia.org/wiki/Sparse dictionary learning [Accessed:
25- Feb- 2017].
[3] A. Rosebrock, ”Convolutions with OpenCV and Python -
PyImageSearch”, PyImageSearch, 2017. [Online]. Available:http://www.
pyimagesearch.com/2016/07/25/convolutions-with-opencv-and-python/.
[Accessed: 01- Mar- 2017].
[4] ”on-line dictionary Learning”,https://en.wikipedia.org/wiki/Sparse
dictionary learning#Online dictionary learning.[Accessed: 06- Mar-
2017]
[5] ”How to Split Image Into Multiple Pieces in Python”, Stackoverflow.com,
2017. [Online]. Available: http://stackoverflow.com/questions/5953373/
how-to-split-image-into-multiple-pieces-in-python. [Accessed: 01- Mar-
2017].
[6] ”Image denoising using dictionary learning scikit-learn 0.18.1
documentation”, Scikit-learn.org, 2017. [Online]. Available:
http://scikit-learn.org/stable/auto examples/decomposition/plot image
denoising.html. [Accessed: 01- Mar- 2017].
[7] ”Result of On-line Dictionary Learning for m=2,4,8,12,16”,https:
02-//github.com/kitsune-udon/online dictionary learning.[Accessed:
April- 2017]
[8] Lijun Xu, ”A Study of the K-SVD Algorithm for Designing Overcomplete
Dictionaries for Sparse Representation” [Source:unknown]. [Accessed:
06- May- 2017]
[9] Digital Image Processing, JAYARAMAN
[10] ”Median filter”, En.wikipedia.org, 2017. [Online]. Available: https://en.
wikipedia.org/wiki/Median filter. [Accessed: 03- Mar- 2017].
[11] Michal Aharon, Michael Elad, and Alfred Bruckstein,”K-SVD: An Al-
gorithm for Designing Overcomplete Dictionaries for Sparse Representa-
tion”,Publication: IEEE TRANSACTIONS ON SIGNAL PROCESSING,
VOL. 54, NO. 11, NOVEMBER 2006.[Accessed on: 21- Mar- 2017]
[12] ”Result of K-SVD”,https://github.com/alsoltani/K-SVD

Credit:

Charvik Patel

Himanshu Budhia

Neel Puniwala

Maharsh Patel