Comments 125
Чем-то напомнило фрактальное масштабирование.
оу… как все сложно… но я сначала подумал… можно просто некоторые части изображения растянуть по горизонтали (там где нет НЛО или лошади)… и будет примерно то самое
Этот алгоритм практически так и делает, даже чуть больше. Он сам «ищет» участки, которые можно растянуть. Кроме того он может растягивать не только строго вертикальные участки. Например картинку со звездным небом таким способом, как описали вы, уже не растянуть.
А насчет сложности — может оно не так и сложно, просто я постарался детально описать, чтобы меньше вопросов оставалость после прочтения.
А насчет сложности — может оно не так и сложно, просто я постарался детально описать, чтобы меньше вопросов оставалость после прочтения.
Тут работает золотое правило программиста: Лучше день потерять, а потом за 5 минут долететь.
Ручками можно сделать всё… вообще говоря, большие числа можно и без калькулятора делить… столбиком на бумажке…
но куда элегантней реализовать это в алгоритме.
:)
Ручками можно сделать всё… вообще говоря, большие числа можно и без калькулятора делить… столбиком на бумажке…
но куда элегантней реализовать это в алгоритме.
:)
UFO just landed and posted this here
Класс! Пойду попробую на чем нибудь реализовать! Спасибо!
UFO just landed and posted this here
Побежал реализовывать на питоне
Боюся, что на Питоне будет большая проблема с быстродействием. Лучше реализовать самые «тяжелые» операции на С/С++ и сделать интерфейс к Питону.
Всё уже придумано :)
blog.eikke.com/index.php/ikke/2007/09/02/seam_carving_content_aware_image_resizin
blog.eikke.com/index.php/ikke/2007/09/02/seam_carving_content_aware_image_resizin
Классная статья. У меня дурацкий вопрос: нафига на два делить, а потом отбрасывать дробную часть, если важно распределение значений?
Дело в том, что там делится не всегда на 2, а на количество посчитаных соседей. Для большинства пикселей мы считаем по два соседа, но для крайних может быть и меньше.
а почему два соседа используется? Почему не все 4?
Можно использовать и все 4 соседа, и даже все 8 :)
Но мне кажется, что 4 соседа мало чего поменяют, поскольку суммы с верхним и левим соседом учитываются когда мы считаем их энергии.
Хотя да, если считать 4 соседа, то ничего плохого не будет :)
Но мне кажется, что 4 соседа мало чего поменяют, поскольку суммы с верхним и левим соседом учитываются когда мы считаем их энергии.
Хотя да, если считать 4 соседа, то ничего плохого не будет :)
Ну как мало чего поменяют — минимальные цепочки иногда другие будут. А что визуально лучше — надо смотреть, зависит от картинки скорее всего.
Вообще производную можно оценивать по-разному. Возможно, для большинства картинок это лучше делать по большей окрестности точки; хотя черт его знает.
Вообще производную можно оценивать по-разному. Возможно, для большинства картинок это лучше делать по большей окрестности точки; хотя черт его знает.
Не буду с вами спорить, поскольку согласен с вами, некоторые изменения действительно будут.
А еще лучше, как подсказал Toshas, использовать оператор Sobel: en.wikipedia.org/wiki/Sobel_operator (англ).
Но в статье я использовал только два соседа, чтобы излишне не усложнять, так как двух соседей хватает для приемлемого качества.
А еще лучше, как подсказал Toshas, использовать оператор Sobel: en.wikipedia.org/wiki/Sobel_operator (англ).
Но в статье я использовал только два соседа, чтобы излишне не усложнять, так как двух соседей хватает для приемлемого качества.
Понял, спасибо.
НЛО прилетело и растянуло этот рисунок здесь!
уже знаю где применю это )
Кстати, на последних двух снимках — львов?
а как насчет двунаправленного растягивания?
растянуть прогой, повернуть, ещё раз применить прогу (-;
Я не хотел про него писать, потому что статья и так достаточно большая вышла. Если вкратце, то есть 2 способа двунаправленого растягивания:
1. Растянуть до нужного размера обычным растягиванием, сохранив пропорции, а потом применить этот способ.
2. Растягивать точно также, как и в случае одного направления, только одновременно искать как вертикальные, так и горизонтальные цепочки, и выбирать среди них постоянно минимум. Единственное замечание — если картинка не квадратная, то надо будет эти значения как-то нормализировать, например помножив суммы по горизонталных цепочках на высоту, а по вертикальных — на ширину.
Если владеете английским, то можете про это почитать тут: PDF от авторов
1. Растянуть до нужного размера обычным растягиванием, сохранив пропорции, а потом применить этот способ.
2. Растягивать точно также, как и в случае одного направления, только одновременно искать как вертикальные, так и горизонтальные цепочки, и выбирать среди них постоянно минимум. Единственное замечание — если картинка не квадратная, то надо будет эти значения как-то нормализировать, например помножив суммы по горизонталных цепочках на высоту, а по вертикальных — на ширину.
Если владеете английским, то можете про это почитать тут: PDF от авторов
UFO just landed and posted this here
Инвайта автору статьи!
Ну, почти получилось…
stratero.ru/homm/SeamCarving.jpg
stratero.ru/homm/SeamCarving.jpg
:)
:)
Для таких случаев использование алгоритма комбинируется с ручной расстановкой зон, которые нельзя трогать. Похожый эффект бывает, если растягивать фотографию человека в лесу. Тогда алгоритм считает человека второстепенным объектом и тоже растягивает его.
Для таких случаев использование алгоритма комбинируется с ручной расстановкой зон, которые нельзя трогать. Похожый эффект бывает, если растягивать фотографию человека в лесу. Тогда алгоритм считает человека второстепенным объектом и тоже растягивает его.
Индусу повезло меньше ipicture.ru/uploads/090107/QS61UIA3uh.jpg ))
Отличная статья и результат!
Спасибо большое!
Спасибо большое!
Мегастатья, спасибо, очень интересно!
У меня на аукцион народ фотки лотов загружает всевозможных форматов (соотношений сторон).
Может попробовать этим алгоритмом их приводить к стандарту для более стройного дизайна страницы — имеются в виду превьюшки маленькие, конечно.
Может попробовать этим алгоритмом их приводить к стандарту для более стройного дизайна страницы — имеются в виду превьюшки маленькие, конечно.
Очень интересный и качественный материал. Автору респект.
По поводу увеличения картинок, думаю, можно попробовать так. Взять N цепочек с минимальной энергией. У каждой из них есть «вес», то есть сумма энергий всех пикселей, из которых они состоят.
Чем меньше вес, тем чаще должна повторяться цепочка. Скажем, если N = 2 и веса цепочек равны W1 = 20, W2 = 40, то цепочка W1 должна повторяться в 2 раза чаще, чем W2.
Скорее всего, N придётся выбирать в зависимости от того, насколько широко нужно растянуть картинку: чем шире, тем больше N потребуется. Думаю, нужно провести эксперименты и посмотреть, почти наверняка там линейная зависимость (если надо увеличить в 2 раза, достаточно 2-х цепочек, если в 3, то трёх и т.д.)
По поводу увеличения картинок, думаю, можно попробовать так. Взять N цепочек с минимальной энергией. У каждой из них есть «вес», то есть сумма энергий всех пикселей, из которых они состоят.
Чем меньше вес, тем чаще должна повторяться цепочка. Скажем, если N = 2 и веса цепочек равны W1 = 20, W2 = 40, то цепочка W1 должна повторяться в 2 раза чаще, чем W2.
Скорее всего, N придётся выбирать в зависимости от того, насколько широко нужно растянуть картинку: чем шире, тем больше N потребуется. Думаю, нужно провести эксперименты и посмотреть, почти наверняка там линейная зависимость (если надо увеличить в 2 раза, достаточно 2-х цепочек, если в 3, то трёх и т.д.)
В этом нет смысла, цепочка и так будет посторяться несколько раз, пока не найдется более дешевая цепочка
*повторяться
Нужно просто новой цепочке добавлять немного бонусной энергии
Старой при этом тоже надо добавлять, иначе она так и останется минимальной.
Ну и возникает тот же самый вопрос: а здесь в счём смысл? С N минимальными цепочками всё совершенно понятно, что и для чего делается.
Ну и возникает тот же самый вопрос: а здесь в счём смысл? С N минимальными цепочками всё совершенно понятно, что и для чего делается.
Да, старой тоже конечно надо добавить.
Смысл в том, что, одна и та же цепочка может разрастаться в случае остутствия достойных альтернатив. А в вашем случае вы принудительно режете картинку даже если остальные цепочки в 100 раз дороже чем дешевая первая
Например если на картинке есть однородный кусок фона, мой вариант будет только его растягивать, а ваш — растянет несколько раз и пойдет рвать основную картинку. Если же картинка полностью сложная, например лес, то наши результаты будут схожими, я думаю
Смысл в том, что, одна и та же цепочка может разрастаться в случае остутствия достойных альтернатив. А в вашем случае вы принудительно режете картинку даже если остальные цепочки в 100 раз дороже чем дешевая первая
Например если на картинке есть однородный кусок фона, мой вариант будет только его растягивать, а ваш — растянет несколько раз и пойдет рвать основную картинку. Если же картинка полностью сложная, например лес, то наши результаты будут схожими, я думаю
Нет. Если веса различаются значительно (например, в 100 раз) то при добавлении 101-ой новой вертикальной цепочки, цепочка с меньшим весом будет вставлена 100 раз, а следующая за ней по весу — 1. Если же добавить нужно будет меньше цепочек, то цепочка с меньшим весом просто не будет вставлена ни разу.
А вообще надо экспериментировать конечно, я ведь просто предложио попробовать. Кстати, когда я работал в институте кибернетики, очень похожим методом распознавали горизонт :) Тоже искали пути с минимальной «энергией» от левого края картинки до правого, только энергия немного по-другому вычислялась
А откуда возьмётся более дешёвая цепочка?
Онлайн ресайз
rsizr.com/
rsizr.com/
На счет увеличения картинки — чтобы не раслягивалась одна и та же цепочка, попробуйте каждой новой вставленной цепочке искуственно повышать энергию (немножко), тогда алгоритм сам собой будет находить альтернативные цепочки, или тянуть одну, пока она не станет дороже какой-то другой альтернативы.
Как автор статьи, благодарю всех за комменты и плюсы. Теперь я один из вас.
При запуске бинарника:
---------------------------
SeamCarving.exe - Ошибка приложения
---------------------------
Ошибка при инициализации приложения (0xc0000135). Для выхода из приложения нажмите кнопку "ОК".
---------------------------
ОК
---------------------------
Спасибо за полезную статью! Узнал много интересного, пишите ещё!
Автор молодец, изложил все доступно и понятно. Кстати, для вычисления производных изображения чаще применяют оператор Sobel.
Пока на Хабре есть такие статьи и такие авторы, все крики «Хабр стал не тот» предлагаю отправлять в /dev/null. Спасибо!
Интересная статья, понравилась, жаль что я не могу вам плюсик поставить :(
Ты мне шкаф скукожил, демон!
From bugatak.ru/shared/i.jpg
To bugatak.ru/shared/i-resized.jpg
С другой стороны, я как-то по солидней стал.
From bugatak.ru/shared/i.jpg
To bugatak.ru/shared/i-resized.jpg
С другой стороны, я как-то по солидней стал.
Очень нужная вещь. Только сегодня искал что-то подобное и тут бац. Спасибо! У меня есть теперь новые обои.
Жаль не могу поставить +, автору просто нереальный респект. Очень умная статья :)
Ценная информация.
Спасибо.
Спасибо.
Вот за что надо ноутбуки давать, а не за херню в притчах.
шикарно. Алгоритм рулит
Могу также предложить свою модификацию программы. Она отличается тем что можна мастшабировать изображение обычным методом и паралельно посмотреть результат обработаным алгоритмом Seam Carving.
Вот эту часть не понял: надо увеличивать изображение поэтапно, так, чтобы на каждом этапе охватывалось как можно больше «не важных» частей изображения, и как можно меньше «важных»
Если увеличивать изображение сразу 100%->200%, то получится такой результат, как показано на рисунке: ipicture.ru/uploads/090107/32689/wMr4XEkBZ6.jpg.
При поэтапном увеличении изображение надо сначала увеличить, например, так: 100%->150%, а потом результат увеличить снова: 150%->200%. Тогда получиться результат, как тут: s1.ipicture.ru/uploads/090107/32689/Tjib6T1n3R.jpg.
При поэтапном увеличении изображение надо сначала увеличить, например, так: 100%->150%, а потом результат увеличить снова: 150%->200%. Тогда получиться результат, как тут: s1.ipicture.ru/uploads/090107/32689/Tjib6T1n3R.jpg.
Что происходит на каждом этапе? Пути с наименьшим энергетическим уровнем тупо клонируются по горизонтали? Мне кажется что не так, потому что тогда на следующем проходе мы найдём те же линии и клонируем их снова. В результате образуются заметные размазывания.
Да, вы совершенно верно заметили, что каждый раз будут копироваться одни и те же линии, что и показано на рисунке ipicture.ru/uploads/090107/32689/Uiu6uRSUTT.jpg.
А чтоб так не происходило, мы выбираем не одну минимальную цепочку, а столько, сколько надо для увеличения. Например если мы увеличиваем от 100px до 120px, то выбираем 20 цепочек с минимальной энергией, и их копируем (точнее даже не копируем, а смешиваем их с соседями — смотрите реализацию функции PartialEnlarge в исходниках, хотя можно и просто копировать, но результат чуть хуже выйдет).
А чтоб так не происходило, мы выбираем не одну минимальную цепочку, а столько, сколько надо для увеличения. Например если мы увеличиваем от 100px до 120px, то выбираем 20 цепочек с минимальной энергией, и их копируем (точнее даже не копируем, а смешиваем их с соседями — смотрите реализацию функции PartialEnlarge в исходниках, хотя можно и просто копировать, но результат чуть хуже выйдет).
Прикольный алгоритм, было — harungo.cn/v.php?id=624a4b051ee2a67399070d5a953b3071, стало — harungo.cn/v.php?id=fdce7725eabe71f00d5a7ba6e7bd3002
Спасибо огромное! Давно интересовала реализация этой идеи
Проделана отличная работа. Теперь-то мы знаем, как насолить Яндексу с его дубликатами картинок ;)
Все здорово, прямо-таки чудесно, только одно замечание: желательно вынести в отдельный раздел как можно более все использованные источники, ибо часто это сильно повышает суммарную полезность любой публикации.
Вопрос по делу: почему бы не перейти в пространство HSI и во всех расчетах учитывать только канал яркость (I)?
Вопрос по делу: почему бы не перейти в пространство HSI и во всех расчетах учитывать только канал яркость (I)?
> почему бы не перейти в пространство HSI и во всех расчетах учитывать только канал яркость (I)
В принципе так сделать можно, но качество, думаю, тогда ухудшиться, поскольку мы не будем использовать информацию про цвет: если в изображении встретиться переход, например, с зеленого на синий с одинаковыми значениями яркости, то алгоритм посчитает, как будто там нет перехода.
Если у нас есть информация про цвет, то лучше ее использовать.
В принципе так сделать можно, но качество, думаю, тогда ухудшиться, поскольку мы не будем использовать информацию про цвет: если в изображении встретиться переход, например, с зеленого на синий с одинаковыми значениями яркости, то алгоритм посчитает, как будто там нет перехода.
Если у нас есть информация про цвет, то лучше ее использовать.
Недавно вплотную занимался как раз численной оценкой структурных искажений в изображениях, так что могу сказать уверенно: цвет как таковой особой инфрмативной составляющей не несет, а держать в памяти и тем более обрабатывать три цветовых слоя вместо одного уместно далеко не всегда.
Вполне возможно, я этим вопросом детально не занимался.
Но что касается данного алгоритма (в частности моей реализации) — то использование только яркости, вместо RGB ощутимого преимущества в скорости и памяти не даст, поскольку почти все вычисления производятся над вспомагательными матрицами, а оригинал изображения используеться только для вычисления энергий вначале работы алгоритма и формировании конечного изображения, а это не самые ресурсоемкие операции.
Поэтому если изображение уже находится в HSI, тогда есть смысл использовать только яркость, а если оно в RGB, то смысла в конвертации почти нет, хотя это еще зависит и от задачи, нельзя дать универсальный рецепт на все случаи жизни.
Но что касается данного алгоритма (в частности моей реализации) — то использование только яркости, вместо RGB ощутимого преимущества в скорости и памяти не даст, поскольку почти все вычисления производятся над вспомагательными матрицами, а оригинал изображения используеться только для вычисления энергий вначале работы алгоритма и формировании конечного изображения, а это не самые ресурсоемкие операции.
Поэтому если изображение уже находится в HSI, тогда есть смысл использовать только яркость, а если оно в RGB, то смысла в конвертации почти нет, хотя это еще зависит и от задачи, нельзя дать универсальный рецепт на все случаи жизни.
Огромное спасибо! Одна из самых познавательных и качественных статей Хабры за последние месяца 2.
Спасибо за статью. А где в фотошопе такая фича?
Не могу сказать точно, где оно, потому что последний фотошоп, который я видел был 7.0, а фича появилась только в CS4, но можете посмотреть на этом видео: www.youtube.com/watch?v=019mu8FTy6M. Там показано, как пользоваться фичей.
Или поищите по ключевым словам «Photoshop CS4 Content Aware Scaling»
Спасибо! Я создал себе помощника.
Очень интересная статья, спасибо!!! Автору респект!
Отличная тема! Вот за такие вещи надо повышать карму :) От себя добавлю, что узнал об этом алгоритме около года назад, когда искал плагины к GIMP. Так вот подобный плагин я нашёл (он кажется так и называется liquid resize), а скомпилировать его не получилось. Сейчас вроде бы этот плагин в репозиториях мандривы и убунту встречался…
Если у кого есть какой-либо опыт использования плагина — напишите обзор или хотя бы пару строк и скрины. Будет очень интересно.
Если у кого есть какой-либо опыт использования плагина — напишите обзор или хотя бы пару строк и скрины. Будет очень интересно.
Познавательно! Спасибо! Интересно читать про основы алгоритмов, которые лежат в основе утилит, реально помогающих в обработке данных.
Автору спасибо, но вообще-то свободных реализаций алгоритма уже есть с полдюжины — от наиболее популярного Liquid Rescale для гимпа и написанной его же автором библиотекой liblqr, попутно используемой в ImageMagick до менее известной SeamCarvingGUI или упомянутых выше экзерсисов с петоном. Было бы неплохо упомянуть для очистки совести хотя бы :)
Суть статьи была не в написании очередной утилиты по SeamCarving, а в описании самого алгоритма, поэтому я и не стал делать обзор готовых решений. А тот, кому надо будеть использовать подобную утилиту для работы, сможет все, что его интересует, найти в гугле. Кстати, в конце статьи я упомянул извесные на тот момент мне реализации — фотошоп и rsizr.com.
(конечно есть еще Photoshop и rsizr.com/, но в этих случаях у вас нет исходников);
Если же вы об этом, то я додал ссылки на свободные реализации алгоритма.
написано великолепно, даже я — нуб нубом — с удовольствием и интересом прочитал
Статья написана хорошо и понятно. Пишите еще.
Небольшой совет автору:
Когда выкладываете изображения для сравнения качества, формат png24 использовать предпочтительнее, чем jpeg
Когда выкладываете изображения для сравнения качества, формат png24 использовать предпочтительнее, чем jpeg
блять, где рисунки, автор!?
Уже на месте. Если все же не видно, статью можно также прочитать в Хабрадайджесте
Перезалейте изображения если они еще остались, пожалуйста.
Да, изображения ушли вместе с ipicture. Можете прочитать статью полностью с рисунками тут
Ни бинарики, ни исходники уже не скачать. Не могли бы вы их перезалить на гитхаб или еще куда-нибудь «навсегда».
И еще:
А какой результат будет качественней при уменьшении на n пикселей?
И еще:
Хочу обратить внимание, что операция уменьшения изображения на n пикселей и операция уменьшения изображения на 1 пиксел n раз не являются эквивалентными. Их отличие в том, что если мы уменьшаем на 1 пиксел n раз, то мы для каждой из промежуточных изображений ищем энергию пикселей, а если сразу уменьшаем на n, то энергии пикселей мы берем из исходного изображения.
А какой результат будет качественней при уменьшении на n пикселей?
Sign up to leave a comment.
Делаем Liquid Resize своими руками