Line segment detection

linear-time Line Segment Detector giving subpixel accurate results

History

Research paper

FAQ

What is it?

image processing algorithm.

How cool is it?

Moderate.

Competitors?

lots,

Where is it?

https://github.com/kazuho/picoev/

When to use it?

When you want to detect lines and don't want to use machine learning, opencv, vigra etc.

Is it dead?

Development is stopped,

How to use it

Download

file: 1_download.sh

#!/bin/bash

mkdir -p tmp
cd tmp
wget -q http://www.ipol.im/pub/art/2012/gjmr-lsd/lsd_1.6.zip
unzip lsd_1.6.zip
cd lsd_1.6
cc -O3 -c -o lsd.o lsd.c
ar cru liblsd.a lsd.o
ranlib liblsd.a

Init

file: main.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#include "lsd.h"

#ifndef FALSE
#define FALSE 0
#endif /* !FALSE */

#ifndef TRUE
#define TRUE 1
#endif /* !TRUE */

void error(const char* msg) {
    fprintf(stderr, "%s", msg);
}

static int get_num(FILE * f) {
    int num,c;

    while( isspace( c = getc( f ) ) );
    if ( !isdigit( c ) ) {
        error("Error: corrupted PGM file.");
    }
    num = c - '0';
    while( isdigit( c = getc( f ) ) ) {
        num = 10 * num + c - '0';
    }
    if ( c != EOF && ungetc( c, f ) == EOF ) {
        error("Error: unable to 'ungetc' while reading PGM file.");
    }

    return num;
}

static void skip_whites_and_comments( FILE * f ) {
    int c;

    do {
        while(isspace(c=getc(f)));
        if(c=='#') {
            while( c!='\n' && c!='\r' && c!=EOF ) {
                c=getc(f);
            }
        }
    }
    while( c == '#' || isspace( c ) );
    if( c != EOF && ungetc(c,f) == EOF ) {
        error("Error: unable to 'ungetc' while reading PGM file.");
    }
}

static void write_pgm_image_int (int *image, int xsize, int ysize, char *name) {
    FILE *f;
    int x, y, n, v, max, min;

    if (image == NULL || xsize <= 0 || ysize <= 0) {
        error ("Error: invalid input image to write_pgm_image_int.");
    }

    max = min = 0;
    for (y = 0; y < ysize; y++) {
        for (x = 0; x < xsize; x++) {
            v = image[x + y * xsize];
            if (v > max) {
                max = v;
            }
            if (v < min) {
                min = v;
            }
        }
    }
    if (min < 0) {
        fprintf( stderr, "Warning: write_pgm_image_int: negative values in '%s'.\n", name );
    }
    if (max > 65535) {
        fprintf( stderr, "Warning: write_pgm_image_int: values exceeding 65535 in '%s'.\n", name );
    }

    if ( strcmp( name, "-" ) == 0 ) {
        f = stdout;
    } else{
        f = fopen(name, "w");
    }
    if ( f == NULL ) {
        error ("Error: unable to open output image file." );
    }

    /* write header */
    fprintf(f, "P2\n" );
    fprintf(f, "%d %d\n", xsize, ysize );
    fprintf(f, "%d\n", max );

    /* write data */
    for ( n = 0, y = 0; y < ysize; y++ ) {
        for ( x = 0; x < xsize; x++ ) {
            fprintf( f, "%d ", image[x + y * xsize] );
            if ( ++n == 8 ) {
                /* lines should not be longer than 70 characters	*/
                fprintf( f, "\n" );
                n = 0;
            }
        }
    }

    /* close file if needed */
    if ( f != stdout && fclose ( f ) == EOF ) {
        error ("Error: unable to close file while writing PGM file.");
    }
}

static double * read_pgm_image_double(int * X, int * Y, char * name) {
    FILE * f;
    int c,bin;
    int xsize,ysize,depth,x,y;
    double * image;

    if ( strcmp( name,"-") == 0 ) {
        f = stdin;
    } else {
        f = fopen( name, "rb" );
    }
    if ( f == NULL ) {
        error("Error: unable to open input image file.");
    }

    /* read header */
    if ( getc( f ) != 'P' ) {
        error( "Error: not a PGM file!" );
    }
    if ( (c=getc( f ) ) == '2' ) {
        bin = FALSE;
    } else if ( c == '5' ) {
        bin = TRUE;
    } else {
        error( "Error: not a PGM file!" );
    }
    skip_whites_and_comments( f );
    xsize = get_num( f );				/* X size */
    if ( xsize <= 0 ) {
        error("Error: X size <= 0, invalid PGM file\n");
    }
    skip_whites_and_comments( f );
    ysize = get_num( f );				/* Y size */
    if ( ysize <= 0 ) {
        error( "Error: Y size <=0, invalid PGM file\n" );
    }
    skip_whites_and_comments( f );
    depth = get_num(f);				/* depth */
    if ( depth <= 0 ) {
        fprintf( stderr,"Warning: depth<=0, probably invalid PGM file\n" );
    }
    /* white before data */
    if ( ! isspace (c = getc( f ) ) ) {
        error("Error: corrupted PGM file.");
    }

    /* get memory */
    image = (double *) calloc( (size_t) (xsize * ysize), sizeof(double) );
    if ( image == NULL ) {
        error( "Error: not enough memory." );
    }

    /* read data */
    for ( y = 0; y < ysize; y++ ) {
        for ( x = 0; x < xsize; x++ ) {
            image[ x + y * xsize ] = bin ? (double) getc( f )
                                         : (double) get_num( f );
        }
    }

    if ( f != stdin && fclose(f) == EOF ) {
        error("Error: unable to close file while reading PGM file.");
    }

    *X = xsize;
    *Y = ysize;

    return image;
}

int main( void ) {
    double *image, *out, *segs;
    int x, y, i, j, n, X, Y, regX, regY, dim = 7;
    double scale = 0.8, sigma_coef = 0.6, quant = 2.0 , ang_th = 22.5, log_eps = 0, density_th = 0.7, n_bins = 1027;

    char *filename = strdup( "input.pgm" );

    image = read_pgm_image_double( &X, &Y, filename );
    if ( image == NULL ) {
        fprintf( stderr, "error: not enough memory\n" );
        exit( EXIT_FAILURE );
    }
    for ( x = 0; x < X; x++ ) {
        for ( y = 0; y < Y; y++ ) {
            image[x + y * X] = x < X / 2 ? 0.0 : 64.0;	/* image( x, y ) */
        }
    }

    printf( "Segments\n" );
    segs = LineSegmentDetection( &n, image, X, Y, scale, sigma_coef,
        quant, ang_th, log_eps, density_th, n_bins, NULL, &regX, &regY );

    for( i = 0; i < n; i++) {
        for( j = 0; j < dim; j++ ) {
            fprintf( stdout, "%f ", segs[i * dim + j]);
        }
        fprintf( stdout,"\n");
    }

    fprintf( stdout, "LSD Call\n" );
    out = lsd( &n, image, X, Y );
    fprintf( stdout, "%d line segments found:\n", n );
    for ( i = 0; i < n; i++) {
        for ( j = 0; j < 7; j++) {
            fprintf( stdout, "%f ", out[7 * i + j] );
        }
        fprintf( stdout, "\n" );
    }

    free( image );
    free( out );
    free( segs );
    free( filename );

    return 0;
}

__**file**: [2_compile.sh](2_compile.sh)__

```bash
#!/bin/bash

clang -c -o ./tmp/main.o main.c -I./tmp/lsd_1.6
clang -o ./tmp/main ./tmp/main.o -L./tmp/lsd_1.6 -llsd -lm

download an image

wget -q -O - http://unsplash.com/photos/RU0KvKLjRSg/download?force=true| convert - input.pgm

That gives us a this input.png file,.

run it

./tmp/main

Unfortunately, this gives the an error, I did not have time to investigate it deeper:

./main: : Unkown error -1732626824

However, the file "lsd_call_example.c" works ok.

Further reading:

We only tipped the top of the iceberg here. There is much more:

The algorithm is described in this paper: http://www.ipol.im/pub/art/2012/gjmr-lsd/

The IPOL Journal website holds lots of information for image processing.