Какова алгоритмическая эффективность метода findContours, реализованного в OpenCV? - PullRequest
3 голосов
/ 11 марта 2019

У меня есть вопрос об алгоритмической эффективности метода findContours, который реализован в OpenCV.Допустим, у меня есть код, более или менее похожий на этот (в Python 3.6, но в C ++ он выглядит почти идентично):

# ... Some image processing code ...
_, contour, _ = cv2.findContours(img_mtx_binary, 
                                 cv2.RETR_TREE, 
                                 cv2.CHAIN_APPROX_NONE)
# ... More image processing code ...

, где img_mtx_binary может быть матрицей Numpy или C ++Матовый объект, который содержит двоичное изображение 0 или 255 и contour - список найденных контуров.Размер изображения NxM .

Какова эффективность (или диапазон значений эффективности) реализованного алгоритма в записи Big O ?Я обнаружил, что он использует алгоритм Suzuki [1] , но в официальной газете [2] я не могу найти четкую информацию об этом.

Всего наилучшего,

Miłosz

1 Ответ

4 голосов
/ 11 марта 2019

Поскольку алгоритм находит все контуры, он должен смотреть на каждый пиксель хотя бы один раз.Для следующего наброска он рассматривает не более 8 соседей каждого пикселя, и благодаря процессу маркировки несколько раз избегает одной и той же обработки.Количество операций на пиксель ограничено.

Таким образом, время выполнения равно O (NM), если вы предпочитаете линейное в области изображения, и это оптимально.Этот термин, скорее всего, доминирует (асимптотически) в дополнительном бухучете.

...