Straight line detection

[PyPK]

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.

[Tim Roberts]

"PyPK" <su*******@gmail.com> 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.

If all you want is horizontal, vertical, or 45 degree diagonal, it's pretty
easy to do that just be checking all of the possibilities.

But what if your array is:

[[1,1,1,1,1],
[1,1,1,1,1],
[1,1,1,1,1],
[1,1,1,1,1],
[1,1,1,1,1]]

Would you say there were 12 lines there?
--
- Tim Roberts, ti**@probo.com
Providenza & Boekelheide, Inc.

[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: http://www.stsci.edu/resources/softw...dware/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.

[Nigel Rowe]

Tim Roberts wrote:

"PyPK" <su*******@gmail.com> 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.

If all you want is horizontal, vertical, or 45 degree diagonal, it's
pretty easy to do that just be checking all of the possibilities.

But what if your array is:

[[1,1,1,1,1],
[1,1,1,1,1],
[1,1,1,1,1],
[1,1,1,1,1],
[1,1,1,1,1]]

Would you say there were 12 lines there?

Actually I'd say 24.

5 vertical,
5 horizontal,
7 diagonal downward to the right (lengths 2,3,4,5,4,3,2)
7 diagonal downward to the left (lengths 2,3,4,5,4,3,2)

--
Nigel Rowe
A pox upon the spammers that make me write my address like..
rho (snail) swiftdsl (stop) com (stop) au