Example for working with hough lines output

[xavriley]

I've been doing some work with hough line transforms in ImageMagick to try to identify and segment tables in scanned documents. This is working great so far with the following output:

You can see the red lines where the hough transform has been applied to the original image.

In the interests of doing this on a larger scale in a more efficient way I'd love to benchmark this against an equivalent vips implementation, but I'm having a hard time working out what to do with the output of the hough_lines command. So far I have:

> require 'vips'
# import the image shown above
> im = Vips::Image.new_from_file "/Users/xriley/Dropbox (Personal)/Public/29_hough.png"
# change the colour space to black and white for the hough_lines method
> im = im.colourspace(:'b-w')
=> #<Image 2359x1709 uchar, 1 bands, b-w>
> im = im.hough_line
=> #<Image 256x256 uint, 1 bands, matrix>

At this point I'd like to use the output from hough_line (assuming it has found the lines) to draw, say, 5px wide red lines onto the original image so that I can validate it. After that point I'd be aiming to segment the image based on those coordinates.

If there's any existing documentation or pointers you could offer I'd really appreciate it. The final aim with this is to make some open data relating to company ownership but that's a long way off yet! Thanks in advance.

p.s. my (very bad) image magick code is here for reference https://gist.github.com/xavriley/cda9ddd393ad43676b64

[jcupitt]

Hello, do you have the sample image anywhere? I had a look on the gist, but the dropbox link there is 404-ing for me.

[jcupitt]

The docs for hough_line are here, in case you missed them:

http://jcupitt.github.io/libvips/API/current/libvips-arithmetic.html#vips-hough-line

I'll try making a sample program.

[jcupitt]

Here's a nip2 workspace which demonstrates the libvips hough line transform. You can drag the sliders in the first column to plot a line, then read out the detected line from the last column.

https://gist.github.com/jcupitt/4e1593641a24655031080dbad52190df

[xavriley]

Thanks for this. I managed to get a little further with the example and I've fixed the link to the example image which is here: https://dl.dropboxusercontent.com/s/qiayht1abl3ctyv/29_hough.png

Running the following example program:

require 'vips'

oim = Vips::Image.new_from_file "/Users/xriley/Dropbox (Personal)/Public/29_hough.png"
im = oim.colourspace(:'b-w')
im.hough_line(width: 2359, height: 1709).write_to_file("/tmp/hough.jpg")

I get the following output image:

Where I'm a little confused is that I'd like to extract multiple lines from the output. A few questions I had while working on this:

1. Do the width: and height: arguments to hough_line need to mirror the size of the input image? Or does "parameter size" correspond to the number of lines that will be calculated?

2. For the pixel values, I can extract these as follows (using a small parameter space as an example)

im.hough_line(width: 4, height: 4).write_to_memory.unpack('I_*')
=> [407, 712, 407, 712, 351, 549, 0, 0, 351, 459, 0, 0, 699, 344, 0, 0]

For that output, is there an easy way of saying which of those is "line angle" and which is "distance from the origin"?

3. I notice in the workspace that you were doing something with maxpos and re (90 - 360 * re C2 / C1.width). I can see that I can call .maxpos on the output image of hough_lines but it's not immediately obvious if this is the same maxpos that you were using in the workspace.

I'm very sorry to take your time with this - feel free to close this out if it's too much trouble.

[jcupitt]

Hi, don't worry, discussing Hough transforms is much more fun than the work I ought to be doing.

1. The parameter space size sets the resolution of the line determination. So if it's 360 pixels across (for example), it'll detect lines to within one degree.

2. The numbers there are "votes", meaning that it saw 712 votes in pixel (1, 0). The coordinates give the angle and distance, so that's 712 votes for horizontal-ish lines in the top 1/4 of the image.

3. You need to search the output of hough for peaks, then pick all the peaks which correspond to lines of about the length you are looking for. You only need to search the roughly horizontal and roughly vertical parts of the transform, so the area around 0 / 90 / 180 / 270 degrees.

I wouldn't use PNG: lots of your counts will be truncated at 255 (or 65535). Use a smaller param space and save as TIFF (it supports int32 pixels).

I'd use nip2 for looking at the results: it can display image with huge ranges. Doubleclick on an image to open a view window, then View / Toolbar / Display control to add some sliders. Drag the left slider to set the view scale. Click on the settings button next to the left slider to turn on false colour: it'll make seeing peaks easy.

[jcupitt]

Do you have the sample image without the red lines?

[xavriley]

Apologies for the delayed response. This one is likely to take me a while to work on!

GitHub won't let me upload a tif of the original directly but it's on Dropbox here: https://www.dropbox.com/s/r99wbjq1iym8zye/output2014-000.tif?dl=0

[jcupitt]

I've been looking at this again. I've improved the hough_line operator and I'm now adding a canny edge detector. Hopefully the two of them plus a bit of ruby should do the job.