WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     | 1 ||

Критерию регулярности удовлетворяют только те узловые области, для которых имеет место следующее: для всех построенных отрезков li i = 1..n выполнены неравенства li - li-li dmax, tgmax, что соответствует ограничениям на диаметр пера и скорость его 2h изменения.

а) б) в) г) Рис. 9. Изображения, содержащие области, для которых критерий регулярности не выполняется Область кратности 1 также может не оказаться концом штриха (см. рис. 9г). Исходя из предположения о том, что область соприкосновение пишущего инструмента с бумагой представляет собой круг, будем считать, что область, идеально соответствующая концу штриха должна иметь форму полукруга с диаметром пера. Отсюда следует простой и эффективный критерий регулярности для K = 1: отношение периметра узловой области к P периметру полукруга не превышает пороговой величины, т.е. const, где P – d 2 + d периметр узловой области, d – длина основания прилегающей трапеции, по которому узловая область соприкасается с трапецией.

Электронный журнал «ИССЛЕДОВАНО В РОССИИ» 187 http://zhurnal.ape.relarn.ru/articles/2003/019.pdf Для областей, кратность которых больше двух (области пересечения штрихов), также может быть построен критерий регулярности, однако он должен быть основан на анализе штрихов в узловой области, который выходит за рамки этапа предобработки. Будем считать, что все узловые области при K > 2 удовлетворяют критерию регулярности.

Если на изображении существуют узловые области кратности 0 или узловые области, для которых не выполняется критерий регулярности, то изображения либо попадает в «отказ» как изображение с пятнами или заплывами либо для его распознавания должны быть применены другие методы, основанные на непосредственном построении признаков по бинарной матрице или контуру изображения (см. например [11]).

5. Основной алгоритм построения регулярных областей Регулярной областью назовем область, полученную объединением последовательности чередующихся и соприкасающихся трапеций и узловых областей кратности 2, начинающуюся и заканчивающуюся трапециями. При этом все узловые области удовлетворяют критерию регулярности, а кратность узловых областей, граничных с регулярной областью не равна K = двум (см. рис. 10).

Алгоритм построения регулярных областей удобно описать в терминах теории графов. Рассмотрим неориентированный граф K 2 G= в котором множеству K вершин соответствует Рис. 10. Построение регулярной области множество всех узловых областей, а множеству ребер – множество всех трапеций. Ребро e = существует, т.е. e E, если существует трапеция, соприкасающаяся с узловыми областями v, w. На множестве вершин определим предикат P(v) принимающий значение «истина» только если узловая область, соответствующая вершине v имеет кратность 2 и удовлетворяет критерию регулярности. Согласно определению регулярной области, задача поиска всех регулярных областей сводится к поиску всех последовательностей < ei,vj,ei,vj,K,ei,vj,ei >, для которых выполнено следующее условие:

1 1 2 2 N -1 N -1 N ei =< vj,vj >, P(v ) =1 для всех k 2..N -1;

jk k k -1 k ei =< w,vj >, P(w) = 0; (3) 1 ei =< vj, y >, P(y) = 0.

N N -Заметим, что при N = 1 регулярная область состоит только из одной трапеции.

Рис. 11. Выделение трапеций, фильтрация трапеций, выделение регулярных областей, построение траекторий Электронный журнал «ИССЛЕДОВАНО В РОССИИ» 188 http://zhurnal.ape.relarn.ru/articles/2003/019.pdf Далее приведен довольно простой алгоритм построения рассматриваемых последовательностей:

Входные данные: G=, V={v1,…,vn}, E={e1,…,em};

Результат: List = {R1…Rk}, где Ri= < ei,vj,ei,vj,K,ei,vj,ei > ;

1 1 2 2 N -1 N -1 N Шаг 1. Qi 0, i=1…m;

Шаг 2. Найти ребро ei=, i=1…m для которого Qi = 0, Шаг 3. Если ребро ei не найдено – конец работы алгоритма, иначе, создать регулярную область R=; Qi 1;

Шаг 4. Если P(v) = 1 и Qj = 0 где ej =, y w, то R ; Qj 1;

i j; ;

перейти к шагу 4;

Шаг 5. Если P(w) = 1 и Qj = 0 где ej =, y v, то R < ej, w, R >; Qj 1;

i j; ;

перейти к шагу 5;

Шаг 6. Добавить R в List;

Шаг 7. Перейти к шагу 2.

В алгоритме используется вспомогательный массив Q1,… Qm; Qi = 1 если ребро ei уже задействовано в построении какой либо регулярной области. Выбирается произвольное неиспользованное ребро (Шаг 2) на основе которого строится регулярная область в виде последовательности состоящей из одного ребра (Шаг 3). Затем в конец последовательности добавляются ребра и вершины, сохраняющие условие (3) для последовательности (Шаг 4). Аналогично ребра и вершины добавляются в начало последовательности (Шаг 5). На шаге 6 готовая последовательность заносится в список найденных областей и начинается поиск следующей регулярной области (Шаг 7).

Независимо от нумерации вершин и ребер и от существования узловых областей, не удовлетворяющих критерию регулярности, алгоритм строит одно и то же множество непересекающихся регулярных областей. Единственным исключение является область черных точек, в форме кольца, в которой все узловые области имеют кратность равную двум. В этом случае первая выбранная трапеция всегда будет начальной в последовательности, соответствующей единственной регулярной области.

На рисунке 11 приведен полный цикл предобработки. Не сложно построить траекторию каждой регулярная области – она состоит из средних линий внутренних трапеций соединенных как показано на рисунке 8. При построении траектории используется информация, полученная на этапе проверки критерия регулярности внутренних узловых областей. В дальнейшем, при необходимости, траектории регулярных областей сглаживаются.

6. Экспериментальные результаты Для исследований использовалась база, состоящая из 1040 изображений рукописных символов – 40 изображений каждой буквы английского алфавита (20 заглавных и строчных букв). Использовались изображения символов, полученные на различных сканирующих устройствах и написанные разными авторами.

На рисунке 12 приведены примеры выделения регулярных областей на изображениях.

Электронный журнал «ИССЛЕДОВАНО В РОССИИ» 189 http://zhurnal.ape.relarn.ru/articles/2003/019.pdf Рис. 12. Результат предобработки изображений На рисунке 13 представлены примеры изображений, попавшие в «отказ» при обработке с помощью критерия регулярности.

а) б) K=K=Рис. 13. Изображения, попавшие в «отказ»: а) заплыв внутреннего контура, б) пятно Для эксперимента были реализованы точечные методы предобработки, описанные в ранних работах. В таблице 1 представлена скорость обработки изображений из используемой базы. Эксперимент проводился на компьютере с процессором Pentium III, 333 MHz. Как видно из таблицы, быстродействие описанного здесь алгоритма значительно выше по сравнению с существующими методами.

Таблица 1.

Метод предобработки Быстродействие (символов/сек) Точечный алгоритм [9] Точечный алгоритм [3] Представленный алгоритм (грубая аппроксимация границ) Представленный алгоритм (точная аппроксимация границ) 7. Заключение Мы представили алгоритм предобработки изображений рукописных символов имеющий высокую вычислительную эффективность по сравнению с существующими методами. Описанный метод использует точечную обработку изображения только для построения граничной ломаной, этим достигается высокая скорость обработки и устойчивость к искажениям на границе.

Электронный журнал «ИССЛЕДОВАНО В РОССИИ» 190 http://zhurnal.ape.relarn.ru/articles/2003/019.pdf Также, мы рассмотрели метод, позволяющий выявлять области, в которых невозможно восстановить траекторию, и тем самым находить изображения, для которых не применим структурный метод распознавания.

Заметим, что описанный алгоритм может быть использован не только в методах восстановления траектории символа. В любых подходах, где используется метод «скелетизация» изображения, его с успехом можно заменить описанным алгоритмом. При этом сохраняется скорость обработки, устраняются искажения границ и не будет потеряна связь точек траектории с граничными точками.

СПИСОК ЛИТЕРАТУРЫ 1. Govindan V.K., Shivaprasad A.P. Character recognition – a review // Pattern Recognition — 1990. — V. 23. — N 7. — P. 671–683.

2. Tappert C.C., Suen C.Y., Wakahara T. The state of art in on-line handwriting recognition // IEEE Trans. Pattern Anal. Mach. Intell. — 1990. — V. 12. — N 8. — P. 787–808.

3. L’Homer E. Extraction of strokes in handwritten characters // Pattern Recognition — 2000.

— V. 33. — N 10. — P. 1147–1160.

4. Kato Y., Yasuhara M. Recovery of drawing order from single-stroke handwriting images // IEEE Trans. Pattern Anal. Mach. Intell. — 2000. — V. 22. — N 9. — P. 938–949.

5. Jager S. Recovering writing traces in off-line handwriting recognition: using a global optimization technique // Proc. 13th International Conference on Pattern Recognition — 1996.

— P. 150–154.

6. Nishida H. An approach to integration of off-line and on-line recognition of handwriting // Pattern Recognition Letters — 1995. — V. 16. — P. 1213–1219.

7. Lam L., Lee S.-W., Suen C.Y. Thinning methodologies – a comprehensive survey // IEEE Trans. Pattern Anal. Mach. Intell. — 1992. — V. 14. — N 9. — P. 869–885.

8. Котович Н.В., Славин О.А. Распознавание скелетных образов // Методы и средства работы с документами – сборник трудов Института системного анализа РАН — 2000.

9. Nishida H., Suzuki T., Mori S. Thin line representation from contour representation of handprinted characters. — in Simon J.-C., Impedovo S.(Ed.) From pixels to features III :

Frontiers in handwriting recognition — Elsevier — Amsterdam — 1992 — P. 29–44.

10. Wall K., Danialsson P.-E. A fast sequential method for polygonal approximation of digitized curves // Computer Graphics and Image Processing — 1984. — V. 28. — P. 220–227.

11. Trier O. D., Jain A. K., Taxt T. Feature extraction methods for character recognition – a survey // Pattern Recognition — 1996. — V. 29. — N. 4. — P. 641–662.

Pages:     | 1 ||



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.