{"id":55,"date":"2010-07-11T18:30:59","date_gmt":"2010-07-11T22:30:59","guid":{"rendered":"http:\/\/dominionsw.com\/wordpress\/?p=55"},"modified":"2019-11-25T07:31:18","modified_gmt":"2019-11-25T11:31:18","slug":"looking-at-the-edge-of-edge-detection-%e2%80%93-part-1","status":"publish","type":"post","link":"https:\/\/www.dominionsw.com\/?p=55","title":{"rendered":"Looking at the edge of Edge Detection \u2013 Part 1."},"content":{"rendered":"

If you\u2019ve done a bit of image processing, or read about it, you\u2019ve probably run into the concept of \u201cedge detection\u201d. In the first part of this article I\u2019ll take a closer look at the basics of edge detection, and explore in more detail what\u2019s going on in those little boxes of numbers.<\/p>\n

When people hear of the concept\u00a0 of edge detection in images, they sometimes think of\u00a0 finding objects in images, and obtaining the actual coordinates of the objects in the image. However, the various algorithms called edge \u201cdetection\u201d would \u00a0probably better be called edge \u201cenhancement\u201d. These algorithms amplify or mark where the segments in an image change, and the result is a new image showing the location of these changes, which are \u201cedges\u201d in the image. So, the \u201cdetection\u201d part does not include creating a map of coordinates of various regions \u2013 other algorithms are needed for this task. However, edge detection is a useful tool in preparing images for location detection, and for enhancing the lines, edges, and corners in images for other image processing tasks.<\/p>\n

If we start with a very simple example, it is easier to understand the basic idea for edge enhancement. Here we have an image with a single, simple edge, where the white section meets the black section in the middle:<\/p>\n

\"\"<\/a><\/p>\n

We will use the convention that the value of the color black on the left is 0, and the value of the white on the right is 1.\u00a0 Let\u2019s take this image down to 1 dimension, and look at it from the edge:<\/p>\n

\"\"<\/a><\/p>\n

Here we can see the black area as all zeros, and the white area as all ones. To detect where that change happens, we have to bring in the dreaded \u201cC\u201d word, Calculus.\u00a0 But, we really only need to know a bit about that topic to understand how to find the edge of the image.<\/p>\n

We are looking for a change \u2013 a difference \u2013 in the image. We want to note where those differences occur. The ideas of Calculus help us find this difference. We can move along the data from left to right, on step at a time, looking for these changes.<\/p>\n

To be clear, we have a discontinuous function, \u00a0as seen by the big jump between 0 and 1. Calculus doesn\u2019t like to deal with this type of data. However, we are in the computer world,\u00a0 where we always have to deal with these types of discontinuities between values.<\/p>\n

The concepts we will borrow from the Calculus are the idea of derivatives, which is the rate of change, and the concept of the limit of the size of the step as it approaches zero.\u00a0 The rate of change is how fast our data is changing \u2013 how much change vs how many steps. – The concept of the limit of the step size is simply taking the step size to its smallest theoretical value, which gives us the most accurate measurement. In our computer world, we have a simpler model \u2013 our step size in this case is just 1 pixel, \u00a0and as we step across this data we can estimate the rate of the change across\u00a0 small sections of our data. This concept is known as Finite Differences, and since our world inside the computer has finite steps and step sizes, we will use this concept.<\/p>\n

Imagine walking along inside a building, writing down the difference in your position vertically in the building as you walk.\u00a0 As you start to walk your position is 0 feet off the floor, and you look ahead and measure the difference between where you are and where you will be the next step forward. As you move along the floor for four steps, say, you note at each step that there is no difference in the height between where you are and where you will be, so you write down a 0 difference for that step. Then you reach a stair, and you look forward and measure the difference between the height of the\u00a0 first stair and the floor. Let\u2019s say it\u2019s 1 foot. The difference is 1 (where you will be) \u2013 0 (where you are now). So you write 1 down and then take a step. \u00a0The floor is level after this first step \u00a0and so as you continue along there is no change in your vertical position, so you write down zeros. \u00a0So, now your notebook has something like the following written in it:<\/p>\n

0 0 0 0 1 0 0 0 0<\/p>\n

Congratulations! You detected the edge in the floor in the building! I hope you didn’t trip over it.<\/p>\n

In more mathematical terms, you\u2019ve taken the \u201cForward Difference\u201d of the data along your path. This can be written as:<\/p>\n

Height(where you are + 1) \u2013 Height(where you are)\/Step Size<\/p>\n

Here, our step size is conveniently just \u201c1\u201d step, so we can just pay attention to the top part of the fraction.<\/p>\n

It turns out, however, that this method is not quite as accurate as it could be. If you are measuring a surface that has a rapidly changing shape, rather than our simple floor,\u00a0 your measurements of the change will be limited by the size of your step.\u00a0 Using our walking example, you could improve your estimate if as you go along you stop and look forward, \u00a0and then staying where you are look backwards, and then average these two measurements. This is known as a \u201cCentered Difference\u201d, and it is a bit intuitive that this kind of measurement might be a better estimate. It’s like the phrase “splitting the difference.”<\/p>\n

Height(where you are + 1) \u2013 Height(where you are – 1)\/2 x Step Size<\/p>\n

There is also a \u201cBackward Difference\u201d, which as you can imagine takes the measurement where you are and the measurement in back of you and takes the difference between them. These Finite Differences provide an estimate of the first derivative of our data, i.e.\u00a0 the rate of change of the data.<\/p>\n

If you wish to see a more detailed discussion of Finite Differences, you can find more information at http:\/\/en.wikipedia.org\/wiki\/Finite_difference or see the book \u201cComputational Engineering\u201d by Gilbert Strang.<\/p>\n

So, we now have a method – the Centered Difference \u00a0– to estimate the change in our data as we move along through it.<\/p>\n

So, let\u2019s apply this to our data. If we take an section of our \u201cedge\u201d data, we have an array of data like this:<\/p>\n

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1<\/p>\n

So…..how are we efficiently going to apply the Centered Difference to this data?<\/p>\n

In image processing, there is the concept of a \u201ckernel\u201d, which is a small and usually square block, or matrix, of numbers used to step along an image and provide a new pixel based on the values in the kernel and the values in the pixels that are covered by the kernel as it moves along. So, for instance, a kernel might conceptually look like this:<\/p>\n\n\n\n\n\n
-1<\/td>\n0<\/td>\n1<\/td>\n<\/tr>\n
-1<\/td>\n0<\/td>\n1<\/td>\n<\/tr>\n
-1<\/td>\n0<\/td>\n1<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Here we have a 3 by 3 matrix of numbers. But, for the moment, we are in one dimension \u2013 so, let us take one row from this matrix:<\/p>\n\n\n\n
-1<\/strong><\/td>\n0<\/strong><\/td>\n1<\/strong><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

This row of numbers can be used to quickly move through our data and give us a Centered Difference. Here is our centered difference formula again:<\/p>\n

Height(where you are + 1) \u2013 Height(where you are – 1)\/2 x Step Size<\/p>\n

We\u2019re not going to use this exactly as above \u2013 it turns out that dividing by two gives us a more accurate measurement of the rate of change, but in our simple case we\u2019re outputing a black and white image, and for now we can skip the divide by 2.<\/p>\n

In order to match our Centered Difference vector above (with a 0 in the center), we can add another measurement \u00a0– Height(where you are) – to the terms just for clarity. So now we have:<\/p>\n

Height(where you are + 1) + (0 x Height(where you are))\u2013 Height(where you are – 1)<\/p>\n

Let\u2019s change the above terms so we are only using addition, and then reorder them to match (see the red numbers) our one row kernel above:<\/p>\n

(-1<\/span><\/strong> x Height(where you are -1)) + (0<\/span><\/strong> x Height(where you are))+ (1 <\/span><\/strong>x Height(where you are +1)<\/p>\n

In the above we take -1 of the height where you are -1 step, plus none of the height where you are, + 1 of the height where you are plus 1 step. Now we can see how to apply the kernel \u2013 we step the kernel along our data, multiply the data under the kernel by the number in the kernel, sum that data up, and set the new data at the center of the kernel to that answer:
\n-1 0 1 \u00a0MOVE ->
\n0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1<\/p>\n

Let\u2019s see what happens when we run through a simple Matlab function (code below) to multiply the array and the kernel:<\/p>\n

0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0<\/p>\n

We can see that the edge is located (approximately) by showing the the change across the span of the edge. This is not a perfect fit – however, it’s a pretty close fit for a small amount of computing work.<\/p>\n

Now that we\u2019ve covered the basic theories, let\u2019s move right into a 2 dimensional image and filter.<\/p>\n

\"\"<\/a><\/p>\n

Here we have an gray scale image with a lot of edges. Let\u2019s move our filter into 2 d, but we\u2019ll limit it to enhanceing only the vertical edges by using this pattern:<\/p>\n\n\n\n\n\n
0<\/td>\n0<\/td>\n0<\/td>\n<\/tr>\n
-1<\/td>\n0<\/td>\n1<\/td>\n<\/tr>\n
0<\/td>\n0<\/td>\n0<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

We will modify and use the ApplyFilter Matlab function (code provided at the end) on this image with this filter:<\/p>\n

\"\"<\/a><\/p>\n

Above we have the image with the vertical lines enhanced. Now we\u2019ll try to pick up some diagonals that point from bottom right to top left. To do that we\u2019ll add another set of coefficients, along the diagonal perpendicular to the lines we want to enhance:<\/p>\n\n\n\n\n\n
0<\/td>\n0<\/td>\n1<\/span><\/td>\n<\/tr>\n
-1<\/td>\n0<\/td>\n1<\/td>\n<\/tr>\n
-1<\/span><\/td>\n0<\/td>\n0<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

\"\"<\/a><\/p>\n

Here we can see the additional diagonal lines picked up. Let\u2019s pull out the other diagonals:<\/p>\n\n\n\n\n\n
-1<\/span><\/td>\n0<\/td>\n0<\/td>\n<\/tr>\n
-1<\/td>\n0<\/td>\n1<\/td>\n<\/tr>\n
0<\/td>\n0<\/td>\n1<\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

 <\/p>\n

\"\"<\/a><\/p>\n

OK, lastly we\u2019ll pick up all the edges with the full set of coefficients.<\/p>\n\n\n\n\n\n
-1<\/td>\n0<\/td>\n1<\/td>\n<\/tr>\n
-1<\/td>\n0<\/td>\n1<\/td>\n<\/tr>\n
-1<\/td>\n0<\/td>\n1<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

\"\"<\/a><\/p>\n

We can see the lines, but, they seem a bit bright. We can put our divide by 2 back in now that we have a \u201creal\u201d image and bring the relative brightness of the lines back into proportion:<\/p>\n

\"\"<\/a><\/p>\n

This is a more accurate, but perhaps less useful image. We could just as well skip the divide by two if we want the lines to stand out more.<\/p>\n

So, that\u2019s all for Part 1!<\/p>\n

In Part 2 I\u2019ll discuss \u00a02nd<\/sup> derivative kernels, and also how to get the angles of the enhanced lines.<\/p>\n

Rick Frank<\/p>\n

Dominion Software, Inc.<\/p>\n

Matlab code:<\/p>\n

function [ RESULT ] = FirstDifference( inputVector )<\/p>\n

%FirstDifference Demonstrate taking the centered first difference of the input vector, as<\/p>\n

%a 1D example of an image processing edge enhancement.<\/p>\n

kernel = [-1 0 1];<\/p>\n

[rows cols] = size(V);<\/p>\n

RESULT = zeros(1,cols);<\/p>\n

% loop through the data, but we must focus on 1 pixel inside<\/p>\n

% at both ends.<\/p>\n

for i = 2:cols-1<\/p>\n

temp = 0;<\/p>\n

% loop over the “Kernel”, K, which simulates a centered first difference<\/p>\n

for j = -1:1<\/p>\n

data = inputVector(i+j);<\/p>\n

mult = kernel(j + 2);<\/p>\n

temp = temp + (data * mult);<\/p>\n

end<\/p>\n

RESULT(i) = temp;<\/p>\n

end<\/p>\n

end<\/p>\n

function [ RESULT ] = ApplyFilter( inputImage )<\/p>\n

%ApplyFilter apply a 3 by 3 filter to the input image<\/p>\n

% Modify this kernel as desired.<\/p>\n

kernel = [-1 0 1; -1 0 1; -1 0 1]<\/p>\n

dbImage = im2double(inputImage);<\/p>\n

[rows cols] = size(dbImage);<\/p>\n

RESULT = zeros(rows,cols);<\/p>\n

% loop through the data, but we must focus on 1 pixel inside<\/p>\n

% at both ends.<\/p>\n

for aRow = 2 : rows – 1<\/p>\n

for aCol = 2 : cols – 1<\/p>\n

temp = 0.0;<\/p>\n

% loop over the “Kernel”<\/p>\n

for rowOffset = -1 : 1<\/p>\n

for colOffset = -1 : 1<\/p>\n

imageRow = aRow + rowOffset;<\/p>\n

imageCol = aCol + colOffset;<\/p>\n

data = dbImage(imageRow,imageCol);<\/p>\n

mult = kernel(rowOffset + 2,colOffset + 2);<\/p>\n

% divide by two if we wish<\/p>\n

temp = temp + ((data * mult) * 0.5);<\/p>\n

end<\/p>\n

end<\/p>\n

RESULT(aRow,aCol) = temp;<\/p>\n

end<\/p>\n

end<\/p>\n

end<\/p>\n","protected":false},"excerpt":{"rendered":"

If you\u2019ve done a bit of image processing, or read about it, you\u2019ve probably run into the concept of \u201cedge detection\u201d. In the first part of this article I\u2019ll take a closer look at the basics of edge detection, and explore in more detail what\u2019s going on in those little boxes of numbers. When people […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[9],"class_list":["post-55","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-image-processing"],"_links":{"self":[{"href":"https:\/\/www.dominionsw.com\/index.php?rest_route=\/wp\/v2\/posts\/55","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.dominionsw.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.dominionsw.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.dominionsw.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.dominionsw.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=55"}],"version-history":[{"count":19,"href":"https:\/\/www.dominionsw.com\/index.php?rest_route=\/wp\/v2\/posts\/55\/revisions"}],"predecessor-version":[{"id":596,"href":"https:\/\/www.dominionsw.com\/index.php?rest_route=\/wp\/v2\/posts\/55\/revisions\/596"}],"wp:attachment":[{"href":"https:\/\/www.dominionsw.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=55"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.dominionsw.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=55"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.dominionsw.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=55"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}