Параллельные алгоритмы для эффективного поиска соответствующих точек в задачах компьютерного зрения

В настоящей статье предложены параллельные алгоритмы для поиска соответствующих точек в задачах компьютерного зрения. Разрабатываемая коллективом авторов фотограмметрическая система основана на использовании искусственных световозвращающих мишеней, идентичных по фотометрическим параметрам. В связи с этим традиционные методы поиска соответствий на основе вычисления дескрипторов (SIFT, SURF, и др.) неприменимы; фотограмметрическая система использует методы, основанные на эпиполярной геометрии. В настоящей статье предложены эффективные алгоритмы поиска соответствий между точками по всей совокупности снимков (в отличие от классических методов, использующих 2-4 снимка), основанные на графах. Приведено точное двухшаговое решение задачи через суперклику графа потенциальных соответствий; показана невозможность практического нахождения суперклики в реальных задачах в связи с вычислительной сложностью. Предложена эффективная параллельная реализация алгоритма формирования графа на основе эпиполярных ограничений, а также быстродействующий параллельный эвристический алгоритм поиска клик в данном графе. Применение итерационной схемы с обратным проецированием точек, отсевом выбросов и уравниванием координат точек и положений камер через метод связок позволяет в итоге получать точное решение задачи с использованием эвристического алгоритма поиска клик на каждой итерации. Предложенная архитектура системы дает значительный выигрыш во времени. Разработаны программные реализации описанных алгоритмов. Выполнена сравнительная оценка эффективности и производительности предложенных алгоритмов применительно к разрабатываемой фотограмметрической системе, экспериментально подтверждена эффективность предлагаемых решений.