Computer Vision: Boundary Detection

 Edges are local, but boundaries are more of a global entity; that is, we can say that an object has a boundary, and we want to group the edge pixels into boundaries, used to identify objects. 

We go through edge detection, thresholding, shrinking/expanding, thinning, and boundary detection in order to travel from edges to boundaries in this circumstance, to group edge pixels together into something that has a more "global meaning. 

We want to fit lines to edges by finding the distance of the line to each point. The average squared vertical distance is 

E = 1/N Σi(yi - mxi - c)^2,  we try to minimize E, and try to find the minimum of the average squared distance.

The issue here is that the points sometimes represent a vertical distance of the points from the line, and that we want to minimize the distance, not the vertical distance. 

Instead of taking vertical distances, we should be taking perpendicular distances. 

The perpendicular distance is given by the following expression. We want to minimize the distance term E. To do this, we use the first derivative test. 

We get xhat yhat where x hat is

and yhat is 

The line passes through a centroid, must pass through the coordinates.

get tan2Θ = b/a - c

which leaves 

Θ = Θ1

and Θ = Θ2 + pi/2

One solution gives the minimum of E, whereas the other gives the maximum. 

dE/dΘ = (a - c) sin 2Θ - b cos 2Θ

We find the Θ that maximizes and minimizes E, and take the second derivative in order to determine the difference between a minima and a maxima. 

Here is the test:

d2E/dΘ2 = (a - c) cos 2Θ + b sin 2Θ

if > 0 then Minimum

and < 0 then maximum.

This is a boundary detection algorithm. All we did was take a bunch of points and found the best fit line that explains these points that passes through, find the closest value possible to all of these points. 

Orientation:

Θ = Θ1 = atan2(b, a - c)/2 

This is what Θ is for the second derivative.

This approach only works if there is one boundary in the image. How do we find the boundaries to this image? 

Without knowing which points fit to a boundary, it is impossible to know that boundary as a result. Of course there is noise, and any algorithm that we design should be robust to noise. How do we find the boundaries to an image? 

Hough Transform is the solution. It works for multiple boundaries, and is fairly robust to noise, and has stood the test of time. This was in HW 2. This algorithm is VERY useful and elegant.

The simple case is the single line boundary. After that, we'll look at multiple lines. 

Consider a point (xi, yi). 

We have 2 maps, the image s[ace, and the parameter pace. 2 axes are x/y and m/c, respectively, and a point represents an image for a line in the original image space. 

It turns out all of the points in this transform concept, lie on a line, and rearrange this and write the Hough Transform into a new location. 

So the correlation goes like Point <--------------------> Line

and Line <-----------------------> Point 

We first want to create a parameter space and discretize it.

The following steps describe the Line Detection Algorithm. 

1. Quantize parameter space (m,c)

2. Create accumulator Array A(,c)

3. Set A(m,c) = 0 for all (m,c) 

4. For each edge point (xi, yi), A(m,c) += 1 if (m, c) lies on the line c = -mxi + yi

5. Find the local maxima in A(m, c). 

A rectangle will create 4 clusters, each with an intersecting point, and the boundaries of these 4 lines. 

Fewer nodes on a line will make the cluster much less dense. It is a very powerful method. 

How do we have an accumulative array with infinite sides? The problem is that the range of value of the line's slope is infinite, which means the size of the array needs to be infinite as well. 

The solution is use x sin Θ - y cos Θ + ρ = 0. The orientation may be finite, but the distance is more infinite. 

Now each point in a parameter space corresponds to a sinusoid in a parameter space. 

This is much more practical. 

There is a tradeoff in regards to accumulator cell size. Too big, and different lines can be merge, and too small the lines might be missed due to noise. The parameter size requires some trial and error? 

If you don't know how many lines there are, you can still count the number of local peaks of the accumulator array, but filtering is highly recommended. 

To handle inaccurate edge locations, increment the neighbors of the cell as well.

 This is what a Hough Transform looks like. 

The following algorithm implements a circle detection algorithm. x and y are related to A and b, and a and b are defined by multiple circles that can have this point at the center of the circle. 

We can change radiuses in these transforms to compare, for example, pemmoes and quarters. 

How do we do a generalized Hough Transform? Hough Transforms can help with arbitrary shapes. 

Hough Transformas are especially effective for simple shapes, boundaries etc. It is possible to extend this into more complex shapes. 

So far we have talked about computing boundaries from scratch, and we have already grouped them into different boundaries. We want to deform a boundary such that it becomes a better fit, to progressively get closer to edge pixels. It it becomes near pixels with a high gradient, and is smooth. 

This helps in speaking or driving a car, where boundaries deform over time. 

The main idea is to deform the contour until it "snaps" onto a boundary. 

We can look for pixels with strong gradients. These pixels are called "edge pixels". The brighter the pixel is somewhere, the stronger it is. We blur the gradient magnitude image, and the brighter a pixel is, the closer it is to an edge location. Continue deforming until it eventually gets to real boundary. We and to maximize the sum of gradients at this contour vertices.  

For each contour point move vi to a position in the window where the energy is the minimum.  Make sure the sum of these points is less than a threshold. 

We want the contour to bend smoothly and contract. We define aditional energy terms for the contours, as follows: 

Ecountour = αEelastic + βEsmooth. 

Elastic terms make the contour contract as much as possible, and the smoothness term makes the gradient smoother and prevents sharp corners.  

Etotal = Eimage + Ecountour.

With a large α it behaves more like a rubber band while a large β will make it behave like a metal strip. It depends on what you want. 

Active contour methods needs a good initialization and elasticity makes contour contract to replace contracting force with ballooning force to expand. This is used in medical-imaging. A rough boundary can be marked, and active contour can do the rest. 

We fit the contours to the gradient magnitude.