Straight line detection

[Juho Schultz]

PyPK wrote:
> Does anyone know of a simple implementation of a straight line
> detection algorithm something like hough or anything simpler.So
> something like if we have a 2D arary of pixel elements representing a
> particular Image. How can we identify lines in this Image.
> for example:
> 
> ary =
> [[1,1,1,1,1],
>  [1,1,0,0,0],
>  [1,0,1,0,0],
>  [1,0,0,1,0],
>  [1,0,0,0,1]]
> So if 'ary' represents pxl of an image which has a horizontal line(row
> 0),a vertical line(col 0) and a diagonal line(diagonal of ary). then
> basically I want identify any horizontal or vertical or diagonal line
> anywhere in the pxl array.
> 
> Thanks.
> 

I would recommend using a module for computing, my choice would be
numarray: www.stsci.edu/resources/software_hardware/numarray
You could even write your own version of hough, should not be too complex.
A fwee things you need to consider:


1) Are all the lines through the image, or would a row with 
[0,0,1 ...(a few dozen ones in here) ... 1,0] be a line?

2) Do you also need edge detection? Then you might need to convolve
the image with a Laplacian or something like that, e.g.
new[i,j] = (4*old[i,j])-old[i-1,j]-old[i+1,j]-old[i,j-1]-old[i,j+1]

3) How "full" are the images?
It is much easier if only a small fraction of your image is lines,
in your example more than half of image pixels are lines.

4) How big images are you processing? I always have at least
one million pixels, so the rest may not work for small images.

To do some quicklook checks you can of course go through each row/column
and check if the values are different enough, something like

mat = numarray.array(ima)
x = mat.mean()
dx = mat.stddev()

then check if some rows are different from others, maybe
(mat[:,i].mean() > (x + N*dx)) for "white" lines or
(mat[:,i].mean() < (x - N*dx))) for "black" lines
you probably need do a few tests to get a good value of N.

repeat for columns (mat[j,:]) and diagonals:
numarray.diagonal(mat,o) where
o is offset from mat[0,0]

and if you need non-diagonal elements, say
ima = [[1 0 0 0 0]
       [0 0 1 0 0]
       [0 0 0 0 1]]
would contain a line of ones, then

vect = ima.flat

gives the image as a rank-1 array and you can then take strides
(every nth element) just like with normal lists, array[a:b:n]
takes every nth element in array[a:b], so vect[::7] would be [1 1 1]

I hope this helps a bit.