Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > Straight line detection

Reply
Thread Tools

Straight line detection

 
 
PyPK
Guest
Posts: n/a
 
      09-28-2005
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.

 
Reply With Quote
 
 
 
 
Tim Roberts
Guest
Posts: n/a
 
      09-30-2005
"PyPK" <(E-Mail Removed)> 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, http://www.velocityreviews.com/forums/(E-Mail Removed)
Providenza & Boekelheide, Inc.
 
Reply With Quote
 
 
 
 
Juho Schultz
Guest
Posts: n/a
 
      09-30-2005
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.
 
Reply With Quote
 
Nigel Rowe
Guest
Posts: n/a
 
      10-15-2005
Tim Roberts wrote:

> "PyPK" <(E-Mail Removed)> 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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Google user site navigation, by design, inhibits straight line support to Users. JAM Computer Support 6 05-21-2007 11:14 AM
Straight ASP problem Joe Coppola ASP .Net 2 06-14-2004 11:58 AM
Data Binding - using inline code vs. functions vs. straight binding Jordan ASP .Net 2 02-10-2004 08:32 PM
Treeview displaying as straight line of text Sandy ASP .Net Web Controls 6 10-24-2003 09:42 PM
Send Records Straight To DataTable Beza ASP .Net 2 06-27-2003 02:40 PM



Advertisments