4
\$\begingroup\$

I have image files consisting of black and white pixels encoded as RGB8. I want to count the number of blobs i.e. contiguous areas of white pixels. I rewrote this algorithm in haskell.
The algorithm works as follows: The image is traversed and whenever a white pixel is encountered the counter is incremented and all accessible pixels are set to black(so they don't get counted again).

import System.Environment
import Codec.Picture
import Codec.Picture.Types
import Data.Vector.Storable ( (!),  (//), Vector, toList )
import GHC.Word

main = do
  args <- getArgs
  Right im <- readPng (head args)
  let imgRGB8 = (\(ImageRGB8 t) -> t) im
  let imgGray = pixelMap computeLuma imgRGB8
  let w = imageWidth  imgGray
  let h = imageHeight imgGray
  let imVec = imageData imgGray
  let coords = [0..(w*h -1)]
  print (loop w h imVec coords 0)

type I = Data.Vector.Storable.Vector GHC.Word.Word8

loop :: Int -> Int -> I -> [Int] -> Int -> Int
loop _ _ _     []     blobCount = blobCount 
loop w h image (c:cs) blobCount = if (image ! c) == 255 then loop w h (deleteBlob w h image c) cs (blobCount+1)
                                   else loop w h image cs blobCount

deleteBlob :: Int -> Int -> I -> Int -> I
deleteBlob w h image c | image ! c == 255 = foldl (deleteBlob w h) (image // [(c, 0)]) coords
                       | otherwise        = image
                       where
                          coords = environment w h c

environment w h i = takeWhile (< w*h) $ dropWhile (<0) [i-w-1, i-w, i-w+1
{- in a vector image the row above is -}               ,i  -1,      i  +1
{- imageWidth apart. perks: easy clipping -}           ,i+w-1, i+w, i+w+1]

My main concern is that my haskell version is so much slower than my python version.
Second concern is am I loading the images right? Should I have used a more recent library? This is the only way I could make it work.
Thirdly, is this how a haskeller would write a blob count?

\$\endgroup\$
  • \$\begingroup\$ This is called connected component analysis. There exist much more efficient algorithms using a UnionFind data structure. I would review your code, but I don’t know Haskell, so can’t answer your main questions. :) \$\endgroup\$ – Cris Luengo Oct 31 '18 at 13:27
  • \$\begingroup\$ I was going to do an actual code review but I think that I’m not familiar enough with these libraries to do so. I think your issue is, from looking at the documentation, that (//) is not in-place. Look into Data.Vector.Storable.Mutable as well as modify in the immutable storable type. I’m not positive, but it seems like that’s where your problems lie. From what I could tell, the image library you were using is the most popular one, so you’re probably fine on that front. \$\endgroup\$ – cole Oct 31 '18 at 18:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.