Компьютерная Графика и Мультимедиа Сетевой журнал

Уравнение Пуассона

Уравнение Пуассона – дифференциальное уравнение в частных производных. С его помощью можно описать некоторые физические процессы и явления, такие как стационарное поле температуры и электростатическое поле. Общий вид уравнение Пуассона выглядит следующим образом: . Неизвестной функцией здесь выступает функция f. Зачастую уравнение решают на каком-то ограниченном множестве. В таком случае, чтобы решение уравнения Пуассона было точно определено, надо добавить краевые условия. Эти условия бывают трех видов: Дирихле, когда ограничения накладываются на саму функцию f на границе, Неймана, когда условия накладываются на ее производную f', и смешанные:

• Дирихле:
• Неймана:
• Смешанные.

Здесь – граница рассматриваемой области, а f*– некоторая известная функция.

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

Восстановление изображения по векторному полю градиентов

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

Пусть изображение – замкнутое подмножество , с границей (Рис. 1). Пусть f – неизвестная скалярная функция, заданная внутри . Наконец, пусть v – векторное поле, заданное на . Необходимо восстановить функцию f, векторное поле градиентов которой равно v.

Рис. 1: Начальные условия задачи.

Проблема в том, что v необязательно интегрируема. То есть может не существовать такой функции f, что . Это следует из того, что для f должно выполняться условие . А значит для интегрируемости v необходимо условие , что совсем необязательно для произвольной v.

Тогда можно найти такую потенциальную функцию f, градиент которой наиболее близок к v. То есть надо минимизировать следующий интеграл:

Функция f, минимизирующая полученный интеграл, должна удовлетворять уравнению Эйлера-Лагранжа.

При замене в этом выражении F получается следующая формула:

В итоге решение сводится к известному уравнению Лапласа .

Чтобы доопределить задачу, следует добавить краевые условия.

• Дирихле:
• Неймана:
• Смешанные.

Здесь – граница рассматриваемой области, а f*– некоторая известная функция. В случае краевых условий Неймана решении определено с точностью до константы. Более того, для существования решения при краевых условиях Неймана интеграл у функции f* по контуру границы должен быть равен 0.

Удобство уравнения Пуассона заключается в существовании достаточно хороших алгоритмов его решения в дискретном случае. Пусть теперь S и – конечные множества точек на дискретной плосткости. – множество соседей пикселя при 4-связности. Уравнение Пуассона в дискретном случае преобразуется в систему линейных уравнений, где число переменных равно числу пикселей в . В случае краевых условий Дирихле – это выглядит так:

Здесь – это проекция соответсвующего вектора из v на ориентированное ребро . Получившаяся система уравнений имеет единственное решение. Несмотря на большое количество неизвестных, её можно эффективно решить, так как подавляющее большинство коэффициентов равны нулю, то есть, задача свелась к решению разреженной системы линейных уравнений.

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

Теперь перейдем к рассмотрению конкретных статей и алгоритмов.

Poisson Image Editing [1]

В статье Poisson Image Editing авторы предлагают различные инструменты для обработки изображений. Все они основаны на решении уравнения Пуассона. Так как методы из статьи работают с областью, являющейся частью какого-то изображения, то для получения точного ответа используются краевые условия Дирихле: на границе искомая функция должна совпадать с исходными значениями пикселей. В случае, когда область затрагивает границы самого изображения, краевые условия становятся смешанными: на границе считаем, что производная результата но направлению, перпендикулярному самой границе, равна 0. В статье предлагаются методы для решения самых разнообразных задач. Рассмотрим лишь некоторые из них.

Бесшовное клонирование

Этот инструмент позволяет вставить часть одного изображения в другое так, чтобы не было заметно швов. Инструмент как бы подстраивает вставляемую часть под остальное изображение. На самом деле для получения результата используется только градиентное поле вставляемой части и значения пикселей исходного изображения на границе обрабатываемой области. Таким образом получается уравнение Пуассона с краевыми условиями Дирихле.

на , , где g – известное изображение, вставляемое в область , а f* – изображение, в которое вставляем.

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

• Бесшовная вставка новых элементов в изображение. Применяется для создания коллажей и других методов художественной обработки изображений и фотографий (Рис. 2).

  

  Рис. 2: Пример бесшовной вставки нового элемента в изображение.

• Подавление нежелательных артефактов. На области с нежелательными объектами копируются кусочки чистой текстуры с других мест того же изображения. Таким образом можно производить ретуширование и восстановление фотографий (Рис. 3).

  

  Рис. 3: Пример подавления нежелательных артефактов на изображении.

Смешивание градиентов

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

Таким образом, учитываются все большие перепады яркости. Такой инструмент (клонирование с предварительным смешиванием градиентов) позволяет решать несколько задач:

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

  

  Рис. 4: Пример вставки нового объекта в изображении без и с применением техники смешивания градиентов.

• Вставка изображений с дырками. Если не хочется очень точно выделять сложный объект перед клонированием, можно просто применить технику смешивания градиентов (Рис. 5).

  

  Рис. 5: Пример результатов вставки сложного объекта в изображение для различных техник: а) клонирование после цветовой сегментации; b) бесшовное клонировние; c) усреднение результата бесшовного клонирования и начальной текстуры; d) бесшовное клонирование со смешиванием градиентов.

Редактирование областей

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

• Локальные изменения освещения. Преобразуя градиенты по специальному закону можно добиться, как увеличения, так и уменьшения освещенности объекта (Рис. 6).

  

  Рис. 6: Пример локального увеличения яркости.

• Локальные изменения цвета. По разному преобразуя градиенты в разных цветовых каналах, можно перекрашивать выделенные объекты (Рис. 7).

  

  Рис. 7: Пример локального изменения цвета.

Gradient Domain High Dynamic Range Compression [2]

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

1. Переход к изображению логарифмов яркостей.
2. Составление карты градиентов.
3. Изменение градиентов с помощью специальной функции.
4. Восстановления функции по градиентному полю с помощью уравнения Пуассона.
5. Обратный переход от логарифмов.
6. Подгонка изображения под заданный диапазон.

Эти шаги для одномерного случая проиллюстрированы на следующем рисунке (Рис. 8).

Рис. 8:

Пример работы алгоритма по шагам для одномерного случая:
a) График яркостей одной строки HDR-изображения с отношением яркостей 2415:1;
b) Логарифм яркостей H(x);
c) Производная логарифма H'(x);
d) Новая производная G(x), полученная специальным преобразованием;
e) Новый логарифм яркостей, восстановленный с помощью уравнения Пуассона из G(x);
f) Результат – сжатое изображение с диапазоном яркостей 7,5:1;
Все графики кроме с) и d) изображены в разных масштабах.

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

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

Рис. 9: Пример сжатия изображения с расширенным диапазаном яркости, составленного по двум фотографиям с разной экспозицией.

Стоит отметить, что предложенный авторами статьи алгоритм, пригоден не только для сжатия HDR-изображений. Он также дает неплохие результаты на обычных картинках, делая более заметными детали в слишком темных или слишком светлых областях (Рис. 10).

Рис. 10: Пример работы алгоритма для обычного изображения.

Gradient based image completion by solving the Poisson equation [3]

В этой статье решается задача восстановления неизвестной области изображения. В этом направлении существует много других работ. Одной из самых распространенных техник является постепенное заполнение неизвестной области патчами (кусочками изображения), взятыми из остальной части картинки. Алгоритмы, в основном, отличаются порядком заполнения неизвестной области и функцией оценки наиболее подходящего патча. Метод из данной статьи также относится к этому направлению. Главной особенностью его является то, что постепенно заполняются не значения цветов пикселей неизвестной области, а градиенты на ней. То есть в алгоритме сначала полностью восстанавливается векторное поле градиентов изображения методами, сходными с теми, которыми в других алгоритмах восстанавливалась сама картинка. А затем с помощью уравнения Пуассона восстанавливается само изображение (Рис. 11). В результате пиксели неизвестной области не обязательно равны каким-либо пикселям из остальной части изображения, что было одним из главных недостатков предыдущих алгоритмов.

Рис. 11: Пример восстановления текстуры в неизвестной области.

Image Fusion for Context Enhancement and Video Surrealism [4]

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

Итак, пусть есть фоновое изображение, снятое в дневное время, и динамичная ночная сцена. Алгоритм работает с векторными полями градиентов. Сильные градиенты ночной картинки оставляются, остальные заменяются на градиенты из дневного изображения. Затем с помощью уравнения Пуассона восстанавливается результирущее изображение. Этот подход можно расширить, оставляя градиенты ночной картинки в тех местах, где сцена меняется (для последовательности изображений). Таким образом динамичные объекты будут браться из ночного изображения, а статичные из дневного, а решение уравнения Пуассона сделает швы незаметными (Рис. 12).

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

Рис. 12: Пример смешивания ночного и дневного изображений сцены.

Removing Photography Artifacts using Gradient Projection and Flash-Exposure Sampling [5]

Методы, предложенные авторами статьи, работают с двумя изображениями одной сцены: снятым со вспышкой и без. Во многих случаях часть сцены лучше получается в одном из этих изображений, а часть в другом. Кроме того каждое изображение может содержать свои типы нежелательных артефактов, таких как блики и отражения. Цель, которую поставили авторы статьи, заключается в получении наиболее подходящей для человеского восприятия картинки. Для этого авторы строят математическую модель освещения. Затем в статье рассматриваются несколько типов конкретных задач. Для каждого из них в статье предлагается свой оптимальный метод смешивания градиентов изображений, исходя из модели освещения. Заключительная часть у всех методов одинаковая: результат восстанавливается уравнением Пуассона (Рис. 13). Чтобы иметь возможность использовать в качестве краевых условий условия Дирихле, авторы обводят изображение слоем из нулевых пикселей. Стоит также отметить, что все методы не работают тогда, когда на одном и том же месте присутствуют артефакты (пускай различные) на обоих изображениях.

Рис. 13: Пример результата для задачи фотографирования человека перед окном в ночное время.

Removing Shadows from Images [6]

В статье рассказывается про метод удаления теней из изображения. Первым этапом алгоритма является получение специального изображения, инвариантного к освещению. Этот этап – отдельная сложная задача, описанная в другой статье. На таком специальном изображении нет теней, но там также нет никаких других данных по освещению и цвету. Авторы предлагают сравнивать векторные градиентные поля двух изображений: исходного и инвариантного к освещению. Участки, где градиенты разительно отличаются, объявляются краями теней. Затем строится новое градиентное поле, которое равно градиентному полю исходного изображения, за исключением найденных участков, на которых градиент приравнивается к нулю. В итоге результирующее изображение без теней получается решением уравнения Пуассона (Рис. 14).

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

Рис. 14: Пример удаления тени с изображения.

Заключение

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

Литература

1. Patrick Perez , Michel Gangnet , Andrew Blake, Poisson image editing, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
2. Raanan Fattal , Dani Lischinski , Michael Werman, Gradient domain high dynamic range compression, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
3. Jianbing Shen , Xiaogang Jin , Chuan Zhou , Charlie C. L. Wang, Technical Section: Gradient based image completion by solving the Poisson equation, Computers and Graphics, v.31 n.1, p.119-126, January, 2007
4. Ramesh Raskar , Adrian Ilie , Jingyi Yu, Image fusion for context enhancement and video surrealism, ACM SIGGRAPH 2005 Courses, July 31-August 04, 2005, Los Angeles, California
5. Amit Agrawal , Ramesh Raskar , Shree K. Nayar , Yuanzhen Li, Removing photography artifacts using gradient projection and flash-exposure sampling, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
6. Graham D. Finlayson , Steven D. Hordley , Mark S. Drew, Removing Shadows from Images, Proceedings of the 7th European Conference on Computer Vision-Part IV, p.823-836, May 28-31, 2002
7. J. Sun, J. Jia, C.-K. Tang, and H.-Y. Shum. Poisson matting. ACM Trans. Graph., 23(3):315-321, 2004
8. http://ru.wikipedia.org/wiki/Уравнение_Пуассона
9. Захаров Е.В., Дмитриева И.В., Орлик С.И., Методическое пособие по курсу "Уравнение математической физики", М: Издательский отдел факультета ВМиК МГУ, 2003
10. Seamless image stitching in the gradient domain by Anat Levin, Assaf Zomet, Shmuel Peleg, Yair Weiss — 2004 — In Eighth European Conference on Computer Vision (ECCV 2004)
11. T. Georgiev. Covariant derivatives and vision. In ECCV, pages IV: 56-69, 2006
12. Lena Gorelick , Meirav Galun , Eitan Sharon , Ronen Basri , Achi Brandt, Shape Representation and Classification Using the Poisson Equation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.28 n.12, p.1991-2005, December 2006
13. James McCann , Nancy S. Pollard, Real-time gradient-domain painting, ACM Transactions on Graphics (TOG), v.27 n.3, August 2008
14. Daniel Leventhal , Bernard Gordon , Peter G. Sibley, Poisson image editing extended, ACM SIGGRAPH 2006 Research posters, July 30-August 03, 2006, Boston, Massachusetts
15. O. Sorkine , D. Cohen-Or , Y. Lipman , M. Alexa , C. Rossl , H.-P. Seidel, Laplacian surface editing, Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, July 08-10, 2004, Nice, France
16. Aseem Agarwala , Mira Dontcheva , Maneesh Agrawala , Steven Drucker , Alex Colburn , Brian Curless , David Salesin , Michael Cohen, Interactive digital photomontage, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
17. Yizhou Yu , Kun Zhou , Dong Xu , Xiaohan Shi , Hujun Bao , Baining Guo , Heung-Yeung Shum, Mesh editing with poisson-based gradient field manipulation, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
18. Dong Xu , Hongxin Zhang , Qing Wang , Hujun Bao, Poisson shape interpolation, Proceedings of the 2005 ACM symposium on Solid and physical modeling, p.267-274, June 13-15, 2005, Cambridge, Massachusetts
19. Michael Kazhdan , Matthew Bolitho , Hugues Hoppe, Poisson surface reconstruction, Proceedings of the fourth Eurographics symposium on Geometry processing, June 26-28, 2006, Cagliari, Sardinia, Italy
20. Michael Kazhdan , Hugues Hoppe, Streaming multigrid for gradient-domain operations on large images, ACM Transactions on Graphics (TOG), v.27 n.3, August 2008

Дополнительная информация

Ссылка: 

Владимир Кононов, Вадим Конушин. Применение уравнения Пуассона в задачах обработки изображений. Компьютерная графика и мультимедиа. Выпуск №7(1)/2009. http://cgm.computergraphics.ru/issues/issue17/poissonimaging

Выпуск: 

Выпуск №7(1)/2009

Статья в PDF: 

cgm_17_2202.pdf