Содержание к диссертации
Введение
Глава 1. Методы обработки изображений 18
1.1. Методологии обработки изображений. 19
1.2. Простые методы обработки изображений. 25
Точечные методы. 26
1.3. Локальные методы обработки изображений 36
1.3.1. Линейные фильтры и свертка 36
1.3.2. Гауссовская фильтрация 39
1.3.3. Нелинейная фильтрация. 41
1.4. Другие типы низкоуровневой обработки 43
1.4.1. Кадровые методы 43
1.4.2. Геометрические методы 44
1.4.3. Морфология 45
1.5. Комбинированные методы обработки изображений 46
1.5.1. Краткий обзор комбинированных методов. 47
1.5.2. Алгоритм ДС. 49
1.6. Анализ качества некоторых комбинированных методов. 58
1.6.1. Сравнение ДС с другими комбинированными методами 58
1.6.2. Сравнение качества работы алгоритмов при больших уровнях шумов. 61
1.7. Понятие контуров и методы их получения . 66
1.7.1. Понятие контура. 66
1.7.2. Методы получения контуров. 70
1.8. Обобщенная запись методов обработки. 73
Выводы по 1-ой главе 77
Глава 2 Контуры - кластеры и понятие эталона . 78
2.1 Контуры - кластеры.
2.2 Формализация методов идентификации графических объектов. 83
2.3 Принципы построения обобщенного вектора свойств эталона. 86
2.4 Информационная часть вектора свойств. 88
2.5 Расширенное понятие информационной части. 92
Глава 3. Идентификация формы объектов по контурным функциям 99
3.1 Понятие контурноіі функции. 100
3.2 Распознавание по элементарным признакам . 106
3.2.1.Классификация по числу точек контура. 107
3.2.2. Классификация по габаритам 108
3.2.3. Классификация по компактности 111
3.2.4. Классификация по площади 112
3.2.5. Классификация на основе математической корреляции 114
3.3 Методы геометрической корреляции на всем контуре. 115
3.4 Методы геометрической корреляции на части контура. 118
3.5. Геометрическая корреляции по части контура по противоположным интервалам. 127
3.6. Идентификация по части контура с автоматическим выбором расположения противоположных интервалов. 129
3.7 Особенности использования методов геометрической корреляции 133
Выводы по 3 главе. 139
Глава.4 Анализ качества методов, основанных на геометрической корреляции . 142
4.1 Оценка чувствительности. 143
4.2 Условия проведения эксперимента 147
4.2. Чувствительность методов, основанных на ГК . 152
4.3. Анализ устойчивости методов ГК к шумам. 156
4.3.1. Анализ работы методов в условиях шумов. 156
4.3.2. Измерение метрик в условиях шумов. 159
4.3.3. Анализ числа ошибок при больших шумах. 166
4.4 Особенности исчисления метрик в методах ГК. 170
4.4.1.Исчисление метрик для комбинаций ЭЭ 170
4.4.1.Исчисление метрик для комбинаций ЭН 174
4.5 Особенности применения методов ГК на фрагментах контура. 179
4.5.1.Особенности методов ИЧК1-2. 179
4.4.2.Особенности методов ИЧК-ПИ1 иИЧК-ПИ2. 185
Выводы по главе 4. 192
Глава.5. О методах повышения качества идентификации
графических объектов в методах геометрической корреляции. 193
5.1. Компактность и размеры фигуры. 195
5.2 Компактность и шум. 201
5.2.1. Влияние искажений на методы ГК. 202
5.3. Методы ГК на основе среднеквадратичной метрики. 206
5.3.1. Определение методов. 206
5.3.2. Анализ методов ГК1С и ГК2С. 208
5.4.Методы ГК с динамически назначаемым КД. 211
Выводы по главе 5. 215
Глава 6. Практические применения. 216
6.1 Математическая модель поисковой системы 218
6.1.1. Описание модели 218
6.1.2.Механизм функционирования модели 224
6.1.З.Практическая реализация 226
6.2 Реализация распределённых поисковых систем. 227
6.2.1. Постановка задачи 227
6.2.2. Архитектура распределенной поисковой системы 230
6.3. Система по обработке изображений и распознаванию образов STIPR 233
6.3.1. Краткое описание системы 233
6.3.2. Контроллер потока 235
б.З.З.Состав системы STIPR 239
6.3.4.Работа с эталоном 239
6.4 Организация распределённых вычислений при обработке изображений и распознавании образов. 240
6.4.1. Принципы построения конвейера 241
6.4.2. Архитектура вычислительного комплекса 243
6.4.3. Оценки повышения производительности 244
6.5 Использование результатов работы в учебном процессе. 247
Выводы по главе 6 249
Заключение 250
Литература 253
- Локальные методы обработки изображений
- Понятие контуров и методы их получения
- Распознавание по элементарным признакам
- Чувствительность методов, основанных на ГК
Локальные методы обработки изображений
Другим классом низкоуровневой обработки является локальная. В этом случае результирующее значение каждого пикселя зависит от значений его соседей. Так, например, усредняя локальное значение каждого пикселя изображения по области, образованной 8-ю смежными пикселями получим сглаженное изображение на выходе Фактически такая операция представляет собой свертку, при которой скользящие окна (маски), применяемые для обработки изобра жений, будут матрицами действительных чисел (весовых коэффициентов) размером PxQ [73]. Их действие на локальную область изображения с центром в элементе Ьп,. . состоит в усреднении с весами — коэффициентами маски, значений яркости элементов изображения в скользящем окне. Так в вышеприведенном примере для сглаживания используется маска размером 3x3 с коэффициентами
Свертка обладает двумя важнейшими свойствами: Линейностью. Пусть Н есть оператор свертки переводящий входное изображение Ьп,,, в выходное Imow. Оператор Н будет линейным, если Н(almj+ЪIm2) = аН(imj) + ЪН(lm2). Инвариантностью относительно сдвига, при которой реакция на смещенный стимулятор представляет собой смещение реакции на исходный стимулятор. Это означает, что безразлично, что сдвигать в процессе вычислений — изображение относительно маски или маску относительно изображения. Варьируя коэффициенты в масках можно решать различные задачи по линейной фильтрации. Так, например, используя маски со сле дующими коэффициентами можно осуществлять низкочастотную фильтрацию: ) которая будет заключаться в сглаживании и подавлении шумов на изображении. Примеры результатов такой фильтрации приведены на рис. 1.9. Слева приведено исходное изображение, а справа результаты фильтрации с масками (1.7) Фильтрация по верхним частотам позволяет выделить высокочастотные составляющие, которые представляют собой границы объектов на изображении. Примеры результатов такой фильтрации с использованием масок, основанных на операторах Лапласа, приведены на рис. 1.10. Для улучшения зрительного восприятия, изображения после обработки были инвертированы, а затем на них была увеличена контрастность примерно на 30%. Недостатками таких фильтров является высокая чувствительность к импульсным шумам на изображении, которые после фильтрации существенно возрастают.
Такая популярность обусловлена несколькими причинами. Во-первых, ядро симметрично относительно осей. Во вторых, значения центральных весовых коэффициентов значительно больше, чем на границах. Поэтому для больших среднеквадратических отклонений у соседних пикселей весовые коэффициенты будут больше, а это значит, что среднее значение будет стремиться к согласованию с соседями и за счет размывания большая часть шума исчезнет. В третьих, свертка га-уссиана с гауссианом дает еще один гауссиан [75] Это очень важное свойство означает, что если дискретная свертка оказывается слишком трудоёмкой операцией (при большом ядре), то её можно разбить на две последовательные с ядрами значительно меньшего размера и с существенным выигрышем в производительности, оценка которого дана, например в [76]. Пример маски гауссовского фильтра с ста = 1: В последнее время для получения границ объектов изображения стали совмещать применения масок Лапласа и Гаусса. Такое объединение позволяет выполнять высокочастотную фильтрацию при уменьшении значения шумовой составляющей изображения и при этом не увеличивать размер ядра фильтра. Для получения такого Также существуют фигурные маски, имеющие различную форму. Они применяются для решения специальных вопросов далеких от рамок рассматриваемой темы. Кроме линейной фильтрации для обработки изображений применяется нелинейная, примером которой является медианная фильтрация, представляющая собой замену центрального пикселя на среднее значение всех пикселей, попадающее в окно-маску [77, 78], например, по следующей формуле: Другими словами, медианой является средний по порядку член ряда, получающегося при упорядоченности исходной последовательности. Например, med(25,23,20,10,7,3,7,l,2) = 7. Особенно эффективно такой фильтр позволяет удалять случайные одиночные импульсные помехи (например, типа «соль и перец»). Рис. 1.12. иллюстрирует применение такого фильтра к зашумленному изображению. На нем представлены слева - направо: исходное изображение; - с наложенными импульсными шумами; - после медианной фильтрации с радиусом усреднения - 2; изображение, отфильтрованное первой из масок ФНЧ (1.6). Легко заметить, что искажения изображения минимальны при полном устранении помех по сравнению с линейной низкочастотной фильтрацией.
Понятие контуров и методы их получения
Используя в следующих главах понятие контурной функции, которая вычисляется по точкам периметра объекта, необходимо ввести корректное определение границы объекта в виде его контура. Для дискретных изображений контур образован последовательностью соседних точек. Но как эти точки расположены друг относительно друга, и как определяется собственно граница между объектом и не объектом? Эти вопросы требуют рассмотрения, а используемые понятия корректного определения. Понятие контура используется практически всеми авторами работ по обработке изображений, однако в настоящее время из всей литературы одно из наиболее полных определений было дано в [49]. Цепь рассуждений в этой работе построена следующим образом. Во-первых, введено понятие связности (neighbors), как примыкание соседних точек друг к другу. При 4-х связности, обозначаемой как - N4(p), для точки р с координатами (i,j)t ее соседи имеют координаты (i+l,j), (7-1, у), При 4-х диагональной связности - ND(p) соседние точки будут иметь следующие координаты (/ + 1,7 + 1), (/ + 1,7-1), ,(/-1,7 + 1), (/-1,7-1). Объединение N4(p)[jND(p) = N8(p) называется 8-ми связно стью. Здесь расстояние между соседними точками (пикселями) изображения принимается за I7. Замечание. Существуют специальные обзоры, связанные с понятием связности, например, [102, 103, 104, 105]. Следующее обозначение - смелсностъ (adjacency) между пикселями является ещё одним фундаментальным понятием, которое упрощает описание других основополагающих в [49] - области и границы.
Пусть V есть множество значений яркости, которые могут принимать пиксели на изображении. Тогда для бинарного изображения имеющего два значения пикселей -Ои 1 - F = {1}, а для полутонового изображения с 256 градациями яркости - V = [256}. Для реального изображения предполагается, что смежность определяется на основе связности пикселей при условии эквивалентности их свойств, например их яркости поГ. Поэтому можно выделить три типа смежности8: 4-х смежность: Два пикселя р и q с некоторым значением из V будут 4-х смежными если q є NA{p). 8-й смежность: Два пикселя р и q с некоторым значением из V будут 8-й смежными если q є Ng(p). m- смежность (смешанная - mixed): Два пикселя р и q с некоторым значением из V будут m - смежными, если: a) q N4(p) илиЬ) qGND(p) и N4(p)( }N4(q) = 0 для V пикселей є. Смешанная смежность необходима для устранения неоднозначности представления расстояния, как показано на рис. 1.28. Пунктиром в центре показана неоднозначность определения расстояния между точками и её устранение (см. рис. 1.28 справа) при использовании понятия т-смежности. На основе понятия смежности в [49] определяется понятие пути (или кривой) в дискретном пространстве. Пусть мы имеем две точки пространства х и у с координатами (p,q) и (s,t) соответственно. Пусть имеется множество последовательностей, образованное соседними пикселями с координатами: где (i0,j0) = (p,q), a (w„) = ( ,0 и все пиксели (/мз./м) и (iltj)) являются смежными для 1 \,п. Здесь п - число точек, или длина некоторого пути. Если (iQ,j0) = (i„,jn), то путь называется замкнутым. Возможно определение 4-х, 8-ми или m-смежного пути, в зависимости от типа смежности. Определение 1.3. Пусть S есть некоторое множество точек, определённое на Im. Две точки а и Ъ называются связанными в S если между ними существует путь, все точки которого принадлежат S, а всё это множество пикселей образует связанную компоненту S . Если S представлено только одной компонентой, то оно называется связанным множеством. Будем называть R областью изображения Im если R есть связанное множество. Определение 1.4. Границей или контуром области R будем называть некоторое множество пикселей в этой области которые имеют один или более соседних пикселей не принадлежащих R. Граница может быть образована как 4-х, так и 8-ми связными точками. Для изображения с V = {і} понятия границы и контура некоторой области совпадает.
А для изображения с V = {256} существует проблемы что называть границей, так в этом случае под контуром объекта будет пониматься граница вычисленная на двоичном изображении после выполнения операции сегментации. А граница, вычисленная согласно Определению 1.4, может содержать некоторое количество пикселей имеющих одно свойство (яркость), лежащих не обязательно на внешней стороне области (объекта). Доопределим понятие контура, используемое в настоящей работе по отношению к [49]. Определение 1.5 (контура объекта). Введем понятие контура объекта, через множество граничных пикселей = []m(ik,jk),k-XK\ образующих на некоторой области R замкнутый путь со следующими характеристиками :
Распознавание по элементарным признакам
Рассмотрим сначала некоторые методы распознавания, которые не могут использоваться для однозначной идентификации формы объекта, но позволяют классифицировать объекты по некоторым элементарным свойствам. В работе будут рассмотрены несколько таких свойств - это количество точек периметра объекта, компактность, габариты и площадь. Эти методы в той или иной степени связаны с КФ и могут быть использованы на предварительных этапах идентификации в МПВ. Кроме этих, существуют еще много различных методов идентификации, в основе которых лежат элементарные свойства отдельно или их совокупности. Однако они не рассматриваются в настоящей работе, так как в явном виде не используют понятие контурных функций. Этот элементарный метод идентификации основан на сравнении количества точек в периметрах идентифицируемого объекта и эталона. Определение 3.6. Назовем функцией распознавания по количеству точек (идентификация по контуру). Здесь ns и п0 являются количеством точек контура эталона и тестируемого объекта соответственно, a sN- классификационный допуск, который определяет точность сравнения объектов. Идентификация по контуру не может претендовать на разделение объектов по форме, однако она может быть использована на предварительном этапе в МПВ (см. 2.2), когда необходимо разделить объекты по числу точек их периметра.
Например, отделить большие объекты с количеством точек 100 и более, от малых, образованных помехами (шумами), состоящими из 5-10 точек. С другой стороны этот метод может быть использован в тех случаях, когда необходимо идентифицировать объекты, описание формы которых не может быть получено. Примером таких объектов может быть дефекты прокраски ткани, когда на однородном фоне текстуры ткани располагаются объ екты неправильной формы, подлежащие распознаванию. Описания формы таких дефектов нет, и не может быть, однако априори известно, что дефектом считается объект, имеющий некоторые линейные размеры превышающие некоторый порог. Их значения легко пересчитываются в число точек периметра. Предполагается, что число точек у дефектов значительно больше чем у контуров, получаемых от текстуры исследуемой ткани. Пример распознавания таких дефектов приведен на рисунке 3.5. На рис. 3.5 объекты, полученные от текстуры ткани, содержат от 3 точек до 15-30, в то время как распознаваемый дефект содержит примерно 150-200 точек. Таким образом, определяя допуск для распознавания такого класса объектов равным eN 100 можно отсеять все шумовые объекты и получить только искомые дефекты ткани4. Рассмотрим еще один элементарный метод, который назовём "распознаванием по габаритам". Понятие габаритов хорошо определено для геометрических фигур с четкими прямолинейными границами. Для любого известный объекта легко представить его расположение в пространстве и место, которое он занимает. Так легко определить габариты объекта расположенного на рисунке 3.6 слева. Для этого объекта габариты это высота и ширина прямоугольника, в который он может быть вписан.
А что означают габариты для объекта, изображенного на рис. 3.6 справа? Как представить себе и тем более измерить эти габариты, принимая во внимание, что он может быть повёрнут на некоторый угол относительно эталона? Ответ на эти вопросы дает метод названный LH. Определение 3.7. Пусть г определена на интервале [0,360] с шагом 1, тогда назовем габаритами графического объекта следующую тройку параметров {zpZ /Je/ такую что: Здесь є1,єкиєір- классификационные допуски, определяющие точность распознавания по длине, высоте и углу поворота объекта. Замечание 3.3. Компонента і3 на практике используется очень редко. Фактически формулы (3.6) предназначены для поиска на контурной функции максимального значения и, отступая от него на угол в 90, дают значение второй габариты объекта. Для идентификации может быть использован и третий параметр метода, который показывает угол поворота объекта относительно эталона. Также как и предыдущий, этот метод не дает описание формы объекта (см. Рис. 3.7), однако он позволяет классифицировать объекты по их "вытя-нутости". Поскольку в нем также не используется информацию о форме объекта то, следовательно, его можно использовать для распознавания объектов, вербальное описание формы, которых не нужно или не представляется возможным получить. Замечание 3.4. Вышеприведенную трактовку понятия габаритов можно расширить путем введения дополнительных параметров г., таких, что где / будут играть роль «дополнительных» габаритов. Такие параметры могут в некоторых случаях повысить качество распознавания (увеличить вероятность правильного распознавания и уменьшить вероятность пропуска объ ектов распознавания). При стремлении количества параметров L к количеству отсчетов функции гнор фактически происходит переход к методам геометрической корреляции, которая требует значительно больших затратах в вычислительном отношении.
Чувствительность методов, основанных на ГК
Рассмотрим чувствительность методов геометрической корреляции на основе методов ГК1 и ГК2, а затем распространим эти результаты на другие методы. Сначала по методу ГК1 для каждого из трех файлов (с 5-, 6- и 7-звёздными объектами) вычислялись значения метрики р = min 5(r) по трем г различным эталонам, один из которых всегда совпадал с типом фигур на изображении (ЭЭ), а два других - не совпадали (ЭН). В методе ГК2 вычисления проводились аналогично, но значения метрики определялось по формуле р = тїпсг(т). v Результаты экспериментов сведены в таблицы 4.1 и 4.24. В них приводятся значения среднего и среднего отклонения измерений р между объек Для ответа на первый вопрос была использована функция jbtest из пакета MatLab, которая проверяет гипотезу о принадлежности распределения к нормальному закону. В этой функции для проверки используется критерий Jarque-Berra [145], основанный на оценке величин асимметрии и эксцесса для исследуемой функции плотности распределения. Результат проверки гипотезы дал положительный результат, то есть все выборки (18 штук) имеют распределение нормального вида
Результаты экспериментов отражены на рисунках 4.5 и 4.6 в виде суммарных гистограмм распределения значений pGCl и pGC2 и их функций плотности вероятности для методов ГК1 и На основании полученных данных по функциям распределения pGCX и pGC2 для методов ГК1 и ГК2 был сделан вывод о постоянстве величин параметров их функций плотности распределения (а и т ), которые не зависят от формы (типа распознаваемых объектов), поворота и масштаба. Кроме того, визуальный анализ представленных на рис. 4.6 результатов показывает, что суммарные ФПР для сочетаний идентифицируемых объектов типа ЭЭ и ЭН при использовании рассматриваемых методов не пересекаются, то есть эти методы обладают высокой чувствительностью (при tx =t2 =3 - fm =3.272 для метода ГК1) по отношению к разным идентифицируемым классам. Значения коэффициента чувствительности метода /т, вычисленные по (4.3) приведены в таблице. Они показывают, что даже если использовать для оценки чувствительности вероятности ложного опознавания и пропуска объектов с рх =р2 = 0.000001 (см 4.1), то при этих значениях fm =1.963 (для ГК1) и fm =2.363 (для ГК2), что превышает предельное значение (fm =1.0). То есть чувствительность методов остается высокой. Кроме того /т показывает, что при прочих равных условиях метод ГК2 имеет более высокую чувствительность чем ГК1. Аналитическое определение величины КД назначаемой для каждого метода может быть основано на вычислении точки пересечения хвостовых частей функций плотности вероятности.
Для этого используется формулы нормального распределения В связи с большим расстоянием между средними значениями в ФПР и небольшими средними отклонениями, функция (4.4) будет практически равна нулю на интервале [3,13] для метода ГК1 (см. рис. 4.6а) и на интервале [5,15] для методов ГК2 (см. рис. 4.6Ь). Поэтому значение допуска можно выбирать любое из этих интервалов, однако поскольку в ФПР для комбинаций ЭН при добавлении дополнительных объектов может возрасти среднее отклонение, то назначение КД желательно осуществлять на основании верхнего доверительного интервала для ФПР типа ЭЭ. Результаты статистического анализа показывают, что ФПР для метрик типа ЭЭ и ЭН в методах ГК1 и ГК2 сильно разнесены и имеют высокий коэффициент чувствительности - /т 1. Такие же убедительные результаты дают численные оценки на основе доверительных интервалов. Пусть нам необходимо идентифицировать объект, совпадающий с классом эталона, тогда можно считать, что y(jp) = x( p) и, следовательно (3.16) будет иметь вид Выражение (4.5) напоминает формулу автокорреляции [147], но в отличие от нее использует разность, а не произведение функций. Как же будет вести себя функция Sxx (г) на отрезке [0,360]? Очевидно, что она имеет один или более минимумов, один из который всегда будет при т = 0. Дополнительные минимумы будут существовать, если функция л имеет одну или более осей симметрии. Кроме того, в (4.5) при г = 0 функция SXX(T)\=0=0. Однако при исследовании значений метрик р, вычисленных на реальных объектах, этого не наблюдалось. Функция 5"XV(T) всегда имела некоторое значение. Этот факт объясняется тем, что в реальных контурах всегда присутствуют некоторые искажения, обусловленные шумами или импульсными помехами. Предположим, что на объект накладываются искажения в виде нормального аддитивного шума у{ф) = х( р)+п((р).
