Фан_Ногк_Хоанг_Диссертация. Алгоритмы обработки и анализа символов вейвлетпреобразованием, методом главных компонент и нейронными сетями
 Скачать 3.2 Mb.
|
|
Глава 1. Аналитический обзор подходов к распознаванию символов В данной главе проведен анализ систем распознавания текстов и подходов к распознаванию символов. Приведен аналитический обзор основных методов и алгоритмов для выделения признаков изображения. Описывается принцип работы двумерного вейвлет-преобразования и определяются его преимущества при решении задач обработки изображений и распознавания образов. Проведен анализ основных методов и алгоритмов, основанных на вейвлет-преобразовании, предназначенных для решения задач обработки изображений и распознавания образов. 1.1 Основные задачи обработки изображений Методы цифровой обработки изображений можно разделить на две категории. Первая категория относится к методам, в которых на входе и на выходе имеются изображения. Во второй категории входом методов являются изображения, выходом – признаки и атрибуты этих изображений [10]. Основные стадии цифровой обработки изображений приведены в табл. 1.1. Таблица 1.1. Основные стадии цифровой обработки изображений 1. Регистрация изображения является предельно простой задачей, в случае, когда исходное изображение уже представлено в цифровой форме. Такая задача применяется во всех областях и в общем случае она включает Первая категория Вторая категория Стадии - Регистрация изображения - Улучшение изображения - Восстановление изображения - Кратномасштабная обработка - Сжатие изображения - Сегментация изображения - Представление и описание - Распознавание образов 13 некоторые этапы предобработки, такие как масштабирование. 2. Методами улучшения изображения являются методы выявления плохо различимых деталей или просто подчеркивания интересующих характеристик на исходном изображении. Улучшение изображения может применяться на этапе предобработки изображения. Оно часто используется при обработке медицинских изображений и т.п. Методы улучшения изображений основаны на предпочтениях человеческого восприятия, которые оценивают, насколько хорош результат улучшения. 3. Задача восстановления изображения связана с повышением визуального качества изображения. Методы такой задачи основаны на математических или вероятностных моделях искажений изображения. К восстановлению изображения также относятся методы подавления шума. Известными методами подавления шума являются фильтры, такие как медианный фильтр, адаптивный медианный фильтр, винеровская фильтрация и др. 4. Кратномасштабная обработка позволяет представлять изображение с несколькими степенями разрешения. В области обработки изображений кратномасштабная обработка широко применяется для решения таких задач, как подавление шума изображений, сжатие изображений и т.п. 5. Задача сжатия изображения относится к методам, в результате которых уменьшается объем памяти, необходимого для хранения или для передачи изображения. Сжатие изображения подразделяют на две категории: сжатие с потерями и сжатие без потерь качества. 6. Цель задачи сегментации изображения заключается в разделении изображения на составные части или объекты, для того чтобы его было проще и легче анализировать. Сегментация изображения обычно используется для решения таких задач, как выделение объектов и выделение границ на изображениях. Примерами известных методов сегментации изображения являются такие методы, как метод водораздела (Watershed), текстурная сегментация, алгоритм К-средних и др. 14 7. Представление и описание часто следуют за этапом сегментации с целью преобразования данных в форму, которая удобна для компьютерной обработки. 8. Стадия распознавания образов относится к методам, которые классифицируют объекты по категориям или классам. Такая стадия является одной из самых изученных задач в таких областях как цифровая обработка изображений, компьютерное зрение, биометрия, создание интеллектуальных систем безопасности и контроля доступа и т.п. Тем не менее, в области распознавания образов продолжают представлять большой научный и практический интерес такие задачи как распознавание лиц, жестов, отпечатков пальцев, печатных и рукописных символов и текстов. 1.2 Подходы и системы распознавания символов и текстов Задача распознавания символов является одной из актуальных задач распознавания образов в настоящее время. Эту задачу можно использовать для решения других задач, таких как распознавание текста, распознавание автомобильных номеров и т.п., являющихся востребованными в различных сферах деятельности современного общества. 1.2.1 Системы распознавания текста В настоящее время существует ряд программных средств и систем, использующих алгоритмы распознавания символов для решения задачи распознавания текстов. Распространение получили такие программные средства как ABBY FineReader, Tesseract OCR, CuneiForm, OmniPage, Readiris и др. В каждом из перечисленных программных продуктов предложены свои алгоритмы и методы для распознавания текстов. Однако большинство указанных программных средств являются коммерческими, поэтому алгоритмы и методы, применяемые в них для решения задач, известны только разработчикам. 15 Хотя перечисленные программы показывают высокую точность распознавания символов и текстов, но они не могут обеспечивать точность распознавания 100% для всех вариантов символов и текстов, а также в присутствии шума на изображениях. Таким образом, можно сделать вывод, что разработка новых алгоритмов для распознавания символов и текстов является актуальной задачей. a. ABBY FineReader FineReader 11 в настоящее время является одной из наиболее распространенных программ распознавания текста, реализованной компанией ABBYY, основанной в 1989 г. Программа позволяет преобразовывать изображения документов и PDF-файлов в виде электронных редактируемых форматов. Она обеспечивает возможность сохранения результатов распознавания в различных форматах, таких как DOC, DOCX, DjVu, TXT и др. Кроме того, FineReader 11 обеспечивает высокую точность распознавания текста и также сохраняет структуру документа при распознавании. Программа может распознавать тексты на 188 языках, основанных на кириллице, латинице, греческом, армянском алфавитах и на иероглифических символах. В том числе для 44 языков используется словарь и проверка орфографии при распознавании [2]. b. Tesseract OCR Tesseract OCR представляет собой систему распознавания текста, обеспечивающую открытый доступ к своим исходным кодам. В 1995 г. она является одной из трех лучших программ по точности распознавания текста в конкурсе «The Fourth Annual Test of OCR Accuracy» [97]. Однако c 1995 г. по 2006 г. развитие системы замедлилось. В августе 2006 г. компания Google купила эту систему и обеспечила открытый доступ к исходным кодам под лицензией Apache 2.0 для дальнейшей разработки. 16 В настоящее время Tesseract OCR является одной из наиболее точных систем распознавания текста. Она позволяет на основе версии 3.0 преобразовывать большое количество форматов изображений в тексты на более чем 60 языках, в том числе на английском, русском, украинском и других. Однако система поддерживает сохранение результата распознавания только в формате текста, для сохранения в других форматах пользователям необходимо реализовать дополнительную программу [23]. c. CuneiForm CuneiForm является программой, предназначенной для распознавания текста документов и преобразования его в редактируемый вид. Программа позволяет редактировать результаты распознавания в офисных средствах и текстовых редакторах. При распознавании она также обеспечивает возможность сохранения структуры и форматирования документа [1]. Многие результаты научных исследований и технологические ноу-хау, основанные на CuneiForm, успешно применяются в коммерческих продуктах компанииCognitive Technologies, таких как Cognitive Forms, Cognitive Forms Bank, Cognitive Passport и Cognitive ScanPack. Следует отметить, что компанией Cognitive Technologies принято решение сделать CuneiForm бесплатной программой и обеспечить доступ к ее исходным кодам. CuneiForm позволяет распознавать текст документов на более чем 20 языках, в том числе на английском, русском, немецком и других. В программе используется словарная проверка для повышения точности распознавания. При этом программа позволяет расширить использованный словарь с помощью импорта новых слов из текстовых файлов. 1.2.2 Подходы к распознаванию символов В данном разделе проводится анализ подходов, предназначенных для решения задачи распознавания символов. В настоящее время подходы для решения этой задачи можно разделить на три основных подхода: шаблонный, структурный и признаковый [3, 9, 17]. 17 a. Шаблонный подход Алгоритмы шаблонного подхода обычно требуют предварительную обработку для обеспечения приемлемой точности распознавания символов. Основной предварительной обработкой данного подхода является представление изображения символов в виде растрового изображения, нормализация размера, наклона и толщины штриха символов. Принцип работы алгоритмов шаблонного подхода основан на прямом сравнении изображения распознаваемого символа со всеми шаблонами, хранящимися в базе шаблонов. Наиболее подходящим является шаблон, который имеет наименьшее количество несовпадающих пикселей, отличающих этот шаблон от изображения распознаваемого символа. При этом большинство систем, использующих алгоритмы данного подхода, имеет шаблоны, созданные для различных начертаний. После того как осуществлено распознавание нескольких слов, система определяет основный используемый шрифт и изображения символов будут сравниваться с шаблонами только этого шрифта. В некоторых случаях система использует численные значения частей символа для определения нового шрифта. Это может улучшить эффективность распознавания символов. К преимуществам шаблонного подхода относятся простота реализации, высокая скорость распознавания и хорошая устойчивость к дефектам изображений символов. Недостаток данного подхода заключается в том, что при данном подходе невозможно распознавать шрифты, которые немного отличаются от шрифтов в базе шаблонов по размеру и начертанию. При этом требуется необходимость настройки системы на типы и размеры шрифтов. Алгоритмы шаблонного подхода должны заранее знать шрифты, которые эти алгоритмы будут распознавать. Однако все шрифты и их модификации невозможно охватить при обучении алгоритмов. При этом алгоритмы шаблонного подхода не являются универсальным. 18 b. Структурный подход Алгоритмы данного подхода распознают символы на основе представления изображений символов в виде топологии, содержащей информацию о взаимном расположении отдельных составных частей символов. Каждый из этих алгоритмов ищет особые характеристики символов, такие как острова, полуострова, точки, прямые оттиски и дуги. Такие особые характеристики могут быть представлены в виде формы графа. Алгоритмы данного подхода также требуют предварительную обработку, которой является процесс скелетизации, предназначенный для утоньшения символов. Преимущество данного подхода заключается в том, что данный подход обеспечивает инвариантность относительно типов и размеров шрифтов символов. Таким образом, точность распознавания символов алгоритмами данного подхода не зависит от шрифтов символов. К недостаткам структурного подхода относятся низкая скорость распознавания и трудность распознавания дефектных символов. Дефектный символ может стать специфической проблемой для данного подхода, так как отсутствующий пиксель может разбивать длинный штрих или кривую, а дополнительное пятно грязи может закрывать петлю. c. Признаковый подход Алгоритмы признакового подхода работают на основе представления изображений символов в виде вектора признаков. Процесс распознавания символов заключается в сравнении вектора признаков изображений символов с набором векторов изображений символов обучающей выборки той же размерности. В алгоритмах данного подхода чаще всего используется классификатор, основанный на определении расстояния Евклида между вектором признаков изображения распознаваемого символа и векторами признаков изображений символов обучающей выборки. Процесс формирования вектора, представляющего изображение символа, называется процессом выделения признаков. Признаки каждого изображения 19 распознаваемого символа получают путем аналоговой обработки изображений символов обучающей выборки. Основными преимуществами признакового подхода являются простота реализации, хорошая обобщающая способность, хорошая устойчивость к изменениям формы, размеры и шрифта символов, низкое число отказов от распознавания и высокая скорость распознавания. Недостаток данного подхода заключается в неустойчивости к различным дефектам изображений и потере части информации о символе на этапе выделения признаков. Выделение признаков ведется независимо, поэтому информация о взаимном расположении элементов символа утрачивается. Благодаря своим преимуществам признаковый подход выбран для дальнейшей разработки алгоритмов, предназначенных для распознавания символов разных шрифтов с высоким быстродействием. 1.2.3 Выделение признаков Выделение признаков традиционно является предметом исследования в области распознавания образов. Оно представляет собой один из шагов, необходимых для решения задачи распознавания. В работах [33, 38] перечислены следующие основные методы выделения признаков. a. Моменты изображений Во многих приложениях моменты изображений используются в качестве признаков образов, предназначенных для решения задачи их распознавания. Эти признаки содержат глобальные свойства изображения, такие как область формы, центр массы и т.п. Геометрические моменты являются распространенными типами моментов. Геометрический момент цифрового изображения можно вычислить по следующей форме: 20 , ( , ), p p p q m x y f x y (1.1) где p и q – целые числа (0, ∞), представляющие уровень момента; x и y – координаты пикселя изображения; f(x, y) – интенсивность изображения в этом пикселе. На основе этих моментов Hu М.К. предложил способ выделения признаков изображения, являющихся инвариантными при преобразовании изображения [56]. Моменты Zernike являются проекциями интенсивности изображения f(x, y) на ортогональный полином Zernike, определяющий полное ортогональное множество сложных полиномов по координатам (x, y), расположенным в круге x 2 + y 2 = 1 [62]. , , , ( , ) ( , ) ( ) , jq p q p q p q V x y V R e (1.2) где p и q – целые числа, представляющие уровень момента, 1, j p≥0, p≥|q|, p–|q| – четное число, ρ – наименьшее расстояние пикселя (x, y) до центра круга, θ – угол между вектором ρ и осью X, R p,q (ρ) – ортогональный радиальный полином, вычисляющийся по формуле: ( )/2 2 , | | | | 0 2 2 ( 1) ( )! ( ) !( )!( )! p q s p s p q p q p q s p s R s s s (1.3) Момент Zernike цифрового изображения вычисляется следующим образом: * 2 2 , , 1 ( , ) ( , ), 1. p q p q x y p Z f x y V x y (1.4) Чтобы вычислить моменты Zernike используются координаты центра изображения в качестве координат центра круга. Пиксели, расположенные вне круга, не учтены при вычислении моментов. Изображение f(x, y) можно представить с использованием моментов Zernike в следующем виде: 21 , , 0 ( , ) ( ) , N N jq Z p q p q p q N f x y Z R e (1.5) где p–|q| – четное число; N – максимальный уровень моментов Zernike. На рис. 1.1 приведены исходное изображение буквы «B» и его представление на основе применения моментов Zernike с максимальным уровнем момента N:0, 2, 4, 6, 8, 10, 12, 14, 16 и 18 («zm0»–«zm18» соответственно). Рисунок 1.1. Преставление изображения буквы «B» на основе применения моментов Zernike [60] Моменты Legendre цифрового изображения с размером N×N пикселей можно вычислить по следующей формуле: 1 1 , 0 0 ( ) ( ) ( , ), N N p q p N q N x y L P x P y f x y (1.6) где p и q – целые числа (0, ∞), представляющие уровень момента; 2 1 , 1 N x N x N 2 1 ( ) ( 1) и [ 1,1], 2 ! p p p p p d P x x x p dx 2 1 ( ) ( 1) и [ 1,1]. 2 ! q q q q q d P y y y q dy 22 В результате представления изображения f(x, y) с использованием моментов Legendre получается новое изображение, значение пикселя (x, y) которого вычисляется по следующей формуле: , 0 0 ( , ) ( ) ( ), p M L p q p q p q f x y L P x P y (1.7) где M – максимальный уровень моментов Legendre. Пример представления изображения символа с использованием моментов Legendre приведен на рис. 1.2. Слева-направо на рис. 1.2 приведены исходные полутоновое (в верхней строке) и бинарное (в нижней строке) изображения символов и их представление на основе применения моментов Legendre с максимальным уровнем момента M: 20, 40 и 60. Рисунок 1.2. Представление изображения символа на основе применения моментов Legendre [105] b. Гистограмма изображения Гистограммы представляют распределение пикселей полутонового изображения по их интенсивности f(x, y). Амплитуда гистограммы полутонового изображения является таблицей H(k), показывающей количество пикселей, имеющих значение интенсивности k. Амплитуда гистограммы полутонового изображения размером N×N пикселей вычисляется следующим образом: max ( ) { ( , ) | ( , ) }, [0, ],( , ) [(0,0),( 1, 1)]. H k count f x y f x y k k k x y N N (1.8) 23 c. Направленные признаки Символы включают штрихи (stroke), ориентация которых играет важную роль в дифференциации между различными символами. При распознавании символов векторы из статистики ориентаций штрихов используются в качестве векторов признаков символов. Для выделения признаков символа угол ориентации штриха разбивается на фиксированное число диапазонов и количество сегментов штрихов в каждом диапазоне используется в качестве значения признака. Множество количеств сегментов штрихов, которое формулирует гистограмму, называется гистограммой ориентации [48]. Чтобы увеличить возможность дифференциации гистограмма обычно вычисляется для локальных диапазонов изображения символов и называется гистограммой локальной ориентации. Локальные ориентации штрихов символов можно определить по-разному: ориентация скелетона, сегмент штриха, цепной код (chaincode) контура, направление градиента и т.п. [65, 72, 99, 111]. На рис. 1.3 приведен пример представления изображения символа с использованием направленных признаков. На рис. 1.3(а) представлено исходное изображение символа, а на рис. 1.3(б–г) приведены его представления на основе применения контура, направления градиента и гистограммы локальной ориентации. Рисунок 1.3. Представление изображения символа на основе применения направленных признаков [38] 24 d. Преобразование Хафа Распространенным методом выделения признаков в области обработки изображений является преобразование Хафа. Оно позволяет обнаружить прямые линии, кривые или любую конкретную форму, которые можно определить с использованием параметрических уравнений. Преобразование Хафа отображает точки из пространства изображения в пространстве параметров и после этого выделяет признаки изображения. Преобразования Хафа можно разделить на два типа: стандартное и случайное (randomized) преобразование Хафа. В стандартном преобразовании Хафа все точки {(x 1 , y 1 },…,(x n , y n )} пространства изображения преобразуются в пространство параметров [46]. Например, линия в пространстве изображения, y = mx + b, определяется в пространстве параметров по следующей формуле: cos sin , x y (1.9) где ρ – расстояние от центра пространства до линии; θ – угол между ρ и осью X (рис. 1.4). Таким образом, прямая линия в пространстве изображения отражается как уникальная точка в пространстве параметров. Рисунок 1.4. Представление прямой линии в пространстве параметров Случайным преобразованием Хафа является расширение стандартного преобразования, предназначенное для выделения признаков бинарных изображений. Оно учитывает недостатки стандартного преобразования Хафа, а именно, длительное время вычислений и большие требования к памяти. 25 e. Представление на основе линии Штрихи на изображениях символов обычно толще, чем один пиксель, поэтому признаки символов, основанные на линии, можно выделить с использованием контура штриха или скелета. Край (контур) определяется как граница между двумя областями изображения, имеющими различные значения серого уровня [10]. Значения серого уровня пикселей изображения, расположенных на крае, сильно изменяются. Это изменение проводит к неоднородности серого уровня. Таким образом, край на изображениях можно выделить на основе использования этого свойства. В большинстве методов выделения края используются первая и вторая производные. Сильное изменение в величине первой производной показывает присутствие края на изображениях. Точно так же вторая производная используется, чтобы определить находится ли пиксель края на темной или светлой стороне. Если значение второй производной положительно, то пиксель края принадлежит к темной стороне. В обратном случае пиксель края принадлежит к светлой стороне. Утоньшением является преобразование изображения, после которого все линии на изображении имеют толщину в один пиксель. Такая линия обычно называется скелетоном. Большинство алгоритмов утоньшения повторяет удаление последовательных слоев пикселей, расположенных на крае символа, пока не оставляют только один скелетон [115]. Алгоритмы утоньшения можно разделить на две категории: последовательные и параллельные. В последовательном алгоритме необходимо предопределить последовательность пикселей, в которой пиксели будут проверены на удаление. При этом работа n-ой итерации зависит от результатов всех предыдущих итераций (1, 2,…, n–1). В параллельном алгоритме работа n-ой 26 итерации зависит от результата только предыдущей итерации (n–1). Примеры результатов утоньшения изображений букв «M» и «K» представлены на рис. 1.5. Слева-направо на рис. 1.5 представлены исходные изображения символов и результаты их утоньшения. Рисунок 1.5. Результаты утоньшения изображений символов [85] f. Дескрипторы Фурье В настоящее время дескрипторы Фурье являются одним из распространенных и эффективных методов, предназначенных для выделения формы на изображениях. В принципе эти дескрипторы представляют форму объекта в частотном домене. Преимущество дескрипторов Фурье заключается в том, что они обеспечивают возможность дифференциации между различными символами, низкую шумовую чувствительность и сохранение информации о символе [115]. Дескрипторы Фурье можно разделить на два типа: стандартные и эллиптические. Они используются для описания формы (закрытая кривая) любого объекта, найденного на входном изображении. Для вычисления дескрипторов Фурье вначале необходимо выделить контуры символа на изображении, затем полученные данные преобразуются в виде одномерного представления. 27 g. Линейное преобразование Методы преобразования пространства признаков обычно используются в области распознавания образов. Они изменяют представление признаков образов с целью улучшения точности классификации. Метод главных компонент (МГК) является статистическим методом, основная цель которого заключается в уменьшении множества признаков путем определения подмножества преобразованных признаков, которое содержит ту же необходимую информацию, что и оригинальное множество признаков. МГК является линейным, поэтому каждый новый преобразованный признак представляет собой линейную комбинацию оригинального множества признаков. МГК также включает в себя концепцию регрессии, целью которой является нахождение простого способа для объяснения отношения между зависимой переменной Y и независимой переменной X. Простым линейным отношением является то, которое минимизирует сумму квадратов ошибок регрессии. Примеры собственных символов, полученных на основе применения МГК, представлены на рис. 1.6. Рисунок 1.6. Собственные символы при использовании МГК [42] Линейный дискриминантный анализ (LDA) является распространенным методом, применяющимся для нахождения линейного подпространства признаков, которое максимизирует критерий Фишера [49]. LDA представляет собой параметрический метод выделения признаков, который вычисляет Гауссову плотность распределения вероятности с равной ковариацией для всех классов. Выделенное подпространство работает 28 довольно хорошо даже в ситуациях, в которых классы описываются негауссовскими распределениями или ковариационные матрицы не равны. Полученные с использованием методом LDA признаки могут быть в дальнейшем распознаны линейными или нелинейными классификаторами. h. Вейвлет-преобразование Вейвлет-преобразование впервые предложено математиком Alfred Haar в 1910 г. и было названо вейвлетом Хаара. Однако в то время концепции вейвлета еще не существовало. В 1982 г. концепция вейвлета была предложена геофизиком Jean Morlet [84] и вейвлет-преобразования сразу были признаны в качестве нового метода для анализа сейсмических сигналов. В это же время обратное преобразование вейвлета было исследовано физиком Alex Grossmann. В 1984 г. Morlet и Grossmann совместно провели подробное математическое исследование такого типа вейвлета, называемого интегральным (непрерывным) вейвлет- преобразованием [52]. В 1985 г. Yves Meyer разработал новое преобразование вейвлета, названное вейвлетом Meyer. В 1988 г. Meyer и Stephane Mallat совместно предложили концепцию кратномасштабного разложения (multiresolution) [77]. В этом же году Ingrid Daubechies разработала метод, предназначенный для конструкции полного ортогонального вейвлет- преобразования [44]. В 1989 г. Mallat предложил так называемое быстрое вейвлет-преобразование, являющееся надежным методом, предназначенным для выполнения вычислений дискретного вейвлет-преобразования [79]. В это время, благодаря приемлемой скорости вычислений, быстрое вейвлет- преобразование широко использовалось для решения задач области обработки сигналов. Все эти типы вейвлет-преобразований являются одномерными вейвлет- преобразованиями и они часто используются для решения задач обработки непрерывных сигналов, например, для подавления шумов на музыкальных записях [40, 78]. Однако сигнал можно разделить на два типа: непрерывный и 29 дискретный. Примером дискретного сигнала является изображение, описываемое функцией f(x, y), где x и y – координаты этого пикселя в пространстве, а значение f указывает интенсивность изображения в этом пикселе. Для анализа и обработки дискретного сигнала целесообразно использовать двумерное вейвлет-преобразование, которое позволяет упростить работу с дискретными сигналами по сравнению с одномерным вейвлет-преобразованием. Рисунок 1.7. Схема работы двумерного вейвлет-преобразования Схема работы первого разложения 2D сигнала, основанного на использовании двумерного вейвлет-преобразования, представлена на рис. 1.7. Вначале сигнал преобразуют по столбцам с использованием низкочастотного фильтра G и высокочастотного фильтра H. Затем два полученных субдиапазона аналогично преобразуют по строкам. В результате получаются четыре субдианазона входного сигнала. На рис. 1.8 представлен пример первого разложения изображения двумерным вейвлет- преобразованием Хаара. 30 Рисунок 1.8. Пример разложения изображения двумерным вейвлет- преобразованием Хаара: а) – исходное изображение; б) – преобразование по столбцам; в) – преобразование по строкам изображения (б) Использование двумерного вейвлет-преобразования для обработки изображений обладает следующими преимуществами. Вейвлет-преобразование разделяет изображение на субдиапазоны, представляющиеся как в пространственных, так и в частотных доменах. При разложении изображения на субдиапазоны, вейвлет- преобразование позволяет анализировать это изображение в различных разрешениях. Вейвлет-преобразование дает возможность анализа изображений по разным направлениям, таким как горизонтальное (вдоль столбцов), вертикальное (вдоль строк) и диагональное направление. Использование вейвлет-преобразований позволяет определить маленькие детали на изображениях. Маленькие вейвлеты можно использовать для выделения маленьких деталей, а большие вейвлеты – для выделения больших деталей изображений. Вейвлеты могут вычисляться с высокой скоростью при разложении изображений. Таким образом, вейвлет-преобразование является перспективным методом для выделения признаков символов. Далее проводится обзор и 31 анализ методов и алгоритмов обработки изображений и распознавания образов, основанных на вейвлет-преобразованиях. 1.3 Методы обработки изображений и распознавания образов с использованием вейвлет-преобразования В области обработки изображений вейвлет-преобразование является одним из распространенных и эффективных методов, предназначенных для решения задач этой области. В работах [30, 34, 47, 54, 57, 76, 87–88, 92–94] показано эффективное использование вейвлет-преобразования для подавления шума на изображениях, а в работах [25, 32, 45, 50, 61, 71, 73, 100– 101] представлены способности вейвлетов при сжатии изображений. В [26– 27, 35–37, 63, 86, 104, 116] представлено применение вейвлетов для решения задачи сегментации изображений. Однако количество работ, посвященных применению вейвлет-преобразований для распознавания образов, еще невелико. Далее проводится подробный аналитический обзор методов и алгоритмов распознавания образов на основе применения вейвлет- преобразований. 1.3.1 Построение дескриптора фигуры В области распознавания образов фигуры являются самыми главными признаками образов. Дескрипторы, которые представляют эти фигуры, играют особенную роль при решении задачи распознавания образов. Эти дескрипторы можно получить с помощью применения вейвлет- преобразования к контурам образов. В работе [41] разработан дескриптор для дуги, полученный с использованием вейвлет-преобразования. Этот дескриптор позволяет разложить дуги на компоненты в различных масштабах, в которых содержится глобальная и локальная информация об этих дугах. Показано, что полученный дескриптор имеет важные свойства, такие как единственность, 32 инвариантность, устойчивость, кратномасштабное представление и локальность. В работе [110] предложен новый дескриптор для представления фигур образов на основе применении вейвлет-преобразования к контурам образов. Этот дескриптор был протестирован на базе из 6000 рукописных символов и в результате численных экспериментов показано, что дескрипторы, полученные на основе применения вейвлет-преобразования, являются эффективными представлениями для решения задачи распознавания образов. 1.3.2 Классификация изображений Цель задачи классификации изображений заключается в том, чтобы определить существует ли на изображениях объект заданного класса, такого как «тигр», «лев», «волк» и т.п., либо установить относятся ли изображения к заданному классу, такому как изображения «на горах», «на море», «в небе» и т.п. В работе [82] признаки изображений получаются на основе применения вейвлет-преобразования Добеши и моментов цветов. Полученные признаки в дальнейшем подаются на вход многослойной нейронной сети для классификации изображений самолетов. В работе [35] разработан алгоритм, в котором используется пакет вейвлет-преобразования для извлечения признаков изображений текстур. В результате тестирования на различных базах изображений текстур показано, что вейвлеты успешно применяются для решения задачи классификации изображений текстур. В работе [43] используется комбинация вейвлет-преобразования и нейронной сети для классификации изображений сцены войны. Проведено сопоставление результатов работы вейвлет-преобразований Хаара и Добеши и показано, что вейвлет Хаара эффективнее. В работе [89] комбинация вейвлет-преобразования и нейронной сети также используется для классификации изображений объектов, таких как 33 яблоко, танк, мотоцикл и т.п. В работе [51] предложен алгоритм, использующий комбинацию вейвлет-преобразования Добеши и многослойной нейронной сети для классификации изображений самолетов. В работе [109] используется вейвлет-преобразование для разложения изображений. Проекции коэффициентов вейвлета низкочастотного субдиапазона на оси X и Y вычисляются для составления вектора признаков, использующихся для классификации изображений. Показано, что алгоритм способен работать для нахождения изображений в больших базах данных. Примеры изображений, использующихся для тестирования алгоритма классификации изображений в этой работе, представлены на рис. 1.9. Рисунок 1.9. Примеры изображений для экспериментов работы [109] Результаты численных экспериментов для алгоритмов вышеперечисленных работ приведены в табл. 1.2. Показано, что использование вейвлет-преобразования для выделения признаков изображения обеспечивает возможность эффективно классификации изображений. Точность классификации изображений при этом составляет 76–99,7%. 34 Таблица 1.2. Результаты классификации изображений различных алгоритмов Работа База изображений Точность число классов обучающая выборка тестовая выборка обучающая выборка ( % ) тестовая выборка ( % ) [82] 6 150 200 98 90 [109] 7 1470 1470 96 90 [35] 30 – – – 99,6 8 – – – 97 [43] 2 200 200 – 82,5 [89] 30 300 300 81,7 76,7 [51] 6 120 120 – 88 В работе [108] предложен алгоритм, предназначенный для быстрого нахождения нужных изображений из больших баз данных. В этом алгоритме используется вейвлет-преобразование Добеши для разложения каждой из трех цветовых компонент изображений. Вейвлет-коэффициенты низкочастотного субдиапазона являются вектором признаков изображений. В результате экспериментов показано, что алгоритм позволяет найти 100 наилучших подобных изображений из базы 10000 изображений за 3,3 секунды. В работе [39] приведен анализ эффективности вейвлет-преобразования для извлечения признаков изображений текстур, использующихся для решения задачи их классификации. Проведены эксперименты с различными классификаторами, такими как Naive Bayse, Feed Forward Neural Network (FFNN), K-Neareast Neighbor (kNN), Cascaded Forward Neural Network (CFNN). В результате численных экспериментов показано, что вейвлет- преобразование эффективно используется для классификации изображений текстур. Точность наилучшего результата составляет 91,3%. 35 В работе [90] используется вейвлет-преобразование Хаара для извлечения признаков изображений, на основе которых составляются векторы из 10 главных признаков. Затем к этим векторам применяется алгоритм К-means для классификации изображений текстур. При тестировании алгоритм используется для нахождения изображений в базе данных по информации о заданном изображении. Показано, что алгоритм позволяет найти нужные изображения из базы данных. На рис. 1.10 представлен пример работы алгоритма. Рисунок 1.10. Пример работы алгоритма [90]: а) – исходное изображение запроса; б–д) – результат нахождения в базе данных 1.3.3 Распознавание лиц Задача распознавания лиц на изображениях является одной из самых актуальных задач области распознавания образов. Она играет важную роль в нашей жизни и имеет широкое применение, например, может использоваться в системах паспортного контроля аэропортов и вокзалов, в иммиграционных службах, в системах видеоконтроля, расположенные в метрополитене, местах проведения зрелищных, спортивных мероприятий, вокзалах, автовокзалах, аэропортах и т.д. 36 В работе [68] предложен алгоритм распознавания лиц, основанный на применении комбинации преобразования Фурье и вейвлет-преобразования. В этом алгоритме к исходным изображениям лиц применяется вейвлет- преобразование для их разложения. Затем к низкочастотным изображениям применяется преобразование Фурье для получения представления изображений лиц. В работе [59] предложено использование двумерного вейвлет- преобразования Добеши для выделения признаков лиц. Полученные признаки в дальнейшем используются в процессе распознавании лиц. В работе [114] разработан алгоритм распознавания лиц, состоящий из двух шагов. Вначале разлагаются изображения лиц на основе применения двумерного вейвлет-преобразования, в результате которого изображения лиц представляются в виде коэффициентов разложения. Затем используется метод классификации лиц, основанный на модели Kernel Associative Memory (KAM), полученной на основе реконструкции изображений лиц. В этом алгоритме каждый человек имеет свою модель. Процесс распознавания лица выполняется на основе определении ошибки реконструкции изображения лица в каждой модели. В работе [53] предложен алгоритм распознавания лиц, в котором вейвлет-преобразование Хаара используется для извлечения признаков лиц, а метод SVM – для их классификации. В работе [107] используется двумерное вейвлет-преобразование Хаара для извлечения признаков лиц. Полученные векторы признаков применяются для классификации лиц на основе вычисления расстояния Евклида между этими векторами. Метод Locality Preserving Projection (LPP) используется для представления локальной структуры изображений. Метод Locally Discriminating Projection (LDP) является расширенным вариантом метода LPP, который эффективно используется для извлечения признаков изображений лиц. Использование таких методов позволяет получить только 37 линейные признаки. В работе [106] предложен метод извлечения нелинейных признаков изображений, называемый Wavelet based Kernel Locally Discriminating Projection (WKLDP), который является расширенным вариантом метода LDP. Эти признаки используются далее для классификации изображений лиц. В работе [81] разработан алгоритм распознавания лиц, в котором используется комбинация вейвлет-преобразования и МГК для извлечения признаков лиц. Полученные признаки подаются на вход многослойной нейронной сети. По результатам сопоставления с другими методами извлечения признаков лиц, применяемыми в отдельности (вейвлет- преобразованием, МГК, LDA), показано, что наилучший результат распознавания лиц получается при использовании комбинации вейвлет- преобразования и МГК. Алгоритмы вышеперечисленных работ протестированы на различных базах лиц и частях этих баз лиц, таких как Yale database [24], ORL database [22], FERET Databases (Release2) [91], XM2VTS Database [74]. На рис. 1.11 и 1.12 представлены примеры изображений из баз данных Yale и ORL. Рисунок 1.11. Примеры изображений в базе лиц Yale 38 Рисунок 1.12. Примеры изображений в базе лиц ORL Результаты численных экспериментов из вышеперечисленных работ приведены в табл. 1.3. В результате показано, что точность распознавания лиц составляет 90–98,5% и доказано что вейвлет-преобразование надежно и эффективно используется для извлечения признаков, предназначенных для распознавания лиц. Таблица 1.3. Точность распознавания лиц различными алгоритмами Работа База изображений лиц Точность ( % ) название объекты обучающая выборка тестовая выборка [59] FERET 10 150 50 90 [114] FERET 119 357 570 84,7 476 451 91,6 XM2VTS 295 855 295 82,2 ORL 40 120 280 89,4 [53] ORL 40 40 360 66,9 80 320 86,2 120 280 93,9 160 240 95,4 200 200 97,5 240 160 98,1 39 Работа База изображений лиц Точность ( % ) название объекты обучающая выборка тестовая выборка [107] ORL 40 – – 89,4 [106] ORL 40 240 160 98,5 [81] Yale 15 164 1 90,3 Показано, что вейвлет-преобразования эффективно применяются в различных алгоритмах для решения задач обработки изображений, таких как восстановление изображений, сжатие изображений, сегментация изображений, классификация изображений и распознавание образов. Доказано, что использование вейвлет-преобразований пригодно для извлечения признаков образов и дает возможность надежного и эффективного решения задач области распознавания образов. Большой научный и практический интерес в настоящее время представляют задачи распознавания лиц, жестов, печатных и рукописных символов, текстов и т.д. Распознавание символов может использоваться в системах OCR, в системах чтения номеров автомобилей и т.п. Программные средства и системы, использующие распознавание символов, продолжают развиваться в направлении повышения точности и скорости распознавания. Таким образом, применение вейвлет-преобразования является перспективным способом для решения задачи разработки новых алгоритмов, предназначенных для распознавания символов и текстов. 1.4 Цель и задачи исследования Целью диссертационной работы является разработка алгоритмов на основе вейвлет-преобразования, метода главных компонент и нейронных сетей, способных распознавать символы разных шрифтов и фрагменты текстов. Для достижения поставленной цели необходимо решить следующие основные задачи. 40 1. Разработать алгоритм распознавания символов на основе вейвлет-преобразования, метода главных компонент и нейронных сетей. 2. Разработать способ построения классификатора для распознавания символов на основе нейронных сетей. 3. Создать алгоритм распознавания фрагментов печатных текстов на основе разработанного алгоритма распознавания символов. 4. Осуществить апробацию созданных в диссертационной работе алгоритмов на задачах распознавания символов и фрагментов печатных текстов на изображениях. 41 1.5 Основные результаты и выводы по главе 1 В данной главе проведен анализ задач цифровой обработки изображений и их областей применения. Сделан аналитический обзор систем распознавания текста и подходов к распознаванию символов. Показаны преимущества и недостатки каждого подхода. Благодаря своим преимуществам признаковый подход выбран для дальнейшей разработки алгоритмов, предназначенных для распознавания символов разных шрифтов с высоким быстродействием. Проведен анализ методов для выделения признаков изображения. На основе проведенного анализа вейвлет- преобразование было выбрано для выделения признаков изображения. Кроме того, в данной главе сделан аналитический обзор методов и алгоритмов для решения задач цифровой обработки изображений и распознавания образов, основанных на вейвлет-преобразовании. Показано, что при использовании вейвлет-преобразования для выделения признаков изображений, точность алгоритмов классификации изображений составляет 76–99,7%, а точность алгоритмов распознавания лиц 90–98,5%. Было принято решение об актуальности исследования возможности применения вейвлет-преобразования при разработке алгоритмов, предназначенных для распознавания символов и фрагментов печатных текстов. |