Автоматическое выделение границ и удаление краевых элементов в бинарных изображениях документов на основе оценок фонта документа

Так как экспертами выделяются некоторые эталонные состояния при планировании найма работников, которым сопоставляются принимаемые решения, то это является достоинством ситуационной модели, что упрощает процесс принятия решений.

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Финаев В.К, Севостьяненко В.В. Методы искусственного интеллекта в управлении персоналом. - Таганрог: Изд-во ТРТУ, 2005. - 167 с.

2. Финаев В.К, Севостьяненко В.В. Системные методы в задачах проектирования сетей информационной связи // Материалы международной научной конференции «Системный подход в науке о природе, человеке и технике» - часть 3. - Таганрог: Изд-во ТРТУ, 2003.

3. Zadeh L.A. Fuzzy logic and approximate reasoning // Synthese, 1975, V. 80. - pp. 407-428.

4. Нечеткие множества в моделях управления и искусственного интеллекта/А.Н.Аверкин, И.З.Батыршин, А.ф.Блиншун, Б.В.Силаев, Б.Н.Тарасов. - М.: Наука, 1986. - 312 с.

5. . ., . ., . . -

четкой логикой. - М.: Наука, 1990. - 272 с.

6. . ., . . . - -тов-на-Дону: Изд-во Ростовского университета, 1993. - 134 с.

7. . ., . .

нечеткой информации. - Ростов-на-Дону.: Изд-во Ростовского университета, 1990. - 128 с.

АЛ. Толкачев

АВТОМАТИЧЕСКОЕ ВЫДЕЛЕНИЕ ГРАНИЦ И УДАЛЕНИЕ КРАЕВЫХ ЭЛЕМЕНТОВ В БИНАРНЫХ ИЗОБРАЖЕНИЯХ ДОКУМЕНТОВ НА ОСНОВЕ ОЦЕНОК ФОНТА ДОКУМЕНТА

. ,

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

Определение границ страницы и процесс их удаления основаны на классифи-/ / , границы и анализе гистограмм профильных проекций и числа переходов в тексто-

. -

жения и отделены от содержания белыми областями. Разрядка между пикселями

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

.

уточнения местонахождения границ. Определение границ страницы и процесс их удаления состоит из 4 шагов, которые будут рассмотрены далее.

Основные характеристики. Гистограмма горизонтальной/вертикальной проекции - сумма черных пикселей, проецируемых на вертикаль-

ную/горизонтальную ось. Гистограмма числа переходов изображает количество

/ 0 1.

Алгоритм размытия (smearing algorithm) заменяет 0 на 1, если число смежных нулей меньше или равно заданной константе C [2].

Информация о фонте включает величину символа (point size), разрядка слов (word spacing), интерлиньяж (linespace), верхние выносные элементы (ascenders), нижние выносные элементы (descenders), линией шрифта (baseline) и медиана (middle line). Величина символа равна высоте прописного знака (Cap-height), который далее будет принят как высота кегельной площадки (em-square). Разрядка слов — пространство между следующими друг за другом словами. Расстояние между соседними строками текста называется интерлиньяж. Нижний выносной эле- , -ных букв (x-height), например, у или ф. Верхний выносной элемент — часть строч-, . -тальная линия, на которой базируются все нижние части прямоугольных букв, называется линией шрифта в то время, как верхняя линия - медианой (рис.1).

A — интерлиньяж

B — высота строчного знака

C — высота прописного знака

E — медиана

1 — верхний выносной элемент

2 — нижний выносной элемент

3 — кегельная площадка

Рис.1. Элементы фонта

Текстовый квадрат бинарного изображения определяется как квадратная область, в которой доминируют текстовые данные. Нетекстовый квадрат — об-

[1,3]. По аналогии вводятся понятия текстовых, нетекстовых и чистых строк/столбцов.

Линии текста отделены друг от друга межстрочными интервалами, поэтому гистограмма проекции для текстовой области будет содержать черные и белые серии, которые будем называть черно-белыми текстовым и структурами[\,5\. Эти структуры (рис.2) удовлетворяют следующим двум эмпирическим условиям:

Длина белой полосы >= 1,

МтЕЮЭТЗКЕ <= длина черной полосы <= МахРООТ8ЕЕ.

ита::::мо::| кажстві

черная

полоса

белая

полоса

"черная

_полоса

белая

полоса

"черная

„полоса

Рис. 2. Формирование черно-белых текстовых структур

Значения для М1пРОЭТ8КЕ и МахРОЭТ8КЕ принимаются равными 3 и 18

. , ,

документах основной текст набирается размером в этих пределах. Менее 3 пунктов текст при сканировании становится не читабельным, а кегль более 18 пунктов ис, , .

Оценка размера фонта. Бинарное изображение разбивается на квадраты, величина которых зависит от разрешения изображения [1,3]. Каждый квадрат затем классифицируется как текстовый или нетекстовый. Информация о фонте затем может быть оценена при анализе гистограмм проекций всех текстовых квадратов. Г оризонтальная гистограмма используется для изображений с книжной ориентаци-, — . -деленности будем полагать, что имеется изображение с книжной ориентацией.

Примем за Htop дистанцию от линии шрифта до верха верхнего выносного элемента, за Hbot (дистанцию от линии шрифта до верха верхнего выносного элемента символов строкой ниже, а за Hmd - высоту строчного знака.

Тогда размер может быть оценен следующим образом:

1. -

белых текстовых структур. Позиция максимального значения из гистограммы длин белых полос соответствует величине Нь<а.

2. -

ся значения, соответствующие чистым строкам, т.е. которые меньше RвlankSquaren, ГДе RвlankSquare - Параметр, ОПреДвЛЯЮЩИЙ «ПуСТуЮ» СТрОКу [5], а п - ширина квадрата. Это выполняется для того, чтобы исключить влияние верхних и нижних выносных элементов на черно-белые тексто-.

3. - ,

и величина Нт^ находится в соответствии с максимумом из гистограммы длин черных полос.

4. В гистограмме длин черных полос, построенной в п.1, находится отличный от Нт^ максимум, т.е. который лежит за пределами [Нт^д, Нт^д], где д берется равным 20% от НтМ. Позиция максимума указывает на величину Нщ.

5. Величины верхнего выносного элемента Нс^с и нижнего выносного элемента Н^с вычисляются по формуле:

Навс Н,еяс Н^р - Hmid.

6. Высота символа Нл, разрядка слов Wx и пространство между линиями Wy находятся по формулам:

Нск Hmid + На%с + Hdesc,

Wx = Нсь/2,

Wy = Hbot - Нскзс.

Оценка областей границ нетекстовых краевых элементов. Области нетекстовых границ могут быть приблизительно локализованы по идентификации /

этих нетекстовых столбцов/строк до текстовых и чистых столбцов/строк в отношении к разрядке и интерлиньяжу.

Эту процедуру можно записать следующим образом:

1) -ластей возле краев изображения.

2) :

3) если нетекстовый, то (число черных пикселей / всего пикселей) >

RGraphicSquare ,

4) иначе текстовый, где RGm!,hCSquare — параметр, определяющий «графиче-

» [5].

5) , , -

стовых границ по следующему правилу: левая/правая граница начинается от левой/правой грани изображения и заканчивается, когда число непрерывно следующих друг за другом текстовых или чистых столбцов больше чем Wx.

6) / / -жения и заканчивается, когда число непрерывно следующих друг за другом текстовых или чистых строк больше чем половина Wy.

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

Эту процедуру можно записать следующим образом:

1) -

ции областей возле краев изображения, исключая все области нетексто-.

2) Размыть горизонтально при C=Wx, размыть вертикально при C=Wy.

3) -дов для областей возле краев изображения, исключая все области нетекстовых границ;

4) :

5) ЧИСТЫЙ еСЛИ (ЧИСЛО черных пикселей / ВСегО пикселей) < RвlankSquare и (число переходов) < RBlan|XCoшts, нетекстовый если (число черных пикселей / всего пикселей) > RGraphicSquare, ИНаче текстовый, где RвlankXCounts — величина, определенная эмпирически и равная 0.010 [5].

6) , , -вых границ по следующему правилу: левая/правая граница начинается

/ ( -вую/правую границы) и заканчивается, когда число непрерывно следующих друг за другом чистых столбцов больше чем Wx.

7) Верхняя/нижняя граница начинается от верхней/нижней грани изобра-( / ) -

,

больше, чем Wy.

Определение границ страницы и их коррекция. На этом этапе границы страницы исправляется по рамке области содержания страницы (желательная об), -ванных краевых элементов с проверкой дистанции от них по отношению к граням

,

.

Следующая процедура описывает определение границы страницы:

1. Размыть горизонтально при C=Wx, размыть вертикально при C=Wy.

2.

объектов, вычисляются координаты объектов и удаляются те объекты, размеры которых не больше половины Wx.

3. / ,

которые не находятся вплотную с верхней/нижней границей.

4.

объектов, вычисляются координаты объектов и удаляются те объекты, размеры которых не больше половины Wx.

5. Левая/правая границы исправляются по местонахождению объектов, ко-

торые не находятся вплотную с левой/правой границей, а также новыми верхней и нижней границами.

Результаты экспериментов. По описанным алгоритмам было разработано , -бражения из указанного каталога. Все изображения были отсканированы при разрешении 300 dpi в черно/белом (бинарном) формате. Обработке по данным алгоритмам предшествовал этап выравнивания изображений, как это описывается в [1], . . ,

.

В таблице представлены результаты этапа оценки размера фонта для 17 изо, .

Таблица

_________Результаты оценки размера фонта____________

Документ Размер фонта \-height азсеМег/ иезсепиег

0001.tif 40 28 6

0002.tif 38 22 8

0003.tif 40 22 9

0004.tif 38 22 8

0005.tif 40 22 9

0006.tif 36 22 7

0007.tif 38 22 8

0008.tif 39 21 9

0009.tif 38 22 8

0010.tif 29 15 7

0011.tif 38 22 8

0012.tif 40 22 9

0013.tif 38 22 8

0014.tif 38 22 8

0015.tif 38 22 8

0016.tif 40 22 9

0017.tif 40 22 9

В результате анализа данных можно сделать вывод, что в 96% случаев размеры фонта были оценены с точностью в 2 пикселя. В остальных случаях имели ме-, . К таким изображениям относятся обложки или документы, в тексте которых встречаются формулы. Необходимо отметить, что разница в размере фонта в 1р1 при разрешении сканирования в 300 dpi составляет 300/72^4 пикселя. Поэтому погрешность в 2 пикселя можно считать допустимой для точного определения .

В дальнейшем на основе оценки размера фонта были последовательно проведены этапы оценки областей границ и удаления краевых элементов. Анализ обработки свыше 300 изображений документов показал, что границы полезной составляющей на изображении документа были определены правильно в 90% случаев. Пример оценки границ представлен на рис.3. При этом ошибки можно объяснить , , пустотами, тем самым, делая невозможным их отсечение описанным методом. В , , , включающий в себя сегментацию на блоки, их категоризацию и анализ размещения отдельных блоков.

Заключение. Автоматизация процесса сегме нтации изображения документа, как правило, основывается на ряде предположений. Так, к примеру, в алгоритме размытия [2] используются константы, которые позволяют объединить буквы одного слова в единый сегмент. Эти константы должны коррелироваться с параметрами фонта и задаются изначально. Однако при потоковом вводе большого объема документов существует достаточно большой разброс в величинах этих параметров.

б

а

Рис.3. Оценка областей границ: а) исходное изображение; б) изображение после удаления границ

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

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Вишняков Ю.М., Толкачев AM. Алгоритмы автоматического определения ориентации и угла наклона бинарных изображений // Информационные технологии, системный анализ и управление. III Всерос. науч. конф. молодых ученых, аспирантов и студентов: Сборник трудов. - Таганрог: Изд-во ТРТУ, 2005. - С. 138-150

2. Wong K.Y., Casey R.G, Wahl F.M. Document analysis system - IBM J. Res. Devel, 1982, Volume 26, №6. - C. 647-656

3. Le D.X., Thoma G.R. Document skew angle detection algorithm - Proc. SPIE Symposium on Aerospace and Remote Sensing - Visual Information Processing II, 1993, Volume 1961. - C. 251-262

4. Le DX., Thoma G.R. Automated portrait/landscape mode detection on a binary image - Proc. SPIE - Visual Information Processing II, 1993 Volume 1961. - C. 202-212

5. Le DX., Thoma G.R., Wechsler H. Automated borders detection and adaptive segmentation for binary document images - Proceedings of the International Conference on Pattern Recognition (ICPR '96), 1996, Volume III-Volume 7276. - C. 737-742