Краткое описание алгоритма ресамплинга Seam Curving

Весьма интересный алгоритм осуществления ресамплинга цифровых изображений был предложен господами Shai Avidan и Ariel Shamir в октябре 2007 года.
Презентация способностей технологии в видеоформате представлена на сайте Seam Carving for Content-Aware Image Resizing.
Имеется более-менее подробное математическое описание алгоритма на английском языке.

Если резюмировать изложенное в статье, предлагается подход к проведению ап- и даунсамплинга с использованием такого понятия, как энергия пиксела. Вычислять энергию пиксела можно по-простому (1), при помощи энтропии, сегментации и с использованием гистограммы градиентов (2).(1)
(2)

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

1. Удаление/добавление строк или стоблбцов изображения содержащие элементы с минимальной/максимальной энергией (рис.1.а);
2. Удаление/добавление элементов в строке или столбце с минимальной/максимальной энергией (рис.1.б);
3. Удаление/добавление элементов с минимальной/максимальной энергией по всему изображению (рис.1.в);
4. Интеллектуальное удаление/добавление элементов (тот самый Seam Carving).

Рис.1. Примеры контентно-зависимого ресамплинга

Как видно из рисунка 1, конентно-зависимый ресамплинг, если он не интеллектуальный, не очень-то и применим. Основным отличием алгоритма интеллектуального от прочих контентно-зависимых методов ресамплинга является способ определения удаляемых/добавляемых пикселов. В алгоритме Seam Carving определяется понятие "шва" - цепочки пикселов с минимально-значимой энергией. "Шов" может быть вертикальным и горизонтальным и представляет собой некоторый вектор S, определяемый вертикально (3) или горизонтально (4).(3)
(4)

Энергия "шва" определяется суммой энергий элементов его составляющих.
(5)

С выбранным набором элементов изображения и выполняется удаление в случае даун-самплинга, либо дублирование при выполнении ап-самплинга.