Straight line detection

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

  1. PyPK

    PyPK Guest

    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
    #1
    1. Advertising

  2. PyPK

    Tim Roberts Guest

    "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
    #2
    1. Advertising

  3. PyPK

    Juho Schultz Guest

    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
    #3
  4. PyPK

    Nigel Rowe Guest

    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
    #4
    1. Advertising

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.
Similar Threads
  1. Beza
    Replies:
    2
    Views:
    420
    Kevin Spencer
    Jun 27, 2003
  2. Jordan
    Replies:
    2
    Views:
    2,539
    Jordan
    Feb 10, 2004
  3. Joe Coppola

    Straight ASP problem

    Joe Coppola, Jun 14, 2004, in forum: ASP .Net
    Replies:
    2
    Views:
    432
    Joe Coppola
    Jun 14, 2004
  4. Sandy

    Treeview displaying as straight line of text

    Sandy, Oct 19, 2003, in forum: ASP .Net Web Controls
    Replies:
    6
    Views:
    386
  5. Alf P. Steinbach
    Replies:
    6
    Views:
    199
Loading...

Share This Page