opencv: временная сложность для обнаружения минимального прямоугольника

Question

Я начинаю изучать минимальное обнаружение прямоугольника с opencv. Мне нужно рассчитать временную сложность для этого, но все еще путайте эти методы:

1. findContours().
2. minAreaRect()

Любой человек может помочь мне

1. , как работают эти методы?
2. Какова временная сложность этих методов?

любая ссылка заметно

Answer 1

cv::findContours() извлекает контуры из бинарного изображения с использованием алгоритма (link):

Сузуки, С. и Abe, К., топологическая структурный анализ оцифрованных Бинарные изображения по границе. CVGIP 30 1, стр 32-46 (1985)

Основная концепция этого алгоритма состоит из отслеживания кромок, рассматривая топологический анализ. Следовательно, связь между внутренним и внешним краями извлекается. На практике алгоритм различает внешние и внутренние границы и классифицирует их иерархически, поэтому контур считается «родительским» для другого контура, если он окружает контур.

С другой стороны, cv::minAreaRect() находит ориентированный минимальный ограничивающий прямоугольник, содержащий набор точек. Это тип ограничивающего объема. Достаточно найти наименьшую ограждающую коробку для выпуклой оболочки объектов. Для выпуклого многоугольника известен линейный алгоритм времени для прямоугольника, охватывающего минимальную площадь. Это основано на наблюдении, что сторона ограждающей коробки с минимальной площадью должна быть коллинеарной со стороной выпуклого многоугольника (см. [1]). Можно перечислить ящики такого типа в линейном времени с подходом rotating calipers.