Hough transform fails to detect lines under certain angles

[kamirr]

I noticed that when a line points under a certain range of angles (between 90° and 135° when measured from the top of the x-axis), the imageproc's implementation of the Hough transform won't detect it.

To give an example, consider those two images:

The first one should result in the almost exact same set of lines as the second one, just with negated angles. Interestingly, that's not the case. Those are my results:

Code:

extern crate imageproc;
extern crate image;

fn main() {
    let args: Vec<String> = std::env::args().collect();
    assert_eq!(args.len(), 2, "Usage: <progname> <edges image>");

    let edges = match image::open(&args[1]).unwrap() {
        image::DynamicImage::ImageRgb8(img) => img,
        _ => panic!("Passed file should be RGB")
    };

    let grayscale = image::GrayImage::from_fn(edges.width(), edges.height(), |x, y| {
        let px = edges.get_pixel(x, y);
        let r = px.data[0] as f64;
        let g = px.data[1] as f64;
        let b = px.data[2] as f64;

        image::Luma{ data: [(0.299 * r*r + 0.587 * g*g + 0.114 * b*b).sqrt() as u8] }
    });

    let vote_threshold = 180;
    let lines = imageproc::hough::detect_lines(&grayscale, imageproc::hough::LineDetectionOptions {
        vote_threshold,
        suppression_radius: 0
    });

    imageproc::hough::draw_polar_lines(
        &edges,
        &lines,
        image::Rgb {
            data: [255, 0, 255]
        }
    ).save("res.png").unwrap();
}

[kamirr]

I've looked into the implementation of detect_lines and managed to get it to work:

/// Detects lines in a binary input image using the Hough transform.
///
/// Points are considered to be in the foreground (and thus vote for lines)
/// if their intensity is non-zero.
///
/// See ./examples/hough.rs for example usage.
pub fn detect_lines(image: &GrayImage, options: LineDetectionOptions) -> Vec<PolarLine> {
    let (width, height) = image.dimensions();

    // The maximum possible radius is the diagonal of the image.
    let rmax = ((width * width + height * height) as f64).sqrt() as i32;

    // Measure angles in degrees, and use bins of width 1 pixel and height 1 degree.
    let mut acc: ImageBuffer<Luma<u32>, Vec<u32>> = ImageBuffer::new(rmax as u32, 360u32);

    let cos_lut: Vec<f32> = (0..360u32).map(|m| degrees_to_radians(m).cos()).collect();
    let sin_lut: Vec<f32> = (0..360u32).map(|m| degrees_to_radians(m).sin()).collect();

    for y in 0..height {
        for x in 0..width {
            let p = unsafe { image.unsafe_get_pixel(x, y)[0] };

            if p > 0 {
                for m in 0..360u32 {
                    let fy = y as f32;
                    let fx = x as f32;

                    let r = unsafe {
                        (fx * *cos_lut.get_unchecked(m as usize) +
                             fy * *sin_lut.get_unchecked(m as usize)) as i32
                    };

                    if r < rmax && r >= 0 {
                        unsafe {
                            let vote_incr = acc.unsafe_get_pixel(r as u32, m)[0] + 1;
                            acc.unsafe_put_pixel(r as u32, m, Luma([vote_incr]));
                        }
                    }
                }
            }
        }
    }

    let acc_sup = suppress_non_maximum(&acc, options.suppression_radius);

    let mut lines = Vec::new();

    for m in 0..acc_sup.height() {
        for r in 0..acc_sup.width() {
            let votes = unsafe { acc_sup.unsafe_get_pixel(r, m)[0] };
            if votes >= options.vote_threshold {
                let line = PolarLine {
                    r: r as f32,
                    angle_in_degrees: m,
                };
                lines.push(line);
            }
        }
    }

    lines
}

The only thing I did was to replace every occurrence of 180 with 360.

It's likely a suboptimal solution (completely outside of my area of expertise, so I don't really know), but I guess it might help a little.

[HeroicKatora]

You are right, looks broken and I might have spotted where in the code:

https://github.com/PistonDevelopers/imageproc/blob/master/src/hough.rs#L59-L62

Here we calculate the displacement-to-line by the dot product of the point and the line normal. However, that might be negative. In fact, only half of all lines (0° - 90° angle) will have positive displacements for all image pixels. Other angles only have positive displacements for a partial amount of pixels, i.e. the problem appears for a superset of what is noted in the initial observation of the bug report.

Hence, the comparison should take into account the other possibility in sign: https://github.com/PistonDevelopers/imageproc/blob/b8296fc3a3f77bf76ded4de7a0fbe42a2969cd09/src/hough.rs#L64

Probably, the temporary hough transformed image should extend from -rmax to rmax in the x direction. The problem with the other immediate fix of extending to 360° is that non-maximum suppression doesn't work properly for the same line with inverted normal.

Additional critique of the code: Why so many unsafes? Replace for m in 0..180u32 with for (m, clut, slut) in cos_lut.iter().zip(sin_lut.iter()).enumerate() for example to avoid the unsafe index access to the table. And all of the multiplications on integers need to occur instead after casting to floating values, else overflows can potentially ruin your day.

[HeroicKatora]

cc @theotherphil

[theotherphil]

Thanks. I've made some changes in https://github.com/PistonDevelopers/imageproc/pull/282 to address this, but I'll not merge until I've done a bit more cleaning up and testing.

[theotherphil]

@kamirr I've just published 0.17 with a fix. Please try it and confirm (or deny!) that this has fixed the problem.

[kamirr]

Everything's ok, my program works flawlessly after the update.