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

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).

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.

• Thanks for a helpful answer. The blob-approach with hole-filling is not useful as sometimes the hole spans the whole width of the object (like crack) thus it appears as two objects rather than one; we tried pre-processing with erosion/dilation but those are suboptimal as they are orientation-agnostic. Aug 21 '17 at 13:11
• Sure, that's true. I like the approach you follow. Aug 21 '17 at 15:01