способ сегментации изображений

Формула изобретения

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

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

3. Способ по п.1, отличающийся тем, что вклад ценовой функции швов в общую сумму ценовых функций швов и данных уменьшают на подмножестве итераций.

Описание изобретения к патенту

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

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

- двоении контуров движущихся объектов, а, в некоторых случаях, и в удвоении числа движущихся объектов на изображении;

- появлении полупрозрачности у движущихся объектов;

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

В настоящее время одним из направлений повышения качества снимков при помощи мобильных устройств является съемка нескольких кадров в короткий промежуток времени с последующим их объединением - сшивкой нескольких изображений в одно результирующее (получение панорамного снимка, снимка с повышенным динамическим диапазоном, понижение уровня шума, и т.д.). При этом сшивка должна производиться таким образом, чтобы шов проходил по траектории наименьших различий в соседних исходных изображениях и обходил движущиеся объекты. Распространенным способом определения оптимальной траектории шва являются различные способы сегментации изображений [Александр Вежневец, Ольга Баринова. Методы сегментации изображений: автоматическая сегментация. Компьютерная графика и мультимедиа. Выпуск № 4(4)/2006. http://cgm.computergraphics.ru/content/view/147].

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

- создание панорамного снимка из нескольких кадров, каждый из которых изображает лишь часть панорамы;

- создание снимка с высоким динамическим диапазоном из нескольких исходных снимков с низким динамическим диапазоном.

Известны различные способы улучшения качества изображений с применением их сегментации.

Способ кластеризации [Bishop, С.М. Neural Networks for Pattern Recognition. Oxford, England: Oxford University Press, 1995], при котором задают отображение точек изображения в некоторое пространство признаков и вводят метрику (меру близости) на этом пространстве признаков.

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

Способ выращивания регионов [A. Tremeau and n. Borel, "A Region growing and erging Algorithm to color segmentation," Pattern Recognition, 1997]; [Y. Kanai, "Image Segmentation Using Intensity and Color Information," SPIE-Visual Communications and Image Processing'98]; [B. Cramariuc, М. Gabbouj, and J. Astola, "Clustering Based Region Growing Algorithm for Color Imag Segmentation," Int. Conf. on Digital signal Processing, 1997]; [Y. Deng, B. S. Manjunath, and H, Shin, "Color Image Segmentation", CVPR 1999], при котором учитывают пространственное расположение точек напрямую. Вначале, по некоторому правилу, выбирают центры регионов, к которым поэтапно присоединяют соседние точки, удовлетворяющие некоторому критерию. Процесс выращивания регионов останавливается, когда ни одна точка изображения не может быть присоединена ни к одному региону. Применяются разные критерии, на основании которых точка присоединяется или не присоединяется к региону: близость точки к центру региона; близость к соседней точке, присоединенной к региону на предыдущем шаге; близость по некоторой статистике региона; стоимость кратчайшего пути от точки до центра региона, и т.п. В основном процедура выращивания региона используется для получения отдельных регионов, однако, применяя эту процедуру последовательно или одновременно для нескольких регионов, можно получить разбиение всего изображения.

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

Способы дробления-слияния [A. Tremeau and n. Borel, "A Region growing and Merging Algorithm to color segmentation," Pattern Recognition, 1997];[В. Cramariuc, M. Gabbouj, and J. Astola, "Clustering Based Region Growing Algorithm for Color Imag Segmentation," Int. Conf. on Digital signal Processing, 1997]; [H. Digabel and C. Lantujoul, "Iterative Algorithms," Proc. of the 2nd European Symp. on Quantitative Analysis of Microstructures in Material Science, Biology and / Medicine, 1977]; [M. Celenk, "Hierarchical Color Clustering for Segmentation of Textured Images," Proc. of the 29th Southeastern Symposium on system Theory, 1997]; [S. Ji and H.W. Park, "Image Segmentation of Color Image Based on Region Coherency," Proc. of ICIP'98];[L. Shafarenko, M. Petrov, and J. Kittler, "Automatic Watershed segmentation of Randomly Textured Color Images," IEEE Trans. on Image Processing, 1997]; [M. Barni, S. Rossi, and A. Mecocci, "A Fuzzy Expert System for Low Level Image Segmentation," EUSIPCO-96], состоящие из двух основных этапов: дробления и слияния. Дробление начинается с некоторого разбиения изображения, не обязательно на однородные области. Процесс дробления областей происходит до тех пор, пока не будет получено разбиение изображения (пересегментация), удовлетворяющее свойству однородности сегментов. Затем происходит объединение схожих соседних сегментов до тех пор, пока не будет получено разбиение изображения на однородные области максимального размера.

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

Способ моделирования Марковским полем [G. R. Cross and А. К. Jain, "Markov Random Field Texture Models," IEEE Trans. on Pattern Analysis and Machine Intelligence, 1983]; [S. German and D. German, "Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images," IEEE Trans. on Pattern Analysis and Machine Intelligence, 1984]; [R. Szeliski, R. Zabih, D. Scharstein, O. Veksler, V. Kolmogorov, A. Agarwala, M. Tappen, C. Rother «A Comparative Study of Energy Minimization Methods for Markov Random Fields with Smoothness-Based Priors» IEEE Trans, on Pattern Analysis and Machine Intelligence, vol.30, no.6, June 2008], который основан на предположении, что цвет каждой точки изображения зависит от цветов некоторого множества соседних точек. Предложено обобщение модели изображения, также возможно обобщение на текстурную сегментацию [Y. Deng, В. S. Manjunath, and H, Shin, "Color Image Segmentation", CVPR 1999].

Недостатком этого способа является сложность в реализации.

Способы, основанные на операторах выделения краев [М. Jacob, M. Unser, "Design of Steerable Filters for Feature Detection Using Canny-Like Criteria," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.26, no.8, pp.1007-1019]; [Edge Detection Using steerable Filters and CN1M, Atilla Ozmen and Emir Tufan Akman, 2002], при которых задача сегментации формулируется как поиск границ регионов и хорошо решается для полутоновых изображений. Полутоновое изображение рассматривается как функция двух переменных, и предполагается, что границы регионов соответствуют максимумам градиента этой функции. Для их поиска применяется аппарат дифференциальной геометрии. Для повышения устойчивости к шуму, перед применением фильтрации, изображение обычно размывают. Благодаря коммутативности оператора Лапласа и Гауссова фильтра, можно одновременно осуществлять размытие и поиск границ.

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

Оптимизационные способы [Y. Deng, В.S. Manjunath, and H, Shin, "Color Image Segmentation", CVPR 1999], при которых задачу разбиения изображения на однородные области сводят к задаче оптимизации. Для этого задачу сегментации формулируют как задачу поиска разбиения изображения, обладающего определенными свойствами, затем вводится функционал, который отражает степень соответствия полученной сегментации предъявляемым требованиям. Например, вводится функционал качества сегментации, использующий распределение цветов на изображении.

Недостатки - трудоемкость способа, высокие требования к ресурсам мобильных устройств.

Общими недостатками всех этих способов являются:

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

- неприемлемые для мобильных устройств требования к ресурсам системы - объему памяти и скорости работы вычислительного блока (способы кластеризации, выращивания регионов, дробления-слияния, моделирования Марковским полем, способ теории графов, оптимизационные подходы),

- плохая работа назашумленных изображениях (способы кластеризации, выделения краев),

- отсутствие учета пространственного расположения точек (кластеризация).

Наиболее близким к заявляемому решению является способ минимизации с помощью нарезки графа [US Patent 6,744,923. «System and method for fast approximate energy minimization via graph cuts»]; [R.Szeliski, R.Zabih, D.Scharstein, O.Veksler, V.Kolmogorov, A.Agarwala, M.Tappen, C.Rother « A Comparative Study of Energy Minimization Methods for Markov Random Fields with Smoothness-Based Priors» IEEE Trans, on Pattern Analysis and Machine Intelligence, vol. 30, no.6, June 2008]. Изображение представляется в виде взвешенного графа, с вершинами в точках изображения. Вес ребра графа отражает сходство точек (например, расстояние между точками по некоторой метрике). Разбиение изображения моделируется разрезами графа. В способах теории графов вводится функционал «стоимости» разреза, отражающий качество полученной сегментации. Так, задача разбиения изображения на однородные области сводится к оптимизационной задаче поиска разреза минимальной стоимости на графе. Такой подход позволяет, помимо однородности цвета и текстуры сегментов, управлять также формой сегментов, их размером, сложностью границ и т.п. Для поиска разреза минимальной стоимости применяются различные методы: жадные алгоритмы (на каждом шаге выбирается такое ребро, чтобы суммарная стоимость разреза была минимальной), способы динамического программирования (гарантируется, что, выбирая на каждом шаге оптимальное ребро, получат в итоге оптимальный путь), и т.п.

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

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

- быстродействие;

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

- отсутствие необходимости в дополнительных ресурсах памяти мобильного устройства;

- устойчивость к шумам в изображении.

Сущность заявляемого технического решения заключается в том, что в известном способе сегментации изображений путем поиска минимума ценовых функций, поиск производят на N-количестве уровней детализации изображения, от более грубой к более детализированной, при этом на каждом уровне детализации изображение разделяют на области; для каждой области путем n-количества последовательных итераций назначают единое значение сегментации, затем подсчитывают значение ценовой функции швов на границах областей при разных вариантах сегментации изображения и для каждой области выбирают значение сегментации, приводящее к минимизации суммы ценовых функций швов и данных. В тех случаях, когда необходимо исключить влияние швов на результат сегментации (например, при необходимости получения одинаковой сегментации вне зависимости от ориентации изображения), поиск минимума на каждой итерации производят путем обработки областей изображения, не имеющих общих границ, а выбор областей для обработки изменяют при каждой последующей итерации. Чтобы исключить остановку (застревание) поиска глобального минимума в одном из локальных минимумов, созданных высокой стоимостью шва вокруг какой-либо локальной области вследствие шумов в изображении, несколько исходных итераций на каждом уровне детализации проводят с уменьшением вклада функции швов в сумму ценовых функций. Это дает возможность швам перескакивать (протекать) сквозь пики стоимости.

На фиг.1 приведен пример исходного изображения, цветовое пространство которого будет оптимально сегментировано на 12 цветов.

На фиг.2 приведен пример исходной сегментации для самой грубой детализации, исходя из ценовой функции данных. Ценовая функция швов принята равной нулю.

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

На фиг.4 изображено состояние сегментации после второй итерации.

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

На фиг.6 представлены графики схождения различных способов [R. Szeliski, R. Zabih, D. Scharstein, O. Veksler, V. Kolmogorov, A. Agarwala, M. Tappen, C. Rother "A Comparative Study of Energy Minimization Methods for Markov Random Fields with Smoothness-Based Priors" IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 30, no. 6, June 2008] к глобальному минимуму на задаче сшивки панорамы. Вертикальная ось - отклонение от глобального минимума (в %), горизонтальная ось - логарифмическая ось времени (в секундах). На графиках (фиг.6; фиг.7; фиг.8):

	- способ моделирования Марковским полем Iterated Conditional Modes ;
	- варианты способа нарезки графа Loopy Belief Propagation ;
	- аналогичный способу Loopy Belief Propagation способ Tree-Reweighted Message Passing ;
	- предсказание нижней границы глобального минимума;
	- различные варианты исполнения способа нарезки графа [2] (прототип);
	- предлагаемый способ (окружностью отмечено полное время обработки и достигнутое отклонение от глобального минимума).

На фиг.7 и фиг.8 представлены укрупненные варианты графика, изображенного на фиг.6 с увеличенным масштабом отклонения от глобального минимума.

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

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

- Ценовая функция шва - указывает, насколько оптимальным является прохождение границы сегментов в данном месте.

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

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

При каждой итерации над каждой из областей пикселей производят следующие действия:

- подсчитывают локальное значение ценовой функции, включая цену данных и цену швов, окружающих данную область;

- ценовую функцию рассчитывают для всех возможных значений сегментации для данной области;

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

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

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

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

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

При каждой итерации над каждым из квадратов производят следующие действия:

- подсчитывают локальное значение ценовой функции, включая цену данных и цену швов, окружающих данный квадрат;

- ценовую функцию рассчитывают для всех возможных значений сегментации для данного квадрата;

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

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

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

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

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

Заявляемый способ обладает следующими преимуществами по сравнению с существующими в настоящее время аналогами:

1. Быстродействие. Общее время обработки на распространенных в данное время мобильных устройствах (выпуска 2011 г.) - в пределах одной секунды.

2. Качество сегментации (близость к абсолютно-оптимальной сегментации) аналогично лучшим известным способам.

3. Весьма низкие требования к ресурсам памяти при реализации способа.

4. Способ устойчив к шумам в изображении, т.к. отсутствует остановка (застревание) в локальных минимумах.

СПИСОК ЛИТЕРАТУРЫ

[1] Александр Вежневец, Ольга Баринова. Методы сегментации изображений: автоматическая сегментация. Компьютерная графика и мультимедиа. Выпуск № 4(4)/2006. http://cgm.computergraphics.ru/content/view/147

[2] US Patent 6,744,923. «System and method for fast approximate energy minimization via graph cuts».

[3] Bishop, С.М. Neural Networks for Pattern Recognition. Oxford, England: Oxford University Press, 1995

[4] A. Tremeau and n. Borel, "A Region growing and Merging Algorithm to color segmentation," Pattern Recognition, 1997

[5] Y. Kanai, "Image Segmentation Using Intensity and Color Information," SPIE-Visual Communications and Image Processing'98

[6] В. Cramariuc, М. Gabbouj, and J. Astola, "Clustering Based Region Growing Algorithm for Color Imag Segmentation," Int. Conf. on Digital signal Processing, 1997

[7] Y. Deng, B. S. Manjunath, and H, Shin, "Color Image Segmentation", CVPR 1999

[8] H. Digabel and C. Lantujoul, "Iterative Algorithms," Proc. of the 2nd European Symp. on Quantitative Analysis ofMicrostructures in Material Science, Biology and Medicine, 1977

[9] М. Celenk, "Hierarchical Color Clustering for Segmentation of Textured Images," Proc. of the 29th Southeastern Symposium on system Theory, 1997

[10] S. Ji and H. W. Park, "Image Segmentation of Color Image Based on Region Coherency," Proc. of ICIP 98

[11] L. Shafarenko, М. Petrov, and J. Kittler, "Automatic Watershed segmentation of Randomly Textured Color Images," IEEE Trans. on Image Processing, 1997

[12] М. Barni, S. Rossi, and A. Mecocci, "A Fuzzy Expert System for Low Level Image Segmentation," EUSIPCO-96

[13] G. R. Cross and A. K. Jain, "Markov Random Field Texture Models," IEEE Trans. on Pattern Analysis and Machine Intelligence, 1983

[14] S. German and D. German, "Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images," IEEE Trans. on Pattern Analysis and Machine Intelligence, 1984

[15] М. Jacob, М. Unser, "Design of Steerable Filters for Feature Detection Using Canny-Like Criteria," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, no. 8, pp.1007-1019

[16] Edge Detection Using steerable Filters and CNN, Atilla Ozmen and Emir Tufan Akman, 2002

[17] Normalized Cuts and Image Segmentation -J. Shi, J. Malik(1997) University of California at Berkeley

[18] Image Segmentation by Nested Cuts (2000) - Olga Veksler, NEC Research Institute

[19] R. Szeliski, R. Zabih, D. Scharstein, O. Veksler, V. Kolmogorov, A. Agarwala, M. Tappen, C. Rother «A Comparative Study of Energy Minimization Methods for Markov Random Fields with Smoothness-Based Priors» IEEE Trans, on Pattern Analysis and Machine Intelligence, vol.30, no.6, June 2008.