Using NArray to crunch the Instagram Engineering Challenge

Recently Instagram put forward a challenge: Instagram Engineering Challenge: The Unshredder.

There are some solutions out there already:

That's just in the first page of Google hits.

Here at Centro, the team all challenged each other and shared our solutions. Here's mine: https://github.com/timgaleckas/instagram_challenge.

When I solved the problem, I was pretty proud of myself until one of the wiseguys here threw this image at my code: Shredded Mona Lisa.

Of course, my original code fell over. It took 21 seconds to to un-shred an image that large. It became a point of pride to see how fast I could get it running.

I tried:

  • Caching
    • This cut off 3 seconds for a speed up to 18 seconds.
  • Unrolling loops and skipping pixels
    • This cut the run time all the way down to 3 seconds.
    • It, however, cost me some resolution.
    • It failed if I started at the second pixel instead of the first.
  • Switching to NArray
    • This ran with comparable speed (5 seconds.)
    • This does not sacrifice any of the resolution.
  • Reducing the scope of the check
    • This reduced the time back to the blazing fast sub 3 second time.
    • This does not sacrifice any vertical resolution.

If you take a careful look at the code and do the math, you'll see that switching to NArray allowed me to go from only checking 100 pixels for each column to checking the full 1549 pixels while staying within one second of the time for the method that picks and chooses pixels to check.

Seems pretty powerful. That's why I'd like to give you a little explanation of how we're using NArray in this case and hopefully give you an incredibly powerful tool in your ruby tool box.

The loop we're trying to optimize is:

def percentage_pixels_that_are_edgelike(other_column)
  @percentage_by_other_column ||= {}
  return @percentage_by_other_column[other_column] if @percentage_by_other_column[other_column]
  # this line is doing all the work
  @percentage_by_other_column[other_column] = (0...pixels.size).select{|index|pixel_is_edgelike?(index, other_column)}.size.to_f / pixels.size
end

def pixel_is_edgelike?(index, other_column)
  (self[index+1] && (self[index]-other_column[index]).intensity > (self[index]-self[index+1]).intensity) ||
  (self[index-1] && (self[index]-other_column[index]).intensity > (self[index]-self[index-1]).intensity)
end

We know that creating that inner block that many times is inefficient and we know that using select{}.size is inefficient. That's why my first attempt at optimization was just to unroll the iteration into a simple loop.

What NArray allows us to do, on the other hand, is remove both iteration and math over arrays of data from ruby and push it down to a native extension.

So what used to be:

def add_arrays( array_1, array_2 )
  new_array = []
  array_1.each_index{ |index| new_array[index] = array_1[index] - array_2[index] }
  new_array
end

Turns into:

#we don't even need a method for this but,
def add_narrays( narray_1, narray_2 )
  narray_1 - narray_2
end

And the fact that NArray handles math between multidimensional arrays just as easily allows us to do stuff like this:

[
  [ 1, 3, 3 ],
  [ 2, 1, 3 ],
  [ 2, 2, 1 ]
] +
[
  [ 0, 1, 2 ],
  [ 3, 4, 5 ],
  [ 6, 7, 8 ]
]
->
[
  [ 1, 4, 5 ],
  [ 3, 5, 8 ],
  [ 8, 9, 4 ]
]

and even cooler:

[
  [ 1, 3, 3 ],
  [ 2, 1, 3 ],
  [ 2, 2, 1 ]
] * 2
->
[
  [ 2, 6, 6 ],
  [ 4, 2, 6 ],
  [ 4, 4, 2 ]
]

So instead of using RMagick's Pixel class and defining a custom :+ operator, we convert the array of pixels to a multidimensional array of color values:

NArray.to_na(pixels.map{|p|[p.red.to_f,p.green.to_f,p.blue.to_f]})

Which allows us to find the absolute difference between pixel columns by:

(pixel_array1 - pixel_array2).abs

And we multiply these pixel arrays by the function to convert to intensity:

def intensity_transform(narray)
  #http://www.imagemagick.org/RMagick/doc/struct.html#Pixel
  #The intensity is computed as 0.299*R+0.587*G+0.114*B.
  a = narray * [0.299,0.587,0.114]
  a[0,true] + a[1,true] + a[2,true]
end

This method multiplies each red value by 0.299, each green value by 0.587, each blue value by 0.114, and then adds the resultant arrays together to find pixel intensity.

Adding parallel arrays works naively for values that run horizontally across the arrays, but our formula needs to compare pixels to the top and the bottom of the current pixel.

Given the pixel map:

C1 C2
a0 b0
a1 b1
a2 b2
a3 b3
a4 b4

The formula to check that a2 is closer to the pixel above or below it than to the pixel next to it is: ( (a2 - b2) > (a2 - a1) ) || ( (a2 - b2) > (a2 - a3) )

To set up the data to allow us to use only operations across parallel arrays, we add shifted copies of the first array to our dataset like so:

C1 C2 C1[U] C1[D]
a1 b1 a2 a0
a2 b2 a3 a1
a3 b3 a4 a2

( Notice the removal of the top and bottom row from c1 )

So the formula for any given index i, becomes: ( ( C1[i] - C2[i] ) > ( C1[i] - C1_U[i] ) ) || ( ( C1[i] - C2[i] ) > ( C1[i] - C1_D[i] ) )

The actual NArray code looks like this:

def compute_percentage_pixels_that_are_edgelike( other_column )
  s = @pixels
  o = other_column.pixels
  # NArray[ range_for_dimensions, range_for_rows ]
  s1 = s[0..2,1..-2]
  column_difference = intensity_transform((s1 - o[0..2,1..-2]).abs)
  difference_up     = intensity_transform((s1 - s[0..2,0..-3]).abs)
  difference_down   = intensity_transform((s1 - s[0..2,2..-1]).abs)
  ((column_difference > difference_down).or( column_difference > difference_up )).where.total.to_f / s[0,true].total
end

Notice the 'where' method and the 'total' method.

'where' returns an array of the indices for which the predicate is true and 'total' is the same as the ruby array's size method ( but faster )

Hopefully this has been an enlightening introduction to NArray for some of you. It is a pretty cool library that can challenge the way you think about a problem and throw some pretty crazy speedup into the mix.

I'm not saying that NArray is perfect. Far from it. It has bugs (I ran into a couple just in this short exercise,) is difficult to use, lacking in documentation, and has an api that is far from desired. But what it lacks in frills and polish, it far makes up for in pure speed when it comes to crunching arrays and matrixes of numbers.

I hope it has made it into your ruby toolbox.