способ классификации банкнот (варианты)

Формула изобретения

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

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

3. Способ по п.1 или 2, в котором в ходе вычисления расстояния между банкнотой и заранее известным классом проверяют, не превысило ли значение суммы величины максимально допустимого расстояния до данного класса, в случае превышения прекращают дальнейшие вычисления и выносят суждение о невозможности принадлежности банкноты к данному классу.

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

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

6. Способ по п.1 или 2, в котором после вынесения суждения о возможности принадлежности банкноты к известным классам дополнительно сравнивают между собой расстояния от банкноты до тех классов, принадлежность к которым признана возможной, находят тот класс, расстояние до которого является минимальным, и выносят суждение о принадлежности банкноты к найденному классу.

7. Способ по п.3, в котором после вынесения суждения о возможности принадлежности банкноты к известным классам дополнительно сравнивают между собой расстояния от банкноты до тех классов, принадлежность к которым признана возможной, находят тот класс, расстояние до которого является минимальным, и выносят суждение о принадлежности банкноты к найденному классу.

8. Способ по п.4, в котором после вынесения суждения о возможности принадлежности банкноты к известным классам дополнительно сравнивают между собой расстояния от банкноты до тех классов, принадлежность к которым признана возможной, находят тот класс, расстояние до которого является минимальным, и выносят суждение о принадлежности банкноты к найденному классу.

9. Способ по п.5, в котором после вынесения суждения о возможности принадлежности банкноты к известным классам дополнительно сравнивают между собой расстояния от банкноты до тех классов, принадлежность к которым признана возможной, находят тот класс, расстояние до которого является минимальным, и выносят суждение о принадлежности банкноты к найденному классу.

10. Способ классификации банкнот (вариант 2), при котором сканируют банкноту для получения двумерного образа банкноты, состоящего из пикселей, разделяют полученный образ на области по заданной схеме разделения, для каждой области по определенному алгоритму вычисляют функцию так, что ее значение зависит от значений пикселей, входящих в область, находят сигнатуру образа банкноты в виде двоичного числа, для чего каждому разряду сигнатуры сопоставляют определенную пару областей, для каждой такой пары областей сравнивают соответствующие этим областям значения функций, устанавливают значение каждого разряда сигнатуры в соответствии с логическим результатом сравнения, производят сопоставление сигнатуры с заранее известными классами банкнот, причем каждый класс представляется заранее известным центроидом класса, заранее известной битовой маской сравнения, а также максимально допустимым расстоянием до центроида, при этом для известного каждого класса находят двоичные разряды сигнатуры, отличающиеся от соответствующих разрядов центроида класса, из них отбрасывают те разряды, которые маскируются битовой маской сравнения, находят расстояние между банкнотой и данным классом, для чего подсчитывают количество отличающихся разрядов, которые не замаскированы битовой маской сравнения, сравнивают найденное расстояние с максимально допустимым расстоянием до данного класса, если найденное расстояние не превышает максимально допустимого расстояния до данного класса, выносят суждение о возможности принадлежности банкноты к данному классу, если же найденное расстояние превышает максимально допустимое расстояние до данного класса, то выносят суждение о невозможности принадлежности банкноты к данному классу.

11. Способ по п.10, в котором для нахождения расстояния до класса дополнительно вычисляют заданную функцию, аргументами которой являются количество отличающихся разрядов, которые не замаскированы битовой маской сравнения, а также количество маскирующих разрядов в битовой маске класса.

12. Способ по п.10 или 11, в котором пары областей составляются из областей, имеющих общую границу.

13. Способ по п.10 или 11, в котором после вынесения суждения о возможности принадлежности банкноты к известным классам дополнительно сравнивают между собой расстояния от банкноты до тех классов, принадлежность к которым признана возможной, находят тот класс, расстояние до которого является минимальным, и выносят суждение о принадлежности банкноты к найденному классу.

14. Способ по п.12, в котором после вынесения суждения о возможности принадлежности банкноты к известным классам дополнительно сравнивают между собой расстояния от банкноты до тех классов, принадлежность к которым признана возможной, находят тот класс, расстояние до которого является минимальным, и выносят суждение о принадлежности банкноты к найденному классу.

Описание изобретения к патенту

Область техники

Изобретение относится к способам определения основных характеристик банкнот, таких как вид валюты и номинал. Способ может быть реализован в устройствах, производящих детектирование, подсчет либо сортировку банкнот.

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

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

Предшествующий уровень техники

Способ классификации в составе устройства, производящего обработку банкнот, описан в международной заявке на изобретение WO 2007/068867 (опубл. 21.06.2007 г., МПК G07D 7/20). Устройство сканирует банкноту, получая цифровой образ, состоящий из двумерных изображений банкноты. Для проведения вычислительной обработки цифрового образа устройство оснащено вычислительным блоком.

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

Одним из недостатков способа, описанного в вышеназванной заявке, является использование отдельной схемы разбиения по областям для каждого из классификаторов. Соответственно, вычисление средних значений областей нужно делать в отдельности для каждого классификатора. Другим недостатком данного способа является то, что основная вычислительная обработка (вычисление средних значений и применение классификаторов) проводится в неизменном объеме для каждого возможного класса, и только затем производится анализ результата. Оба указанных недостатка приводят к большой вычислительной сложности, особенно если число применяемых классификаторов велико. Большая вычислительная сложность, в свою очередь, требует применения вычислительного блока повышенной производительности.

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

Раскрытие изобретения

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

Техническим результатом является снижение вычислительных затрат при обработке банкноты.

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

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

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

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

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

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

В одной из реализаций второго варианта способа пары областей составляются из областей, имеющих общую границу.

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

Классы, принадлежность к которым можно проверить по заявленному способу, будем называть известными классами. Состав известных классов определяется особенностями области применения устройства. Так, если устройство предназначено только для обработки банкнот одного государства, то для него в состав известных классов должны входить все номиналы банкнот данного государства, каждый в 4 возможных ориентациях. Для многовалютных устройств состав известных классов должен быть соответственно увеличен, чтобы охватить все номиналы и ориентации заданного набора валют. Заявленный способ при реализации для конкретного устройства настраивается на определенный набор известных классов за счет соответствующего выбора параметров (заранее известных). Заявленный способ выявляет принадлежность банкноты к одному из известных классов либо дает заключение о том, что банкнота не принадлежит ни к одному из известных классов.

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

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

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

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

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

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

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

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

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

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

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

Каждому образу банкноты ставится в соответствие точка в n-мерном пространстве признаков, координатами которой являются значения соответствующих признаков. Для определения классов, к которым, возможно, принадлежит банкнота, вычисляют расстояние от каждого из известных классов до анализируемой банкноты. Под расстоянием до класса здесь понимается некоторая математическая характеристика, которая тем меньше, чем более банкнота похожа на типичного представителя заданного класса. Расстояние вычисляется на основании вектора признаков банкноты.

Это расстояние используется как мера соответствия банкноты заданному классу. Варианты 1 и 2 используют различные способы вычисления расстояния.

Описание чертежей

На фиг.1 изображено расположение класса в пространстве признаков.

На фиг.2 показано взаимное расположение известных классов в пространстве признаков.

На фиг.3 показано упорядоченное регулярное разбиение цифрового образа банкноты на квадратные зоны 10х10 пикселей на примере образа купюры 500 Евро в инфракрасном свете.

На фиг.4а изображен график изменения уровней пропускания (отражения) банкноты при износе.

На фиг.4b изображен график перемещения банкноты в пространстве признаков по мере износа.

На фиг.5 (а-d) показано изменение гистограммы банкноты по мере износа, на фиг.5е показан вид гистограммы после линейного преобразования интервала значений пикселей.

На фиг.6а показано расположение класса в пространстве признаков до линейного преобразования интервала значений пикселей, на фиг.6b - после линейного преобразования.

На фиг.7 изображена блок-схема алгоритма классификации по способу 1.

На фиг.8а изображена схема разбиения банкноты, на фиг.8b приведены значения признаков, на фиг.8с - значения полученных битов сигнатуры.

На фиг.9 изображена блок-схема алгоритма классификации по способу 2.

На фиг.10, 11 изображена блок-схема алгоритма классификации с использованием сигнатуры и манхеттенского расстояния.

На фиг.12 изображена блок-схема последовательности действий при пересчете банкнот в устройстве.

Варианты реализации изобретения

Вычисление расстояния от банкноты до заданного класса по варианту 1 проиллюстрировано на фиг.1, фиг.2. С целью упрощения для изображения пространства признаков используется плоская прямоугольная система координат с двумя координатными осями. В реальности размерность «n» пространства признаков может достигать 100 и более, однако изобразить его на чертеже практически невозможно. Изображение трехмерного пространства происходит с потерей наглядности, а для пространств большей размерности изображение вовсе невозможно. Тем не менее, заключения, сделанные для двумерного пространства, без потери общности можно распространить и на общий случай n-мерного пространства.

Каждая банкнота на чертеже представляется точкой Х=(Х1, Х2). Класс задается центроидом С=(С1, С2) и вектором допустимого отклонения =( 1, 2). Эти величины определяются в ходе анализа большого количества банкнот, принадлежащих данному классу, так называемых обучающих банкнот. Каждая обучающая 1 банкнота на чертеже изображена крестиком. В ходе обучения необходимо построить минимально возможный по размерам прямоугольник 2, охватывающий все имеющиеся обучающие 1 банкноты. Такой прямоугольник мы в дальнейшем будем называть моделью класса. В n-мерном пространстве модель класса является гиперпараллелепипедом. Центр модели класса является центроидом класса С=(С1, С2), а половина размера модели класса по каждой координате дает соответствующий компонент вектора отклонения =( 1, 2). Модель класса можно представить как декартово произведение интервалов ([С1- 1, С1+ 1], [С2- 2, С2+ 2]).

Элементы вектора центроида С характеризуют средние значения признаков банкнот одного класса. Элементы вектора допустимого отклонения , напротив, характеризуют изменчивость отдельных признаков в совокупности обучающих 1 банкнот. Из-за описанной изменчивости отдельные признаки банкноты заданного класса, соответствующие изменчивым зонам, могут иметь большее отклонение от центроида С, чем другие, которые соответствуют мало изменчивым зонам. При помощи компонентов вектора задаются индивидуальные пределы отклонения признаков в пределах модели класса.

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

Для нахождения расстояния между банкнотой и заданным классом по варианту 1 применяется так называемое «манхеттенское расстояние». По определению «манхеттенское расстояние» между двумя точками А=(А1, А2) и В=(В1, В2) вычисляется как сумма модулей разностей соответствующих координат точек |А1-В1|+|А2-В2|. «Манхеттенское расстояние» известно в математике как одна из альтернатив традиционному понятию «евклидова расстояния», вычисляемого как . Для нахождения «манхеттенского расстояния» используются только вычислительные операции сложения, вычитания и сравнения. «Евклидово расстояние» дополнительно требует для своего вычисления более сложных операций возведения в квадрат и взятия квадратного корня. Поэтому вычислительные затраты для нахождения «манхеттенского расстояния» значительно ниже, чем затраты на нахождение «евклидового расстояния». Как характеристика близости «манхеттенское расстояние» практически не уступает «евклидовому».

В качестве расстояния от банкноты 3 до класса для варианта 1 мы будем использовать «манхеттенское расстояние» между банкнотой 3 и моделью 2 этого класса. Поскольку класс представляется моделью 2 класса в виде прямоугольника (гиперпараллелепипеда), а банкнота 3 представляется точкой, то расстояние между моделью 2 класса и банкнотой 3 есть минимальное «манхеттенское расстояние» между этой точкой и множеством точек прямоугольника (гиперпараллелепипеда) модели. Для его обозначения мы будем использовать символ DM.

Для вычисления расстояния между банкнотой В=(В1, В2) и заданным классом для каждой отдельной координаты в пространстве признаков находят модуль разности между значениями этой координаты вектора признаков банкноты В и вектора центроида С и вычитают из него значение данной координаты вектора отклонения А. Значение расстояния находят суммируя только те из полученных значений, которые являются положительными. Фактически, этот вычислительный процесс находит наименьшее из «манхеттенских расстояний» между банкнотой В и точками модели ([С1- 1, С1+ 1], [С2- 2, С2+ 2]) заданного класса.

Банкноты 1 из обучающей совокупности всегда имеют нулевое расстояние DM от банкноты до класса. Банкноты 3 из обращения, принадлежащие заданному классу, имеют нулевое расстояние DM до этого класса, только если они лежат внутри его модели 2. Те банкноты, которые не попадают в пределы модели 2 класса, будут иметь некоторое положительное расстояние DM до этого класса. Когда банкнота 3 из обращения принадлежит заданному классу, значение расстояния DM будет невелико. Банкнота 5, относящаяся к другому классу, имеет большое расстояние DM до заданного класса. Это свойство используется для классификации банкнот согласно заявленному способу.

На Фиг.1 при помощи восьмиугольников 4 показаны границы областей, для внутренних точек которых расстояние DM до заданного класса меньше определенного значения. В n-мерном пространстве эти области будут ограничены многогранными гиперповерхностями. Для исключения банкноты, не относящейся к заданному классу, следует определить максимально допустимое значение DM=DMTH, при котором все банкноты заданного класса будут находиться внутри соответствующего многоугольника. Чтобы проверить, относится ли банкнота к заданному классу, вычисляют расстояние от нее до этого класса и проверяют, что оно не превосходит максимально допустимого значения DMTH до этого класса. Если оно не превосходит DMTH, то делают вывод о том, что банкнота может принадлежать к заданному классу. Если же расстояние больше, чем DMTH, то делают вывод о том, что банкнота не может принадлежать заданному классу.

На Фиг.2 изображено расположение известных классов а-h в пространстве, причем каждый класс изображается в виде его модели и семейства ограничивающих линий (гиперповерхностей). Внешняя ограничивающая линия (гиперповерхность) для каждого класса соответствует максимально допустимому расстоянию DMTH и называется границей класса. Точка, соответствующая классифицируемой банкноте, может попасть в пределы внутри границы того или иного класса. В этом случае делается вывод о том, что банкнота может принадлежать этому классу. Если точка не попадает в границы ни для одного класса, то делается вывод о том, что банкнота не принадлежит ни одному из известных классов.

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

При оптимальном выборе признаков, как показывает опыт, в большинстве случаев удается достигнуть такого расположения классов, при котором их границы не пересекаются. Однако в определенных случаях это невозможно, например для похожих друг на друга версий банкнот одного и того же номинала, которые обычно различаются только небольшими деталями. Классы с и f, как показано на чертеже, пересекаются своими границами. Точка 6, соответствующая банкноте, попадает в пределы обоих классов. Поэтому результатом ее классификации являются два класса: с и f. В этом случае в устройстве необходимо провести дополнительные действия по уточнению, к какому же из найденных классов все-таки относится банкнота.

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

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

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

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

В качестве первого шага вычисляют усредненное значение пикселей из заданного двумерного массива, которые попадают в заданную область. Затем преобразуют полученное значение, чтобы учесть различия между банкнотами одного класса, находящимися в обороте. Различия между банкнотами по выходе с печатной фабрики относительно невелики и начинают увеличиваться по мере их износа. Износ банкнот можно разделить на общий, происходящий во всех областях банкноты, и локальный, относящийся к отдельным зонам банкноты. Локальный износ плохо поддается моделированию и учету, так как связан с индивидуальными повреждениями банкнот: получению пятен, проколов, разрывов, отгибу уголков, появлению посторонних надписей. Общий износ, напротив, происходит достаточно единообразно у всех банкнот, и включает два основных процесса: истирание красочного слоя и загрязнение.

Особенности общего износа банкноты, в первом приближении, учитываются линейной моделью износа банкноты, как проиллюстрировано графиками 7-10 на Фиг.4а. Линейная модель износа непосредственно применима к характеристикам оптического пропускания и отражения. За счет загрязнения снижается общее пропускание или отражение излучения бумагой. В свою очередь, истирание красочного слоя приводит к уменьшению общего контраста банкноты. На графике Фиг.4а показано отображение начальных значений оптической плотности на различных участках совершенно новой банкноты (ось абсцисс) в значения оптической плотности на тех же участках после износа банкноты (ось ординат). При помощи Ibm обозначено значение пропускания чистой банкнотной бумаги неизношенной банкноты. Imax обозначает максимальный отклик датчика. Прямая 8 соответствует практически неизношенной банкноте, прямая 7 - банкноте с истертым красочным слоем, прямая 10 - банкноте с равномерным загрязнением, прямая 9 - загрязненной банкноте с истертым красочным слоем. Данная модель не отражает нелинейные искажения в передаче градаций оптической плотности. Однако, как показывает опыт, применение данной модели дает возможность существенно уменьшить различия признаков для банкнот одного класса и разной степени износа.

На Фиг.4b показано, каким образом видоизменяется положение банкноты в пространстве признаков по мере износа. Предполагается, что признаки X1, Х2 вычислены при помощи функции усреднения значения пикселей. Точка (Ibm, Ibm) соответствует наибольшим значениям признаков, достигаемых на чистой бумаге неизношенной банкноты. Точка О, напротив, соответствует полному отсутствию оптического отклика. Неизношенная банкнота изображена в пространстве признаков точкой К. При истирании банкноты ее положение смещается по прямой в сторону точки (Ibm, Ibm). При помощи точки L изображена незагрязненная банкнота с истертым красочным слоем. Аналогично, при загрязнении банкноты ее положение смещается по прямой в сторону точки О. При помощи точки N изображена загрязненная банкнота с неистертым красочным слоем. Точка М соответствует загрязненной банкноте с истертым красочным слоем. Уровень износа банкнот, изображенных точками L, М, N, предполагается предельно допустимым в обращении. Четырехугольник KLMN ограничивает реальные положения банкноты в пространстве признаков по мере ее износа, до тех пор пока износ не станет недопустимым.

Износ в соответствии с линейной моделью приводит к изменению гистограммы банкноты (Фиг.5). Гистограмма неизношенной банкноты показана на Фиг.5а. Износ можно охарактеризовать интервалом значений Ht и Нb, между которыми заключен интервал значений пропускания (отражения) банкноты. Загрязнение банкноты (Фиг.50) приводит к сжатию этого интервала и смещению его вниз, в то время как истирание банкноты (Фиг.5с) приводит к сжатию этого интервала и смещению его вверх. Комбинация истирания и загрязнения еще более сжимает интервал градаций и смещает его вниз (Фиг.5d). При вычислении каждого из признаков первоначально усредняют значения элементов двумерного массива цифрового образа, попадающих в соответствующую область. Таким образом, создается массив усредненных значений, в котором каждый элемент соответствует одному признаку. Затем этот массив корректируют таким образом, чтобы его значения лежали в интервале от 0 до максимальной величины Imax. Для этого производят линейное преобразование интервала исходных значений признаков [Hb, Ht] в новый интервал значений признаков от [0, Imax], по формуле:

В этой формуле Iin - значение признака до преобразования, Iout - значение признака после преобразования. Это преобразование применяют ко всем элементам массива признаков.

Линейное преобразование интервала [Hb, Ht] в интервал [0, Imax] приводит различные гистограммы банкнот одного класса (Фиг.5а-d) к практически идентичному виду (Фиг.5е), вне зависимости от их степени износа. После применения такого преобразования различия признаков между банкнотами одного класса, но разной степени износа становятся малыми. Ответственными за эти небольшие остаточные различия являются нелинейные изменения оптической плотности индивидуальных изношенных банкнот, а также локальный износ. Данные эффекты не учитываются в линейной модели износа, но, однако, и не создают существенных препятствий при классификации.

С точки зрения представления классов результатом коррекции значений признаков является уменьшение координат вектора допустимого отклонения по каждой из областей, а также уменьшение максимально допустимого значения расстояния DMTH.

На Фиг.6а показано распределение совокупности банкнот одного класса в пространстве признаков без применения коррекции. Для него характерно неполное заполнение модели, поскольку форма облака точек, представляющего класс, в соответствии с линейной моделью износа близка к четырехугольнику KLMN, представленному на Фиг.4b. На Фиг.6b показано распределение той же совокупности банкнот одного класса в пространстве признаков после применения коррекции. Видно, что размер класса уменьшился. Все точки четырехугольника KLMN, изображенного на Фиг.4b, после применения линейного преобразования интервала стягиваются в одну общую точку, расположенную в середине новой модели класса. Разброс точек в пределах модели и границы класса вызван эффектами, которые не учитываются линейной моделью износа.

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

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

Для того чтобы ускорить классификацию, во время вычисления расстояния проводят проверку, не превысила ли накапливаемая сумма значение максимально допустимого расстояния DMTH. В случае превышения прекращают дальнейшее вычисление расстояния и делают вывод о том, что банкнота не принадлежит заданному классу.

Одна из возможных последовательностей реализации классификации по варианту 1 показана на Фиг.7. Классификация начинается после получения цифрового образа банкноты. Первоначально (11) вычисляют вектор признаков банкноты, используя для этого ее цифровой образ и схему разделения на области. Затем выбирают класс для сопоставления (12) и вычисляют «манхеттенское расстояние» до этого класса (13). Полученное значение расстояния сравнивают с максимально допустимой величиной для этого класса (14). Если расстояние меньше либо равно максимально допустимой величины, то вносят класс в список возможных (15). Если есть еще известные классы, с которыми не проводилось сопоставление, то повторяют последовательность с шага 12. Если все известные классы уже использовались для сопоставления и список возможных классов пуст, то сообщают о том, что банкнота не принадлежит ни одному из известных классов (18). Если же список возможных классов не пуст, то производят ранжирование этих классов по значению расстояния до банкноты (16) и выбирают класс с минимальным расстоянием (17). Этот класс сообщается как результат классификации (19).

Перед выполнением заявленного способа по варианту 1 необходимо провести обучение и определить векторы центроида и отклонения для всех известных классов. Кроме того, требуется задать максимально допустимое расстояние до каждого из известных классов. Определение векторов центроида С и вектора отклонения для заданного класса производится в результате анализа обучающей совокупности банкнот этого класса. Для всех банкнот обучающей совокупности находят значения каждого из признаков. Затем анализируют значения Xj каждого j-го признака по всей совокупности банкнот и находят его минимальное Xj_min и максимальное Xj_max значение. Далее вычисляют компоненты и . Описанный здесь способ нахождения векторов центроида и отклонения представляет собой лишь один из возможных.

Необходимо отметить, что модель класса может быть задана и использоваться без понятия вектора центроида и вектора отклонения. Например, можно задаться моделью в виде декартова произведения ([X1_min, X1_min], [X2_min, X2_min]), которая будет равна ранее определенной нами как ([С1- 1, С1+ 1], [С2- 2, С2+ 2]). При таком задании возможно видоизменить способ вычисления расстояния таким образом, чтобы он давал тот же самый результат, не используя понятия векторов центроида и отклонения. Однако при этом нужно учитывать, что такое видоизменение способа классификации приводит к способу, эквивалентному заявленному по первому варианту.

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

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

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

Сигнатура характеризует соотношение между свойствами областей на банкноте. Если признаки выбраны таким образом, что соотношение между ними для банкнот одного класса практически неизменно, то сигнатуры таких банкнот будут совпадать в большинстве двоичных разрядов. Указанный выше простейший вид признака удовлетворяет такому условию. Действительно, износ банкноты в соответствии с линейной моделью будет вызывать изменение абсолютных значений признаков, но не будет менять соотношение «больше-меньше» между признаками. Напротив, для банкнот разных классов при соответствующем выборе областей соотношения «больше-меньше» между признаками будут различаться в большем количестве двоичных разрядов из-за различий рисунков банкнот. Таким образом, количество различающихся двоичных разрядов в сигнатурах может быть использовано в качестве меры различия банкнот.

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

В качестве расстояния от банкноты до класса используется специально определенная мера различия между сигнатурами анализируемой банкноты и центроида класса. Эта мера основывается на широко известном понятии «расстояния Хемминга». По определению «расстояние Хемминга» между двумя двоичными числами равно количеству различающихся между собой двоичных разрядов этих чисел. Например, расстояние между двоичными числами 0011 и 1010 равно 2, так как у них отличаются оба крайних разряда.

Для реализации способа 2 понятие «расстояния Хемминга» было модифицировано таким образом, чтобы дать возможность не учитывать различия в определенных разрядах сравниваемых двоичных чисел. Для этого введено понятие маски сравнения. Определенный разряд маски сравнения, равный 1, указывает на необходимость учета разницы двух сравниваемых чисел в таком же разряде. Напротив, 0 в определенном разряде маски сравнения указывает на то, что различие между двумя числами в этом разряде не должно учитываться при подсчете расстояния. Например, маска 1110 указывает на то, что необходимо учитывать различия во всех разрядах, кроме крайнего правого. Таким образом, модифицированное «расстояние Хемминга» между двоичными числами 0011 и 1010, с маской сравнения 1110, равно 1, поскольку учитывается только имеющаяся разница в одном, крайнем левом разряде.

Применение маски сравнения позволяет исключить из рассмотрения те разряды, которые соответствуют паре признаков, изменчивой в пределах одного класса. Для пар признаков, соотношение между которыми практически неизменно для всех банкнот одного класса, соответствующий разряд маски сравнения необходимо устанавливать равным 1. Напротив, для тех пар признаков, соотношение между которыми нестабильно в пределах заданного класса, разряд маски должен быть установлен в 0. Тогда при вычислении расстояния от банкноты до заданного класса будут учитываться только те разряды сигнатуры, которые практически неизменны для банкнот этого класса. Поэтому расстояние от банкнот заданного класса до этого класса будет малым. Расстояние от банкнот других классов будет больше, поскольку различия в разрядах сигнатуры между ними и центроидом класса имеются во многих, в том числе незамаскированных, разрядах сигнатуры.

На практике вычисление модифицированного «расстояния Хемминга» DH от банкноты с сигнатурой S до класса с центроидом С и маской сравнения М производится, например, следующим образом. Сначала производят побитовую операцию ИСКЛЮЧАЮЩЕЕ ИЛИ (XOR) между сигнатурой банкноты и центроидом класса. Затем при помощи побитовой операции И (AND) отбрасывают разряды, которые не нужно учитывать при подсчете расстояния. Общий результат этих операций можно записать как Z=(S XOR С) AND M. Если количество разрядов сигнатуры не превосходит разрядности слова процессора вычислительного устройства, то вычисление S обычно производится за две вычислительные операции процессора. В случае, если разрядность сигнатуры больше разрядности слова процессора, вычисление S производят последовательно, в несколько этапов. При этом разбивают S, С и М на отрезки битов, вмещающиеся в слово процессора.

Расстояние DH определяют, подсчитывая число единичных битов в двоичном числе Z. Это может быть выполнено разными способами. Одним из самых эффективных является разбиение Z на отдельные байты и подсчет числа единичных битов в каждом байте при помощи 256-строчной таблицы. Таблица содержит количество единичных битов для всех возможных значений байта. Результаты, полученные для каждого отдельного байта, суммируются и дают значение расстояния DH. Для сигнатуры, которая полностью размещается в Р байтах, требуется Р обращений к таблице и Р-1 операций сложения. Таким образом, вычисление расстояния DH между банкнотой и классом в соответствии со вторым вариантом способа является очень быстрой и вычислительно несложной операцией.

Для принятия решения о возможности принадлежности банкноты к данному классу сравнивают найденное значение расстояния DH с максимально допустимым DHTH для данного класса. Если расстояние превосходит максимально допустимое, то судят о невозможности принадлежности банкноты данному классу. В противном случае говорят о возможной принадлежности банкноты к данному классу.

Процедуру определения расстояния DH от банкноты до класса проводят для всех известных классов. В результате суждение о возможности принадлежности к какому-либо классу может быть вынесено для одного или нескольких известных классов либо ни для одного из известных классов.

Совершенно аналогично варианту 1, в случае заключения о возможности принадлежности банкноты нескольким классам, необходимо провести либо дополнительное уточнение класса по дополнительным признакам, либо определить класс по результатам ранжирования расстояния. В последнем случае класс с минимальным расстоянием до банкноты признается результатом классификации.

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

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

Формирование сигнатуры банкноты проиллюстрировано Фиг.8. На Фиг.8а дано изображение банкноты 5 Евро в проходящем красном свете, взятое из цифрового образа банкноты. На него наложена регулярная схема разбиения банкноты на одинаковые области квадратной формы. Области расположены в виде рядов и колонн и граничат друг с другом. Схема разбиения центрируется по центральной точке изображения банкноты. Таблица на Фиг.8b показывает усредненные значения пикселей по областям, используемые в качестве признаков. Каждой области соответствует отдельная клетка таблицы. Для определения разрядов сигнатуры выбираются все пары граничащих областей, расположенные вертикально друг над другом. Разряд сигнатуры равен 1, если в соответствующей ему паре признак верхней области больше признака нижней области. В противном случае разряд сигнатуры равен 0. Полный набор разрядов сигнатуры, сформированный таким образом, изображен на Фиг.8с. Стрелками показано, как пара признаков областей формирует определенный разряд. Аналогичным образом сигнатура может быть дополнена разрядами, формируемыми в результате сравнения признаков соседних областей, расположенных горизонтально. Разряд сигнатуры равен 1, если в соответствующей ему паре признак левой области больше признака правой области. В противном случае разряд сигнатуры равен 0.

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

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

Для того чтобы сделать сравнение между собой расстояний до различных классов более представительным, следует ввести дополнительную зависимость расстояния от количества единичных разрядов в маске сравнения. Приведем пример такой дополнительной зависимости. Пусть k - разрядность сигнатуры S, а m - количество единичных разрядов маски. После вычисления модифицированного «расстояния Хемминга», его дополнительно умножают на коэффициент . Как следствие, влияние отдельных пар областей на расстояние будет больше для тех случаев, когда при вычислении расстояния принимают во внимание меньшее количество пар областей.

Одна из возможных последовательностей реализации классификации по варианту 2 показана на Фиг.9. Классификация начинается после получения цифрового образа банкноты. Первоначально (20) вычисляют вектор признаков банкноты. Затем выбирают класс для сопоставления (12) и вычисляют модифицированное «расстояние Хемминга» до этого класса (21). Полученное значение расстояния сравнивают с максимально допустимой величиной для этого класса (22). Если расстояние меньше либо равно максимально допустимой величины, то вносят класс в список возможных (15). Если есть еще известные классы, с которыми не проводилось сопоставление, то повторяют последовательность с шага 12. Если все известные классы уже использовались для сопоставления и список возможных классов пуст, то сообщают о том, что банкнота не принадлежит ни одному из известных классов (18). Если же список возможных классов не пуст, то о составляющих его классах сообщается как о результате классификации (23). Данная последовательность предполагает уточнение класса после классификации, поскольку результатом классификации может оказаться более чем один класс.

Перед выполнением заявленного способа по варианту 2 необходимо провести обучение и определить сигнатуру центроида и маску сравнения для каждого из известных классов. Кроме того, требуется задать максимально допустимое расстояние до каждого из известных классов. Для определения центроида класса и маски сравнения вычисляют сигнатуры для всех банкнот из обучающей совокупности для данного класса. Затем последовательно анализируют каждый из битов сигнатур и строят результирующую сигнатуру центроида. Для каждого разряда находят частоты, с которой в этом разряде встречается «0» и встречается «1» в сигнатурах банкнот обучающей совокупности. Каждому разряду центроида назначают то значение, которое наиболее часто встречается в сигнатурах банкнот обучающей совокупности.

Затем приступают к поразрядному формированию маски сравнения М. Вначале задают эмпирически определяемый порог достоверности, лежащий в пределах от 0 до 0,5. Для каждого разряда сравнивают наименьшую из двух частот появления значения «0» либо значения «1» в этом разряде с порогом достоверности. Единичное значение в соответствующем разряде маски назначают в том и только том случае, когда наименьшая из этих двух частот не превосходит порога достоверности. Таким образом, в разрядах с высокой степенью неопределенности устанавливается 0, в то время как в разрядах с низкой степенью неопределенности устанавливается 1. Описанный способ выбора центроида и маски сравнения является одним из многих возможных и приведен здесь только для иллюстрации подготовки исходных данных для проведения классификации по способу 2.

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

Как видно из описания вариантов изобретения, вариант 1 обеспечивает наиболее высокое качество классификации, в то время как вариант 2 обеспечивает наиболее высокое быстродействие. Для того чтобы объединить преимущества обоих вариантов, классификация по варианту 1 может быть дополнена предварительной классификацией, использующей идеи, положенные в основу варианта 2 (см. Фиг.10, 11). После вычисления вектора признаков банкноты (11) производят вычисление ее сигнатуры (20). Разряды сигнатуры вычисляются на основании соотношений «больше-меньше» между назначенными парами компонентов вектора признаков. Таким образом, используются единая схема разбиения на области и одна и та же функция получения признака для заданной области.

Перед тем как вычислить «манхеттенское расстояние» DM между банкнотой и заданным классом, предварительно вычисляют (21) модифицированное «расстояние Хемминга» DH между банкнотой и этим же классом. Затем сравнивают (22) полученное модифицированное «расстояние Хемминга» DH с максимально допустимым значением DHTH этого расстояния для заданного класса. Если модифицированное «расстояние Хемминга» превышает DHTH, немедленно делают заключение о том, что банкнота не принадлежит заданному классу. В этом случае дальнейшую проверку «манхеттенского расстояния» до данного класса не проводят ввиду ее бессмысленности и переходят к выбору следующего класса (12). Если же, напротив, DH DHTH, то продолжают проверку, вычисляют (13) «манхеттенское расстояние» DM и сравнивают (14) его с максимально допустимым значением DMTH. Если DM не превосходит DMTH, то делают вывод о том, что банкнота может принадлежать к заданному классу, и вносят класс в число возможных классов (15). Если же расстояние больше, чем DMTH, то делают вывод о том, что банкнота не может принадлежать заданному классу, и переходят к выбору следующего из известных классов (12). Если все известные классы уже проанализированы, проверяют, был ли хоть один из них отобран как возможный. Если список возможных классов пуст, то сообщают о том, что банкнота не принадлежит ни одному классу (18). Если же были отобраны возможные классы, то ранжируют их (16) по расстоянию DM и выбирают (17) класс-результат с наименьшим значением DM. В завершение классификации сообщают, что банкнота принадлежит этому классу (19).

Таким образом, вычисление «махеттенского расстояния» производится только в том случае, когда проверка по модифицированному «расстоянию Хемминга» допускает принадлежность банкноты к заданному классу. Для подавляющего большинства классов проводится только быстрая проверка по модифицированному «расстоянию Хемминга», которая заканчивается отклонением класса. Вычисление и модифицированного «расстояния Хемминга», и «манхеттенского расстояния» производится для очень небольшого числа классов. Поэтому классификация имеет быстродействие, лишь несколько превышающее время классификации по варианту 2. В случае заключения о возможной принадлежности банкноты к заданному классу решение основывается на совместном применении критериев, предусмотренных как вариантом 1, так и вариантом 2. Поэтому уверенность в результате классификации в этом случае выше, чем по отдельности для результатов классификации по варианту 1 и по варианту 2.

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

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

Датчики сканирования расположены в виде линейного массива (линейки) фотодатчиков с одной стороны банкнотопроводного тракта и двухволнового осветителя на противоположной стороне тракта. Излучение осветителя направлено через толщину тракта на линейку фотодатчиков. Массив фотодатчиков и двухволновой осветитель выполнены таким образом, что ими регистрируется пропускание света банкнотой по всей ширине тракта. Массив фотодатчиков оснащен оптической системой, обеспечивающей перенос изображения поверхности банкноты на поверхность линейки фотодатчиков. Двухволновой осветитель синхронно с вращением механизма попеременно излучает либо на длине волны в видимом диапазоне, либо на длине волны в инфракрасном (ИК) диапазоне. Период переключения осветителя соответствует перемещению банкноты на 1 миллиметр. Таким образом, при перемещении банкноты на каждый миллиметр перемещения линейка фотодатчиков регистрирует пропускание банкноты как в ИК излучении, так и видимом свете. Уровень засветки фотодатчиков таков, что они работают в линейном режиме при прохождении света через банкноту и в режиме насыщения при прохождении света через ту часть тракта, где нет банкноты.

Встроенное программное обеспечение процессора хранится в ПЗУ. Оно управляет перемещением банкнот и осуществляет связь с пользователем через пользовательский интерфейс. Кроме того, оно реализует функции сканирования и классификации.

На Фиг.12 показана общая последовательность действий при пересчете банкнот под управлением встроенного программного обеспечения. Пересчет банкнот начинается, как только в приемный карман счетчика помещается пачка банкнот. Механизм запускается (23) и начинает подачу банкнот по тракту в направлении датчиков сканирования. Как только банкнота входит в зону датчиков, начинается ее сканирование (25). При продвижении банкноты на 1 мм по тракту программа дважды считывает оцифрованные значения сигналов фотодатчиков линейки - один раз для пропускания в ИК-излучении, а другой раз - для пропускания в видимом свете. Эти оцифрованные значения размещаются в двух соответствующих массивах в ОЗУ процессора. Сканирование завершается, как только программа определяет, что все фотодатчики линейки находятся в насыщении. В результате сканирования в ОЗУ размещается цифровой образ банкноты, содержащий один двумерный массив для пропускания ИК-излучения и другой двумерный массив для пропускания видимого света.

После завершения сканирования программа переходит к классификации банкноты на основании ее цифрового образа (26). Классификация происходит в соответствии с вариантами заявленного изобретения, например так, как показано на фиг.7, либо фиг.9, либо фиг.10, 11. По завершении классификации может быть выполнена дополнительная операция уточнения результата классификации (27). Она является обязательной, если классификация может сообщить о возможной принадлежности банкноты к более чем одному классу, как, например, при реализации согласно фиг.9. При реализации классификации (26) согласно фиг.7 либо фиг.10 результатом классификации может быть не более одного класса, поэтому операция (27) не является строго обязательной. В этом случае операция (27) может потребоваться для повышения уверенности в результате классификации за счет дополнительной проверки по большему количеству признаков.

Далее определяются (28) действия, необходимые по результату классификации (26) и его уточнения (27), если таковое проводилось. В зависимости от настроек счетчика, введенных пользователем, счетчик может остановить (32) механизм либо продолжать счет. Остановка может быть определена, например, в случае, если банкнота не отнесена ни к одному классу. Если принято решение продолжить счет, то счетчик выполняет действия (30) по учету банкноты, например добавляет ее номинал к общей денежной сумме пересчитываемой пачки.

В этой точке последовательности проверяется (31), имеются ли еще банкноты в приемном кармане. Если приемный карман не пуст, то программа переходит к ожиданию (24) входа очередной банкноты в зону датчиков. Если же приемный карман пуст и, таким образом, все банкноты пересчитаны, механизм останавливается (32).

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