СПОСОБ ОБЕСПЕЧЕНИЯ КОРРЕКТНОЙ ОРИЕНТАЦИИ ДОКУМЕНТОВ ПРИ АВТОМАТИЧЕСКОЙ ПЕЧАТИ
METHOD TO ENSURE CORRECT ALIGNMENT OF DOCUMENTS IN AUTOMATIC PRINTING

Изобретение относится к технологиям обработки изображений в процессе сканирования и копирования, а более конкретно к корректной ориентации обрабатываемых изображений, в частности, при распознавании текста.
Автоматизация процессов распознавания текста в качестве одного из важных этапов требует надежного способа автоматического определения ориентации индивидуальных страниц. Перевернутые страницы (верхняя сторона внизу) нередко приводят к сбоям в распознавании текста. Такие случаи возникают, как правило, на этапе сканирования бумажных документов. Ориентация страницы документа определяется направлением печати строк текста. При печати текст обычно выводится в портретном или ландшафтном режиме. Следовательно, страница может быть напечатана либо в горизонтальной ориентации (портретный режим) или вертикальной ориентации (ландшафтный режим). Для процесса распознавания текста важно знать ориентацию текста в изображении документа до начала операции распознавания. Точное автоматическое определение ориентации страниц повышает производительность автоматизированных систем распознавания текста и облегчает дальнейшую обработку документа, поступающего с автоподатчика, например, с применением степлера, дырокола или устройства для скрепления печатных блоков.
Известные из уровня техники подходы к определению ориентации документа использовали методы, основанные на вертикальных и горизонтальных вариациях профилей проекций в двоичном изображении. Главным источником ошибок в этих подходах являлось присутствие нетекстовых данных. Алгоритмы работали только для документов с преобладанием текста. Таким образом, первым шагом в определении ориентации документа является нахождение текста.
Патент США № 5767978 [1] описывает метод классификации областей изображения на три класса, такие как традиционный текст, штриховая графика и фотографии. Классификация выполняется на основе результатов статистического анализа изображения по значениям градиента яркости и абсолютной яркости каждого пикселя. Очевидно, результаты классификации зависят от точности алгоритма сегментации области изображения. Классификация может быть ошибочной, если область изображения содержит данные, которые принадлежат более чем одному классу данных. Например, если область изображения содержит текст и фото, она может быть классифицирована в любой из трех классов. Надежность классификации может быть повышена за счет использования разделителя областей взамен разделителя линий и применения иных, более сложных, методов классификации областей. Области штриховой графики имеют промежуточные признаки, и области, которые не удовлетворяют критериям текста или фото, классифицируются как штриховая графика.
Наиболее близким к заявляемому изобретению является патент США №5889884 [2], который описывает метод автоматического определения ориентации изображения (нормальное, перевернутое) документа. Алгоритм предназначен для работы с текстами на романских языках. При этом анализируют распределение кумулятивных значений пикселей в профилях проекций в вертикальном и горизонтальном направлениях. Алгоритм работает только с бинарными изображениями документов с преобладанием текста и не способен определять портретную/ландшафтную ориентацию. Алгоритм не работает с цветными изображениями и с документами, содержащими фотографии.
Задача, на решение которой направлено заявляемое изобретение, заключается в разработке усовершенствованного способа обеспечения корректности ориентации страницы исходного документа, в том числе при наличии цветных изображений.
Технический результат заключается в том, что применен усовершенствованный способ определения корректности ориентации страницы, содержащей текст либо на романских языках, либо на славянских языках, причем в способе предусмотрена возможность исправления вероятных ошибок ориентации. Способ заключается в выполнении следующих операций:
- выполняют выделение текстовых блоков;
- выполняют проверку, является ли число текстовых блоков меньше заданного порога;
- в случае, если число текстовых блоков меньше заданного порога, то определения ориентации документа не выполняют;
- в случае, если число текстовых блоков больше заданного порога, то выполняют заливку нетекстовых областей белым цветом;
- выполняют преобразование RGB изображения (здесь RGB означает 24-битовый формат файла цветных изображений, при котором отводится по 8 бит на красный, зеленый и синий цвета) в бинарное изображение;
отличающийся тем, что
- выполняют вычисление параметров асимметрии текста исходного документа (asym0) и текста документа, повернутого на 90° (asym90);
- выполняют вычисление горизонтального коэффициента (ah) и вертикального коэффициента (av);
-выполняют проверку, является ли значение параметра асимметрии текста исходного документа (asym0) больше нуля и горизонтальный коэффициент (ah) превышает вертикальный коэффициент (av);
- в случае, если в результате проверки установлено, что значение параметра asym0 больше нуля и горизонтальный коэффициент ah превышает вертикальный коэффициент av, делают заключение, что документ имеет корректную ориентацию для текста на романских языках, причем для текста на славянских языках осуществляют поворот изображения на угол 180°;
- в случае, если в результате проверки установлено, что условие, касающееся того, что значение параметра asym0 больше нуля и горизонтальный коэффициент ah превышает вертикальный коэффициент av, не выполняется, то проверяют, является ли значение параметра asym0 меньше нуля, и горизонтальный коэффициент ah превышает вертикальный коэффициент av;
- в случае, если в результате проверки установлено, что значение параметра asym0 меньше нуля и горизонтальный коэффициент ah превышает вертикальный коэффициент av, делают заключение, что документ имеет корректную ориентацию для текста на славянских языках, а для текста на романских языках осуществляют поворот изображения на угол 180°;
- в случае, если в результате проверки установлено, что условие, касающееся того, что значение параметра asym0 меньше нуля и горизонтальный коэффициент ah превышает вертикальный коэффициент av, не выполняется, проверяют, является ли значение параметра asym90 больше нуля и горизонтальный коэффициент ah меньше, чем вертикальный коэффициент av;
- в случае, если условие, касающееся того, что значение параметра асимметрии текста исходного документа, повернутого на 90°, т.е. asym90, больше нуля и горизонтальный коэффициент ah меньше, чем вертикальный коэффициент av, выполняется, то осуществляют поворот изображения на угол 90°;
- иначе поворачивают изображение на угол 270° для корректной ориентации.
При реализации заявляемого способа важно, чтобы операцию по проверке корректности ориентации электронного представления страницы выполняли исходя из распределения пикселей изображения в направлении сканирования и в перпендикулярном направлении.
Что касается аппаратной реализации способа, то для этого достаточно применить формирователь изображения, выполненный с возможностью генерации копий с электронного представления страницы документа, включающий:
- блок формирования изображения для генерации копий с электронного представления страницы документа;
- процессор;
- блок памяти, содержащий алгоритм обработки страницы, выполняемый процессором при проверке корректности ориентации электронного представления страницы и вращении электронного представления страницы до корректной ориентации.
Кроме того, в такой формирователь изображения целесообразно дополнительно ввести оптический сканер. В общем случае, в качестве такого формирователя может использоваться МФУ.
Следует отметить, что заявляемый способ позволяет определять, имеет ли страница портретную или ландшафтную ориентацию, нормальную ориентацию или ориентацию «верхняя сторона внизу».
Это определяют, вычисляя асимметрию текста, состоящего из букв романского или славянского алфавита. Существующие алгоритмы используют асимметрию текста только для определения нормальной/перевернутой ориентации. Это делает невозможным применение существующих подходов для корректной ориентации страниц формата портретный/ландшафтный. Предложенный алгоритм определяет как нормальную/перевернутую, так и портретную/ландшафтную ориентацию. Это преимущество делает предложенный алгоритм весьма эффективным при его реализации в МФУ.
Заявляемое изобретение обеспечивает способ для простого, эффективного и экономичного определения ориентации текста в черно-белом или цветном изображении документа, имеющего в своем составе нетекстовые компоненты (фото, рисунки и т.д.).
Первым шагом в определении ориентации страницы является нахождение области текста. Затем идет обработка только текстовой области для определения ориентации. Следующий шаг это преобразование RGB изображения в бинарное. Затем вычисляется асимметрия для вертикального и горизонтального профилей проекций и определяется, корректно ли ориентирована страница, если нет, производится ее переориентация.
Более детально сущность заявляемого изобретения поясняется далее с привлечением графических материалов.
Фиг.1. Выровненный по вертикали фрагмент страницы.
Фиг.2. Горизонтальная проекция страницы.
Фиг.3. Вертикальная проекция страницы.
Фиг.4. Горизонтальный профиль проекции после пороговой обработки.
Фиг.5. Дифференцированный горизонтальный профиль проекции после пороговой обработки.
Фиг.6. Квадрат дифференцированного профиля проекции после пороговой обработки.
Фиг.7. Квадрат дифференцированного профиля проекции после пороговой обработки со знаком.
Фиг.8. Блок-схема алгоритма вычисления асимметрии.
Фиг.9. Блок-схема алгоритма определения ориентации документа.
Способ автоматического определения ориентации документа основан на асимметрии текста, выполненного на основе романского или славянского алфавита. Например, в английском языке прописные буквы вытянуты вверх по сравнению со строчными буквами. Строчные буквы "b, d, f, h, i, j, k, l, t" имеют части, вытянутые вверх в сравнении с другими строчными буквами, и только буквы "g, j, p, q, y" имеют части, вытянутые вниз в сравнении с другими буквами. Также букв, имеющих части вытянутые вверх (например b) встречается обычно больше, чем букв, имеющих части вытянутые вниз (например p), даже если рассматривается частота встречаемости соответствующих букв. В заявляемом изобретении верх и низ серии букв определяется на основе вышеупомянутых характеристик романского алфавита. В частности, для строчных букв английского языка частота встречаемости букв "b, d, f, h, i, j, k, l, t" 26,5%, букв "g, j, p, q, y" 6,25% и остальных букв 67,25% соответственно (см. Kahn D., 1967. The Code breakers - the Story of Secret Writing. Macmillan, New York. [3]). Данное соотношение справедливо и для других романских языков (немецкого, французского и др.). Для документа, содержащего достаточно большое число букв, верх будет в том направлении, в котором больше выступает основная часть строк текста.
Признаки извлекаются из профилей проекций строк текста. Обозначим как page(N,M) бинарное изображение документа, имеющего N строк и М колонок. Определим вертикальный профиль проекции как сумму черных пикселей, перпендикулярных оси y, т.е. он представляется вектором Pv длины N:
Горизонтальный профиль проекции - это сумма черных пикселей, перпендикулярных оси x, т.е. он представляется вектором Ph длины М:
На Фиг.1 показан развернутый вниз фрагмент текстовой страницы вдоль горизонтального направления. В дальнейшем рассматривается повернутый таким образом текст. Алгоритм основывается на вычислении профиля горизонтальной проекции вдоль достаточно узкой вертикальной полосы страницы текста. Результаты для конкретной вертикальной полосы страницы текста обычно объединяют с соответствующими результатами для других таких полос.
На Фиг.2 показан горизонтальный профиль проекции фрагмента страницы с Фиг.1. На Фиг.3 показан вертикальный профиль проекции фрагмента страницы с Фиг.1.
На Фиг.2 можно видеть, что график горизонтального профиля проекции обнаруживает два признака асимметрии нормального и перевернутого текста. Первый - это структура пиков и второй - структура плато пиков. У основания нижний пик значительно меньше, чем верхний пик. На плато нижний пик значительно больше, чем верхний пик.
Определяют асимметрию текста asym. Применив пороговую обработку к горизонтальным пикам проекции на уровне плато, получают tp (threshold projection):
tp(j)=min(Ph(j), thresh*max(Ph)),
где соответствующее значение thresh для порога относительно глобального максимума функции проекции в данной реализации равно 0,4. График tp показан на Фиг.4.
Следующий шаг - это дифференцирование результата пороговой обработки проекции. Определяют dtp (differentiated threshold projection) как
dtp(j)=tp(j+1)-tp(j)
На Фиг.5 показан график dtp. Из графика можно видеть, что каждая строка текста характеризуется одним или двумя большими положительными пиками сверху и, обычно, одним даже большим отрицательным пиком снизу, а также несколькими меньшими пиками. Это подтверждает, что асимметрия текста сохраняется и на этом этапе алгоритма.
Интеграл от dtp по всем строкам является разницей между значениями для tp для низа и верха строк теста и не служит индикатором ориентации. Для эффективного определения ориентации необходимо нелинейно трансформировать dtp для выявления разницы высот пиков. Возведение в квадрат является достаточно эффективным. Следовательно, вычисляют sdtp (squared differentiated threshold projection) как
2
sdtp(j)=dtp(j)
График квадрата дифференцированного профиля проекции после пороговой обработки показан на Фиг.6.
Так как при возведении в квадрат теряется важная информация о знаке, которая присутствует в dtp, то выполняют восстановление этой информации, налагая знак dtp на sdtp, т.е. формируя ssdtp (signed squared differentiated threshold projection):
ssdtp(j)=sign(dtp(j))*sdtp(j)
График квадрата дифференцированного профиля проекции после пороговой обработки со знаком показан на Фиг.7.
Ориентация страницы определяется из функций sdtp и ssdtp на основе того, что корректно ориентированная страница будет иметь отрицательные пики ssdtp, преобладающие над положительными в среднем для всех строк. Нормализованная мера этой асимметрии asym' определяется как
где текст корректно ориентирован, когда asym' положительна и текст перевернут, когда отрицательна, что отражено в дискретной переменной up':
up'=asym'>0
Уровень достоверности переменной up' возрастает с возрастанием абсолютного значения asym'.
Алгоритм позволяет вычислить горизонтальную проекцию по достаточно узкой вертикальной полосе страницы текста (Фиг.1). Результаты для данной полосы текста могут быть объединены с соответствующими результатами для других таких полос. Предыдущие шаги повторяют для каждой вертикальной полосы, и функции sdtp и ssdtp накапливаются по всем полосам, формируя csdtp (cumulative squared differentiated threshold projection) и cssdtp (cumulative signed squared differentiated threshold projection):
Нормализованная мера асимметрии текста asym определяется как
где текст корректно ориентирован, когда asym положительна, и текст перевернут, когда отрицательна, что отражено в дискретной переменной up
up=asym > 0
Поскольку знаменатель asym положителен, результат определения ориентации зависит только от числителя asym. Знаменатель asym имеет важное свойство нормализации статистики, так что независимо от величины последнего, значение asym всегда связано с тем же уровнем доверительности в принятии решения об ориентации. Заметим, что суммарные результаты по вертикальным полосам могут быть расширены на несколько страниц с соответствующим повышением уровня доверительности по принятию решения об ориентации, если известно, что страницы имеют одинаковую ориентацию.
Для области текста ошибка определения asym обратно пропорциональна квадратному корню из площади области текста (чем больше область текста, тем точнее результат).
Алгоритм вычисления асимметрии текста
1. Вычисление профиля проекции.
2. Применение пороговой обработки для проекции.
3. Дифференцирование профиля проекции после пороговой обработки.
4. Вычисление квадрата дифференцированного профиля проекции после пороговой обработки.
5. Вычисление квадрата дифференцированного профиля проекции после пороговой обработки со знаком.
6. Вычисление кумулятивного квадрата дифференцированного профиля проекции после пороговой обработки.
7. Вычисление кумулятивного квадрата дифференцированного профиля проекции после пороговой обработки со знаком.
8. Вычисление асимметрии текста asym.
9. Для романских языков, если asym > 0, то текст ориентирован корректно, иначе текст перевернут. Для славянских языков, если asym < 0, то текст ориентирован корректно, иначе текст перевернут.
Фиг.8 представляет блок-схему алгоритма для вычисления асимметрии текста. На этапе 801 выполняется вычисление профиля проекции. На этапе 802 выполняется вычисление результата пороговой обработки для проекции. На этапе 803 выполняется вычисление дифференцированного профиля проекции после пороговой обработки. На этапе 804 выполняется вычисление квадрата дифференцированного профиля проекции после пороговой обработки. На этапе 805 выполняется вычисление квадрата дифференцированного профиля проекции после пороговой обработки со знаком. На этапе 806 выполняется вычисление кумулятивного квадрата дифференцированного профиля проекции после пороговой обработки со знаком. На этапе 807 выполняется вычисление кумулятивного квадрата дифференцированного профиля проекции после пороговой обработки со знаком. На этапе 808 выполняется вычисление асимметрии текста asym. На этапе 809 алгоритм проверяет, является ли asym больше нуля. Если да, то на этапе 810 ориентация корректна для романского языка, а для славянского языка страница перевернута. Если нет, то на этапе 811 ориентация корректна для славянского языка, а для романского языка страница перевернута.
Пусть asym0 - это ориентация исходного документа изображения, asym90 - асимметрия исходного изображения, повернутого на 90°; asym180 - асимметрия исходного изображения, повернутого на 180°, и asym270 - асимметрия исходного изображения, повернутого на 270°. Здесь и далее подразумевается угол поворота против движения часовой стрелки. Asym0 и asym180, asym90 и asym270 имеют приблизительно одинаковые значения, но противоположные знаки. Пусть коэффициенты ah0 и av0 являются средними абсолютными значениями для asym0 и asym180, asym90 и asym270 (здесь h означает горизонтальное направление, a v - вертикальное направление):
ah0=0.5*(|asym0|+|asym180|)
av0=0.5*(|asym90|+|asym270|)
Был проведен эксперимент по вычислению коэффициентов ah0 и av0. Использовалась база данных изображений более чем 500 цветных и черно-белых документов, сканированных с разрешением 300 точек на дюйм. Было найдено, что |asym0| приблизительно равен |asym180| и |asym90| приблизительно равен |asym270|, и для ускорения вычислений возможно использовать горизонтальный ah и вертикальный av коэффициенты:
ah=|asym0|
av=|asym90|
Для изображений документов на романских или славянских языках с горизонтальными строками ah > av для 98% изображений. Следовательно, по значениям ah и av можно определить ориентацию изображения документа.
Первый шаг в определении ориентации документа - это выделение областей текста. В нашей реализации целесообразно использовать способ выделения областей текста, предложенный в патенте США №5767978 [4]. Если число текстовых блоков N меньше заданного порога Т, считается, что изображение не содержит текста и определение ориентации документа не выполняется. Иначе, если изображение содержит текстовый документ, следующим шагом является заливка нетекстовых областей белым цветом и преобразование RGB изображения в бинарное. Преобразование RGB изображения в бинарное состоит из двух шагов: 1) преобразование RGB изображения в черно-белое; 2) преобразование черно-белого изображения в бинарное.
В описанной реализации данного изобретения возможно преобразование RGB изображения в черно-белое путем усреднения суммы R, G, и В компонентов. В описанной реализации данного изобретения целесообразно выполнять преобразование черно-белого изображения в бинарное, используя алгоритм адаптивного порога скользящего среднего (см. J.R.Parker Algorithms for image processing and computer vision. Wiley Computer Publishers, New York, 1997 p.145-149 [5]). Этот алгоритм был разработан для изображений, содержащих текст, и дает хорошие результаты сегментации. Затем к бинарному изображению текста применяется алгоритм на основе отношения ah и av для определения ориентации портретная/ландшафтная. Заключительный шаг - это определение корректной ориентации, используя положительное значение asym.
Алгоритм вычисления асимметрии текста:
1) выполняют выделение текстовых блоков;
2) выполняют проверку, является ли число текстовых блоков меньше заданного порога;
3) в случае, если число текстовых блоков меньше заданного порога, определения ориентации документа не выполняют;
4) в случае, если число текстовых блоков больше заданного порога, выполняют заливку нетекстовых областей белым цветом;
5) выполняют преобразование RGB изображения в бинарное;
6) выполняют вычисление параметров асимметрии текста исходного документа (asym0) и текста документа, повернутого на 90 градусов (asym90);
7) выполняют вычисление горизонтального коэффициента (ah) и вертикального коэффициента (av);
8) выполняют проверку, является ли значение параметра асимметрии текста исходного документа (asym0) больше нуля, и горизонтальный коэффициент (ah) превышает вертикальный коэффициент (av);
9) в случае, если в результате проверки установлено, что значение параметра asym0 больше нуля и горизонтальный коэффициент ah превышает вертикальный коэффициент av, делают заключение, что документ имеет корректную ориентацию для текста на романских языках, а для текста на славянских языках осуществляют поворот изображения на угол 180°;
10) в случае, если в результате проверки установлено, что условие, касающееся того, что значение параметра asym0 больше нуля и горизонтальный коэффициент ah превышает вертикальный коэффициент av, не выполняется, то проверяют, является ли значение параметра asym0 меньше нуля и горизонтальный коэффициент ah превышает вертикальный коэффициент av;
11) в случае, если в результате проверки установлено, что значение параметра asym0 меньше нуля и горизонтальный коэффициент ah превышает вертикальный коэффициент av, делают заключение, что документ имеет корректную ориентацию для текста на славянских языках, а для текста на романских языках осуществляют поворот изображения на угол 180°;
12) в случае, если в результате проверки установлено, что условие, касающееся того, что значение параметра asym0 меньше нуля и горизонтальный коэффициент ah превышает вертикальный коэффициент av, не выполняется, проверяют, является ли значение параметра asym90 больше нуля и горизонтальный коэффициент ah меньше, чем вертикальный коэффициент av;
13) в случае, если условие, касающееся того, что значение параметра асимметрии текста исходного документа, повернутого на 90° т.е. asym90 больше нуля и горизонтальный коэффициент ah меньше, чем вертикальный коэффициент av, выполняется, то осуществляют поворот изображения на угол 90°;
14) иначе поворачивают изображение на угол 270° для корректной ориентации.
Фиг.9 представляет блок-схему алгоритма для определения ориентации документа. На этапе 901 выполняется выделение текстовых блоков. На этапе 902 выполняется проверка, является ли число текстовых блоков N меньше заданного порога Т. Если да, считается, что изображение не содержит текста и определение ориентации документа не выполняется. Если нет, то на этапе 903 выполняется заливка нетекстовых областей белым цветом. На этапе 904 выполняется преобразование RGB изображения в бинарное. На этапе 905 выполняется вычисление параметров asym0, asym90. На этапе 906 выполняется вычисление параметров ah, av. На этапе 907 выполняется проверка, является ли asym больше нуля и ah больше, чем av. Если да, то на этапе 908 документ имеет корректную ориентацию для романского языка, для славянского языка производится поворот изображения на 180° для корректной ориентации. Если нет, то на этапе 909 выполняется проверка, является ли asym меньше нуля и ah больше, чем av. Если да, то на этапе 910 документ имеет корректную ориентацию для славянского языка, для романского языка производится поворот изображения на 180° для корректной ориентации. Если нет, то на этапе 911 выполняется проверка, является ли asym90 больше нуля и ah меньше, чем av. Если да, то на этапе 912 производится поворот изображения на угол 90° для корректной ориентации. Если нет, тогда на этапе 913 производится поворот изображения на угол 270° для корректной ориентации.
Заявляемый способ обеспечения корректной ориентации входного документа может найти применение в различных сканирующих устройствах, в частности в таких устройствах, как МФУ. Способ может быть востребован также в системах распознавания текста в изображении документа как предварительный этап процесса распознавания. Этот способ применим также для корректного копирования перевернутых страниц из автоподатчика документов для дальнейшей обработки, например степлером, дыроколом или устройством для скрепления печатных блоков.