OpenCV C++ how to know the number of contours per row for sorting?

Question

I have a binary image: In this image I can easily sort the contours that I found from top to bottom and from left to right using the overloaded std::sort.

I first sort from top to bottom via:

sort(contours.begin(), contours.end(), top_to_bottom_contour_sorter());

Then I sort from left to right by:

for (int i = 0; i < contours.size(); i = i + no_of_contours_horizontally)
    {
        sort(i, i + no_of_contours_horizontally, left_to_right_contour_sorter);
    }

Where top_to_bottom and left_to_right are separate functions that I pass to the sort function. And no_of_contours_horizontally with respect to the first image is three (3).

However this only works if I know the number of contours horizontally. If the image I am using will have varying number of contours horizontally like in this image. contours_sample. The program fails. I could brute force and define for a specific index to change the no of contours found. However, it would limit the program to operate on a specific input instead of being flexible. I am thinking of creating rects or lines that I can overlay on top of the image and with that count the number of contours inside so I can get a value of the number of horizontal contours. If there is a more elegant solution I would appreciate it.

Here are my sorting functions

bool top_to_bottom_contour_sorter(const std::vector<Point> &lhs, const std::vector<Point> &rhs)
{
    Rect rectLhs = boundingRect(Mat(lhs));
    Rect rectRhs = boundingRect(Mat(rhs));

    return rectLhs.y < rectRhs.y;
}

bool left_to_right_contour_sorter(const std::vector<Point> &lhs, const std::vector<Point> &rhs)
{
    Rect rectLhs = boundingRect(Mat(lhs));
    Rect rectRhs = boundingRect(Mat(rhs));

    return rectLhs.x < rectRhs.x;
}

EDIT Here are my current outputs and desired output for each image. Using the first image and my current working code. Current_Output

My desired output for the second image. Desired_Output

Answer 1

I guess, your only problem was not to respect equality for one of the coordinates!?

Here we go:

// Custom sorter.
bool sortContour(std::vector<cv::Point> a, std::vector<cv::Point> b)
{
    cv::Rect rectA = cv::boundingRect(a);
    cv::Rect rectB = cv::boundingRect(b);

    if (rectA.y == rectB.y)
        return (rectA.x < rectB.x);

    return (rectA.y < rectB.y);
}

int main()
{
    // Load image.
    cv::Mat image = cv::imread("contours.jpg", cv::IMREAD_GRAYSCALE);

    // There are some artifacts in the JPG...
    cv::threshold(image, image, 128, 255, cv::THRESH_BINARY);

    // Find contours.
    std::vector<std::vector<cv::Point>> contours;
    std::vector<cv::Vec4i> hierarchy;
    cv::findContours(image, contours, hierarchy, cv::RETR_EXTERNAL, cv::CHAIN_APPROX_NONE);

    // Output unsorted contours.
    cv::Mat imageUnsorted = image.clone();
    for (int i = 0; i < contours.size(); i++)
    {
        cv::Rect rect = cv::boundingRect(contours[i]);
        cv::putText(imageUnsorted, std::to_string(i), cv::Point(rect.x - 10, rect.y - 10), cv::FONT_HERSHEY_COMPLEX, 0.5, cv::Scalar(255));
    }
    cv::imwrite("unsorted.png", imageUnsorted);

    // Sort using custom sorter.
    std::sort(contours.begin(), contours.end(), sortContour);

    // Output sorted contours.
    cv::Mat imageSorted = image.clone();
    for (int i = 0; i < contours.size(); i++)
    {
        cv::Rect rect = cv::boundingRect(contours[i]);
        cv::putText(imageSorted, std::to_string(i), cv::Point(rect.x - 10, rect.y - 10), cv::FONT_HERSHEY_COMPLEX, 0.5, cv::Scalar(255));
    }
    cv::imwrite("sorted.png", imageSorted);
}

The unsorted contours:

The sorted contours:

As you can see, one could also just inverse the original order, since cv::findContours just goes in the opposite direction(s). ;-)

One big caveat: If the scan (or however you obtain the surveys) is even slightly rotated counterclockwise, this routine will fail. Therefore, the angle of the whole scan (or...) should be checked beforehand.

Answer 2

A simple practical solution is to sort by

y*100 + x

Something more sophisticated that will work also in case of rotated input is

1. Pick the minimum distance between two blobs
2. Let's call the vector connecting these two dots (dx, dy)
3. Sort based on (x*dx + y*dy)*100 + (x*dy - y*dx)

The output will be in a "grid" order (may be one that you want or one rotated by 90 degrees, but with rotated input the problem is ill-posed, you should choose between the two using some rule).