Google Summer of Code 2018 is just about over and I am absolutely thrilled to have worked for Haskell.org under my mentor Alp Mestanogullari. This summer, I worked towards implementing different classes of image processing algorithms using Haskell and incorporating
the same to the existing code base of Haskell Image Processing (HIP) package to enhance its scope. The algorithms that I implemented have vast applications in real image processing tasks and this project was aimed at encouraging more and more users to actually use Haskell as an alternative for some computer vision problems.
This post is dedicated towards providing a brief overview of the work I managed to accomplish in this project this summer. A preview of which can be looked up at my commit history here.
I started my journey by taking up the implementation of ‘Hough Transform’ as my first challenge. This transformation is generally used as a part of feature extraction in image analysis and computer vision tasks. It is a tool that makes it far easier to identify straight lines in the source image, whatever their orientation. The implementation of this includes computing the Linear Hough transform first and mapping each point in the target image, (ρ, θ) to the average color of the pixels on the corresponding line of the source image (x,y) space, where the line corresponds to points of the form (ρ = xcosθ + ysinθ ). Haskell implementation of the same can be found here. Sample input/output are as follows:
The idea is that where there is a straight line in the original image, it corresponds to a
bright (or dark, depending on the color of the background field) spot. By applying a suitable filter to the results of the transform, it is possible to extract the locations of lines in the original image. Further extending it’s scope, the classical Hough Transform can be tweaked to correctly detect the positions of arbitrary shapes, including circles and ellipses.
Next algorithm in my bucket list was Adaptive Histogram Equalization. Adaptive histogram equalization (AHE) is a technique used to improve contrast in images. It adjusts image intensity in small regions (neighborhood) in the image. It operates on small ‘contextual’ regions of the image. It enhances the contrast of each region and this technique works well when the distribution of pixel values is similar throughout the image. Haskell implementation of the above can be found here.
The idea is to perform contrast enhancement in ‘neighborhood region’ of each pixel and the size
of the region is a parameter of the method. It constitutes a characteristic length scale: contrast at smaller scales is enhanced, while contrast at larger scales is reduced. However, AHE tends to over amplify the noise in relatively homogeneous regions of the image. This could be taken care of by it’s variant ‘Contrast Limited Adaptive Histogram Equalization (CLAHE).
In the second coding phase of GSoC’18, I started taking up some important convolution filters which were yet to be implemented in the HIP Package. First, I took up the implementation of ‘Laplacian filter’. The Laplacian is a 2-D isotropic measure of the 2nd spatial derivative of an image. The Laplacian of an image highlights regions of rapid intensity change and is therefore often used for edge detection purposes.
Since derivative filters are very sensitive to noise, it is common to smooth the image (e.g., using a Gaussian filter) before applying the Laplacian. This two-step process is call the Laplacian of Gaussian (LoG) operation. The LoG operator takes the second derivative of the image. Where the image is basically uniform, the LoG will give zero. Wherever a change occurs, the LoG will give a positive response on the darker side and a negative response on the lighter side.
For coding purposes, any variants (in terms of kernel) of these may be used (eg., negative central peak). The convolution kernels used for implementation purposes were pre-computed and were of sizes 3 x 3 and 9 x 9 for Laplacian and Laplacian of Gaussian respectively.
Haskell implementation of these can be found here.
In many computer vision problems, we need to deal with noisy images. The most common application of this is in remote sensing or processing satellite data. Keeping this in mind, the next algorithm which I implemented was ‘Gaussian Smoothing’. It is a widely used effect in graphics software, typically to reduce image noise and reduce detail. It is also used as a pre-processing stage in computer vision algorithms in order to enhance image structures at different scales. Haskell implementation of the same is available here.
The Gaussian smoothing operator is a 2-D convolution operator. The idea of Gaussian smoothing is to use this 2-D distribution as a `point-spread’ function. Since the image is stored as a collection of discrete pixels we need to produce a discrete approximation to the Gaussian function before we can perform the convolution. It is commonly used before edge detection to reduce the level of noise in the image, which improves the result of the algorithm following it.
For the first half of this phase, I continued on with my quest to complete the un-implemented filters in the HIP package. This time, I started with some rather simple but important filters which were yet to be added to HIP. First, I began with the ‘Mean filter’. The Mean filter is a simple sliding-window spatial filter that replaces the center value in the window with the average (mean) of all the pixel values in the window . It is a simple, intuitive and easy to implement method of smoothing images, i.e. reducing the amount of intensity variation between one pixel and the next. It is often used to reduce noise in images.
Next, I went on to implement ‘Un-sharp Masking’ filter. The Un-sharp filter is a simple sharpening operator which derives its name from the fact that it enhances edges (and other high frequency components in an image) via a procedure which subtracts an un-sharp, or smoothed, version of an image from the original image. This technique is commonly used in the photographic and printing industries for crispening edges.
The un-sharp filter is implemented as a window-based operator, i.e. it relies on a convolution kernel to perform spatial filtering. The idea is to use a negative image to create a mask of the original image.
The un-sharped mask is then combined with the positive (original) image.
So, the resulting image is less blurry, i.e clearer.
The general idea of this technique is :
where f(x, y) is the input image and g(x, y) is the edge /output image.
Haskell implementation of this is available here.
While testing the Gaussian smoothing filter I observed that the HIP Package was lacking some of the necessary noise addition methods. After discussing this point with my mentor and the author of HIP, with their permission I took a little detour from my original planned list of algorithms to take care of this important point. So, with this I started my next algorithm ‘Salt & Pepper Noise’ which was to basically introduce the ‘salt and pepper’ type of noise in images.
Salt and pepper noise or impulse noise is a form of noise seen on images. It is mainly caused by sharp and sudden disturbances in the image signal. For implementation, it can be generated by introducing a sparse distribution of white and black pixels in the input image.
Haskell implementation for this can be found here.
The level or intensity of the noise to be introduced is a parameter of this method and is scaled between 0 and 1, that is the input Noise Intensity has a domain : (0, 1).
The above was the last algorithm successfully implemented by me this summer during the GSoC’18 program.
Summing it up (Tasks Completed and Merged)
- Hough Transform
- Adaptive Histogram Equalization
- Laplacian filter
- Laplacian of Gaussian (LOG) filter
- Gaussian Smoothing filter
- Mean filter
- Un-sharp Masking filter
- Salt and Pepper Noise Implementation
Tasks Currently Under Review
Along with the above completed tasks, following are the algorithms which I have attempted to complete and are currently under review but would be ready for testing soon:
- Deconvolution algorithm.
- Floyd Steinberg algorithm.
- Gaussian noise addition.
- Gabor filter for texture analysis.
- Otsu Clustering algorithm.
Haskell Image Processing (HIP) Package has many algorithms which are yet to be incorporated in it. Some of these include:
- Contrast Adaptive version of AHE or CLAHE.
- Generalized Hough Transform for detecting arbitrary shapes.
- Speckle Noise Reduction.
- Fingerprint Detection (Minutiae based).
- Optical Character Recognition (OCR) Algorithm
GSoC Experience with Haskell.org
Being a Google summer of code intern at Haskell.org has been a wonderful experience for me. The people in the Haskell community are really kind and helpful. ‘IRC’ is the best forum for discussion of any issues (silly or complex), and the people there would always try to help you out. I did face some difficulties in coping up with the deadlines in the starting (since I was a beginner to Haskell) but eventually, I ended up being comfortable coding in Haskell and this enabled me to ‘tick’ the task of learning a functional programming language in my bucket list.
People I Could Not Have Done It Without
I would like to express my gratitude to the GSoC Administrators for Haskell.org, especially George Wilson sir who guided me from the beginning for selection of a project suited to my skills.
Next, I would like to thank Alexey Kuleshevich sir (Author of HIP Package), who guided me throughout the project, ensuring that my PR’s were always of the best quality. Thank you for teaching me the necessary techniques for efficiently writing and documenting the code!
A special thanks to my mentor Alp Mestanogullari sir who has been a wonderful mentor as well as a friend to me. From helping me select a project to leading the way towards successfully completing one, you are really the one without whom I couldn’t imagine bringing this project towards completion! Thank you for taking time out your busy schedule to regularly interact with me and helping me out with all the queries I had. I will always be grateful to you for your support and kindness.
- Link to the commits authored by me : Here
- Haskell organization : Haskell.org
- Mentor : Alp Mestanogullari
- Link to previous blog : Here
Thank you for reading my blog!!
GSoC 2018 Student