войти зарегистрироваться

Алгоритмы whois

индекс
313,66

Делаем Liquid Resize своими руками

Вы наверное уже слышали о технологии масштабирования Liquid Resize, которая учитывает содержимое изображения. Если вам интересно как оно все работает и как можно реализовать все это самому, то читайте далее (осторожно, много рисунков).


(НЛО прилетело и растянуло этот рисунок здесь)
Статья выложена мной по просьбе моего друга, который не может поместить ее на хабр, поскольку не имеет аккаунта. Благодаря вашим плюсам у автора появился инвайт, и он теперь с нами: Kotter.


Содержание


  • Что такое Seam Carving?
  • Несколько замечаний по прочтению статьи
  • Общая схема алгоритма
  • Вычисление энергии точек
  • Нахождение цепочки с минимальной суммарной энергией
  • Уменьшение рисунков
  • Увеличение рисунков
  • Примеры
  • Итоги

Что такое Seam Carving?


Seam Carving — это алгоритм изменения размеров изображения, который учитывает содержимое изображения (как называют авторы — Content-Aware Image Resizing Algorithm). Впервые был продемонстрирован в 2007 году и вызвал немалый интерес. Наверное многие читатели Хабра про него слышали, поскольку тут уже были статьи на эту тему.

Возникает тогда вопрос: как же этот алгоритм учитывает содержимое изображений? В теории тут все просто — сначала вычисляется важность разных участков изображения, после чего изменяются в размере только те части, которые, по мнению алгоритма, являются не такими важными. На практике же для реализации этого алгоритма надо решить ряд вопросов: как определить насколько важными являются части изображения, как найти и сжать менее важные участки изображения и т. д.

В этой статье я попытался ответить на эти, а также на ряд других вопросов, возникающих при решении данной задачи.

Те, кто уже сейчас хотят посмотреть что у меня в итоге получилось, могут в конце статьи найти примеры изображений и демо-программу с прокомментированными исходниками.

Несколько замечаний по прочтению статьи


Перед самой статьей хочется оговорить некоторые условности.

Во-первых. В статье я часто использую термин «энергия», хотя и не уверен в правильности этого термина. А использую я его потому, что сами авторы называют это английским словом «energy». Энергия точки означает ее важность в изображении. Чем больше энергия — тем важнее точка.

Во-вторых. В статье рассматривается только изменение размера по-горизонтали. При одновременном изменении размера по обоих направлениях принцип остается тот-же, только мы теперь рассматриваем не только вертикальные цепочки пикселей, но и горизонтальные.

В-третьих. У меня нету опыта написания под C#/.NET. Выбор платформы/языка написания программы был обусловлен простотой кода для понимания и широким охватом аудитории. Поэтому если я что-то написал в программе неэффективно или не «по дотнетовски», то не обращайте на это внимание. Не в этом суть программы.

В-четвертых. Русский для меня не родной язык, поэтому извините за возможные ошибки.

И последнее. Код программы не оптимален. Между простотой кода и оптимальностью кода я выбирал простоту, поэтому если вы захотите где-то использовать этот алгоритм — оптимизируйте его под свою задачу. Благо простор для оптимизаций там есть.

Вот, собственно, с прелюдией закончили, теперь переходим к самому интересному...

Общая схема алгоритма


Весь алгоритм состоит из таких составных частей:

  1. Нахождение энергии каждой точки. На этом этапе нам надо узнать какие части изображения являются более важными, а какие — менее важными, исходя их этих данных мы в последствии будем менять размер изображения.
  2. Нахождение такой вертикальной цепочки пикселей, чтобы суммарная энергия пикселей, которые входят в эту цепочку была минимальной. Цепочка пикселей — это такой набор пикселей, что в каждой строке выбрано ровно по одному пикселю, и соседние пикселы в ней соединены сторонами или углами. Если мы найдем такую цепочку то сможем ее удалить из изображения, при этом минимально затронув информационное наполнение изображения.
  3. Когда мы нашли цепочку с минимальной энергией, то нам остается ее только удалить, если нам надо уменьшить изображение, или растянуть, если надо увеличить изображение.

Теперь рассмотрим каждый пункт более детально.

Вычисление энергии точек


Первым делом нам надо решить какие участки изображения важны, а какие не очень.

Для решения этой задачи авторы алгоритма предлагают для каждого пикселя посчитать его «энергию» — то есть какой-то условный показатель (в попугаях), который буде показывать важен ли данный пиксел в данном изображении, или не очень.

В принципе способов это сделать много: от самых простых (например посчитать изменения цвета по сравнению с соседними) до достаточно сложных (например сделать анализ акцентирования внимания человека). По словам самих авторов, они проверили множество функций энергии, и одна из самых простых функций дала один из лучших результатов. Поэтому мы воспользуемся сейчас этой функцией. Вот она:


Если вы при виде данной формулы с производными испугались, что вам надо будет вспоминать матанализ, то зря. На самом деле она формулируется достаточно просто: энергия пикселя равна изменению цвета соседних пикселей по сравнению с данным пикселом. То есть чем больше разница в цвете между данным пикселем и соседними — тем больше его энергия.

Теперь рассмотрим реализацию вычислений энергии на практике. Пусть точки изображения характеризуются своей интенсивностью. У нас есть следующее изображение размером 3х3 точки:



Сначала посчитаем по модулю разницу интенсивностей между пикселем и его соседями (справа и снизу), а потом вычислим энергию этого пикселя как среднее арифметическое этих значений.



Для выделенного пикселя: разница между ним и соседом справа — 8, соседом снизу — 3. Среднее арифметическое — (8+3)/2 = 5.5. Но поскольку с целыми числами работать удобнее и быстрее, а такая точность излишняя, то отбросим дробную часть. То есть энергия выделенного пикселя равна 5.

Аналогично посчитаем для остальных пикселей. При этом пиксели, которые крайние справа и крайние снизу будут иметь только соседа справа или снизу, поэтому для них значение разницы и будет средним арифметическим. Для пикселя в правом-нижнем углу таких соседей вообще нет, поэтому мы просто примем его энергию за 0. Хотя теоретически можно и для него посчитать энергию, но не будем усложнять себе жизнь, поскольку на практике им можно пренебречь.

В результате получим следующую матрицу энергий пикселей:



Если же у нас пиксели характеризуются не просто интенсивностью, а значением интенсивности отдельно для R, G, B, то энергия пикселя равна сумме энергий по каждой из компонент.
Пример карты энергий для изображения:



На этой картинке чем темнее цвет на карте энергий — тем больше энергия.

Я реализовал нахождение энергий пикселей с помощью следующей функции:
private void FindEnergy()
{
  for (int i = 0; i < imgHeight; i++)
    for (int j = 0; j < imgWidth; j++)
    {
      energy[i, j] = 0;

         // Считаем отдельно для компонент R, G, B
      for (int k = 0; k < 3; k++)
      {
        int sum = 0, count = 0;

          // Если пиксел не крайний снизу, то добавляем в sum разность между текущим пикселом и соседом снизу
        if (i != imgHeight - 1)
        {
          count++;
          sum += Math.Abs((int)image[i, j, k] - (int)image[i + 1, j, k]);
        }

          // Если пиксел не крайний справа, то добавляем в sum разность между поточным пикселом и соседом справа
        if (j != imgWidth - 1)
        {
          count++;
          sum += Math.Abs((int)image[i, j, k] - (int)image[i, j + 1, k]);
        }

          // В массив energy добавляем среднее арифметическое разностей пикселя с соседями по k-той компоненте (то есть по R, G или B)
        if (count != 0)
          energy[i, j] += sum / count;
      }
    }
}

* This source code was highlighted with Source Code Highlighter.

Функция работает с глобальными переменными: energy — массив, в который записываются энергии и image — массив, в котором хранится изображение.

Нахождение цепочки с минимальной суммарной энергией


У нас уже есть значения энергий для каждого пикселя, но теперь нам надо выбрать те пиксели у которых значение энергии минимальное. Но если мы начнем забирать/добавлять произвольные пиксели, то само изображение у нас просто расползется, и деформируется до неузнаваемости. Конечно такой результат нам не подходит. Поэтому сначала надо выбрать цепочку пикселей, а потом уж их удалять или прибавлять. При чем не произвольную цепочку, а «правильную».

«Правильная» цепочка — это набор точек, такой, что в каждой строчке изображения выбран ровно 1 пиксел, а пикселы в соседних строчках «соединены» или сторонами, или углами.

Пример «правильных» цепочек:



Пример «неправильных» цепочек:



Теперь мы знаем, что удалять надо «правильные» цепочки, тогда мы не сильно испортим изображение. Но какую цепочку тогда выбрать? Авторы алгоритма предлагают выбрать для удаления/растяжение те цепочки, сумма энергий пикселей, которые входят в нее, минимальна.

Отсюда возникает вполне естественный вопрос: как нам найти такую цепочку?

Вариант первый — перебираем все цепочки, их суммируем, и находим с минимальной суммой. Вариант, конечно, интересный, но тогда для обработки даже небольшого изображения нам надо будет ждать вечность :) Если у нас есть вечность в запасе, то пишем код полного перебора, запускаем и ждем. Если вы хотите увидеть результат за более короткий промежуток времени — то читаем дальше.

Тут нам на помощь приходить динамическое программирование. Не буду углубляться в детали, и показывать в чем именно «динамичность» программирования (кстати термин «программирование» тут отношения к написанию кода не имеет), и сразу перейду непосредственно к алгоритму. Если кто-то не знает, что такое «динамическое программирование» и хочет узнать — может почитать об этом на Википедии, или других источниках.

Сначала мы создадим новый массив, который по размеру равен массиву с энергиями пикселей. В этот массив мы для каждого пикселя запишем сумму элементов минимальной цепочки пикселей, которая начинается у верхнего края изображения и заканчивается на данном пикселе.

Покажем процесс вычисления на примере. Пусть у нас есть массив с значениями энергий для каждого пикселя:



Будем вычислять элементы этого массива по строчкам — от первой к последней. Для верхней строчки элементы данного массива будут равны элементам массива, поскольку из каждого такого элемента можно только 1 цепочку построить (все единичной длины):


Теперь вычислим вторую строчку. Рассмотрим выделенную ячейку. Мы, чтобы построить цепочку от этой ячейки, можем пойти тремя способами, как показано на рисунке. Из этих трех способов нам надо выбрать минимальный (поскольку ми считаем суммы именно минимальных цепочек). Для выделенной ячейки это будет цепочка с суммой 3, и к этой цепочке прибавляем энергию самой ячейки. Поэтому в эту ячейку запишем число 7 (сумма 3 и 4). Аналогично посчитаем все суммы для всех элементов второй строки:


Перейдем к третьей строчке. В принципе, третья строчка считается аналогично второй. Снова рассмотрим выделенную ячейку. От нее мы можем образовать такие цепочки:
  • эта ячейка плюс минимальная цепочка длинны 8;
  • эта ячейка плюс минимальная цепочка длинны 6;
  • эта ячейка плюс минимальная цепочка длинны 7;
Из этих вариантов опять выбираем минимальный (6) и прибавляем к энергии самой ячейки (6). Получаем значение этой ячейки равно 12. Аналогично считаем остальные элементы третьей строчки.

После вычисления таким образом всех строчек мы получим в результате следующий массив:


Если формализовать вычисление этого массива, то получим следующую формулу:



где s — наш массив сумм, а e — массив энергий.

Мой вариант реализации вычисления массива сумм:

private void FindSum()
{
     // Для верхней строчки значение sum и energy будут совпадать
   for (int j = 0; j < imgWidth; j++)
     sum[0, j] = energy[0, j];

     // Для всех остальных пикселей значение элемента (i,j) массива sum будут равны
     //  energy[i,j] + MIN ( sum[i-1, j-1], sum[i-1, j], sum[i-1, j+1])
   for (int i = 1; i < imgHeight; i++)
     for (int j = 0; j < imgWidth; j++)
     {
       sum[i, j] = sum[i - 1, j];
       if (j > 0 && sum[i - 1, j - 1] < sum[i, j]) sum[i, j] = sum[i - 1, j - 1];
       if (j < imgWidth - 1 && sum[i - 1, j + 1] < sum[i, j]) sum[i, j] = sum[i - 1, j + 1];

       sum[i, j] += energy[i, j];
     }
}

* This source code was highlighted with Source Code Highlighter.

Функция работает с глобальными переменными: energy — массив, в котором записаны энергии и sum — массив, в который записываются значения сумм.
Теперь, когда у нас уже есть этот массив, настало время задуматься — а для чего он вообще нам надо? Отвечу — по этому массиву мы теперь можем быстро найти цепочку с минимальной суммой энергий.

Сначала мы найдем какой пиксел из нижней строчки изображения принадлежит этой цепочке: элемент, что мы ищем, будет иметь наименьшее значение в массиве сумм среди элементов нижней строчки. Почему? Вспомните, что в данном массиве записаны значения сумм элементов минимальных цепочек от верхнего края до данного пиксела. Цепочки, которые нас интересуют заканчиваются на пикселе из последнего ряда. Соответственно для всего рисунка минимальная цепочка будет выбрана как минимальная из всех минимальных цепочек, которые заканчиваются на пикселях из нижней строчки.

Для нашего примера это будет следующий элемент:


Мы уже знаем на каком пикселе заканчивается минимальная цепочка, теперь мы можем найти пиксел из предпоследней строчки. Как уже было написано, из нижнего пиксела мы можем пойти только в 3 соседние пиксели на строчку выше: слева-сверху, сверху или справа-сверху. Среди этих пикселей выбираем пиксел с минимальным значением в массиве сумм, и переходим к нему. Продолжаем, пока на дойдем до верхней строчки. Процесс показан на следующем рисунке:


После выполнения всех этих операций мы получим то, чего и хотели — набор пикселей, которые мы можем изменить с минимальными потерями для изображения.

Пример минимальной цепочки на рисунке:



Программная реализация алгоритма поиска цепочки:

private int[] FindShrinkedPixels()
{
    // Номер последней строчки
  int last = imgHeight - 1;
    // Выделяем память под массив результатов
  int[] res = new int[imgHeight];

    // Ищем минимальный элемент массива sum, который находиться в нижней строке и записываем результат в res[last]
  res[last] = 0;
  for (int j = 1; j < imgWidth; j++)
    if (sum[last, j] < sum[last, res[last]])
      res[last] = j;

    // Теперь вычисляем все элементы массива от предпоследнего до первого.
  for (int i = last - 1; i >= 0; i--)
  {
      // prev - номер пикселя цепочки из предыдущей строки
       // В этой строке пикселями цепочки могут быть только (prev-1), prev или (prev+1), поскольку цепочка должна быть связанной
    int prev = res[i + 1];
          
      // Здесь мы ищем, в каком элементе массива sum, из тех, которые мы можем удалить, записано минимальное значение и присваиваем результат переменной res[i]
    res[i] = prev;
    if (prev > 0 && sum[i, res[i]] > sum[i, prev - 1]) res[i] = prev - 1;
    if (prev < imgWidth - 1 && sum[i, res[i]] > sum[i, prev + 1]) res[i] = prev + 1;
  }

  return res;
}

* This source code was highlighted with Source Code Highlighter.

Уменьшение рисунков


Мы, наконец-то, нашли цепочку пикселей, c которыми будем работать. Теперь можно вспомнить зачем вообще мы ее искали. Наша задача — изменение размера изображения. Увеличение и уменьшение изображение немного отличаются, поэтому сначала рассмотрим уменьшение, а потом уже увеличение.

Если нам надо уменьшить ширину картинки на 1 пиксел, то тут все просто: находим вертикальную цепочку, как это описывается выше, и просто удаляем ее из изображение. Я реализовал эту операцию с помощью следующего цикла:

for (int i = 0; i < imgHeight; i++)
   for (int j = cropPixels[i]; j < imgWidth; j++)
   {
     pImage[i, j] = pImage[i, j + 1];
   }

* This source code was highlighted with Source Code Highlighter.

В i-м элементе массива cropPixels записан номер столбика пикселя, который мы удаляем из i-й строчки.  А сам цикл делает следующее: все пиксели, которые записаны справа от тех, которых удаляем, мы сдвигаем на одну точку влево. В результате этой операции наша цепочка пикселей будет удалена из изображения.

Если нам надо уменьшить изображение не на 1 пиксел, а на большее значение, то выполняем операцию удаления цепочки столько раз, сколько надо (каждый раз при этом нам надо будет эту цепочку искать).

Хочу обратить внимание, что операция уменьшения изображения на n пикселей и операция уменьшения изображения на 1 пиксел n раз не являются эквивалентными. Их отличие в том, что если мы уменьшаем на 1 пиксел n раз, то мы для каждой из промежуточных изображений ищем энергию пикселей, а если сразу уменьшаем на n, то энергии пикселей мы берем из исходного изображения.

Увеличение рисунков


Уменьшать изображения мы уже умеем, теперь надо выяснить, как же их надо увеличивать.

Первое, что приходит на ум — это точно так же, как и при уменьшении, выбирать цепочки и их «растягивать». Но если мы это реализуем мы получим такой результат:



Как мы видим, программа просто взяла один столбик и его растянула, а это не совсем то, что нам надо.

Следующая мысль может быть, например, такой: надо брать не одну минимальную цепочку, а столько, сколько надо, чтобы дополнить рисунок до нужной ширины. Допустим мы реализовали данный алгоритм, но что будет, если мы увеличим рисунок в 2 раза?



Как видно из этого рисунка — мы просто выбрали все точки, и растянули их по горизонтали, но это тоже не совсем то, что нам надо, поскольку этот способ не отличается от обычного растягивания.

Но в принципе сама идея последнего способа правильная, но с небольшим изменением: нам надо увеличивать изображение поэтапно, так, чтобы на каждом этапе охватывалось как можно больше «не важных» частей изображения, и как можно меньше «важных». Тогда возникает вопрос, как разбить процесс увеличение на этапы? Вариантов много — от разбиения на этапы вручную, до написания каких-то эвристических анализаторов. Но в своей программе я написал просто — разбивание на этапы происходит таким образом, чтобы на каждом этапе изображение не увеличивалось больше, чем на 50%. Иногда это дает приемлемый результат, иногда не очень, но, как я уже написал, вариантов реализации разбиения на этапы можно придумать много.

Если увеличить таким образом нашу картинку с НЛО, то получим следующий результат:



Как видим, НЛО, человек и дерево остались не измененными.

Примеры


Все примеры масштабирования рисунков были получены с помощью программы, которую я написал параллельно с этой статьей, реализовав алгоритмы, которые здесь описываются.

Исходники и бинарник программы можете скачать внизу статьи.

Классический пример Content-Aware Resizing'а:



На следующей картинке ярко выражены «важные» объекты и фон.


(оригинал) (уменьшено) (увеличено)

Рисунок звездного неба. При изменении размера, форма звезд почти не изменяется.


(оригинал) (уменьшено) (увеличено)

И еще пример масштабирования двух фотографий, сделанных gmm.


(оригинал) (уменьшено) (увеличено)



(оригинал) (уменьшено) (увеличено)


Итоги



Итак, что же мы получили в результате:
  • Знание принципа работы такого интересного и полезного алгоритма, как Seam Carving;
  • Программку, в которой можно поиграться в изменителя размеров изображений (конечно есть еще Photoshop и http://rsizr.com/, но в этих случаях у вас нет исходников);
  • Простор для воображения по возможным улучшениям алгоритма (например можно детектор лиц к нему прицепить, результаты, думаю, будут получше);
  • Знание, что Content-Aware Rescale в Photoshop это не особая фотошоповская магия, а обычный алгоритм, который поддается пониманию.

Спасибо тем, кто дочитал статью до конца, надеюсь было интересно.


P. S.


Исходники (VS 2008)
Бинарник (.NET)

upd
Полезные линки по теме:Список может пополнятся.
+223
7 января 2009, 15:53
GMM

комментарии (122)

  • Чем-то напомнило фрактальное масштабирование.
  • раскрыть комментарий
    • Этот алгоритм практически так и делает, даже чуть больше. Он сам «ищет» участки, которые можно растянуть. Кроме того он может растягивать не только строго вертикальные участки. Например картинку со звездным небом таким способом, как описали вы, уже не растянуть.

      А насчет сложности — может оно не так и сложно, просто я постарался детально описать, чтобы меньше вопросов оставалость после прочтения.
      • Узнаю старый добрый Хабрахабр… (скупая мужская слеза)
    • Тут работает золотое правило программиста: Лучше день потерять, а потом за 5 минут долететь.
      Ручками можно сделать всё… вообще говоря, большие числа можно и без калькулятора делить… столбиком на бумажке…
      но куда элегантней реализовать это в алгоритме.
      :)
  • Офигенно. Спасибо.
  • Класс! Пойду попробую на чем нибудь реализовать! Спасибо!
  • шикарно. спасибо
  • Побежал реализовывать на питоне
    • Боюся, что на Питоне будет большая проблема с быстродействием. Лучше реализовать самые «тяжелые» операции на С/С++ и сделать интерфейс к Питону.
      • Ну если человеку не для производства надо, то почему бы и не реализовать. Интересно ведь :)
        • я изучаю питон. все же приятней написать такой алгоритм, а не какий нибудь обсчет октарного дерева :)
          • Октарное дерево тоже неплохо сделать, если есть интересное применение. Например, когда игрушку пишешь на чистом D3D или OpenGL…
            • Ага, OpenGL. Я давным давно тетрарным деревом обрезал невидимые части ландшафта.
              • Знакомо :)
    • Всё уже придумано :)

      blog.eikke.com/index.php/ikke/2007/09/02/seam_carving_content_aware_image_resizin
  • Классная статья. У меня дурацкий вопрос: нафига на два делить, а потом отбрасывать дробную часть, если важно распределение значений?
    • Дело в том, что там делится не всегда на 2, а на количество посчитаных соседей. Для большинства пикселей мы считаем по два соседа, но для крайних может быть и меньше.
      • а почему два соседа используется? Почему не все 4?
        • Можно использовать и все 4 соседа, и даже все 8 :)
          Но мне кажется, что 4 соседа мало чего поменяют, поскольку суммы с верхним и левим соседом учитываются когда мы считаем их энергии.

          Хотя да, если считать 4 соседа, то ничего плохого не будет :)
          • Ну как мало чего поменяют — минимальные цепочки иногда другие будут. А что визуально лучше — надо смотреть, зависит от картинки скорее всего.

            Вообще производную можно оценивать по-разному. Возможно, для большинства картинок это лучше делать по большей окрестности точки; хотя черт его знает.
            • Не буду с вами спорить, поскольку согласен с вами, некоторые изменения действительно будут.

              А еще лучше, как подсказал Toshas, использовать оператор Sobel: en.wikipedia.org/wiki/Sobel_operator (англ).

              Но в статье я использовал только два соседа, чтобы излишне не усложнять, так как двух соседей хватает для приемлемого качества.
      • Понял, спасибо.
  • НЛО прилетело и растянуло этот рисунок здесь!
  • уже знаю где применю это )
    • как-то давно это предполагалось использовать в инете на резиновых сайтах. ну чтобы это поддерживалось браузерами
  • Кстати, на последних двух снимках — львов?
    • Да, Львов.
    • тоже хотел задать этот вопрос (=
  • а как насчет двунаправленного растягивания?
    • растянуть прогой, повернуть, ещё раз применить прогу (-;
      • ну это напрашивается само собой ) интересно посмотреть на результат )
    • Я не хотел про него писать, потому что статья и так достаточно большая вышла. Если вкратце, то есть 2 способа двунаправленого растягивания:
      1. Растянуть до нужного размера обычным растягиванием, сохранив пропорции, а потом применить этот способ.
      2. Растягивать точно также, как и в случае одного направления, только одновременно искать как вертикальные, так и горизонтальные цепочки, и выбирать среди них постоянно минимум. Единственное замечание — если картинка не квадратная, то надо будет эти значения как-то нормализировать, например помножив суммы по горизонталных цепочках на высоту, а по вертикальных — на ширину.

      Если владеете английским, то можете про это почитать тут: PDF от авторов
      • вот как раз второй способ инетересен. Или же искать и выкидывать одновременно, или же по очереди. Но тогда имеет ли значение порядок (гориз/верт)? Если же одновременно искать, то как быть если по вертикали и горизонтали разное количество выкидывать надо?
        • Не совсем понял, что имеется ввиду по «одновременно, или же по очереди».

          Порядок выкидывания имеет значение, поэтому надо делать по такому алгоритму:
          1. Вычисляем какую цепочку лучше удалить — вертикальную или горизонтальную.
          2. Удаляем.
          3. Пока не урезали картинку до нужного размера — к пункту 1.
  • НЛО прилетело и опубликовало эту надпись здесь.
    • хабрачую
  • Инвайта автору статьи!
  • Ну, почти получилось…
    stratero.ru/homm/SeamCarving.jpg
    • :)
    • :)

      Для таких случаев использование алгоритма комбинируется с ручной расстановкой зон, которые нельзя трогать. Похожый эффект бывает, если растягивать фотографию человека в лесу. Тогда алгоритм считает человека второстепенным объектом и тоже растягивает его.
      • а может она такая на самом деле? ;)
        шутка конечно, но получилось забавно
    • Индусу повезло меньше ipicture.ru/uploads/090107/QS61UIA3uh.jpg ))
    • l2k
    • l2k
    • 7 января 2009, 17:02
    • #
      • 0
    Отличная статья и результат!
    Спасибо большое!
  • Мегастатья, спасибо, очень интересно!
  • У меня на аукцион народ фотки лотов загружает всевозможных форматов (соотношений сторон).

    Может попробовать этим алгоритмом их приводить к стандарту для более стройного дизайна страницы — имеются в виду превьюшки маленькие, конечно.
    • только тогда надо дать возможность менять пользователям алгоритмы, ибо иногда этот может давать ошибочные результаты, как было видо из комментариев выше.
      • Да.
        Было бы неплохо еще как то автоматически понимать. Пригодна ли данная фотография для этого метода или нет.
    • да
    • нет
  • НЛО прилетело и опубликовало эту надпись здесь.
    • В этом нет смысла, цепочка и так будет посторяться несколько раз, пока не найдется более дешевая цепочка
      • *повторяться
      • Нужно просто новой цепочке добавлять немного бонусной энергии
        • НЛО прилетело и опубликовало эту надпись здесь.
          • Да, старой тоже конечно надо добавить.
            Смысл в том, что, одна и та же цепочка может разрастаться в случае остутствия достойных альтернатив. А в вашем случае вы принудительно режете картинку даже если остальные цепочки в 100 раз дороже чем дешевая первая
            Например если на картинке есть однородный кусок фона, мой вариант будет только его растягивать, а ваш — растянет несколько раз и пойдет рвать основную картинку. Если же картинка полностью сложная, например лес, то наши результаты будут схожими, я думаю
            • НЛО прилетело и опубликовало эту надпись здесь.
          • А вообще надо экспериментировать конечно, я ведь просто предложио попробовать. Кстати, когда я работал в институте кибернетики, очень похожим методом распознавали горизонт :) Тоже искали пути с минимальной «энергией» от левого края картинки до правого, только энергия немного по-другому вычислялась
            • НЛО прилетело и опубликовало эту надпись здесь.
      • НЛО прилетело и опубликовало эту надпись здесь.
        • Возьмется не более дешевая, а проведенная только что станет чуть дороже, чем какая-то другая, которая до этого была на 2-м месте по цене
          • НЛО прилетело и опубликовало эту надпись здесь.
  • Онлайн ресайз
    rsizr.com/
    • Ага, на флэше и уже года 2 назад

    • спасибо, как раз искал такой сервис!
  • На счет увеличения картинки — чтобы не раслягивалась одна и та же цепочка, попробуйте каждой новой вставленной цепочке искуственно повышать энергию (немножко), тогда алгоритм сам собой будет находить альтернативные цепочки, или тянуть одну, пока она не станет дороже какой-то другой альтернативы.
  • Как автор статьи, благодарю всех за комменты и плюсы. Теперь я один из вас.
    • Спасибо, пишите ещё!
  • При запуске бинарника:
    ---------------------------
    SeamCarving.exe - Ошибка приложения
    ---------------------------
    Ошибка при инициализации приложения (0xc0000135). Для выхода из приложения нажмите кнопку "ОК".
    ---------------------------
    ОК
    ---------------------------
    • Наверное потому, что у меня VS не установлена…
    • Программа написана на Visual C# 2008 Express.
      Для запуска надо .NET Framework, правда не знаю, какой версии, наверное 3.5.
      • Спасибо. Ноутбук чужой, я не знал, что здесь нет НЕТ Фреймфорка. Установил и всё заработало.
  • Спасибо за полезную статью! Узнал много интересного, пишите ещё!
  • Автор молодец, изложил все доступно и понятно. Кстати, для вычисления производных изображения чаще применяют оператор Sobel.
    • Да, наверное для реальных приложений лучше использовать оператор Sobel или Scharr. Я просто хотел максимально упростить статью, чтоб сконцентрироваться именно на самом Seam Carving.
  • Пока на Хабре есть такие статьи и такие авторы, все крики «Хабр стал не тот» предлагаю отправлять в /dev/null. Спасибо!
    • О. Щас пойду плюсану оригинального автора, так как достойны явно оба.
  • Интересная статья, понравилась, жаль что я не могу вам плюсик поставить :(
    • acy
    • acy
    • 7 января 2009, 18:48
    • #
      • +2
    Ты мне шкаф скукожил, демон!

    From bugatak.ru/shared/i.jpg
    To bugatak.ru/shared/i-resized.jpg

    С другой стороны, я как-то по солидней стал.
  • раскрыть комментарий
    • нечестно давать ссылку на ресурс требующий инвайта
    • дай инвайт на лепру
    • Ваш хостинг картинок просит логин/пароль.
    • etc
    • etc
    • 7 января 2009, 19:13
    • #
      • –1
    Жаль не могу поставить +, автору просто нереальный респект. Очень умная статья :)
  • Ценная информация.
    Спасибо.
  • Вот за что надо ноутбуки давать, а не за херню в притчах.
  • шикарно. Алгоритм рулит
    • GMM
    • GMM
    • 7 января 2009, 19:59
    • #
      • +1
    Могу также предложить свою модификацию программы. Она отличается тем что можна мастшабировать изображение обычным методом и паралельно посмотреть результат обработаным алгоритмом Seam Carving.
    • Ааа! Демон, ты мне брата скукожил.
      Было: Hosted on free image hosting Xmages.net
      Стало: Hosted on free image hosting Xmages.net
      • Нда, лучшей иллюстрации к слову «скукожить» мне еще не попадалось
  • Вот эту часть не понял: надо увеличивать изображение поэтапно, так, чтобы на каждом этапе охватывалось как можно больше «не важных» частей изображения, и как можно меньше «важных»
    • Если увеличивать изображение сразу 100%->200%, то получится такой результат, как показано на рисунке: ipicture.ru/uploads/090107/32689/wMr4XEkBZ6.jpg.

      При поэтапном увеличении изображение надо сначала увеличить, например, так: 100%->150%, а потом результат увеличить снова: 150%->200%. Тогда получиться результат, как тут: s1.ipicture.ru/uploads/090107/32689/Tjib6T1n3R.jpg.
      • Что происходит на каждом этапе? Пути с наименьшим энергетическим уровнем тупо клонируются по горизонтали? Мне кажется что не так, потому что тогда на следующем проходе мы найдём те же линии и клонируем их снова. В результате образуются заметные размазывания.
        • Да, вы совершенно верно заметили, что каждый раз будут копироваться одни и те же линии, что и показано на рисунке ipicture.ru/uploads/090107/32689/Uiu6uRSUTT.jpg.

          А чтоб так не происходило, мы выбираем не одну минимальную цепочку, а столько, сколько надо для увеличения. Например если мы увеличиваем от 100px до 120px, то выбираем 20 цепочек с минимальной энергией, и их копируем (точнее даже не копируем, а смешиваем их с соседями — смотрите реализацию функции PartialEnlarge в исходниках, хотя можно и просто копировать, но результат чуть хуже выйдет).
  • Прикольный алгоритм, было — harungo.cn/v.php?id=624a4b051ee2a67399070d5a953b3071, стало — harungo.cn/v.php?id=fdce7725eabe71f00d5a7ba6e7bd3002
    • ага. Тело толстеет, а лицо остается прежним. Весело.
  • Спасибо огромное! Давно интересовала реализация этой идеи
  • Проделана отличная работа. Теперь-то мы знаем, как насолить Яндексу с его дубликатами картинок ;)
  • Все здорово, прямо-таки чудесно, только одно замечание: желательно вынести в отдельный раздел как можно более все использованные источники, ибо часто это сильно повышает суммарную полезность любой публикации.
    Вопрос по делу: почему бы не перейти в пространство HSI и во всех расчетах учитывать только канал яркость (I)?
    • > почему бы не перейти в пространство HSI и во всех расчетах учитывать только канал яркость (I)
      В принципе так сделать можно, но качество, думаю, тогда ухудшиться, поскольку мы не будем использовать информацию про цвет: если в изображении встретиться переход, например, с зеленого на синий с одинаковыми значениями яркости, то алгоритм посчитает, как будто там нет перехода.

      Если у нас есть информация про цвет, то лучше ее использовать.
      • Недавно вплотную занимался как раз численной оценкой структурных искажений в изображениях, так что могу сказать уверенно: цвет как таковой особой инфрмативной составляющей не несет, а держать в памяти и тем более обрабатывать три цветовых слоя вместо одного уместно далеко не всегда.
        • Вполне возможно, я этим вопросом детально не занимался.

          Но что касается данного алгоритма (в частности моей реализации) — то использование только яркости, вместо RGB ощутимого преимущества в скорости и памяти не даст, поскольку почти все вычисления производятся над вспомагательными матрицами, а оригинал изображения используеться только для вычисления энергий вначале работы алгоритма и формировании конечного изображения, а это не самые ресурсоемкие операции.

          Поэтому если изображение уже находится в HSI, тогда есть смысл использовать только яркость, а если оно в RGB, то смысла в конвертации почти нет, хотя это еще зависит и от задачи, нельзя дать универсальный рецепт на все случаи жизни.
  • Огромное спасибо! Одна из самых познавательных и качественных статей Хабры за последние месяца 2.
  • Спасибо за статью. А где в фотошопе такая фича?
    • Не могу сказать точно, где оно, потому что последний фотошоп, который я видел был 7.0, а фича появилась только в CS4, но можете посмотреть на этом видео: www.youtube.com/watch?v=019mu8FTy6M. Там показано, как пользоваться фичей.
      • Спасибо, просто потрясающе!
    • Или поищите по ключевым словам «Photoshop CS4 Content Aware Scaling»

  • Спасибо! Я создал себе помощника.
  • Очень интересная статья, спасибо!!! Автору респект!
  • Отличная тема! Вот за такие вещи надо повышать карму :) От себя добавлю, что узнал об этом алгоритме около года назад, когда искал плагины к GIMP. Так вот подобный плагин я нашёл (он кажется так и называется liquid resize), а скомпилировать его не получилось. Сейчас вроде бы этот плагин в репозиториях мандривы и убунту встречался…

    Если у кого есть какой-либо опыт использования плагина — напишите обзор или хотя бы пару строк и скрины. Будет очень интересно.
    • А сам алгоритм — благодатная почва для различных курсовых и дипломных работ по профилю.
    • Liquid Rescale всё-таки :)
  • Познавательно! Спасибо! Интересно читать про основы алгоритмов, которые лежат в основе утилит, реально помогающих в обработке данных.
  • Автору спасибо, но вообще-то свободных реализаций алгоритма уже есть с полдюжины — от наиболее популярного Liquid Rescale для гимпа и написанной его же автором библиотекой liblqr, попутно используемой в ImageMagick до менее известной SeamCarvingGUI или упомянутых выше экзерсисов с петоном. Было бы неплохо упомянуть для очистки совести хотя бы :)
    • Суть статьи была не в написании очередной утилиты по SeamCarving, а в описании самого алгоритма, поэтому я и не стал делать обзор готовых решений. А тот, кому надо будеть использовать подобную утилиту для работы, сможет все, что его интересует, найти в гугле. Кстати, в конце статьи я упомянул извесные на тот момент мне реализации — фотошоп и rsizr.com.
    • (конечно есть еще Photoshop и rsizr.com/, но в этих случаях у вас нет исходников);

      Если же вы об этом, то я додал ссылки на свободные реализации алгоритма.
      • Да, я именно об этом :) Спасибо :)
  • написано великолепно, даже я — нуб нубом — с удовольствием и интересом прочитал
  • Статья написана хорошо и понятно. Пишите еще.
  • Небольшой совет автору:
    Когда выкладываете изображения для сравнения качества, формат png24 использовать предпочтительнее, чем jpeg
  • блять, где рисунки, автор!?
    • Уже на месте. Если все же не видно, статью можно также прочитать в Хабрадайджесте
Только авторизованные пользователи могут оставлять комментарии. Авторизуйтесь, пожалуйста.