Хабрахабр

[Перевод] Динамическое программирование в реальном мире: вырезание швов

У динамического программирования репутация метода, который вы изучаете в университете, а затем вспоминаете только на собеседованиях. Но на самом деле метод применим во многих ситуациях. По сути, это техника эффективного решения задач, которые можно разбить на множество сильно повторяющихся подзадач.

Задача и методика подробно описаны в работе Авидана и Шамира «Вырезание швов для изменения размеров изображения с учётом контента» (статья в свободном доступе). В статье я покажу интересное реальное применение динамического программирования — задача вырезания швов (seam carving).

Если хотите освежить в памяти методы, см. Эта одна из серии статей по динамическому программированию. иллюстрированное введение в динамическое программирование.

Чтобы решить с помощью динамического программирования реальную проблему, нужно правильно её сформулировать. В этом разделе описываются необходимые преднастройки для выбранной задачи.

Подробности смотрите в оригинальной работе, а я предлагаю краткий обзор. Авторы оригинальной статьи описывают контентно-ориентированное изменение размера изображения, то есть изменение ширины или высоты изображения с учётом содержимого. Предположим, вы хотите изменить размер фотографии сёрфера:

Фото: Кирил Добрев на Pixabay
Вид сверху сёрфера посреди спокойного океана, с турбулентными волнами справа.

Как вы можете представить, это оставляет на фотографии видимый шов, где изображение слева и справа не совпадают. Как подробно описано в статье, есть несколько способов уменьшения ширины изображения: это стандартные обрезка и масштабирование, с их присущими недостатками, а также удаление столбцов пикселей из середины. И таким способом можно удалить только ограниченный объём изображения.

Последнее оставляет видимый шов
Попытка уменьшить ширину путём обрезки левой части и вырезания блока из середины.

Она сначала определяет менее важные «низкоэнергетические» области, а затем вычисляет низкоэнергетические «швы», которые проходят по картинке. Авидан и Шамир в статье описывают новую технику «вырезания швов» (seam carving). В случае уменьшения ширины изображения определяется вертикальный шов от верхней части изображения к нижней, который на каждой строке смещается влево или вправо не более чем на один пиксель.

Это соответствует нашей интуиции. На фотографии сёрфера самый низкоэнергетический шов проходит через середину изображения, где вода самая спокойная.


Самый низкоэнергетический шов, найденный на изображении сёрфера, показан красной линией шириной пять пикселей для видимости, хотя на самом деле шов его ширина всего один пиксель

Повторение этого процесса снова и снова позволяет существенно уменьшить ширину всей фотографии. Определив шов с наименьшей энергией, а затем удалив его, мы уменьшаем ширину изображения на один пиксель.


Изображение серфера после уменьшение ширины на 1024 пикселя

Но в отличие от кадрирования, сохраняется текстура воды слева и нет резких переходов. Опять же, алгоритм вполне логично удалил неподвижную воду посередине, а также в левой части фотографии. Правда, можно найти некоторые неидеальные переходы в центре, но в основном результат выглядит естественно.

Определение энергии изображения

Магия в том, чтобы найти самый низкоэнергетический шов. Для этого мы сначала назначаем каждому пикселю изображения энергию. Затем применяем динамическое программирование, чтобы найти путь через изображениес наименьшей энергией — этот алгоритм подробно обсудим в следующем разделе. Сначала рассмотрим, как присвоить пикселям значения энергии.

Не будем усложнять и возьмём функцию, которая просто фиксирует величину изменения цвета вокруг каждого пикселя. В научной статье рассматриваются несколько энергетических функций и их различия. Для полноты картины я немного подробнее опишу энергетическую функцию на случай, если вы захотите реализовать её самостоятельно, но это просто предварительная установка для последующих вычислений динамического программирования.

Разница между первым и последним велика.
Слева три пикселя от тёмного до светлого. Справа три тёмных пикселя с небольшой разностью в интенсивности цвета

Покомпонентно вычисляем квадрат расстояния между ними, то есть квадрат разницы между красными, зелёными и синими компонентами, а затем складываем их. Для вычисления энергии конкретного пикселя смотрим на пиксели слева и справа от него. Наконец, складываем горизонтальные и вертикальные расстояния. То же самое делаем для пикселей выше и ниже центрального.

$| \Delta x |^2 = (\Delta r_x)^2 + (\Delta g_x)^2 + (\Delta b_x)^2$

$| \Delta y |^2 = (\Delta r_y)^2 + (\Delta g_y)^2 + (\Delta b_y)^2$

$e(x, y) = | \Delta x | ^2 + | \Delta y | ^2$

Единственное предостережение — скажем, если пиксель на левом краю, то слева нет соседа. В этом случае производим сравнение только с правым пикселем. Аналогичные проверки производим для пикселей на верхнем, правом и нижнем краях.

Функция энергии велика, если соседние пиксели сильно отличаются по цвету, и мала, если они похожи.

Как и ожидалось, самая высокая энергия у сёрфингиста в середине и турбулентных волн справа
Энергия каждого пикселя на фотографии сёрфера: чем светлее — тем она выше.

Однако она принимает очень большой диапазон значений. Функция энергии хорошо работает на фотографии сёрфера. На самом деле там просто очень низкие значения по сравнению с регионами с самой высокой энергией. Поэтому при визуализации кажется, что на большей части фотографии у пикселей нулевая энергия. Чтобы упростить визуализацию, я зуммировал сёрфера и осветил эту область.

Вычислив энергию каждого пикселя, мы можем найти шов с наименьшей энергией от верхней части изображения к нижней. Такой же анализ применим и для горизонтальных швов для уменьшения высоты исходного изображения. Однако мы сосредоточимся на вертикальных.

Начнём с определения:

  • Шов — это последовательность пикселей, по одному пикселю на строку. Требование состоит в том, что между двумя последовательными строками координата $x$ изменяется не более чем на один пиксель. Это сохраняет последовательность шва.
  • Шов с наименьшей энергией — тот, чья полная энергия по всем пикселям в шве минимизирована.

Важно заметить, что шов с наименьшей энергией не обязательно проходит через все пиксели с наименьшей энергией. Учитывается общая энергия всех, а не отдельных пикселей.

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

Как видим, нельзя просто выбирать пиксель с наименьшей энергией в следующей строке.

Разбиваем проблему на подзадачи

Проблема с жадным подходом в том, что при принятии решения о следующем шаге мы не учитываем остальную часть шва впереди. Мы не можем заглянуть в будущее, однако способны учесть всё, что нам уже известно к настоящему моменту.

Вместо выбора между несколькими пикселями для продолжения одного шва, будем выбирать между несколькими швами для перехода к одному пикселю. Давайте перевернём задачу с ног на голову. Если каждый из пикселей в строке выше кодирует путь, пройденный до этой точки, то мы по сути смотрим на полную историю до этой точки. Что нам нужно сделать, так это взять каждый пиксель и выбрать между пикселями в строке выше, от которых может исходить шов.

Фундаментальный выбор — какой из швов продолжать?
Для каждого пикселя изучаем по три пикселя в строке выше.

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

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

Определение рекуррентного соотношения

Как обычно, теперь нужно формализовать идею в рекуррентное соотношение. Существует подзадача, соответствующая каждому пикселю в исходном изображении, поэтому входы в наше рекуррентное соотношение могут быть просто координатами $x$ и $y$ этого пикселя. Это даёт целочисленные входы, позволяя легко упорядочивать подзадачи, а также возможность хранить ранее вычисленные значения в двумерном массиве.

Он начинается в верхней части изображения и заканчивается в пикселе $(x,y)$. Определим функцию $M(x,y)$, которая представляет энергию вертикального шва с наименьшей энергией. Название $М$ выбрано как в оригинальной научной статье.

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

$M(x,0)=e(x,0)$

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

$M(x, y) = e(x, y) + \min \begin M(x - 1, y - 1) \\ M(x, y - 1) \\ M(x + 1, y - 1) \end{cases}$

В качестве пограничной ситуации следует рассмотреть случай, когда текущий пиксель находится у левого или правого края изображения. В этих случаях мы опускаем $M(x-1,y-1)$ для пикселей на левом краю или $M(x+1,y-1)$ на правом краю.

Это означает, что мы смотрим на нижнюю строку изображения и выбираем самый низкоэнергетический шов, который заканчивается на одном из этих пикселей. Наконец, нужно извлечь энергию самого низкоэнергетического шва, который охватывает всю высоту изображения. Для фотографии шириной $W$ и высотой $H$ пикселей:

$\min_{0 \le x < W} M(x, H - 1)$

Итак, мы получили рекуррентное соотношение со всеми нужными свойствами:

  • У рекуррентного соотношения есть целочисленные входы.
  • Из соотношения легко извлечь окончательный ответ.
  • Соотношение зависит от самого себя.

Проверка подзадачи DAG (ориентированный ациклический граф)

Поскольку каждая подзадача $M(x,y)$ соответствует одному пикселю исходного изображения, график зависимостей очень легко визуализировать. Просто разместим их на двумерной сетке, как на исходном изображении!


Подзадачи расположены в двумерной сетке, как и пиксели в исходном изображении

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

Обратите внимание на отсутствие стрелок из верхнего ряда ячеек
Верхний ряд не зависит от других подзадач.

Во-первых, в самой левой ячейке во второй строке мы сталкиваемся с пограничной ситуацией. Во второй строке начинают появляться зависимости. То же самое произойдёт позже с самой левой ячейкой в третьем ряду. Поскольку слева ячеек нет, то ячейка $(1,0)$ зависит только от ячеек, расположенных непосредственно над ней и справа вверху.


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

Эта ячейка зависит от трёх ячеек: слева вверху, прямо над ней и справа вверху. Во второй ячейке второго ряда (1,1), мы видим наиболее типичное проявление рекуррентного соотношения. Такая структура зависимостей применяется ко всем «средним» ячейкам во второй и последующих строках.


Подзадачи между левым и правым краями зависят от трёх подзадач сверху

Поскольку справа больше нет ячеек, она зависит только от ячеек непосредственно вверху и вверху слева. Наконец, ячейка с правого края представляет вторую пограничную ситуацию.


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

Процесс повторяется для всех последующих строк.


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

Полный граф зависимостей пугает большим количеством стрелок, но просмотр их по одной помогает установить явные шаблоны.

Реализация снизу вверх

Проведя этот анализ, мы получили порядок обработки:

  • Переходим от верхней части изображения к нижней.
  • В каждой строке можно действовать в любом порядке. Естественный выбор — идти слева направо.

Поскольку каждая строка зависит только от предыдущей, то нужно сохранять только две строки данных: одну для предыдущей строки и одну для текущей строки. Двигаясь слева направо, мы даже можем выбросить отдельные элементы из предыдущей строки по мере их использования. Однако это усложняет алгоритм, так как придётся выяснять, какие части предыдущей строки можно отбросить.

Входные данные называются pixel_energies, а pixel_energies[y][x] представляет энергию пикселя в координатах $(x,y)$. В следующем коде Python на входе список строк, где каждая строка содержит список чисел, представляющих отдельные энергии пикселей в этой строке.

Начнём с вычисления энергии швов верхнего ряда, просто скопировав отдельные энергии пикселей в верхнем ряду:

previous_seam_energies_row = list(pixel_energies[0])

Затем выполняем цикл по оставшимся строкам входа, вычисляя энергии шва для каждой строки. Самая «сложная» часть — определить, на какие элементы предыдущей строки ссылаться, поскольку слева от левого края или справа от правого края нет пикселей.

В конце итерации заменяем данные предыдущей строки данными текущей строки для следующей итерации. На каждой итерации создаётся новый список энергий шва для текущей строки. Вот как мы отбрасываем предыдущую строку:

# Skip the first row in the following loop.
for y in range(1, len(pixel_energies)): pixel_energies_row = pixel_energies[y] seam_energies_row = [] for x, pixel_energy in enumerate(pixel_energies_row): # Determine the range of x values to iterate over in the previous # row. The range depends on if the current pixel is in the middle of # the image, or on one of the edges. x_left = max(x - 1, 0) x_right = min(x + 1, len(pixel_energies_row) - 1) x_range = range(x_left, x_right + 1) min_seam_energy = pixel_energy + \ min(previous_seam_energies_row[x_i] for x_i in x_range) seam_energies_row.append(min_seam_energy) previous_seam_energies_row = seam_energies_row

В итоге previous_seam_energies_row содержит энергии шва для нижней строки. Находим минимальное значение в этом списке — и это ответ!

min(seam_energy for seam_energy in previous_seam_energies_row)

Можете проверить эту реализацию, обернув приведённый код в функцию, а потом вызвав её с двумерным массивом, который вы построили. Следующие входные данные подобраны так, чтобы жадный подход потерпел неудачу, при этом был очевидный шов с самой низкой энергией:

ENERGIES = [ [9, 9, 0, 9, 9], [9, 1, 9, 8, 9], [9, 9, 9, 9, 0], [9, 9, 9, 0, 9],
] print(min_seam_energy(ENERGIES))

Пространственная и временнáя сложность

Каждому пикселю в исходном изображении соответствует одна подзадача. Для каждой из подзадач есть не более трёх зависимостей, поэтому решение каждой из них предполагает постоянный объём работы. Последний ряд проходится дважды. Таким образом, для изображения шириной $W$ и высотой $H$ пикселей временнáя сложность равна $O(W×H+W)$.

В первом $W$ элементов, а второй постепенно увеличивается до $W$. В каждый момент времени у нас хранятся два списка: один для предыдущей строки и один для текущей. Таким образом, пространственная сложность равна $O(2W)$, то есть просто $O(W)$.

Таким образом, пространственная сложность останется $O(W)$. Обратите внимание, что если бы мы фактически отбрасывали элементы данных предыдущей строки, то сокращали бы список элементов предыдущей строки примерно с той же скоростью, с какой нарастает список текущей строки. Хотя ширина может варьироваться, обычно это не так важно.

Итак, мы нашли значение самого низкоэнергетического шва, но что делать с этой информацией? Ведь на самом деле нас волнует не значение энергии, а сам шов! Проблема в том, что от конечного пикселя нет способа вернуться к остальной части шва.

Например, если вы помните задачу о грабителе домов, мы нашли максимальное значение для суммы грабежа, но не какие конкретно дома нужно ограбить для получения этой суммы. Это то, что я пропустил в предыдущих статьях, но то же самое относится ко многим проблемам динамического программирования.

Представление обратных указателей

Общий ответ: хранить обратные указатели. В задаче вырезания швов нам нужно не только значение энергии шва на каждом пикселе. Нужно ещё знать, какой из пикселей в предыдущей строке привёл к этой энергии. Сохраняя эту информацию, мы можем следовать обратным указателям вплоть до верхней строчки, получив координаты всех пикселей, которые составляют шов с наименьшей энергией.

Энергия будет использоваться для расчёта подзадач. Во-первых, создадим класс для хранения энергии и обратных указателей. Поскольку обратный указатель определяет, какой пиксель в предыдущей строке дал текущую энергию, можем представить его просто как координату x.

class SeamEnergyWithBackPointer(): def __init__(self, energy, x_coordinate_in_previous_row=None): self.energy = energy self.x_coordinate_in_previous_row = x_coordinate_in_previous_row

Результатом расчёта каждой подзадачи будет не просто число, а экземпляр этого класса.

Хранение обратных указателей

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

Результаты сохраняем в двумерном массиве, который выглядит так же, как входной массив. Для этого просто сохраним полный результат всех подзадач, хотя технически можно отказаться от числовых энергий шва предыдущих строк.

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

seam_energies = [] # Initialize the top row of seam energies by copying over the top row of
# the pixel energies. There are no back pointers in the top row.
seam_energies.append([ SeamEnergyWithBackPointer(pixel_energy) for pixel_energy in pixel_energies[0]
])

Основной цикл работает в основном так же, как и предыдущая реализация, со следующими отличиями:

  • Данные для предыдущей строки содержат экземпляры SeamEnergyWithBackPointer, поэтому при вычислении значения рекуррентного соотношения следует искать энергию шва внутри этих объектов.
  • Сохраняя данные для текущего пикселя, нужно построить новый экземпляр SeamEnergyWithBackPointer. Здесь мы будем хранить энергию шва для текущего пикселя, а также координату x из предыдущей строки, используемую для расчёта текущей энергии шва.
  • В конце каждой строки вместо того, чтобы отбрасывать данные предыдущей строки, мы просто добавляем данные текущей строки в seam_energies.

# Skip the first row in the following loop.
for y in range(1, len(pixel_energies)): pixel_energies_row = pixel_energies[y] seam_energies_row = [] for x, pixel_energy in enumerate(pixel_energies_row): # Determine the range of x values to iterate over in the previous # row. The range depends on if the current pixel is in the middle of # the image, or on one of the edges. x_left = max(x - 1, 0) x_right = min(x + 1, len(pixel_energies_row) - 1) x_range = range(x_left, x_right + 1) min_parent_x = min( x_range, key=lambda x_i: seam_energies[y - 1][x_i].energy ) min_seam_energy = SeamEnergyWithBackPointer( pixel_energy + seam_energies[y - 1][min_parent_x].energy, min_parent_x ) seam_energies_row.append(min_seam_energy) seam_energies.append(seam_energies_row)

Идём по обратным указателям

Теперь вся таблица подзадач заполнена и мы можем восстановить шов с наименьшей энергией. Начнём с поиска координаты x в нижней строке, которая соответствует шву с наименьшей энергией:

# Find the x coordinate with minimal seam energy in the bottom row.
min_seam_end_x = min( range(len(seam_energies[-1])), key=lambda x: seam_energies[-1][x].energy
)

Теперь переходим от нижней части изображения к верхней, изменяя $y$ из len(seam_energies) - 1 до нуля. На каждой итерации добавляем текущую пару $(x,y)$ в список, представляющий наш шов, а затем устанавливаем значение $x$ для объекта, на который указывает SeamEnergyWithBackPointer в текущей строке.

# Follow the back pointers to form a list of coordinates that form the
# lowest-energy seam.
seam = []
seam_point_x = min_seam_end_x
for y in range(len(seam_energies) - 1, -1, -1): seam.append((seam_point_x, y)) seam_point_x = \ seam_energies[y][seam_point_x].x_coordinate_in_previous_row seam.reverse()

Так шов выстраивается снизу вверх, список потом можно прочитать в обратном порядке, если нужны координаты сверху вниз.

Пространственная и временнáя сложность

Временнáя сложность аналогична предыдущей, потому что нам всё равно нужно один раз обработать каждый пиксель. После просмотра последней строки и поиска шва с наименьшей энергией мы затем поднимаемся на всю высоту изображения, чтобы восстановить шов. Таким образом, для изображения $W×H$ временнáя сложность равна $O(W×H+W+H)$.

Таким образом, мы используем объём $O(W×H)$. Что касается объёма, мы по-прежнему храним постоянный объем данных для каждой подзадачи, но теперь не отбрасываем никаких данных.

Как только будет найден вертикальный шов с наименьшей энергией, мы можем просто скопировать пиксели из исходного изображения в новое. Каждая строка нового изображения содержит все пиксели из соответствующей строки исходного изображения, за исключением пикселя из шва с наименьшей энергией. Поскольку мы удаляем один пиксель в каждой строке, начиная с изображения $W×H$, то получаем изображение $(W−1)×H$.

Кажется заманчивым найти более одного низкоэнергетического шва в исходном изображении, а затем удалить их все сразу. Можем повторить этот процесс, пересчитав энергетическую функцию на новом изображении и найдя на нём самый низкоэнергетический шов. Когда первый удалён, второй станет недействителен, потому что в нём отсутствует один или несколько пикселей. Проблема в том, что два шва могут пересечься.

Анимация процесса удаления шва. Лучше смотреть в полноэкранном режиме для более чёткого просмотра швов

Каждый кадр видео представляет собой изображения на каждой итерации с наложением визуализации шва с наименьшей энергией.

В статье было много подробных объяснений, так что давайте закончим серией красивых фотографий! На следующем фото — скальное образование в Национальном парке Арчес:

Фото: Майк Гоад на Flickr
Скальное образование с отверстием в Национальном парке Арчес.

Энергетическая функция для этого изображения:

Обратите внимание на высокую энергию вокруг края отверстия
Энергия каждого пикселя на фотографии: чем светлее — тем она выше.

Обратите внимание, что он проходит через скалу справа, входя прямо в скальное образование там, где освещённая часть на вершине скалы совпадает с цветом неба. В результате вычисления получается такой шов с наименьшей энергией. Возможно, следует подобрать энергетическую функцию получше!


Самый низкоэнергетический шов, найденный на изображении, показан красной линией шириной пять пикселей для видимости, хотя на самом деле шов его ширина всего один пиксель

Наконец, изображение арки после изменения размера:


Арка после сжатия на 1024 пикселя

Одним из улучшений может быть реализация одной из других энергетических функций, перечисленных в научной статье. Результат определённо не идеален: многие края горы из исходного изображения искажены.

Хотя динамическое программирование обычно обсуждается в теории, но является полезным практическим методом для решения сложных проблем. В этой статье мы рассмотрели одно из приложений динамического программирования: изменение размера изображения с учётом контента путём вырезания швов.

Кроме того, мы изучили использование обратных указателей, чтобы не только найти значение энергии для оптимального шва, но и определить координаты каждого пикселя, которые составили это значение. Мы применили те же принципы разбиения задачи на более мелкие подзадачи, анализируя зависимости между этими подзадачами, а затем решая подзадачи в порядке, минимизирующем пространственные и временные сложности алгоритма. Затем применили эти части к реальной проблеме, которая требует некоторой пред- и постобработки для действительно эффективного использования алгоритма динамического программирования.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть