Эффективный способ комбинирования пересекающихся ограничивающих прямоугольников

Ответ 1

Чтобы выполнить то, что вы хотите, мы будем использовать findContours. Ключевым моментом здесь является понимание того, как он работает, если mode установлен на CV_RETR_TREE. В этом случае hierarchy строится таким образом, что каждый четный уровень глубины содержит внешние контуры, а нечетные уровни глубины содержат внутренние контуры. Здесь нам нужно пройти по дереву иерархии, где будут отображаться контуры, связанные с четными уровнями глубины.

Сначала мы найдем контуры изображения, называемого original

typedef std::vector<std::vector<cv::Point> > Contours;
typedef std::vector<cv::Vec4i> Hierarchy;

Contours contours;
Hierarchy hierarchy;
cv::findContours(original, contours, hierarchy, CV_RETR_TREE, CV_CHAIN_APPROX_NONE);

Для печати внешних контуров на изображении под названием processed нам нужна рекурсивная функция.

void printExternalContours(cv::Mat img, Contours const& contours, Hierarchy const& hierarchy, int const idx)
{
    //for every contour of the same hierarchy level
    for(int i = idx; i >= 0; i = hierarchy[i][0])
    {
        //print it
        cv::drawContours(img, contours, i, cv::Scalar(255));

        //for every of its internal contours
        for(int j = hierarchy[i][2]; j >= 0; j = hierarchy[j][0])
        {
            //recursively print the external contours of its children
            printExternalContours(img, contours, hierarchy, hierarchy[j][2]);
        }
    }
}

printExternalContours(processed, contours, hierarchy, 0);

Результат показан ниже, где original и processed отображаются бок о бок.

Если вам абсолютно нужны прямоугольные фигуры, вам просто нужно использовать boundingRect, чтобы получить минимальный прямоугольник с прямоугольником, заданный набором точек (каждый один контур в этом случае) и используйте rectangle для чертежа. Другими словами, замените

cv::drawContours(img, contours, i, cv::Scalar(255));

по

cv::rectangle(img, cv::boundingRect(contours[i]), cv::Scalar(255));

findContours ожидает одно 8-битное изображение, кроме того, вы можете либо сделать серое изображение с ваших оригиналов, а затем порог его, чтобы получить идеальный черный фон или, возможно, достаточно использовать красный канал в вашем случае, просто убедитесь, что фон совершенно черный.

Что касается сложности findContours, я не могу утверждать, что он лучше, чем O (N ^ 2), и я не нашел никаких данных об этом после быстрого поиска в Google, но я уверен, что OpenCV реализует наиболее известный алгоритм.

Ответ 2

ОБНОВЛЕНИЕ: Я неправильно понял вопрос раньше. Мы не хотим удалять прямоугольники, которые полностью внутри других. Мы хотим заменить только пересекающиеся прямоугольники. Поэтому для первого случая мы ничего не должны делать.

Новый api (2.4.9) поддерживает и и | операторы.

Из opencv doc:

• rect = rect1 и rect2 (прямоугольное пересечение)
• rect = rect1 | rect2 (минимальный прямоугольник области, содержащий rect2 и rect3)

Он также поддерживает сравнение равенства (==)

• rect == rect1

Так что сейчас очень легко выполнить задачу. Для каждой пары прямоугольников rect1 и rect2,

if((rect1 & rect2) == rect1) ... // rect1 is completely inside rect2; do nothing.
else if((rect1 & rect2).area() > 0) // they intersect; merge them.
    newrect = rect1 | rect2;
    ... // remove rect1 and rect2 from list and insert newrect.

ОБНОВЛЕНИЕ 2: (для перевода в java)

Я знаю java очень мало. Я также никогда не использовал java API. Я даю здесь некоторый psudo-код (который, я думаю, можно легко перевести)

Для оператора & нам нужен метод, который находит пересечение двух прямоугольников.

Method: Intersect (Rect A, Rect B)
left = max(A.x, B.x)
top  = max(A.y, B.y)
right = min(A.x + A.width, B.x + B.width)
bottom = min(A.y + A.height, B.y + B.height)
if(left <= right && top <= bottom) return Rect(left, top, right - left, bottom - top)
else return Rect()

Для оператора | нам нужен аналогичный метод

Method: Merge (Rect A, Rect B)
left = min(A.x, B.x)
top  = min(A.y, B.y)
right = max(A.x + A.width, B.x + B.width)
bottom = max(A.y + A.height, B.y + B.height)
return Rect(left, top, right - left, bottom - top)

Для оператора == мы можем использовать перегруженный метод equals.

Ответ 3

Учитывая два контура ограничивающего прямоangularьника в форме (x,y,w,h), здесь есть функция для создания одного ограничивающего прямоangularьника (при условии, что прямоangularьники касаются друг друга или находятся внутри друг друга). Возвращает (x,y,w,h) объединенного ограничивающего прямоangularьника, то есть верхнего левого x, верхнего левого y, ширины и высоты. Вот иллюстрация

(x1,y1)       w1                           (x3,y3)         w3
  ._____________________.                    .____________________________.
  |                     |                    |                            | 
  |                     |  h1                |                            |
  |   (x2,y2)           |                    |                            |
  |     ._______________|_______.      -->   |                            |
  |     |               |       |            |                            |  h3
  ._____|_______________.       |            |                            |
        |                       |  h2        |                            |
        |                       |            |                            |
        |           w2          |            |                            |
        ._______________________.            .____________________________.

код

def combineBoundingBox(box1, box2):
    x = min(box1[0], box2[0])
    y = min(box1[1], box2[1])
    w = box2[0] + box2[2] - box1[0]
    h = max(box1[1] + box1[3], box2[1] + box2[3]) - y
    return (x, y, w, h)

Пример

С этими двумя ограничивающими рамками,

>>> print(box1)
>>> print(box2)
(132, 85, 190, 231)
(264, 80, 121, 230)

>>> new = combineBoundingBox(box1, box2) 
>>> print(new)
(132, 80, 253, 236)

Вот визуальный результат: до -> после