Содержание к диссертации
Введение
Глава 1. Анализ методов коррекции и идентификации 9
1.1 Отделение сюжетной части изображения от фона 9
1.2 Приведение изображений к единым условиям съёма 24
1.3 Классификация изображений 33
1.4 Выводы 38
Глава 2. Отделение сюжета 40
2.1 Предварительная обработка изображений 40
2.2 Пороговая обработка 47
2.3 Градиентные методы выделения контуров полутонового изображения 53
2.4 Выделение контуров изображения с помощью вейвлет-преобразования 60
2.5 Выделение сюжетной части изображения в задачах идентификации личности 65
2.6 Выводы 71
Глава 3. Методика приведения изображения к одинаковым условиям съема 72
3.1 Построение формы изображения 73
3.2 Алгоритм приведения изображений к одинаковым условиям съема 76
3.3 Выводы 79
Глава 4. Идентификация изображений по численным характеристикам 80
4.1 Численное описание изображений 80
4.2 Классификация изображений по численным характеристикам 93
4.3 Классификация изображений по набору оценок 103
4.5 Выводы 114
Заключение 115
Список используемой литературы 118
Приложение 125
- Приведение изображений к единым условиям съёма
- Градиентные методы выделения контуров полутонового изображения
- Алгоритм приведения изображений к одинаковым условиям съема
- Классификация изображений по численным характеристикам
Введение к работе
Актуальность работы. Многие направления науки и техники, имеющие отношение к получению, обработке, хранению и передаче информации, в значительной степени ориентируются в настоящее время на развитие систем, в которых информация имеет характер изображений. При этом возникает ряд сложных научных и технических проблем.
В настоящее время активно ведутся работы по анализу изображений [1 - 7].
Одной из самых сложных на сегодняшний момент задач является распознавание изображений на основе формализованных численных характеристик конкретного изображения. Следует отметить, что исследования по распознаванию образов и анализу изображений включены в перечень приоритетных направлений развития науки и техники и критических технологий федерального уровня.
Распознавание изображений находит широкое применение в различных областях науки и техники [8]. В технике это может быть контроль топологии
• печатных плат, текстуры ткани, робототехника (интеллектуальные системы). В информатике - контроль доступа к информации по идентификации личности (биометрическая идентификация). Спецприменение - доступ к объектам ограниченного доступа и учреждения в целом, оперативный поиск в картотеке изображений, дактилоскопия и др. Применение для классификации исторических источников на бумаге, а также в физике, химии, биологии и др. областях науки. Возрастающий объем задач и повышение требований к точности и скорости их » решения вызывают интенсивное развитие именно цифровых алгоритмов как методов автоматической обработки изображений.
Проблема распознавания изображений рассматривалась еще на ранних стадиях развития компьютерного зрения. Для решения задачи распознавания предлагаются различные методики, среди которых можно выделить подходы, основанные на нейронных сетях, на разложении Кархунена - Лоэва [9], на алгебраических моментах [10], линиях одинаковой интенсивности, эластичных f (деформируемых) эталонах сравнения. Все эти методики основаны на двух раз личных подходах к распознаванию: геометрическом и эталонном. Геометрическое сравнение, ориентировано на определение элементов изображения (ЭИ). Показано [И], что если даже ЭИ извлекаются вручную, то компьютерное распознавание дает хорошие результаты.
Эталонное сравнение построено на том предположении, что изображение, представленное в виде массива байтов - величин интенсивности, сравнивается в подходящей метрике с эталоном - целым изображением. Такой подход, в частности, рассматривается в теории восприятия Гештальта, согласно которой образ сразу, без всякого предварительного опыта воспринимается человеком как целое, без какого-либо синтеза из отдельных частей, благодаря способности воспринимать «форму», «целостность» и «организацию» [12]. Особенности восприятия слабоконтрастных изображений зрительным трактом человека заключаются также в том, что в процессе узнавания мозг выступает как активная распознающая система (с проверкой правильности решений). Этапами распознавания при этом могут быть: выделение признаков, предварительный анализ, выдвижение гипотезы, проверка гипотезы - сличение изображений с эталоном, взятым из памяти. Поэтому принцип активного распознавания, должен закладываться на этапе проектирования систем кибернетического видения слабоконтрастных объектов.
Распознавание образов актуально в задачах идентификации личности. 20 лет назад проблема распознавания лиц считалась одной из сложнейших задач искусственного интеллекта и компьютерного зрения. Однако целая череда успешных реализаций прошлого десятилетия показала, что этот метод идентификации личности не только технически осуществим, но и экономически выгоден.
В современных системах (таких как, Facelt компании Visionics, TrueFace компании Miros) для фронтальных изображений, сделанных в один и тот же день, приемлемая точность распознавания, как правило, составляет 95%. Однако, для изображений, сделанных разными аппаратами и при разном освещении, точность, как правило, падает до 80%. Для изображений, сделанных с разницей в год, точность распознавания составляет примерно 50%.
Исходя из вышеописанного, была сформулирована основная цель диссер % тации: разработка методов, алгоритмов и программ идентификации полутоно вых изображений полученных в различных условиях съема, и как частный случай - идентификация лица человека. Для реализации поставленной цели необходимо решать последовательность задач:
- Коррекция и фильтрация изображений;
- Отделения сюжетной части изображения от фона;
- Приведение изображения к единым условиям съёма;
- Выбор и обоснование формализованных характеристик адекватно описывающих изображение;
- Создание эффективного алгоритма идентификации полутоновых изображений.
Методы исследования вытекают из его цели. В качестве основных методов исследования выбран метод математического моделирования и вычислительный эксперимент, проводимый по замкнутой схеме, опирающийся на: математический аппарат статистического анализа; методы морфологического ана лиза формы изображения; численные методы, методы функционального и объектно-ориентированного программирования.
Основные защищаемые положения:
1. Последовательность решения задачи идентификации, применительно к целям практического использования, включающая в себя отделение сюжетной части изображения от фона, выделение формы изображения и распознавание по формализованным характеристикам. Предложенная последовательность обработки изображения обеспечивает максимальную вероятность распознавания;
2. Методика реставрации изображений, позволяющая компенсировать разницу в условиях их съема, с сохранением формы каждого из анализируемых изображения;
Разработанный набор формализованных характеристик описания формы изображения обеспечивает адекватное описание изображения, при его иден тификации.
Достоверность результатов диссертационной работы подтверждаются экспериментальными данными, полученными при использовании программно — технической системы созданной при непосредственном участии соискателя, имеющими как научную, так и практическую ценность. Достоверность результатов выводов и положений диссертационной работы обеспечиваются:
- тщательной разработкой методик и алгоритмов идентификации минимизирующих погрешности;
- качественным и количественным сопоставлением полученных результатов с я имеющимися современными теоретическими и экспериментальными данными;
- практическим использованием системы в производственных условиях ООО «Радио и сигнальные системы», Томского управления исполнения наказаний.
Научная новизна работы заключается в следующем:
Проведен анализ методов обработки изображений, предложена и обоснована последовательность задач обработки изображений, обеспечивающая вероятность идентификации на уровне 95%.
Сформулированы формализованные численные характеристики описания формы изображения, обеспечивающие надежное распознавание изображения по ним.
Оценено влияние отдельных интегральных характеристик на точность идентификации.
Предложена схема компенсации различий в условиях съема изображений, позволяющая сохранять индивидуальные формы сравниваемых изображений.
Практическая значимость.
Изложенный в диссертации подход к задаче идентификации полутоновых изображений и разработанные алгоритмы послужили основой для создания программно-технической системы «ЛИК».
На основании результатов диссертационной работы модернизируется комплекс программно-аппаратных средств распределенных информационно- поисковых систем различного назначения и сложности (система «Портрет» « ООО «PortLand»).
Результаты исследований непосредственно используются в учебном процессе при изучении спецкурса «Обработка изображений» на кафедре АСУ ТУ СУР.
Публикация и апробация работы. Основные научные результаты опубликованы в 19 работах (в том числе в 3-х статьях в сборнике научных статей, в тезисах 11-ти докладов, препринт ИОА, в 2-х зарубежных статьях).
Материалы работы обсуждались на научно-методических семинарах кафедры оптико-электронных систем и дистанционного зондирования радиофизического факультета ТГУ, и кафедры автоматизированных систем управления факультета систем управления ТУСУР, и докладывались на научных конференциях:
1. Научно практической конференции «Музей 2000» (2000,Томск).
2. XXXIX Международной научной конференции «Студент и научно - технический прогресс». (2001, Новосибирск).
3. Региональной научно - технической конференции студентов и молодых специалистов «Радиотехнические устройства, информационные технологии и системы управления» (2000,Томск).
4. XL Международной научной конференции «Студент и научно - технический прогресс» (2002, Новосибирск).
5. XLI Международной научной конференции «Студент и научно - технический прогресс» (2003, Новосибирск).
Программно-техническая система идентификации полутоновых изображений демонстрировалась на выставках:
1. 8-ой международной азиатской выставке оборонных технологий DSA -2002, г. Куала-Лумпур (Малайзия).
2. Выставка - ярмарка «Средства и системы безопасности 2002», Томск.
3. Выставка — ярмарка «Средства и системы безопасности 2003», Томск.
4. XII специальных систем и средств охраны и безопасности «Сиббезопас-ность 2003», Новосибирск.
Личный вклад. В диссертации использованы только те результаты, в которых автору принадлежит определяющая роль. Опубликованные работы написаны в соавторстве с сотрудниками научной группы. В совместных работах диссертант принимал участие в непосредственной разработке алгоритмов, теоретических расчетах и вычислительных экспериментов, в интерпретации результатов. Постановка задачи исследований осуществлялась научным руководителем, к.т.н., с.н.с. Калайдой В.Т.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы из 78 наименований и приложения. Общий объем работы составляет 127 страниц, в том числе 44 рисунка.
Приведение изображений к единым условиям съёма
Задача контрастирования связана с улучшением согласования динамического диапазона изображения [15]. Если для цифрового представления каждого отсчета изображения отводится 1 байт (8 бит) запоминающего устройства, то входной или выходной сигналы могут принимать одно из 256 значений. Обычно в качестве рабочего используется диапазон 0...255; при этом значение 0 соответствует при визуализации уровню черного, а значение 255 - уровню белого. Предположим, что минимальная и максимальная яркости исходного изображения равны л:тіп и тах соответственно. Если эти параметры или один из них существенно отличаются от граничных значений яркостного диапазона, то визуализированная картина выглядит как ненасыщенная, неудобная, утомляющаяпри наблюдении. Пример такого неудачного представления приведен на рис. 1.5,а, где диапазон яркостей имеет границы min =180, max =180. При линейном контрастировании используется линейное поэлементное преобразование вида: параметры которого а и b определяются желаемыми значениями минимальной
Уты и максимальной утлх выходной яркости. Решив систему уравнений: относительно параметров преобразования а и Ь, нетрудно привести (1.19) к виду:
Результат линейного контрастирования исходного изображения, представ ленного на рис. 1.5,о, приведен на рис. 1.5,6 при ymia = 0 и ушк = 255.
Сравнение двух изображений свидетельствует о значительно лучшем визуальном качестве обработанного изображения.
Диапазон яркостей выходного изображения, подвергнутого цифровой обработке, может отличаться от диапазона яркостей исходного изображения. Более того, в диапазоне числовых значений яркости обработанного изображения, могут оказаться отрицательные значения, которые не могут иметь прямого соответствия с физическими яркостями. Существует два способа приведения диапазона выходного изображения в соответствии с входным. Согласно первому, обработанное изображение линейно отображается таким образом, чтобы полностью охватить отведенный ему диапазон яркостей. Второй способ предусматривает ограничение экстремальных значений яркости обработанного изображения максимальным и минимальным пороговыми уровнями (способ коррекции несинусоидальными ортогональными преобразованиями). Этот способ часто обеспечивает более высокое качество изображения, особенно если обработанное изображение содержит относительно мало элементов с превышением уровней ограничения. В программах и системах повышения контраста нередко предусматривается возможность введения ограничения для фиксированного процента значений яркости на обоих краях шкалы яркостей.
Гистограмма распределения яркостей типичного изображения естественного происхождения, подвергнутого линейному квантованию, обычно имеет ярко выраженный перекос в сторону малых уровней, т.е. яркость большинства элементов ниже средней. На темных участках подобных изображений детали часто оказываются неразличимыми. Одним из методов улучшения таких изображений является видоизменение гистограмм. Этот метод предусматривает преобразование яркостей исходного изображения, с тем, чтобы гистограмма распределения яркостей обработанного изображения приняла желаемую форму. Рис. 1.6 иллюстрирует процедуру выравнивания гистограммы в том случае, когда число уровней на выходе составляет половину числа уровней на входе, яркостей, когда обработанное и исходное изображения имеют неодинаковое число уровней квантования HKj)
Градиентные методы выделения контуров полутонового изображения
Проведенные исследования возможности применения классических методов для задач выделения контура изображения показали, что последовательность применения их в различных условиях может решить проблему выделения контура, однако для различных классов изображения эта последовательность индивидуальна, и не подается формализации.
Резкие изменения (разрывы) яркости, координат цвета или параметров, характеризующих текстуру, являются важными простейшими признаками, поскольку они часто определяют очертания объектов. Локальные разрывы значений яркости называются яркостными перепадами, или яркостными контурами (luminance edge).
На рис. 2.10 показаны участки изображения с быстрым изменением яркости от низкого уровня к высокому в одномерном и двумерном случаях.
Одномерный и двумерный перепады В одномерном случае перепад характеризуется высотой, углом наклона и координатой центра склона. Перепад существует, если его угол наклона и высота больше некоторого заданного порога. Для двумерного случая важна также ориентация перепада по отношению к оси х. Идеальный детектор перепада при обработке областей изображения, представленных на рис. 2.10, должен указывать на наличие перепада в единственной точке, расположенной в центре склона.
Общий подход к обнаружению перепадов на монохромном изображении иллюстрируется в виде блок-схемы на рис. 2.11.
Исходное изображение, представленное массивом чисел F(j,k), подвергается линейной или нелинейной обработке с тем, чтобы усилить перепады яркости. В результате образуется массив чисел G(j,k), описывающий изображение с подчёркнутыми изменениями яркостей. Затем выполняется операция сравнения с порогом и определяется положение элементов изображения с ярко выраженными перепадами. Если имеет место нисходящий перепад, а при восходящий перепад. Величины TL(j,k) и Tv(j,k) представляют собой нижнее и верхнее пороговые значения. Эти значения можно сделать переменными в плоскости изображения для компенсации влияния сильных изменений яркости на результаты обнаружения перепадов. Выбор порога является одним из ключевых вопросов выделения перепадов. При слишком высоком уровне порога не будут обнаружены структурные элементы с низким контрастом. Наоборот, слишком низкий уровень порога явится причиной того, что шум будет ложно принят за перепад. Для обозначения положения перепадов на изображении часто формируют контурный препарат- массив элементов E(j,k). Например, положение точек восходящих препаратов можно было бы отмечать белыми точками на черном фоне. Можно также точки восходящих препаратов белым цветом, нисходящих - черными, а остальные элементы изображения - некоторым средним уровнем яркости.
Другой важный подход к обнаружению перепада состоит в аппроксимации фрагмента реального изображения некоторым идеальным одно- или двумерным перепадом, показанным на рис. 2.10. Если аппроксимация оказывается достаточно точной, то считается, что перепад существует и ему приписываются параметры идеального перепада.
До выполнения операции порогового обнаружения можно «подчеркнуть» перепады с помощью различных способов контрастирования. Один из наиболее простых способов заключается в вычислении дискретных разностей, что аналогично непрерывному пространственному дифференцированию.
Линейные методы контрастирования удобно применять для выделения перепадов по одному заданному направлению, что не всегда удобно при автоматической обработке. В нелинейных системах для контрастирования перед пороговым ограничением используются нелинейные комбинации значений яркости элементов изображения.
Алгоритм приведения изображений к одинаковым условиям съема
На основании вышеизложенных предположении предлагается следующий алгоритм морфологического приведения изображений. Первоначально изображение преобразовывается в полутоновое с «-битной градацией яркости в диапазоне (0,и). Выделение заданного фрагмента изображения (сюжетной части) и приведение его к «универсальному» размеру (масштабирование). Для выбранного класса изображений по интенсивностям одного из изображений («эталон») вычисляются индикаторные функции путем попиксельного анализа всего изображения. В результате такой операции формируется индикаторные функции формы изображения для соответствующих интенсивностей. Затем по индикаторным функциям изображения компенсируется разность яркостных характеристик, без нарушения формы анализируемого изображения («претендента»). Для этого, для каждой индикаторной функции анализируемого изображений вычисляется корректирующий коэффициент, так как сравнение может производиться лишь тогда, когда условия получения были максимально идентичны. Такой результат можно достичь, применением метода наименьших квадратов (МНК). Для этого интенсивность анализируемого изображений приводится к интенсивности «эталона» так, чтобы сумма квадратов отклонения была минимальна: V\Ст -KQC j -» min - линейное преобразование интенсивности «претендента», Y(Cra -КХС - К2С 2) -» min - квадратичное преобразование интенсивности «претендента»; п - количество точек индикаторной функции; Ст- интенсивность in -ой индикаторной функции «эталона»; С - интенсивность «претендента»; Кг - корректирующие коэффициенты г =0,1,2. Таким образом, для линейного преобразования интенсивностей имеем: Отличительной особенностью данного алгоритма от преобразований интенсивностей, предложенных в работах
Пытьева Ю.П. [17 - 19] является отсутствие в преобразовании формы постоянного члена. Это позволяет преобразовывать интенсивности анализируемого изображения по индикаторной функции без искажения его формы. Пример работы данного алгоритма представлен нарис. 3.1, рис. 3.2. В случае идентичных изображений разница между ними будет равна нулю. При сравнении различных изображений разница может быть не нулевая. Для оценки остаточного изображения необходимо ввести численные характеристики, которые позволят адекватно описать изображение и, следовательно, классифицировать его. Проведенные исследования на различных типах изображений показали, что линейное преобразование интенсивности дает лучший результат приведения для задачи идентификации личности, так как не искажается форма претендента (рис. 3.2). В то время как для задач коррекции и реставрации более эффективно использовать квадратичное преобразование интенсивности, компенсирующее изменение условий съемки (рис. 3.3).
Классификация изображений по численным характеристикам
Как уже отмечалось, одного параметра не всегда достаточно для проведения качественной классификации, поэтому необходимо обратиться к анализу, учитывающему несколько параметров (например, набор интегральных характеристик).
В основу многофакторного анализа положен метод таксономии (группировка объектов по похожести их свойств) [40]. Одним из вариантов применения является алгоритм FOREL [74]. Алгоритмы семейства FOREL используют критерий, основанный на гипотезе компактности: в один таксон должны собираться объекты, «похожие» по своим свойствам на некоторый центральный объект. Мера похожести определяется через Евклидово расстояние в простран стве характеристик. Все объекты описываются определенным набором параметров или признаков, и могут быть представлены как точка в n-мерном пространстве признаков - X - {хх, х2, х3,..., хр ). Расстояние от точки (объекта) А до точки Б (RAB) в пространстве параметров размерностью р, определяется по следующей формуле: где Хи - і - ый параметр точки А; ХіБ -і- ый параметр точки Б. Если координаты центра j - того таксона обозначить символом С;., то сумма расстояний между центром и всеми ij точками Xу этого таксона будет равна: Нужно найти такое разбиение т объектов на k таксонов, чтобы величина F была минимальной. Опишем базовую версию и некоторые модификации алгоритма FOREL, предназначенных для поиска такого разбиения. Базовое описание алгоритма FOREL 1. Таксоны, получаемые этим алгоритмом, имеют сферическую форму. Вначале признаки объектов нормируются так, чтобы их значения находились в диапазоне от 0 до 1. Затем строится гиперсфера минимального радиуса R0, которая охватывает все т точек.
Для этого: находится средняя точка - среднее значение признаков для исходной совокупности по всем т точкам: где X}i - значение j - ого признака і - ой точки; р - количество признаков; Sr. значение j- ого признака средней точки. из всей совокупности точек по формуле (4.1) определяется точка т1, рас стояние R до которой от «средней точки» будет минимальным. Т.е. эта точ ка должна удовлетворять следующему условию: Точка w, - будет являться центром тяжести исходной совокупности точек. Затем, аналогично, по формуле (4.1), но уже от точки /я, ищется точка т2, расстояние до которой Rm будет максимальным. Полученное значение Rm будет представлять собой минимальный радиус начальной гиперсферы с центром в точке /и,: Если бы нам был нужен один таксон, то он был бы представлен именно этой начальной сферой. Для получения большего числа таксонов радиус сфер постепенно уменьшается. Берется радиус /?, = 0,9 RQ и центр сферы помещается в любую из имеющихся точек. Находим точки, расстояние до которых меньше радиуса, и вычисляем координаты центра тяжести этих «внутренних» точек. Переносим центр сферы в этот центр тяжести и снова находим внутренние точки. Сфера как бы плывет в сторону локального сгущения точек. Такая процедура определения внутренних точек и переноса центра сферы продолжается до тех пор, пока сфера не остановится, т.е. пока на очередном шаге мы не обнаружим, что состав внутренних точек, а следовательно, и их центр тяжести, не меняются. Это значит, что сфера остановилась в области локального максимума плотности точек в признаковом пространстве.
Похожие диссертации на Алгоритмы и программные средства идентификации полутоновых изображений
