Введение
В компьютерном зрении или обработке естественного языка анализ структуры документа – это процесс идентификации и категоризации областей интереса на сканированном изображении текстового документа. Система чтения требует сегментации текстовых зон от нетекстовых и упорядочивания их в правильном порядке чтения. Обнаружение и маркировка различных зон (или блоков) как основного текста, иллюстраций, математических символов и таблиц, встроенных в документ, называется геометрическим анализом структуры. Однако текстовые зоны выполняют различные логические функции внутри документа (заголовки, подписи, сноски и т.д.), и этот вид семантической маркировки относится к области логического анализа структуры. Анализ структуры документа представляет собой объединение геометрической и логической маркировки. Обычно он выполняется перед отправкой изображения документа в систему оптического распознавания символов (OCR), но также может использоваться для обнаружения дубликатов одного и того же документа в больших архивах или для индексации документов по их структуре или графическому содержанию. Структура документа формально определена в международном стандарте ISO 8613-1:1989.
Обзор методов
Существует два основных подхода к анализу макета документа. Во-первых, это подходы снизу вверх, которые итеративно анализируют документ, основываясь на исходных данных пикселей. Обычно эти подходы сначала разбивают документ на связанные области чёрного и белого, затем эти области группируются в слова, после чего в текстовые строки и, наконец, в текстовые блоки. Во-вторых, это подходы сверху вниз, которые пытаются итеративно разделить документ на колонки и блоки, используя информацию о пробелах и геометрии. Для любого подхода к анализу макета документа характерны две общие проблемы: шум и перекос. Под шумом понимается шум изображения, например, импульсный шум или гауссовский шум. Перекос означает, что изображение документа может быть повернуто таким образом, что текстовые строки не будут идеально горизонтальными. В алгоритмах анализа макета документа и алгоритмах оптического распознавания символов обычно предполагается, что символы на изображении документа ориентированы так, чтобы текстовые строки были горизонтальными. Поэтому, если присутствует перекос, важно повернуть изображение документа, чтобы его устранить. Следовательно, первые шаги в любом коде анализа макета документа – это удаление шума изображения и определение угла перекоса документа.
Пример подхода "снизу вверх"
В этом разделе мы рассмотрим шаги алгоритма анализа макета документов снизу вверх, разработанного в 1993 году О’Горманом. Шаги в этом подходе следующие: предварительно обработайте изображение для удаления гауссовского и импульсного шума. Обратите внимание, что некоторые фильтры для удаления шума могут воспринимать запятые и точки как шум, поэтому требуется осторожность. Преобразуйте изображение в бинарное, то есть преобразуйте каждое значение пикселя в полностью белый или полностью черный цвет. Сегментируйте изображение на связные компоненты черных пикселей. Это символы изображения. Для каждого символа вычислите ограничивающую рамку и центроид. Для каждого символа определите его k ближайших соседей, где k – целое число, большее или равное четырем. О’Горман предлагает k=5 в своей статье как хороший компромисс между устойчивостью и скоростью. Причина использования хотя бы k=4 заключается в том, что для символа в документе два или три ближайших символа – это те, которые находятся непосредственно рядом с ним на той же строке текста. Четвертый ближайший символ обычно находится на строке непосредственно выше или ниже, и важно учитывать эти символы при вычислении ближайших соседей для последующего анализа. Каждая пара ближайших соседей связана вектором, направленным от центроида одного символа к центроиду другого символа. Если эти векторы построить для каждой пары ближайших соседей, получится так называемый докструм документа (см. рисунок ниже). Также можно использовать угол Θ относительно горизонтали и расстояние D между двумя ближайшими соседями для создания гистограммы углов ближайших соседей и гистограммы расстояний до ближайших соседей. Используя гистограмму углов ближайших соседей, можно вычислить перекос документа. Если перекос достаточно мал, перейдите к следующему шагу. Если нет, поверните изображение, чтобы устранить перекос, и вернитесь к шагу 3. Гистограмма расстояний до ближайших соседей имеет несколько пиков, которые обычно соответствуют расстоянию между символами, между словами и между строками. Вычислите эти значения по гистограмме и отложите их. Для каждого символа рассмотрите его ближайших соседей и отметьте те, которые находятся на расстоянии, близком к расстоянию между символами или между словами с некоторой допустимой погрешностью. Для каждого отмеченного ближайшего соседа проведите отрезок линии, соединяющий их центроиды. Символы, соединенные с соседями отрезками, образуют текстовые строки. Используя все центроиды в текстовой строке, можно вычислить фактический отрезок линии, представляющий текстовую строку, с помощью линейной регрессии. Это важно, поскольку маловероятно, что все центроиды символов в текстовой строке окажутся коллинеарными. Для каждой пары текстовых строк вычислите минимальное расстояние между соответствующими отрезками линий. Если это расстояние находится в пределах допустимого размера расстояния между строками, рассчитанного на шаге 7, то две текстовые строки объединяются в один текстовый блок. Наконец, можно вычислить ограничивающую рамку для каждого текстового блока, и анализ макета документа завершен.
Preprocess the image to remove Gaussian and salt and pepper noise. Note that some noise removal filters may consider commas and periods as noise, so some care must be taken. Convert the image into a binary image, i. e. convert each pixel value to completely white or completely black. Segment the image into connected components of black pixels. These are the symbols of the image. For each symbol, compute a bounding box and centroid. For each symbol, determine its k nearest neighbors where k is an integer greater than or equal to four. O`Gorman suggests k=5 in his paper as a good compromise between robustness and speed. The reason to use at least k=4 is that for a symbol in a document, the two or three nearest symbols are the ones right next to it on the same text line. The fourth nearest symbol is typically on a line right above or below, and it is important to include these symbols in the nearest neighbor calculation for the following. Each nearest neighbor pair of symbols is related by a vector pointing from one symbol’s centroid to the other symbol’s centroid. If these vectors are plotted for every pair of nearest neighbor symbols, then one gets what is called the docstrum for the document (See figure below). One can also use the angle Θ from the horizontal and distance D between two nearest neighbor symbols and create a nearest neighbor angle and nearest neighbor distance histogram. Using the nearest neighbor angle histogram, the skew of the document can be calculated. If the skew is acceptably low, continue to the next step. If it is not, rotate the image so as to remove the skew and return to step 3. The nearest neighbor distance histogram has several peaks, and these peaks typically represent between character spacing, between word spacing, and between line spacing. Calculate these values from the histogram and set them aside. For each symbol, look at its nearest neighbors and flag any of them that are a distance away which is within some tolerance of the between character spacing distance or between word spacing distance. For each nearest neighbor symbol which is flagged, draw a line segment connecting their centroids. Symbols connected to their neighbors by line segments form text lines. Using all the centroids in a text line, one can compute an actual line segment representing the text line with linear regression. This is important because it is unlikely that all the centroids of symbols in a text line are actually collinear. For each pair of text lines, one can compute a minimum distance between their corresponding line segments. If this distance is within some tolerance of the between line spacing calculated in step 7, then the two text lines are grouped into the same text block. Finally, one can calculate a bounding box for each text block, and the document layout analysis is complete.
Программное обеспечение для анализа макета
OCRopus – Бесплатная система анализа структуры документов и оптического распознавания символов (OCR), реализованная на C++ и Python для FreeBSD, Linux и Mac OS X. Это программное обеспечение поддерживает плагины, позволяющие пользователю выбирать из различных алгоритмов анализа структуры документов и OCR. OCRFeeder – Пакет программ для OCR под Linux, написанный на Python, который также поддерживает анализ структуры документов. Это программное обеспечение активно разрабатывается и распространяется по лицензии свободного и открытого исходного кода.