Last updated on Wednesday, October 25, 1995 at 9:00 AM.
In this lecture, we'll talk about how to link sets of possible edge pixels to find connected boundaries. (In other words, we'll start playing connect-the-dots.)
We'll call 
the set of edge pixels.
We can link adjacent edge pixels by examining each pixel-neighbor pair and seeing if they have similar properties:
for some magnitude difference threshold T.
for some angular threshold A.
Notice that unless you constrain the linked pixels in some sense (for example, by scanning along horizontal or vertical lines), these can create clusters of linked pixels rather than long single-pixel thick chains.
Edge linking is usually followed by postprocessing to find sets of linked pixels that are separated by small gaps-these can the be filled in.
Let's consider this question of whether or not a pixel between two sets of edge pixels is itself an edge pixel. One way of determining this is to look at the magnitude of the intervening pixel: if it is relatively high, but less than the threshold used to determine that its neighbors are edge pixels, it's probably an edge. Of course, we can also check the similarity of the gradient magnitude and gradient orientation, just like we did with edge linking.
We can also use this not just to interpolate between edge pixels, but to extrapolate from them as well. Suppose that we have two adjacent edge pixels followed my a slightly sub-threshold one (with similar gradient magnitude and orientation). Again, it's likely that this is really an edge pixel.
We can add these possible pixels to the set of edge pixels and repeat the process. Supposing that these are now really edge pixels, there may be other near-misses that we might want to allow as edge pixels.
In a sense, we are successively relaxing the criteria used to determine edge pixels, taking into account not just the properties of the pixel in question but of its neighbors as well.
This process is calle d edge relaxation.
In general, the term relaxation applies any technique such as this that iteratively re-evaluate pixel classification.
One way to do this is to consider the image as being a graph where the vertices of the graph are the pixel corners and the edges of the graph are the pixel cracks. We can then use gradient or other edge-detecting operators to assign costs to each edge. Edge-like cracks would have low costs; cracks that do not look like edges would have high cost. The problem of finding an optimal boundary through as set of possible pixels thus becomes a simple minimal-cost path, graph-searching problem. (And of course, you should all know how to find minimum-cost paths through graphs.)
There are four basic subparts to this problem:
Let's take a look at an example before we discuss each of these four in more detail.
As an example, let's consider the case where we know that the boundary runs from the top to the bottom of some subset of the image without looping backwards. We can thus build a starting node representing the top of the image. The edges proceeding out from this node are all vertical cracks on the top row of the image. For each of these edges, successors include the corresponding vertical crack on next row, the horizontal crack to the left, and the horizontal crack to the right. Each of these has successors that go down vertically or sideways horizontally. Eventually, we get to the bottom row of the image where all paths lead to the end node.
where 
is the maximum pixel value.
Remember that we're trying to trying to trace between the inside (one
intensity) and the outside (presumably another intensity) of an
object.
The example is obviously a simple cast, but we can do similar things for more complicated cases. If we know that the boundary goes around the object with a monotomically increasing radial angle (i.e., it may move towards or away from the center as it goes around, but it never doubles back as one sweeps around), we can construct a constraining band around the potential boundary. We can also construct our graph so that it at each stage it sweeps radially around the image, but can vary in radial distance.
Both of these formulations give us discrete multistage graphs,
either as we move from row to row or radially around the boundary.
Sometimes, though, we may want to allow the graph to curve and wind,
passing through possibly any pixel. In such a formulation, we
can allow unoriented edges along any pixel crack in the image. In
other words, an 
image would have 
nodes
and 
edges.
Our search could be between any two vertices and could trace through
any of the edges.
This is obviously a huge graph and a compute-intensity search.
All of the above possible cost functions are based on the image data, not properties of the boundary curve itself. If we want smoother contours, we can add more cost for paths that would cause greater curvature.
Cost properties based on image data are called external cost terms; cost properties based on the boundary curve are called internal cost terms. Notice that internal cost for an edge is not fixed--it depends on the curve preceeding the edge.
One important property of the starting and ending points is that thier selection shouldn't dramatically change the result. While this sometimes happens, it is not a good thing.
Common ways include:
Notice that all of these involve our old friend: optimization.
© Bryan S. Morse, 1995