OpenCV; sort a vector<Rect> and delete certain entries

Question

I have this problem I can't wrap my head around. I am trying to detect and track something in a video. Therefore I use functions like GaussianBlur(), threshold(), findContours(),.

findContours() gives me a contour vector which is later converted into bounding rectangles. So far so good.

What I need now from the vector with the bounding rectangles is that they are sorted by size (area) and contains only rectangles which are not enclosed by another rectangle.

I tried to draw a little sketch for better understanding, click here for image.

So what I am looking for is that #8 is the first entry, followed by #1, #3,.... Entries like #2,#4, #9, #10 and #11 should be deleted.

I understand that vectors are not ideal for sorting and deleting. So I tried to copy the vector into a list like so:

std::list<Rect> sorted_list(boundRect_temp.begin(), boundRect_temp.end());

But now I am not able to access the member variables like area. The thing is that the algorithm shouldn't be too time consuming that's why I am looking for a good solution. Maybe there is a function for that already?

Answer 1

1) Most of the intersections can be filtered if you use findContours() with CV_RETR_EXTERNAL flag. This means that contours that are contained inside other contours won't be returned. Of course this will not prevent all the cases of intersections of bounding boxes but this will considerably improve performance of your post-processing

2) vectors are definitely good for sorting. The code will be short and efficient. And it is better than list anyway since the data will be continuous in the memory.

3) Deleting values from vector one by one is not effective indeed but you don't need to do that. Just create temporary vector that will contain chosen boxes, like this:

vector < Rect > nonIntersect;
for(unsigned int i=0; i < sortedBoxes.size(); i++) {
    bool toAdd = true;
    Point center = (sortedBoxes[i].tl()+sortedBoxes[i].br())*0.5;
    for(unsigned int j=0; j < nonIntersect.size(); j++)
        if (nonIntersect[j].contains(center)) {
            toAdd = false;
            break;
        }
    if (toAdd)
        nonIntersect.push back(sortedBoxes[i]);
 }

This can be done 'inplace' as well but why bother. This memory is ignorable comparing to memory of original image, or memory of contours found by findContours.

Answer 2

apart from what michael burdinov said, here's sorting by area

struct byArea {
    bool operator () (const Rect & a,const Rect & b) {
         return a.width*a.height < b.width*b.height ;
    }
};

vector<Rect> rects;
std::sort(rects.begin(), rects.end(), byArea());