title: How to improve the efficiency of a sobel edge detector
body: <p>I am writing a <a href="https://github.com/RoadKillCat/PiCamVision" rel="nofollow noreferrer">computer vision library</a> from scratch in Python to work with a <code>rpi</code> camera. At the moment, I have implemented conversion to <code>greyscale</code> and some other basic <code>img</code> operations which both run relatively fast on my <code>model B</code> <code>rpi3</code>.</p>
  
  <p>However, my edge detection function using the <code>sobel</code> operator (<a href="https://en.wikipedia.org/wiki/Sobel_operator" rel="nofollow noreferrer">wikipedia description</a>) is much slower than the other functions although it does work. Here it is:</p>
  
  <pre><code>def sobel(img):
      xKernel = np.array([[-1,0,1],[-2,0,2],[-1,0,1]])
      yKernel = np.array([[-1,-2,-1],[0,0,0],[1,2,1]])
      sobelled = np.zeros((img.shape[0]-2, img.shape[1]-2, 3), dtype="uint8")
      for y in range(1, img.shape[0]-1):
          for x in range(1, img.shape[1]-1):
              gx = np.sum(np.multiply(img[y-1:y+2, x-1:x+2], xKernel))
              gy = np.sum(np.multiply(img[y-1:y+2, x-1:x+2], yKernel))
              g = abs(gx) + abs(gy) #math.sqrt(gx ** 2 + gy ** 2) (Slower)
              g = g if g &gt; 0 and g &lt; 255 else (0 if g &lt; 0 else 255)
              sobelled[y-1][x-2] = g
      return sobelled
  </code></pre>
  
  <p>and running it with this <code>greyscale</code> image of a cat:</p>
  
  <p><a href="https://i.stack.imgur.com/lHv5s.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/lHv5s.jpg" alt="greyscale cat"></a></p>
  
  <p>I get this response, which seems correct:</p>
  
  <p><a href="https://i.stack.imgur.com/SGpNz.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/SGpNz.jpg" alt="cat edges"></a></p>
  
  <p>The application of the library, and this function in particular, is on a chess playing robot in which the edge detection will help to recognise the location of the pieces. The problem is that it takes <code>&gt;15</code> seconds to run which is a significant problem as it will add to the time the robot takes to make its move by a lot.</p>
  
  <p>My question is: <strong>how can I speed it up?</strong></p>
  
  <p>So far, I have tried a couple of things:</p>
  
  <ol>
  <li><p>Instead of <code>squaring</code> then <code>adding</code>, then <code>square rooting</code> the <code>gx</code> and <code>gy</code> values to get the total gradient, I just <code>sum</code> the <code>absolute</code> values. This improved the speed a decent amount.</p></li>
  <li><p>Using a lower <code>resolution</code> image from the <code>rpi</code> camera. This obviously is a simple way to make these operations run faster, however its not really that viable as its still pretty slow at the minimum usable resolution of <code>480x360</code> which is massively reduced from the camera's max of <code>3280x2464</code>.</p></li>
  <li><p>Writing nested for-loops to do the <code>matrix convolutions</code> in place of the <code>np.sum(np.multiply(...))</code>. This ended up being slightly <em>slower</em> which I was surprised by as since <code>np.multiply</code> returns a new array, I thought that it should have been faster to do it with <code>loops</code>. I think though that this may be due to the fact that <code>numpy</code> is mostly written in <code>C</code> or that the new array isn't actually stored so doesn't take a long time but I'm not too sure.</p></li>
  </ol>
  
  <p>Any help would be much appreciated - I think the main thing for improvement is point <code>3</code>, i.e the <code>matrix</code> multiplication and summing.</p>