The last week I spent some time build a small tool for abstracting  an image into a mosaic, for fun. To do this I’ve used Haskell, of course. However, this is my first “complete” program I’ve written in Haskell. Before that, I’ve read a lot about Haskell and used it for solving tons of ProjectEulers’s problems. However writing  program that performs real stuff, such as loading an image, do stuff and write a new image is a completely different things. Using Haskell for the Project Euler problem is almost like cheating, using Haskell for a _side-effect-full _application can be a pain in the neck if you are not prepared.

So the idea was to do this trying to be as much idiomatic as possible so that this code could be used by new haskellers in order to learn something on the language. It is still not really idiomatic, but I’m working on that.

What is Quadarto?

No more talk! It is time to see something real. First, what is Quadarto? Quadarto is a mosaic filter based on Quadtrees. The basic algorithm is very simple:

1. We took an image and we divide it in 4 square region.
2. We measure the average color for each region.
3. If this color is “good enough” we stop. Otherwise we apply recursively the algorithm on the sub-region that is: we divide the region in 4 and we start to find the average color for each sub-sub-region.
4. We repeat this until there are no more divisions or the minimum size for a region is reached.

The question is: what do you men for “good enough”? There are several way to specify what “good enough” means but, for now, we decide that a color is good enough  for a region if every pixel in the region is “near” the average color, that is, the difference between RGB components of the pixels and the average color are in between a certain threshold. We could define better heuristic for this (something more perception-based but for now it is not important)

A bit of Haskell

Let’s see a bit of code. The algorithm is fully summarized by this function:

1
2
3
4
5
6

-- | Return a list of rect obtained by the quaddecomposition of the image over the given rect.
quadDecomposition :: Image PixelRGB8 -> Int -> Rect -> [Rect]
quadDecomposition img threshold rect
    | rectWidth rect <= 8 = [rect]
    | isIndivisible img threshold rect = [rect]
    | otherwise =  foldr ((++) . quadDecomposition img threshold) [] (quadSplit rect)

The function takes an image, and int representing the color threshold and a starting Rect. A Rect is just the representation for a rectangle: a pair of ints for the top-left corner coordinates and another pair of ints for the bottom-right one. After the computation the function will return a list of Rects representing a full partitioning of the image! We will use this list of Rects to render the final image! Easy.

What the function does? Haskell allow us to read this function as mathematical function, that is great!  Line 4: if the rectangle size is less or equal to 8 we stop recursing. Line 5: if is indivisible, we stop recursing. Line 6: otherwise, we divide the rect in 4 sub-regions and we apply quadDecomposition on each of them. This last line is the hardest to understand if you are unfamiliar with Haskell, you need to know what foldr does and how composition works. Then, this function can be easily read as a function that apply quadDecomposition to every rect in (quadSplit rect)  and concatenates the results. Exactly what we wanted!

Again, what we intend for an indivisible rect? We can read this in the following function

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

isIndivisible :: Image PixelRGB8 -> Int -> Rect -> Bool
isIndivisible img threshold rect =
    let
        isPixelInThreshold (PixelRGB8 r g b)
            | wordIsNear ar r threshold && wordIsNear ag g threshold || wordIsNear ab b threshold = True
            | otherwise = False
            where
                (PixelRGB8 ar ag ab) = avgColor img rect
    in
        all isPixelInThreshold (pixelsInSquare img rect)

This function is super easy! It just returns True if all the pixels in the Rect are in threshold ( all isPixelInThreshold (pixelsInSquare img rect) ).

You can explore the rest of the code here! And if you have any problem, just ask me!

Why is called Quadarto?

Quadarto is just the word “quadrato” (the italian word for square) with the “a” and “r” exchanged of place in order to expose the word “art”. A bit pretentious, indeed.

Now?

Well, the idea is that if you are interested in some small (fun?) program in Haskell you can use the source code of Quadarto to learn something. My goal is to make the code more idiomatic, add tons of comments and ask any questions you want. Then, if you want to use the application to produce actual images, well, good for you and good for me. Glad to be helpful! :D

You can find the full project on GitHub.