Edge detection

      #include <gandalf/vision/edge_feature.h>

An edge map is a collection of edge points (or edgels) stored in an edge map structure. The edge structure is

      /* Definition of basic 2D edge feature structure */
      typedef struct Gan_EdgeFeature
      {
         unsigned short r, c; /* row/column coordinates in coordinate frame of 2D
                                 feature array */
         Gan_Vector2_f p; /* potentially sub-pixel coordinates of edge feature in
                             coordinate frame defined by edge map */
         Gan_Vector2_f pu; /* coordinates of feature with any non-linear image
                              distortion removed */
         float strength; /* edge feature strength/contrast value */
         float angle; /* orientation of edge, where applicable. The angle is
                         measured clockwise from the positive x axis, and should
                         be in the range [-pi,pi]. The angle should point in the
                         direction of higher image intensity, or a suitably
                         analagous direction. */
         float cov; /* covariance of feature edge in direction given by the
                       orientation field (angle) */
      
         /* fields for user program to define */
         short status;
         short index;
      
         /* next and previous features in list for when edges are stored in a
            list */
         struct Gan_EdgeFeature *next, *prev;
      } Gan_EdgeFeature;

The r, c fields are the integer local coordinates of the edge feature. p and pu are coordinates in the user-defined coordinate frame. Note that here and elsewhere in the feature detection structures we employ single precision floating point in order to save memory and computation. The edge structures are designed to be placed into doubly linked strings of edges. The edge string is defined as

      /* Structure defining a connected string of edge features
       */
      typedef struct Gan_EdgeString
      {
         Gan_EdgeFeature *first, *last;
         unsigned length;
      } Gan_EdgeString;

The sense of the direction of the edge string is such that as you traverse the string from the first edge to the last edge, the brighter region is on the left. So if you are walking along the string from first to last and stick your left arm out sideways, it will point approximately in the edge direction (the angle field of a Gan_EdgeFeature). New edge detection algorithms should be written to conform to this convention, since the string direction is relevant to other procedures, such as finding line segments given an edge map as input.

The edgels and strings are built into an edge map structure as follows:

      /* Definition of 2D edge feature map structure */
      typedef struct Gan_EdgeFeatureMap
      {
         unsigned nedges;       /* number of edge features stored */
         Gan_EdgeFeature *edge; /* array of edge features */
         unsigned max_nedges;   /* allocated limit on number of edge features */

         unsigned nstrings;      /* number of connected edge strings stored */
         Gan_EdgeString *string; /* array of connected strings of edges */
         unsigned max_nstrings;  /* allocated limit on number of strings */
      
         /* dimensions of image region in which edge features have been computed */
         unsigned height, width;

         /* whether the following A, Ai fields are set */
         Gan_Bool A_set;

         /* transformation between region coordinates (0..width) and (0..height)
            and edge coordinates, and its inverse */
         Gan_Matrix23_f A, Ai;
      
         /* calibration structure defining camera used for non-linear distortion
            correction */
         Gan_Camera_f camera;

         /* local blocked feature index map */
         Gan_LocalFeatureMap local_fmap;

         /* whether this structure was dynamically allocated */
         Gan_Bool alloc;
      } Gan_EdgeFeatureMap;

The fields are fairly self-explanatory. The $A$ transformation matrix between local and user-defined global coordinates is defined by the A field. If it is not set (A_set having value GAN_FALSE) then the two coordinate systems are identical.

The most important function in this module sets up the edge feature map structure, a necessary precursor to filling it with edges. Here is in an example call to the routine.

      Gan_EdgeFeatureMap EdgeMap;

      /* initialise edge map */
      gan_edge_feature_map_form ( &EdgeMap,
                                  10000,   /* initial limit on number of edges */
                                    500 ); /* initial limit on number of edge strings */

If the initially allocated number of edges or strings is exceeded, gan_realloc_array() is used to reallocate the array(s), so if you have no idea what reasonable initial limits should be, you can pass zero for either or both.

The edge detection algorithm will then add edges and strings to the edge map, using the functions
gan_edge_feature_add() and gan_edge_feature_string_add() defined in the edge_feature.[ch] module. To free the edge map afterwards, call

      /* free edge map */
      gan_edge_feature_map_free ( &EdgeMap );

The other low-level edge routines defined in the edge_feature.[ch] module are relevant only if you are developing your own edge detector; examples of their use can be found in the Canny edge detector code.