Creation of edges from edgelets -- R P Futrelle -- March 2004

Introduction

Version of 27 March 2004

The creation of "edgelets" using operators such as the Sobel edge detector produces a estimate of the magnitude and direction of an edge at each pixel in an image. In order to apply our line models, single or double wing, it is necessary to have some indication that there is an extended portion of an edge in a region. A general and uniform way to do this is to merge edgelets together into larger edge segments. Various people have worked on this "linking" process and we will certainly be studying their papers. The merging can be done in a uniform way by applying clustering algorithms.

Below you'll find links to working Java code for edgelets via Sobel, plus links to two reviews on Clustering cached on our SVP sub-site.

The major topics

There are four aspects of clustering to be concerned with here. These are listed first and then elaborated on.

  1. The distance function between pairs, e.g., edgelets. Edgelets are "close", for example, when they are colinear and in nearby pixels.
  2. When edgelets are added to a cluster, then at some point we need to create a larger edge segment object, based on the edgelets in the cluster. This may be done a pair at a time or after a number of closely related edgelets have been added.
  3. A clustering algorithm needs to be chosen. There are many and they are well-studied and reviewed. Some PDFs of reviews are linked here.
  4. Because the number of pairs and their pair distances is huge, we need to pay some attention to efficiency up front. This should not be too difficult because we will never look at edgelets that are more than a few pixels apart, so that all computations are localized.

A brief run-through of the computational steps

A (bordered) image array is used. The operator, e.g., Sobel, is applied at every image pixel, within the border. The results are stored in an array of 2D vectors. Better, we may want to store the results in an array of more general objects which contains the vector as one field, or contains the x and y components as fields, and could store the magnitude in addition, computed by the Manhattan metric. A histogram of the magnitudes could be generated to allow us to choose a magnitude threshold. The edgelets could be sorted by magnitude. Then for the strongest one, its neighborhood could be examined centered on it and the edgelet clustered with the strongest other edgelets in the neighborhood (closest by the distance function). At some point, these strong and well aligned edgelets in the cluster could be used to produce an edge segment, which might be five or so pixels in length. Since the edgelets are oriented and approximately aligned, we know which side of the segment is in the line core and which is in the exterior region. This allows us to position a line model with one edge at the edge segment. We can begin with a one winged model and optimize its orientation and position. Once that's done we could add the other wing and expand the core until (and if!) the other edge of the model reached the other edge of the line.

Java experiments

To see how all this works, I've developed a few simple experiments. The one completed first generate edgelets for a simulated edge using Sobel. No clustering code is there yet. The EdgeletTest source contains the numerical output pasted in. The Javadoc is here, and the sources are here:

Clustering - Some reviews

Here are links to two recent reviews on clustering to augment the clustering book(s) in the lab.

Return to main SVP page.