INTELLIGENT APPROACH TO DIGITAL PHOTOAND VIDEO-BASED DIGITAL COLLAGE COMPOSITION

Full Text

Автоматическое составление коллажей цифровых изображений является актуальной задачей в силу ряда причин. Конечные изображения, составленные на основе данной техники, получаются выигрышными в плане наглядности и информативности по сравнению с отдельно взятыми изображениями. В свою очередь, автоматическое составление коллажей цифровых изображений в силу значительных затрат пользовательских визуальных решений является востребованным в широком спектре задач - от создания обложек домашних фотоальбомов до коммерческих рекламных проектов. Непосредственная задача составления коллажа заключается в создании визуального резюмированного образа, составляемого из набора изображе ний, при условии максимизации информативной области изображений, также называемой областью интереса (ОИ) изображения. Отметим, что задача оптимального размещения сегментов коллажа является одной из подзадач задачи рационального раскроя и упаковки. Результаты решения таких задач используются для создания эффектного выходного изображения на основе метода «бесшовной стыковки» сегментов. Сложность задачи создания плавных переходов между сегментами коллажа состоит в подборе соседних изображений с максимально похожими границами и оптимальном выборе параметров размытия границ и настроек прозрачности. Также важной задачей при создании комплексного 102 Вестник Сибирского государственного аэрокосмического университета имени академика М. Ф. Решетнева подхода к автоматическому составлению коллажа является максимальная оптимизация скорости выполнения всех методов анализа для получения приемлемого времени обработки цифровых фотографий и видеоматериалов. Решение задачи составления коллажа цифровых фотографий или кадров видеопоследовательности на основе эффекта «бесшовной стыковки» и адаптивной подстройки границ ОИ сегментов коллажа состоит из четырех этапов: - отбор кадров видеопоследовательности; - оптимальное размещение сегментов коллажа; - создание гибкого контура ОИ на изображении; - «бесшовная стыковка» сегментов. Рассмотрим указанные этапы комплексного подхода к автоматическому составлению коллажей более подробно. Метод отбора кадров видеопоследовательности, используемый в разрабатываемом комплексном подходе автоматического составления коллажей, основан на технике эвристического поиска и продукционной системе принятия решений [1]. На первом шаге случайным образом переходим к первому кадру, проверяем, удовлетворяет ли он заданным критериям. Если текущий кадр не удовлетворяет каким-либо параметрам, то переходим к проверке следующего кадра до тех пор, пока не получим изображение для первого сегмента коллажа. Проверка второго кадра и всех последующих производится аналогично, но также содержит в себе критерий отбора исключения одинаковых кадров, который выполняется вначале всей проверки. Если пользователь указал необходимость детектирования лиц на изображениях, то по завершении выполнения всех предыдущих критериев производится проверка на содержание лиц в кадре. Если по окончании заданного пользователем количества итераций не было обнаружено ни одного кадра, содержащего лицо человека, в качестве сегментов коллажа будут выбраны любые кадры, удовлетворяющие всем остальным критериям отбора. Случайность выбора кадра задается с помощью функции Random, которая генерирует псевдослучайные числа исходя из длительности анализируемого видеоряда. Данный метод размещения сегментов коллажа не является универсальным, но он очень эффективен в применении к составлению коллажа из заранее определенного числа сегментов, в данном случае из шести, что является основным ограничением. Он основан на последовательном размещении сегментов коллажа в пределах рабочей области в соответствии со значением параметра «размер области перекрытия сегментов». Его выполняют в три этапа: - сортировка сегментов коллажа; - размещение сегментов коллажа; - минимизация незаполненных регионов рабочей области коллажа. Предположим, что имеется 6 входных изображений. На первом этапе происходит сортировка входных изображений по размерам, затем они попарно объединяются следующим образом: пара № 1 (изображение с наибольшим размером, изображение с наименьшим размером), пара № 2 аналогично формируется из оставшихся после образования первой пары (изображение с наибольшим размером, изображение с наименьшим размером), пара № 3 состоит из оставшихся двух изображений. Данный этап необходим для обеспечения баланса между оптимизацией размещения сегментов, оптимизации областей их перекрытия и оптимизации размеров самих сегментов. Второй этап состоит из трех шагов, каждый из которых соответствует размещению отдельной пары сегментов коллажа. Размер и координаты расположения сегментов зависят от результатов расположения предыдущего сегмента и значения размера области перекрытия сегментов по формуле [2]: [x ; y, ] = [x±1 • (1 - L); y,±1 • (1 - L)], где xi, yj - координаты текущего сегмента; xi±1 - координата соседнего по горизонтали сегмента; L - значение параметра «размер области перекрытия сегментов»; j - координата соседнего по вертикали сегмента. На первом шаге случайным образом выбирается входное изображение в качестве первого сегмента. Заполнение канвы начинается с левого верхнего угла, размер первого изображения выбирается случайным образом из диапазона значений, ограниченного некоторым максимумом и минимумом, которые в свою очередь задаются процентным отношением размера рабочей области коллажа к размеру текущего сегмента. Данное ограничение вводится с целью равномерного заполнения канвы коллажа всеми сегментами. В качестве второго сегмента используется изображение парно соответствующее первому сегменту. Высота текущего сегмента вычисляется по выражению: H 2 = H 0 - Hj(1 - L), где H0 - высота рабочей области коллажа; H i - высота соответствующего сегмента. Ширина второго сегмента рассчитывается по правилам пропорции. Второй сегмент размещается под первым сегментом следующим образом: [x2;y2] = [x1;y1 + Hj(1 -L)]. Третий и четвертый сегменты размещаются в правой части коллажа аналогично первой паре сегментов. Оставшиеся изображения размещаются в качестве пятого и шестого сегментов в центр незаполненной области между первым и третьим, вторым и четвертым сегментами соответственно. Размеры и координаты размещения текущих сегментов зависят от площади незаполненной области и значения размера области перекрытия сегментов: W56 = W - Wu(1 - L) - W3,4(1 - L), [ X5; y5] = [ x + W1(1 - L); yj, [ X6; y6] = [ X2 + W2(1 - L); y5 + H5 (1 - L)], где W0 - ширина рабочей области коллажа; Wi - ширина соответствующего сегмента. 103 Математика, механика, информатика Высота пятого и шестого сегментов вычисляются по правилам пропорции. На третьем шаге проводится анализ незаполненных областей. Если такие области были найдены, то размер всех граничащих с ними сегментов увеличивается до полного редуцирования существующих разрывов. Рассмотрим процесс создания гибкого контура ОИ, который логически разделяется на поиск ОИ и последующее создание гибкого контура. Поиск ОИ основан на методе текстурной сегментации объектов переднего плана (области интереса) от фоновых объектов. Адаптивность данного подхода заключается в нетривиальности самой задачи: никаких определенных требований на объект/область интереса не накладывается, что существенно осложняет поиск. Метод создания гибкого контура, применяемый в комплексном подходе автоматического составления коллажей, основан на адаптивном подборе порога сегментации, учитывающем распределение интенсивности. Исходя из теоретического предположения, что объекты интереса имеют более высокую интенсивность, чем фоновая область, значение интенсивности выше среднего значения интенсивности изображения в целом, а фоновая область характеризуется определенной степенью цветовой однородности и площадью большей, чем площадь ОИ, на первом шаге производится двухпороговая бинаризация изображения. Бинаризация заполняет черным цветом все пиксели, интенсивность которых меньше первого порога или интенсивность которых равна второму порогу. Первый порог вычисляется как среднее значение интенсивности для всего изображения, второй порог - как пиковое значение распределения интенсивности, исходя из гистограммы изображения. Таким образом, для области интереса формируются два условия: Е lLJx,y T = JLJ:-; Ixy <Tj, 1 HW x y 1 T2 = 1 (Histmax ) ; Ix,y ^ T2 , где T1, T2 - соответственно, первый и второй пороги; x, y - координаты пикселя; Ix,y - интенсивность пикселя с заданными координатами; H, W - высота и ширина изображения; Histmax - максимальное число пикселей одинаковой интенсивности, исходя из гистограммы; I(Histmax) - показатель интенсивности. После описанного процесса бинаризации полученное изображение анализируется по размерам областей белого и черного цвета, где белый цвет соответствует ОИ, а черный - фоновой области. Если условие о превалировании размеров фоновых областей над размерами ОИ не выполняется, полученное изображение инвертируется. На втором шаге происходит построение гибкого контура найденной ОИ. На данном шаге главными задачами являются фильтрация шумовых включений и аппроксимация области графическими примитива ми для дальнейшего формирования нечеткой маски для «бесшовной стыковки». Рассмотрим методы создания гибкого контура ОИ на изображении, реализованные в комплексном подходе автоматического составления коллажей: метод оценки формы и блочный метод. Метод оценки формы состоит из четырех основных шагов [3]: 1) выделения связных областей; 2) сравнительной оценки формы выделенных областей; 3) выбора аппроксимирующего графического примитива для каждой из выделенных областей; 4) формирования аппроксимирующей области. На первом шаге выделяются связные области по итеративному методу последовательного сканирования [4], на этом же шаге контролируются размеры и осуществляется первоначальный контроль формы найденных областей. Отбрасываются связные области, размеры которых меньше заданного порога или пропорции отношений длин сторон которых не входят в заданный порог. Таким способом решается задача фильтрации шумовых включений и удаления мало информативных объектов. На втором и третьем шаге выделенные связные области анализируются на соответствие двум типам графических примитивов: эллипс и прямоугольник, и для каждой области выбирается примитив, имеющий наибольший процент совпадения. На четвертом шаге формируется массив графических примитивов, аппроксимирующих область интереса. Данный метод характеризуется высокой скоростью работы, поскольку использует аппроксимацию достаточно крупных областей двух типов графических примитивов. Однако в связи с этим возникает и его главный недостаток: низкая точность аппроксимации и, следовательно, слишком простые и однотипные контуры аппроксимированной области, что в большинстве случаев не является визуально выигрышным. Однако стоит отметить, что в ряде случаев грубая аппроксимация метода оценки формы позволяет скрыть неточности выделения ОИ. Указанный выше метод блочного анализа также состоит из четырех шагов: 1) разбиения изображения на блоки размеров n*n; 2) анализа заполненности каждого блока; 3) аппроксимации каждого блока графическим примитивом типа «круг» (иначе говоря, «блобом», от англ. «blob» - «маленький шарик»); 4) формирования аппроксимирующей области. Рассмотрим описанные шаги подробнее. На первом шаге необходимо провести разбиение изображения на блоки размером n*n, где n равно 2, 4, 8, 16...2* и выбрать в соответствии с размерами исходного изображения оптимальное число блоков. Значение оптимального числа блоков зависит от требуемой точности аппроксимации области и в общем случае равно 300 блокам. На втором шаге подсчитывается заполненность F каждого блока пикселями, принадлежа 104 Вестник Сибирского государственного аэрокосмического университета имени академика М. Ф. Решетнева щими ОИ. Отбрасываются блоки, заполненность которых ниже заданного порога, за счет чего производится фильтрация шумовых включений. Радиус аппроксимирующего «блоба» рассчитывается также исходя из заполненности блока по следующей формуле [5]: Ri , = kt j •n + n; k = %, n где i, j - координаты блока в массиве аппроксимирующих блоков; Ri,j - радиус аппроксимирующего блоба; ki,j - коэффициент заполненности блока; n -величина длины/ширины блока; Fi,j - показатель заполненности блока пикселями, принадлежащими ОИ. За счет корректирующего коэффициента k расширяется аппроксимирующий блоб в соответствии с заполненностью аппроксимируемого блока. Центр построения аппроксимирующего блоба выбирается как центр масс расположения пикселей ОИ внутри блока, например, как среднее арифметическое координат пикселей: / , Xroi yroi xc = —— ; yc = ——, c F F. i ,j i, j где xc, yc - координаты центра блоба; xroi, yroi - координаты пикселей области интереса; Fÿ - показатель заполненности блока пикселями, принадлежащими ОИ. На четвертом шаге из рассчитанных аппроксимирующих блобов формируется массив графических примитивов, аппроксимирующих ОИ. Блочный метод характеризуется повышенной сложностью аппроксимирующей модели по сравнению с методом оценки формы, так как при аппроксимации использует массив, состоящий не из 1-10 блоков, а из 100-200 блоков. Однако при должном уровне оптимизации процесса блочного разбиения, как самой ресурсоемкой операции, данный метод не уступает в быстродействии методу оценки формы. Данный метод характеризуется более точной и, кроме того, зависящей от масштаба разбиения, а потому настраиваемой точностью аппроксимации ОИ, и в результате получается визуально более выигрышные и генерируемые натуральные контуры. Безусловно, высокая точность аппроксимации не позволяет данному методу компенсировать неточности выделения ОИ, внесенные на этапе текстурной сегментации. Полученный массив аппроксимирующих графических примитивов используется в дальнейшем для создания нечетких масок на этапе формирования «бесшовной стыковки» сегментов коллажа. С целью создания целостности получаемой картины необходимо осуществить плавные переходы от одного сегмента коллажа к другому. Решение данной задачи заключается в применении метода, получившего название «бесшовная стыковка» (seamless blending) [6]. В комплексном подходе автоматического составления коллажей создание выходного изображения с применением метода «бесшовной стыковки» реализуется посредствам рекурсивного алгоритма наложения изображений и состоит из двух этапов: создания нечеткой маски сегмента и этапа «бесшовной стыковки» сегментов коллажа. На начальном этапе подготавливается фон выходного изображения: заливается изображение указанным цветом и накладывается заданное фоновое изображение. В дальнейшем для каждого сегмента генерируется нечеткая маска и сегмент накладывается посредством нечеткой маски на заранее подготовленный фон. Рекурсивность данного метода заключается в том, что изображение, полученное на шаге n-1, используется как фон для наложения изображения следующего сегмента на шаге n. Указанная выше нечеткая маска представляет собой изображение в градациях серого цвета, содержащее области от черного до белого цвета, размерами соответствующее размерам сегмента коллажа. Нечеткая маска позволяет накладывать изображение сегмента коллажа на фон с определенной прозрачностью для каждого пикселя, которая определяется интенсивностью соответствующего по координатам пикселя нечеткой маски. Существует два принципиально различных способа формирования нечеткой маски: простой способ создания полупрозрачных взаимных переходов между сегментами и фоном и адаптивный способ на основе рассчитанной аппроксимации ОИ каждого из сегментов. Простой способ формирования нечеткой маски заключается в выделении центральной части изображения каким-либо графическим примитивом (наиболее универсальна прямоугольная область), данная область маски заполняется белым цветом и созданием плавных, градиентных переходов к границам маски от белого к черному цвету. В ходе практической реализации для формирования такой маски на вход подается значение ширины области градиентного перехода, иначе называемой шириной области сглаживания в виде процента от площади самого изображения, а положение и размеры центральной области интереса уже рассчитываются исходя из заданной величины. Ширина области сглаживания прямо пропорциональна плавности перехода между сегментами и фоном: чем больше ширина, тем плавней взаимные переходы. Способ адаптивного формирования нечеткой маски почти полностью повторяет описанный выше способ, за исключением того, что плавный градиентный переход от белого к черному цвету создается уже между аппроксимирующей областью и границами сегмента. Для обеспечения плавного перехода между сегментами при практической реализации прямо -угольная область исходного изображения, на которой производится выделение и аппроксимация ОИ, рассчитывается исходя из заданного параметра ширины области сглаживания. Такой способ гарантирует формирование ширины сглаживания заданной плавности и одновременно позволяет игнорировать случаи больших или неравномерно распределенных ОИ, которые могут локализоваться на границах сегмента и препятствовать созданию плавного перехода. Кроме 105 Математика, механика, информатика того, существует способ оптимизации ширины области сглаживания для случая малых ОИ - это способ апостериорной оценки площади выделенной ОИ. Суть данного метода заключается в том, что если площадь выделенной ОИ достаточно мала, то область ширины сглаживания можно увеличить вплоть до границ данного сегмента. Процесс наложения изображения сегмента на фоновое изображение происходит с использованием альфа-смешивания текстур по следующему принципу: белые области нечеткой маски дают на выходном изображении непрозрачные области изображения сегмента коллажа, черные области дают непрозрачные области фона, а оттенки серого цвета дают полупрозрачные сочетания фона и изображения оттенков коллажа по формуле: jOUt _ i j ~ I Г? • I- i J mask i,J ' (Imax Ii, j mask где i, j - координаты обрабатываемого пикселя; IOUt- значение интенсивности пикселя выходного изображения; Ise? - значение интенсивности пикселя изображения сегмента коллажа; I mask - значение интенсивности пикселя изображения нечеткой маски; Ibg -значение интенсивности пикселя фонового изображения; Imax - максимально допустимое значение интенсивности в выбранной цветовой модели. Нормируются значения IOUt также по значению Imax. Результирующее изображение после наложения всех сегментов коллажа на фоновое изображение по описанному принципу представляет собой выходное изображение коллажа, созданного с применением эффекта «бесшовная стыковка». Преимуществом адаптивного метода формирования бесшовной стыковки при создании фотоколлажей является способность находить и выделять ОИ на изображении, тем самым, исключая неинформативные области изображений, строить плавные естественные переходы между изображениями. Благодаря данным особенностям готовый коллаж получается наглядным, визуально привлекательным и гармоничным. Тестирование разработанной на основе описанного комплексного подхода программной системы интеллектуального составления коллажей CollAge проводилось посредством эмпирико-визуальной оценки полученных коллажей. Оценивались методы построения гибких контуров по трем параметрам (корректность выделения ОИ, плавность переходов между сегментами и общая информативность выходного изображения). Для наглядности изображения, полученные с помощью адаптивных методов выделения ОИ (метод блочного анализа и метод оценки формы), также сравнивались с изображениями, сформированными на основе бесшовной стыковки, но без выделения ОИ. По результатам тестирования метод блочного анализа был определен как наиболее эффективный по всем исследуемым характеристикам (рис. 1). Кроме того, был проведен анализ временных затрат на создание выходного изображения. По результатам тестирования метод блочного анализа мало уступает простому неадаптивному методу выделения ОИ (рис. 2). По общим результатам экспериментального исследования метод блочного анализа считается наиболее оптимальным для формирования выходных изображений. В ходе тестирования разработанный программный продукт показал стабильно высокие результаты в формировании наглядных выходных изображений коллажей, производящих впечатление целостной картины за счет плавных переходов между сегментами, созданных на основе метода «бесшовной стыковки». Информативность создаваемых коллажей также находится на очень высоком уровне благодаря точному выделению областей интереса, основанному на разработанных методах оценки формы и блочного анализа. Корректность ВЕЛЕНИЯ»! rWiSHOCibnepeiM« и-фори«и*мств коллажа Рис. 1. Сводная диаграмма анализа эффективности формирования выходных изображений 106 Вестник Сибирского государственного аэрокосмического университета имени академика М. Ф. Решетнева Рис. 2. Сводная диаграмма анализа временных затрат на формирование выходного изображения В дальнейшем планируется продолжить исследования в направлении повышения точности выделения областей интереса за счет совмещения методов блочного анализа и оценки формы. Метод блочного анализа будет усовершенствован таким образом, чтобы форма каждого отдельного «блоба» анализировалась и аппроксимировалась графическим примитивом наиболее подходящей формы. Предполагается также расширение критериев отбора кадров из видеоматериалов, например, поиск определенных объектов по заданному шаблону или поиск людей в видео по заданному эталонному изображению лица.

About the authors

E. L. Yaroslavtseva

Email: yaroslavtseva@inbox.ru

K. E. Levtin

Email: levtin@list.ru

References

Supplementary files