Voronoi Image Manipulator
Voronoi Image Manipulator
Authors:
Gokce Dilek, Shirley Yang
What is the problem?
We wanted to explore computer image processing and image manipulation in functional languages. We’re interested in whether it’s plausible to complete things on a much larger scale in the potential context of image processing. We took inspiration from a CPSC 221 project and are planning to generate voronoi patterns and flood fill our image with that pattern. Given an input image, and the number of voronoi partitions to create, we will implement a flood fill algorithm starting from a randomly generated set of center coordinates in the image to create the specified number of partitions in the image, resulting in interesting artistic results where every pixel in a given voronoi partition have the same color.
What is the something extra?
We are looking to implement specific, customized data structures for the context of our problem, including structures to represent center coordinates of the flood fill, regular coordinates that are not centers, and a container for the flood fill algorithm (which will be a queue). We’re also looking to implement certain algorithms and patterns (round-robin, BFS) for our project. For this specific image / pixel manipulation task, we will make use of the JuicyPixels package: JuicyPixels
What did we learn from doing this?
Firstly, we learned how to set up a Haskell project with dependencies, using Haskell’s package manager Stack, which runs an isolated instance of GHC for the project that doesn’t interfere with other GHC installations. We primarily learned how to convert an imperative algorithm we have implemented into a functional one, where we tried to define each function to be as small and as simple as possible. We also found that Haskell has a very rich library collection at Hackage, and the libraries were in general straight-forward to get started with, whether it is to find a data structure suitable for a task, or to do image/pixel manipulation.
One of the interesting obstacles we encountered was the runtime of our program. We expected the runtime of our algorithm to increase linearly with the number of pixels (a data type we created ourselves) in the input image, but we realised this wasn’t the case. Eventually, we figured that this was because we were storing the processed pixels in a simple list, which meant that our lookup per pixel was not O(1):
isProcessed _ [] = False
isProcessed (x,y) ((Point xp yp (cx, cy)):t) | (x == xp && y == yp) = True | otherwise = isProcessed (x,y) t
After finding this bottleneck, we switched over to exploring efficient data structures of Haskell – maps:
isProcessed (x,y) p | (Map.member (x,y) p) = True | otherwise = False
This improved the runtime considerably.
Overall, despite the functions, Monads, and types being difficult to handle at first, the code was generally clean and simple. Dealing with images and pixels was surprisingly easy, but smaller functionalities like figuring the validity of a neighbour required 3 different functions to verify the validity of a neighbour and add it to the queue. The aspect of functional programming of recursive structures and the non-existence of conventional loops made it necessary to split up the validation, verification, and addition to our data structures. However, when those were created, the program was very intuitive and straight-forward, which ultimately gave us a greater appreciation of the beauty of Haskell and functional programming in general!