Генетический алгоритм распознавания рукописных символов



Скачать 197.26 Kb.

Дата07.04.2017
Размер197.26 Kb.
Просмотров121
Скачиваний0

51
ГЕНЕТИЧЕСКИЙ АЛГОРИТМ РАСПОЗНАВАНИЯ
РУКОПИСНЫХ СИМВОЛОВ
О. Ю. Котов
В последнее время в связи с широким распространением и попу- лярностью автоматической обработки данных часто возникает про- блема преобразования рукописного текста или отдельных символов
(букв, цифр, специальных символов) в вид, «понятный» компьютеру, или, проще говоря, проблема распознавания рукописных символов.
Несмотря на то, что данная проблема легче всего решается при ис- пользовании так называемого перьевого ввода (например, в наладон- ных компьютерах и других PDA-устройствах), когда программа рас- познавания «знает», как именно был нарисован символ, наибольший интерес все же представляет возможность распознавания символов, предварительно записанных на бумаге и затем отсканированных.
Рассматриваемый здесь алгоритм, вообще говоря, является сово- купностью нескольких алгоритмов, применяемых последовательно, – это скелетизация (утончение линий в изображении), векторизация
(преобразование изображения в векторную форму), удаление «шпор»
(мешающих распознаванию коротких отрезков, часто возникающих на этапе скелетизации), поиск отдельных букв и, наконец, непосредст- венно распознавание отдельного символа.
Итак, пусть у нас имеется уже отсканированное изображение, пе- реведенное в однобитовый режим (рис.1).
Необходимо толстые линии на рисунке сделать тонкими, чтобы далее можно было произвести векторизацию. Для этого и нужен алго- ритм скелетизации. В данной работе используется так называемый
SPTA-алгоритм, или алгоритм утончения, с использованием безопас- ных точек (safe-point thinning algorithm), предложенный Наккаче и
Шингалом (Nabil Jean Naccache & Rajjan Shinghal)[1]. Данный алго- ритм был выбран за его относительную простоту, быстродействие и наилучшую среди 14 других алгоритмов «чистоту» получающейся картинки (наименьшее количество «шпор» и т. д.). Основное предна- значение алгоритма – итерационно удалять краевые точки (edge- points) так, чтобы, во-первых, не удалять концевые точки (end-points)
(которые находятся на конце штриха), во-вторых, не нару- шать «связанность» рисунка и, в-третьих, не приводить к из-
Рис.1

52
лишнему «разъеданию» рисунка. Алгоритм SPTA достаточно быстр, легко дополнительно оптими- зируется и выдает ре- зультат буквально после нескольких проходов.
После скелетизации мы имеем следующую картинку (рис. 2). Сле- дующий шаг задачи – это векторизация изображения (перевод его в такую форму, когда оно представлено набором отрезков).
Алгоритм векторизации работает следующим образом.
1.
Ищется начало какого-нибудь отрезка – точка, у которой есть толь- ко один сосед.
2.
Координаты каждой точки добавляются в массив, хранящий коор- динаты всех точек в текущей кривой. Для каждой новой точки прове- ряется, чтобы получившаяся кривая не была слишком выгнутой.
3.
Ищется очередная точка кривой. Здесь может быть несколько ва- риантов:

у текущей точки вообще нет соседей;

у текущей точки ровно одна соседняя точка;

и, наконец, самый сложный вариант – у текущей точки несколько
соседей, в этом случае выбирается та точка, которая ближе всего по направлению к текущему направлению вектора; затем текущая точка стирается, но запоминается в массиве точек, которые нужно восстано- вить после окончания отслеживания текущего вектора (так как эта точка, возможно, является началом еще одного отрезка), наилучшее направление выбирается по минимуму угла между текущей точкой, точкой начала отрезка и искомой точкой.
В результате работы мы получим вместо растровой картинки не- сортированный набор векторов (т. е., вообще говоря, отрезки, нахо- дящиеся рядом, не обязательно будут последовательно располагаться в массиве отрезков).
Иногда в результате скелетизации образуются так называемые
«шпоры» – короткие отрезки, которые могут помешать распознава- нию. Если их достаточно много, то можно запустить алгоритм удале- ния «шпор», который сводится к удалению достаточно коротких от- резков, имеющих не более одного отрезка по соседству.
После векторизации и удаления «шпор» необходимо выделить от- дельные буквы. Для этого служит алгоритм выделения. Его суть в том,

53
что для каждого вектора рекурсивно ищем все соседние векторы, при- чем два отрезка являются соседними, если, во-первых, какой-либо из концов одного находится недалеко от какого-либо конца другого от- резка или, во-вторых, отрезки пересекаются или почти пересекаются.
Таким образом, процедура нахождения всех соседей данного вектора работает следующим образом:
1.
Ставится некоторая пометка на данный вектор.
2.
Проверяется соседство данного вектора и всех остальных. Если данный вектор является соседним по отношению к какому-либо дру- гому и второй вектор не помечен, то рекурсивно запускается процеду- ра нахождения всех соседей второго вектора.
3.
Процедура последовательно перебирает все соседние непомечен- ные векторы, рекурсивно запускаясь для каждого из них, и выходит, когда все соседние векторы уже помечены или соседи отсутствуют.
В результате все помеченные векторы образуют некую систему отрезков, которая в большинстве случаев и является символом. После этого данные группы отрезков сохраняются для дальнейшего распо- знавания в отдельных массивах и удаляются из основной массы от- резков. Результат работы алгоритма показан на рис.3.
После того как отдельные символы выделены, можно приступать непосредственно к их распознаванию. Необходимо каким-то образом сравнивать два символа – эталонный и распознаваемый – и выбрать среди эталонных символов тот, который наиболее похож на распозна- ваемый.
Так как символы могут иметь разную высоту, ширину, наклон и поворот, необходимо попытаться максимально приблизить исходный символ к эталонному с помощью масштабирования, поворота и на- клона. Так как символы представлены в векторной форме, сами эти операции не представляют труда, однако из-за того, что неизвестно,
как именно нужно масштабировать, наклонять, поворачивать симво- лы, сам подбор параметров наклона, поворота и масштабирования может занять достаточно много времени. Для ускорения подбора и воспользуемся генетическим алгоритмом (ГА). Суть его сводится к следующему.
Рис.3

54
На первом шаге формируется случайная популяция, каждая особь которой представлена бинарной строкой, заключающей в себе четыре параметра (коэффициенты масштабирования, угол наклона и угол по- ворота). На каждом последующем шаге ГА происходит, во-первых, так называемый кроссовер, или скрещивание, когда две особи обме- ниваются своими частями; во-вторых, с малой вероятностью – мута- ция, когда единичный бит может случайно изменить свое значение; и, в-третьих, отбор на основе функции приспособленности (фитнесс- функции) каждой особи. Количество «потомков» данной особи про- порционально ее фитнесс-функции. В свою очередь фитнесс-функция особи рассчитывается, исходя из «похожести» эталонного символа и исходного с учетом сделанных преобразований. Генетический алго- ритм прорабатывает достаточно большое число (порядка тысячи) по- пуляций, в результате чего получает оптимальные параметры для пре- образования.
При сравнении двух символов каждому вектору одного ищется соответствующий вектор второго символа, и, если такой вектор нахо- дится (т. е. вектор, расположенный примерно в том же месте и на- правленный примерно так же), к «похожести» символов добавляется некоторое значение. В результате работы всего алгоритма выбирается тот эталонный символ, который при преобразованиях больше всего похож на распознаваемый.
При проверке на реальных изображениях алгоритм давал относи- тельно неплохие результаты, однако встречались ошибки при распо- знавании похожих по написанию букв (например, «И» и «Н»).
Литература
1.
Naccache E. J. SPTA: A proposed algorithm for thinning binary patterns. IEEE
Transactions on Systems, Man and Cybernetics. V. SMC-14 № 3. 1984.
2.
Pavlidis T. Algorithms for Graphics and Image Processing. Rockville MD: Com- puter Science Press. 1982. P. 195–214.


Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©nethash.ru 2017
обратиться к администрации

войти | регистрация
    Главная страница


загрузить материал