Резьба по шву (или жидкое изменение масштаба ) — это алгоритм изменения размера изображения с учетом содержимого , разработанный Шаем Авиданом из Mitsubishi Electric Research Laboratories (MERL) и Ариэлем Шамиром из Междисциплинарного центра и MERL. Он действует путем создания ряда швов (путей наименьшей важности) в изображении и автоматически удаляет швы, чтобы уменьшить размер изображения, или вставляет швы, чтобы расширить его. Резьба по швам также позволяет вручную определять области, в которых пиксели не могут быть изменены, и дает возможность удалять целые объекты с фотографий.
Целью алгоритма является ретаргетинг изображений, то есть задача отображения изображений без искажений на носителях различных размеров (сотовые телефоны, проекционные экраны) с использованием стандартов документов, таких как HTML, которые уже поддерживают динамические изменения макета страницы и текста, но не изображений. . [1]
Ретаргетинг изображений был изобретен Видья Сетлур, Саеко Такаге, Рамеш Раскар, Майкл Глейхер и Брюс Гуч в 2005 году. [2] Работа Setlur et al. выиграл награду за 10-летнее воздействие в 2015 году [ где? ] .
Швы могут быть как вертикальными, так и горизонтальными. Вертикальный шов — это путь пикселей, соединенных сверху вниз на изображении, по одному пикселю в каждой строке. [1] Горизонтальный шов аналогичен, за исключением того, что соединение осуществляется слева направо. Функция важности/энергии оценивает пиксель, измеряя его контраст с соседними пикселями.
В приведенном ниже примере описан процесс резьбы по шву:
Количество швов, которые нужно удалить, зависит только от размера (высоты или ширины), который нужно уменьшить. Также возможно инвертировать шаг 4, чтобы алгоритм увеличился в одном измерении, копируя шов с низкой энергией и усредняя его пиксели с соседними. [1]
Вычисление шва заключается в поиске пути с минимальными затратами энергии от одного конца изображения к другому. Это можно сделать, среди прочего, с помощью алгоритма Дейкстры , динамического программирования, жадного алгоритма или разрезания графа . [1]
Динамическое программирование — это метод программирования, который сохраняет результаты дополнительных вычислений, чтобы упростить вычисление более сложного результата. Динамическое программирование можно использовать для расчета швов. При попытке вычислить вертикальный шов (путь) с наименьшей энергией для каждого пикселя в строке мы вычисляем энергию текущего пикселя плюс энергию одного из трех возможных пикселей над ним.
На изображениях ниже показан процесс DP для расчета одного оптимального шва. [1] Каждый квадрат представляет собой пиксель, причем значение в верхнем левом углу красного цвета представляет собой значение энергии этого пикселя. Значение черного цвета представляет собой совокупную сумму энергий, ведущих к этому пикселю и включая его.
Вычисление энергии тривиально распараллеливается для простых функций. Вычисление массива DP также можно распараллелить с некоторым межпроцессным взаимодействием. Однако проблема создания нескольких швов одновременно сложнее по двум причинам: для обеспечения правильности необходимо регенерировать энергию для каждого удаления, а простое отслеживание нескольких швов может привести к перекрытию. Avidan 2007 вычисляет все швы, итеративно удаляя каждый шов и сохраняя «индексную карту» для записи всех сгенерированных швов. Карта содержит номер «n-го шва» для каждого пикселя изображения и может использоваться позже для настройки размера. [1]
Однако, если игнорировать обе проблемы, возможно жадное приближение к параллельному вырезанию швов. Для этого нужно начать с пикселя с минимальной энергией на одном конце и продолжать выбирать путь с минимальной энергией до другого конца. Использованные пиксели помечаются, чтобы их нельзя было выбрать повторно. [3] Для получения хорошей аппроксимации локальные швы также можно рассчитывать параллельно для меньших частей изображения. [4]
Adobe Systems приобрела неисключительную лицензию на технологию вырезания швов у MERL [6] и реализовала ее как функцию в Photoshop CS4, где она называется Content Aware Scaling. [7] Поскольку лицензия не является эксклюзивной, другие популярные приложения компьютерной графики (например, GIMP , digiKam и ImageMagick ), а также некоторые автономные программы (например, iResizer) [8] также имеют реализации этой техники, некоторые из которых выпускаются как бесплатное программное обеспечение с открытым исходным кодом . [9] [10] [11]
Обзор восьми методов ретаргетинга изображений, проведенный в 2010 году, показал, что вырезание швов дает результат, который был признан одним из худших из протестированных алгоритмов. Однако это была часть одного из алгоритмов самого высокого ранга: упомянутого выше многооператорного расширения (в сочетании с обрезкой и масштабированием). [15]