Резьба по шву (или жидкое изменение масштаба ) - это алгоритм изменения размера изображения с учетом содержимого, разработанный компанией Mitsubishi Electric Research Laboratories (MERL), а также Междисциплинарный центр и MERL. Он работает, устанавливая ряд швов (наименее важных путей) в изображении и автоматически удаляет швы для уменьшения размера изображения или вставляет швы для его удлинения. Вырезание швов также позволяет вручную определять области, в которых нельзя изменять пиксели, и позволяет удалять целые объекты с фотографий.
Целью алгоритма является перенацеливание изображения, то есть проблема отображения изображений без искажения на носителях различного размера (сотовые телефоны, проекционные экраны) с использованием стандартов документов, таких как HTML, которые уже поддерживают динамические изменения на странице. макет и текст, но не изображения.
Ретаргетинг изображений был изобретен Видьей Сетлур, Саеко Такаге, Рамешем Раскаром, Майклом Глейхером и Брюсом Гучем в 2005 году. Работа Сетлура и др. получил награду за 10-летний эффект в 2015 году.
Швы могут быть вертикальными или горизонтальными. Вертикальный шов - это путь пикселей, соединенных сверху вниз на изображении с одним пикселем в каждой строке. Горизонтальный шов аналогичен за исключением того, что соединение выполняется слева направо. Функция важности / энергии оценивает пиксель, измеряя его контраст с соседними пикселями.
В примере ниже описывается процесс вырезания шва:
Шаг | Изображение |
---|---|
1) Начните с изображения. | |
2) Рассчитайте вес / плотность / энергию каждого пикселя. Это можно сделать с помощью различных алгоритмов: величины градиента, энтропии, визуальной значимости, движения взгляда. Здесь мы используем величину градиента. | |
3) Из энергии составьте список швов. Швы ранжируются по энергии, при этом швы с низким энергопотреблением имеют наименьшее значение для содержания изображения. Швы можно рассчитать с помощью метода динамического программирования, описанного ниже. | |
4) При необходимости удалите низкоэнергетические швы. | |
5) Окончательное изображение. |
Удаление швов зависит только от размера (высоты или ширины), который нужно уменьшить. Также можно инвертировать шаг 4, чтобы алгоритм увеличивался в одном измерении, копируя низкоэнергетический шов и усредняя его пиксели с его соседями.
Вычисление шва состоит из поиска путь минимальных затрат энергии от одного конца изображения до другого. Это можно сделать с помощью алгоритма Дейкстры, динамического программирования, жадного алгоритма или вырезания графа среди прочего.
Динамическое программирование - это метод программирования, который сохраняет результаты дополнительных вычислений, чтобы упростить вычисление более сложных результатов. Для расчета швов можно использовать динамическое программирование. Если вы пытаетесь вычислить вертикальный шов (путь) с наименьшей энергией, для каждого пикселя в строке мы вычисляем энергию текущего пикселя плюс энергию одного из трех возможных пикселей над ним.
На изображениях ниже изображен процесс DP для вычисления одного оптимального шва. Каждый квадрат представляет пиксель, а значение в верхнем левом углу красного цвета представляет значение энергии этого пикселя. Значение, выделенное черным цветом, представляет совокупную сумму энергий, ведущих к этому пикселю и включая его.
Над верхним рядом ничего нет, поэтому энергии такие же, как у исходного изображения.
Для каждого пикселя в остальных строках энергия равна его собственной энергии плюс минимальная из трех энергий выше. Повторяйте, пока не достигнете дна.
Для получения наименьших энергий, которые у нас есть в конце, увеличьте минимальные значения, чтобы восстановить шов с минимальной энергией.
Расчет энергии тривиально распараллеливается для простых функций. Вычисление массива DP также может быть распараллелено с некоторым межпроцессным взаимодействием. Однако проблема создания нескольких швов одновременно сложнее по двум причинам: энергия должна регенерироваться для каждого удаления для правильности, а простое прослеживание нескольких швов может привести к перекрытию. Avidan 2007 вычисляет все швы, итеративно удаляя каждый шов и сохраняя «индексную карту» для записи всех сгенерированных швов. Карта содержит номер «n-го шва» для каждого пикселя изображения и может использоваться позже для корректировки размера.
Однако, если игнорировать оба вопроса, возможно жадное приближение для параллельного вырезания шва. Для этого нужно начать с пикселя с минимальной энергией на одном конце и продолжать выбирать путь с минимальной энергией до другого конца. Используемые пиксели помечаются, чтобы их больше не выбирали. Локальные швы также могут быть вычислены параллельно для более мелких частей изображения для хорошего приближения.
Adobe Systems приобрела неисключительную лицензию на технологию резьбы по швам от MERL и реализовала ее как функцию в Photoshop CS4, где она называется масштабированием с учетом содержимого. Поскольку лицензия не является эксклюзивной, другие популярные приложения для компьютерной графики, среди которых GIMP, digiKam, ImageMagick, а также некоторые автономные программы, Среди них iResizer, также есть реализации этого метода, некоторые из которых выпущены как бесплатное программное обеспечение с открытым исходным кодом.
В 2010 году был обнаружен обзор восьми методов ретаргетинга изображений Эта резьба по шву дала результат, который был признан одним из худших из протестированных алгоритмов. Однако это было частью одного из алгоритмов высшего ранга: многооператорного расширения, упомянутого выше (в сочетании с кадрированием и масштабированием).