Find the center of a red dot of an image in Haskell

I try to find the center of all the red pixels contained in an image using Haskell and repa.

My problem is, that the code is not fast enough, probably because I read the image with repa-io which returns an Array Z DIM3 Word8, but I was not able to figure out how to filter the repa array by how red the given pixels are.

That's why I convert the array to a normal list, using R.toList. The rest of the calculations are then done using lists.

Here is my code:

import Data.Array.Repa.Repr.ForeignPtr (F, fromForeignPtr, toForeignPtr)
import Data.Array.Repa (Z(..), (:.)(..), DIM0, DIM1, DIM2, DIM3, Array(..),
    Source, Shape)
import qualified Data.Array.Repa as R
import Data.Array.Repa.IO.DevIL
import Data.List

import System.Environment (getArgs)

main :: IO ()
main = do
    [path]  Array r DIM3 a -> (Int, Int)
findRedDot img = (median . fst $ splitted, median . snd $ splitted)
    where -- function returning the coordinates as a tuple, when the pixel
          -- is red enough, otherwise return (-1, -1)
          convert f (Z :. i :. j) = let r = f (Z :. i :. j :. 0)
                                        g = f (Z :. i :. j :. 1)
                                        b = f (Z :. i :. j :. 2) in
                                    if r > 237 && (g + b)  Z :. w :. h)
                   convert
          -- turns the DIM2 repa array into a default haskell list
          lst = R.toList packed
          p (-1, -1) = False
          p _        = True
          -- split up the list into x and y component
          splitted = splitUp $ filter p lst

-- | split up a list of tuples into two lists
splitUp :: [(Int, Int)] -> ([Int], [Int])
splitUp [] = ([], [])
splitUp ((x, y):rest) = (x:(fst next), y:(snd next))
    where next = splitUp rest

-- | find the median of a numeric list
median :: (Num a, Ord a) => [a] -> a
median [] = -1
median l = sorted !! mid
    where len = length l
          mid = len `quot` 2
          sorted = sort l

I did compile with `g

Small things I noticed:

• splitUp is already defined in the prelude as unzip.

-
median working on a list makes it slow and your implementation is not semantically correct.

Generally the median is defined as the "center" element for datasets of odd magnitude, or the arithmetic mean of the two center elements for datasets of even magnitude.

If you made it use an array, you'd also get the vast benefit of not needing the len traverse the full list, nor to traverse it when accessing a specific index, which should cut execution time for that function roughly in half.

According to the profiling, that will also vastly reduce overall execution time.

-
The argument to convert f in findRedDot is repeated unnecessarily a lot, it should be possible to do the following:

convert f a@(Z:. i :. j) = let r = f (a :. 0)
                               g = f (a :. 1)
                               b = f (a :. 2)  in
                           if r > 237 && (g+b) < 50
                           then (i,j) 
                           else (-1, -1)

This makes it a tad easier to understand what exactly you do here, IMO

-
You speak of not being able to figure out a way to filter the repa array. A bit of hoogling reveals selectP, which should help with that. They explicitly mention:


Produce an array by applying a predicate to a range of integers. If the predicate matches, then use the second function to generate the element.

• This is a low-level function helpful for writing filtering operations on arrays.

• Use the integer as the index into the array you're filtering.

StackExchange Code Review Q#162861, answer score: 2