Pruning short line segments from edge detector output?

Question

I am looking for an algorithm to prune short line segments from the output of an edge detector. As can be seen in the image (and link) below, there are several small edges detected that aren't "long" lines. Ideally I'd like just the 4 sides of the quadrangle to show up after processing, but if there are a couple of stray lines, it won't be a big deal... Any suggestions?

Image Link

Answer 1

Before finding the edges pre-process the image with an open or close operation (or both), that is, erode followed by dilate, or dilate followed by erode. this should remove the smaller objects but leave the larger ones roughly the same.

I've looked for online examples, and the best I could find was on page 41 of this PDF.

Answer 2

I doubt that this can be done with a simple local operation. Look at the rectangle you want to keep - there are several gaps, hence performing a local operation to remove short line segments would probably heavily reduce the quality of the desired output.

In consequence I would try to detect the rectangle as important content by closing the gaps, fitting a polygon, or something like that, and then in a second step discard the remaining unimportant content. May be the Hough transform could help.

UPDATE

I just used this sample application using a Kernel Hough Transform with your sample image and got four nice lines fitting your rectangle.

Answer 3

In case somebody steps on this thread, OpenCV 2.x brings an example named squares.cpp that basically nails this task.

I made a slight modification to the application to improve the detection of the quadrangle

Code:

#include "highgui.h"
#include "cv.h"

#include <iostream>
#include <math.h>
#include <string.h>

using namespace cv;
using namespace std;

void help()
{
        cout <<
        "\nA program using pyramid scaling, Canny, contours, contour simpification and\n"
        "memory storage (it's got it all folks) to find\n"
        "squares in a list of images pic1-6.png\n"
        "Returns sequence of squares detected on the image.\n"
        "the sequence is stored in the specified memory storage\n"
        "Call:\n"
        "./squares\n"
    "Using OpenCV version %s\n" << CV_VERSION << "\n" << endl;
}

int thresh = 70, N = 2; 
const char* wndname = "Square Detection Demonized";

// helper function:
// finds a cosine of angle between vectors
// from pt0->pt1 and from pt0->pt2
double angle( Point pt1, Point pt2, Point pt0 )
{
    double dx1 = pt1.x - pt0.x;
    double dy1 = pt1.y - pt0.y;
    double dx2 = pt2.x - pt0.x;
    double dy2 = pt2.y - pt0.y;
    return (dx1*dx2 + dy1*dy2)/sqrt((dx1*dx1 + dy1*dy1)*(dx2*dx2 + dy2*dy2) + 1e-10);
}

// returns sequence of squares detected on the image.
// the sequence is stored in the specified memory storage
void findSquares( const Mat& image, vector<vector<Point> >& squares )
{
    squares.clear();

    Mat pyr, timg, gray0(image.size(), CV_8U), gray;

    // karlphillip: dilate the image so this technique can detect the white square,
    Mat out(image);
    dilate(out, out, Mat(), Point(-1,-1));
    // then blur it so that the ocean/sea become one big segment to avoid detecting them as 2 big squares.
    medianBlur(out, out, 3);

    // down-scale and upscale the image to filter out the noise
    pyrDown(out, pyr, Size(out.cols/2, out.rows/2));
    pyrUp(pyr, timg, out.size());
    vector<vector<Point> > contours;

    // find squares only in the first color plane
    for( int c = 0; c < 1; c++ ) // was: c < 3
    {
        int ch[] = {c, 0};
        mixChannels(&timg, 1, &gray0, 1, ch, 1);

        // try several threshold levels
        for( int l = 0; l < N; l++ )
        {
            // hack: use Canny instead of zero threshold level.
            // Canny helps to catch squares with gradient shading
            if( l == 0 )
            {
                // apply Canny. Take the upper threshold from slider
                // and set the lower to 0 (which forces edges merging)
                Canny(gray0, gray, 0, thresh, 5);
                // dilate canny output to remove potential
                // holes between edge segments
                dilate(gray, gray, Mat(), Point(-1,-1));
            }
            else
            {
                // apply threshold if l!=0:
                //     tgray(x,y) = gray(x,y) < (l+1)*255/N ? 255 : 0
                gray = gray0 >= (l+1)*255/N;
            }

            // find contours and store them all as a list
            findContours(gray, contours, CV_RETR_LIST, CV_CHAIN_APPROX_SIMPLE);

            vector<Point> approx;

            // test each contour
            for( size_t i = 0; i < contours.size(); i++ )
            {
                // approximate contour with accuracy proportional
                // to the contour perimeter
                approxPolyDP(Mat(contours[i]), approx, arcLength(Mat(contours[i]), true)*0.02, true);

                // square contours should have 4 vertices after approximation
                // relatively large area (to filter out noisy contours)
                // and be convex.
                // Note: absolute value of an area is used because
                // area may be positive or negative - in accordance with the
                // contour orientation
                if( approx.size() == 4 &&
                    fabs(contourArea(Mat(approx))) > 1000 &&
                    isContourConvex(Mat(approx)) )
                {
                    double maxCosine = 0;

                    for( int j = 2; j < 5; j++ )
                    {
                        // find the maximum cosine of the angle between joint edges
                        double cosine = fabs(angle(approx[j%4], approx[j-2], approx[j-1]));
                        maxCosine = MAX(maxCosine, cosine);
                    }

                    // if cosines of all angles are small
                    // (all angles are ~90 degree) then write quandrange
                    // vertices to resultant sequence
                    if( maxCosine < 0.3 )
                        squares.push_back(approx);
                }
            }
        }
    }
}


// the function draws all the squares in the image
void drawSquares( Mat& image, const vector<vector<Point> >& squares )
{
    for( size_t i = 1; i < squares.size(); i++ )
    {
        const Point* p = &squares[i][0];
        int n = (int)squares[i].size();
        polylines(image, &p, &n, 1, true, Scalar(0,255,0), 3, CV_AA);
    }

    imshow(wndname, image);
}


int main(int argc, char** argv)
{
    if (argc < 2)
    {
        cout << "Usage: ./program <file>" << endl;
        return -1;
    }

    static const char* names[] = { argv[1], 0 };

    help();
    namedWindow( wndname, 1 );
    vector<vector<Point> > squares;

    for( int i = 0; names[i] != 0; i++ )
    {
        Mat image = imread(names[i], 1);
        if( image.empty() )
        {
            cout << "Couldn't load " << names[i] << endl;
            continue;
        }

        findSquares(image, squares);
        drawSquares(image, squares);
        imwrite("out.jpg", image);

        int c = waitKey();
        if( (char)c == 27 )
            break;
    }

    return 0;
}

Answer 4

The Hough Transform can be a very expensive operation.

An alternative that may work well in your case is the following:

1. run 2 mathematical morphology operations called an image close (http://homepages.inf.ed.ac.uk/rbf/HIPR2/close.htm) with a horizontal and vertical line (of a given length determined from testing) structuring element respectively. The point of this is to close all gaps in the large rectangle.

2. run connected component analysis. If you have done the morphology effectively, the large rectangle will come out as one connected component. It then only remains iterating through all the connected components and picking out the most likely candidate that should be the large rectangle.

Answer 5

Perhaps finding the connected components, then removing components with less than X pixels (empirically determined), followed by dilation along horizontal/vertical lines to reconnect the gaps within the rectangle

Answer 6

It's possible to follow two main techniques:

1. Vector based operation: map your pixel islands into clusters (blob, voronoi zones, whatever). Then apply some heuristics to rectify the segments, like Teh-Chin chain approximation algorithm, and make your pruning upon vectorial elements (start, endpoint, length, orientation and so on).

2. Set based operation: cluster your data (as above). For every cluster, compute principal components and detect lines from circles or any other shape by looking for clusters showing only 1 significative eigenvalue (or 2 if you look for "fat" segments, that could resemble to ellipses). Check eigenvectors associated with eigenvalues to have information about orientation of the blobs, and make your choice.

Both ways could be easily explored with OpenCV (the former, indeed, falls under "Contour analysis" category of algos).

Answer 7

Here is a simple morphological filtering solution following the lines of @Tom10:

Solution in matlab:

se1 = strel('line',5,180);            % linear horizontal structuring element 
se2 = strel('line',5,90);             % linear vertical structuring element 
I = rgb2gray(imread('test.jpg'))>80;  % threshold (since i had a grayscale version of the image)
Idil = imdilate(imdilate(I,se1),se2); % dilate contours so that they connect
Idil_area = bwareaopen(Idil,1200);    % area filter them to remove the small components

The idea is to basically connect the horizontal contours to make a large component and filter by an area opening filter later on to obtain the rectangle.

Results: