Databases
StackOverflow2013
Postsdbo
POOptimizing an average image colour program in haskell using REPA
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POOptimizing an average image colour program in haskell using REPA
    primarykey
    data
    text
    <h2>The problem</h2> <p>I've written a Haskell program that goes through a folder and finds the average colour of each image in the folder. It uses the repa-devil package from hackage to load images into repa arrays. I find the average by adding all the red, blue and green values and then dividing by the number of pixels:</p> <pre><code>-- compiled with -O2 import qualified Data.Array.Repa as R import Data.Array.Repa.IO.DevIL import Control.Monad.Trans (liftIO) import System.Directory (getDirectoryContents) size :: (R.Source r e) =&gt; R.Array r R.DIM3 e -&gt; (Int, Int) size img = (w, h) where (R.Z R.:. h R.:. w R.:. 3) = R.extent img averageColour :: (R.Source r e, Num e, Integral e) =&gt; R.Array r R.DIM3 e -&gt; (Int, Int, Int) averageColour img = (r `div` n, g `div` n, b `div` n) where (w, h) = size img n = w * h (r,g,b) = f 0 0 0 0 0 f row col r g b | row &gt;= w = f 0 (col + 1) r g b | col &gt;= h = (r, g, b) | otherwise = f (row + 1) col (addCol 0 r) (addCol 1 g) (addCol 2 b) where addCol x v = v + fromIntegral (img R.! (R.Z R.:. col R.:. row R.:. x)) main :: IO () main = do files &lt;- fmap (map ("images/olympics_backup/" ++) . filter (`notElem` ["..", "."])) $ getDirectoryContents "images/olympics_backup" runIL $ do images &lt;- mapM readImage files let average = zip (map (\(RGB img) -&gt; averageColour img) images) files liftIO . print $ average </code></pre> <p>I have also written this program in Python, using the Python Image Library. It finds the average of the images in the same way:</p> <pre><code>import Image def get_images(folder): images = [] for filename in os.listdir(folder): images.append(folder + filename) return images def get_average(filename): image = Image.open(filename) pixels = image.load() r = g = b = 0 for x in xrange(0, image.size[0]): for y in xrange(0, image.size[1]): colour = pixels[x, y] r += colour[0] g += colour[1] b += colour[2] area = image.size[0] * image.size[1] r /= area g /= area b /= area return [(r, g, b), filename, image] def get_colours(images): colours = [] for image in images: try: colours.append(get_average(image)) except: continue return colours imgs = get_images('images/olympics_backup/') print get_colours(imgs) </code></pre> <p>When both of these are run on a folder with 301 images the Haskell version is outperformed by 0.2 seconds (0.87 vs 0.64). This seems strange because Haskell is a compiled language (which are often faster than interpreted ones) and I had heard repa arrays had good performance (although this may have just been in comparison to other Haskell data types, like the list).</p> <h2>What I tried</h2> <p>The first thing I did was notice I was using explicit recursion and so I decided to replace it using a fold, which would also mean I no longer had to check if I was beyond the bounds of the array:</p> <pre><code>(r,g,b) = foldl' f (0,0,0) [(x, y) | x &lt;- [0..w-1], y &lt;- [0..h-1]] f (r,g,b) (row,col) = (addCol 0 r, addCol 1 g, addCol 2 b) where addCol x v = v + fromIntegral (img R.! (R.Z R.:. col R.:. row R.:. x)) </code></pre> <p>This made it run slower (1.2 seconds) so I decided to profile the code and see where most of the time was being spent (in case I had created an obvious bottleneck or the repa-devil package was just slow). The profile told me that ~58% of the time was spent in the f function and ~35% of the time was spent in the addCol.</p> <p>Unfortunately I cannot think of any way to make this run faster. The function is just an array index and an addition - the same as the python code. Is there a way to improve the performance of this code or does the Python Image Library just offer greater performance?</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USHaskellElephant
    1. USmatio2matio
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POOptimizing an average image colour program in haskell using REPA
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POOptimizing an average image colour program in haskell using REPA
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POOptimizing an average image colour program in haskell using REPA
      1. This table or related slice is empty.
      1. VTUpMod
    1. COUsing `foldl'` in `(r,g,b) = foldl' f (0,0,0) [(x, y) | x <- [0..w-1], y <- [0..h-1]]` buys you nothing. `foldl'` evaluates the intermediate result to weak head normal form, that is to the `(,,)` constructor here. The components remain thunks. I'm not going to install a package just to check, so I have to guess. Does making `f` strict in `r`, `g` and `b`, `f row col !r !g !b` (requires `BangPatterns` of course) help?
      singulars
      1. POOptimizing an average image colour program in haskell using REPA
      1. USDaniel Fischer
    2. COUsing a custom `fold` with repa strikes me as a bad idea that converting to lists might not solve. I'd bet using `backpermute` to get the color channels as three separate delayed arrays then calling `sumS` would result in better performance if anyone wants to check.
      singulars
      1. POOptimizing an average image colour program in haskell using REPA
      1. USThomas M. DuBuisson
    3. CO@DanielFischer making r, g and b strict did help. In fact it made the program a lot slower (17 seconds). Thanks for the suggestion and explanation of foldl' though.
      singulars
      1. POOptimizing an average image colour program in haskell using REPA
      1. USmatio2matio
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload