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

На правах рукописи

Сидякин Сергей Владимирович

РАЗРАБОТКА АЛГОРИТМОВ ПОСТРОЕНИЯ МОРФОЛОГИЧЕСКИХ СПЕКТРОВ ДЛЯ АНАЛИЗА ЦИФРОВЫХ ИЗОБРАЖЕНИЙ И ВИДЕОПОСЛЕДОВАТЕЛЬНОСТЕЙ

05.13.17 - Теоретические основы информатики

1 ноя 2013

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Москва - 2013

005537380

Работа выполнена в подразделении 3000 «Системы интеллектуального анализа данных, технического зрения, улучшенного и синтезированного видения» Федерального государственного унитарного предприятия «Государственный научно-исследовательский институт авиационных систем».

Научный руководитель: Официальные оппоненты:

доктор физико-математических наук, с.н.с. Визильтер Юрий Валентинович Местецкий Леонид Моисеевич доктор технических наук, профессор Международный университет в Москве, заведующий кафедрой информатики и математики

Майсурадзе Арчил Ивериевич кандидат физико-математических наук, Факультет вычислительной математики и кибернетики Московского государственного университета имени М. В. Ломоносова, доцент

Федеральное государственное бюджетное учреждение науки Институт проблем информатики Российской академии наук (ИПИ РАН)

Защита состоится "¿(О-^^ЭЛ- IQfZг. в i. £*0 мин. на заседании Диссертационного совета Д002.017.02 при Федеральном государственном бюджетном учреждении науки Вычислительном центре им. A.A. Дородницына Российской академии наук по адресу: 119333, г. Москва, ул. Вавилова, д. 40.

С диссертацией можно ознакомиться в библиотеке ВЦ РАН.

Ведущая организация:

Автореферат разослан О^^Л^рЯ J.0¿2т.

Ученый секретарь Диссертационного совета Д 002.017.02, доктор физико-математических наук, профессор

В. В. Рязанов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Особое положение среди методов описания формы занимают морфологические спектры по параметру масштаба детализации, предложенные П. Марагосом (1989) в рамках математической морфологии Серра. Они характеризуют степень содержания в исследуемой форме особенностей формы различного масштаба, задаваемых выбранным структурирующим элементом. Дальнейшие исследования показали, что морфологический спектр является достаточно удобным и востребованным инструментом анализа изображений. В частности, в работах Е. Догерти (1992) морфологические спектры успешно применялись для решения задач анализа текстуры и выделения мелкоразмерных объектов различных типов. В работе А. Асано (1999) был предложен способ вычисления характеристик текстуры с использованием морфологического спектра. М. Вилкинсон и П. Салембиер (2009) активно использовали морфологические спектры для адаптивной настройки параметров морфологической фильтрации и сегментации изображений. О. Барних (2006) использовал морфологические спектры для решения задач анализа формы объектов на видеопоследовательностях. Однако, несмотря на значительное количество исследовательских работ, практическое применение морфологических спектров до сих пор в существенной степени сдерживалось отсутствием эффективных в вычислительном смысле процедур их построения, позволяющих получать морфологические спектры в реальном времени.

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

зацией процедур вычисления базовых морфологических фильтров. В частности, Ван Другенброек и Талбот (1996), Винсент (2000), Гил и Киммел (2002) предложили ряд эффективных алгоритмов вычисления морфологических операторов Серра. Лучший из известных алгоритмов был предложен Е. Урбахом и М. Вилкинсоном (2008). Однако и при использовании этого алгоритма для вычисления спектра традиционным способом требуется слишком много времени. Таким образом, проблема вычисления морфологических спектров в реальном времени остается по-прежнему актуальной.

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

В последние годы появились предпосылки для решения указанных проблем формирования и сравнения морфологических спектров, связанные с алгоритмическими и математическими подходами, развитыми в рамках непрерывной бинарной морфологии, предложенной Л.М. Местецким, и обобщенной критериальной морфологии, предложенной Ю.В. Визильтером на основе работ Ж.Серра и Ю.П. Пытьева. Непрерывная бинарная морфология Л.М. Местецкого исследует способы описания формы объектов в цифровых бинарных изображениях с помощью непрерывных моделей (многоугольных границ, скелетов, циркуляров). В отличие от дискретного подхода, данный подход позволяет осуществлять анализ формы фигур в реальном времени. Математический аппарат критериальной проективной морфологии позволяет вскрыть единую математическую природу таких подходов как корреляционный анализ, математическая морфология Серра, морфология разбиений кадра Ю.П. Пытьева, методы голосования, восходящие к преобразованию Хафа, частотные и пространственно-частотные методы фильтрации. При этом многие практические инструменты, созданные в рамках морфологических систем одного типа, могут быть реализованы и для морфологий другого типа. В частности, в работе Ю.В. Визильтера (2008) была указана возможность построения спектра по параметру морфологической сложности. Однако ни для одной конкретной морфологии такие спектры ранее не были построены.

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

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

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

При этом решались следующие задачи:

1) Разработка вычислительно эффективных алгоритмов построения морфологических спектров для бинарной и полутоновой морфологии Серра на основе непрерывной бинарной морфологии;

2) Разработка алгоритмов построения обобщенных морфологических спектров сложности на основе проективной критериальной морфологии;

3) Разработка алгоритмов сравнения морфологических спектров, применимых в задачах классификации объектов по форме;

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

Диссертационная работа выполнена в подразделении 3000 «Системы интеллектуального анализа данных, технического зрения, улучшенного и синтезированного видения» ФГУП «ГосНИИАС» на основе исследований, проводившихся при поддержке РФФИ в рамках грантов №09-07-13551-офи ц, М1-08-01114-а, №11-08-01039-а, №12-07-31218-мол а.

Методы исследования. Теоретические исследования выполнены на основе методов компьютерного зрения, математической морфологии, вычислительной геометрии, методов динамического программирования. Экспериментальные исследования проводились на реальных и синтезированных примерах цифровых изображений в средах Pisoft, Borland Delphi 7, Microsoft Visual Studio. Достоверность результатов, проведенных исследований подтверждена программным моделированием.

Научная новизна диссертационной работы состоит в следующем:

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

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

ных уровней пороговой сегментации при помощи метода динамического программирования.

3) Разработан новый подход к сравнению морфологических спектров, отличающийся использованием ЕМБ метрики. Для случая ЕМБ — Ь1 метрики (расстояния Вассерштайна 1-го порядка) доказана устойчивость сравнения морфологических спектров при помощи ЕМИ метрик к сочетанию площадных и контурных искажений формы фигур.

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

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

На защиту выносятся следующие положения:

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

2) Доказана устойчивость сравнения морфологических спектров при помощи ЕМБ — Ь1 метрик (расстояний Вассерштайна 1-го порядка) к сочетанию площадных и контурных искажений формы фигур, характеризуемых расстояниями Ь1 и Хаусдорфа между сравниваемыми фигурами.

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

4) Непрерывный алгоритм построения критериальных морфологических спектров позволяет вычислять точные значения морфологических спектров сложности, что повышает их информативность и надежность

сравнения таких спектров между собой.

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

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

Апробация работы. Основные результаты работы докладывались автором на следующих международных и российских конференциях: "10-th International Conference Pattern Recognition and Image Analysis" (Санкт-Петербург. 2010), "Интеллектуализация обработки информации" (Будва, 2012), 2-ая конференция молодых ученых и специалистов московского отделения международной общественной организации "Академия навигации и управления движением" (Москва, 2009), "Математические методы распознавания образов" (Петрозаводск, 2011), "Моделирование авиационных систем" (Москва, 2011), "Техническое зрение в системах управления" (Москва, 2012, 2013).

Публикации. По результатам диссертационной работы опубликовано 13 работ, в том числе 8 научно-технических статей в изданиях, включенных в перечень ВАК.

Объем и структура работы. Диссертационная работа состоит из введения, пяти глав, заключения и списка литературы (94 наименования). Работа содержит 163 станицы, 71 рисунок и 6 таблиц.

СОДЕРЖАНИЕ РАБОТЫ

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

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

структурирующим элементом В.

В непрерывном случае:

РБх{г, В) = -дБ(Х о гВ)/дг, г > 0. (1)

В дискретном случае:

РЗх(г, В) = Б{Х о гВ) - Б(Х о (г + 1)В), г ^ 0, (2)

где о г В) - площадь открытия объектов на изображении X.

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

В последние годы появились предпосылки для решения указанных проблем формирования и сравнения морфологических спектров, связанные с алгоритмическими и математическими подходами, развитыми в рамках непрерывной бинарной морфологии, предложенной Л.М. Местецким, и обобщенной критериальной морфологии, предложенной Ю.В. Визильтером на основе работ Ж. Серра и Ю.П. Пытьева. Непрерывная бинарная морфология и обобщенная критериальная морфология кратко изложены в разделах 1.3 и 1.4.

Вторая глава состоит из трёх разделов.

Раздел 2.1 посвящён разработке эффективного алгоритма вычисления морфологических спектров плоских фигур. Он основан на использовании непрерывных скелетных представлений бинарных фигур, введённых в работах Л.М. Местецкого. Сравнение непрерывной скелетной морфологии (НСМ) с известными ранее непрерывной и дискретной математическими морфологиями (ММ) Серра показывает, что НСМ можно считать специфической реализацией бинарной ММ, в которой за счет наложения дополнительных ограничений на форму бинарных образов (они должны быть приближённо описаны многоугольной границей) становится возможным вычислять результаты морфологических операций в непрерывно-аналитическом виде. Вычислительная эффективность НСМ по сравнению с ММ определяется тем, что от исходного описания изображения в виде дискретной матрицы пикселей осуществляется переход к гораздо более компактному описанию формы в виде набора

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

Алгоритм 1.

Шаг 1. Представить бинарное изображение в виде непрерывной многоугольной фигуры Р.

Шаг 2. Вычислить скелетное представление б'Д(^).

Шаг 3. Создать аккумулятор равный размеру изображения. Инициализировать все ячейки аккумулятора нулями.

Шаг 4• Выбрать очередное ребро из списка ребер скелета и перейти к шагу 5. Если список пуст, перейти к шагу 6.

Шаг 5. Текущее ребро скелета представить в дискретном виде при помощи обобщений алгоритма Брезенхэма для случаев растеризации прямых и парабол, образовав набор точек {р,}, характеризуемых координатами (^¿,уг) центра и радиусом и соответствующих пустых кругов. Для каждой точки р; при помощи обобщения алгоритма Брезенхэма для растеризации окружности, построить диск радиуса п в аккумуляторе, поместив в соответствующие ячейки значение радиуса г^ если Г{ больше текущего значения в рассматриваемой ячейке, в противном случае -оставить ее без изменений. Вернуться к шагу 4-

Шаг 6. Вычислить морфологический спектр как гистограмму значений аккумулятора.

Конец Алгоритма 1.

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

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

Рис. 1. Дискретно-непрерывный морфологический спектр и пиковые составляющие

формы фигуры.

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

В разделе 2.2. предложен оригинальный подход к вычислению морфологических спектров полутоновых изображений с дисковыми структурирующими элементами, основанный на использовании непрерывных скелетных представлений плоских фигур и уровневого разложения морфологических операций. Рассмотрим стековое разложение морфологических операторов. Пусть дана дискретная iV-уровневая двумерная функция f{x,y) в {0,1,... ,N - 1} С Z, (х, у) G R2. Определим срез функции на уровне г £ {0,..., N} С Z как бинарную функцию

Mx,y) = {i:f(x,y)>i-,0-.f(x,y)<i}.

Полным срезовым стеком функции f(x,y) назовем упорядоченный набор ее срезов f = (/о(г, у),..., /аг(ж, у)), на основе которых можно определить оператор реконструкции срезового стека 5:

f(x,y) =6f= Ei=0.....Nfi(x,y) = máximo.....jv{í x fi{x,y)}.

При этом между любыми срезами fi{x,y) и fp(x,y) выполняется т.н. стековое свойство: р> г =i> /¿(а;, у) ^ fP{x,y). Стек начинается наибольшим (единичным) и заканчивается наименьшим (нулевым) бинарным образом: fo(x,y) = 1и /ы(х,у) = 0.

Рассмотрим частный случай полутоновой морфологии Серра, с т.н. «плоскими» (fiat) бинарными структурирующими элементами Ь(и, v) 6 € {0,1}. Как показано в работе Митчела (1989), в этом случае фильтры полутоновой морфологии Серра могут быть представлены в виде разложения на соответствующие срезовые бинарные морфологические операции:

f{x, у) о Ь(и, v) = £,-=о.....x{fi(x, у) о Ь(и, и)} =

= maxi=0,...,N{i х fi{x,y) о b(u,v)}.

Отсюда вклад «объекта» в полутоновой спектр на г'-ом уровне:

PSfi{r, Ъ) = —dS(fi о Ъ)/дг, г ^ 0. (3)

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

N

PSf = ^^CiPSji(r, Ь) (4)

г=1

Ci = (hist[i] - hist[i - 1])/255, i € N, (5)

где с, - коэффициент значимости уровня. Таким образом, для вычисления точного морфологического спектра iV-градационного полутонового изображения с дисковым структурирующим элементом потребуется в N раз больше времени, чем для построения спектра одного бинарного изображения. Однако, если точное построение спектра не требуется, а достаточно лишь получение приближенного решения, характеризующего основные особенности формы, скорость вычислений может быть существенно увеличена за счет использования меньшего числа бинарных срезов, аппроксимирующих полутоновое изображение. Выбор необходимого числа срезов определяется числом существенных мод гистограммы. В данной работе способ автоматического выделения мод гистограммы основывается на оптимизации глобального критерия разделимости на п > 1 мод, подобного критерию бимодальной разделимости Отсу. Введем (n + 1) - мерный вектор t = (to,.. •, tn), где to = 0, tn = 255, 11,..., in-i - свободные переменные, соответствующие порогам, разделяющим моды

гистограммы. Тогда среднеквадратичный критерий оптимального выбора порогов сегментации будет иметь следующий вид:

¿=0,..,п

где Б13Р(и, - значение дисперсии фрагмента гистограммы изображения на отрезке (и, £,+].)■ Поскольку гистограмма - одномерный массив, эта задача однозначно решается методом динамического программирования. В результате определяется такой набор порогов сегментации, который обеспечивает минимальное среднеквадратичное отклонение сегментированного на п уровней изображения от исходного. Если число мод гистограммы заранее неизвестно, то задача гистограммной сегментации является некорректной по Адамару и требует регуляризации. В качестве регуляризующего критерия можно применить, например, следующий критерий, одновременно штрафующий и суммарное среднеквадратичное отклонение сегментированного изображения от исходного, и число выделяемых при сегментации мод:

У^ и+х) + а • п тгп(п, ..., ¿„-г).

г=0 ,...,п

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

Алгоритм 2.

Шаг 0. Выбрать первый уровень из списка уровней изображения.

Шаг 1. Представить бинарное изображение текущего уровня в виде непрерывной многоугольной фигуры (7.

Шаг 2. Вычислить срезовый спектр РБо{г, Ь) (Алгоритм 1).

Шаг 3. Выбрать изображение, соответствующее следующему уровню, и перейти к шагу 1. Если все уровни пройдены, то перейти к шагу 4-

Шаг 4- Все вычисленные срезовые спектры суммировать в общий полутоновой спектр с учетом коэффициентов значимости уровней в соответствии с формулами (4)-(5).

Конец Алгоритма 2.

Рассмотренный алгоритм позволяет эффективно формировать дискретно-непрерывные морфологические спектры полутоновых

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

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

Предлагается сравнивать морфологические спектры при помощи EMD-метрик, введенных в работе (Рабнер, Томази и др., 2000) и используемых для сравнения «гистограммоподобных» объектов-описаний, представленных конечным множеством (массивом) пар {Pi, hpгде Pi -i-й «объект» описания, a hpi - его «вес» (значимость в описании). Если при этом известная некоторая базовая (Earth) метрика (is, позволяющая попарно сравнивать объекты, то на основе этой базовой метрики может быть определена EMD-метрика для сравнения двух «гистограммоподобных» описаний Р и Q:

dEMD{P, Q) == min{h,.} 12 MB(fi.Qi). (6)

12 = Ц = 12 12 hii =

j=l,..m i=l,..,n j=l,..,mi=l,.,n

Vi, j : кц > 0, hPi= hij, hQj = fry.

В общем случае расстояние (6), являющееся частным случаем метрики Монжа-Канторовича, вычисляется путем решения т.н. «транспортной задачи» методом линейного программирования. В частном случае, когда гистограммы Р(^) и Q(j/j) являются одномерными дискретными массивами, они могут рассматриваться как эмпирические плотности распределения одномерных случайных величин € Я. В работе (Валландер, 1973) было показано, что если базовой метрикой на R является L1 и Sj=i. mQiVj) = Et=i,..,n^0E»)> т0 расстояние (6) оказывается частным случаем расстояния Вассерштайна 1-го порядка, то есть EMD — L1 расстояние можно вычислить по следующей формуле (Деза, 2008):

/+0О

|F(x)-G(x)|da;, (7)

-ОО

где F{x) и G(x) — функции распределения для P(Xi) и Q(yj):

/X гх

P(t) dt, G(x) = / Q(t)dt

•00 J —oo

Таким образом, на основе формулы (7) можно реализовать алгоритм вычисления ЕМ И - Ь1 расстояния между двумя одномерными гистограммами за линейное время, не требующий решения в явном виде задачи линейного програмирования.

Рассмотрим проблему устойчивости сравнения морфологических спектров при помощи ЕМИ - Ь1 метрик к сочетанию площадных и контурных искажений формы фигур.

Введем понятие карты толщин. Пусть дана бинарная фигура X, целиком помещающаяся в кадр К : X С. К. Обозначим Хс(-К] = К \Х - дополнение или фон фигуры X в кадре К. Тогда фигуре X можно поставить в соответствие бинарное изображение:

, (I если р = (х,у) € Х\ /оч

0 еслир = (х,у)еХ°™ ^

Выберем в качестве структурирующего элемента бинарную фигуру В(^г) (например, диск В) с центром в точке я = (х,у) = и

размерным параметром г.

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

В случае дискретного изменения размера г структурирующего элемента с шагом Дг карта толщин Тв,дг(/х) имеет следующий вид:

Тв,дг(/х)= и,в,Дг(®,1/) = (9)

( -тахг^к){{х!У) € В{4,г) С : {х,у) €

= { 0 :{х,у)£дХ = дХсЮ-,

( тахтеП2(К){(.х, у) € В(ч, г) С X} : (х, у) € X, ,

где Кг (К) - множестве дискретных значений размерного параметра г.

В диссертационной работе показано, что дискретный морфологический спектр Марагоса (2) есть плотность распределения (гистограмма) значений карты толщин (9) бинарного изображения.

Устойчивость признакового описания изображения будем понимать в следующем смысле. Пусть имеются метрические пространства образов (изображений) и (П.рпг) с совпадающими опорными множе-

ствами образов и различными метриками рпиРП2 соответственно, и

метрическое пространство описаний Л с метрикой р,\. Оператор описания ф : О, —> Л изображения будем называть устойчивым на тройке метрических пространств ((Г2,№2),(Л,рл)), если для всякого е > 0 существуют такие > 0, ^(е) > 0, что для любых двух

образов Л, S € П из неравенств /?ni(A-B) < Рт{А, В) < б^е) следует неравенство р\(фА, фВ) < е, Описание, формируемое устойчивым оператором, будем также называть устойчивым.

Утверждение 1. Пусть имеются метрические пространства бинарных изображений и (Çl,dii) с совпадающим опорным мно-

жеством S7 и различными метриками cf#, du (расстояние Хаусдорфа и расстояние L1 соответственно), и метрическое пространство дискретных морфологичесих спектров А с метрикой dEUD-V- (EMD метрика с базовым расстоянием L1). Тогда оператор ф : Q —)■ Л описания бинарного изображения его морфологическим спектром является устойчивым на тройке метрических пространств ((Г2, djj),{Çi, rf^i),(Л, dEMD-L1)), причем для всякого е > 0 существуют такие 5\(е) = е/2 > О, ^(е) = ^/4гта1 > 0, что для любых двух образов А, В Ç О из неравенств dj}(A, В) < <5i(e), di,\{A, В) < ^(е) следует неравенство ¿emo-l1 {ФА, фВ) < е, где rmax - максимальный радиус диска, вписанного в кадр конечной площади.

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

Утверждение 1.1. Оператор описания изображения А его нормализованной гистограммой H (А) является устойчивым на паре метрических пространств ((fi,c?£i), (A^emo-l1))'-

dv(A, В) ^е => dEMD_v{H{A), H (В)) < е.

У т в е р ж д е н и е 1.2. Дискретный морфологический спектр PSA,D,&r изображения А пропорционален нормализованной гистограмме дискретной карты толщин HtADt&r-

PSA,dat = (S/&r)HtADAr,

где S - площадь кадра, Дг - шаг изменения размерного параметра г.

Утвержден и е 1.3. Дискретная карта толщин ¿л.длг является устойчивым описанием бинарных изображений на паре метрических пространств ((О/, dgj), (&т> d^)), где fi/ - пространство бинарных изображений, Î2r - пространство карт толщин, где йнн{А, В) = 2rmaxdi,i(A, В) + djj(A, В) - метрика, сочетающая оценку

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

<1нн{АI В) < е dL\(tA,DAT^B,DAr) ^ е-

То есть, малое изменение формы фигуры на изображении влечет малое изменение карты толщин.

Из утверждений 1.1, 1.2, 1.3 следует:

<Iemd-l1(PSai PSb) ^ 2rmaid£,i(Л, В) + djj(A, В) < 2гтах52 = 2rmaxe/4rmax + е/2 = е/2 + е/2 = е,

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

Далее в разделе 2.3 рассматриваются усеченные морфологические спектры, включающие положительные элементы спектра, соответствующие фигуре без фона, дополненные одним нормировочным отсчётом, соответствующим фону. Показано, что такие усеченные спектры являются инвариантными к сдвигам, поворотам и масштабированию фигуры внутри кадра. Экспериментально показано, что EMD — L1 расстояния между усеченными спектрами могут успешно использоваться для решения задач классификации объектов по форме. Примеры классификации условных силуэтов по форме (dataset Myth) с использованием формулы (7) изображены на рисунке 2. В таблице 1 приведены средние внутриклассовые и межклассовые EMD—L1 расстояния между спектрами. Как видно, межклассовые расстояния существенно больше внутриклассовых, что позволяет осуществлять распознавание фигур по форме.

Были также рассчитаны показатели быстродействия алгоритмов ске-летизации, построения морфологического спектра и EMD — L1 метрики. Общее среднее время построения спектра и классификации одного изображения (635 х 475 пикселей) не превышает 22 миллисекунды.

Люди Кентавры Лошади

Люди 0,812 3,054 6,31

Кентавры 3,054 0,69 2,25

Лошади 6,31 2,25 0,78

Таблица 1. Средние внутри- и межклассовые EMD — L1 расстояния для Myth.

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

Рис. 2. Сравнение фигур по морфологическим спектрам с использованием ЕМ £> — Ь1 метрики.

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

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

Рис. 3. Примеры регуляризации контура и скелета листа кленового дуба, а -параметр качества регуляризации.

Четвертая глава посвящена разработке алгоритмов построения критериальных морфологических спектров сложности. Описано обобще-

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

Пусть задан критерий морфологического риска вида

Ра{А,Ь) = 3{А,Ь) + аЯ{Ь), (10)

где А,ЬС£1- изображения или образы; Ь) е [0, +оо) - функционал (критерий) соответствия морфологической реконструкции Ь наблюдаемому образу А; Я{Ь) е [0,+оо) - функционал (критерий) качества морфологической реконструкции Ь; а > 0 - действительное число, называемое моделирующим параметром. На основе заданного критерия (10) определяется критериальный морфологический фильтр

фаА = агдттЬецРа{А, Ь), (11)

являющийся идемпотентным оператором на О. ('ф\ = фа)- При этом а ^ Р =>• фрфа = Фа, что в точности соответствует отношению морфологической сложности, введенному Пытевым. С увеличением значения структурирующего параметра а морфологическая сложность модели, которую определяет проектор, монотонно убывает. Таким образом, структурирующий параметр а также можно назвать параметром морфологической сложности модели.

Определим теперь критериальный морфологический спектр по параметру морфологической сложности а по аналогии с выражением (1) для площадного спектра Марагоса через к производную от критерия соответствия по данному параметру:

Р5(Л, а) = дJ{A, фаА)/да. (12)

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

/

морфологической сложности с учетом зависимостиг(а). Основанием для этого является формула дифференцирования сложной функции:

PS(A, а) = dJ(A, A{a)A)/da = J'r{A, фг{а]А)г'а{а), (13)

где J'r(A,A(a)A) = dJ{A,iPT[a)A)/dr, r'a{a) = дг(а)/да.

Для приближенного вычисления спектра сложности (12) на основе (13) был предложен дискретный двухэтапный алгоритм, описанный в разделе 4.2 диссертационной работы.

Другая вычислительная схема, описанная в разделе 4.3, позволяет строить точные непрерывные морфологические спектры сложности фигур и изображений даже в тех случаях, когда нет явного структурирующего параметра г, от которого зависит сложность модели а. Используемый при этом алгоритм точного построения кусочно-линейной функции минимума критерия морфологического риска от параметра морфологической сложности аналогичен методам Ньютона и Динкель-баха, применяемым, в частности, для поиска экстремумов рациональных функций (Колмогоров, Бойков, Ротер, 2007). Суть метода в следующем.

Определим функцию, представляющую собой минимум критерия морфологического риска (10) от параметра морфологической сложности:

F(a) = minaFa(A, L). (14)

Решения L\,...,Lk 6 Ь, оптимальные, по крайней мере, для одного значения параметра а, будем называть доминантными решениями. На интервале I = [amin,атах], необходимо вычислить решения Li,...,Lfc и интервалы доминирования I\ = [атгп,а1],12 = [а1, а2],..., h = [afc_1, атах] для каждого соответствующего решения. После этого функция (14) строится как нижняя огибающая найденного множества доминантных решений, а функционал J(A,L) для каждого интервала доминирования h рассчитывается в аналитической форме по известным значениям J(A, L,). На заключительном этапе предложенного алгоритма непрерывный спектр PS (А, а) определяется путем непосредственного дифференцирования J(A, L) по а.

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

В разделе 5.1 решается задача проверки подлинности

металлографской печати с использованием морфологических спектров.

Для автоматического определения подлинности металлографской

печати путем контроля качества металлографских усиков ранее

/

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

Рис. 4. Слева - морфологический спектр подлинной марки; справа -морфологический спектр поддельной марки.

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

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

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

Общая архитектура системы автоматической классификации движущихся объектов имеет следующий вид:

1) Выделение объекта из видеопотока, осуществляемое на основе кратнорегрессионных псевдоспектров и алгоритмов выделения связных областей (Вишняков, Визильтер, 2011);

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

3) Классификация объекта на основе экстремально случайных деревьев (Геуртс, Эрнст и др., 2006). Используемая стратегия выбора необходимого количества дисков из покрытия заключается в том, что нужно выбрать N дисков, которые содержат максимальное число уникальных пикселов.

т

§ ® %

Рис. 5. Примеры покрытия для различных человеческих фигур.

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

2. Разработаны алгоритмы сравнения морфологических спектров на основе ЕМ И метрики для решения задачи классификации объектов по форме. Для случая ЕМБ метрики с базовым расстоянием Ь1 (расстояния Вассерштайна 1-го порядка) доказана устойчивость сравнения морфологических спектров при помощи ЕМБ — Ь1 метрик к сочетанию площадных и контурных искажений формы фигур, характеризуемых расстояниями Ь1 и Хаусдорфа между сравниваемыми фигурами. Экспериментально показано, что ЕМ Б — Ь1 расстояния между инвариантными усеченными спектрами могут успешно использоваться для решения задач классификации сложных объектов по форме в случае достаточно разнообразного распределения локальной толщины фигуры.

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

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

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

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

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

Публикации в журналах из перечня ВАК

1) Сидякин C.B., Визильтер Ю.В, Регуляризация гранично-скелетных представлений формы бинарных фигур методом динамического программирования // Вестник компьютерных и информационных технологий, 2011, № 9, С. 9-16.

2) Сидякин C.B., Рубис А.Ю., Горбацевич B.C. Построение и использование морфологических коэффициентов корреляции в задачах анализа изображений // Вопросы оборонной техники. Сер. 9. Специальные системы управления, следящие приводы и их элементы, 2010, Выпуск 3(244) - 4(245), С. 53-59.

3) Vizi J ter Yu., Sidy akin S., Rubis A., Gorbazevich V. Morphological shape comparison based on skeleton representations // Pattern Recognition and Image Analysis, 2012, vol. 22, № 3, pp. 412-418.

4) Визильтер Ю.В., Сидякин C.B. Построение морфологических спектров полутоновых изображений // Вестник компьютерных и информационных технологий, 2012, №4, С. 8-17.

5) Визильтер Ю.В., Сидякин G.B. Построение спектров морфологической сложности // Вестник компьютерных и информационных технологий, 2012, №11, С. 3-8.

6) Визильтер Ю.В., Сидякин C.B. Использование морфологических спектров для классификации двумерных фигур и бинарных изображений // Вестник компьютерных и информационных технологий, 2013, №7, С. 20-28.

7) Визильтер Ю.В., Сидякин C.B. Бициклические каркасы двумерных фигур // Вестник компьютерных и информационных технологий, №10, 2012, С. 17-21.

8) Vizilter Yu., Sidyakin S., Rubis A., Gorbazevich V. Skeleton-based morphological shape comparison // Pattern Recognition and Image Analysis, 2011, vol. 21, № 2, pp. 357-360.

Публикации в других изданиях

9) Визильтер Ю.В., Сидякин C.B., Рубис А.Ю. Вычисление морфологических спектров плоских фигур с использованием непрерывных скелетных представлений // Математические методы распознавания образов: 15-я Всероссийская конференция. г.Петрозаводск, 11-17 сентября

2011 г.: сборник докладов. -М.: МАКС Пресс, 2011, С. 416-419.

10) Визильтер Ю. В., Сидякин С. В. Построение обобщенных скелетов многоугольных бинарных фигур с многоугольными выпуклыми структурирующими элементами // 9-я международная конференция. «Интеллектуализация обработки информации», Черногория, г. Будва,

2012 г.: Сборник докладов. - М.: Торус Пресс, С. 414-418

11) Визильтер Ю.В., Сидякин C.B. Бициклические каркасы двумерных фигур // Техническое зрение в системах управления - 2012. Труды конференции. Москва, ИКИ РАН, 2012 г., С. 258-264.

12) Визильтер Ю.В., Сидякин C.B. Морфологические спектры // Техническое зрение в системах управления - 2012. Труды научно-технической конференции. Москва, ИКИ РАН, 2012 г., С. 234-241.

13) Горбацевич B.C., Визильтер Ю.В., Рубис А.Ю., Сидякин C.B. Морфологические методы анализа изображений земной поверхности // Моделирование АС, 2011 г. - М.: ФГУП «ГосНИИАС», С. 269-278.

Подписано в печать 20 октября 2013г. Тираж 100 экз. Отпечатано с готовых оригинал-макетов ФГУП ГосНИИАС, 125319, Москва, ул. Викторенко, 7.

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

На правах рукописи

04201365538

Сидякин Сергей Владимирович

РАЗРАБОТКА АЛГОРИТМОВ ПОСТРОЕНИЯ МОРФОЛОГИЧЕСКИХ СПЕКТРОВ ДЛЯ АНАЛИЗА ЦИФРОВЫХ ИЗОБРАЖЕНИЙ И ВИДЕОПОСЛЕДОВАТЕЛЬНОСТЕЙ

05.13.17 — Теоретические основы информатики

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель

доктор физико-математических наук,

с.н.с. Ю. В. Визильтер

Москва - 2013

Оглавление

Введение 6

1 Методы анализа формы изображений, математические морфологии и морфологические спектры 14

1.1. Современное состояние исследований в области описания и сравнения форм.................................. 14

1.2. Морфология Серра и морфологические спектры Марагоса ..... 18

1.2.1. Морфологические операции на бинарных и полутоновых изображениях ......................................................19

1.2.2. Морфологические спектры на структурирующих элементах . 23

1.2.3. Известные алгоритмы вычисления морфологических операторов и морфологических спектров..............................31

1.2.4. Практические приложения морфологических спектров .... 34

1.3. Непрерывная морфология бинарных изображений Л. М. Местедкого 36

1.4. Критериальная проективная морфология и критериальные морфологические спектры........................................................41

1.5. Выводы по Главе 1..........................................................45

2 Разработка алгоритмов построения морфологических спектров с использованием непрерывной бинарной морфологии 46 2.1. Вычисление морфологических спектров плоских фигур с использованием непрерывных скелетных представлений............ 46

2.1.1. Непрерывно-аналитический подход к вычислению морфологических спектров на основе скелетных представлений .... 47

2.1.2. Вычислительно эффективные алгоритмы растеризации ребер непрерывного скелетного представления............ 50

2.1.3. Дискретно-непрерывный алгоритм вычисления морфологических спектров на основе скелетных представлений..... 62

2.2. Построение морфологических спектров полутоновых изображений . 67

2.2.1. Полутоновая морфология Серра и морфологические спектры полутоновых изображений.................... 67

2.2.2. Стековый алгоритм вычисления морфологического спектра полутоновых изображений с плоским структурирующим элементом ............................... 68

2.2.3. Примеры построения морфологических спектров полутоновых изображений .........~................ 72

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

2.3.1. ЕМЭ-метрики ........................... 78

2.3.2. Устойчивость описаний и робастное сравнение ........ 81

2.3.3. Схема доказательства устойчивости сравнения морфологических спектров бинарных фигур при помощи ЕМ И метрик . 83

2.3.4. Робастное сравнение гистограмм изображений при помощи ЕМ Б метрик............................ 85

2.3.5. Преобразование Марагоса и его связь с морфологическими спектрами.............................. 88

2.3.6. Устойчивость дискретных преобразований Марагоса (карт толщин) бинарных изображений................. 92

2.3.7. Устойчивость дискретных морфологических спектров фигур 96

2.3.8. Усеченные спектры. Инвариантность к сдвигу и повороту фигур. Сравнение форм при помощи усеченных морфологических спектров.......................... 97

2.3.9. Экспериментальное исследование алгоритма сравнения морфологических спектров в задачах классификации объектов

по форме..............................100

2.4. Выводы по Главе 2.............................104

3 Разработка алгоритма регуляризации гранично-скелетных представлений формы бинарных фигур 106

3.1. Проективная морфологическая регуляризация контурных многоугольников .................................108

3.2. Алгоритм динамического программирования для решения задачи РГСП.....................................110

3.3. Результаты тестирования процедуры РГСП..............112

3.4. Выводы по Главе 3.............................114

4 Разработка алгоритмов построения морфологических спектров по параметру сложности 115

4.1. Критериальные проективные морфологии и морфологические спектры по параметру сложности....................115

4.2. Алгоритм вычисления дискретного морфологического спектра по параметру сложности...........................117

4.3. Алгоритм построения непрерывных морфологических спектров по параметру сложности...........................122

4.4. Выводы по Главе 4.............................129

5 Практические приложения 130

5.1. Использование морфологических спектров в задаче проверки подлинности металлографской печати .................130

5.1.1. Морфологическое выделение особенностей формы металлографских усиков..........................131

5.1.2. Примеры морфологических спектров металлографской печати 136

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

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

5.2.1. Выделение движущегося объекта-кандидата из видеопотока 143

5.2.2. Построение вектора признаков выделенного движущегося объекта на основе карты толщин ................147

5.2.3. Классификация движущегося объекта.............148

5.2.4. Экспериментальные результаты.................149

5.3. Выводы по Главе 5.............................152

Заключение 153

Список литературы 155

Введение

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

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

Как было показано многими исследователями, морфологический спектр является достаточно удобным и востребованным инструментом анализа изображений. В частности, в работах Е Догерти (1992) морфологические спектры успешно применялись для решения задач анализа текстуры и выделения мелкоразмерных объектов различных типов. В работе А Асано (1999) был предложен способ вычисления характеристик текстуры с использованием морфологического спектра. Анализом текстуры применение морфологического спектра не ограничилось М

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

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

Высокая вычислительная сложность построения морфологического спектра связана с тем, что его определение, данное Марагосом, требует выполнения одной операции открытия (закрытия) всего изображения на каждый отсчет спектра. "В связи с этим возможность ускорения процедур вычисления спектров традиционно связывались с оптимизацией процедур вычисления базовых морфологических фильтров. В частности, Ван Другенброек и Талбот (1996), Винсент (2000), Гил и Киммел (2002) предложили ряд эффективных алгоритмов вычисления морфологических операторов Серра. Лучший из известных алгоритмов был предложен Е. Урбахом и М. Вилкинсоном (2008). При этом он позволял строить морфологические спектры для произвольного структурирующего элемента. Однако и при использовании этого алгоритма для вычисления спектра традиционным способом требуется слишком много времени. Таким образом, проблема вычисления морфологических спектров в реальном времени остается по-прежнему актуальной.

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

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

непрерывных моделей (многоугольных границ, скелетов, циркуляров). В отличие от дискретного подхода, данный подход позволяет осуществлять анализ формы фигур в реальном времени. Математический аппарат критериальной проективной морфологии позволяет вскрыть единую математическую природу таких подходов как корреляционный анализ, математическая морфология Серра, морфология разбиений кадра Ю.П. Пытьева, методы голосования, восходящие к преобразованию Хафа, частотные и пространственно-частотные методы фильтрации. При этом многие практические инструменты, созданные в рамках морфологических систем одного типа, могут быть реализованы и для морфологий другого типа. В частности, в работе Визильтера (2008) была указана возможность построения спектра по параметру морфологической сложности. Однако ни для одной конкретной морфологии такие спектры ранее не были построены.

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

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

При этом решались следующие задачи:

1) Разработка вычислительно эффективных алгоритмов построения морфологических спектров для бинарной и полутоновой морфологии Серра на основе непрерывной бинарной морфологии;

2) Разработка алгоритмов построения обобщённых морфологических спектров по параметру сложности на основе проективной критериальной морфологии;

3) Разработка алгоритмов сравнения морфологических спектров, применимых в задачах классификации объектов по форме;

4) Разработка прикладных алгоритмов морфологического анализа изображений на основе морфологических спектров и непрерывной бинарной морфологии

Диссертационная работа выполнена в подразделении 3000 «Системы интеллектуального анализа данных, технического зрения, улучшенного и синтезированного видения» Федерального государственного унитарного предприятия «Государственный научно-исследовательский институт авиационных систем» на основе исследований, проводившихся при поддержке РФФИ в рамках грантов №09-07-13551-офи ц, №11-08-01114-а, №11-08-01039-а, №12-07-31218-мол а.

Методы исследования. Теоретические исследования выполнены на основе методов компьютерного зрения, обработки изображений, математической морфологии, вычислительной геометрии, методов динамического программирования. Экспериментальные исследования проводились на реальных и синтезированных цифровых изображениях в средах Pisoft, Borland Delphi 7, Microsoft Visual Studio. Для реализации алгоритмов использовались языки Object Pascal и С++. Достоверность полученных результатов подтверждена программным моделированием.

Научная новизна диссертационной работы состоит в следующем:

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

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

3) Разработан новый подход к сравнению морфологических спектров, отличающийся использованием EMD метрики. Для случая EM D — L1 метрики (расстояния Вассерштейна 1-го порядка) доказана устойчивость сравнения морфологических спектров при помощи EMD метрик к сочетанию площадных и контурных искажений формы фигур.

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

5) Предложены алгоритмы вычисления дискретных и непрерывных критериальных морфологических спектров по параметру морфологической

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

На защиту выносятся следующие положения:

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

2) Доказана устойчивость сравнения морфологических спектров при помощи ЕМ И — Ь1 метрики (расстояния Вассерштейна 1-го порядка) к сочетанию площадных и контурных искажений формы фигур, характеризуемых расстояниями Ь1 и Хаусдорфа между сравниваемыми фигурами.

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

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

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

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

времени.

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

1. 2-ая конференция молодых учёных и специалистов московского отделения международной общественной организации "Академия навигации и управления движением". - г. Москва, 2009;

2. 10-th International Conference Pattern Récognition and Image Analysis: New Information Technologies (PMA-10-2010). - г. Санкт-Петербург. 2010;

3. 15-я Всероссийская конференция "Математические методы распознавания образов". - г. Петрозаводск, 2011;

4. Юбилейная научно-техническая конференция "Моделирование авиационных систем". - г. Москва, 2011;

5. Научно-технические конференции "Техническое зрение в системах управления". - г. Москва, 2012, 2013;

6. 9-я Международная конференция "Интеллектуализация обработки информации". - Черногория, г. Будва, 2012;

Публикации. Основные результаты диссертационной работы опубликованы в 8 статьях в журналах, входящих в перечень ВАК [1] - [8], в сборниках трудов [9]

- [13].

Объем и структура работы. Диссерта