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

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

005004640

ЛАРИОНОВ Игорь Борисович

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

Специальность 05.13.01 - Системный анализ, управление и обработка информации (в промышленности) .

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

-1 ДЕК 2011

Уфа - 2011

005004640

Работа выполнена в ФГБОУ ВПО «Омский государственный университет им. Ф.М. Достоевского» на кафедре информационной безопасности

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

Официальные оппоненты:

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

д-р физ.-мат. наук, проф. Белим Сергей Викторович

кафедра информационной безопасности Омского государственного университета им.Ф.М.Достоевского

д-р техн. наук, проф. Валеев Сагит Сабитович

кафедра информатики Уфимского государственного авиационного технического университета

д-р физ.-мат. наук, проф Зыкина Анна Владимировна

кафедра прикладной математики и фундаментальной информатики Омского государственного технического университета

ФГБОУ ВПО «Тюменский государственный университет»

Защита состоится 21 декабря 2011 г. в 10 часов 00 мин. на заседании диссертационного совета Д-212.288.03 при Уфимском государственном авиационном техническом университете по адресу: 450000, Республика Башкортостан, г. Уфа, ул. К. Маркса, д. 12

С диссертацией можно ознакомиться в библиотеке университета.

Автореферат разослан «21» ноября 2011 г.

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

В.В.Миронов

Общая характеристика работы

Актуальность темы

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

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

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

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

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

Для достижения поставленной цели были решены следующие задачи:

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

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

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

4. Разработка алгоритма заполнения статических пропусков в графических объектах с помощью самоорганизующихся карт Кохонена.

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

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

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

Основные научные результаты выносимые на защиту

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

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

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

4. Алгоритм заполнения пропущенных пикселов в растровых изображениях с использованием самоорганизующихся карт Кохонена.

5. Прикладное программное обеспечение, реализующее предложенные алгоритмы.

6. Результаты сравнительного анализа эффективности предложенных алгоритмов.

Научная новизна

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

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

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

4. Использованы самоорганизующиеся карты Кохонена для восстановления пропущенных пикселов в графических объектах систем технического зрения.

Практическая и научная значимость результатов

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

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

Апробация работы Основные результаты диссертации докладывались и обсуждались на следующих конференциях: «Решетнёвские чтения» (2009 г., г. Красноярск), «Информационные технологии и автоматизация управления» (2009 г., г. Омск).

Публикации

Материалы диссертации опубликованы в 7 печатных работах, из них 2 статьи в рецензируемых журналах из списка, рекомендованного ВАК.

Структура и объем диссертации

Диссертация состоит из введения, 6 глав, заключения и библиографии. Общий объем диссертации 125 страниц, включая 31 рисунок и 14 таблиц. Библиография включает 101 наименование.

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

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

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

Метрика Минковского (ММ) вычисляется путем нахождения среднего значения разности значений пикселей сначала пространственно, а затем хроматически (т. е. по зонам):

= max ||C(i,j) - С(», j)||, (1) tj

где Ck(i,j) и Ck(i,j) - значения цветосоставляющей пикселей двух изображений, N - количество пикселей.

Среднеквадратическал ошибка (MSE):

ij= 0 \ ' Метрика разницы с соседями (DON)-.

Ck(i,j)~Ck(i,j)

б =

j N-w/2

2 (N - wf v ; >¿=«72

A* + B2

(3)

A.= min (d(C(i,j),C(t,m))l, B= min fd(C(i,j),C(l,m))V

l,mew¡j ^ J l.mewij [ J

где d(», •) - некая функция расстояния. В данной работе рассматривается эвклидово расстояние.

Метрика многомерного расстояния (МОМ), которая основывается на том, что большинство изображений хранятся в больших разрешения (2000 пикселей в каждом измерении и более)

(4)

< = t (¿2^3 £ Гс»5 - + с*5 - +- 1/2)'

г=1 ^ 1,7=1

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

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

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

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

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

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

Для определения пропущенных пикселей вводится матрица повреждений Е, в которой пропущенным пикселам соответствует значение 1, а известным пикселам значение 0. Данная матрица формируется на этапе обучения системы. То есть для первых изображений, получаемых системой технического зрения предобработка сводится к формированию матрицы Е. Алгоритм состоит в побитовом выполнении коньюнкции элементов трех компонентных матриц последовательно получаемых К изображений. Если присутствует статически поврежденные символы, то соответствующий элемент будет ненулевым. Для изменяющихся пикселов логические операции будут приводить к нулевому значению. Эксперимент показывает, что значение К — 100 обеспечивает правильное построение матрицы поврежденных пикселей.

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

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

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

зз зз зз

(=0 j=0 1=0 }=О «=0 .7=0

о „ (5)

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

ции в точках, следующих за ближайшими по шаблону:

/•о • о о • • • о

• • х • • , (6)

о • • • о

О • О

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

Если на изображении пропущен блок пикселей размером W х Я, то для учета, информации о значении функции в точках соседних с поврежденным блоком, необходимо увеличить степень сплайна. Функции компонент цветности будут аппроксимироваться сплайнами:

п п п п п п

рЛХ,, ря{х,г/) = ЕЕу) = ЕЕ•

¿=0 j=0 1=0 j=О t=0 j=0

(7)

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

п = + 2(Я - 1) - 1. (8)

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

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

Пример восстановления пропущенного блока пикселей предстален на рисунке 1.

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

л(к) (к) (к) , ,(к)

ний пикселей а суммой матриц специального вида Аг = а\ у^ + о , где

Рисунок 1 - Поврежденное и востановленное с использованием сплайнов изображения

х(к)^ у(к) ^ ^(к) _ п_мерные векторы, задающие линейное многообразие. Окончательно, приближение исходной матрицы определяется суммой а = ^ Нахождение координат векторов х^к\ ]/к\ происходит итерационно.

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

Ф= £ (ау - х^у? - -V шт. (9)

1 ./«.¡/V.

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

дФ/дх\1] = 0. Данная система решалась методом Горнера. После этого для найденных значений координат вектора а:'1' решалась система уравнений дФ/дх^ = 0 для поиска координат вектора у^К Критерием остановки итерационного процесса является малое изменение значения квадратичной формы Ф.

Найденные значения ж'1' и г/1' определяют матрицу

А«1). После этого

необходимо найти матрицу — а — Ж Далее методом последовательных итераций строится приближение матрицей и так далее. Приближение исходной матрицы, как уже было указано выше определяется суммой найденных матриц а = ^ А^ ■

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

Ф = ^ (ау - - Ь,)2 ->■ тт. (10)

iJ п

ацф-1

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

пропущенных элементов, при заметном росте объема вычилений и затрат машинного времени.

Пример восстановления пропущенного блока пикселей предстален на рисунке 2.

Рисунок 2 - Поврежденное и востановленное с использованием многомерных линейных многообразий изображения

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

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

Саморганизующиеся карты Кохонена требуют векторного представления блоков пикселей. В данной работе было выбрано следующее представление:

хй(х,у) = .Р[г + г©£, ¿ + <т5], 1 = х-[Э/ 2], г = у -[5/2], (11)

где ¿Г С 2 - размер блока, х, у € Ъ - координаты пикселя, для которого строится вектор наблюдения.

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

[5/2] < х < IV, - [5/2], [5/2] < у < Нр - [5/2], (12)

а также 5 должно быть нечетным.

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

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

Введем следующие обозначения: х - вектор наблюдаемых данных. В применении к восстановлению мультемидийной информации это может быть какой-то набор пикселей (сэмплов, набор блоков сжатия изображений), сгруппированных по определенному правилу, т - вектор веса нейрона (по определению, должен быть одной размерности с х). На (4) - мера соседства нейронов (некоторая функция, возвращающая расстояние между нейронами и зави-сищая от номера итерации ¿). Мера соседства нейронов при определенных условиях может определять и топологию поверхности, на которую нанесена карта. ^(х(£),771*(£)) - мера отклонения, показывающая, насколько вектор х{£) не «похож» на вектор т;(£).

Мера соседства нейронов Ла(£) представляет собой функцию от индексов нейронов и номера итерации. В дальнейшем для меры соседства нейронов выбрано следующее представление:

где к - видоизмененную функцию Гаусса, с - индекс первого нейрона, i -индекс второго нейрона, Ь - номер итерации, функция ¿{с, г) имеет вид:

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

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

Функция <5(£) является «функцией радиуса», т. е. она отражает, насколько указанные нейроны являются соседями. С каждой итерацией, происходит

(13)

й{с, г) =

гат

«¡хб{-д„о,(}*} <г„е{-<г„,о,ои}

у/{тс{х} - тщ{х} + (1Х)2 + (тс{у} - т{{у} + йу)2,

(14)

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

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

1. Выбирается случайный вектор x(t) из набора входных значений.

2. Вычисляются расстояния до всех векторов весов всех нейронов карты. Для данной операции был выбрана метрика среднеквадратичного отклонения. Ищем нейрон, наиболее близкий ко входному значению x(t):

¿хМ^.т^^ОФ). mc{t)) < mit)), (15)

где mc{t) - вектор веса нейрона победителя Mc(t), m.i(t) - вектор веса г-го узла в карте, d{x(t),TTii(t)) - метрика среднеквадратической ошибки. Следует заметить, что метрика d вычисляется по известным компонентам всех используемых векторов. В случае, если вышеуказаному условию удовлетворяет несколько нейронов, победитель выбирается случайным образом.

3. Вектора весов изменяются по формуле:

nuit) = nuit - 1) + MtXz(i) - - !)) (16)

Таким образом, все узлы, являющиеся соседями нейрона-победителя, при-блилижаются к рассматриваемому наблюдению.

Критериями остановки выбраны следующие:

1. Алгоритм останавливается, если было произведено обучение по всем известным входным значениям.

2. Алгоритм останавливается в случае, если a(i) < 256, т. е., если очередное изменение веса значения будет меньше, чем шаг квантования цветовой составляющей.

3. Алгоритм останавливается, если <5(i) < 1, т. е., если радиус, на который влияет очередное наблюдение будет меньше, чем минимальное расстояние между нейронами.

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

d(ï(i)lmj(i))= Y1 (гпШ-^t) И)2.

(17)

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

Компьютерный эксперимент показал малые метрические отклонения и низкое быстродействие метода на фоне высокого качества заполнения пропусков «на глаз».

На рисунке 3 представлен пример восстановления поврежденной области изображения.

Рисунок 3 - Поврежденное и востановленное с использованием карт Кохонена изображения

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

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

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

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

Рисунок 4 - График количества распознанных лиц при восстановлении различными методами

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

ЗАКЛЮЧЕНИЕ

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

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

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

Рисунок 5 - График количества распознанного текста при восстановлении различными методами

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

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

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

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

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

ПУБЛИКАЦИИ ПО МАТЕРИАЛАМ ДИССЕРТАЦИИ В рецензируемых журналах из перечня ВАК

1. Карты Кохонена как способ восстановления мультимедийной информации / И. Б. Ларионов // Журнал радиоэлектроники [Электронный ресурс]. 2010. №10. 29 с. (URL: http://jre.cplire.ru/jre/octl0/3/text.html).

2. Алгоритм автоматизированного восстановления поврежденных графических файлов / И. Б. Ларионов // Вестник Омского университета. 2011. №2. С. 176-177.

В других изданиях

3. Использование самоорганизующихся карт Кохонена для восстановления графической информации / И. Б. Ларионов, С. В. Белим // Решетнев-ские чтения: материалы XIII междунар. науч. конф., посвящ. 50-летию Сиб. гос. аэрокосмич. ун-та имени академика М. Ф. Решетнева (10-13 нояб. 2009, г. Красноярск): в 2 ч.; под общ. Ред. Ю. Ю. Логинова / Сиб. гос. аэрокосмич. ун-т. Красноярск, 2009. Ч. 2. С. 437.

4. Кластеризация матриц с пропусками как метод восстановления графической информации / И. Б. Ларионов // Математические структуры и моделирование. Омск: ООО «УниПак», 2009. - Вып. 20. С. 97-106.

5. Многомерные линейные многообразия как способ восста-новления графической информации / И. Б. Ларионов // Математические структуры и моделирование. Омск: «Омское книжное издательство», 2010. Вып. 21. С. 24-31.

6. Восстановление изображений при помощи многомерных линейных многообразий / И. Б. Ларионов // Проблемы обработки и защиты информации. Книга 2. Анализ графической и текстовой информации: коллективная монография / Под общей ред. д-ра физ.-мат. наук С. В. Белима. Омск: ООО «Полиграфический центр КАН», 2010. С. 43-57.

7. Восстановление изображений с использованием самоор-ганизующихся карт Кохонена / И. Б. Ларионов // Проблемы обработки и защиты информации. Книга 2. Анализ графической и текстовой информации: коллективная монография / Под общей ред. д-ра физ.-мат. наук С. В. Белима. Омск: ООО «Полиграфический центр КАН», 2010. С. 58-74.

Диссертант

И. Б, Ларионов

ЛАРИОНОВ Игорь Борисович

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

Специальность 05.13.01 - Системный анализ, управление и обработка информации (в промышленности).

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

Подписано в печать 17.11.2011 Формат 60x84/16. Бумага офсетная. Печать оперативная. Гарнитура Times New Roman. Усл. печ. л. 1.0 Уч.-изд. л. 1,0 Тираж 100 экз. Заказ № 314

Отпечатано в «Полиграфическом центре КАН» 644122, г. Омск, ул. Красный Путь, 30 тел. (3812)24-70-79, 8-904-585-98-84

E-mail: pc_kan@mail.ru Лицензия ПЛД № 58-47 от 21.04.97

ФГБОУ ВПО «Омский Государственный Университет им. Ф .М .Достоевского»

61 12-5/899

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

ЛАРИОНОВ Игорь Борисович

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

05.13.01 - Системный анализ, управление и обработка информации

(в промышленности).

ДИССЕРТАЦИЯ на соискание ученой степени кандидата технических наук

Научный руководитель д. ф.-м. н., проф. Белим Сергей Викторович

Омск - 2011

СОДЕРЖАНИЕ

ВВЕДЕНИЕ..................................................................5

1 Моделирование объектов компьютерной графики с неполными данными в системах технического зрения..........10

1.1 Существующие методы восстановления повреждений......10

1.2 Моделирование объектов компьютерной графики........11

1.3 Метрики сравнения изображений.................12

1.4 Объекты компьютерной графики с неполными данными .... 14

1.5 Интерполяция неполных данных сплайнами...........15

1.6 Интерполяция неполных данных методом главных компонент . 17

1.7 Карты Кохонена...........................18

1.8 Выводы.................................20

2 Статические пропуски в объектах компьютерной графики в системах технического зрения....................22

2.1 Модель представления графической информации с помощью матриц с пропусками........................22

2.2 Выявление статических пропусков.................28

2.3 Выводы................................29

3 Заполнение статических пропусков в объектах компьютерной графики с помощью интерполяций..............31

3.1 Заполнение статических пропусков в объектах компьютерной графики с помощью сплайнов......................31

3.2 Программный комплекс заполнения статических пропусков с помощью сплайнов .........................39

3.3 Выводы ............................... . 44

4 Заполнение статических пропусков в объектах компьютер-

ной графики методом кластеризации матриц с пропусками . 45

4.1 Заполнение статических пропусков в объектах компьютерной графики с помощью многомерных многообразий ........45

4.2 Программный комплекс заполнения неполных данных с помощью метода главных компонент..................51

4.3 Выводы................................56

5 Заполнение статичных пропусков в объектах компьютерной

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

5.1 Модель представления графической информации........57

5.2 Заполнение статичных пропусков в объектах компьютерной графики с использованием карт Кохонена............61

5.3 Программный комплекс заполнения статичных пропусков в объектах компьютерной графики с использованием карт Кохонена 65

5.4 Выводы................................71

6 Компьютерный эксперимент ....................72

6.1 Компьютерный эксперимент и сравнение метода с применением сплайнов и метода многомерных линейных многообразий . . 73

6.2 Результаты компьютерного эксперимента.............74

6.3 Компьютерный эксперимент и сравнение методов заполнения пропусков в объектах компьютерной графики с использованием карт Кохонена и методом интерполяции сплайнами.....96

6.4 Компьютерный эксперимент с применением методов в системах технического зрения......................98

6.5 Компьютерный эксперимент с распознаванием лиц....... 103

6.6 Компьютерный эксперимент с распознаванием текста......106

6.7 Выводы................................108

ЗАКЛЮЧЕНИЕ ..............................Ill

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ........114

ВВЕДЕНИЕ

Актуальность работы

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

Однако кроме случайных помех часто встречаются статические испорченные пикселы, возникающие вследствие недостатков аппаратной части си-

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

В связи с описанными проблемами, актуальной является задача заполнения статических пропущенных пикселов на этапе предварительной обработки изображений. Особенностью статических пропусков является то, что они могут быть однозначно локализованы на основе анализа множества изображений, получаемых с одной камеры. После этого для заполнения пропущенных пикселов могут быть применены алгоритмы обработки данных с пропусками. В последнее время широкое распространение получил ряд подобных алгоритмов: 8-СЬЕА]М, Ричардсона-Люси, метод главных кривых, аппроксимация многообразиями малой размерности, аппроксимация сплайнами, нейро-сетевые методы и т. д. Однако все эти методы имеют ограничения в области применимости и предполагают наличие определенных закономерностей в множестве обрабатываемых данных. В связи с чем актуальной является задача исследования применимости алгоритмов восстановления пропущенных данных для автоматической предварительной обработки графических объектов со статическими пропущенными пикселами в системах технического зрения.

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

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

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

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

Для достижения поставленной цели были решены следующие задачи:

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

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

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

4. Разработка алгоритма заполнения статических пропусков в графических объектах с помощью самоорганизующихся карт Кохонена.

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

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

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

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

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

4. Использованы самоорганизующиеся карты Кохонена для восстановления пропущенных пикселов в графических объектах систем технического зрения.

Практическая и научная значимость работы.

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

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

Основные положения, выносимые на защиту.

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

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

3. Алгоритм заполнения пропущенных пикселов в растровых изображе-

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

4. Алгоритм заполнения пропущенных пикселов в растровых изображениях с использованием самоорганизующихся карт Кохонена.

5. Прикладное программное обеспечение, реализующее предложенные алгоритмы.

6. Результаты сравнительного анализа эффективности предложенных алгоритмов.

Апробация работы.

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

Публикации. Материалы диссертации опубликованы в 7 печатных работах, из них 2 статьи в журналах из списка, рекомендованного ВАК.

Структура и объем диссертации. Диссертация состоит из введения, 6 глав, заключения и библиографии. Общий объем диссертации 124 страницы, включая 31 рисунок и 14 таблиц. Библиография включает 101 наименование.

1 Моделирование объектов компьютерной графики с неполными данными в системах

технического зрения

Проблемы обработки данных с неполными данными рассматривались с применением методов регресий [51, 105], метода главных компонент [72], пошаговой регрессии [65], методом многомерной линейной экстраполяции [17], и другими [22, 49, 52, 56, 62, 71, 78, 80].

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

1.1 Существующие методы восстановления повреждений

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

В работе [12], Сачков и другие предлагают метод восстановления изображений на основе вариационного принципа. Данный метод основан на ана-

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

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

1.2 Моделирование объектов компьютерной графики

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

Существует множество моделей хранения цвета пикселя в памяти [18, 39], однако относительным распространением пользуются следующие [9, 18, 41]:

а) Номер цвета из палитры, соответствующей данному изображению

б) Аддитивная цветовая модель КОВ (красный, зеленый, синий)

в) Линейная трехкомпонентная цветовая модель CIE XYZ

г) Трехкомпонентная яркостно-цветоразностная модель YUV

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

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

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

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

1.3 Метрики сравнения изображений

В ходе работы встал вопрос о сравнении изображений и автоматизации этого процесса.

Метрика Минковского (ММ) [83] Норма разницы между изображениями может быть посчитана следующим образом: вычисляется среднее арифметическое разниц пикселей сначала пространственно, а затем хроматически

(т.е. по зонам):

N-1

Л

К S

k=l ^ i,j= о

Ck(i,j) ~ Ck(i,j)

7 л 1/7

J '

где - значение цветосоставляющей пикселя восстановленного изобра-

жения.

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

В ходе работы использовалось значение 7 = оо: к

1

Ск(ьз) - Ск{г,з)

б°° = in ах

= max||C(i,i)-C(i,j)ll

1,3

Среднеквадратическая ошибка (MSE)[57] является частным случаем метрики Минковского:

N—l / \ 2

£ =

1

iV —X / N

£ (c(ij)-c(ij)

i,j=0 ^

Метрика разницы с соседями (ОСЖ)[99], толерантна к сдвигам пикселей и обычно используется в оценке качества сжатия видеоряда.

£ =

\

N—w/2

_1_ V

2(N-w)2 V ' i,j=w/2

А2 + В2

А= min \d(C{i,j),C{i,m))} B= min \d(C(i,j),C(l,m))\.

где d(», •) - некая функция расстояния. В данной работе рассматривается эвклидово расстояние.

Нетрудно заметить, что данная метрика, при w = 1 сводится к сред-неквадратической ошибке, описанной выше. В работе используется размер блока поиска w равный 5.

Метрика многомерного расстояния (МОМ)[85], которая основывается на том, что большинство изображений хранятся в больших разрешениях (2000 пикселей в каждом измерении и более)

я

( 2Г 22г~3 т=1 ^ 1

2г