DP Динамическое программирование Алгоритм
Seam carving
Также: Seam carving · вырезание швов · умное сжатие картинок · content-aware resizing · Content-Aware Scale · Liquid Rescale
Как сделать фото уже, не сплющив горы и не отрезав края: убирать по одному шву — пути из пикселей сверху донизу, которые меньше всего отличаются от соседей. Самый дешёвый шов из почти 10¹⁷⁷ возможных находит таблица динамики за один проход по картинке.
Фото «Вода и горы» — панорама шириной 720 пикселей: небо, горный хребет на закате, полоса камыша и озеро. Его нужно сделать на треть уже. Если сжать, сплющится всё сразу: вершины станут острее, стебли камыша — гуще. Если обрезать края, пропадут камыш слева и справа и половина хребта. Но в кадре много места, которого никто не хватится: ровное небо, рябь, дымка между вершинами. Сцена ниже убирает именно его — шов за швом, по одному пикселю в каждой строке.
Сравните три режима при одной ширине. При сжатии вершины вытягиваются вверх, при обрезке исчезают края, а швы сохраняют и оба края, и форму вершин: хребет становится короче, но не уже. Слой «где прошли швы» показывает, откуда взяты пиксели. Каждый шов обязан пересечь каждую строку, в том числе горы, но в полосе гор швы протискиваются через пологие склоны и дымку, а резкие гребни и стебли камыша обходят. Кисть позволяет вмешаться: закрасьте то, что нельзя трогать, или то, что нужно убрать, и швы найдутся заново.
Идея
Назначим каждому пикселю энергию — насколько он отличается от соседей. Шов — путь сверху донизу по одному пикселю в строке, где соседние пиксели пути стоят в одном столбце или в соседних. Вырежем шов с наименьшей суммой энергий: в каждой строке пропадёт по пикселю, и пропадут самые незаметные. Повторим столько раз, на сколько пикселей нужно сузить картинку.
В статье Шая Авидана и Ариэля Шамира, где метод появился, энергия — сумма модулей изменения яркости по горизонтали и по вертикали. Мы считаем её по трём каналам цвета, сравнивая соседей пикселя слева и справа, сверху и снизу:
$$e(x, y) = \sum_{R,G,B} \Bigl(\bigl|I(x+1, y) - I(x-1, y)\bigr| + \bigl|I(x, y+1) - I(x, y-1)\bigr|\Bigr).$$На ровном небе соседи почти одинаковые, и энергия близка к нулю. На гребне горы, на стебле камыша, на буквах подписи она большая. Переключите в сцене слой «энергия»: на картинке остаются одни края. Глаз тоже первым делом замечает границы, поэтому то, что удаляют швы, и правда видно меньше всего.
Как найти самый дешёвый шов
Швов очень много. На куске 10 × 7 пикселей их 5574, на всём фото 720 × 366 — число из 177 цифр: из каждого пикселя вниз ведут два-три пути, и с каждой строкой вариантов почти втрое больше. Сосчитать их, кстати, помогает та же динамика, что найдёт лучший. Перебор безнадёжен, но и не нужен. Обозначим M(x, y) энергию самого дешёвого шва от верхней строки до пикселя (x, y). Такой шов пришёл в пиксель из одного из трёх пикселей над ним, поэтому
$$M(x, y) = e(x, y) + \min\bigl(M(x-1, y-1),\; M(x, y-1),\; M(x+1, y-1)\bigr),$$а в верхней строке M равно самой энергии. Таблица заполняется строка за строкой, самое маленькое число в нижней строке — цена лучшего шва, а сам шов восстанавливается снизу вверх: из каждой клетки — к тому из трёх соседей сверху, у кого число меньше. Вот это на куске нашего фото — подножие гор и берег с камышом — с теми самыми энергиями, которые печатает программа ниже:
Таблица находит шов почти прямо посередине: 552. Нажмите «Жадный шов». Жадность начинает с самого дешёвого пикселя верхней строки, 37, и каждый раз шагает к самому дешёвому из трёх соседей снизу. Вначале она экономит, потом сворачивает влево, где внизу стоит камыш с энергиями за 300, и набирает 999 — почти вдвое больше. Дешёвый первый шаг ничего не говорит о следующих. Таблица помнит лучший путь до каждого пикселя, а не один путь, и поэтому не ошибается.
Почему шов самый дешёвый
Для каждого пикселя M(x, y), посчитанное по формуле выше, равно наименьшей энергии шва от верхней строки до (x, y).
Индукция по строкам. В верхней строке шов состоит из одного пикселя, и формула верна. Пусть для строки y − 1 всё верно. Любой шов до (x, y) проходит через один из пикселей (x − 1, y − 1), (x, y − 1), (x + 1, y − 1), и его часть до этого пикселя — тоже шов, не дешевле M этого пикселя. Значит, весь шов не дешевле e(x, y) плюс наименьшее из трёх M. С другой стороны, лучший шов до самого выгодного из трёх соседей, продолженный в (x, y), стоит ровно столько. Значит, M(x, y) — наименьшая энергия.
На языке графов это кратчайший путь. Пиксели — вершины, из каждого вниз ведут три ребра, цена вершины — её энергия, а таблица перебирает вершины строка за строкой, то есть в топологическом порядке этого графа без циклов. Дейкстра тоже нашёл бы этот путь, но ему нужна куча, чтобы угадывать порядок, а здесь порядок известен заранее.
Код
Сначала кусок 10 × 7 из второй сцены: таблица M, шов и жадный путь.
Теперь целые фото. В песочнице лежат четыре фото автора сайта шириной 120 пикселей; программа ищет на каждом лучший и жадный шов, а потом вырезает 40 швов из «Озера Иссык». Каждый пиксель помнит свой столбец на исходном фото, чтобы в конце посчитать, сколько энергии выброшено.
Жадный шов дороже лучшего на всех четырёх фото — на 17–54 процента. Сорок швов выбрасывают 140 538 единиц энергии, а сорок самых «пустых» прямых столбцов — 181 296, на 29 процентов больше: швам не нужно идти по прямой, они обходят то, что встречается на пути. Видно и другое: каждый следующий шов дороже — 2382 у первого, 3517 у сорокового. Дешёвое место кончается, и чем сильнее сжимать, тем заметнее вмешательство. Сцена в начале статьи — тот же алгоритм на JavaScript, и на этих маленьких фото он находит те же самые швы с теми же ценами.
Сколько это стоит
Энергия — O(W·H), таблица — O(W·H): по три сравнения на пиксель. Путь назад — O(H), вырезать шов — сдвинуть хвосты строк, не больше O(W·H). Итого O(W·H) на шов и O(k·W·H) на k швов. Энергию после каждого шва целиком пересчитывать не нужно: у пикселя меняются соседи, только если он стоял рядом со швом или шов прошёл прямо над ним или под ним, — это полоса в несколько пикселей вдоль шва. Сцена так и делает и под картинкой показывает, сколько миллисекунд уходит на шов в вашем браузере.
Наклон на логарифмических осях близок к единице: вдвое больше пикселей — вдвое дольше. Чтобы сузить фото 720 × 366 на треть, нужно 240 швов, то есть 240 проходов по картинке. Ещё одна мысль из статьи Авидана и Шамира: если запомнить, каким по счёту шов забрал каждый пиксель, картинку потом можно показывать любой ширины мгновенно, без нового поиска. Сцена хранит такую карту, поэтому ползунок ширины работает без задержки.
Где ломается
Когда лишнего места нет. Авидан и Шамир называют две причины неудач. Картинка может быть слишком плотной: если в ней нет неважных участков, никакое сужение по содержимому не поможет. Или важные части расположены так, что швам их не обойти. Тогда честнее просто сжать. Выберите в сцене «Озеро Иссык» и сузьте до половины: склоны и лес занимают почти весь кадр, и правый склон сминается в узкую полоску. На «Воде и горах» при той же ширине из подписи в углу пропадают пробелы, и буквы встают вплотную.
Когда энергия ошибается. Лицо на ровном фоне — небольшой участок с плавными переходами, и простая энергия считает его неважным. В статье это лечат детектором лиц, а пользователю дают кисть, как в сцене: закрашенное зелёным получает огромную энергию, и швы его обходят, а закрашенное лиловым — огромную отрицательную, и швы идут через него, пока не вынут весь предмет. Так метод убирает предметы с фото.
Прямые линии. Шов вынимает в разных строках пиксели из разных столбцов, и прямая, которую он пересекает наискось, сдвигается неравномерно: край крыши или столб получают ступеньки. На фото природы это почти незаметно, на фото города — сразу.
Шов за швом — не лучшее сразу. Каждый шов лучший при уже вынутых предыдущих, но k швов вместе не обязаны быть лучшим набором из всех возможных. Есть и тоньше: вынутый шов сводит вместе пиксели, которые раньше не соседствовали, и на месте ровного участка может появиться новый резкий край. В 2008 году Михаэль Рубинштейн, Шамир и Авидан предложили оценивать «энергию вперёд» — не сами вынимаемые пиксели, а края, которые появятся после выреза, — и перенесли метод на видео, где швы становятся поверхностями сквозь все кадры и ищутся минимальным разрезом графа.
Где работает
Самое известное применение — Photoshop. Adobe получила неисключительную лицензию на технологию у исследовательской лаборатории MERL, где работал Авидан, и встроила её в Photoshop CS4 под названием Content-Aware Scale. Есть свободные реализации: плагин Liquid Rescale для GIMP, операция -liquid-rescale в ImageMagick, инструмент в фоторедакторе digiKam. Задача, которую решает метод, называется ретаргетингом — подогнать картинку под экран другой формы, — и в 2005 году её предложили Видья Сетлур, Саэко Такаги, Рамеш Раскар, Майкл Глейхер и Брюс Гуч. Швы стали самым простым и самым известным её решением, а заодно — классическим учебным упражнением на динамику: например, в курсе алгоритмов Роберта Седжвика и Кевина Уэйна это одно из домашних заданий.
История
Статью «Seam Carving for Content-Aware Image Resizing» Шай Авидан из Mitsubishi Electric Research Labs и Ариэль Шамир из Междисциплинарного центра в Герцлии и той же MERL представили на конференции SIGGRAPH в 2007 году. В ней уже было почти всё, о чём здесь шла речь: энергия, таблица, вырезание швов и вставка для расширения, удаление предметов кистью, карта порядка швов для мгновенного изменения размера. О демонстрационном видео к докладу сразу написали сайты для фотографов, а сама идея объясняется на одной странице — редкий случай, когда исследовательская статья почти сразу становится и инструментом, и учебной задачей.
Задачи
Первая — найти самый дешёвый шов с номерами его столбцов; два теста — энергии настоящих фото. Во второй про каждый пиксель спрашивают, сколько стоит лучший шов через него, и одной таблицы сверху для этого мало.
Самый дешёвый шов Шов через пиксельДанные: Фотографии автора сайта