Книги по разным темам
Pages: | 1 | 2 | Критерию регулярности удовлетворяют только те узловые области, для которых имеет место следующее: для всех построенных отрезков li i = 1..n выполнены неравенства li - li-li dmax, tgmax, что соответствует ограничениям на диаметр пера и скорость его 2h изменения.
а) б) в) г) Рис. 9. Изображения, содержащие области, для которых критерий регулярности не выполняется Область кратности 1 также может не оказаться концом штриха (см. рис. 9г). Исходя из предположения о том, что область соприкосновение пишущего инструмента с бумагой представляет собой круг, будем считать, что область, идеально соответствующая концу штриха должна иметь форму полукруга с диаметром пера. Отсюда следует простой и эффективный критерий регулярности для K = 1: отношение периметра узловой области к P периметру полукруга не превышает пороговой величины, т.е. const, где P - d 2 + d периметр узловой области, d - длина основания прилегающей трапеции, по которому узловая область соприкасается с трапецией.
Электронный журнал ИССЛЕДОВАНО В РОССИИ 187 Для областей, кратность которых больше двух (области пересечения штрихов), также может быть построен критерий регулярности, однако он должен быть основан на анализе штрихов в узловой области, который выходит за рамки этапа предобработки. Будем считать, что все узловые области при K > 2 удовлетворяют критерию регулярности.
Если на изображении существуют узловые области кратности 0 или узловые области, для которых не выполняется критерий регулярности, то изображения либо попадает в лотказ как изображение с пятнами или заплывами либо для его распознавания должны быть применены другие методы, основанные на непосредственном построении признаков по бинарной матрице или контуру изображения (см. например [11]).
5. Основной алгоритм построения регулярных областей Регулярной областью назовем область, полученную объединением последовательности чередующихся и соприкасающихся трапеций и узловых областей кратности 2, начинающуюся и заканчивающуюся трапециями. При этом все узловые области удовлетворяют критерию регулярности, а кратность узловых областей, граничных с регулярной областью не равна K = двум (см. рис. 10).
Алгоритм построения регулярных областей удобно описать в терминах теории графов. Рассмотрим неориентированный граф K 2 G=
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 Далее приведен довольно простой алгоритм построения рассматриваемых последовательностей:
Входные данные: G=
Результат: 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=
Шаг 4. Если P(v) = 1 и Qj = 0 где ej =
i j;
перейти к шагу 4;
Шаг 5. Если P(w) = 1 и Qj = 0 где ej =
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 Рис. 12. Результат предобработки изображений На рисунке 13 представлены примеры изображений, попавшие в лотказ при обработке с помощью критерия регулярности.
а) б) K=K=Рис. 13. Изображения, попавшие в лотказ: а) заплыв внутреннего контура, б) пятно Для эксперимента были реализованы точечные методы предобработки, описанные в ранних работах. В таблице 1 представлена скорость обработки изображений из используемой базы. Эксперимент проводился на компьютере с процессором Pentium III, 333 MHz. Как видно из таблицы, быстродействие описанного здесь алгоритма значительно выше по сравнению с существующими методами.
Таблица 1.
Метод предобработки Быстродействие (символов/сек) Точечный алгоритм [9] Точечный алгоритм [3] Представленный алгоритм (грубая аппроксимация границ) Представленный алгоритм (точная аппроксимация границ) 7. Заключение Мы представили алгоритм предобработки изображений рукописных символов имеющий высокую вычислительную эффективность по сравнению с существующими методами. Описанный метод использует точечную обработку изображения только для построения граничной ломаной, этим достигается высокая скорость обработки и устойчивость к искажениям на границе.
Электронный журнал ИССЛЕДОВАНО В РОССИИ 190 Также, мы рассмотрели метод, позволяющий выявлять области, в которых невозможно восстановить траекторию, и тем самым находить изображения, для которых не применим структурный метод распознавания.
Заметим, что описанный алгоритм может быть использован не только в методах восстановления траектории символа. В любых подходах, где используется метод скелетизация изображения, его с успехом можно заменить описанным алгоритмом. При этом сохраняется скорость обработки, устраняются искажения границ и не будет потеряна связь точек траектории с граничными точками.
СПИСОК ЛИТЕРАТУРЫ 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 | 2 |
Книги по разным темам