Algo Name: Detecting Elongated Shape in 2D Image by Convolution with Directed Lines

Question

I am detecting a shape with roughly known orientation (obtained by using Hough line transform) in thresholded binary image by convolving the image with line with that orientation, and counting the ratio of pixels which match; this line is swept across the image, and lines which have hit ratio higher than some threshold (like 0.9) are considered belonging to the object completely.

The motivation is not only to remove holes but also discontinuities across the object; how a hole is removed is shown in the image, where grey line parts are not-matching and red are matching; blue lines are from Hough transform:

This routine was found by intuition and I wonder whether there is some name for it, or perhaps a more sophisticated algorithm based on similar idea. In that case I could use an optimized implementation instead of the hand-written code (I am using python, OpenCV and scikit-image).

Answer 1

What you are essentially doing is a matched filter. However, thanks to Hough transform, your filter (line) is oriented and therefore I would call it an oriented matched filter. For generating the Bresenham line and sampling the pixels you might want the use the OpenCV line iterator. The simple usage would be similar to:

cv::LineIterator it(image, pt1, pt2, 8);
std::vector<cv::Vec3b> buf(it.count);
std::vector<cv::Point> points(it.count);

for(int i = 0; i < it.count; i++, ++it)
{
    buf[i] = *(const cv::Vec3b)*it;
    points[i] = it.pos();
}

The hole detection part can also be implemented using convolutions as follows:

1. Convolve the image with a horizontal convolution kernel composed of the oriented line. Use filter2D.
2. Threhsold the result to identify the areas with holes (use threshold).
3. Perform a blob-filtering and select the desired hole.

Even though I think that this approach is really valid and would work fine in many cases, the typical blob-person would approach the problem differently: First identify the large connected components in the image and filter out the rest. Within that single large component, perform a morphological hole filling. This is a pretty standard pipeline, and with that method, you will be able to find more tools (blob analysis) to help you. For example OpenCV methods such as findContours, drawContours or morphologyEx come handy.

Finally, if you know the shape of the hole, you might benefit from e.g. ellipse detection to directly find it.

Hope these help.