Описание способов комбинирования классификаторов в задаче распознавания символов. Различные методы реализации этапов комбинирования, их сочетания. Эксперимент, заключающийся в распознавании множества изображений отдельных заглавных букв английского языка.
Аннотация к работе
Ядром распознавания символов является классификатор или система классификаторов, которая по пришедшему на распознавание изображению определяет, какому символу оно соответствует наилучшим образом. Первые системы распознавания символов использовали простейшие классификаторы, которые даже при незначительных искажениях в изображении уже не могли дать правильного ответа. Один вариант - это пара, состоящая из графемы (класс символа) и оценки уверенности, что распознаваемое изображения является данной графемой. Комбинирующий уровень объединяет список вариантов от различных классификаторов в единый список, расставляя вариантам объединенные оценки, которые учитывают оценки каждого из первичных классификаторов. Этап завершающего комбинирования объединяет оценки, полученные после комбинирующего этапа и после распознавания сильным классификатором.По результатам экспериментов были сделаны следующие выводы: Наилучшие способы нормализации для распознавания отдельными классификаторами - простое приведение и отношение «своих» и «чужих». Использование комбинирующей таблицы на завершающем уровне дает незначительный прирост верного результата на 1-м месте, но не всегда - для верного результата на 1-м или 2-м месте.
Введение
Задача оптического распознавания символов состоит в приведении изображения с текстом в машинно-редактируемый формат. Это позволяет значительно увеличить скорость и качество обработки больших объемов документов, по сравнению с ручным вводом.
Основные методы, использующиеся при распознавании символов, основаны на теории распознавания образов. Ядром распознавания символов является классификатор или система классификаторов, которая по пришедшему на распознавание изображению определяет, какому символу оно соответствует наилучшим образом.
Первые системы распознавания символов использовали простейшие классификаторы, которые даже при незначительных искажениях в изображении уже не могли дать правильного ответа. В дальнейшем стали использоваться более сложные классификаторы разной природы. Лучших же результатов получилось добиться только путем совместного использования нескольких классификаторов.
Таким образом, основной вклад в качество распознавания символов вносят как сами используемые классификаторы, так и способы их комбинирования. В данной работе исследуются некоторые методы комбинирования.
1. Схема распознавания одного символа
Рис. 1. Схема распознавания символов
Эта схема соответствует алгоритму распознавания рукописных символов, используемому в ABBYY FLEXICAPTURE [Терещенко и др., 1997], [Ян, 2003].
Рассмотрим схему детальнее и поясним обозначения: C1 … Cn - первичные классификаторы, задача которых состоит в порождении списка вариантов.
Один вариант - это пара, состоящая из графемы (класс символа) и оценки уверенности, что распознаваемое изображения является данной графемой.
N1 … Nn - этапы нормализации оценок от соответствующих классификаторов. Нормализация необходима, так как в результате распознавания первичными классификаторами полученные оценки имеют различные диапазоны у разных классификаторов и имеют различный смысл. Перед комбинированием необходимо как минимум привести их к единому диапазону.
Комбинирующий уровень объединяет список вариантов от различных классификаторов в единый список, расставляя вариантам объединенные оценки, которые учитывают оценки каждого из первичных классификаторов.
На дифференциальном уровне происходит попарное сравнение вариантов в списке между собой, в результате которого оценки могут быть переоценены.
Сильный классификатор отличается от первичных классификаторов тем, что помимо самого изображения, ему необходим список вариантов-гипотез. Это позволяет ограничить перебор при распознавании и использовать медленный, но качественный классификатор в качестве сильного. В результате его работы к оценкам вариантов добавится оценка от сильного классификатора. В качестве сильного классификатора в системе ABBYY FLEXICAPTURE используется структурный классификатор, описанный в [Шамис, 2010].
Этап завершающего комбинирования объединяет оценки, полученные после комбинирующего этапа и после распознавания сильным классификатором.
Непосредственно к комбинированию относятся этап нормализации, комбинирующий этап и этап завершающего комбинирования. В дальнейшем рассмотрим различные варианты реализации этих этапов. Также один из вариантов реализации был рассмотрен в [Anisimovichetal., 1997].
2. Этапы комбинирования
2.1 Нормализация
Нормализовать оценки классификаторов к единому диапазону можно несколькими способами: Прямое приведение где nw(w) - нормализованная оценка nw, соответствующая ненормализованнойw;
wmax - максимальная ненормализованная оценка.
Положение в списке где weights - упорядоченный список ненормализованных оценок, полученный после распознавания изображений из некоторого обучающего множества изображений;
length(weights) - количество элементов в weights;
pos(w) - индексwвweights.
Отношение «своих» и «чужих»
, где RIGHTWEIGHTS - упорядоченный список ненормализованных оценок, полученный после распознавания изображений некоторой графемы X эталоном этой же графемы X;
WRONGWEIGHTS - аналогичный список, только составленный из оценок изображений, отличных от X;
less(w,weights) - количество элементов в weights, значение которых равно или меньше w;
more(w,weights) - количество элементов в weights, значение которых равно или больше w.
2.2 Комбинирующий уровень
Объединить оценки нескольких классификаторов можно следующими способами: Максимум
Среднее арифметическое
Средневзвешенная сумма
Средневзвешенная сумма с коэффициентами, отдельными для каждой графемы
2.3 Завершающее комбинирование
Завершающее комбинирование сильного классификатора с результатами комбинирующего: Простая формула
Здесь ws - оценка сильного классификатора;
wc - оценка, полученная после этапа комбинирования, c - коэффициент, соответствующий степени доверия сильному классификатору;
a - минимальная степень доверия, если оценка сильного классификатора равна нулю.
Комбинирующая таблица
Для каждой пары оценок (ws, wc) будет ставиться в соответствие своя объединенная оценка w. Такое соответствие задается предварительно обученной таблицей. Получить коэффициенты этой таблицы можно путем распознавания изображений из обучающей базы всеми эталонами и разделения на множества «своих» и «чужих» оценок, аналогично способу нормализации, описанному ранее.
Далее для каждой пары оценок (ws, wc) считается количество «своих» и «чужих» изображений, распознанных с такой же парой оценок. Объединенная оценка будет равна отношению «своих» изображений с такой парой оценок к сумме «своих» и «чужих» изображений с такой же парой оценок. При этом можно учитывать также изображения, распознанные с близкими по значению парами оценок.
3. Эксперимент
Были проведены эксперименты, заключающиеся в распознавании множества изображений отдельных заглавных букв английского языка. Общее количество таких изображений было 56072, то есть примерно по 2000 изображений на одну графему. В качестве системы распознавания использовалось программное обеспечение, используемое в компании ABBYY для тестирования технологий распознавания рукописных символов, используемых в продукте ABBYYFLEXICAPTURE и других. На момент начала работы в этих технологиях использовались следующие этапы комбинирования: нормализация с помощью положения в списке, комбинирующий уровень с помощью средневзвешенной суммы с коэффициентами, отдельными для каждой графемы, завершающее комбинирование с помощью простой формулы.
Результаты экспериментов с различными вариантами реализации комбинирующих этапов представлены в таблицах 1-4 ниже. Результаты в таблице следует интерпретировать следующим образом: каждая первая строчка - правильный вариант оказался на 1-м месте в списке, каждая вторая строчка - правильный вариант оказался на 1-м или 2-м месте в списке.
Табл. 1.
Результаты распознавания каждым классификатором в отдельности в зависимости от различной нормализации
Простое приведение Положение в списке Отношение «своих» и «чужих»
Классификатор 1 93,70% 90,34% 93,19%
97,90% 96,76% 97,47%
Классификатор 2 69,81% 59,40% 75,58%
92,78% 79,72% 90,83%
Классификатор 3 85,88% 82,43% 87,72%
94,04% 92,42% 94,62%
Табл. 2.
Результаты распознавания после комбинирующего уровня
Простое приведение Положение в списке Отношение «своих» и «чужих»
Максимум 86,84% 96,34% 94,84%
96,98% 99,01% 98,59%
Среднее арифметическое 87,65% 96,51% 95,07%
97,47% 99,12% 98,69%
Средневзвешенная сумма 87,95% 96,62% 95,16%
97,56% 99,14% 98,72%
Средневзвешенная сумма с коэф., отд. для каждой графемы 87,78% 96,57% 95.02%
97.48% 99.07% 98.63%
Отдельно рассмотрим результаты распознавания только одним сильным классификатором. При этом в качестве списка гипотез использовалось все множество графем, изза чего время распознавания было самое долгое среди рассматриваемых конфигураций.
Правильный вариант на первом месте: 97,33%.
Правильный вариант на первом или втором месте: 98.72%. распознавание классификатор символ
Табл.3.
Результаты распознавания полной схемой с завершающим комбинированием с помощью простой формулы
Простое приведение Положение в списке Отношение «своих» и «чужих»
Максимум 96,23% 98,12% 97,48%
99,21% 99,62% 99,44%
Среднее арифметическое 96,24% 98,12% 97.49%
99,25% 99,63% 99,45%
Средневзвешенная сумма 96,28% 98,13% 97,49%
99,30% 99,63% 99,45%
Средневзвешенная сумма с коэф., отд. для каждой графемы 96,28% 98,12% 97,49%
99,27% 99,63% 99,44%
Табл.4.
Результаты распознавания полной схемой в зависимости от завершающего уровня
Простая формула Комбинирующая таблица
Положение в списке средневзвешенная сумма 98,13% 98,14%
99,63% 99,61%
Положение в списке средневзвешенная сумма с отд. коэф. 98,12% 98,14%
99,63% 99,63%
Отношение «своих» и «чужих» средневзвешенная сумма 97,49% 97,49%
99,45% 99,47%
Отношение «своих» и «чужих» средневзвешенная сумма 97,49% 97,51%
99,44% 99,47%
Вывод
По результатам экспериментов были сделаны следующие выводы: Наилучшие способы нормализации для распознавания отдельными классификаторами - простое приведение и отношение «своих» и «чужих».
Наилучший способ нормализации для комбинирования классификаторов - с помощью положения в списке.
Наилучший способ комбинирования нескольких классификаторов - с помощью средневзвешенной суммы. При этом незначительно худшими являются способы с помощью среднего арифметического и средневзвешенной суммы с коэффициентами, отдельными для каждой графемы.
Использование комбинирующей таблицы на завершающем уровне дает незначительный прирост верного результата на 1-м месте, но не всегда - для верного результата на 1-м или 2-м месте. Поэтому предпочтительнее использовать простую формулу, так как она не требует долгого по времени предварительного обучения.
Наилучшая конфигурация комбинирования для рассматриваемой схемы распознавания одного символа: нормализация с помощью положения в списке, комбинирующий уровень с помощью средневзвешенной суммы, завершающий уровень с помощью простой формулы.
Список литературы
Терещенко В.В., Рыбкин В.Ю., Шамис А.Л., Ян Д.Е., Принципы распознавания рукописных символов в системе FINEREADER // РОАИ-III. - Нижний Новгород, 1997.
Шамис А.Л. Модели поведения, восприятия и мышления. - М.: Интуит.РУ, БИНОМ.ЛЗ, 2010.
Ян Д.Е. Исследование, развитие и реализация методов автоматического распознавания рукописных текстов в компьютерных системах. Дис. канд. физ.-мат. наук: 05.13.18. - М., 2003.
Anisimovich K., Rybkin V., Shamis A., Tereschenko V., Using combination of structural, feature and raster classifiers for recognition of hand-printed characters // Proc. of the Intl. Conf. on Document Analysis and Recognition, Ulm, Germany, 1997.