31 мая 2019г.
Что такое Seam Carving?
Seam Carving — это алгоритм изменения размеров изображения, который учитывает содержимое изображения (как называют авторы — Content-Aware Image Resizing Algorithm). Впервые был продемонстрирован в 2007 году и вызвал немалый интерес.
Общая схема алгоритма
Весь алгоритм состоит из таких составных частей:
Первый этап. Создание маски для изображения, на которой пользователь отметит, что он хочет непременно сохранить, а что удалить.
Второй этап. Нахождение энергии каждого пикселя. Сразу оговорюсь, что под энергией будем понимать важность пикселя в изображении, чем больше значение, тем он важнее.
Третий этап. Нахождение такой вертикальной цепочки пикселей, чтобы суммарная энергия пикселей, которые входят в эту цепочку была минимальной.
Четвертый этап. Когда мы нашли цепочку с минимальной энергией, то нам остается ее только удалить, чтобы уменьшить изображение. После того, мы n раз повторим пункты 3 – 4, и удалим объект.
Пятый этап. Добавление n новых цепочек на изображение вместо удаленных. Более детальный разбор этапов алгоритма приведен ниже.
Вычисление энергии точек. Для решения этой задачи используем следующий принцип – будем считать изменение цвета, по сравнению с его соседями. Формула будет выглядеть следующим образом:
Выглядит неудобно, но на практике переменные R, G и B содержат значения цветов (от 0 до 255), а индексы: left, right, up, down – указывают на расположение пикселя, цвета которого используются для расчета. После расчета карта энергии изображения будет иметь следующий вид:
Нахождение
цепочки с минимальной суммарной энергией
После того как нашли энергию каждого пикселя, нам нужно выбрать те пиксели, у которых значение энергии минимальное. Но если начать удалять и добавлять произвольные пиксели, то само изображение деформируется до неузнаваемости. Такой вариант нас не устраивает. Поэтому, для начала, нужно выбрать цепочку пикселей, которую, в свою очередь, можно без проблем удалить или добавить такую же, что бы растянуть изображение. Но цепочка должна быть «правильной». В чем заключается правильность? «Правильная» цепочка или шов — это набор точек, да такой, что в каждой строке изображения, выбран ровно один пиксель, а пиксели в соседних строках «соединены» или сторонами, или углами.
Как выглядит правильная цепочка, мы выяснили. Но как найти
ее на изображении? Вариант, который использовал я, заключается в использовании динамического программирования. Углубляться в то, что такое динамическое программирование не буду. Опишу, как это будет выглядеть конкретно в нашем случае. Сначала мы создадим новый массив, который по размеру равен массиву с энергиями пикселей. В этот массив мы для каждого пикселя запишем сумму элементов минимальной цепочки пикселей, которая начинается у верхнего края изображения и заканчивается на данном пикселе.
Если формализовать вычисление этого массива, то получим следующую формулу:
Теперь, по этому массиву мы можем быстро найти цепочку с минимальной суммой энергий. Сначала мы найдем, какой пиксель из нижней строчки изображения принадлежит этой цепочке: элемент, что мы ищем, будет иметь наименьшее значение среди элементов нижней строчки. Потому что в данном массиве записаны значения сумм элементов минимальных цепочек от верхнего края до данного пикселя. Цепочки,
которые нас
интересуют, заканчиваются на пикселе из последнего ряда. Соответственно для
всего рисунка минимальная цепочка будет выбрана как минимальная из всех минимальных цепочек, которые заканчиваются на пикселях из нижней строчки. Из нижнего пикселя мы можем пойти только в 3 соседние пиксели на строчку
выше:
слева-сверху, сверху или справа-сверху. Среди
этих пикселей выбираем пиксел с минимальным значением в массиве сумм, и переходим к нему. Продолжаем, пока не дойдем до верхней строчки.
Но из того что было сказано ранее можно сделать вывод что искать
и удалять будем только вертикальные цепочки. Вернемся к модификациям, о которых я говорил. Первой модификацией было то, что мы используем алгоритм для удаления объектов. Второй модификацией будет то, что алгоритм будет выбирать какую цепочку удалить, вертикальную или горизонтальную. То есть построение энергетической карты, и вычисление цепочки будет происходить дважды. Сперва найдем вертикальную цепочку с наименьшей энергией, а затем горизонтальную. Изображения редко имеют форму квадрата, и у более короткой цепочки будет меньшая энергия. Чтобы это не мешало в сравнении, мы нормируем две цепочки, поделив их на высоту и ширину изображения соответственно. Затем из двух чисел выберем меньшее.
И будем работать с цепочкой которой принадлежит меньшее число.
Уменьшение рисунков
Уменьшение рисунков. Мы, наконец-то, нашли цепочку пикселей, c которыми будем работать. Вертикальную или горизонтальную. Теперь нужно ее удалить. Если нам надо уменьшить ширину картинки на один пиксель, то тут все просто: находим вертикальную цепочку, как это описывается выше, и просто удаляем ее из изображение. Если нам надо уменьшить изображение не на 1 пиксел, а на большее значение, то выполняем операцию удаления цепочки столько раз, сколько надо (каждый раз при этом нам надо будет эту цепочку искать).
Хочу обратить внимание, что операция уменьшения изображения на n пикселей и операция уменьшения изображения на 1 пиксел n раз не являются эквивалентными. Их отличие в том, что если мы уменьшаем на 1 пиксел n раз, то мы для каждой из промежуточных изображений ищем энергию пикселей, а если сразу уменьшаем
на n, то энергии пикселей мы берем из исходного изображения.
Увеличение рисунков
Уменьшать изображения на практике проще, чем увеличивать его. Тогда, вопрос в чем сложность увеличения изображения? Она в том, что вначале думаешь — это точно так же, как и при уменьшении, выбирать цепочки и их «растягивать». Результат будет следующим:
Чтобы такое не произошло нужно брать не одну минимальную цепочку, а столько, сколько надо, чтобы дополнить рисунок по высоте и ширине. Но делать будем это поэтапно. Так, чтобы на каждом этапе охватывалось как можно больше «не важных» частей изображения, и как можно меньше важных. Увеличение разбито на этапы таким образом, чтобы на каждом из них изображение увеличивалось не более чем на 50%.
Заключение
Предложенный алгоритм, в связи с тем, что работает в двух направлениях, более аккуратно подходит к процессу удаления объектов с изображения. Но
вместе с тем не стоит
упускать из виду тот факт, что и время необходимое на выполнения алгоритма выросло соизмеримо проделанной работе. Из чего можно сделать вывод,
что данная модификация алгоритма имеет место быть в тех случаях, когда можно пожертвовать временем в угоду повышенного качества.
Список литературы
1.
Seam Carving for Content-Aware Image Resizing. Shai Avidan, Ariel Shamir, 2007.
2.
Wang Z., Bovik A. C.,
Sheikh H.
R.,
Simoncelli
E. P. Image quality assessment: From error visibility to structural similarity. IEEE Transactions on Image Processing, 2004, no. 4, pp. 600–612.
3.
Efros A. A., Leung T. K. Sintez Texture synthesis by nonparametric sampling, IEEE Int. Conf. Computer Vision, Corfu, Greece, 1999, pp.1033–1038.
4.
Jump up to:a b Improved Seam Carving for Video Retargeting. Michael Rubinstein, Ariel Shamir, Shai Avidan. SIGGRAPH 2008.
5.
Mitsubishi Electric press release, Business Wire, December 16, 2008.
6.
Liquid Rescale, seam carving plug-in for GIMP
7.
Rane S.D., Sapiro G., Bertalmio M. Structure and texture filling-In of missing image blocks in wireless transmission and compression applications.
IEEE Transactions on Image Processing, 2003, pp. 296-303.
8.
Ballester C., Bertalmio M., Caselles V., Sapiro G., Verdera J. Filling-in by joint interpolation
of vector fields and gray levels. IEEE Transactions on Image Processing, 2001, pp. 1200-1211.
9.
Real-time content-aware image resizing Science in
China
Series
F:
Information Sciences,
2009 SCIENCE IN CHINA PRESS. Archived July 7, 2011, at the Wayback Machine
10.
On-demand, server-side seam carving based on CAIR
11.
Ariel (2010).
"A Comparative Study of Image Retargeting" (PDF). ACM Transactions on Graphics. 29 (5). See
also the RetargetMe benchmark.
