Вырезание швов (или жидкое изменение масштаба ) - это алгоритм изменения размера изображения с учетом содержимого , разработанный Шаем Авиданом из Mitsubishi Electric Research Laboratories (MERL) и Ариэлем Шамиром из Междисциплинарного центра и MERL. Он работает, устанавливая ряд швов (наименее важных путей) в изображении и автоматически удаляет швы для уменьшения размера изображения или вставляет швы для его удлинения. Вырезание швов также позволяет вручную определять области, в которых нельзя изменять пиксели, и дает возможность удалять целые объекты с фотографий.
Целью алгоритма является перенацеливание изображений, то есть проблема отображения изображений без искажения на носителях различного размера (сотовые телефоны, проекционные экраны) с использованием стандартов документов, таких как HTML, которые уже поддерживают динамические изменения макета страницы и текста, но не изображений. . [1]
Ретаргетинг изображений был изобретен Видьей Сетлур, Саэко Такаге, Рамешем Раскаром, Майклом Глейхером и Брюсом Гучем в 2005 году. [2] Работа Сетлура и др. получил награду за 10-летнее воздействие в 2015 году.
Швы
Швы могут быть как вертикальными, так и горизонтальными. Вертикальный шов - это путь пикселей, соединенных сверху вниз на изображении с одним пикселем в каждой строке. [1] Горизонтальный шов аналогичен за исключением того, что соединение выполняется слева направо. Функция важности / энергии оценивает пиксель, измеряя его контраст с соседними пикселями.
Процесс
В приведенном ниже примере описывается процесс высечки шва:
Шаг | Изображение |
---|---|
1) Начните с изображения. | |
2) Рассчитайте вес / плотность / энергию каждого пикселя. Это можно сделать с помощью различных алгоритмов: величины градиента, энтропии, яркости, движения взгляда. [1] Здесь мы используем величину градиента. | |
3) Из энергетики составьте список швов. Швы ранжируются по энергии, при этом швы с низкой энергией имеют наименьшее значение для содержания изображения. Швы можно рассчитать с помощью метода динамического программирования, описанного ниже. | |
4) При необходимости удалите низкоэнергетические швы. | |
5) Финальное изображение. |
Удаляемые швы зависят только от размера (высоты или ширины), который нужно уменьшить. Также можно инвертировать шаг 4, чтобы алгоритм увеличивался в одном измерении, копируя шов с низким энергопотреблением и усредняя его пиксели с его соседями. [1]
Вычислительные швы
Расчет шва заключается в нахождении пути с минимальными затратами энергии от одного конца изображения до другого. Это можно сделать с помощью алгоритма Дейкстры , динамического программирования, жадного алгоритма или вырезания графа среди других. [1]
Динамическое программирование
Динамическое программирование - это метод программирования, который сохраняет результаты подсчетов, чтобы упростить вычисление более сложных результатов. Для расчета швов можно использовать динамическое программирование. При попытке вычислить вертикальный шов (путь) с наименьшей энергией для каждого пикселя в строке мы вычисляем энергию текущего пикселя плюс энергию одного из трех возможных пикселей над ним.
На изображениях ниже изображен процесс DP для вычисления одного оптимального шва. [1] Каждый квадрат представляет собой пиксель, а значение в верхнем левом углу красного цвета представляет значение энергии этого пикселя. Значение, выделенное черным цветом, представляет совокупную сумму энергий, ведущих к этому пикселю и включая его.
Над верхним рядом ничего нет, поэтому энергии такие же, как у исходного изображения.
Для каждого пикселя в остальных строках энергия равна его собственной энергии плюс минимальная из трех энергий выше. Повторяйте, пока не достигнете дна.
Для получения наименьшей энергии, которая у нас есть в конце, работайте с минимальными значениями, чтобы восстановить шов с минимальной энергией.
Расчет энергии тривиально распараллеливается для простых функций. Вычисление массива DP также может быть распараллелено с некоторым межпроцессным взаимодействием. Однако проблема создания нескольких швов одновременно сложнее по двум причинам: энергия должна регенерироваться для каждого удаления для правильности, а простое прослеживание нескольких швов может привести к перекрытию. Avidan 2007 вычисляет все швы, итеративно удаляя каждый шов и сохраняя «индексную карту» для записи всех сгенерированных швов. Карта содержит номер «n-го шва» для каждого пикселя изображения и может использоваться позже для корректировки размера. [1]
Однако, если игнорировать оба вопроса, возможно жадное приближение для параллельной резьбы швов. Для этого нужно начать с пикселя с минимальной энергией на одном конце и продолжать выбирать путь с минимальной энергией к другому концу. Используемые пиксели помечаются, чтобы их больше не выбирали. [3] Локальные швы также могут быть рассчитаны параллельно для меньших частей изображения для хорошего приближения. [4]
вопросы
- Алгоритму может потребоваться информация, предоставленная пользователем, чтобы уменьшить количество ошибок. Это может заключаться в закрашивании областей, которые необходимо сохранить. Для человеческих лиц можно использовать распознавание лиц.
- Иногда алгоритм, удаляя шов с низкой энергией, может в конечном итоге непреднамеренно создать шов с более высокой энергией. Решение этой проблемы - смоделировать удаление шва, а затем проверить дельту энергии, чтобы увидеть, увеличивается ли энергия (прямая энергия). Если это так, предпочтите вместо этого другие швы. [5]
Реализации
Adobe Systems приобрела у MERL неисключительную лицензию на технологию вырезания швов [6] и реализовала ее как функцию в Photoshop CS4, где она называется Content Aware Scaling. [7] Поскольку лицензия не является эксклюзивной, другие популярные приложения для компьютерной графики, среди которых GIMP , digiKam , ImageMagick , а также некоторые автономные программы, среди которых iResizer, [8] также имеют реализации этого метода, некоторые из них выпускаются как бесплатное программное обеспечение с открытым исходным кодом . [9] [10] [11]
Улучшения и расширения
- Улучшенная функция энергопотребления и приложение к видео за счет введения швов 2D (время + 1D). [5]
- Мультиоператор: комбинируйте с кадрированием и масштабированием. [13]
- Намного более быстрое снятие нескольких швов [14]
Обзор восьми методов перенацеливания изображений в 2010 году показал, что резьба по швам дает результат, который считается одним из худших из протестированных алгоритмов. Однако это было частью одного из алгоритмов высшего ранга: многооператорного расширения, упомянутого выше (в сочетании с кадрированием и масштабированием). [15]
Смотрите также
Рекомендации
- ^ a b c d e f g Авидан, Шай; Шамир, Ариэль (июль 2007 г.). «Резьба швов для изменения размера изображения с учетом содержимого | Документы ACM SIGGRAPH 2007» . SIGGRAPH 2007 : 10. DOI : 10,1145 / 1275808,1276390 .
- ^ Видья Сетлур, Саэко Такаге, Рамеш Раскар, Майкл Глейхер и Брюс Гуч (декабрь 2005 г.). «Автоматический ретаргетинг изображений» . MUM '05: Материалы 4-й Международной конференции по мобильным и повсеместным мультимедиа : 59–68. DOI : 10.1145 / 1149488.1149499 . ISBN 0473106582.CS1 maint: использует параметр авторов ( ссылка )
- ^ Бист; Палаккоде (2016). «Резьба по параллельному шву» . www.andrew.cmu.edu .
- ^ а б Чен-Куо Чан; Шу-Фань Ван; И-Лин Чен; Шан-Хун Лай (ноябрь 2009 г.). «Быстрая резка видео на основе JND с ускорением графического процессора для ретаргетинга видео в реальном времени». IEEE Transactions on Circuits and Systems for Video Technology . 19 (11): 1588–1597. DOI : 10.1109 / TCSVT.2009.2031462 .
- ^ a b Улучшенная резьба швов для ретаргетинга видео. Майкл Рубинштейн, Ариэль Шамир, Шай Авидан. СИГГРАФ 2008.
- ^ Mitsubishi Electric пресс - релиз , Business Wire, 16 декабря 2008.
- ^ Список новых функций Adobe Photoshop CS4 .
- ^ iResizer Программное обеспечение для изменения размера изображений с учетом содержимого от Teorex
- ^ Liquid Rescale , плагин для вырезания швов для GIMP
- ^ Объявление о включении в digiKam
- ^ Возможность вырезания швов включена в ImageMagick
- ^ https://avikdas.com/2019/07/29/improved-seam-carving-with-forward-energy.html
- ^ Мультиоператорный ретаргетинг медиа. Майкл Рубинштейн, Ариэль Шамир, Шай Авидан. СИГГРАФ 2009.
- ^ Изменение размера изображения с учетом содержимого в реальном времени Наука в Китае Серия F: Информационные науки, 2009 НАУКА В КИТАЕ ПРЕССА. Архивировано 7 июля 2011 года в Wayback Machine.
- ^ Рубинштейн, Майкл; Гутьеррес, Диего; Соркина, Ольга; Шамир, Ариэль (2010). «Сравнительное исследование ретаргетинга изображений» (PDF) . Транзакции ACM на графике . 29 (5): 1–10. DOI : 10.1145 / 1882261.1866186 .См. Также тест RetargetMe .
Внешние ссылки
- Интерактивная демонстрация резьбы по шву
- Демонстрационные видеоролики по резьбовому шву:
- на ютубе
- на страницах Ариэля Шамира на сайте Междисциплинарного центра (высокое разрешение)
- Объяснение резьбы швов (Liquid rescaling) на сайте ImageMagick
- Учебное пособие по нарезке швов