Methods Based on Intensity Discontinuity

Loading...

En provenance du cours de Northwestern University

Fundamentals of Digital Image and Video Processing

722 notes

Northwestern University

Fundamentals of Digital Image and Video Processing

722 notes

In this class you will learn the basic principles and tools used to process images and videos, and how to apply them in solving practical problems of commercial and scientific interests. Digital images and videos are everywhere these days – in thousands of scientific (e.g., astronomical, bio-medical), consumer, industrial, and artistic applications. Moreover they come in a wide range of the electromagnetic spectrum - from visible light and infrared to gamma rays and beyond. The ability to process image and video signals is therefore an incredibly important skill to master for engineering/science students, software developers, and practicing scientists. Digital image and video processing continues to enable the multimedia technology revolution we are experiencing today. Some important examples of image and video processing include the removal of degradations images suffer during acquisition (e.g., removing blur from a picture of a fast moving car), and the compression and transmission of images and videos (if you watch videos online, or share photos via a social media website, you use this everyday!), for economical storage and efficient transmission. This course will cover the fundamentals of image and video processing. We will provide a mathematical framework to describe and analyze images and videos as two- and three-dimensional signals in the spatial, spatio-temporal, and frequency domains. In this class not only will you learn the theory behind fundamental processing tasks including image/video enhancement, recovery, and compression - but you will also learn how to perform these key processing tasks in practice using state-of-the-art techniques and tools. We will introduce and use a wide variety of such tools – from optimization toolboxes to statistical techniques. Emphasis on the special role sparsity plays in modern image and video processing will also be given. In all cases, example images and videos pertaining to specific application domains will be utilized.

À partir de la leçon

Image and Video Segmentation

In this module we introduce the problem of image and video segmentation, and discuss various approaches for performing segmentation including methods based on intensity discontinuity and intensity similarity, watersheds and K-means algorithms, and other advanced methods.

Methods Based on Intensity Discontinuity 49:49

Methods Based on Intensity Similarity 18:55

Watersheds and K-Means Algorithms 23:18

Advanced Methods 18:05

Rencontrer les enseignants

Aggelos K. Katsaggelos
Joseph Cummings Professor
Department of Electrical Engineering and Computer Science

Welcome to week 11.

This and one more week to go.

We'll address here the important topic of image and video segmentation.

For many applications you're going to be able to

group pixels together based on some of their characteristics.

Intensity and color come to mind right

away, as such characteristics, but also maybe motion.

So for example, bright regions in an image can

be grouped together, or regions which have a certain color,

or regions which have similar characteristics in a medical image,

or regions which move the same way in a video.

This is the problem of image and video segmentation.

It's an important problem, with a large number of publications in the literature.

One of the difficulties actually with this problem, is

that there is no established ground truth in an image.

In other words.

If an image is presented to two dif-, two, let's say ten different people.

And they're instructed of how to perform manual segmentation.

Most probably they'll end up with ten different segmentations.

We describe segmentation techniques, which are

based on intensity discontinuities, that is edges.

On intensity similarities and on morphological features of the image.

We also present, present techniques performing

Motion-based Segmentation and finally some techniques which

in, we can call them advanced techniques, such as Mean Shift and Graph Cut.

So, let us proceed with this exciting material.

As the saying goes, the whole is greater than the sum of its parts.

Human beings perceive an image as a whole, extract meanings behind the image, and the

segmentation of the image is a natural and intuitive task, an easy one we would say.

Machines on the other hand, perceive an image as a matrix filled with numbers.

Don't have a clue what the big picture is.

And therefore, segmentation of the image is an extremely difficult task.

The objective of image and video segmentation is to

break the image of the video into constituent meaningful regions.

And this division can be based on a number of attributes.

Such as color, texture, and, or motion.

As already mentioned, segmentation is a difficult task for the computer

and some of the challenges are the ambiguity in the data.

The ever present noise, the need to integrate high level information

into the segmentation process and the lack of ground truth.

If for example the, an image is given to ten different

people with specific instructions of how to go about segmenting this image.

Most probably, we'll, we will end up with ten different segmentations.

Based on that, the current thinking in evaluating

the performance of a segmentation system or the

quality of the resulting segmentation is to do

so by considering the end to end system.

So in other words, how will this segmentation be used?

Will it be input to a restoration system, a

classification one, compression one, tracking one and so on.

We will present some basic techniques in this

class which are based on intensity discontinuity.

Intensity similarity and and morphology.

As we will see with some of the techniques, the

output of the system will be the boundary of a region.

and clearly if this boundary is closed as shown here, then this

boundary defines a region, The pixels that are inside this boundary.

Other techniques.

Will provide the pixels belonging to a region.

So, if all these pixels belong to a specific region then clearly one

can define the boundary that separates this region from neighboring regions.

During this week, we will look at

methods towards segmentation based on the intensity discontinuity.

And more specifically, we will look at edge-based segmentation.

We'll also look at methods that are based on intensity similarity.

More specifically, thresholding, region growing and region splitting and merging.

We will then study the watersheds and K-means algorithms.

And finally we will look at some advanced methods,

such as Motion-based Segmentation, Mean shift and Graph cut.

On group of algorithms we will study toward

segmentation, are based on the detection of the discontinuities.

In the image intensity.

And these discontinuities represent the special edges in the image.

So, given an image like this, this is a picture actually

of a statue of Hercules holding the two pillars, Europe and Africa.

It is the statue that can be found at

the entrance of the harbour in Ceuta, in Spanish Morocco.

So we want to find the pixels at which the intensity transitions

from high values to low values or from low values to high values.

And such pixels will give rise to these edges here.

If we have a sensitive enough algorithm it might also detect the.

Change in intensities at these locations.

This is a mountain range in the distance, if you pay close attention

you should be able to see it or maybe pull out these intensity changes.

The result with one of the algorithms we will discuss is the one shown here.

So this result.

This algorithm did a good job in pulling out the

major edges, however it missed the not so strong ones.

The ones in, in the distance, I already mentioned.

So what are some of the ways to detect the edges?

A group of algorithms are based on taking the first

derivative of the intensity, the so called gradient of the image.

We will see some specific kernels to allow us

to take the gradient due to Sobel, Prewitt and Roberts.

We will also look at algorithms that

utilize the second derivative of the intensities or

the so called Laplacian and more specifically, we'll

discuss an algorithm due to Marr and Hildreth.

And finally we'll also look at an algorithm due

to Canny, that also detects the edges in an image.

We talked actually about gradients and the Laplacian when we covered recovery.

And when we covered also, enhancement.

Let us see what information the 1st and 2nd order derivatives provide us with.

Let's consider and one dimensional continuous function

f1 of x that looks like this.

If this were to represent the intensity of an image then this is

a good representation of a transition in intensities where an edge is located.

So it transitions from a low value here to a large value up there.

This is actually a more realistic representation of a.

Transition in intensity in images of natural scenes versus these

sharp transitions you might see very often as representing edges.

So let's take the first derivative of f1 of x.

We know that the derivative is zero down here and it's also zero up there, so

it increases the derivative and after a point

it starts decreasing so that it reaches zero again.

So indeed the first derivative looks like this, so the maximum of the

first derivative is a good candidate to tell us where an edge is located.

In this smooth transitions.

It's probably hard to tell which specific pixel represents the edge, but

the maximum again of the 1st derivative is a definitely good candidate for that.

Let us look at, another image or one dimensional

continuous function f2 of x that looks as shown here.

So it starts at the large value and.

Decades to a smaller value.

So this could also be an edge going from a high intensity to a low intensity value.

Taking the 1st derivative of this we know that

the derivative is zero here and it's zero here

as well, so it should decrease and after a

point start increasing and until it reaches zero again.

So indeed this is the 1st derivative of f2 of x.

In this case is the minimum of the 1st

derivative that indicates the location of an edge, or if

I take the absolute value is again the maximum value

of the 1st derivative indicating the location of the edge.

Let us now consider the 2nd derivative of f1 of x.

Clearly, this is the 1st derivative of its 1st derivative, f1 prime of x.

If we look at f1 prime of x then this.

Is really an f1 of x followed by an f2 of x.

So, we think this is up to a point and then starts.

Decreasing.

And therefore, the derivative, the 1st derivative

of a function like this should be this.

So if I take the 1st derivative, it should be an

f1 prime of x, followed by an f2 prime of x.

So indeed, the secondary value of f1 of x looks like this.

So in this case, it's the zero crossing that indicates the location of an edge.

If you consider the 2nd derivative of f2 of x, which is

the 1st derivative of f2 prime of x, then we see that f2

prime of x consists of an f2 of x, followed by an f1 of x.

And therefore, if I take the derivative of this, it should be the

derivative of f2 of x followed by the derivative of f1 of x.

So indeed the 2nd derivative of f2 of x, looks like this.

So again, in this case, it's the zero

crossing that indicates the location of an edge.

So in summary, taking the 1st derivative of the function, that

maximum of its absolute value will indicate the location of an edge,

while when you consider the 2nd derivative is the zero crossing, the

location of the zero crossing that indicates the location of an edge.

Let us now look at the gradient operator.

We introduced the gradient during week 6 when we talked about image recovery.

Given an image, x, n1, n2, is gradient, you noticed

by this upside down Delta, or [UNKNOWN] is a vector.

X is a scalar, its gradient is a vector.

The first component is a partial of x with respect to n1.

While the second component is a partial with respect to n2.

So here is our image coordinate system.

And let's consider a pixel location n1, n2.

So at this pixel, the partial with respect to n1.

Is denoted here, so this is, the partial with respect to n1, which

we also call g1, n1 n2 While, let's assume this is the partial.

[SOUND] With respect to n2.

So, this is the length, or the value of the partial in the n1 direction.

So the gradient is the vector that has.

These partials as its components, its projection,

so this here, the gradient at location

n1 n2 and clearly points to the direction of the greatest change in intensities.

Very often we're interested in the magnitude of the gradient.

So it's a magnitude of this vector and using the

Pythagorean theo, theorem, is a square root of this component, squared.

Plus, these components squared.

We can also find the angle of this vector, alpha, which

is simply the inverse tangent of the vertical component which you call g of 2.

N1 n2 divided by the horizontal component, g1 of n1 n2.

The next step towards edge detection, is the calculation of the gradient.

One of the standard questions in

numerical analysis is how to approximate derivatives.

1st order, 2nd order derivatives, in one or higher dimensions.

So the gradient consists of this partial.

Derivatives of all the one and in approximating

this variable use, we're going to use neighborhood differences.

There are clearly multiple ways to do so

and what we'll be doing, we will find filters.

With impulse response, lets say, h1.

So, this is the filter that will give rise

to the estimation of the partial in the n1 direction.

So this is what we call g1.

So, this is the partial of x with respect to n1.

So it's a linear, especially in variant filter, with impulse response h1.

Similarly, we will define filters with impulse response h2, which

will give rise to the partial of the image in the vertical direction.

As already mentioned.

Towards the detection, we will be, be making using of the magnitude of the

gradient, which is written again as the previous slide in terms of g1 now, and g2.

So, clearly the next question is, what are some examples of this impulse response

of these filters that will again approximate

the horizontal and the vertical partial derivatives.

We show now some examples of the impulse responses, h1

and h2, as we called them in the previous slide.

For finding respectively the horizontal and vertical

first order differences, I call them here Kernels.

At Lyon, people would associate their name with

some of this ways to approximate first order derivatives.

So, the ones due to Roberts are shown here.

So this is the impulse responsible to find the horizontal difference, h1.

Actually, what's shown here is minus n1 and minus n2.

So this is a flipped around he points the spots in both

directions, it's a step we need to take when we go for convolution.

So this particular mask is moved around on

the image and directly multiplies the pixel values.

So we see here that according to Roberts to find the horizontal partial derivative

we find the difference along the forty

five degree direction, so the pixel value at.

Xn1+1, N2+1 will be used and from that we will

subtract the value of the pixel at N1 and 2.

So similarly this is a way to find the vertical first order difference.

These kernels according to Sobel look like this.

So, in this case, six pixels are used

in finding the horizontal and the vertical differences.

And the masks, kernels, impulse responses according to Prewitt look like this.

Again, they're all reasonable ways to find this first order derivatives.

Actually, if we compare this and this, they look quite similar.

The only difference is that the values here, at this

particular locations, are different, while everything else is the same.

They do have actually Sobel and Prewitt also filters, to detect diagonal.

Changes, so for example, according to Sobel, this is also - [SOUND] - an impulse

response to find, differences in the 45 de-, degree direction.

So 1, 1, 2.

Minus 1, minus 1, minus 2.

So when you see examples in what we'll be

doing or in the literature that the Sobel or

Roberts, agitator was used, you know, exactly now, that

these are again ample responses that were used to approximate.

Restore the derivatives and therefore, the gradient.

We showed here the block diagram

of a representative gradient-based, edge detection system.

X1 and 2 is the input image for which you want to find the edges.

The gradient for this image is what you want to find first so at this point we

have available a two dimensional array and each entry of the array is a vector.

So here's example of it.

After this step the magnitude of the gradient is found so at this point we have

thrown a way the directionality of the edges

and we just kept its strength so that.

Length of the vector, so we now have a 2D array where each entry is a scalar.

So, for example, this is 1, 1, 1,

2, 0, 1.5, .5 and 0.

So these numbers are compared against the threshold.

If the number at location m1m2 is smaller than

the threshold, than no edge exists at that point.

If, however, the value's greater than the threshold, then.

That m1, m2 pixel belongs to an edge.

Since we identify edge pixels based on this

thresholding operation, very often we end up with thick.

Edges, multiple pixels belonging to an edge

and therefore typically an edge thinning algorithm.

As the name implies, the [INAUDIBLE] of such edges

is thinned, becomes smaller, maybe a couple of pixels.

And after that.

We have available the edge map of the original image X, N1, N2.

We

will demonstrate the effect of the application

of the [UNKNOWN] operator with this image.

This is an image that I showed back

in week five when we talked about enhancement.

It's a picture actually of the Technological Institute

here at Northwestern that was taken back in 1942.

The building looks very different today.

My office is around here.

Plus here where like Michigan used to be there and now about.

Half a dozen buildings, due to a landfill that was made since 1942.

We can [UNKNOWN] this

image with H1, N1, N2.

Due to Sobel.

[SOUND] But we did see the exact form of this function a couple of slides ago.

So with this filter, with a simple response, we approximate

the partial derivatives of the image in the horizontal direction.

Therefore, in the resulting image.

We detect the vertical edges in the original image.

We also detect the boundaries in the original photograph.

We also convolve this image with h2 (N1 and 2).

Also due to Sobel and as you recall, this h2 approximates

the calculation of the parcel derivatives in the vertical direction of the image.

Therefore, the resulting image will exhibit the horizontal edges.

So, this is what we see in this picture and we also see again the.

Horizontal boundaries in the original photograph, what we observe is that edges

that are neither perfectly vertical nor horizontal like, an edge like this.

They appear in both images.

This one as well as this one.

The reason for this is that these slanted edges can

be approximated by [UNKNOWN] linear either vertical or horizontal edges.

So, you see similarly activity in these regions where the edges

are not perfectly horizontal or perfectly vertical.

Let us look now at the use of the Laplacian in detecting edges.

Here is the definition of the Laplacian.

Is the gradient of the gradient or this number square of the image X N1 and 2.

It's equal to the second partial derivative in the N1 direction.

Plus the second partial derivative in the N2 direction.

The obvious next question is how to

go about evaluating this second order derivatives?

As we saw there are various ways to

approximate the horizontal and the vertical first order derivatives.

So if H1 is the impulse response of a filter that will

calculate the horizontal first order derivative it's applied to the image so

this is a first order derivative and then we apply general,

another filter to find the first order derivative of the first order derivative.

Then in finding the vertical second of the derivative we apply h2 to find the first

derivative and h2 prime to find the first

of the derivative of the first of the derivative.

So clearly even the fact that we have multiple ways

to represent h1 and h2, we saw for example the [UNKNOWN].

As examples, and since, in addition, we can use different h1

prime and h2 prime to find the second order derivative so the

first order derivative of the first order derivative, there are very many

combinations here and therefore, very many ways to calculate the, Laplacian.

If I combine the two terms here, I have

the image of the outside which is [UNKNOWN] with

the composites filter here, which consists of the convolution

of the h1s plus a convolution of the h2s.

And they can call whatever I have here.

The second site their parentheses and h, n1, n2.

So at the end clearly we want to find this

[UNKNOWN] filter that will approximate the calculation of the Laplacian.

So when converted with the image, will give us the Laplacian.

We'll show in a simple example what h1 and h1 prime and h2 and h2 prime we can use,

so that we end up with the impulsive response of

the filtered calculation of the Laplacian that looks like this.

That's minus 4 in the middle and 1, 1, 1 in the other two directions.

Let us see now what choices we need to make for the impulse responses

h1, h1 Prime, h2, and h2 prime so as to obtain the two dimensional

impulse response of the [UNKNOWN] that I showed you in the previous slide.

So in obtaining the horizontal derivatives,.

We use this expression to obtain the 1st partial horizontal derivative.

So this means that - [SOUND] - the impulse response

h1 minus n1 minus n2 looks like this.

Minus 1 here and 1 here.

So this is what this expression is telling us.

In finding the second derivative which is the first

derivative of the first derivative, we use this expression.

So, according to this.

>> The impulse response of the field

there which we called h1 prime minus

n1 minus n2 looks like this.

And if I now substitute here for g1, the g1 I have already

derived above then we obtain this expression.

So this tells us that the filter for

finding the second derivative in the horizontal direction has inverse response.

So this is h1, m1, m2 coevolved with h2, n1, n2.

A response

that looks like this.

Minus 3 in the middle, one.

One.

Similarly in computing the vertical second derivative, we

use this expression for the first order derivative.

This means that.

H2 minus n1 minus

n2 has this form.

Minus 1 here and one here.

Then in computing the second of the derivative, which is again the

first of the derivative of the first of the derivative, we use.

Expression, which simply means that the impulse response of the 2nd filter

which we call h2 prime, minus n1, minus n2, looks like this.

It's 1 here and minus 1 here.

Substituting g2 from the expression above in here, we

obtain the expression for the secondary [UNKNOWN] shown here.

So, therefore.

The filter which computes the 2nd

partial derivative, 2nd order partial derivative of the vertical direction that

is the result of convolution of h2, n1 and 2 with h2 prime and 1 and 2.

Here's this form it's minus 2 in the middle.

1 and 1.

And if you recall, at the end, the Laplacian

is the sum of this impulse response shown here.

Plus the impulse response I showed in the previous slide and therefore the, the sum

will give rise to the [UNKNOWN] theater with impulse response.

This on minus 4 in the middle because it will be a minus 2 from this.

[UNKNOWN] minus 2 from the horizontal second of

the derivative and then 1 at this four locations.

We show here the blog diagram of a system which can

be used to find the edges in an image using the Laplacian.

As you'll see precautions are taken so as not to generate false edges.

So XN1 and 2 is the image of which you

want to find the edges it's input to the system.

According to this block here the Laplacian is found.

The Laplacian can be found using any of

the approximations we discussed in the previous slides.

Then, we check if each and every pixel is a 0 crossing pixel.

Which means that neighbouring pixels change values from

negative to positive or from positive to negative.

If this is not the case, then this is not an edge pixel.

If it is the case, we don't declare this yet in edge pixel because,

for example, it can be located in a flat region, so there's no edge there.

But due to noise, when you take the Laplacian it gives rise to 0.

So, to avoid the situation we also evaluate the local variance of the image

and we compare it with the pixel location at which a 0 crossing was detected.

The local variance is greater than a threshold.

If this is not the case, this means that this pixel again

is in a flat region and the 0 crossing was due to noise.

And therefore this point is declared as a non edge point.

And don't leave this local variance as greater than

the threshold we declare the pixel as an edge point.

The result of applying the Laplacian to the cameraman

image and finding the 0 crossings is shown here.

As is clear, we find a lot of additional 0 crossings than the ones belonging

to the edges of the image and this can be due to the existence of the noise.

If we apply the system that was shown in the previous slide, according to which.

At though 0 crossings we also utilise the local variance to

determine whether that 0 crossing belongs to an edge or not.

We obtain this result.

It's a much cleaner obviously result and.

What we see is white pixels here belong really

to edges and not to noise in the image.

[BLANK_AUDIO]

Intensity changes occur at different scales.

For example, there are blurry regions in an image which represent

low frequencies, and also finely focused regions which represent high frequencies.

It will therefore be desirable to band limit

the image first, and then perform edge detection.

So we are going to have edges corresponding to different scales.

Maren Hildreth argued that edge maps of different

scales contained important information about physically significant parameters.

In battling within the image, a Gaussian filter can be used,

where the variants of the Gaussian controls the Cato frequency.

Did you note that variants here by sigma square?

So, for this smooth image, edges are detected and towards the

task any HD detection approach that we covered can be utilized.

If the Laplacian is used, then we can

either take the Laplacian of the image, then

convolve it with Gaussian or convolve the image

with the Laplacian of the Gaussian, as shown here.

So this is where the approach derives it's name.

It's the LOG approach because again, this is here the Laplacian of the Gaussian.

The Laplacian of the Gaussian can be computed analytically.

It's expression is shown here.

We've been showing all this functions here.

There's a continuous x, y variables.

A plot of this LOG is shown here.

What is more informative actually is to look at the LOG in the frequency domain.

So the full transform of the LOG is,

shown here, we can again find the analytical expression.

If we plot it, here it's how it looks.

In this example, sigma is equal to 1.

We see clearly that the LOG performs band pass filtering and the width of the.

Pass band is controlled by the variance of the Gaussian sigma.

We show here an example of the application of the LOG

approach to this particular image, it's the segment of the cameraman image.

We blend this image with a Gaussian with standard deviation equal to 2.

If you recall, taking the Laplacian of the image after it is convolved with a

Gaussian, is equivalent to convolving the image with the Laplacian of the Gaussian.

So, taking now the Laplacian of this

image, we obtain this edge image shown here.

So, these are the 0 crossings.

If we blur the original image with a Gaussian with standard deviation

equal to 4 and then obtain the Laplacian we find this result.

And finally blurred with the Gaussian with standard deviation equal

to 6 and finding the Laplacian here resulting in 0 crossings.

So, we obtain an edge map at different scales.

The density clearly of the edges is controlled by the parameter sigma.

One can therefore choose the scale that provides

the more suitable edges for the application at hand.

Or one could potential combine the edges from the value scales.

Another advantage of the use of the Gaussian is clearly, the

suppression of noise, that might be present in the original image.

Image.

A popular and effective technique towards edge detection is due to

Canny and carries his name, so it's a Canny edge detector.

It also uses the gradient towards edge detection.

But as you'll see, it uses both the

magnitude and the angle of the gradient fill.

It consists of four steps.

The first step is to smooth the image with a Gaussian filter.

And this is done towards noise suppression.

So the variants of this Gaussian filter is input to the system.

The second step is to compute the

gradient, both the magnitude and the angle.

This is a step, we covered in detail

earlier and we know now that there are different

ways to compute the gradient and we also know

how to obtain both the magnitude and the angle.

The third step, is to apply

non-maximal suppression to the gradient magnitude image.

This is a step I'll explain in detail next, but according to this step.

We find the local maximum of the magnitude

of the gradient along the direction of the edge.

So therefore the angle information is used.

And the final step is to create connected edges with the use of two thresholds.

There'll be a high threshold and a low threshold.

And these are also inputs to the algorithm.

So we'll look at the details of the last two steps next.

Seems there is nothing that we need really

to add with respect to the first two steps.

The idea of the non-maximal suppression step

is to find the locally maximum value of

the gradient by only considering the pixels in

the neighborhood that belong to the same edge.

This is determined by the value of the angle of the gradient, so

we utilize with this approach all the information of the gradient field that

is both components of the gradient vector, the magnitude and its angle, and

not just the magnitude, as we did in the previous cases that we studied.

Now, as we saw, the gradient vector

is perpendicular to the direction of the edge.

So, a vertical edge has a horizontal gradient vector.

We do not want to be stringent in determining which pixels belong

to the same edge, so we quantize the edge directions into four groups.

Horizontal,

minus 45 degrees, plus 45 degrees and vertical edge directions.

By doing so in essence we divide there 360 degree celkon into four regions.

So, an edge is a vertical edge, as long as its direction is

in the shaded ranges between 67.5 and 112.5 degrees.

This is a 45 degree here arc.

And, in this region, so this is 67.5 plus 180 and this point

here is 112.5 plus 180.

After we established

this, we examine each and every point in the angle image.

And for the particular angle value, we find one

of the four directions that is closest to it.

So, we classify this particular pixel as having

horizontal minus 45, plus 45, or vertical edge direction.

[BLANK_AUDIO]

Then we look at the magnitude of the gradient of that pixel, and we consider

the neighbours based on this classification that you already did.

So if this magnitude is less than at least one of its neighbours, we ignore it.

We suppress it.

Otherwise, we keep it.

We obtain a thin edge from the previous step, but not necessarily a connected

edge, This is actually a common problem

with this gradient based edge detection algorithms.

So, the objective of this step is to link edge pixels.

Two thresholds are input into the algorithm.

A high one, T of H and a low one, T of L.

Then based on this thresholds, pixels with

values greater than TH are classified as strong

edge pixels, while pixels with values smaller

than TL are classified as weak edge pixels.

So the procedure for linking the edge pixels is to locate a

pixel p that is classified as a strong pixel and then

we look for weak pixels that are connected to

this strong pixel and if we find such pixels then they are appended.

To the strong pixel p.

Clearly, the values of T of Hand T of L

are critical for the quality of the resulting edge image.

We compare here experimentally three of the algorithms we started so far.

We utilize this image that I showed earlier, the Pillars of Hercules.

And we apply to it, the Sobel edge detector and obtain this result, the LOG

algorithm and we obtain this result and Canny's edge detector with this result.

As mentioned earlier, there is typically no ground truth

in comparing the results of the various edge detection algorithms.

And so, it's not possible to come up with an objective

metric that will again compare the

performance of the, these three algorithms.

Now, the result shown here were obtained clearly with

specific values of the various parameters that are needed.

So, a threshold is needed for obtaining the Sobel result.

The variance of the Gaussian is to defined with LOG and we

saw that their three parameters needed to obtain the result by Canny's algorithm.

So clearly changing this parameters that results with look differently.

By looking at the results we can comment

at various attributes I guess of which, of those.

So we can comment that, that.

Thickness of the line here obtained by Sobel, not a very

desirable necessarily quality, or we can point to the

disconnected edges here by the LOG or we can also point

at the incomplete edges here by Canny's algorithm.

One could argue, again looking subjectively at this images

and qualitatively that Canny's edge detector is definitely doing a,

a very good job in just pulling out these

thin and straight edges along this direction, along this direction.

Still, however, even this album has this

problem I mentioned, of the incomplete edges.

And that's why we need a Hough transform

that we will be discussing in the next slides.

The Hough transform addresses the incompleteness of

straight edges, resulting from various algorithms, as was

pointed out, for example, in the result

by the Canny,s detector in the previous slide.

The basic idea is explained here.

Let us consider a set of points that belong to a line

or a line has been fit through the, this set of points.

So here is the equation of the line.

A prime is the slope.

And b prime is the y-intercept of this line.

We can rewrite the equation of this line in terms of and b.

So in this ab domain, mine was.

1 over x is now the slope,

and y over x is the a intercept.

So, this is now a line in the ab space, the so-called parameter space.

For each xiyi, if I fix the value of x and y here, I obtain a line in the ab space.

So, for one value of x and y, I obtain this line.

For an another one, this line, this line.

This line and so on.

What

is the main characteristic of all these lines?

It is that they go through the same point and this is

the point, a prime, b prime, the parameters of my initial line.

Therefore, by looking at this parameter space, the ab space, the parameters of

the initial line that I started with, my a prime and b prime, can be pulled out.

So this is the main idea that if I have a set of points that belong on a line then

looking at the parameter space I can find a slope

and the y intercept and therefore I can find an equation.

For the line that goes through all these points.

A difficulty with this representation is that

a vertical line that has an infinite slope

cannot be represented into this ab parameter

space and therefore we need to find another.

Representation for this case.

In addressing the difficulty of representing a

line with infinite slope in the ab parameter

space that we showed in the previous slide

the polar representation of a line is considered.

So we see here again a line and Hough is the distance.

Of the line from the origin, so this is

perpendicular to the line and theta is the angle.

So, all the points of this line satisfy this equation.

We can now use a, a row feta parameter

space to represent the various points on this line.

So if we consider a particular point xi, yi then it satisfies this

equation and by plotting this equation we get a sinusoidal type of curve.

So the reasoning is exactly the same as

before if I consider multiple points on this line.

They will give rise to multiple sinusoidal curves

like this and all these curves will go

through the same rho theta point that describes

my initial line that I want to characterize.

We show here an experimental results of the

application of the Hough Transform utilizing the rho theta.

But on the space, which is a space

of choice when the Hough transform is implemented.

So we see here in the xy plane, points that belong

to a line, but all the points are not connected.

For each and every point, we find its representation in the Hough Theta domain.

And we get this sinusoidal curve that we showed in the previous slide.

So what we observe is that all these curves go through one specific point and

this specific point has coordinates rho equals 0 and theta is minus 45 degrees.

So, the dominant line that describe all these points passes through

the origin and forms a minus 45 degrees angle with the x axis.

We summarize here the procedural steps of the Hough Transform.

We start by finding the edges in an image, using any

of the available techniques, like the ones we have already discussed.

We then map each and every point of an edge onto the rho theta plane.

We take the raw theta plane and we break it into cells.

And for its cell, we count how many intersects we observe.

If this number is a substantial, then there is a

line in the original image plane, otherwise there is no line.

And with this procedure, we bridge the gap based on continuity.

And we can declare that the gap is bridged if

the length of the gap is smaller than the threshold.

We show here result of the application of the Hough transform.

We utilize again this image.

Canny's edge detector is applied to this image.

We obtained the edge map, the one I showed a few slides ago and then we

take each and every edge point and we map it on to the raw theta plane.

So, that's how it looks and we see here that there are

three intersect points here, three at this location and three at this location.

So, therefore there are nine lines, the dominant lines that have been identified.

And these lines are superimposed on the original image.

We can use these lines to complete some of the edges.

That we found by this particular exotype.

So that as we pointed out earlier, they were not, completed.

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2018 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play