Эффективный способ объединить пересекающиеся ограничивающие прямоугольники
Я пытаюсь упростить следующее изображение с помощью OpenCV:
У нас здесь много красных фигур. Некоторые из них полностью содержат другие. Некоторые из них пересекаются со своими соседями. Моя цель - объединить все пересекающиеся фигуры, заменив любые две пересекающиеся фигуры ограничительной рамкой многоугольника их объединения. (повторяется до тех пор, пока больше не будет пересекающихся фигур).
Под пересечением я подразумеваю также прикосновение. Надеюсь, это прояснит все на 100%:
Я пытаюсь сделать это эффективно, используя стандартные операции морфологии; очевидно, это можно сделать наивно в O(N^2), но это будет слишком медленно. Расширение не помогает, потому что некоторые фигуры находятся на расстоянии всего 1 пикселя, и я не хочу, чтобы они сливались, если они не пересекаются.
2 ответа
Для достижения того, что вы хотите, мы будем использовать 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 реализует самый известный алгоритм.
ОБНОВЛЕНИЕ: я неправильно понял вопрос ранее. Мы не хотим удалять прямоугольники, которые полностью находятся внутри других. Мы только хотим заменить пересекающиеся прямоугольники. Поэтому для первого случая мы ничего не должны делать.
Новый API (2.4.9) поддерживает & и | операторы.
Из документа opencv:
- 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 очень мало. Я также никогда не использовал API Java. Я даю здесь некоторый псевдо-код (который, я думаю, может быть легко переведен)
За & Оператор, нам нужен метод, который находит пересечение двух прямоугольников.
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 метод.
Учитывая два контура ограничивающего прямоугольника в виде (x,y,w,h), вот функция для создания единого ограничивающего прямоугольника (при условии, что прямоугольники соприкасаются или находятся внутри друг друга). Возврат(x,y,w,h)объединенного ограничивающего прямоугольника, т. е. левого верхнего угла 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)
Вот визуальный результат: До -> После
