• Оригинальный адрес:Real-world dynamic programming: seam carving
• Оригинальный автор:Avik Das
• Перевод с:Программа перевода самородков
• Постоянная ссылка на эту статью:GitHub.com/rare earth/gold-no…
• Переводчик:nettee
• Корректор:JalanJiang,TokenJan

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

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

В этом посте я подробно рассмотрю интересное практическое применение динамического программирования: вырезание швов.Эта статья Авидана и ШамираSeam Carving for Content-Aware Image ResizingЭтот вопрос, наряду с предлагаемой методикой, подробно обсуждается в (в свободном доступе по поиску по названию статьи).

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

(Поскольку Medium не поддерживает рендеринг математических формул, я использую изображения, чтобы показать сложные формулы. Если у вас возникли трудности с доступом к изображениям, вы можете увидетьСтатьи на моем личном сайте. )

Контекстно-зависимое изменение размера изображения

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

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

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

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

(Попробуйте уменьшить ширину изображения, обрезав левую и центральную части изображения. Обрезка центра оставит на изображении видимую разделительную линию.)

Авидан и Шамир представляют в своей статье метод, называемыйрезка швовТехнологии. Сначала он идентифицирует менее значимые «низкоэнергетические» области изображения, а затем находит самые низкоэнергетические «швы» по всему изображению. Для уменьшения ширины изображения обрезка по шву находит вертикальный шов, который проходит от верхней части изображения к нижней, и перемещает следующую строку вверх на один пиксель влево или вправо.

На картинке серфера шов с наименьшей энергией проходит через самую спокойную часть воды в середине картинки. Это соответствует нашей интуиции.

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

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

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

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

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

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

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

(Левая половина показывает, что пиксель имеет больше энергии, когда соседние пиксели имеют очень разные цвета. Правая половина показывает, что пиксель имеет меньше энергии, когда соседние пиксели имеют одинаковые цвета.)

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

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

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

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

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

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

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

Сначала определим понятие шва с наименьшей энергией:

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

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

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

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

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

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

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

(Для каждого пикселя мы смотрим на три пикселя в предыдущей строке. Основной вопрос заключается в том, какой шов мы должны расширить?)

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

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

определить рекурсию

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

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

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

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

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

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

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

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

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

Из-за каждой подзадачиM(x,y) соответствует одному пикселю в исходном изображении, график зависимости подзадач очень легко визуализировать, просто поместите подзадачи в 2D-сетку, точно так же, как они были расположены на исходном изображении!

(Подзадачи помещаются в двумерную сетку, точно так же, как на исходном изображении.)

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

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

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

(Подзадача на левом краю зависит только от двух приведенных выше подзадач.)

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

(Подзадачи между левым и правым краями зависят от трех приведенных выше подзадач.)

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

(Подзадача на правом краю зависит только от двух приведенных выше подзадач.)

Наконец, повторите процесс для всех последующих рядов.

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

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

восходящая реализация

Из приведенного выше анализа мы можем получить порядок подзадач:

• сверху вниз на картинке.
• Для каждой строки в любом порядке. Естественный порядок слева направо.

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

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

Сначала рассчитайте энергию шва в верхней строке, просто скопируйте энергию одного пикселя в верхней строке:

previous_seam_energies_row = list(pixel_energies[0])

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

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

# 在循环中跳过第一行
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):
        # 判断要在前一行中遍历的 x 值的范围。这个范围取决于当前像素是在图片
        # 的中间还是边缘。
        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))

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

Для каждого пикселя исходного изображения существует соответствующая подзадача. Каждая подзадача имеет не более 3 зависимостей, поэтому усилия для решения каждой подзадачи постоянны. Наконец, нам нужно еще раз перебрать последнюю строку. Итак, если изображение широкое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

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

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

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

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

Начнем с первой строки, которая содержит только энергию одного пикселя. Поскольку предыдущей строки нет, все обратные указателиNone.但是为了一致性，我们还是会存储SeamEnergyWithBackPointerПримеры:

seam_energies = []

# 拷贝最顶行的像素能量来初始化最顶行的接缝能量。最顶行没有后向指针。
seam_energies.append([
    SeamEnergyWithBackPointer(pixel_energy)
    for pixel_energy in pixel_energies[0]
])

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

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

# 在循环中跳过第一行
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):
        # 判断要在前一行中遍历的 x 值的范围。这个范围取决于当前像素是在图片
        # 的中间还是边缘。
        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-координату нижнего ряда, соответствующего самому низкому энергетическому шву:

# 找到最底行接缝能量最低的 x 坐标
min_seam_end_x = min(
    range(len(seam_energies[-1])),
    key=lambda x: seam_energies[-1][x].energy
)

Затем, двигаясь снизу вверх по картинке,yКоординаты отlen(seam_energies) - 1вплоть до0. В каждом раунде петли замените ток (x,y) координатную пару в список, представляющий шов, а затемxЗначение текущей строки устанавливается равнымSeamEnergyWithBackPointerМесто, на которое указывает объект.

# 沿着后向指针前进，得到一个构成最低能量接缝的坐标列表
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ВверхMike Goad. )

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

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

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

(Шов с самой низкой энергией на изображении арки. Шов визуализируется красной линией шириной в пять пикселей, тогда как на самом деле шов имеет ширину всего в один пиксель.)

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

(Изображение арки с уменьшенной шириной на 1024 пикселя.)

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

---

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

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

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

---

Программа перевода самородковэто сообщество, которое переводит высококачественные технические статьи из Интернета сНаггетсДелитесь статьями на английском языке на . Охват контентаAndroid,iOS,внешний интерфейс,задняя часть,блокчейн,продукт,дизайн,искусственный интеллектЕсли вы хотите видеть более качественные переводы, пожалуйста, продолжайте обращать вниманиеПрограмма перевода самородков,официальный Вейбо,Знай колонку.