На чем основан алгоритм opencv GCGRAPH (максимальный поток)?
opencv имеет реализацию алгоритма максимального потока (класс GCGRAPH в файле gcgraph.hpp). Это доступно здесь.
Кто-нибудь знает, какой именно алгоритм максимального потока реализован этим классом?
Решение
Я не уверен на 100% в этом, но я считаю, что алгоритм основан на эта исследовательская работа, описывающая алгоритмы максимального потока для компьютерного зрения. В частности, в разделе 3 описан новый алгоритм для вычисления максимальных потоков.
Я не выровнял каждую деталь алгоритма статьи с реализацией алгоритма, но многие детали, кажется, совпадают:
- Описанный алгоритм работает с использованием двунаправленного поиска по s и t, что и делает реализация: например, есть чтение комментария
// grow S & T search trees, find an edge connecting them, - Описанный алгоритм отслеживает набор потерянных узлов, который переменная
std::vector<Vtx*> orphansкажется, отслеживать в реализации. - Описанный алгоритм работает путем построения набора деревьев и их повторного использования; Реализация алгоритма отслеживает дерево, связанное с каждым узлом.
Надеюсь, это поможет!
Другие решения
Других решений пока нет …