Способ бинаризации изображений символов на банкноте на основе гистограммы длины границ
METHOD FOR BINARISATION OF IMAGES OF SYMBOLS ON A BANKNOTE BASED ON HISTOGRAM OF LENGTH OF BOUNDARIES

Изобретение относится к способу бинаризации изображений символов на банкнотах и может быть использовано при проверке подлинности. Банкнота представляет собой защищенный документ, содержащий как изобразительную, так и текстовую информацию. Текстовая информация состоит из символов, представляющих собой буквы, цифры и некоторые знаки, такие как прямые и наклонные черты. В данном описании мы не будем относить к текстовой информации те символы, которые художественным образом встроены в рисунок на банкноте и, таким образом, являются неотъемлемой частью изобразительной информации.
Часть текстовой информации неизменно наносится на каждую банкноту определенного номинала и версии ее выпуска. К такой информации относятся, например, указание версии выпуска банкноты и места ее эмиссии, а также имя казначея национального банка. Кроме того, каждый экземпляр помечен уникальной строкой символов, которую принято называть серийным номером. Контроль неизменной текстовой информации важен для проверки подлинности банкнот. Однако, более важно обеспечить распознавание переменной текстовой информации. В современной технологии обработки банкнот необходимо вести учет движения индивидуальных экземпляров банкнот по цепочкам денежного оборота. Таким образом, для обработки банкнот необходимо оборудование, которое может распознавать символы на банкноте, находящиеся в серийном номере, а также в местах размещения неизменной текстовой информации. Распознавание символов на банкнотах представляет собой особую задачу, которая отличается от широко распространенных способов распознавания текстов, применяемых в офисной и библиотечной практике. Документы и печатные издания, за исключением небольшого числа особых видов документов (исторические документы, древняя литература), имеют высокое качество печати. Как правило, они напечатаны черным цветом на белом фоне, а загрязнения бумаги и повреждения красочного слоя практически отсутствуют. При сканировании таких документов получается контрастное и целостное изображение каждого символа. Разрешение сканирования, используемое для документов и печатных изданий, как правило, составляет 300 точек на дюйм или больше.
В отличие от документов и печатных изданий, банкноты постоянно находятся в обращении, что приводит к постепенному истиранию красочного слоя, запятныванию и общему загрязнению бумаги. В результате, контрастность и целостность изображения символа на банкнотах могут очень ощутимо снижаться. Ситуация также осложняется тем, что серийный номер или неизменный текст далеко не всегда печатается на белом участке банкноты. Во многих случаях, он наносится на ранее запечатанную область бумаги. Поэтому, даже на новых банкнотах, фон символа часто уже содержит дополнительное изображение, мешающее распознаванию.
Качество сканирования банкнот в машинах для обработки наличности значительно уступает качеству сканирования обычных документов, поскольку банкнота перемещается в машине на высокой скорости (до 10 километров в час). Это приводит к необходимости использовать невысокое разрешение сканирования, не превышающее 200 точек на дюйм.
За счет высокой скорости перемещения банкноты в машине, к быстродействию распознавания символов на банкноте предъявляются высокие требования. Обычно, допустимым является время распознавания строки серийного номера в пределах нескольких миллисекунд. Это время примерно сопоставимо с временем распознавания напечатанного слова той же длины в современных способах распознавания обычных документов, выполняемых на высокопроизводительных процессорах. Однако, применение высокопроизводительных процессоров в большинстве машин для обработки банкнот невозможно по экономическим причинам. Те же виды процессоров, которые экономически оправданы для применения в машинах для обработки банкнот, имеют в 10 и более раз низкую производительность, чем производительность процессора рабочей станции с архитектурой IBM PC. В связи с этим, вычислительная сложность распознавания символов на банкноте должна быть снижена в сравнении со способами распознавания, применяемыми для распознавания обычных документов.
Способы распознавания символов на банкнотах можно условно разделить на те, в которых используется предварительная бинаризация полутонового изображения, и те, где алгоритм распознавания напрямую обращается к полутоновому изображению. Примером алгоритма распознавания, не требующего бинаризации, можно назвать метод сверточной нейронной сети, а также метод гистограммы градиентов. В способах с бинаризацией сначала отделяют пиксели, принадлежащие значимому объекту на изображении, от пикселей фона. Бинаризация представляет собой метод выделения значимого объекта в полутоновом изображении, такого, как символ, основываясь на яркости пикселей. Обычно, результат бинаризации представляется как изображение с двумя градациями яркости, где пиксели фона представляются белыми, а пиксели объекта имеют черный цвет. Алгоритм распознавания работает с бинаризованным изображением. К таким алгоритмам распознавания относятся, например, морфологические алгоритмы. Эти алгоритмы анализируют бинаризованное изображение символа на предмет наличия и расположения определенных формных элементов символа, таких, как прямые линии, дуги, перекрестья символа, а также элементов фона в виде «островов» и «полуостровов».
Пиксели объекта часто называют пикселями переднего плана изображения. В рамках данного описания, в качестве объекта рассматривается символ, поэтому, пиксели переднего плана изображения называются пикселями, отнесенными к символу. Необходимо учитывать, что качество бинаризации может быть различным. При плохом качестве, к пикселям символа, в ходе бинаризации, могут ошибочно быть отнесены пиксели, которые, в действительности, не принадлежат символу и являются частью фона либо постороннего объекта на изображении. Аналогично, пиксели, которые, в действительности, относятся к символу, могут быть ошибочно отнесены к фону. Как показывает опыт, невозможно создать совершенно безошибочный способ бинаризации, поэтому указанные ошибки, так или иначе, всегда имеют место.
В целом, алгоритмы, работающие с бинаризованным изображением, требуют меньших вычислительных ресурсов и выполняются быстрее алгоритмов, которые напрямую обращаются к полутоновому изображению. Поэтому, бинаризацию часто используют в машинах для обработки банкнот. В то же время, бинаризация, сама по себе, требует дополнительных затрат процессорного времени. При неудачном выполнении, бинаризация может ухудшить качество изображения символа до такой степени, что его распознавание становится невозможным. В таких случаях, изображение символа состоит из отдельных разделенных сегментов с потерей определенных частей символа, либо же, наоборот, фрагменты фона соединяются с символом и нарушают структуру его составных частей. Еще один вид ошибки, вносимой при бинаризации, состоит в проявлении изолированных фрагментов фона в виде точек и линий, которые ошибочно воспринимаются алгоритмом распознавания как элементы символа.
Таким образом, способ бинаризации для применения в машинах для обработки банкнот должен обладать определенным набором свойств. Во-первых, он должен быстро выполняться, так чтобы позволить всему процессу распознавания уложиться в отведенное под него короткое время. Во-вторых, символ должен передаваться в бинаризованное изображение без потерь частей и разрывов линий. В-третьих, способ бинаризации должен надежно блокировать проявление пикселей фона в бинаризованном изображении в качестве пикселей символа, несмотря на то, что сам фон может быть высококонтрастным изображением, а яркость отдельных пикселей фона может вплотную приближаться к яркости пикселей символа.
Полутоновый цифровой образ банкноты, получаемый в результате сканирования в машине для обработки банкнот, обладает некоторыми особенностями, которые несколько облегчают задачу бинаризации. При сканировании, засветка поверхности банкноты в машине для обработки банкнот является весьма равномерной, поэтому в цифровом образе не возникает совместного изменения яркости частей символа и частей фона, обуславливаемого неравномерностью засветки. При бинаризации изображения символа нет необходимости проводить компенсацию неравномерности засветки, которая создает существенные сложности в ходе решения родственных технических задач, таких, как распознавание номерных знаков автомобилей.
Кроме того, за редчайшими исключениями, интервал яркостей пикселей фона на банкноте в окрестности символа не перекрывается с интервалом яркостей пикселей символа. В большинстве случаев, эти интервалы соприкасаются в разделяющей точке на шкале яркостей, по одну сторону которой находятся значения яркости пикселей символа, а по другую располагаются яркости пикселей фона. Это позволяет разделять пиксели фона и пиксели символа при помощи единого, так называемого глобального, порога бинаризации, который равняется яркости в указанной разделяющей точке. Все пиксели, яркость которых меньше яркости порога бинаризации, относят к символу, а остальные пиксели относят к фону. Возможность применения глобального порога бинаризации значительно ускоряет процесс бинаризации, поскольку порог должен быть вычислен только один раз и далее многократно применяется к пикселям участка цифрового образа банкноты, где расположен символ. В то же время, выбор порога бинаризации является ответственной задачей, от которой, главным образом, зависит качество бинаризации символов на банкноте.
Для минимизации вычислительных затрат, бинаризацию и распознавание проводят для заранее известного участка цифрового образа банкноты, на котором находится требуемый символ или группа символов. Как правило, перед распознаванием символов, цифровой образ анализируется для определения валюты, номинала, версии выпуска банкноты и ее ориентации при прохождении через машину для обработки банкнот. Способы, применяемые на практике для подобного анализа, хорошо известны специалистам. По результатам этого анализа, на основе известного изобразительного дизайна банкноты, можно с высокой точностью выделить участок цифрового образа для распознавания символа или символов.
Печатные символы на банкноте, как правило, обладают высокой оптической плотностью красочного слоя и четкими границами. За счет местной нестабильности краскопередачи в печатном процессе, оптическая плотность в пределах символа изменяется, как правило, на небольшую величину, не превышающую нескольких процентов. Кроме того, по мере износа банкноты, оптическая плотность красочного слоя становится различной в различных точках символа. Указанные различия передаются в цифровой образ банкноты в виде неизбежного разброса яркости пикселей, относящихся к символу.
Фон, на котором напечатан символ, может быть незапечатанной поверхностью бумаги либо печатным рисунком. Для банкнот на полимерной основе фон часто выполняют в виде сплошной запечатки белой краской. Яркость пикселей фона в цифровом образе непостоянна, даже в том случае, когда в фоне отсутствует печатный рисунок. Локальная отражающая способность поверхности бумаги непостоянна и определяется ее волокнистой структурой. Сплошная запечатка белой краской также дает неравномерность яркости из-за локальной неравномерности толщины красочного слоя. Дополнительный вклад в неоднородность яркости как печатного символа, так и фона, вносят шумы фотоприемного датчика и электронной аппаратуры, используемой для регистрации цифрового образа.
За счет размытия в оптической системе фотоприемного датчика, применяемого для получения цифрового образа, на цифровом образе банкноты образуется полоса неопределенности, окружающая линии каждого символа. Пиксели в полосе неопределенности имеют яркость, которая складывается из яркости пограничной части символа и яркости фона. Важно, что вклад каждой из этих яркостей зависит от массы случайных факторов, таких, как смещение поверхности банкноты из точки наилучшей фокусировки оптической системы фотоприемного датчика, а также расстояние между границей пикселя и ближайшей к нему границей символа. Поэтому, для пикселей в полосе неопределенности, соотношение между вкладами яркости символа и яркости фона не может быть достоверно определено. Это создает трудно разрешаемую задачу отнесения каждого пикселя в зоне неопределенности к пикселям символа или к пикселям фона.
Рассмотрим, как поэтапно изменяется бинаризованное изображение при последовательном увеличении глобального порога бинаризации. На первом этапе, при очень низком значении глобального порога, яркость практически всех пикселей в цифровом образе оказывается выше значения порога. В результате, бинаризованное изображение состоит почти исключительно из белых пикселей. По мере роста порога, он оказывается выше наиболее темных пикселей символа. На этом, втором этапе, в бинаризованном изображении начинают проявляться разрозненные черные пиксели, относящиеся к символу. В ходе дальнейшего увеличения порога, на третьем этапе, разрозненные черные пиксели объединяются в кластеры, которые представляют собой части символа, разделенные разрывами, состоящими из белых пикселей. Далее, эти разрывы сокращаются, и при определенном значении порога, которое мы будем называть минимально допустимым, разрывы исчезают практически полностью. Как на втором, так и на третьем этапе не происходит одномоментного проявления символа в бинаризованном изображении, так как пиксели символа имеют различные уровни яркости и начинают передаваться в бинаризованное изображение при различных значениях порога.
В момент практически полного исчезновения разрывов, при так называемом минимально допустимом значении порога, символ в бинаризованном изображении состоит из непрерывных линий, соответствующих линиям исходного символа на банкноте. Возможные случайные единичные разрывы не нарушают возможности распознавания символов. Начертание символа в бинаризованном изображении, в целом, соответствует исходному, но толщина линий оказывается существенно меньше.
В ходе четвертого этапа, последующее увеличение порога ведет к тому, что пиксели в полосе неопределенности постепенно переходят из фона в символ, что сопровождается ростом толщины линий с сохранением начертания. Имеется значение порога, которое мы будем называть наилучшим, при котором средняя толщина линий символа в бинаризованном изображении равна средней толщине линий исходного символа. При увеличении порога сверх наилучшего продолжается увеличение толщины линий с сохранением начертания. Существует максимально допустимое значение порога, при котором начертание символа еще сохраняется, несмотря на то, что толщина линий символа в бинаризованном изображении превосходит толщину линий исходного символа. На пятом этапе, при увеличении порога сверх максимально допустимого, некоторые пиксели фона в цифровом образе оказываются ниже порога и проявляются в бинаризованном изображении как черные пиксели. В результате, нарушается начертание символа и возникают шумовые кластеры черных пикселей в местах пробелов. На шестом этапе, при очень больших значениях порога шумовые кластеры сливаются с линиями символа. На седьмом этапе шумовые кластеры и линии символа сливаются друг с другом, образуя сплошное черное заполнение бинаризованного изображения с белыми включениями. На восьмом этапе, при наибольшем значении порога, белые включения исчезают, и все бинаризованное изображение состоит из черных пикселей. На этапах с пятого по седьмой не происходит одномоментного перехода всех пикселей фона в пиксели символа, поскольку пиксели фона, даже при отсутствии рисунка фона, имеют различные уровни яркости и переходят в пиксели символа в бинаризованном изображении при различных значениях порога.
Для специалиста очевидно, что для гарантированного распознавания символа, в ходе бинаризации требуется сохранить его начертание. Это возможно, когда порог бинаризации находится между минимально допустимым и максимально допустимым значениями, что соответствует четвертому этапу увеличения порога.
Чтобы получить наилучшие условия распознавания символа нужно, чтобы порог бинаризации был равен наилучшему значению. Тогда, в бинаризованном изображении черные пиксели наиболее точно отражают изображение исходного символа на банкноте, с сохранением всех формных элементов символа и толщины его линий. Если выбран порог между минимально допустимым и наилучшим значениями, то пиксели в полосе неопределенности, которые фактически относятся к символу, могут быть ошибочно отнесены к фону. Если выбран порог между наилучшим и максимально допустимым значениями, то, наоборот, пиксели в полосе неопределенности, относящиеся к фону, могут быть ошибочно отнесены к символу. Неправильный выбор порога приводит к утонению или, наоборот, к утолщению линий символа, а также к искажению мелких формных элементов, таких, как засечки на концах линий. В некоторых шрифтах, линии очень близко подходят друг к другу, образуя узкий зазор. Вблизи максимально допустимого порога, за счет избыточного увеличения толщины линий, линии могут сомкнуться, так что зазор может исчезнуть. Перечисленные искажения создают сложности для работы алгоритма распознавания, использующего бинаризованное изображение.
Таким образом, выбор глобального порога является ответственной задачей. Можно говорить о грубом выборе порога, когда обеспечивается его значение в интервале между минимально допустимым и максимально допустимым. Однако, для наилучшего качества распознавания символа, требуется точный выбор порога, когда порог получает значение, близкое к наилучшему.
Широко известным способом выбора глобального порога бинаризации является так называемый метод Отсу (в литературе также встречается написание Otsu или Отцу). В этом методе, глобальный порог определяется исключительно на основе анализа гистограммы яркостей изображения. Метод Отсу основан на предположении, что гистограмма яркости представляет собой бимодальное статистическое распределение, в котором одна мода относится к символу, а другая мода относится к фону. В таком предположении, оптимальный порог бинаризации должен располагаться на границе этих мод. В статистических терминах, метод Отсу разделяет гистограмму яркости изображения значением глобального порога на две части, называемые классами, таким образом, что межклассовая дисперсия оказывается максимальной. Метод Отсу использует перебор всех значений яркости в гистограмме и, в исходной реализации, требует существенных затрат процессорного времени. Однако, для него известны усовершенствования, которые используют рекуррентные формулы и уменьшают общее количество вычислений. Поэтому, общепринятая реализация метода Отсу обладает умеренной вычислительной сложностью.
В применении к символам на банкнотах, метод Отсу успешно обеспечивает грубый выбор порога, если фон символа является светлым и равномерным либо слабоконтрастным. В таких случаях, гистограмма полутонового участка цифрового образа, подлежащего распознаванию, имеет явный бимодальный характер. Поэтому, глобальный порог бинаризации, находимый по методу Отсу, устойчиво разделяет интервалы яркостей пикселей, относящихся к символу и относящихся к фону. Однако, когда фон является высококонтрастным изображением, бимодальный характер гистограммы нарушается. Для такой гистограммы, метод Отсу очень часто находит неверный порог бинаризации, который лежит вне интервала между наименьшим и наибольшим допустимыми значениями. Часто гистограмма оказывается многомодальной, с числом мод более двух. В случае многомодальной гистограммы, фону может соответствовать две или большее количество мод гистограммы. В этом случае, найденный порог зачастую разделяет пиксели символа и часть пикселей фона от другой части пикселей фона вблизи точки, где моды фона граничат друг с другом. Это приводит к слиянию символа с частью пикселей фона.
В более сложном случае гистограмма имеет одну моду, где реальная разделяющая точка, отделяющая интервалы яркостей символа и фона, находится в пределах одной моды. Как правило, это происходит, если статистические плотности распределения как пикселей символа, так и пикселей фона в гистограмме вблизи разделяющей точки оказываются достаточно высокими. Кроме того, возможен случай, когда гистограмма, за счет бимодального распределения яркости пикселей фона, также является бимодальной, но разделяющая точка находится в пределах одной моды. Для такого распределения, метод Отсу не всегда гарантирует даже грубый выбор порога.
Известен патент US 5956421 (опубл. 21.09.1999, МПК G06K 9/38), далее называемый в этом описании методом Танаки. В методе Танаки, для нахождения глобального порога, как и в методе Отсу, используются только данные гистограммы яркости. Для поиска порога используется процесс последовательного приближения, на каждом шаге которого вычисляют новое положение рабочего отрезка уровней гистограммы. Первоначально, рабочий отрезок охватывает всю гистограмму. На первом шаге, вычисляют математическое ожидание и параметр асимметрии распределения на этом отрезке. Параметр асимметрии представляет собой отношение третьего и второго центральных статистических моментов. Если параметр асимметрии отрицателен, то верхний конец отрезка устанавливают в ранее вычисленную точку математического ожидания. Если параметр асимметрии положителен, то нижний конец отрезка устанавливают в ранее вычисленную точку математического ожидания. Далее, шаг повторяют. На каждом шаге, происходит уменьшение длины отрезка. Процесс останавливают, как только модуль параметра асимметрии становится меньше единицы. Математическое ожидание, полученное на последнем отрезке, используют в качестве глобального порога бинаризации. В случае близкого уровня яркости символа и фона, а, также, при контрастном фоне, метод Танаки находит значительно лучшее положение разделяющей точки, чем метод Отсу. Он гарантирует грубое определение порога практически при любом фоне. Однако, метод Танаки обладает высокой вычислительной сложностью, так как на каждом шаге приходится вычислять, по всем уровням на рабочем отрезке, не только математическое ожидание, но также суммы квадратов и кубов отклонения от этого математического ожидания. В известном патенте описывается аппаратный ускоритель для реализации метода Танаки, призванный обеспечить приемлемое быстродействие.
К сожалению, ни метод Отсу, ни метод Танаки не позволяют провести точное определение глобального порога. В целом, эта проблема характерна для тех способов, где, в качестве данных для нахождения глобального порога, используется исключительно гистограмма яркости. Поскольку для пикселей в полосе неопределенности соотношение между вкладами яркости символа и яркости фона не известно достоверно, то отсутствует возможность выработать критерий, по которому можно разделить в гистограмме яркости те уровни, которые в этой полосе относятся к пикселям фона и пикселям символа. Различия в яркости соседних участков фона создают дополнительные сложности в разделении полосы неопределенности. Чаще всего, указанная проблема приводит к неконтролируемому изменению толщины линий символа в бинаризованном изображении в зависимости от яркости и контрастности фона и состояния сканирующего механизма в конкретный момент сканирования, а также иных случайных факторов.
Таким образом, использование одной только гистограммы яркости участка цифрового изображения не позволяет надежно находить наилучшее значение глобального порога бинаризации для многих случаев практического применения.
В научной литературе известны так называемые адаптивные методы бинаризации, в которых вместо использования глобального порога применяется индивидуальное значение порога, отдельно вычисляемое для каждого пикселя. В качестве примеров можно назвать адаптивный метод Отсу, методы Брэдли, Ниблэка, а также Сауволы. В целом, адаптивный метод анализирует окрестность для каждого пиксела, и по значениям яркости пикселей в этой окрестности определяет требуемый индивидуальный порог. В адаптивном методе Отсу строится гистограмма яркости в заданной окрестности пикселя, и по ней, аналогично обычному методу Отсу, определяется разделяющая точка. Эта разделяющая точка используется в качестве индивидуального порога для пикселя. В методе Брэдли вычисляется средний уровень яркости в пределах окрестности пикселя, и далее этот средний уровень домножается на некоторый настроечный коэффициент. Значение настроечного коэффициента выбирается несколько меньшим единицы. В результате домножения, получают индивидуальный порог для пикселя. В методе Ниблэка, для получения индивидуального порога, из среднего уровня яркости вычитается дисперсия яркости в окрестности пикселя, домноженная на настроечный коэффициент. В методе Сауволы, средний уровень яркости домножается на переменный коэффициент, который линейно зависит от дисперсии яркости в окрестности пикселя. Специалистам известны дальнейшие развития методов Сауволы и Ниблэка, использующие более сложные функциональные зависимости для вычисления индивидуального порога.
Методы адаптивной бинаризации учитывают состояние ближайших пикселей фона вокруг символа и, в определенной мере, снижают влияние яркости и контрастности фона на выделение пикселей символа в полосе неопределенности. Главным недостатком всех адаптивных методов бинаризации является их повышенная вычислительная сложность. Из перечисленных здесь, только метод Брэдли обладает вычислительной сложностью и быстродействием, приемлемыми для применения в машинах для обработки банкнот. Все остальные адаптивные методы оказываются во много раз медленнее метода Брэдли. По качеству отделения высококонтрастного фона от символа, метод Сауволы показывает достаточно хорошие результаты. К сожалению, он же оказывается и наиболее медленным. Метод Брэдли разрешает часть сложностей, вызываемых наличием высококонтрастного фона. Однако, при его использовании, в результате бинаризации, на больших областях фона появляются случайно расположенные кластеры черных пикселей, а толщина линий символа уменьшается в местах их пересечений. Таким образом, известные адаптивные алгоритмы оказываются малопригодными для бинаризации символов на банкноте.
Полутоновые изображения символов характеризуются тем, что пиксели символа имеют схожие и низкие значения яркости. Символы как европейских, так и азиатских алфавитов состоят из линий, длина которых во много раз превосходит толщину. Поэтому, пиксели символа соседствуют друг с другом, образуя вытянутые кластеры. Эти вытянутые кластеры содержат значительное количество пикселей и соответствуют линиям символа. Наличие крупных вытянутых кластеров соседствующих пикселей, имеющих близкие и невысокие значения яркости, отличает символы от других элементов изображения. Фон образует кластеры высокой яркости. Шумовые элементы, вызванные волокнистой структурой и загрязнениями поверхности бумаги, образуют темные кластеры небольшого размера. Графические элементы, не состоящие из линий, образуют темные кластеры, не имеющие вытянутой формы. Перечисленные здесь свойства кластеризации пикселей, образующих символы, используют в качестве дополнительной информации для нахождения оптимального глобального порога. Так, известен патент США US 9367899 (опубл. 14.06.2016, МПК G06K 9/00), в котором проводят пробную бинаризацию цифрового образа при различных значениях порога, и анализируют полученный результат бинаризации. В каждом из полученных бинарных образов, проводят поиск кластеров черных пикселей, измеряют их геометрические параметры, и на основе этих параметров относят кластеры либо к символам, либо к шумовым элементам. Для каждого пробного значения порога, вычисляют отношение между количеством шумовых кластеров и кластеров символов. Оптимальным считают порог, при котором это отношение минимально.
В соответствии с ранее описанными этапами изменения бинаризованного изображения, шумовые кластеры в большом количестве присутствуют в этом изображении на втором, третьем, и пятом этапах. На четвертом этапе, соответствующем грубому определению порога, шумовые кластеры отсутствуют или же их количество минимально. Таким образом, оптимальный порог, определяемый в известном патенте, соответствует четвертому этапу.
Известный способ отличается большой вычислительной сложностью за счет многократного повторения бинаризации и выполнения процедур поиска и оценки кластеров на многочисленных пробных бинарных изображениях. Так, в практической реализации способа создается 16 бинарных изображений, по одному для 16 пробных значений порога. В связи с высокой вычислительной сложностью, он мало пригоден для распознавания символов на банкнотах. Находимый им порог гарантированно находится в интервале между наименьшим и наибольшим допустимыми значениями. Однако, указанный способ не выполняет точного определения порога, по крайней мере, в реализациях, описанных в патенте. В этом отношении он показывает результат, сходный с результатом метода Танаки.
Известен ряд способов бинаризации изображений символов, основанных на сравнении яркостей соседних пикселей и исследовании так называемых связанных компонентов в исходном цифровом образе, состоящих из соседствующих пикселей, близких по яркости.
В патенте США US 10049291 (опубл. 15.02.2018, МПК G06K 9/34) изображение разбивают на связанные компоненты, состоящие из соседствующих пикселей одного и того же уровня яркости. Далее, строят иерархический граф соединения связанных компонентов друг с другом по принципу касания пикселей, относящихся к различным связанным компонентам. Затем, анализируют соотношения площадей соединенных связанных компонентов и получают так называемый параметр резкости. Параметр резкости, а также параметры контраста и площади, позволяют отличить связанные компоненты, которые вместе составляют символ, от шумовых и фоновых связанных компонентов. В результате, выбирается порог бинаризации, обеспечивающий полную передачу символа в бинарное изображение. За счет использования иерархического графа связи, в бинарное изображение передаются только связанные компоненты, отнесенные к символу, не передаются шумовые кластеры, не связанные с символом. Описанный способ обеспечивает надежное отделение символа от фона, но обладает повышенной вычислительной сложностью. Эта сложность связана, прежде всего, с затратами на прослеживание цепочек соседствующих пикселей в отдельных связанных компонентах, на построение иерархического графа соединения связанных компонентов, и на обсчет характеристик соединения между связанными компонентами. Чем сложнее оказывается граф связи и чем больше связанных компонентов в изображении, тем дольше длится бинаризация. Это не позволяет удовлетворить жесткие требования к быстродействию при обработке банкнот. Сказанное можно отнести в целом к способам, в которых используют построение иерархических графов связанных компонентов.
Как и все другие способы, описанные ранее, этот способ не содержит критерия, по которому можно выбрать порог, который наилучшим образом разделяет пиксели, находящиеся в полосе неопределенности. Параметр резкости позволяет определить принадлежность к линии, но не толщину этой линии. Таким образом, при бинаризации не гарантируется точная передача мелких формных элементов и толщины линий исходного символа.
В случае символов на банкнотах, всегда известен шрифт, которым напечатаны символы, а, следовательно, заранее известна средняя толщина линий символов. Это дает возможность провести поиск наилучшего порога бинаризации, обеспечивающего заранее известную среднюю толщину символов. Это позволяет исключить, либо существенно уменьшить влияние зоны неопределенности на точность воспроизведения символа в бинаризованном изображении.
Для нахождения наилучшего порога можно было бы оценивать толщину линий, получаемую при использовании того или иного порога бинаризации. В качестве наилучшего значения следовало бы выбирать тот порог бинаризации, при котором средняя толщина линий в бинаризованном изображении соответствует заранее известной. Это можно было бы сделать, например, с использованием способа, описанного в упомянутом ранее патенте US 9367899. Для этого, нужно было бы обеспечить измерение толщины линий в кластерах на пробных бинаризованных образах, и сравнение измеренной толщины с заранее известной величиной. Тот порог, при котором почти все кластеры бинаризованного изображения имеют заранее известную среднюю толщину линий, был бы близок к наилучшему. К сожалению, за счет вычислительной сложности, указанной ранее, подобное решение не подходит для распознавания символов на банкнотах.
Патент US 9367899 был выбран в качестве прототипа заявленного изобретения. Техническим результатом заявленного изобретения является повышение быстродействия распознавания символов банкноты.
Этот результат достигается в способе бинаризации изображений символов на банкноте, в котором получают полутоновое изображение участка банкноты, содержащего, по меньшей мере, один символ, подлежащий бинаризации, в котором каждый пиксель характеризуется уровнем яркости, и определяют итоговый порог бинаризации и формируют итоговый результат бинаризации, для чего применяют пороговую процедуру с использованием итогового порога бинаризации где пороговая процедура является процессом формирования двухуровневого изображения, в котором каждый пиксель соответствует пикселю полутонового изображения, и имеет один из двух возможных уровней яркости, назначаемый на основе сравнения яркости соответствующего пикселя полутонового изображения с заданным порогом бинаризации, при этом для определения итогового порога бинаризации строят гистограмму длины границ указанного полутонового изображения для чего задают упорядоченный набор возрастающих значений яркости, возможных в полутоновом изображении, и, для всех значений яркости в указанном наборе, начиная со значения, следующего за наименьшим, задают значение соответствующей ячейки гистограммы длины границ как приращение длины границ двухуровневого изображения, получаемого в результате выполнения пороговой процедуры, соответствующее приращению порога, применяемого в пороговой процедуре, до рассматриваемого значения яркости от предшествующего ему значения яркости в указанном наборе, причем длина границ двухуровневого изображения подсчитывается как сумма длин отрезков, каждый из которых представляет собой границу двух граничащих пикселей с различными уровнями яркости, плюс дополнительная составляющая для учета длины тех сторон пикселей, которые находятся на краю изображения, и по заданному критерию анализируют указанную гистограмму длины границ для нахождения итогового порога бинаризации, при использовании которого результат бинаризации содержит непрерывные линии, содержащиеся в полутоновом изображении участка банкноты.
Получение полутонового изображения участка банкноты, содержащего символ, является типовой операцией обработки банкнот и хорошо известно специалистам. Применение пороговой процедуры с использованием заданного глобального порога для получения итогового результата бинаризации, также является типовой операцией, применяемой в способах бинаризации, опирающихся на глобальный порог. Новизна и изобретательский уровень заявленного изобретения обеспечиваются признаками, характеризующими то, каким образом в нем определяется итоговый порог бинаризации.
В прототипе, для определения итогового порога бинаризации, производят множество пробных бинаризаций с пробными значениями порога, анализируют результаты пробных бинаризаций, и, по результатам анализа выбирают итоговый порог. В заявленном изобретении также рассматривается набор возможных значений для порога, однако, для выбора из них итогового порога не требуется выполнять множество пробных бинаризаций. Вместо этого, для анализа качества бинаризации и выбора подходящего итогового порога используют гистограмму длины границ. Рассмотрим гистограмму длины границ более подробно.
Длина границ в двухуровневом бинаризованном изображении есть сумма длин отрезков, каждый из которых представляет собой границу двух граничащих пикселей с различными уровнями яркости. Если два граничащих пикселя в бинаризованном изображении имеют одинаковое значение яркости, то их пограничный отрезок не входит в длину границ. Гистограмма длины границ показывает, каким образом изменяется длина границ при пошаговом нарастании порога бинаризации, который используется для получения бинаризованного изображения.
При рассмотрении двух соседних пикселей полутонового изображения, имеется простой способ определить, при каких значениях порога бинаризации пограничный отрезок между этими пикселями будет включен в длину границ бинаризованного изображения. Для каждого из пограничных отрезков между двумя пикселями полутонового изображения, если порог бинаризации находится в интервале между значениями яркостей этих пикселей, то в результате бинаризации будут получены пиксели с разными уровнями яркости. В этом случае, их пограничный отрезок входит в длину границ. Если порог бинаризации имеет значение ниже указанного интервала либо выше указанного интервала, то в результате бинаризации будут получены пиксели с одинаковыми уровнями яркости. В этом случае, их пограничный отрезок не входит в длину границ.
Включение концов интервала или их исключение зависит от того, как именно определена операция сравнения в конкретной реализации пороговой процедуры.
Когда некоторые стороны части пикселей символа оказываются на границе участка банкноты, они должны быть рассмотрены в особом порядке. Они не являются пограничными отрезками между пикселями изображения участка банкноты. Для учета вклада этих сторон в длину границ в заявленном способе предусматривается дополнительная составляющая длины границ. В частности, для темных пикселей символа и светлых пикселей фона, дополнительная составляющая длины границ двухуровневого изображения представляет собой сумму длин тех сторон пикселей двухуровневого изображения с низшим уровнем яркости, которые находятся на краю изображения.
Рассмотрим, в самом общем виде, каким образом может быть построена гистограмма длины границ. В ходе последовательного нарастания порога, пограничный отрезок пары граничащих пикселей будет включен в длину границ бинаризованного изображения при прохождении наименьшего значения яркости в рассматриваемой паре граничащих пикселей в полутоновом изображении. Затем, он будет исключен из длины границ при прохождении наибольшего значения яркости в рассматриваемой паре. В гистограмме длины границ, этим значениям яркости пикселей соответствуют две ячейки, в одной из которых рассматриваемая пара пикселей обеспечивает прибавление длины отрезка, а в другой - вычитание длины отрезка. Таким образом, рассмотрев все пограничные отрезки между граничащими пикселями и проведя увеличение и уменьшение соответствующих им ячеек, можно построить гистограмму длины границ, не выполняя пробную бинаризацию.
Можно легко увидеть, что количество пограничных отрезков между граничащими пикселями в двухуровневом изображении, подлежащих анализу, несколько меньше удвоенного числа пикселей. Для определения наибольшего и наименьшего значения яркости в паре пикселей нужно лишь несколько простых арифметических операций. Более того, в большинстве современных процессоров, операции вычисления минимума и максимума являются атомарными процессорными командами. Все это обуславливает низкую вычислительную сложность и быстроту построения гистограммы длины границ. Как будет показано далее, ее можно построить, например, сравнивая яркость каждого пикселя участка банкноты с яркостями четырех соседних граничащих с ним пикселей, хотя, возможно, существуют и другие способы с еще более низкими вычислительными затратами. Таким образом, построение гистограммы длины границ требует четырех операций сравнения на каждый пиксель. Вполне возможно, что существует еще более быстрый, но пока неизвестный, способ построения гистограммы длины границ.
Дальнейшая обработка данных в заявленном изобретении производится на основе гистограммы длины границ результата бинаризации. Сложность этой обработки не зависит от числа пикселей и определяется только количеством уровней гистограммы. В соответствии с критериями анализа гистограммы длины границ, приведенными далее, для каждого уровня гистограммы необходимо всего лишь несколько простых арифметических операций. Практически необходимое количество уровней гистограммы не превышает 256 и, как показывает практика, может быть уменьшено до 64. Поэтому, вычислительная сложность критерия анализа гистограммы длины границ оказывается ниже, чем вычислительная сложность построения этой гистограммы.
В прототипе при пробной бинаризации для каждого пробного значения порога нужно произвести сравнение яркости каждого пикселя с значением пробного порога. Кроме того, в прототипе для поиска кластеров в каждом пробном бинаризованном изображении необходимо сравнивать значение яркости каждого пикселя с, как минимум, четырьмя соседними. Таким образом, в прототипе на каждый пиксель приходится количество сравнений, равное числу пробных значений порога, помноженному, как минимум, на 5. На практике, рекомендуется не менее 16 пробных значений порога, из-за чего в прототипе требуется количество сравнений на один пиксель, которое на порядок превосходит количество сравнений, требуемое в заявленном изобретении. К этому нужно добавить процедуры анализа кластеров, сложность которых достаточно тяжело оценить, но которые дополнительно увеличивают вычислительную сложность прототипа.
Таким образом, вычислительная сложность заявленного изобретения оказывается существенно ниже вычислительной сложности прототипа. Это обеспечивает достижение технического результата.
В то же время, заявленное изобретение обеспечивает, по меньшей мере, такую же точность определения итогового порога бинаризации, какую обеспечивает прототип. В наиболее общем виде, как заявленное изобретение, так и прототип гарантируют, что итоговый порог бинаризации будет находиться между минимальным и максимальным допустимыми порогами. В заявленном изобретении, для этого используется критерий анализа гистограммы длины границ.
Для пояснения использования гистограммы длины границ при нахождении итогового порога бинаризации рассмотрим поэтапное изменение длины границ бинаризованного изображения по мере последовательного увеличения порога бинаризации. На первом этапе, черные пиксели в бинаризованном изображении отсутствуют, так что длина их границ оказывается равной нулю. При появлении разрозненных пикселей на втором этапе, длина границ начинает резко расти. Без нарушения общности, мы будем рассматривать квадратные пиксели, а в качестве единиц длины границы будем использовать длину стороны пикселя. У каждого квадратного пикселя четыре равные стороны, поэтому, при его проявлении в бинаризованном изображении длина границ изображения вырастает сразу на 4 единицы. На третьем этапе, разрозненные пиксели объединяются в мелкие кластеры. Прибавление нового пикселя к кластеру увеличивает длину границ менее чем на 4 единицы, однако, в целом темп роста длины границ остается высоким.
Ситуация меняется на четвертом этапе, на котором символ в бинаризованном изображении состоит из безразрывных линий. С ростом порога растет толщина линий. Однако, длина границ линий растет только за счет их концов. На протяженных участках линий длина границ практически не меняется. Соответственно, на четвертом этапе рост границ бинаризованного изображения очень мал. Для замкнутых символов, где линии не имеют концов, рост границ практически отсутствует. На пятом этапе, с проявлением шумовых разрозненных пикселей фона в бинаризованном изображении, вновь начинается резкий рост длины границ с темпом до 4 единиц на один пиксель.
Суммируя описанное здесь, можно сказать, что на втором, третьем и пятом этапах, по крайней мере часть ячеек гистограммы длины границ содержит значительные положительные значения, связанные с появлением разрозненных пикселей и ростом небольших кластеров. Напротив, средние значения ячеек гистограммы длины границ на четвертом этапе очень малы, поскольку рост границ мал или практически отсутствует. Это явное противопоставление позволяет реализовать различные критерии, находящие порог бинаризации на допустимом отрезке уровней гистограммы от минимально допустимого до максимально допустимого, соответствующие четвертому этапу. Любое значение порога бинаризации в пределах допустимого отрезка обеспечивает передачу символа в бинаризованное изображение с сохранением его формы. Конкретное значение порога бинаризации может быть найдено внутри допустимого отрезка с использованием дополнительных соображений. Самым простым решением может быть выбор порога в середине допустимого отрезка. Основную разницу между прототипом и заявленным изобретением можно описать следующим образом. В прототипе, проводится многократная пробная бинаризация с различными значениями порога, результаты ее анализируется и по результатам анализа выбирается итоговый порог бинаризации. При анализе производится выделение и сравнение геометрических признаков кластеров, с целью определения того порога бинаризации, при котором кластеры, почти исключительно, будут представлять собой бинаризованные изображения символов. В заявленном изобретении, гистограмма длины границ применяется для анализа результата бинаризации, проводимого с той же целью, что и в прототипе, но без необходимости проведения самой бинаризации. Отсутствием пробной бинаризации, в конечном счете, объясняется сниженная вычислительная сложность и повышенное быстродействие заявленного способа в сравнении с прототипом.
Пороговая процедура может быть определена различным образом. В наиболее общепринятом определении порога бинаризации и пороговой процедуры, пиксели, яркость которых меньше яркости порога бинаризации, относят к символу, а остальные пиксели относят к фону. Для пороговой процедуры, определенной таким образом, переходный уровень пикселя оказывается на единицу больше значения яркости пикселя. При ином определении порога бинаризации и пороговой процедуры, когда пиксели, яркость которых меньше либо равна яркости порога бинаризации, относят к символу, переходный уровень пикселя равен яркости этого пикселя. Для заявленного способа, разница в определениях порога бинаризации и пороговой процедуры не играет существенной роли. Так как переходный уровень отличается от уровня яркости пикселя на постоянную величину, то соотношения «больше», «меньше» и «равно» для уровня яркости между соседними пикселями совпадают с соотношениями «больше», «меньше» и «равно» для переходного уровня соседних пикселей. Понятие переходного уровня позволяет единым образом рассматривать различные реализации пороговой процедуры.
Для построения гистограммы длины границ в соответствии с приведенным ранее общим подходом, первоначально присваивают всем ячейкам гистограммы длины границ нулевые значения, а затем анализируют границы между граничащими пикселями, для чего для каждой пары граничащих пикселей полутонового изображения, разделенных пограничным отрезком, проводят сравнение яркости пикселей и определяют менее яркий и более яркий пиксель в паре, после чего увеличивают значение ячейки, соответствующей переходному уровню менее яркого пикселя в паре, на длину пограничного отрезка, и уменьшают значение ячейки, соответствующей переходному уровню более яркого пикселя в паре, на длину пограничного отрезка, где переходный уровень пикселя представляет собой такой уровень из упорядоченного набора возрастающих значений яркости, при котором значение соответствующего пикселя в двухуровневом изображении, формируемом пороговой процедура, изменяется при изменении порога, применяемого в пороговой процедуре, до переходного уровня от предшествующего ему уровня в упомянутом упорядоченном наборе, и, для учета дополнительной составляющей длины границ, для каждого пикселя, находящегося на краю изображения, увеличивают значение ячейки гистограммы длины границ, соответствующей переходному уровню этого пикселя, на длину стороны пикселя, находящейся на краю изображения.
Для простоты рассуждения, мы будем говорить о черных пикселях символа и белых пикселях фона в бинаризованном изображении. Длина границ в бинаризованном изображении определяется суммарной длиной пограничных отрезков между соседними граничащими пикселями, один из которых является черным, а другой является белым.
Для формирования гистограммы длины границ, по отдельности рассматриваются все пары граничащих пикселей полутонового изображения. При нарастании порога бинаризации, результат пороговой процедуры для пикселя в паре изменяется в тот момент, когда порог бинаризации достигает переходного уровня этого пикселя. Такое изменение, называемое здесь переходом, вносит свой вклад в значение ячейки гистограммы длины границ, которая соответствует переходному уровню. Когда переход приводит к тому, что пиксели в двухуровневом бинаризованном изображении, соответствующие рассматриваемой паре, получают различающиеся значения, длина границ в бинаризованном изображении увеличивается на длину пограничного отрезка. Для отражения этого в гистограмме длины границ, длина пограничного отрезка должна быть добавлена к ячейке, соответствующей переходному уровню изменившегося пикселя. Напротив, если в результате перехода, значения пикселей в двухуровневом бинаризованном изображении становятся одинаковыми, то длина границ уменьшается и длина пограничного отрезка должна быть вычтена из ячейки, соответствующей переходному уровню изменившегося пикселя. При одинаковых переходных уровнях, в результате синхронного перехода пикселей, длина границ не меняется, и модифицировать ячейки гистограммы длины границ нет необходимости.
Чтобы реализовать описанную логику модификации значения ячеек гистограммы длины границ, проводится сравнение яркости пикселей, составляющих пару граничащих пикселей. На основе результатов сравнения, когда уровни яркости граничащих пикселей различаются, то обеспечивают изменение значения двух ячеек гистограммы, соответствующих переходным уровням пикселей, на длину пограничного отрезка с использованием соответствующего знака. При равенстве уровней яркости пикселей и, соответственно, их переходных уровней, не изменяют ни одной ячейки гистограммы.
С целью учета дополнительной составляющей длины границ, для каждого пикселя, находящегося на краю изображения, увеличивают значение ячейки гистограммы длины границ, соответствующей переходному уровню этого пикселя, на длину стороны пикселя, находящейся на краю изображения. Подобная реализация учета основывается на предположении, что вне рассматриваемого участка находятся пиксели заведомо более высокой яркости, чем любой пиксель участка изображения, содержащего символ. За счет этого, граница темного символа, находящаяся на границе участка, рассматривается совершенно аналогично границе данного символа с более ярким фоном. А именно, сторона пикселя, находящаяся на границе рассматриваемого участка, по мере роста порога включается в общую длину границ, как только указанный пиксель, при бинаризации, переходит из высокого уровня яркости в низкий.
Для ускорения формирования гистограммы длины границ, сравнение уровней яркостей пикселей и соответствующая модификация гистограммы длины границ могут быть сгруппированы наиболее эффективным образом. В одной из реализаций способа, сначала устанавливают накопительную сумму в нулевое значение, а затем если имеется граничащий пиксель, расположенный в строке с меньшим номером, и яркость рассматриваемого пикселя больше либо равна яркости граничащего пикселя, то увеличивают накопительную сумму на длину пограничного отрезка, если имеется граничащий пиксель с меньшим номером, расположенный в той же строке, и яркость рассматриваемого пикселя больше либо равна яркости граничащего пикселя, то увеличивают накопительную сумму на длину пограничного отрезка, если имеется граничащий пиксель, расположенный в строке с большим номером, и яркость рассматриваемого пикселя больше яркости граничащего пикселя, то увеличивают накопительную сумму на длину пограничного отрезка, если имеется граничащий пиксель с большим номером, расположенный в той же строке, и яркость рассматриваемого пикселя больше яркости граничащего пикселя, то увеличивают накопительную сумму на длину пограничного отрезка, после чего изменяют ячейку гистограммы приращения длины границ, соответствующую переходному уровню рассматриваемого пикселя, на число 4, из которого предварительно вычитается удвоенная накопительная сумма.
Рассмотрение каждого пикселя представляет собой анализ влияния его границ с другими граничащими пикселями на значение в ячейке гистограммы приращения границ, соответствующей переходному уровню рассматриваемого пикселя. Накопительная сумма М соответствует числу пограничных отрезков рассматриваемого пикселя с менее яркими граничащими пикселями. При нарастании порога бинаризации переход менее ярких граничащих пикселей происходит сначала, и лишь потом происходит переход рассматриваемого пикселя. Поэтому, переход рассматриваемого пикселя уменьшает длину границ бинаризованного изображения в соответствии со значением накопительной суммы. В случае более ярких граничащих пикселей, переход рассматриваемого пикселя происходит до перехода более ярких граничащих пикселей, и увеличивает длину границ. Суммарное число граничащих пикселей, вне зависимости от их яркости, равно 4. Поэтому, отрицательный вклад пограничного отрезка с более темным пикселем не только напрямую уменьшает значение ячейки гистограммы приращения границ, соответствующей переходному уровню рассматриваемого пикселя, но также и сокращает количество более светлых граничащих пикселей, увеличивающих значение ячейки. Таким образом, отрицательный вклад накопительной суммы М в ячейку гистограммы длины границ нужно учитывать дважды. В результате, значение 4-2М характеризует полный вклад рассматриваемого пикселя в указанную ячейку.
Для пикселей, находящихся на краю участка, отсутствие граничащего пикселя не приводит к увеличению накопительной суммы М и, за счет этого, всегда учитывается как пограничный отрезок с более ярким пикселем за пределом участка.
В двух из четырех условий, применяемых для изменения накопительной суммы М, для яркости используется условие «больше либо равна», а в оставшихся двух применяется условие «больше». Благодаря этому, случай равенства яркости двух граничащих пикселей рассматривается таким образом, что длина пограничного отрезка между двумя указанными пикселями учитывается дважды и приводит, один раз, к увеличению соответствующей ячейки гистограммы длины границ, а другой раз к ее уменьшению. За счет этого, граница между двумя пикселями равной яркости вовсе не учитывается в гистограмме длины границ, поскольку она ни при каком пороге бинаризации не входит в длину границ бинаризованного изображения.
Описанная здесь группировка действий не изменяет описанного ранее общего подхода, основанного на выборе наибольшего и наименьшего уровня яркости в паре граничащих пикселей. Изменяется порядок действий, но не их результат. Однако, группировка действий уменьшает общее количество арифметических операций и, без дополнительных операций, учитывает вклад пикселей, находящихся на границах участка.
Для нахождения итогового порога бинаризации, при использовании которого бинаризованное изображение содержит непрерывные линии, анализируют гистограмму длины границ на предмет нахождения интервала непосредственно следующих друг за другом значений яркости, таких, что значения ячеек гистограммы, соответствующих значениям яркости на указанном интервале, по модулю не превышают заранее заданного предела, и определяют итоговый порог бинаризации на основе значений конечных точек указанного интервала в соответствии с заранее заданным правилом.
Указанный способ позволяет установить итоговый порог в пределах между минимально допустимым и максимально допустимым значением, опираясь на тот ранее описанный факт, что рост границ бинаризованного изображения на четвертом этапе оказывается очень малым.
Однако, существенное дополнительное преимущество дает предпочтительная реализация способа, в которой дополнительно формируют гистограмму яркости полутонового изображения, где ячейки соответствуют значениям яркости из упорядоченного набора, используемого при построении гистограммы длины границ, и, для каждого значения яркости в упорядоченном наборе, задают значение соответствующей ему ячейки как количество пикселей полутонового изображения, переходный уровень которых равен названному значению яркости, а для оценки усредненной толщины линии при пробном значении порога используют параметр толщины, равный отношению суммы всех ячеек гистограммы длины границ на интервале от минимального уровня яркости в наборе до пробного порога к сумме всех ячеек гистограммы яркости на интервале от минимального уровня яркости в наборе до пробного порога, и, по заданному правилу, в качестве итогового порога бинаризации выбирают такой пробный порог, при котором параметр толщины близок к целевому значению, причем, указанное значение заранее выбирают для уменьшения погрешности воспроизведения символа в итоговом результате бинаризации, на основе известных начертаний тех символов, которые могут располагаться в пределах участка банкноты.
Для каждого значения пробного порога сумма всех ячеек гистограммы длины границ на интервале от минимального уровня яркости в наборе до значения пробного порога есть площадь темных частей бинарного изображения, полученного в результате бинаризации с пробным порогом. Площадь выражается числом пикселей. Параметр толщины вычисляется как отношение суммы всех ячеек гистограммы длины границ на интервале от минимального уровня яркости в наборе до пробного порога к сумме всех ячеек гистограммы яркости на интервале от минимального уровня яркости в наборе до пробного порога. То есть, параметр толщины есть отношение длины границ бинаризованного изображения к площади его темных частей.
Символы состоят из линий, для которых характерно существенное превышение длины над шириной. Прежде всего, рассмотрим отдельную длинную прямую линию постоянной толщины, расположенную в участке, подвергаемом бинаризации. При этом рассмотрении, для упрощения, первоначально мы не будем учитывать дискретную пиксельную структуру изображения. Указанная прямая линия, по сути, представляет собой прямоугольник, одна из сторон которого соответствует длине линии, а другая соответствует ее ширине. Для такой линии, из очевидных геометрических соображений, площадь равна произведению длины на толщину.
Длина границ такой линии есть периметр соответствующего ей прямоугольника. Этот периметр почти точно равен удвоенной длине линии, так как ширина линии мала в сравнении с длиной, и вкладом сторон прямоугольника, соответствующим ширине, можно пренебречь. Таким образом, длина линии почти равна половине длины границ линии. Соответственно, площадь линии S почти равна половине произведения длины границ В на ширину линии W.
Если дополнительно брать в рассмотрение пиксельную структуру изображения, то каждую из сторон прямоугольника нужно заменить на ломаную линию, состоящую из горизонтальных и вертикальных отрезков, соответствующих сторонам пикселей. Поэтому, длина границ представляет собой сумму длин горизонтальных и вертикальных отрезков в составе ломаных линий, соответствующих сторонам прямоугольника. Из-за этого, длина границ линии с учетом дискретной пиксельной структуры изображения отличается от идеальной геометрической длины границ, рассматриваемой без учета дискретности, на коэффициент дискретности, примерно равный 1,2±17% и зависящий от угла наклона линии. Минимальное значение коэффициента дискретности получается в случае вертикальной и горизонтальной ориентации линии, а максимальное достигается при наклоне 45°. Эти соображения непосредственно подтверждаются теоремой Пифагора. При наклоне 45° длина границы с учетом дискретности формируется суммой одинаковых вертикальных и горизонтальных катетов прямоугольных треугольников, образуемых сторонами пикселей. Эта сумма примерно в 1,41 раз превышает длину границы линии без учета дискретизации, вычисляемую как сумма гипотенуз указанных треугольников. Для любых других углов разница между суммой катетов и гипотенузой оказывается меньше названной, и вовсе отсутствует при углах 0° и 90°.
Таким образом, с учетом дискретности, площадь линии S почти равна (0,6±17%)BW. За счет этого, параметр толщины Р, определяемый как отношение длины границ к площади, оказывается обратно пропорциональным толщине линии: . Указанное соотношение, с небольшой потерей точности, сохраняется и для изогнутых линий. Пренебрегая малым вкладом в границы и площадь в местах пересечения линий, это соотношение можно далее распространить на единичный символ либо несколько символов, выполненных одним шрифтом, расположенных в участке изображения, подлежащем бинаризации. Точное значение коэффициента обратной пропорциональности будет варьироваться для различных символов либо их наборов, в зависимости от конкретной формы и ориентации линий в символе либо символах.
Существуют шрифты сложного начертания, в которых толщина линии может меняться от одного конца линии к другому. Для таких шрифтов параметр толщины обратно пропорционален среднему значению толщины линий. В целом, параметр толщины соответствует художественной характеристике, называемой насыщенностью шрифта, которая изменяется по шкале «светлый - жирный». Более светлый шрифт имеет меньшую толщину линий и, соответственно, больший параметр толщины символа, в то время как более жирный имеет большую толщину линий и меньший параметр толщины символа. При составлении начертаний различных символов одного и того же шрифта, дизайнер старается обеспечить постоянство насыщенности для всех символов, поскольку это обеспечивает гармоничное восприятие текста, набранного шрифтом. Этим объясняются близкие значения параметра толщины для символов, составляющих один шрифт.
В предпочтительной реализации, по заданному правилу, в качестве итогового порога бинаризации выбирают такой пробный порог, при котором параметр толщины близок к заранее выбранному целевому значению. Указанное целевое значение выбирают для уменьшения погрешности воспроизведения символа в итоговом результате бинаризации, и делают этот выбор на основе известных начертаний тех символов, которые могут располагаться в пределах участка банкноты. Целевое значение параметра толщины, которое обеспечивает уменьшение погрешности воспроизведения, может быть задано путем теоретического анализа эталонных изображений символов известного шрифта либо пробной бинаризации изображений символов этого шрифта.
Теоретический анализ позволяет вычислить площадь и длину границ для известного эталонного бинарного изображения каждого символа в шрифте. По вычисленным значениям следует найти обобщенное значение параметра толщины, которое, в целом, соответствует символам шрифта. Использование такого обобщенного значения параметра толщины в качестве целевого, в свою очередь, обеспечит близость итогового результата бинаризации к соответствующему эталонному изображению.
При пробной бинаризации следует получить несколько сканированных изображений каждого из символов известного шрифта! Далее, каждое сканированное изображение нужно бинаризовать множество раз с использованием различных порогов бинаризации, и, по полученным бинарным изображениям, найти соответствующие им значения параметра толщины. Из различных значений параметра толщины нужно выбрать и усреднить те, которые обеспечивает наиболее точное воспроизведение символов в бинарном изображении. Усредненное значение параметра толщины следует использовать в качестве целевого.
Предпочтительная реализация позволяет найти итоговый порог, близкий к наилучшему. При таком итоговом пороге, в бинаризованном изображении, с точностью до примерно ±17%, будет достигнута средняя толщина линий, характерная для известного шрифта, которым выполнен символ либо символы. За счет сохранения характерной толщины линий повышается сходство между итоговыми результатами бинаризации одного и того же символа, расположенного на различных банкнотах, и снижается влияние различий в загрязнении при износе банкнот. Повышение сходства, выражающееся, в частности, в уменьшении разброса расстояний между характерными точками символа, позволяет проводить распознавание с уменьшенным уровнем ошибок. Важно отметить, что для итогового результата бинаризации изображения разных экземпляров символа одного и того же начертания, различие средней толщины линий между экземплярами оказывается существенно меньше ±17%. Так происходит, поскольку коэффициент дискретности зависит от формы линий и мало изменяется при одинаковой форме линий в символе. Поэтому, хотя искажение толщины линий определенного символа, в сравнении с символами других начертаний, будет находиться в пределах примерно ±17%, но оно будет мало изменяться от одного экземпляра символа к другому экземпляру символа того же начертания. Иначе говоря, предпочтительный способ обеспечивает повышенную повторяемость средней толщины линий в итоговом результате бинаризации для символов одного и того же начертания. Нужно учитывать, что повышенной повторяемости не удается достичь, когда в участке изображения располагается более чем один символ, поскольку коэффициент дискретности будет различаться в зависимости от набора символов.
На Фиг. 1 приведено полутоновое изображение серийного номера банкноты, подлежащего бинаризации (А) и результаты его бинаризации с использованием различных значений порога (В - Н).
На Фиг. 2 показаны гистограмма длины границ (А) и гистограмма яркостей (В) полутонового изображения серийного номера. Там же, как функции примененного порога бинаризации, приведены зависимости длины границ и параметра толщины (А), а также площади черных пикселей (В) бинаризованного изображения.
На Фиг. 3 показан вклад границы между двумя пикселями в общую длину границ при различных значениях порога бинаризации, и вклад этих пикселей в гистограмму длины границ.
На Фиг. 4 дана блок-схема вычисления гистограммы длины границ.
На Фиг. 5 показаны различные варианты формирования вклада пикселя в общую длину границ при различных соотношениях яркости этого пикселя по отношению к яркости граничащих пикселей.
На Фиг. 6 приведена блок-схема применения заявленного способа в устройстве для обработки банкнот.
В примере реализации заявленного способа, проводится бинаризация изображения серийного номера банкноты. Для иллюстрации, выбрано полутоновое изображение серийного номера банкноты номиналом 200 израильских шекелей, показанное на Фиг. 1А. Это изображение содержит номер, содержащий 10 символов цифр, а также фон в окрестности номера. Каждый пиксель изображения представлен значением яркости в интервале от 0 (самый темный) до 255 (самый светлый).
Гистограмма 3 яркости этого изображения показана на Фиг. 2 и является трехмодовой. Фон изображения имеет высокую оптическую плотность, сильно различающуюся в разных частях изображения. Две правые моды на гистограмме 3 яркости относятся к фону и разделены глубоким провалом, что затрудняет правильный выбор порога исключительно на основе гистограммы. При использовании алгоритма Отцу, за разделяющую точку на подобных банкнотах часто принимается не раздел между фоном и символом, а провал, разделяющий две моды фона. Это часто приводит к неправильной бинаризации и невозможности распознавания серийного номера.
При бинаризации с применением фиксированного порога L, в получаемом бинаризованном изображении помечают черным все пиксели, яркость которых меньше или равна L. В выбранной таким образом реализации пороговой функции, переходный уровень пиксела равен его яркости. При использовании различных значений порога L получаются бинаризованные изображения, показанные на Фиг. 1В - Фиг. 1Н, в порядке нарастания порога. Значения использованного порога L показаны справа от каждого бинаризованного изображения.
Для бинаризованного изображения на Фиг. 1В порог бинаризации L=20 оказывается выше наиболее темных пикселей символа, из-за чего в бинаризованном изображении начинают проявляться разрозненные кластеры черных пикселей, относящиеся к символу. Такой порог соответствует второму этапу, описанному ранее. Изображение на Фиг. 1С (L=27) соответствует моменту, когда разрывы линий исчезают практически полностью, за исключением единичных выпадений черных пикселей, не влияющих на качество распознавания. Это изображение соответствует началу четвертого этапа и минимально допустимому порогу бинаризации. Бинаризованные изображения, получаемые на четвертом этапе, позволяют уверенно проводить распознавание символов. Бинаризованные изображения, получаемые на предшествующих этапах, мало пригодны для распознавания из-за массового нарушения целостности линий символа.
Как уже указывалось ранее, в ходе четвертого этапа, дальнейшее увеличение порога ведет к тому, что пиксели в полосе неопределенности постепенно переходят из фона в символ, что сопровождается ростом толщины линий с сохранением структуры символа. Изображения на Фиг. 1D соответствует наилучшему порогу бинаризации L=32, при котором средняя толщина линий символа в бинаризованном изображении равна средней толщине линий исходного символа. При дальнейшем увеличении порога продолжается увеличение толщины линий с сохранением начертания, как показано на Фиг. 1Е. Это изображение соответствует максимально допустимому порогу L=37 и завершению 4 этапа. При максимально допустимом пороге возможно проявление отдельных единичных черных пикселей в месте расположения фона, что не приводит к затруднению распознавания символов. На пятом этапе, как показано на Фиг. 1F (L=45), при увеличении порога сверх максимально допустимого, некоторые пиксели фона в цифровом образе оказываются ниже порога и проявляются в бинаризованном изображении как черные пиксели. За счет этого возникают шумовые кластеры черных пикселей в местах пробелов. На шестом этапе, как показано на Фиг. 1G, при значении порога L=64, которое значительно больше максимально допустимого, шумовые кластеры сливаются с линиями символа. На седьмом этапе, которому соответствует изображение на Фиг. 1H, шумовые кластеры и линии символа полностью сливаются друг с другом, образуя сплошное черное заполнение бинаризованного изображения с белыми включениями. Начиная с пятого этапа, бинаризованное изображение плохо пригодно для распознавания символов из-за массового слияния элементов символа с участками фона. Таким образом, допустимый интервал порога L составляет от 27 до 37, и наилучшее значение порога L=32 лежит приблизительно посередине этого интервала. Чтобы определить наименьшее допустимое, наибольшее допустимое, и наилучшее значения порога, строят гистограмму длины границ на основе полутонового изображения и далее анализируют ее. На Фиг. 2А показана гистограмма 1 длины границ, построенная на основе полутонового изображения, показанного на Фиг. 1А.
Получение гистограммы 1 длины границ основано на наблюдении, которое проиллюстрировано на Фиг. 3. Рассмотрим любую пару пикселей полутонового изображения, имеющих общую границу. Для примера, на Фиг. 3 эти пиксели имеют яркости 10 и 20 и разделены горизонтальным пограничным отрезком между ними. При 0<L<10, в результате бинаризации, оба пикселя в бинаризованном изображении отображаются как белые, граница между черным и белым по границе пикселей в паре не проходит, и вклад этой пары в общую длину границ d=0. При 10≤L<20 пиксель с яркостью 10 отображается как черный, а пиксель с яркостью 20 отображается как белый, так что граница между черным и белым проходит по пограничному отрезку между пикселями, а вклад данной пары пикселей в общую длину границ d=l. При 20≤L≤255 оба пикселя в бинаризованном изображении отображаются как черные, и вклад этой пары в общую длину границ d=0. То есть, при последовательном нарастании L граница между черным и белым в бинаризованном изображении начинает проходить по пограничному отрезку между пикселями в паре при L=10, и перестает проходить по пограничному отрезку между пикселями в паре при L=20. Из этого можно сделать вывод, что для отражения изменения вклада пограничного отрезка между пикселями в гистограмму длины границ, нужно увеличить ячейку этой гистограммы НВ(10) на 1 и уменьшить ячейку НВ(20) на 1.
В более общем виде, пара граничащих пикселей вносит вклад +1 (инкремент) в ячейку гистограммы, соответствующую наименьшему значению яркости пикселя в паре, и вклад -1 (декремент) в ячейку гистограммы, соответствующую наибольшему значению яркости пикселя в паре. Чтобы построить гистограмму длины границ полутонового изображения, нужно рассмотреть все пары граничащих пикселей таким образом, и дополнительно учесть увеличение длины границ на краях изображения. Чтобы учесть вклад всех возможных пар, можно рассматривать границы каждого пикселя не со всеми соседями, а только с соседями справа и снизу, что исключает ошибочное рассмотрение каждой границы дважды. Для большинства пикселей в изображении, за исключением выходящих на правом и нижнем краю изображения, нужно оценить их вклад в две пары с соседними пикселями. Таким образом, количество пар, которые нужно рассмотреть, почти вдвое превышает количество пикселей в полутоновом изображении. Для пикселей на краю изображения, положительный вклад стороны пикселя, проходящей по краю изображения, в общую длину границ, возникает в момент перехода, то есть, когда порог бинаризации становится равным яркости такого пикселя. Соответственно, для каждого пикселя с яркостью I, находящегося на краю изображения, нужно дополнительно увеличить ячейку НВ(I) на количество сторон пикселя, выходящих на край изображения. Для каждой пары граничащих пикселей, используя описанное выше наблюдение, нужно сделать два обращения к гистограмме длины границ. Для почти всех пикселей изображения, таким образом, нужно по 4 обращения к гистограмме длины границ. Имеется возможность, сохранив общий принцип учета вклада каждой пары граничащих пикселей в гистограмму длины границ, с целью повышения быстродействия, уменьшить количество обращений к гистограмме длины границ. Такая возможность использована в примере реализации заявленного способа и будет описана ниже.
Для получения гистограммы 1 длины границ используют вычислительный процесс, блок-схема которого приведена на Фиг. 4. В этом процессе по отдельности рассматривают все пиксели полутонового изображения. При обработке изображений общепринятым является расположение строки с меньшим номером сверху от рассматриваемой строки, и пикселя с меньшим номером слева от рассматриваемого пикселя. Такой порядок нумерации используется и в данном описании. Для каждого пикселя, вначале обнуляют накопительную сумму М (шаг 102), а затем анализируют соотношения яркости I рассматриваемого пикселя и четырех граничащих с ним пикселей сверху, слева, снизу и справа (шаги 103 - 106). Накопительную сумму М инкрементируют каждый раз, когда яркость I рассматриваемого пикселя оказывается больше либо равна яркости граничащего пикселя сверху или слева. Аналогично, накопительную сумму М инкрементируют каждый раз, когда яркость I рассматриваемого пикселя оказывается больше яркости граничащего пикселя снизу или справа.
Исследуем более подробно, что происходит в переходный момент, когда порог бинаризации L изменяется от значения (I-1) к переходному значению I, то есть, когда в бинаризованном изображении рассматриваемый пиксель меняет цвет с белого на черный. Будем обозначать при помощи D увеличение длины границ бинаризованного изображения, проходящих по всем четырем сторонам рассматриваемого пикселя, в момент его перехода из белого состояния в черное. D выражается в единицах, равных длине стороны пикселя. На Фиг. 5, при помощи значений, указанных в соответствующих квадратах пикселей, показаны яркости граничащих пикселей. На Фиг. 4А все 4 пикселя ярче рассматриваемого, то есть, М=0. При переходе все 4 стороны рассматриваемого пикселя увеличивают длину границ на D=4.
В случае на Фиг. 5В, из 4 граничащих пикселей один темнее рассматриваемого и три светлее, то есть, М=1. До перехода, между более темным пикселем и рассматриваемым пикселем проходит граница, показанная пунктирной линией, и она исчезает в момент перехода. В то же время, между тремя более светлыми пикселями и рассматриваемым пикселем, в момент перехода, добавляются три пограничных отрезка, показанные жирной линией. В сумме, это увеличивает длину границ на D=2.
В случае на Фиг. 5С, из 4 граничащих пикселей два темнее рассматриваемого и два светлее, то есть, М=2. При переходе исчезают два граничных отрезка и два появляются, что дает итоговое значение D=0. И, наконец, на Фиг. 5D и Фиг. 5Е показаны случаи с М=3 и М=4, соответственно. При переходе исчезает больше границ, чем добавляется, что дает D=-2 и D=-4, соответственно.
В целом, для всех описанных случаев верной оказывается формула D=4-2M, приведенная на Фиг. 5F. Вычисление по этой формуле выполняют на шаге 107, и добавляют полученное значение D к ячейке НВ(I) гистограммы 1 длины границ, соответствующей значению яркости I рассматриваемого пикселя.
Особого рассмотрения требует соседство рассматриваемого пикселя с пикселем с такой же яркостью I. Ни при каком пороге бинаризации между ними не может образоваться граница, поскольку они совершают переход одновременно. Исходя из наблюдения, показанного на Фиг. 3, эта пара пикселей одновременно дает как инкремент, так и декремент ячейки НВ(I), и потому вообще не вносит вклада в гистограмму длины границ. Чтобы корректно обработать этот случай, на шагах 103 - 106, для граничащего пикселя сверху или слева используется сравнение «больше либо равно», а для граничащего пикселя снизу или справа используется сравнение «больше». Один из пары граничащих пикселей оказывается слева от другого или же снизу от другого. Оба пикселя, при выполнении шага 107, изменяют ячейку НВ(I) гистограммы 1 длины границ. За счет различия в используемом сравнении для расположения пары пикселей сверху-снизу или же слева-справа, вклады этих пикселей в ячейку НВ(I) оказываются противоположными. Один из пикселей дает вклад длины пограничного отрезка между ними, равный 1, а другой пиксель дает вклад, равный -1. В результате суммирования этих вкладов, граница между пикселями равной яркости I вовсе не влияет на ячейку НВ(I) гистограммы 1 длины границ. Также, нужно рассмотреть влияние тех сторон рассматриваемого пикселя, которые выходят на край изображения. В случае выхода стороны рассматриваемого пикселя на край изображения, соответствующий граничащий пиксель отсутствует, и в соответствующем этому шаге 103 - 106 не происходит инкрементирования значения М. Соответственно, в момент перехода рассматриваемого пикселя его сторона, выходящая на край изображения, всегда добавляется к ячейке НВ(I) гистограммы 1 длины границ. Это соответствует формуле D=4-2M, вычисляемой на шаге 107. Описанный эффект эквивалентен тому, как если бы за краем изображения находились пиксели, имеющие яркость больше любой возможной яркости пикселя в самом изображении. Если линия символа находится вплотную к кромке изображения, ее граница, в том числе и участок вдоль края, полностью учитывается в общей длине границ бинаризованного изображения.
Представленный на Фиг. 4 процесс построения гистограммы длины границ оптимизирован по быстродействию, но выполняет те же действия над гистограммой длины границ, которые изображены на Фиг. 3. Процесс на Фиг. 4 группирует действия, связанные с парами, куда входит каждый пиксель, так чтобы уменьшить общее количество обращений к ячейкам гистограммы длины границ, хранимым в оперативной памяти процессора. При рассмотрении каждого пикселя обращение к ячейке гистограммы происходит лишь однажды, а операции декремента не используются. Операции инкремента выполняются для одной и той же переменной М, которая может храниться в регистре процессора и требовать минимальных затрат времени на инкремент. Кроме того, процесс на Фиг. 4 позволяет вычислить дополнительную составляющую для учета длины тех сторон пикселей, которые находятся на краю изображения, не применяя для этого дополнительные шаги.
Рассмотрим полученную гистограмму 1 длины границ. При помощи линии 2 показан график зависимости длины границ B(L). Длина границ B(L) для заданного уровня яркости L представляет собой сумму всех ячеек гистограммы 1 длины границ от нулевого уровня до заданного уровня L.
Для удобства рассмотрения, яркостной диапазон возможных значений порога бинаризации L разделен на отдельные интервалы при помощи штриховых линий 6-13. Для значений яркости слева от линии 6, полностью отсутствуют пиксели с такими значениями, что видно по нулевым значениям гистограммы 3 яркости и гистограммы 1 длины границ. Между линиями 6 и 7 расположены значения яркости, соответствующие второму и третьему этапу, где символ проявляется в бинаризованном изображении лишь частично. В частности, здесь находится порог бинаризации для получения изображения на Фиг. 1В.
Минимально допустимый уровень бинаризации L=27 и изображение на Фиг. 1С соответствует линии 7. Максимально допустимый уровень бинаризации L=37 и изображение на Фиг. 1Е соответствует линии 9. Наилучший уровень бинаризации L=32 и изображение на Фиг. 1D соответствует линии 8.
lim
Как уже описывалось ранее, на четвертом этапе увеличения порога бинаризации, в интервале между линиями 7 и 9, длина границ бинаризованного изображения B(L) с ростом L прирастает в минимальной степени. Соответственно, ячейки HB(L) гистограммы 1 длины границ на этом участке принимают очень малые значения, близкие к нулю. Поэтому, для нахождения максимально и минимального допустимых уровней достаточно найти интервал, где абсолютное значение ячеек HB(L) гистограммы 1 длины границ будет меньше некоторого эмпирически заданного предела. В нашем примере такой предел HB равен 5.
На интервале между линиями 9 и 10, соответствующем пятому этапу, происходит резкий рост значений ячеек гистограммы 1 длины границ, обусловленный появлением шумовых кластеров в области фона изображения. Справа от линии 10 ячейки HB(L) становятся отрицательными, что соответствует снижению длины границ B(L) из-за слияния черных кластеров друг с другом. Колебания значений ячеек между линиями 10 и 11, и 11 и 12 связаны с двухмодовым характером фона изображения. Линия 13 отделяет участок яркостного интервала, правее которого все пиксели в бинаризованном изображении имеют черный цвет, а длина границ B(L) постоянна и равна длине края изображения. Этот интервал соответствует восьмому этапу.
lim
lim
В простом варианте реализации заявленного изобретения, находят минимальный и максимальный допустимый уровни бинаризации, соответствующие линиям 7 и 9. Для этого не требуется рассматривать поведение гистограммы длины границ на участке между линиями 9 и 13, соответствующему этапам с пятого по восьмой. Следует искать лишь интервал, соответствующий четвертому этапу. Для этого начинают перебирать значения уровней яркости от линии 6 в сторону увеличения. При этом, ищут интервал, на котором абсолютное значение ячеек |HB(L)| гистограммы 1 длины границ оказывается меньше эмпирически заданного предела HB. Как только значение |HB(L)| на протяжении нескольких последовательных уровней уйдет выше предела HB, нужно закончить поиск. Наилучший уровень бинаризации находят как середину найденного интервала, что соответствует среднему арифметическому минимального и максимального допустимых уровней бинаризации. Найденный наилучший уровень применяют для бинаризации полутонового изображения (см. Фиг. 1А) и получения итогового результата бинаризации (см. Фиг. 1D).
Однако, этот вариант не опирается на толщину линий в бинаризованном изображении, и не позволяет реализовать дополнительное преимущество, связанное с тем, что заранее известен шрифт, используемый для печати серийного номера. Более сложный, но и более эффективный вариант реализации изобретения использует понятие параметра толщины линии, введенное ранее. Для расчета параметра толщины P(L) используют длину границ B(L), а также количество черных пикселей S(L). Количество черных пикселей S(L) показано кривой 4 на Фиг. 2В, и для заданного уровня L определяется как сумма всех ячеек гистограммы 3 яркости от нулевого уровня до L. По определению, параметр толщины линии вычисляется как .
График P(L) показан кривой 5 на Фиг. 2А. Он не определен при нулевом значении знаменателя, то есть слева от линии 6. В области между линиями 6 и 7 график спадает от начального значения 4,0. Начальное значение 4,0 определяется отношением длины границ к площади для изолированных черных пикселей, которые первыми проявляются в бинаризованном изображении по мере роста порога. Спад графика соответствует образованию кластеров черных пикселей, граница которых растет медленнее площади. Из этих кластеров, при подходе к минимально допустимому значению порога, постепенно формируются линии символов. Уменьшение числа разрывов линий символа соответствует продолжающемуся спаду графика.
Между линиями 7 и 8, на участке четвертого этапа, символ бинаризуется без существенных разрывов линий и проявлений пикселей фона. График P(L) снижается, отражая рост толщины линий символа по мере роста L. Локальный максимум графика P(L) между линиями 9 и 10 возникает из-за появления мелких изолированных черных пикселей фона на пятом этапе. Эти пиксели значительно увеличивают длину границы. При дальнейшем росте L график продолжает снижаться и выходит на очень малое постоянное значение после линии 13.
opt
Путем многократного проведения бинаризации эталонных изображений различных символов цифр шрифта, использованного для печати символов серийного номера израильских шекелей, было определено оптимальное значение параметра ширины линии, равное P=0,72. Оно отмечено на Фиг. 2А штриховой линией 15. При этом значении средняя толщина линии в бинаризованном изображении соответствует средней толщине линии печатного эталона шрифта.
opt
Для нахождения наилучшего порога бинаризации, двигаются по шкале уровней от линии 6 в сторону возрастания L, и для каждого уровня вычисляют P(L). Как только P(L) станет меньше либо равным оптимальному значению P параметра ширины линии, поиск останавливают и используют последнее значение L в качестве наилучшего порога бинаризации. На Фиг. 3А показана точка 14 остановки поиска. Найденный наилучший уровень применяют для бинаризации полутонового изображения (Фиг. 1А) и получения итогового результата бинаризации (Фиг. 1D).
Как простой, так и сложный варианты реализации, в ходе поиска порога бинаризации, не достигают значений порога, при которых в бинаризованном изображении в заметной степени появляются черные пиксели, соответствующие фону. Этим обеспечивается независимость результата бинаризации от особенностей фона. Если фон является контрастным и/или многомодовым, но, как бывает в большинстве случаев, его можно отделить от символа при помощи глобального порога, то оба варианта реализации позволяют найти такой порог.
Результаты выполнения простого и сложного варианта различаются по обработке пикселей в зоне неопределенности вокруг символа. Простой вариант определяет порог как среднее арифметическое минимального и максимального допустимых значений. Это приблизительное решение обеспечивает практическое отсутствие в бинаризованном изображении разрывов линий символа и черных шумовых пикселей фона, но, не обязательно обеспечивает соответствие эталону средней толщины линий символа. Сложный вариант, дополнительно к отсутствию разрывов линий символа и черных шумовых пикселей фона, обеспечивает соответствие эталону средней толщины линий символа. За счет сохранения эталонной толщины линии, распознавание символов может проводиться с более высокой достоверностью. Простой и сложный варианты реализации незначительно отличаются по времени исполнения, поскольку основное время затрачивается на построение гистограммы 1 длины границ. Время исполнения любого из этих вариантов составляет долю от времени исполнения способа, описанного в прототипе, так как бинаризация с помощью найденного порога проводится однократно, а не множество раз.
Последовательность обработки банкноты с применением заявленного способа в счетно-сортировальной машине показана на Фиг. 6. Машина обеспечивает транспортировку банкнот из подающего кармана, при этом проводится сканирование и распознавание с определением типа банкноты (шаг 201). Если банкнота не распознана, то принимается решение (шаг 210) направить банкноту в карман отбраковки. Это решение реализуется при помощи электромеханического перенаправляющего узла, размещенного в банкнотопроводном тракте счетно-сортировальной машины. Если же банкнота распознана, то выделяют цифровое изображение серийного номера из сканированного образа банкноты и поворачивают его для компенсации перекоса (шаг 203). При выделении изображения, опираются на известное место расположения серийного номера на конкретном типе банкноты.
Затем, строят гистограмму длины границ, используя последовательность шагов 100 - 108 (шаг 204). Далее, находят наилучший порог (шаг 205), используя простой либо сложный вариант, описанные ранее. Если используется сложный вариант, на шаге 205, перед выполнением поиска порога, дополнительно строят гистограмму яркости. Найденный наилучший порог применяют для бинаризации изображения (шаг 206).
Распознают полученное бинаризованное изображение (шаг 207) с получением строки серийного номера. Если серийный номер не распознан (шаг 208), то принимают решение о направлении банкноты в карман отбраковки (шаг 210). Если же символ распознан, то направляют банкноту в приемный карман (шаг 209) и записывают серийный номер из массива-строки в электронный отчет о сортировке (шаг 211). Описанную обработку (шаги 201 - 211) повторяют для всех банкнот, находящихся в подающем кармане счетно-сортировальной машины. После этого, распознанные банкноты с успешно распознанным серийным номером оказываются в приемном кармане машины, а в электронном отчете находится список серийных номеров этих банкнот. Банкноты, которые были не распознаны, либо же в серийном номере которых были распознаны не все символы, оказываются в кармане отбраковки. Электронный отчет, содержащий список серийных номеров, может далее использоваться для отслеживания движения банкнот в обороте.
Методы, применяемые для распознавания банкноты на шаге 201, выделения изображения серийного номера и его поворота для компенсации перекоса на шаге 203, и распознавания серийного номера на шаге 207, хорошо известны специалистам в области техники для обработки банкнот и широко описаны в патентной литературе.
Раскрытый здесь способ не ограничен применением для бинаризации всего серийного номера банкноты целиком. Он также может применяться в устройствах, где полутоновое изображение серийного номера вначале разделяют на отдельные знакоместа, содержащие по одному символу каждый. В этом случае, описанный способ бинаризации может быть применен к изображению каждого знакоместа в отдельности. А именно, для каждого изображения знакоместа должно проводиться построение гистограммы длины границ, нахождение наилучшего порога, и бинаризация с использованием найденного наилучшего порога. Полученные бинаризованные изображения далее должны использоваться для распознавания отдельных символов. Применение заявленного способа к отдельным знакоместам, во многих случаях, позволяет надежно отделить символы от фона даже в тех случаях, когда качественная бинаризация всего серийного номера с помощью глобального порога невозможна. Подобная проблема характерна для банкнот, где серийный номер напечатан полупрозрачной краской на темном контрастном фоне. Яркость пикселей различных символов, напечатанных полупрозрачной краской, сильно зависит от яркости фона и различается для различных знакомест, что приводит к расширению общего градационного интервала яркости пикселей символа. В результате, часто возникает сильное перекрытие градационных интервалов яркости символов и фона в пределах всего номера. Заявленный способ позволяет успешно бинаризовать символы по отдельности, при условии отсутствия существенного перекрытия градационных интервалов яркости символа и фона в пределах каждого из знакомест.