Main Page | Data Structures | File List | Data Fields | Globals

lsd.h File Reference


Detailed Description

LSD module header.

Author:
rafael grompone von gioi <grompone@gmail.com>

Definition in file lsd.h.

This graph shows which files directly or indirectly include this file:

Included by dependency graph

Go to the source code of this file.

Functions

double * LineSegmentDetection (int *n_out, double *img, int X, int Y, double scale, double sigma_scale, double quant, double ang_th, double log_eps, double density_th, int n_bins, int **reg_img, int *reg_x, int *reg_y)
 LSD Full Interface.

double * lsd_scale_region (int *n_out, double *img, int X, int Y, double scale, int **reg_img, int *reg_x, int *reg_y)
 LSD Simple Interface with Scale and Region output.

double * lsd_scale (int *n_out, double *img, int X, int Y, double scale)
 LSD Simple Interface with Scale.

double * lsd (int *n_out, double *img, int X, int Y)
 LSD Simple Interface.


Function Documentation

double* LineSegmentDetection int *  n_out,
double *  img,
int  X,
int  Y,
double  scale,
double  sigma_scale,
double  quant,
double  ang_th,
double  log_eps,
double  density_th,
int  n_bins,
int **  reg_img,
int *  reg_x,
int *  reg_y
 

LSD Full Interface.

Parameters:
n_out Pointer to an int where LSD will store the number of line segments detected.
img Pointer to input image data. It must be an array of doubles of size X x Y, and the pixel at coordinates (x,y) is obtained by img[x+y*X].
X X size of the image: the number of columns.
Y Y size of the image: the number of rows.
scale When different from 1.0, LSD will scale the input image by 'scale' factor by Gaussian filtering, before detecting line segments. Example: if scale=0.8, the input image will be subsampled to 80% of its size, before the line segment detector is applied. Suggested value: 0.8
sigma_scale When scale!=1.0, the sigma of the Gaussian filter is: sigma = sigma_scale / scale, if scale < 1.0 sigma = sigma_scale, if scale >= 1.0 Suggested value: 0.6
quant Bound to the quantization error on the gradient norm. Example: if gray levels are quantized to integer steps, the gradient (computed by finite differences) error due to quantization will be bounded by 2.0, as the worst case is when the error are 1 and -1, that gives an error of 2.0. Suggested value: 2.0
ang_th Gradient angle tolerance in the region growing algorithm, in degrees. Suggested value: 22.5
log_eps Detection threshold, accept if -log10(NFA) > log_eps. The larger the value, the more strict the detector is, and will result in less detections. (Note that the 'minus sign' makes that this behavior is opposite to the one of NFA.) The value -log10(NFA) is equivalent but more intuitive than NFA:
  • -1.0 gives an average of 10 false detections on noise
  • 0.0 gives an average of 1 false detections on noise
  • 1.0 gives an average of 0.1 false detections on nose
  • 2.0 gives an average of 0.01 false detections on noise
Suggested value: 0.0
density_th Minimal proportion of 'supporting' points in a rectangle. Suggested value: 0.7
n_bins Number of bins used in the pseudo-ordering of gradient modulus. Suggested value: 1024
reg_img Optional output: if desired, LSD will return an int image where each pixel indicates the line segment to which it belongs. Unused pixels have the value '0', while the used ones have the number of the line segment, numbered 1,2,3,..., in the same order as in the output list. If desired, a non NULL int** pointer must be assigned, and LSD will make that the pointer point to an int array of size reg_x x reg_y, where the pixel value at (x,y) is obtained with (*reg_img)[x+y*reg_x]. Note that the resulting image has the size of the image used for the processing, that is, the size of the input image scaled by the given factor 'scale'. If scale!=1 this size differs from XxY and that is the reason why its value is given by reg_x and reg_y. Suggested value: NULL
reg_x Pointer to an int where LSD will put the X size 'reg_img' image, when asked for. Suggested value: NULL
reg_y Pointer to an int where LSD will put the Y size 'reg_img' image, when asked for. Suggested value: NULL
Returns:
A double array of size 7 x n_out, containing the list of line segments detected. The array contains first 7 values of line segment number 1, then the 7 values of line segment number 2, and so on, and it finish by the 7 values of line segment number n_out. The seven values are:
  • x1,y1,x2,y2,width,p,-log10(NFA)
for a line segment from coordinates (x1,y1) to (x2,y2), a width 'width', an angle precision of p in (0,1) given by angle_tolerance/180 degree, and NFA value 'NFA'. If 'out' is the returned pointer, the 7 values of line segment number 'n+1' are obtained with 'out[7*n+0]' to 'out[7*n+6]'.

Definition at line 2025 of file lsd.c.

References add_7tuple(), image_char_s::data, image_double_s::data, image_int_s::data, error(), free_image_char(), free_image_double(), gaussian_sampler(), image_char, image_double, image_int, ll_angle(), M_PI, new_image_char_ini(), new_image_double_ptr(), new_image_int_ini(), new_ntuple_list(), NOTDEF, NOTUSED, ntuple_list, rect::p, rect_improve(), refine(), region2rect(), region_grow(), ntuple_list_s::size, ntuple_list_s::values, rect::width, rect::x1, rect::x2, image_double_s::xsize, image_char_s::xsize, image_int_s::xsize, rect::y1, rect::y2, image_double_s::ysize, and image_int_s::ysize.

Referenced by lsd_scale_region().

02031 {
02032   image_double image;
02033   ntuple_list out = new_ntuple_list(7);
02034   double * return_value;
02035   image_double scaled_image,angles,modgrad;
02036   image_char used;
02037   image_int region = NULL;
02038   struct coorlist * list_p;
02039   void * mem_p;
02040   struct rect rec;
02041   struct point * reg;
02042   int reg_size,min_reg_size,i;
02043   unsigned int xsize,ysize;
02044   double rho,reg_angle,prec,p,log_nfa,logNT;
02045   int ls_count = 0;                   /* line segments are numbered 1,2,3,... */
02046 
02047 
02048   /* check parameters */
02049   if( img == NULL || X <= 0 || Y <= 0 ) error("invalid image input.");
02050   if( scale <= 0.0 ) error("'scale' value must be positive.");
02051   if( sigma_scale <= 0.0 ) error("'sigma_scale' value must be positive.");
02052   if( quant < 0.0 ) error("'quant' value must be positive.");
02053   if( ang_th <= 0.0 || ang_th >= 180.0 )
02054     error("'ang_th' value must be in the range (0,180).");
02055   if( density_th < 0.0 || density_th > 1.0 )
02056     error("'density_th' value must be in the range [0,1].");
02057   if( n_bins <= 0 ) error("'n_bins' value must be positive.");
02058 
02059 
02060   /* angle tolerance */
02061   prec = M_PI * ang_th / 180.0;
02062   p = ang_th / 180.0;
02063   rho = quant / sin(prec); /* gradient magnitude threshold */
02064 
02065 
02066   /* load and scale image (if necessary) and compute angle at each pixel */
02067   image = new_image_double_ptr( (unsigned int) X, (unsigned int) Y, img );
02068   if( scale != 1.0 )
02069     {
02070       scaled_image = gaussian_sampler( image, scale, sigma_scale );
02071       angles = ll_angle( scaled_image, rho, &list_p, &mem_p,
02072                          &modgrad, (unsigned int) n_bins );
02073       free_image_double(scaled_image);
02074     }
02075   else
02076     angles = ll_angle( image, rho, &list_p, &mem_p, &modgrad,
02077                        (unsigned int) n_bins );
02078   xsize = angles->xsize;
02079   ysize = angles->ysize;
02080 
02081   /* Number of Tests - NT
02082 
02083      The theoretical number of tests is Np.(XY)^(5/2)
02084      where X and Y are number of columns and rows of the image.
02085      Np corresponds to the number of angle precisions considered.
02086      As the procedure 'rect_improve' tests 5 times to halve the
02087      angle precision, and 5 more times after improving other factors,
02088      11 different precision values are potentially tested. Thus,
02089      the number of tests is
02090        11 * (X*Y)^(5/2)
02091      whose logarithm value is
02092        log10(11) + 5/2 * (log10(X) + log10(Y)).
02093   */
02094   logNT = 5.0 * ( log10( (double) xsize ) + log10( (double) ysize ) ) / 2.0
02095           + log10(11.0);
02096   min_reg_size = (int) (-logNT/log10(p)); /* minimal number of points in region
02097                                              that can give a meaningful event */
02098 
02099 
02100   /* initialize some structures */
02101   if( reg_img != NULL && reg_x != NULL && reg_y != NULL ) /* save region data */
02102     region = new_image_int_ini(angles->xsize,angles->ysize,0);
02103   used = new_image_char_ini(xsize,ysize,NOTUSED);
02104   reg = (struct point *) calloc( (size_t) (xsize*ysize), sizeof(struct point) );
02105   if( reg == NULL ) error("not enough memory!");
02106 
02107 
02108   /* search for line segments */
02109   for(; list_p != NULL; list_p = list_p->next )
02110     if( used->data[ list_p->x + list_p->y * used->xsize ] == NOTUSED &&
02111         angles->data[ list_p->x + list_p->y * angles->xsize ] != NOTDEF )
02112        /* there is no risk of double comparison problems here
02113           because we are only interested in the exact NOTDEF value */
02114       {
02115         /* find the region of connected point and ~equal angle */
02116         region_grow( list_p->x, list_p->y, angles, reg, &reg_size,
02117                      &reg_angle, used, prec );
02118 
02119         /* reject small regions */
02120         if( reg_size < min_reg_size ) continue;
02121 
02122         /* construct rectangular approximation for the region */
02123         region2rect(reg,reg_size,modgrad,reg_angle,prec,p,&rec);
02124 
02125         /* Check if the rectangle exceeds the minimal density of
02126            region points. If not, try to improve the region.
02127            The rectangle will be rejected if the final one does
02128            not fulfill the minimal density condition.
02129            This is an addition to the original LSD algorithm published in
02130            "LSD: A Fast Line Segment Detector with a False Detection Control"
02131            by R. Grompone von Gioi, J. Jakubowicz, J.M. Morel, and G. Randall.
02132            The original algorithm is obtained with density_th = 0.0.
02133          */
02134         if( !refine( reg, &reg_size, modgrad, reg_angle,
02135                      prec, p, &rec, used, angles, density_th ) ) continue;
02136 
02137         /* compute NFA value */
02138         log_nfa = rect_improve(&rec,angles,logNT,log_eps);
02139         if( log_nfa <= log_eps ) continue;
02140 
02141         /* A New Line Segment was found! */
02142         ++ls_count;  /* increase line segment counter */
02143 
02144         /*
02145            The gradient was computed with a 2x2 mask, its value corresponds to
02146            points with an offset of (0.5,0.5), that should be added to output.
02147            The coordinates origin is at the center of pixel (0,0).
02148          */
02149         rec.x1 += 0.5; rec.y1 += 0.5;
02150         rec.x2 += 0.5; rec.y2 += 0.5;
02151 
02152         /* scale the result values if a subsampling was performed */
02153         if( scale != 1.0 )
02154           {
02155             rec.x1 /= scale; rec.y1 /= scale;
02156             rec.x2 /= scale; rec.y2 /= scale;
02157             rec.width /= scale;
02158           }
02159 
02160         /* add line segment found to output */
02161         add_7tuple( out, rec.x1, rec.y1, rec.x2, rec.y2,
02162                          rec.width, rec.p, log_nfa );
02163 
02164         /* add region number to 'region' image if needed */
02165         if( region != NULL )
02166           for(i=0; i<reg_size; i++)
02167             region->data[ reg[i].x + reg[i].y * region->xsize ] = ls_count;
02168       }
02169 
02170 
02171   /* free memory */
02172   free( (void *) image );   /* only the double_image structure should be freed,
02173                                the data pointer was provided to this functions
02174                                and should not be destroyed.                 */
02175   free_image_double(angles);
02176   free_image_double(modgrad);
02177   free_image_char(used);
02178   free( (void *) reg );
02179   free( (void *) mem_p );
02180 
02181   /* return the result */
02182   if( reg_img != NULL && reg_x != NULL && reg_y != NULL )
02183     {
02184       if( region == NULL ) error("'region' should be a valid image.");
02185       *reg_img = region->data;
02186       if( region->xsize > (unsigned int) INT_MAX ||
02187           region->xsize > (unsigned int) INT_MAX )
02188         error("region image to big to fit in INT sizes.");
02189       *reg_x = (int) (region->xsize);
02190       *reg_y = (int) (region->ysize);
02191 
02192       /* free the 'region' structure.
02193          we cannot use the function 'free_image_int' because we need to keep
02194          the memory with the image data to be returned by this function. */
02195       free( (void *) region );
02196     }
02197   if( out->size > (unsigned int) INT_MAX )
02198     error("too many detections to fit in an INT.");
02199   *n_out = (int) (out->size);
02200 
02201   return_value = out->values;
02202   free( (void *) out );  /* only the 'ntuple_list' structure must be freed,
02203                             but the 'values' pointer must be keep to return
02204                             as a result. */
02205 
02206   return return_value;
02207 }

Here is the call graph for this function:

double* lsd int *  n_out,
double *  img,
int  X,
int  Y
 

LSD Simple Interface.

Parameters:
n_out Pointer to an int where LSD will store the number of line segments detected.
img Pointer to input image data. It must be an array of doubles of size X x Y, and the pixel at coordinates (x,y) is obtained by img[x+y*X].
X X size of the image: the number of columns.
Y Y size of the image: the number of rows.
Returns:
A double array of size 7 x n_out, containing the list of line segments detected. The array contains first 7 values of line segment number 1, then the 7 values of line segment number 2, and so on, and it finish by the 7 values of line segment number n_out. The seven values are:
  • x1,y1,x2,y2,width,p,-log10(NFA)
for a line segment from coordinates (x1,y1) to (x2,y2), a width 'width', an angle precision of p in (0,1) given by angle_tolerance/180 degree, and NFA value 'NFA'. If 'out' is the returned pointer, the 7 values of line segment number 'n+1' are obtained with 'out[7*n+0]' to 'out[7*n+6]'.

Definition at line 2243 of file lsd.c.

References lsd_scale().

02244 {
02245   /* LSD parameters */
02246   double scale = 0.8;       /* Scale the image by Gaussian filter to 'scale'. */
02247 
02248   return lsd_scale(n_out,img,X,Y,scale);
02249 }

Here is the call graph for this function:

double* lsd_scale int *  n_out,
double *  img,
int  X,
int  Y,
double  scale
 

LSD Simple Interface with Scale.

Parameters:
n_out Pointer to an int where LSD will store the number of line segments detected.
img Pointer to input image data. It must be an array of doubles of size X x Y, and the pixel at coordinates (x,y) is obtained by img[x+y*X].
X X size of the image: the number of columns.
Y Y size of the image: the number of rows.
scale When different from 1.0, LSD will scale the input image by 'scale' factor by Gaussian filtering, before detecting line segments. Example: if scale=0.8, the input image will be subsampled to 80% of its size, before the line segment detector is applied. Suggested value: 0.8
Returns:
A double array of size 7 x n_out, containing the list of line segments detected. The array contains first 7 values of line segment number 1, then the 7 values of line segment number 2, and so on, and it finish by the 7 values of line segment number n_out. The seven values are:
  • x1,y1,x2,y2,width,p,-log10(NFA)
for a line segment from coordinates (x1,y1) to (x2,y2), a width 'width', an angle precision of p in (0,1) given by angle_tolerance/180 degree, and NFA value 'NFA'. If 'out' is the returned pointer, the 7 values of line segment number 'n+1' are obtained with 'out[7*n+0]' to 'out[7*n+6]'.

Definition at line 2235 of file lsd.c.

References lsd_scale_region().

Referenced by lsd().

02236 {
02237   return lsd_scale_region(n_out,img,X,Y,scale,NULL,NULL,NULL);
02238 }

Here is the call graph for this function:

double* lsd_scale_region int *  n_out,
double *  img,
int  X,
int  Y,
double  scale,
int **  reg_img,
int *  reg_x,
int *  reg_y
 

LSD Simple Interface with Scale and Region output.

Parameters:
n_out Pointer to an int where LSD will store the number of line segments detected.
img Pointer to input image data. It must be an array of doubles of size X x Y, and the pixel at coordinates (x,y) is obtained by img[x+y*X].
X X size of the image: the number of columns.
Y Y size of the image: the number of rows.
scale When different from 1.0, LSD will scale the input image by 'scale' factor by Gaussian filtering, before detecting line segments. Example: if scale=0.8, the input image will be subsampled to 80% of its size, before the line segment detector is applied. Suggested value: 0.8
reg_img Optional output: if desired, LSD will return an int image where each pixel indicates the line segment to which it belongs. Unused pixels have the value '0', while the used ones have the number of the line segment, numbered 1,2,3,..., in the same order as in the output list. If desired, a non NULL int** pointer must be assigned, and LSD will make that the pointer point to an int array of size reg_x x reg_y, where the pixel value at (x,y) is obtained with (*reg_img)[x+y*reg_x]. Note that the resulting image has the size of the image used for the processing, that is, the size of the input image scaled by the given factor 'scale'. If scale!=1 this size differs from XxY and that is the reason why its value is given by reg_x and reg_y. Suggested value: NULL
reg_x Pointer to an int where LSD will put the X size 'reg_img' image, when asked for. Suggested value: NULL
reg_y Pointer to an int where LSD will put the Y size 'reg_img' image, when asked for. Suggested value: NULL
Returns:
A double array of size 7 x n_out, containing the list of line segments detected. The array contains first 7 values of line segment number 1, then the 7 values of line segment number 2, and so on, and it finish by the 7 values of line segment number n_out. The seven values are:
  • x1,y1,x2,y2,width,p,-log10(NFA)
for a line segment from coordinates (x1,y1) to (x2,y2), a width 'width', an angle precision of p in (0,1) given by angle_tolerance/180 degree, and NFA value 'NFA'. If 'out' is the returned pointer, the 7 values of line segment number 'n+1' are obtained with 'out[7*n+0]' to 'out[7*n+6]'.

Definition at line 2212 of file lsd.c.

References LineSegmentDetection().

Referenced by lsd_scale().

02215 {
02216   /* LSD parameters */
02217   double sigma_scale = 0.6; /* Sigma for Gaussian filter is computed as
02218                                 sigma = sigma_scale/scale.                    */
02219   double quant = 2.0;       /* Bound to the quantization error on the
02220                                 gradient norm.                                */
02221   double ang_th = 22.5;     /* Gradient angle tolerance in degrees.           */
02222   double log_eps = 0.0;     /* Detection threshold: -log10(NFA) > log_eps     */
02223   double density_th = 0.7;  /* Minimal density of region points in rectangle. */
02224   int n_bins = 1024;        /* Number of bins in pseudo-ordering of gradient
02225                                modulus.                                       */
02226 
02227   return LineSegmentDetection( n_out, img, X, Y, scale, sigma_scale, quant,
02228                                ang_th, log_eps, density_th, n_bins,
02229                                reg_img, reg_x, reg_y );
02230 }

Here is the call graph for this function:


Generated on Fri Nov 11 11:11:11 2011 for LSD by doxygen 1.3.4