Способ кодирования папиллярного узора
Изобретение относится к области криминалистики и предназначено для кодирования отпечатков папиллярных узоров. Техническим результатом является повышение точности идентификации объекта по рисунку папиллярного узора. Способ кодирования папиллярного узора заключается в выделении на отпечатке линий и особенностей, нумерации особенностей, определении для каждой особенности угла направления, координат, типа особенности и двух проекций на соседние линии, построении для каждой точки, исключая особенности, каждой линии топологической характеристики в виде нумерованного набора пар, представленных событием и номером особенности, и объединении одинаковых топологических характеристик. В топологической характеристике, по крайней мере для одного события, измеряют длину связи при движении по линии от сечения до точки, в которой детектируется событие, и назначают для этого события измеренную длину связи, а при объединении топологических характеристик рассчитывают новую длину связи для этого события на основе назначенных ранее длин связей топологических характеристик, участвующих в операции объединения. 4 з.п. ф-лы, 4 ил., 2 табл.
Изобретение относится к области криминалистики и предназначено для кодирования отпечатков папиллярных узоров пальцев, ладоней и ступней ног. Его использование позволяет получить технический результат в виде повышения точности идентификации объекта.
Известен способ кодирования папиллярных узоров, заключающийся в кручении условного вектора вокруг заданного центра и фиксации шестнадцатеричного кода при прохождении этого вектора через особенность (заявка РСТ №87/01224, МПК G06 K9/00, опубл. 1987).
Такой способ кодирования неустойчив, так как результаты фиксации кода зависят от порядка обхода особенностей, который меняется при смещении центра. Поэтому точность идентификации объекта невысокая.
Известен способ кодирования папиллярного узора, содержащего n особенностей, заключающийся в определении для каждой особенности вектора направления, координат, типа особенности, вектора и величины кривизны папиллярных линий в окрестности особенности, масштабной характеристики как среднего расстояния между папиллярными линиями в окрестности особенности, а также расстояния и гребневого счета от особенности до остальных n-1 особенностей, встречающихся в порядке вращения условного вектора вокруг особенности, начиная с вектора направления самой особенности, и углов, которые образуются между вектором направления особенности и условным вектором при встрече условного вектора с очередной из n-1 особенностей (патент РФ №2054197, МПК G06K 9/46, опубл. 1992).
Этот способ кодирования отпечатка неустойчив по четырем причинам: гребневый счет для особенностей, расположенных вдоль одной прямой, не детектируется; группы особенностей, близких к одной прямой, перестраиваются для разных отпечатков одного и того же пальца из-за нелинейных деформаций отпечатков; гребневый счет не оценивается точно в случае расположения особенностей вдоль папиллярных линий; гребневый счет не оценивается точно в области петель, дельт, завитков и карманов. Поэтому точность идентификации объекта невысокая.
Известен способ кодирования отпечатка папиллярного узора, заключающийся в выделении на отпечатке линий и особенностей, нумерации особенностей, определении для каждой особенности угла направления, координат, типа особенности, вектора кривизны линий в окрестности особенности, масштабной характеристики в окрестности особенности, топологической характеристики, представленной нумерованным набором пар, образованных событием в виде числа и номером соответствующей особенности, причем топологическая характеристика детектируется при движении по линиям-связям от сечения, проходящего через особенность перпендикулярно линиям (патент РФ №2185660, МПК 7 G06K 9/52, опубл. 2002).
Недостатком способа является то, что порядок нумерации связей для окончания и разветвления линий различается. Поэтому при мутации окончания в разветвление или разветвления в окончание связи, образующие набор пар, перенумеровывается. Кроме того особенности, расположенные близко к сечению при измерении топологической характеристики, могут переходить через сечение по причинам механизма следообразования. Эти нежелательные эффекты снижают точность идентификации объекта.
Наиболее близким к изобретению является способ кодирования отпечатка папиллярного узора, заключающийся в выделении на отпечатке линий и особенностей, нумерации особенностей, определении для каждой особенности угла направления, координат и типа особенности, вектора кривизны линий в окрестности особенности, масштабной характеристики в окрестности особенности, двух проекций на соседние линии, построении для каждой точки каждой выделенной линии, исключая особенности, топологической характеристики, представленной в виде нумерованного набора пар из события и номера соответствующей особенности, причем событие детектируют при движении по линии от сечения, проходящего через точку линии на глубину нескольких линий перпендикулярно касательным к пересекаемым линиям, и объединении одинаковых топологических характеристик (патент РФ №2321057, МПК G06K 9/52, А61В 5/117, опубл. 27.03.2008, бюл. №9). Этот способ выбран в качестве прототипа.
Способ кодирования по прототипу более устойчив к деформации и другим искажениям папиллярного узора по сравнению с аналогами. Однако в топологической характеристике отсутствует длина связей. При разрезании сечением одной линии образуются две связи. На линейных участках узора длина связей описывает расстояние от особенностей до сечения топологической характеристики, и это расстояние не рассчитывается на основе геометрических координат особенностей, так как сечение обычно изгибается, а не идет по прямой линии. Сумма длин связей, располагающихся на одной линии, определяет расстояние по линии между особенностями. Для закручивающихся линий геометрическое расстояние между особенностями может быть маленькое, а расстояние по линиям - большое. Несовпадение геометрических расстояний между особенностями и длины линии между особенностями как суммы длин связей служит важной идентификационной характеристикой дактилоскопического узора. Отсутствие длин связей в топологической характеристике является существенным недостатком прототипа.
Задачей, решаемой настоящим изобретением, является повышение точности идентификации объекта по рисунку папиллярного узора.
Достигается это тем, что на рисунке папиллярного узора выделяют линии и особенности, нумеруют особенности, определяют для каждой особенности угол направления, координаты, тип особенности и две проекции на соседние линии, строят для каждой точки, исключая особенности, каждой линии топологическую характеристику в виде нумерованного набора пар, представленных событием и номером особенности, причем событие детектируют при движении по линии от сечения, проходящего через точку, для которой строится топологическая характеристика, вправо и влево на глубину нескольких линий перпендикулярно касательным к пересекаемым линиям, объединяют одинаковые топологические характеристики и дополнительно в топологической характеристике по крайней мере одному событию назначают длину связи, которую измеряют при движении по линии от сечения до точки, в которой детектируется событие, длину связи при объединении топологических характеристик не учитывают, а рассчитывают новую длину связи на основе назначенных длин связей топологических характеристик, участвующих в операции объединения.
Кроме того, длины связей назначают для событий, порождаемых особенностью или проекцией от особенности.
Кроме того, длины связей назначают для событий, порождаемых особенностью.
Кроме того, топологические характеристики строят только для тех точек линий, которые располагаются вблизи особенностей.
Кроме того, выделяют области информативные и неинформативные, а линии и особенности располагают в информативной области.
Сущность предлагаемого способа иллюстрируется четырьмя фигурами и двумя таблицами:
на фиг.1 показана особенность типа окончания с углом направления особенности, ориентированным вдоль линии, и проекциями на соседние папиллярные линии 100 и 200;
на фиг.2 показана особенность типа разветвления с углом направления особенности и проекциями на соседние папиллярные линии 100 и 200;
на фиг.3 от точки А линии, на которой лежит окончание 30, проведено сечение через другие линии, которые разрезаны сечением, пронумерованы и образуют связи 0-17, начинающиеся от сечения, на которых располагаются особенности 20-27 и 30 с двумя проекциями от каждой;
на фиг.4 от точки В линии, которая замыкается в разветвление 31, проведено сечение через другие линии, которые разрезаны сечением, пронумерованы и образуют связи 0-17, начинающиеся от сечения, на которых располагаются особенности 20-27 и 31 с двумя проекциями от каждой;
в табл.1 показана топологическая характеристика для точки А линии, сечение через которую представлено на фиг.3, с указанием на нумерованных связях событий в виде двоичных чисел, номеров особенностей и длин связей;
в табл.2 показана топологическая характеристика для точки В линии, сечение через которую представлено на фиг.4, с указанием на нумерованных связях событий в виде двоичных чисел, номеров особенностей и длин связей.
Рассмотрим последовательность выполняемых действий в заявляемом способе.
В области ясного отпечатка выделяют папиллярные линии, на которых детектируют особенности: окончания и разветвления (фиг.1, 2). Каждую особенность нумеруют числом и определяют координатами, углом направления в сторону увеличения числа линий, типом особенности (окончание, разветвление). Известны и другие признаки особенностей, такие как вектор кривизны и масштабная характеристика, однако они для решения поставленной задачи несущественны. От каждой особенности определяют проекции вправо и влево перпендикулярно углу направления особенности на соседние линии 100 и 200 (фиг.1, 2).
Через каждую точку, исключая разветвления и окончания, каждой линии, выделенной на рисунке папиллярного узора, проводят сечение вправо и влево на глубину нескольких линий (обычно 1-8 линий вправо и столько же влево) перпендикулярно касательным к пересекаемым линиям. Разрезанные сечением линии образуют связи, которые нумеруют по спирали, разворачивающейся по часовой стрелке. На фиг.3 пронумерованы связи 0-17, на фиг.4 - связи 0-17. Одна линия образует две связи.
Для сечения строят топологическую характеристику методом последовательного прослеживания по каждой связи хода связи от сечения до встречи с другой особенностью, расположенной на связи, или с проекцией от особенности на связи. При этом синтезируются следующие возможные события, детектируемые на связях и представленные в двоичном коде:
0000 - нет особенности или проекции от особенности на связи (линия обрывается на краю отпечатка);
1101 - на связи проекция от окончания, расположенного справа от связи по ходу прослеживания связи, угол направления окончания ориентирован навстречу ходу по связи;
1001 - на связи проекция от окончания, расположенного справа от связи по ходу прослеживания связи, угол направления окончания ориентирован по ходу по связи;
1110 - на связи проекция от окончания, расположенного слева от связи по ходу прослеживания связи, угол направления окончания ориентирован навстречу ходу по связи;
1010 - на связи проекция от окончания, расположенного слева от связи по ходу прослеживания связи, угол направления окончания ориентирован по ходу по связи;
0101 - на связи проекция от разветвления, расположенного справа от связи по ходу прослеживания связи, угол направления разветвления ориентирован навстречу ходу по связи;
0001 - на связи проекция от разветвления, расположенного справа от связи по ходу прослеживания связи, угол направления разветвления ориентирован по ходу по связи;
0110 - на связи проекция от разветвления, расположенного слева от связи по ходу прослеживания связи, угол направления разветвления ориентирован навстречу ходу по связи;
0010 - на связи проекция от разветвления, расположенного слева от связи по ходу прослеживания связи, угол направления разветвления ориентирован по ходу по связи;
1111 - окончание на связи, угол направления окончания ориентирован навстречу ходу по связи;
0011 - разветвление на связи, угол направления разветвления ориентирован по ходу по связи;
0111 - разветвление на связи, образованной линией, касательная к которой образует минимальный угол при повороте угла направления разветвления на связи против часовой стрелки;
1011 - разветвление на связи, образованной линией, касательная к которой образует минимальный угол при повороте угла направления разветвления на связи по часовой стрелке;
1100 - связь по линии замыкается, какая-либо особенность или проекция от особенности отсутствует.
С событием как числом, детектированным на связи, ассоциируют номер особенности, породившей событие. События однозначно привязывают к номеру связи. Для событий 0000 и 1100 номера особенностей не записывают. Нумерованный набор связей, для каждой из которых детектируется событие, с которым ассоциируется номер особенности, есть топологическая характеристика, которая для точки А на фиг.3 представлена в табл.1, а для точки В на фиг.4 представлена в табл.2. Максимальное число особенностей в таблице не превышает числа связей.
Обычно рисунок папиллярных линий при компьютерной обработке изображений представляют в виде скелета - связанную линию толщиной в одну точку. Тогда прослеживание связи сводится к движению по скелету от сечения в заданном направлении, следуя всем изгибам скелетных линий. При движении по связи подсчитывается количество шагов, сделанных до точки, в которой детектируется событие. Количество шагов есть длина связи (обычно 10-100 шагов). На фиг.3 и фиг.4 показана длина L0 связи 0, длина L4 связи 4 и длина L5 связи 5. Таким образом, каждому событию назначается длина связи (см. табл.1 и табл.2). Для событий 0000 и 1100 длина связи измеряется подобно, просто анализируется обрыв связи (граница узора) или возвращение по связи в исходную точку. Сумма длин связей, лежащих на одной линии, определяет расстояние между особенностями по линиям, которое обычно заметно отличается от геометрических расстояний между особенностями. Для события 0000 длина связи (если она записана в топологической характеристике) определяет вероятную информативную область узора, не содержащую особенности, что является важным идентификационным признаком узора.
Действия по построению топологических характеристик выполняются для всех точек выделенных линий отпечатка, исключая особенности. Так как при компьютерной обработке рисунок линий обычно представляют в виде скелета линий, то количество топологических характеристик счетное. На фиг.3 внизу жирной двунаправленной стрелкой показана зона, умещающаяся между особенностями 30 и 25, в пределах которой для точки А при смещении точки по линии синтезируется топологическая характеристика с одинаковыми событиями и номерами особенностей на связях, но изменяющимися длинами связей. Аналогичная зона между особенностями 31 и 25 для точки В указана внизу на фиг.4. Топологические характеристики, у которых на одноименных связях располагаются одинаковые события и номера особенностей, считают одинаковыми в целом и объединяют. При объединении топологических характеристик для каждого события рассчитывают новую длину связи. При этом новая длина связи может соответствовать длине одноименной связи одной из топологических характеристик, участвующей в операции объединения. Например, на фиг.3 для всех объединяемых в зоне топологических характеристик новая длина связи L0=L0 (точка А). Или новая длина связи есть функция от длин одноименных связей объединяемых топологических характеристик, обычно как среднее значение.
Общее количество объединенных топологических характеристик невелико и достигает величины 100-1000 для контактного отпечатка пальца с количеством особенностей 20-100. Объединенные топологические характеристики соответствуют отрезкам линий, автоматически определяемым в результате операции объединения. На этом кодирование отпечатка папиллярного узора заканчивают. Для событий 0000 и 1100 длину связей можно не записывать. При этом остаются события: 1101, 1001, 1110, 1010, 0101, 0001, 0110, 0010, 1111, 0011, 0111, 1011. Это приводит к построению эффективной объединенной топологической характеристики, ориентированной на события, порождаемые и особенностями, и проекциями от особенностей.
Длину связей можно записывать только для событий: 1111, 0011, 0111, 1011. Это приводит к построению экономной объединенной топологической характеристики, ориентированной на события, порождаемые особенностями, что несколько обедняет топологическую характеристику, зато заметно экономит объем памяти. Даже в экономном виде предлагаемый способ содержит много дополнительной информации, например можно вычислить расстояние по линии между особенностями, а короткая длина связи может привести к перестройке сечения: сечение, вероятно, может пройти либо до, либо после особенности. При идентификации рисунка линий это можно учесть.
Небольшое количество "ядерных" топологических характеристик можно строить для точек линий в непосредственной окрестности особенностей (радиус 20-40 точек). Это сокращает время анализа рисунка линий и объем требуемой памяти для хранения данных.
Линии, связи и особенности располагаются в информативных областях, отличающихся от неинформативных областей, в которых особенности и линии не выделяются из-за неясного рисунка линий. Поэтому разделение площади узора на информативные и неинформативные области существенно. Прерывание линии в неинформативной области сопровождается событием 0000, для которого длина связи может отсутствовать (прочерк в таблицах).
Отметим преимущества предлагаемого способа кодирования. Здесь сохраняются все достоинства прототипа, однако топологические характеристики дополняются длинами связей, на основе которых рассчитывается длины линий между особенностями, которые не совпадают с геометрическими расстояниями между особенностями в области изгиба и кручения линий. Длины связей не рассчитываются из координат особенностей, так как сечение изгибается, следуя структуре узора, а сам ход сечения в топологической характеристике неизвестен. Кроме того, длины связей измеряются до границ узора, что позволяет описать обширные области узора, не содержащие особенности. Это существенно обогащает описание папиллярного узора, а операция объединения топологических характеристик обеспечивает устойчивость результата кодирования к деформациям и искажениям рисунка линий. Поэтому повышается точность идентификации объекта.
Способ кодирования папиллярного узора реализуется в виде последовательности действий, выполняемых на компьютере, и может быть применен в криминалистике, в системах предотвращения несанкционированного доступа в охраняемые помещения, при идентификации личности человека, пользующегося кредитной картой.
СПОСОБ КОДИРОВАНИЯ ПАПИЛЛЯРНОГО УЗОРА
| Таблица 1 | |||
| Номер связи | Событие | Особенность | Длина связи |
| 0 | 1110 | 22 | L0 |
| 1 | 1111 | 30 | L1 |
| 2 | 1110 | 30 | L2 |
| 3 | 1111 | 22 | L3 |
| 4 | 0001 | 21 | L4 |
| 5 | 1101 | 30 | L5 |
| 6 | 1010 | 24 | L6 |
| 7 | 0010 | 25 | L7 |
| 8 | 0011 | 21 | L8 |
| 9 | 1111 | 23 | L9 |
| 10 | 1010 | 26 | L10 |
| 11 | 0011 | 25 | L11 |
| 12 | 0010 | 21 | L12 |
| 13 | 1010 | 20 | L13 |
| 14 | 1111 | 27 | L14 |
| 15 | 0001 | 25 | L15 |
| 16 | 0000 | - | - |
| 17 | 1001 | 20 | L17 |
| Таблица 2 | |||
| Номер связи | Событие | Особенность | Длина связи |
| 0 | 1110 | 22 | L0 |
| 1 | 1011 | 31 | L1 |
| 1 | 0111 | 31 | L2 |
| 3 | 1111 | 22 | L3 |
| 4 | 0001 | 21 | L4 |
| 5 | 0101 | 31 | L5 |
| 6 | 0110 | 31 | L6 |
| 7 | 0010 | 25 | L7 |
| 8 | 0011 | 21 | L8 |
| 9 | 1111 | 23 | L9 |
| 10 | 1010 | 26 | L10 |
| 11 | 0011 | 25 | L11 |
| 12 | 0010 | 21 | L12 |
| 13 | 1010 | 20 | L13 |
| 14 | 1111 | 27 | L14 |
| 15 | 0001 | 25 | L15 |
| 16 | 0000 | - | - |
| 17 | 1001 | 20 | L17 |
1. Способ кодирования папиллярного узора, заключающийся в выделении на рисунке линий и особенностей, нумерации особенностей, определении для каждой особенности угла направления, координат, типа особенности и двух проекций на соседние линии, построении для каждой точки, исключая особенности, каждой линии топологической характеристики в виде нумерованного набора пар, представленных событием и номером особенности, причем событие детектируют при движении по линии от сечения, проходящего через точку, для которой строится топологическая характеристика, вправо и влево на глубину нескольких линий перпендикулярно касательным к пересекаемым линиям, объединении одинаковых топологических характеристик, отличающийся тем, что в топологической характеристике по крайней мере для одного события измеряют длину связи при движении по линии от сечения до точки, в которой детектируется событие, и назначают для этого события измеренную длину связи, а при объединении топологических характеристик рассчитывают новую длину связи для этого события на основе назначенных ранее длин связей топологических характеристик, участвующих в операции объединения.
2. Способ кодирования папиллярного узора по п.1, отличающийся тем, что длины связей назначают для событий, порождаемых особенностью или проекцией от особенности.
3. Способ кодирования папиллярного узора по п.1, отличающийся тем, что длины связей назначают для событий, порождаемых особенностью.
4. Способ кодирования папиллярного узора по любому из пп.1-3, отличающийся тем, что топологические характеристики строят только для тех точек линий, которые располагаются вблизи особенностей.
5. Способ кодирования папиллярного узора по любому из пп.1-3, отличающийся тем, что выделяют области информативные и неинформативные, а линии и особенности располагают в информативной области.
