Одномерная транспортная оптимизация на окружности — эффективный алгоритм и применения

При цифровой обработке изображений нередко возникает необходимость найти количественную характеристику сходства или различия заданных изображений, а также тем или иным образом установить соответствие между сходными изображениями. Часто при таком сравнении учитываются лишь параметры ориентации, т.е. направления на плоскости: например, при построении т.н. локальных дескрипторов вычисляются направления, в которых наиболее быстро меняется интенсивность изображения, а при обработке цветных изображений в цветовом пространстве «тон-насыщенность-яркость» (HSB) тон задается точкой на цветовой окружности. Удобной количественной характеристикой сходства двух заданных распределений направлений на окружности является транспортная метрика Л.В. Канторовича.
В докладе будет описан эффективный численный метод, устанавливающий оптимальное соответствие двух распределений в транспортной метрике для случая, когда ценовая функция выпукла (напр., равна квадрату расстояния между точками окружности) или, более общо, удовлетворяет т.н. условию Монжа. При этом используется специальная параметризация, сходная с некоторыми конструкциями теории Обри-Мезера в нелинейной динамике. Доклад основан на статье J. Delon, J. Salomon & A. Sobolevski “Fast transport optimization for Monge costs on the circle” (SIAM J. Appl. Math 70:7 (2010) 2239–2258, arXiv: 0902.3527v3).