saush

Edge detection with the Sobel operator in Ruby

Posted in Ruby by sausheong on April 20, 2011

I was never much into image processing. Sure, like most programmers I dabbled into it for cropping images or doing some fancy-schmancy filtering effects stuff. I even wrote a Flickr clone for my last book which has a rather impressive photo editor (mashed up from Pixlr, not mine). But I never thought much on how those effects were done or who came up with them in the first place. That is until I met Irwin Sobel.

For those who know their image processing, this should ring bells immediately. Yes, it’s that Sobel. But a minute to give some background — Irwin is a colleague of mine working in the Mobile and Immersive Experience Lab in HP Labs. I was visiting about two weeks ago and was introduced to him and his current projects. Inevitably someone talked about the Sobel operator, a commonly used algorithm used for edge detection. I was, unfortunately, totally clueless about what it was. Not good. So not surprisingly I ended up Googling for ‘Sobel operator’ at the first possible chance and found out what it was.

The Sobel operator is an algorithm for edge detection in images. Edge detection for those who are not familiar with the term, is an image processing technique to discover the boundaries between regions in an image. It’s an important part of detecting features and objects in an image. Simply put, edge detection algorithms help us to determine and separate objects from background, in an image.

The Sobel operator does this in a rather clever way. An image gradient is a change in intensity (or color) of an image (I’m over simplifying but bear with me). An edge in an image occurs when the gradient is greatest  and the Sobel operator makes use of this fact to find the edges in an image. The Sobel operator calculates the approximate image gradient of each pixel by convolving the image with a pair of 3×3 filters. These filters estimate the gradients in the horizontal (x) and vertical (y) directions and the magnitude of the gradient is simply the sum of these 2 gradients.

The magnitude of the gradient, which is what we use, is calculated using:

That’s the simplified, 2-paragraph theory behind the algorithm. If this fascinates you, you should grab a couple of books on image processing and computer vision and go through them.

Let’s look at how to implement the Sobel operator. This is simply by creating the 2 filters and running them through each pixel in the image, starting from the left and going right. Note that because the filter is a 3×3 matrix, the pixels in the first and last rows as well as the first and last columns cannot be estimated so the output image will be a 1 pixel-depth smaller than the original image.

To calculate the pixel in the right side of the equation (the one with coordinates 1,1) the following equation is used:

output pixel [1,1] = ([0,0] x -1) + ([0,1] x 0) + ([0,2] x 1) + ([1,0] x -2) + ([1,1] x 0) + ([1,2] x 2) + ([2,0] x -1) + ([2,1] x 0) + ([2,2] x 1)

To simplify matters even more, the grayscale version of the original image is usually used.

Now let’s look at the Ruby implementation


require 'chunky_png'

class ChunkyPNG::Image
  def at(x,y)
    ChunkyPNG::Color.to_grayscale_bytes(self[x,y]).first
  end
end

img = ChunkyPNG::Image.from_file('engine.png')

sobel_x = [[-1,0,1],
           [-2,0,2],
           [-1,0,1]]

sobel_y = [[-1,-2,-1],
           [0,0,0],
           [1,2,1]]

edge = ChunkyPNG::Image.new(img.width, img.height, ChunkyPNG::Color::TRANSPARENT)

for x in 1..img.width-2
  for y in 1..img.height-2
    pixel_x = (sobel_x[0][0] * img.at(x-1,y-1)) + (sobel_x[0][1] * img.at(x,y-1)) + (sobel_x[0][2] * img.at(x+1,y-1)) +
              (sobel_x[1][0] * img.at(x-1,y))   + (sobel_x[1][1] * img.at(x,y))   + (sobel_x[1][2] * img.at(x+1,y)) +
              (sobel_x[2][0] * img.at(x-1,y+1)) + (sobel_x[2][1] * img.at(x,y+1)) + (sobel_x[2][2] * img.at(x+1,y+1))

    pixel_y = (sobel_y[0][0] * img.at(x-1,y-1)) + (sobel_y[0][1] * img.at(x,y-1)) + (sobel_y[0][2] * img.at(x+1,y-1)) +
              (sobel_y[1][0] * img.at(x-1,y))   + (sobel_y[1][1] * img.at(x,y))   + (sobel_y[1][2] * img.at(x+1,y)) +
              (sobel_y[2][0] * img.at(x-1,y+1)) + (sobel_y[2][1] * img.at(x,y+1)) + (sobel_y[2][2] * img.at(x+1,y+1))

    val = Math.sqrt((pixel_x * pixel_x) + (pixel_y * pixel_y)).ceil
    edge[x,y] = ChunkyPNG::Color.grayscale(val)
  end
end

edge.save('engine_edge.png')

First thing you’d notice is that I used a library called ChunkyPNG, which is PNG manipulation library that is implemented in pure Ruby. While wrappers over ImageMagick (like RMagick) is probably the defacto image processing and manipulation library in Ruby, I thought it’s kind of pointless to do a Sobel operator with ImageMagick since it already has its own edge detection implementation.

To simplify the implementation, I opened up the Image class in ChunkyPNG and added a new method that will return a grayscale pixel at a specific location. Then I created the 2 Sobel filters with arrays of arrays. I created 2 nested loops to iterate through each pixel column by column, then row by row and at each pixel I used the equation above to calculate the gradient by applying the x filter then the y filter. Finally I used the gradient and set a grayscale pixel based on the gradient value, on a new image.

Here you can see the original image, which I reused from the Wikipedia entry on Sobel operator.

And the edge detected image with the x filter applied only.

This is the edge detected image with the y filter only.

Finally this is the edge detected image with both x and y filters applied.

This short exercise might not be technically challenging but it made me appreciate the pioneers who invented things that we now take for granted. Here’s a final picture, one with myself and Irwin (he is the guy who’s sitting opposite me), and a bunch of other colleagues at HP Labs Palo Alto over lunch. Thanks Irwin, for the Sobel operator!

About these ads

19 Responses

Subscribe to comments with RSS.

  1. Kevin Elliott said, on April 22, 2011 at 10:15 am

    I love posts like these. More please :)

    • Henri said, on April 28, 2011 at 7:12 am

      @Kevin, you know that this is Sage Sobel’s dad? Maybe you knew that :)

  2. sausheong said, on April 23, 2011 at 7:53 am

    Thanks Kevin. Do suggest topics you are interested in reading :)

  3. health said, on September 8, 2011 at 9:49 pm

    It can be easily stored in purpose- built tanks in places where no other power is available or practical
    Health and safety

  4. Filters for fridges said, on November 6, 2011 at 5:04 pm

    I’m glad that I came across your site. I have read a number of your articles and they were all an excellent read and very informative. Thanks :)

    • Ibraheem said, on February 5, 2012 at 3:16 pm

      thanks! -What fatonicnul forms did you use for the galaxy model and point spread function models, and how did you determine these?We ended up using an exponential profile for the galaxy model and a moffat distribution for the PSF. We also experimented with add a de Vacouleurs component to the galaxy model. Our software was designed so that it would be easy to swap and combine models. To assess the quality of our models we studied the pixel-level residuals (stacked from thousands of images) between the predicted and observed image.-Which neural network implementation in TMVA did you use?The Multi-Layer Perceptron implementation with BFGS training.-What parameters for the network did you use?The parameters from the model fits were fed to the network as inputs. We trained the network to “learn” corrections to the fitted ellipticity values.-How did you select these parameters?Trial and error for the most part. We had trouble with convergence feeding ALL of the information we had available for each of the images at first. So we started from a smaller subset of the parameters and systematically added parameters and evaluated the results.

    • yuwuyrl said, on February 5, 2012 at 10:19 pm

      sdw9b3 ptobnhejjqnq

  5. maya said, on February 9, 2012 at 1:06 pm

    I need a code for performing sobel operation in java where the input image is read from a file and edge detected image is stored in a file….plz reply…

  6. Leonard said, on February 17, 2012 at 9:10 am

    I like this post, however in your ruby implementation of the sobel operator, I don’t believe you perform any thresholding on your image, you merely set each pixel to it’s calculated magnitude value instead of setting a threshold and only setting an edge to a white value if the gradient is above a certain value. Would this not be the proper way to implement the sobel for edge detection?

  7. Larry W said, on April 5, 2012 at 1:57 am

    Great post, helped me understand it well! But I am struggling to find the original paper on Sobels’ work to reference, do you know of it?
    thanks

  8. omer said, on May 8, 2012 at 6:05 pm

    thank you and what apply the algorithm in a parallel execution

  9. smaganazook said, on October 25, 2012 at 12:31 pm

    Thank you for your great explanation of this topic!

  10. handrienoprisson said, on November 14, 2012 at 11:25 pm

    thank you sir, i get more information about sobel operator from this article..

  11. Ricardo Caldeira said, on November 29, 2012 at 12:35 am

    How to modify the algorithm to generate image only with the y filter or x filter?

  12. Troy J. Gray said, on January 7, 2013 at 4:37 am

    I’m having a problem with edge detection using Sobel operator: it produces too many false edges, effect is shown on pictures below. I’m using a 3×3 sobel operator – first extracting vertical then horizontal, final output is magnitude of each filter output. Edges on synthetic images are extracted properly but natural images produce have too many false edges or “noise” even if image is preprocessed by applying blur or median filter. What might be cause of this? Is it implementation problem (then: why synthetic images are fine?) or I need to do some more preprocessing?

  13. Robert Gawron said, on March 8, 2013 at 3:23 am

    Hi,

    edges can be also found by using genetic algorithms, I made a simple implementation in Java, my results are a bit worse, but it also works.

    The idea can be checked on below link:

    http://robertgawron.blogspot.com/2013/03/image-edge-detection-by-using-genetic.html

    Regards.

  14. taher said, on July 24, 2013 at 1:57 pm

    can you guve me the detail explanation for the matrix used in sobel operator

  15. page said, on February 24, 2014 at 5:14 am

    The relation between two countries is not cordial but that air of antagonism
    has never stopped or forced any business from withdrawing any of their business initiatives.
    If you want to get into reselling of used printer cartridges, you will
    need to source for additional empty cartridges to make
    your efforts viable. Its weight is 122 grams and casing measures 111 x 51 x 13.

    Hi friends, how is all, and what you would like to
    say regarding this article, in my view its actually amazing
    for me.

  16. european muscle cars said, on April 12, 2014 at 8:48 pm

    Excellent way of telling, and good paragraph to take data on the topic
    of my presentation focus, which i am going to present in
    institution of higher education.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 444 other followers

%d bloggers like this: