# Straight line detection

Discussion in 'Python' started by PyPK, Sep 28, 2005.

1. ### PyPKGuest

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.

PyPK, Sep 28, 2005

2. ### Tim RobertsGuest

"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.

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,
Providenza & Boekelheide, Inc.

Tim Roberts, Sep 30, 2005

3. ### Juho SchultzGuest

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.

Juho Schultz, Sep 30, 2005
4. ### Nigel RoweGuest

Tim Roberts wrote:

> "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.

>
> 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

Nigel Rowe, Oct 15, 2005

## Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.