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.

Data Structures

struct  image_char_s
 char image data type More...

struct  image_double_s
 double image data type More...

struct  image_int_s
 int image data type More...

struct  ntuple_list_s
 'list of n-tuple' data type More...


Typedefs

typedef ntuple_list_sntuple_list
 'list of n-tuple' data type

typedef image_char_simage_char
 char image data type

typedef image_int_simage_int
 int image data type

typedef image_double_simage_double
 double image data type


Functions

void free_ntuple_list (ntuple_list in)
 Free memory used in n-tuple 'in'.

ntuple_list new_ntuple_list (unsigned int dim)
 Create an n-tuple list and allocate memory for one element.

void free_image_char (image_char i)
 Free memory used in image_char 'i'.

image_char new_image_char (unsigned int xsize, unsigned int ysize)
 Create a new image_char of size 'xsize' times 'ysize'.

image_char new_image_char_ini (unsigned int xsize, unsigned int ysize, unsigned char fill_value)
 Create a new image_char of size 'xsize' times 'ysize', initialized to the value 'fill_value'.

void free_image_int (image_int i)
 Free memory used in image_int 'i'.

image_int new_image_int (unsigned int xsize, unsigned int ysize)
 Create a new image_int of size 'xsize' times 'ysize'.

image_int new_image_int_ini (unsigned int xsize, unsigned int ysize, int fill_value)
 Create a new image_int of size 'xsize' times 'ysize', initialized to the value 'fill_value'.

void free_image_double (image_double i)
 Free memory used in image_double 'i'.

image_double new_image_double (unsigned int xsize, unsigned int ysize)
 Create a new image_double of size 'xsize' times 'ysize'.

image_double new_image_double_ini (unsigned int xsize, unsigned int ysize, double fill_value)
 Create a new image_double of size 'xsize' times 'ysize', initialized to the value 'fill_value'.

ntuple_list LineSegmentDetection (image_double image, double scale, double sigma_scale, double quant, double ang_th, double eps, double density_th, int n_bins, double max_grad, image_int *region)
 LSD Full Interface.

ntuple_list lsd_scale (image_double image, double scale)
 LSD Simple Interface with Scale.

ntuple_list lsd (image_double image)
 LSD Simple Interface.


Typedef Documentation

typedef struct image_char_s * image_char
 

char image data type

The pixel value at (x,y) is accessed by:

image->data[ x + y * image->xsize ]

with x and y integer.

Referenced by free_image_char(), LineSegmentDetection(), new_image_char(), new_image_char_ini(), reduce_region_radius(), refine(), and region_grow().

typedef struct image_double_s * image_double
 

double image data type

The pixel value at (x,y) is accessed by:

image->data[ x + y * image->xsize ]

with x and y integer.

Referenced by free_image_double(), gaussian_sampler(), get_theta(), isaligned(), LineSegmentDetection(), ll_angle(), lsd(), lsd_scale(), new_image_double(), new_image_double_ini(), rect_improve(), rect_nfa(), reduce_region_radius(), refine(), region2rect(), and region_grow().

typedef struct image_int_s * image_int
 

int image data type

The pixel value at (x,y) is accessed by:

image->data[ x + y * image->xsize ]

with x and y integer.

Referenced by free_image_int(), LineSegmentDetection(), new_image_int(), and new_image_int_ini().

typedef struct ntuple_list_s * ntuple_list
 

'list of n-tuple' data type

The i component, of the n-tuple number j, of an n-tuple list 'ntl' is accessed with:

ntl->values[ i + j * ntl->dim ]

The dimension of the n-tuple (n) is:

ntl->dim

The number of number of n-tuples in the list is:

ntl->size

The maximum number of n-tuples that can be stored in the list with the allocated memory at a given time is given by:

ntl->max_size

Referenced by add_5tuple(), enlarge_ntuple_list(), free_ntuple_list(), gaussian_kernel(), gaussian_sampler(), LineSegmentDetection(), lsd(), lsd_scale(), and new_ntuple_list().


Function Documentation

void free_image_char image_char  i  ) 
 

Free memory used in image_char 'i'.

Definition at line 280 of file lsd.c.

References image_char_s::data, error(), and image_char.

Referenced by LineSegmentDetection().

00281 {
00282   if( i == NULL || i->data == NULL )
00283     error("free_image_char: invalid input image.");
00284   free( (void *) i->data );
00285   free( (void *) i );
00286 }

Here is the call graph for this function:

void free_image_double image_double  i  ) 
 

Free memory used in image_double 'i'.

Definition at line 387 of file lsd.c.

References image_double_s::data, error(), and image_double.

Referenced by gaussian_sampler(), and LineSegmentDetection().

00388 {
00389   if( i == NULL || i->data == NULL )
00390     error("free_image_double: invalid input image.");
00391   free( (void *) i->data );
00392   free( (void *) i );
00393 }

Here is the call graph for this function:

void free_image_int image_int  i  ) 
 

Free memory used in image_int 'i'.

Definition at line 336 of file lsd.c.

References image_int_s::data, error(), and image_int.

00337 {
00338   if( i == NULL || i->data == NULL )
00339     error("free_image_int: invalid input image.");
00340   free( (void *) i->data );
00341   free( (void *) i );
00342 }

Here is the call graph for this function:

void free_ntuple_list ntuple_list  in  ) 
 

Free memory used in n-tuple 'in'.

Definition at line 194 of file lsd.c.

References error(), ntuple_list, and ntuple_list_s::values.

Referenced by gaussian_sampler().

00195 {
00196   if( in == NULL || in->values == NULL )
00197     error("free_ntuple_list: invalid n-tuple input.");
00198   free( (void *) in->values );
00199   free( (void *) in );
00200 }

Here is the call graph for this function:

ntuple_list LineSegmentDetection image_double  image,
double  scale,
double  sigma_scale,
double  quant,
double  ang_th,
double  eps,
double  density_th,
int  n_bins,
double  max_grad,
image_int region
 

LSD Full Interface.

Parameters:
image Input image.
scale When different than 1.0, LSD will scale the image by Gaussian filtering. Example: is scale=0.8, the input image will be subsampled to 80% of its size, and then the line segment detector will be 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 level is 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
eps Detection threshold, -log10(NFA). The bigger, 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 corresponds to 10 mean false alarms
  • 0.0 corresponds to 1 mean false alarm
  • 1.0 corresponds to 0.1 mean false alarms
  • 2.0 corresponds to 0.01 mean false alarms
Suggested value: 0.0
density_th Minimal proportion of region points in a rectangle. Suggested value: 0.7
n_bins Number of bins used in the pseudo-ordering of gradient modulus. Suggested value: 1024
max_grad Gradient modulus in the highest bin. For example, for images with integer gray levels in [0,255], the maximum possible gradient value is 255.0. Suggested value: 255.0
region Optional output: an int image where the pixels used in some line support region are marked. Unused pixels have the value '0' while the used ones have the number of the line segment, numbered 1,2,3,... If desired, a non NULL pointer to an image_int should be used. 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'. Suggested value: NULL
Returns:
A 5-tuple list, where each 5-tuple corresponds to a detected line segment. The five values are:
  • x1,y1,x2,y2,width
for a line segment from (x1,y1) to (x2,y2) and a width 'width'.

Definition at line 1913 of file lsd.c.

References add_5tuple(), image_double_s::data, image_char_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_int_ini(), new_ntuple_list(), NOTDEF, NOTUSED, ntuple_list, rect_improve(), refine(), region2rect(), region_grow(), rect::width, rect::x1, rect::x2, image_double_s::xsize, image_char_s::xsize, rect::y1, rect::y2, and image_double_s::ysize.

Referenced by lsd_scale().

01918 {
01919   ntuple_list out = new_ntuple_list(5);
01920   image_double scaled_image,angles,modgrad;
01921   image_char used;
01922   struct coorlist * list_p;
01923   void * mem_p;
01924   struct rect rec;
01925   struct point * reg;
01926   int reg_size,min_reg_size,i;
01927   unsigned int xsize,ysize;
01928   double rho,reg_angle,prec,p,log_nfa,logNT;
01929   int ls_count = 0;                   /* line segments are numbered 1,2,3,... */
01930 
01931 
01932   /* check parameters */
01933   if( image==NULL || image->data==NULL || image->xsize==0 || image->ysize==0 )
01934     error("invalid image input.");
01935   if( scale <= 0.0 ) error("'scale' value must be positive.");
01936   if( sigma_scale <= 0.0 ) error("'sigma_scale' value must be positive.");
01937   if( quant < 0.0 ) error("'quant' value must be positive.");
01938   if( ang_th <= 0.0 || ang_th >= 180.0 )
01939     error("'ang_th' value must be in the range (0,180).");
01940   if( density_th < 0.0 || density_th > 1.0 )
01941     error("'density_th' value must be in the range [0,1].");
01942   if( n_bins <= 0 ) error("'n_bins' value must be positive.");
01943   if( max_grad <= 0.0 ) error("'max_grad' value must be positive.");
01944 
01945 
01946   /* angle tolerance */
01947   prec = M_PI * ang_th / 180.0;
01948   p = ang_th / 180.0;
01949   rho = quant / sin(prec); /* gradient magnitude threshold */
01950 
01951 
01952   /* scale image (if necessary) and compute angle at each pixel */
01953   if( scale != 1.0 )
01954     {
01955       scaled_image = gaussian_sampler( image, scale, sigma_scale );
01956       angles = ll_angle( scaled_image, rho, &list_p, &mem_p,
01957                          &modgrad, (unsigned int) n_bins, max_grad );
01958       free_image_double(scaled_image);
01959     }
01960   else
01961     angles = ll_angle( image, rho, &list_p, &mem_p, &modgrad,
01962                        (unsigned int) n_bins, max_grad );
01963   xsize = angles->xsize;
01964   ysize = angles->ysize;
01965   logNT = 5.0 * ( log10( (double) xsize ) + log10( (double) ysize ) ) / 2.0;
01966   min_reg_size = (int) (-logNT/log10(p)); /* minimal number of points in region
01967                                              that can give a meaningful event */
01968 
01969 
01970   /* initialize some structures */
01971   if( region != NULL ) /* image to output pixel region number, if asked */
01972     *region = new_image_int_ini(angles->xsize,angles->ysize,0);
01973   used = new_image_char_ini(xsize,ysize,NOTUSED);
01974   reg = (struct point *) calloc( (size_t) (xsize*ysize), sizeof(struct point) );
01975   if( reg == NULL ) error("not enough memory!");
01976 
01977 
01978   /* search for line segments */
01979   for(; list_p != NULL; list_p = list_p->next )
01980     if( used->data[ list_p->x + list_p->y * used->xsize ] == NOTUSED &&
01981         angles->data[ list_p->x + list_p->y * angles->xsize ] != NOTDEF )
01982        /* there is no risk of double comparison problems here
01983           because we are only interested in the exact NOTDEF value */
01984       {
01985         /* find the region of connected point and ~equal angle */
01986         region_grow( list_p->x, list_p->y, angles, reg, &reg_size,
01987                      &reg_angle, used, prec );
01988 
01989         /* reject small regions */
01990         if( reg_size < min_reg_size ) continue;
01991 
01992         /* construct rectangular approximation for the region */
01993         region2rect(reg,reg_size,modgrad,reg_angle,prec,p,&rec);
01994 
01995         /* Check if the rectangle exceeds the minimal density of
01996            region points. If not, try to improve the region.
01997            The rectangle will be rejected if the final one does
01998            not fulfill the minimal density condition.
01999            This is an addition to the original LSD algorithm published in
02000            "LSD: A Fast Line Segment Detector with a False Detection Control"
02001            by R. Grompone von Gioi, J. Jakubowicz, J.M. Morel, and G. Randall.
02002            The original algorithm is obtained with density_th = 0.0.
02003          */
02004         if( !refine( reg, &reg_size, modgrad, reg_angle,
02005                      prec, p, &rec, used, angles, density_th ) ) continue;
02006 
02007         /* compute NFA value */
02008         log_nfa = rect_improve(&rec,angles,logNT,eps);
02009         if( log_nfa <= eps ) continue;
02010 
02011         /* A New Line Segment was found! */
02012         ++ls_count;  /* increase line segment counter */
02013 
02014         /*
02015            The gradient was computed with a 2x2 mask, its value corresponds to
02016            points with an offset of (0.5,0.5), that should be added to output.
02017            The coordinates origin is at the center of pixel (0,0).
02018          */
02019         rec.x1 += 0.5; rec.y1 += 0.5;
02020         rec.x2 += 0.5; rec.y2 += 0.5;
02021 
02022         /* scale the result values if a subsampling was performed */
02023         if( scale != 1.0 )
02024           {
02025             rec.x1 /= scale; rec.y1 /= scale;
02026             rec.x2 /= scale; rec.y2 /= scale;
02027             rec.width /= scale;
02028           }
02029 
02030         /* add line segment found to output */
02031         add_5tuple(out, rec.x1, rec.y1, rec.x2, rec.y2, rec.width);
02032 
02033         /* add region number to 'region' image if needed */
02034         if( region != NULL )
02035           for(i=0; i<reg_size; i++)
02036             (*region)->data[reg[i].x+reg[i].y*(*region)->xsize] = ls_count;
02037       }
02038 
02039 
02040   /* free memory */
02041   free_image_double(angles);
02042   free_image_double(modgrad);
02043   free_image_char(used);
02044   free( (void *) reg );
02045   free( (void *) mem_p );
02046 
02047   return out;
02048 }

Here is the call graph for this function:

ntuple_list lsd image_double  image  ) 
 

LSD Simple Interface.

Parameters:
image Input image.
Returns:
a 5-tuple list of detected line segments.

Definition at line 2077 of file lsd.c.

References image_double, lsd_scale(), and ntuple_list.

02078 {
02079   /* LSD parameters */
02080   double scale = 0.8;       /* Scale the image by Gaussian filter to 'scale'. */
02081 
02082   return lsd_scale(image,scale);
02083 }

Here is the call graph for this function:

ntuple_list lsd_scale image_double  image,
double  scale
 

LSD Simple Interface with Scale.

Parameters:
image Input image.
scale When different than 1.0, LSD will scale the image by Gaussian filtering. Example: is scale=0.8, the input image will be subsampled to 80% of its size, and then the line segment detector will be applied. Suggested value: 0.8
Returns:
a 5-tuple list of detected line segments.

Definition at line 2053 of file lsd.c.

References image_double, LineSegmentDetection(), and ntuple_list.

Referenced by lsd().

02054 {
02055   /* LSD parameters */
02056   double sigma_scale = 0.6; /* Sigma for Gaussian filter is computed as
02057                                 sigma = sigma_scale/scale.                    */
02058   double quant = 2.0;       /* Bound to the quantization error on the
02059                                 gradient norm.                                */
02060   double ang_th = 22.5;     /* Gradient angle tolerance in degrees.           */
02061   double eps = 0.0;         /* Detection threshold, -log10(NFA).              */
02062   double density_th = 0.7;  /* Minimal density of region points in rectangle. */
02063   int n_bins = 1024;        /* Number of bins in pseudo-ordering of gradient
02064                                modulus.                                       */
02065   double max_grad = 255.0;  /* Gradient modulus in the highest bin. The
02066                                default value corresponds to the highest
02067                                gradient modulus on images with gray
02068                                levels in [0,255].                             */
02069 
02070   return LineSegmentDetection( image, scale, sigma_scale, quant, ang_th, eps,
02071                                density_th, n_bins, max_grad, NULL );
02072 }

Here is the call graph for this function:

image_char new_image_char unsigned int  xsize,
unsigned int  ysize
 

Create a new image_char of size 'xsize' times 'ysize'.

Definition at line 291 of file lsd.c.

References image_char_s::data, error(), image_char, image_char_s::xsize, and image_char_s::ysize.

Referenced by new_image_char_ini().

00292 {
00293   image_char image;
00294 
00295   /* check parameters */
00296   if( xsize == 0 || ysize == 0 ) error("new_image_char: invalid image size.");
00297 
00298   /* get memory */
00299   image = (image_char) malloc( sizeof(struct image_char_s) );
00300   if( image == NULL ) error("not enough memory.");
00301   image->data = (unsigned char *) calloc( (size_t) (xsize*ysize),
00302                                           sizeof(unsigned char) );
00303   if( image->data == NULL ) error("not enough memory.");
00304 
00305   /* set image size */
00306   image->xsize = xsize;
00307   image->ysize = ysize;
00308 
00309   return image;
00310 }

Here is the call graph for this function:

image_char new_image_char_ini unsigned int  xsize,
unsigned int  ysize,
unsigned char  fill_value
 

Create a new image_char of size 'xsize' times 'ysize', initialized to the value 'fill_value'.

Definition at line 316 of file lsd.c.

References image_char_s::data, error(), image_char, and new_image_char().

Referenced by LineSegmentDetection().

00318 {
00319   image_char image = new_image_char(xsize,ysize); /* create image */
00320   unsigned int N = xsize*ysize;
00321   unsigned int i;
00322 
00323   /* check parameters */
00324   if( image == NULL || image->data == NULL )
00325     error("new_image_char_ini: invalid image.");
00326 
00327   /* initialize */
00328   for(i=0; i<N; i++) image->data[i] = fill_value;
00329 
00330   return image;
00331 }

Here is the call graph for this function:

image_double new_image_double unsigned int  xsize,
unsigned int  ysize
 

Create a new image_double of size 'xsize' times 'ysize'.

Definition at line 398 of file lsd.c.

References image_double_s::data, error(), image_double, image_double_s::xsize, and image_double_s::ysize.

Referenced by gaussian_sampler(), ll_angle(), and new_image_double_ini().

00399 {
00400   image_double image;
00401 
00402   /* check parameters */
00403   if( xsize == 0 || ysize == 0 ) error("new_image_double: invalid image size.");
00404 
00405   /* get memory */
00406   image = (image_double) malloc( sizeof(struct image_double_s) );
00407   if( image == NULL ) error("not enough memory.");
00408   image->data = (double *) calloc( (size_t) (xsize*ysize), sizeof(double) );
00409   if( image->data == NULL ) error("not enough memory.");
00410 
00411   /* set image size */
00412   image->xsize = xsize;
00413   image->ysize = ysize;
00414 
00415   return image;
00416 }

Here is the call graph for this function:

image_double new_image_double_ini unsigned int  xsize,
unsigned int  ysize,
double  fill_value
 

Create a new image_double of size 'xsize' times 'ysize', initialized to the value 'fill_value'.

Definition at line 422 of file lsd.c.

References image_double_s::data, image_double, and new_image_double().

00424 {
00425   image_double image = new_image_double(xsize,ysize); /* create image */
00426   unsigned int N = xsize*ysize;
00427   unsigned int i;
00428 
00429   /* initialize */
00430   for(i=0; i<N; i++) image->data[i] = fill_value;
00431 
00432   return image;
00433 }

Here is the call graph for this function:

image_int new_image_int unsigned int  xsize,
unsigned int  ysize
 

Create a new image_int of size 'xsize' times 'ysize'.

Definition at line 347 of file lsd.c.

References image_int_s::data, error(), image_int, image_int_s::xsize, and image_int_s::ysize.

Referenced by new_image_int_ini().

00348 {
00349   image_int image;
00350 
00351   /* check parameters */
00352   if( xsize == 0 || ysize == 0 ) error("new_image_int: invalid image size.");
00353 
00354   /* get memory */
00355   image = (image_int) malloc( sizeof(struct image_int_s) );
00356   if( image == NULL ) error("not enough memory.");
00357   image->data = (int *) calloc( (size_t) (xsize*ysize), sizeof(int) );
00358   if( image->data == NULL ) error("not enough memory.");
00359 
00360   /* set image size */
00361   image->xsize = xsize;
00362   image->ysize = ysize;
00363 
00364   return image;
00365 }

Here is the call graph for this function:

image_int new_image_int_ini unsigned int  xsize,
unsigned int  ysize,
int  fill_value
 

Create a new image_int of size 'xsize' times 'ysize', initialized to the value 'fill_value'.

Definition at line 371 of file lsd.c.

References image_int_s::data, image_int, and new_image_int().

Referenced by LineSegmentDetection().

00373 {
00374   image_int image = new_image_int(xsize,ysize); /* create image */
00375   unsigned int N = xsize*ysize;
00376   unsigned int i;
00377 
00378   /* initialize */
00379   for(i=0; i<N; i++) image->data[i] = fill_value;
00380 
00381   return image;
00382 }

Here is the call graph for this function:

ntuple_list new_ntuple_list unsigned int  dim  ) 
 

Create an n-tuple list and allocate memory for one element.

Parameters:
dim the dimension (n) of the n-tuple.

Definition at line 206 of file lsd.c.

References ntuple_list_s::dim, error(), ntuple_list_s::max_size, ntuple_list, ntuple_list_s::size, and ntuple_list_s::values.

Referenced by gaussian_sampler(), and LineSegmentDetection().

00207 {
00208   ntuple_list n_tuple;
00209 
00210   /* check parameters */
00211   if( dim == 0 ) error("new_ntuple_list: 'dim' must be positive.");
00212 
00213   /* get memory for list structure */
00214   n_tuple = (ntuple_list) malloc( sizeof(struct ntuple_list_s) );
00215   if( n_tuple == NULL ) error("not enough memory.");
00216 
00217   /* initialize list */
00218   n_tuple->size = 0;
00219   n_tuple->max_size = 1;
00220   n_tuple->dim = dim;
00221 
00222   /* get memory for tuples */
00223   n_tuple->values = (double *) malloc( dim*n_tuple->max_size * sizeof(double) );
00224   if( n_tuple->values == NULL ) error("not enough memory.");
00225 
00226   return n_tuple;
00227 }

Here is the call graph for this function:


Generated on Fri Dec 3 10:18:48 2010 for LSD by doxygen 1.3.4