Интеллектуальный подход к формированию цифровых коллажей на основе фотои видеоматериалов

Библиографические ссылки

1. Ерунова М. Г., Гостева А. А., Якубайлик О. Э. Геоинформационное обеспечение задач экологического мониторинга особо охраняемых территорий // Журнал Сибирского федерального университета. Серия: Техника и технологии. 2008. Т. 1. № 4. С. 366-376.

2. Попов В. Г., Якубайлик О. Э. Разработка модели геоинформационной аналитической Интернет-системы для задач мониторинга и анализа состояния региона // Горный информационно-аналитический бюллетень. 2009. Т. 17. № 12. С. 39-44.

3. Якубайлик О. Э., Попов В. Г. Технологии для геоинформационных Интернет-систем // Вычислительные технологии. 2009. Т. 14. № 6. С. 116-126.

4. Якубайлик О. Э. Геоинформационная Интернет-система мониторинга состояния окружающей природной среды в зоне действия предприятий нефтегазовой отрасли // Вестник СибГАУ. 2010. Вып. 1. С. 40-45.

5. Кадочников А. А., Попов В. Г., Токарев А. В., Якубайлик О. Э. Формирование геоинформационного Интернет-портала для задач мониторинга состояния природной среды и ресурсов // Журнал Сибирского федерального университета. Серия: Техника и технологии. 2008. Т. 1. № 4. С. 377-386.

6. Ерунова М. Г., Якубайлик О. Э., Кадочников А. А. Геоинформационный анализ состояния природной среды государственного заповедника «Столбы» // География и природные ресурсы. 2006. № 2. С. 136-142.

O. E. Yakubailik

PROBLEMS OF FORMATION OF INFORMATION-COMPUTER SUPPORT OF ENVIRONMENTAL MONITORING SYSTEMS

The article deals with particular problems and tasks of forming the information infrastructure of the environmental monitoring system, discuss its features and software technology platform. A system of environmental monitoring of areas in Krasnoyarsk region, and the tasks of GIS support of environmental monitoring of protected natural territories through geoportal technologies, are described as examples.

Keywords: environmental monitoring, geoportal, GIS, geospatial data, web mapping, web service.

© .3Ky6ataHK O. Э., 2012

УДК 004.932.2

Е. Л. Ярославцева, К. Э. Левтин

ИНТЕЛЛЕКТУАЛЬНЫЙ ПОДХОД К ФОРМИРОВАНИЮ ЦИФРОВЫХ КОЛЛАЖЕЙ НА ОСНОВЕ ФОТО- И ВИДЕОМАТЕРИАЛОВ

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

Ключевые слова: автоматическое составление коллажей, видеоколлаж, «бесшовная стыковка».

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

ний, при условии максимизации информативной области изображений, также называемой областью интереса (ОИ) изображения.

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

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

Решение задачи составления коллажа цифровых фотографий или кадров видеопоследовательности на основе эффекта «бесшовной стыковки» и адаптивной подстройки границ ОИ сегментов коллажа состоит из четырех этапов:

- отбор кадров видеопоследовательности;

- оптимальное размещение сегментов коллажа;

- создание гибкого контура ОИ на изображении;

- «бесшовная стыковка» сегментов.

Рассмотрим указанные этапы комплексного подхода к автоматическому составлению коллажей более подробно.

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

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

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

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

- сортировка сегментов коллажа;

- размещение сегментов коллажа;

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

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

объединяются следующим образом: пара № 1 (изображение с наибольшим размером, изображение с наименьшим размером), пара № 2 аналогично формируется из оставшихся после образования первой пары (изображение с наибольшим размером, изображение с наименьшим размером), пара № 3 состоит из оставшихся двух изображений. Данный этап необходим для обеспечения баланса между оптимизацией размещения сегментов, оптимизации областей их перекрытия и оптимизации размеров самих сегментов.

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

[х; у- ] = [х±1 • (1 - Ь); у.±1 • (1 - Ь)],

где х, у- - координаты текущего сегмента; х1±1 - координата соседнего по горизонтали сегмента; Ь - значение параметра «размер области перекрытия сегментов»; у-±1 - координата соседнего по вертикали сегмента.

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

В качестве второго сегмента используется изображение парно соответствующее первому сегменту. Высота текущего сегмента вычисляется по выражению:

Н2 = Н0 - Щ{1 - Ь),

где Н0 - высота рабочей области коллажа; Н , - высота соответствующего сегмента.

Ширина второго сегмента рассчитывается по правилам пропорции. Второй сегмент размещается под первым сегментом следующим образом:

[х2; У2 ] = [х1; У1 + Нг(1 - Ь)].

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

Г5,6 = Жо - Ги(1 - Ь) - ^3,4(1 - Ь),

[ Х5; У5] = [ х + ^(1 - Ь); у], [ Хб; Уб] = [ Х2 + ^(1 - Ь); у5 + Н5 (1 - Ь)],

где Ж0 - ширина рабочей области коллажа; Ж - ширина соответствующего сегмента.

Высота пятого и шестого сегментов вычисляются по правилам пропорции.

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

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

Е Е4,у

Т = JLJУ—; 1ху <Т1,

1 НЖ ху 1

Т2 = 1 (Нг'5^шах ) ; 1х,у ^ Т2 ,

где Ть Т2 - соответственно, первый и второй пороги; х, у - координаты пикселя; 1ху - интенсивность пикселя с заданными координатами; Н, Ж - высота и ширина изображения; Histшax - максимальное число пикселей одинаковой интенсивности, исходя из гистограммы; I(Histшax) - показатель интенсивности.

После описанного процесса бинаризации полученное изображение анализируется по размерам областей белого и черного цвета, где белый цвет соответствует ОИ, а черный - фоновой области. Если условие о превалировании размеров фоновых областей над размерами ОИ не выполняется, полученное изображение инвертируется.

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

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

Метод оценки формы состоит из четырех основных шагов [3]:

1) выделения связных областей;

2) сравнительной оценки формы выделенных областей;

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

4) формирования аппроксимирующей области.

На первом шаге выделяются связные области по итеративному методу последовательного сканирования [4], на этом же шаге контролируются размеры и осуществляется первоначальный контроль формы найденных областей. Отбрасываются связные области, размеры которых меньше заданного порога или пропорции отношений длин сторон которых не входят в заданный порог. Таким способом решается задача фильтрации шумовых включений и удаления мало информативных объектов.

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

Указанный выше метод блочного анализа также состоит из четырех шагов:

1) разбиения изображения на блоки размеров n*n;

2) анализа заполненности каждого блока;

3) аппроксимации каждого блока графическим примитивом типа «круг» (иначе говоря, «блобом», от англ. «blob» - «маленький шарик»);

4) формирования аппроксимирующей области.

Рассмотрим описанные шаги подробнее. На первом шаге необходимо провести разбиение изображения на блоки размером n*n, где n равно 2, 4, 8, 1б.. ,2k, и выбрать в соответствии с размерами исходного изображения оптимальное число блоков. Значение оптимального числа блоков зависит от требуемой точности аппроксимации области и в общем случае равно 300 блокам. На втором шаге подсчитывается заполненность F каждого блока пикселями, принадлежа-

щими ОИ. Отбрасываются блоки, заполненность которых ниже заданного порога, за счет чего производится фильтрация шумовых включений. Радиус аппроксимирующего «блоба» рассчитывается также исходя из заполненности блока по следующей формуле [5]:

Ri j = kt}. • п + п; к = %, п

где i, j - координаты блока в массиве аппроксимирующих блоков; Rj - радиус аппроксимирующего блоба; kjj - коэффициент заполненности блока; п -величина длины/ширины блока; Fj - показатель заполненности блока пикселями, принадлежащими ОИ.

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

/ , Xroi Уroi

xc = —-; yc = —---------,

c F F.

i,j i, j

где xc, yc - координаты центра блоба; xroi, yroi - координаты пикселей области интереса; Fi,j - показатель заполненности блока пикселями, принадлежащими ОИ.

На четвертом шаге из рассчитанных аппроксимирующих блобов формируется массив графических примитивов, аппроксимирующих ОИ. Блочный метод характеризуется повышенной сложностью аппроксимирующей модели по сравнению с методом оценки формы, так как при аппроксимации использует массив, состоящий не из 1-10 блоков, а из 100-200 блоков. Однако при должном уровне оптимизации процесса блочного разбиения, как самой ресурсоемкой операции, данный метод не уступает в быстродействии методу оценки формы. Данный метод характеризуется более точной и, кроме того, зависящей от масштаба разбиения, а потому настраиваемой точностью аппроксимации ОИ, и в результате получается визуально более выигрышные и генерируемые натуральные контуры. Безусловно, высокая точность аппроксимации не позволяет данному методу компенсировать неточности выделения ОИ, внесенные на этапе текстурной сегментации.

Полученный массив аппроксимирующих графических примитивов используется в дальнейшем для создания нечетких масок на этапе формирования «бесшовной стыковки» сегментов коллажа. С целью создания целостности получаемой картины необходимо осуществить плавные переходы от одного сегмента коллажа к другому. Решение данной задачи заключается в применении метода, получившего название «бесшовная стыковка» (seamless blending) [6].

В комплексном подходе автоматического составления коллажей создание выходного изображения с применением метода «бесшовной стыковки» реализуется посредствам рекурсивного алгоритма наложения

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

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

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

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

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

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

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

jOUt _ i j ~

mask i,J '

(Imax Ii, j

mask

где I, ] - координаты обрабатываемого пикселя; /ои‘ - значение интенсивности пикселя выходного изображения; - значение интенсивности пикселя изо-

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

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

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

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

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

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

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

Корректность

выделения ои ГМаеноа. переходов Информативность

Рис. 1. Сводная диаграмма анализа эффективности формирования выходных изображений

15 19Д

17 23

15 55 15.:: вт *5 «

Is j: —

12.12 12 S?

^ 112 10.5 _ 10 0? IX Я

лея

и 3. 61 3-.2.S 3,32 г —<

Подбор* > м 1 Подборка К-8 2 Подбор*» КА з подбор* 1 кед подбор* а ка 5 Подборка Квв Подбор* • Ка 7

♦ прв моу га*виоб  »де/«иив Ш Мб'од ои^нк и форм м Д Метод блхногэ а нал юа

Рис. 2. Сводная диаграмма анализа временных затрат на формирование выходного изображения

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

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

Библиографические ссылки

1. Marriott K., Stuckey P. Programming with Constraints. The MIT Pr, 1998.

2. Ярославцева Е. Л. Применение цифрового коллажа для наглядного представления видеопоследовательностей // Цифровая обработка сигналов и ее применение : материалы XII междунар. конф. : в 2 т. 2010. Т. 2. С. 189-191.

3. Liu T., Sun J., Zheng N. N., Tang X. and Shum H.-Y. Learning to detect a salient object, in Proc. CVPR, 2007.

4. Man H. L., Singhal N., Cho S. and Park I. K. Mobile photo collage // Proc. VI IEEE Workshop on Embedded Computer Vision (June 2010). 2010. Р. 24-30.

5. Ярославцева Е. Л. Составление коллажей из фрагментов изображений // Решетневские чтения : материалы XIV междунар. научн. конф. ; Сиб. гос. аэрокосмич. ун-т. Красноярск, 2010. Ч. 2. С. 538-539.

6. Mei T., Wang T., Hua X.-S., Zhou H.-Q. Video collage: a novel presentation of video sequence // IEEE Intern. Conf. on MME (2007, Beijing). 2007. Р. 1479-1482.

E. L. Yaroslavtseva, K. E. Levtin

INTELLIGENT APPROACH TO DIGITAL PHOTO- AND VIDEO-BASED DIGITAL

COLLAGE COMPOSITION

An intelligence approach to collage compositions, based on seamless integration effect and adaptive regions of interest selection, is proposed in a detailed algorithm. Intelligent system, based on this algorithm, was developed and tested on a whole number of photo and video materials. Conclusions and possible further investigations, are given in the end of this paper.

Keywords: automatic collage composition, video collage, seamless integration.

© Ярославцева Е. Л., Левтин К. Э., 2012