СПОСОБ, УСТРОЙСТВО И КОМПЬЮТЕРНЫЙ ПРОГРАММНЫЙ ПРОДУКТ ДЛЯ СОПОСТАВЛЕНИЯ ОТПЕЧАТКОВ ПАЛЬЦЕВ Российский патент 2012 года по МПК G06K9/00 G06F17/30 

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

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

Описание предшествующего уровня техники

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

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

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

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

- пластичности пальца, например отпечаток пальца не является одинаковым, если палец сильно надавливает на поверхность, по сравнению с отпечатком пальца, когда палец только слегка надавливает на поверхность;

- отпечаток пальца искажается из-за сырости, грязи, влаги и т.д. на поверхности или на пальце;

- размера области соприкосновения между пальцем и поверхностью;

- угла поворота пальца.

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

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

Сущность изобретения

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

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

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

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

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

Чередование может содержать чередование всех битов из упомянутого множества битов.

Чередование может содержать побитовое чередование множества битов.

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

В варианте осуществления присваивание может содержать присваивание соответствующего двоичного числа a₃ a₂ a₁ a₀, b₃ b₂ b₁ b₀, c₃ c₂ c₁ c₀, d₃ d₂ d₁ d₀ … N₃ N₂ N₁ N₀ каждой из множества характерных особенностей, и формирование может содержать формирование числового представления посредством размещения множества битов в следующем порядке: N₃… d₃ C₃ b₃ a₃ N₂… d₂ c₂ b₂ a₂ N₁… d₁ c₁ b₁ a₁ N₀… d₀ c₀ b₀ a₀.

В другом варианте осуществления присваивание может содержать присваивание соответствующего двоичного числа a₃ a₂ a₁ a₀, b₃ b₂ b₁ b₀, c₃ c₂ c₁ c₀, d₃ d₂ d₁ d₀ … N₃ N₂ N₁ N₀ каждой из множества характерных особенностей, а формирование может содержать формирование числового представления посредством размещения множества битов в следующем порядке: a₃ b₃ c₃ d₃… N₃ a₂ b₂ c₂ d₂… N₂ a₁ b₁ C₁ d₁… N₁ a₀ b₀ C₀ d₀… N₀.

Еще в одном варианте осуществления присваивание может содержать присваивание соответствующего двоичного a₇ a₆ a₅ a₄ a₃ a₂ a₁ a₀, b₇ b₆ b₅ b₄ b₃ b₂ b₁ b₀, c₇ c₆ c₅ c₄ c₃ c₂ c₁ c₀, d₇ d₆ d₅ d₄ d₃ d₂ d₁ d₀ … N₇ N₆ N₅ N₄ N₃ N₂ N₁ N₀ каждой из множества характерных особенностей, а формирование может содержать формирование числового представления посредством размещения множества битов в следующем порядке: N₇… d₇ C₇ b₇ a₇ N₆… d₆ c₆ b₆ a₆ N₅… d₅ c₅ b₅ a₅ N₄… d₄ c₄ b₄ a₄ N₃… d₃ C₃ b₃ a₃ N₂… d₂ c₂ b₂ a₂ N₁… d₁ c₁ b₁ a₁ N₀… d₀ c₀ b₀ a₀.

Еще в одном варианте осуществления присваивание может содержать присваивание соответствующего двоичного числа a₇ a₆ a₅ a₄ a₃ a₂ a₁ a₀, b₇ b₆ b₅ b₄ b₃ b₂ b₁ b₀, c₇ c₆ c₅ c₄ c₃ c₂ c₁ c₀, d₇ d₆ d₅ d₄ d₃ d₂ d₁ d₀ … N₇ N₆ N₅ N₄ N₃ N₂ N₁ N₀ каждой из множества характерных особенностей, а формирование может содержать формирование числового представления посредством размещения множества битов в следующем порядке: a₇ b₇ c₇ d₇… N₇ a₆ b₆ c₆ d₆… N₆ a₅ b₅ c₅ d₅… N₅ a₄ b₄ c₄ d₄… N₄ a₃ b₃ c₃ d₃… N₃ a₂ b₂ c₂ d₂… N₂ a₁ b₁ c₁ d₁… N₁ a₀ b₀ c₀ d₀… N₀.

В другом варианте осуществления присваивание может содержать присваивание соответствующего двоичного числа a₇ a₆ a₅ a₄ a₃ a₂ a₁ a₀, b₇ b₆ b₅ b₄ b₃ b₂ b₁ b₀, c₇ c₆ c₅ c₄ c₃ c₂ c₁ c₀, d₇ d₆ d₅ d₄ d₃ d₂ d₁ d₀ … N₇ N₆ N₅ N₄ N₃ N₂ N₁ N₀ каждой из множества характерных особенностей, а формирование может содержать формирование числового представления посредством размещения множества битов в следующем порядке: a₇ a₆ a₅ a₄ a₃ a₂ a₁ a₀ a₇ b₇ c₇ d₇… N₇ b₆ c₆ d₆… N₆ b₅ c₅ d₅… N₅ b₄ c₄ d₄… N₄ b₃ c₃ d₃… N₃ b₂ c₂ d₂… N₂ b₁ C₁ d₁…N₁ b₀ c₀ d₀… N₀.

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

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

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

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

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

Дополнительные варианты осуществления изобретения определены в зависимой формуле изобретения.

Краткое описание чертежей

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

Фиг.1 является графическим представлением отпечатка пальца и характерных точек в нем;

Фиг.2 является графическим представлением параметрических данных, которые характеризуют характерные точки отпечатка пальца на Фиг.1;

Фиг.3 является блок-схемой, иллюстрирующей способ согласно варианту осуществления настоящего изобретения;

Фиг.4A - это таблица;

Фиг.4B - это другая таблица;

Фиг.5 является блок-схемой устройства согласно варианту осуществления настоящего изобретения; и

Фиг.6 является блок-схемой компьютерного программного продукта согласно варианту осуществления настоящего изобретения.

Подробное описание вариантов осуществления

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

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

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

Формирование характерных особенностей включает в себя формирование множества характерных особенностей на основе двух или более характерных точек.

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

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

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

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

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

ОТПЕЧАТОК ПАЛЬЦА

Фиг.1 иллюстрирует представление части отпечатка 10 пальца, такого как отпечаток пальца человека. Отпечаток 10 пальца типично представлен одной или более характерными особенностями, характеризующими набор характерных точек, обычно называемых "точками минуций", ассоциативно связанных с отпечатком 10 пальца. Характерные точки, ассоциативно связанные с отпечатком 10 пальца, типично получаются из изображения отпечатка 10 пальца, например, с использованием технологий обработки изображения, все из которых могут быть реализованы вариантами осуществления изобретения. Различные технологии обработки изображения для этой цели известны и могут быть реализованы обычными специалистами в области техники.

Характерные точки отпечатка 10 пальца могут быть определены или получены из особенностей рисунка гребней отпечатка 10 пальца. Как иллюстрировано на Фиг.1, рисунок гребней может содержать особенности, такие как, например, окончания гребней и разветвления гребней. Точка A является примером окончания гребней, тогда как B и C являются примерами разветвления гребней. Как иллюстрируется на Фиг.2, каждая локальная характерная точка может быть представлена координатами (x, y) локального признака в справочной системе, общей для всех локальных характерных точек в данном изображении отпечатка пальца.

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

ХАРАКТЕРНАЯ ОСОБЕННОСТЬ

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

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

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

Характерной особенностью может быть угол α рисунка гребней в координатах (x, y) каждой из идентифицированных характерных точек. Более конкретно угол α, ассоциативно связанный с конкретной характерной точкой, может представлять угол между первым направлением гребня в конкретной характерной точке относительно линии, начерченной от конкретной характерной точки к другой характерной точке, и вторым направлением гребня в конкретной характерной точке относительно линии, начерченной от конкретной характерной точки к еще одной характерной точке.

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

Характерной особенностью может быть область A, ассоциативно связанная с тремя или более идентифицированными характерными точками.

В качестве одного иллюстрирующего примера некоторые характерные особенности, характеризующие отпечаток 10 пальца поблизости идентифицированных характерных точек A-B-C неизвестного отпечатка 10 пальца, показаны на Фиг.2. В этом примере характерные особенности включают в себя D₁, D₂, D₃, θ₁, θ₂, θ₃, α₁, α₂, α₃ и A. Кроме того, характерные особенности могут включать в себя подсчеты RC_A-B, RC_A-C, RC_B-C (не показано) гребней, где RC_A-B представляет число гребней, пересеченных линией, начерченной между характерными точками A и B, где RC_A-C представляет собой число гребней, пересеченных линией, начерченной между характерными точками A и C, и где RC_B-C представляет собой число гребней, пересеченных линией, начерченной между характерными точками B и C.

СПОСОБ

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

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

На следующем этапе, этапе 302, множество характерных особенностей, т.е. две или более характерные особенности, формируются на основе двух или более характерных точек, которые идентифицированы в неизвестном отпечатке 10 пальца на этапе 301. Этап 302 формирования множества характерных особенностей может содержать группировку или связывание двух или более характерных точек в один или более поднаборов (например, тройки). Каждый поднабор может быть ассоциативно связан с двумя или более характерными точками. Для каждого поднабора, который может быть выбран, могут быть сформированы одна или более характерных особенностей, которые характеризуют выбранный поднабор.

Одна или более характерных особенностей, которые сформированы на этапе 302, например, могут быть одной или более из характерных особенностей, описанных выше в секции ХАРАКТЕРНАЯ ОСОБЕННОСТЬ. Т.е. одна или более характерных особенностей могут быть выбраны из группы, содержащей: расстояние между двумя характерными точками; направление гребня в конкретной характерной точке относительно линии, начерченной от конкретной характерной точки к другой характерной точке; угол рисунка гребней в координатах от конкретной характерной точки; число гребней, пересекаемых линией, начерченной между двумя характерными точками; и область, ассоциативно связанную с, по меньшей мере, одним поднабором характерных точек.

Существует много различных реализаций для выполнения этапов 301-303, т.е. идентификации характерных точек и/или формирования ассоциативно связанных характерных особенностей, представляющих собой отпечаток 10 пальца, все из которых могут использоваться вариантами осуществления настоящего изобретения. Различные способы идентификации характерных точек и/или формирования ассоциативно связанных характерных особенностей известны в области техники и могут быть реализованы специалистами в данной области техники. Следовательно, они не будут дополнительно объясняться в данном документе.

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

На этапе 303 каждой характерной особенности из множества характерных особенностей присваивается число. Число содержит множество цифр. Число, например, может быть числом, содержащим множество двоичных цифр (битов). Число, например, может содержать 4 бита (т.е., полубайт), 6 битов, 8 битов (т.е., байт), 16 битов, 24 бита, 32 бита или даже больше битов.

Обращаясь теперь к Фиг.2, в иллюстративном примере четыре характерных особенности D1, D2, α1 и A_A-B-C сформированы из трех идентифицированных характерных точек A-B-C отпечатка 10 пальца. На этапе 303 этим четырем характерным особенностям, например, могут быть присвоены следующие двоичные числа по одному байту каждое a₇ a₆ a₅ a₄ a₃ a₂ a₁ a₀, b₇ b₆ b₅ b₄ b₃ b₂ b₁ b₀, c₇ c₆ с₅ с₄ с₃ с₂ с₁ с₀ и d₇ d₆ d₅ d₄ d₃ d₂ d₁ d₀, соответственно. Т.е. D₁ присвоено число a₇ a₆ a₅ a₄ a₃ a₂ a₁ a₀, D₂ присвоено число b₇ b₆ b₅ b₄ b₃ b₂ b₁ b₀ и т.д.

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

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

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

Обращаясь опять к Фиг.2 и примеру выше, теперь будут описаны различные примеры числового представления.

Согласно варианту осуществления изобретения числовое представление формируется посредством размещения двоичных цифр в следующем порядке: d₇ с₇ b₇ a₇ d₆ c₆ b₆ a₆ d₅ c₅ b₅ a₅ d₄ c₄ b₄ a₄ d₃ с₃ b₃ a₃ d₂ c₂ b₂ a₂ d₁ c₁ b₁ a₁ d₀ c₀ b₀ a₀.

Согласно другому варианту осуществления изобретения числовое представление создается посредством размещения битов в следующем порядке: a₇ b₇ c₇ d₇ a₆ b₆ c₆ d₆ a₅ b₅ c₅ d₅ a₄ b₄ c₄ d₄ a₃ b₃ c₃ d₃ a₂ b₂ c₂ d₂ a₁ b₁ c₁ d₁ a₀ b₀ c₀ d₀. Согласно некоторым вариантам осуществления формирование или создание числового представления содержит чередование только наиболее значимых битов упомянутого множества битов.

В варианте осуществления числовое представление создается посредством размещения битов в следующем порядке: a₇ a₆ a₅ a₄ a₃ a₂ a₁ a₀ a₇ b₇ c₇ d₇ b₆ c₆ d₆ b₅ c₅ d₅ b₄ c₄ d₄ b₃ c₃ d₃ b₂ c₂ d₂ b₁ с₁ d₁ b₀ c₀ d₀.

В другом варианте осуществления формирование числового представления содержит чередование только двух наиболее значимых битов каждой характерной особенности согласно следующей последовательности битов: d₇ c₇ b₇ a₇ d₆ с₆ b₆ a₆ d₅ d₄ d₃ d₂ d₁ d₀ c₅ c₄ c₃ c₂ c₁ c₀ b₅ b₄ b₃ b₂ b₁ b₀ a₅ a₄ a₃ a₂ a₁ a₀.

Еще в одном варианте осуществления формирование числового представления содержит чередование только двух или трех наиболее значимых битов каждой характерной особенности и т.д. Из-за изменений в качестве изображения отпечатка 10 пальца, давления при нажатии и т.д., в целом, резонно предположить, что два наименее значимых бита в каждой характерной особенности являются незначимыми или, по меньшей мере, малозначимыми. Это означает, что 8 битов числового представления могут быть маскированы. В варианте осуществления числовое представление, таким образом, может быть сформировано посредством размещения битов в следующем порядке: d₇ с₇ b₇ a₇ d₆ c₆ b₆ a₆ d₅ c₅ b₅ a₅ d₄ c₄ b₄ a₄ d₃ с₃ b₃ a₃ d₂ c₂ b₂ a₂.

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

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

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

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

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

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

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

Фиг.4A показывает иллюстративный пример таблицы, которая перечисляет похожие значения, полученные из характерных особенностей с присвоенными числами 52, 49, 53. При просмотре таблицы, показанной на Фиг.4A, следует понимать, что требуется только один двоичный поиск, число линейных поисков достаточно, чтобы найти все похожие характерные особенности в таблице. Если числа A, B, C в таблице представляют стороны треугольника, специалист в области техники понимает, что похожие по форме треугольники будут найдены поблизости друг друга. Однако чередование цифр не всегда имеет в результате список последовательных значений. Фиг.4B показывает другой список характерных особенностей, где требуются 2 двоичных поиска, чтобы найти значения, заключенные в похожие тройки. Больше списков характерных особенностей может быть создано, показывающих, что может потребоваться более чем 2 двоичных поиска. Было обнаружено, что, если используемые двоичные цифры присвоенного числа каждой характерной особенности изменяются на +/-1, число двоичных поисков, требуемых, чтобы найти все похожие по форме характерные особенности в отсортированной глобальной таблице, может быть значительно уменьшено по сравнению с решениями предшествующего уровня. Это следует понимать при просмотре Фиг.4A и 4B и сравнении этого с SQL-предложением, которое может быть использовано в решениях предыдущего уровня. Такое SQL-предложение может иметь следующий синтаксис:

SELECT* From GLOBALTABLE where A>ACONST-2 AND A<ACONST+2 AND B>BCONST-2 AND B<BCONST+2 AND C>CCONST-2 AND C<CCONST+2

УСТРОЙСТВО

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

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

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

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

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

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

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

Блок(и) устройства 50 могут быть, например, в аппаратных средствах, таких как, к примеру, процессор с памятью. Процессор может быть любым из множества процессоров, таких как процессоры фирм Intel или AMD, ЦП, микропроцессоры, микроконтроллеры программируемых интеллектуальных компьютеров (PIC), процессоры цифровых сигналов (DSP) и т.д. Однако рамки изобретения не ограничены этими конкретными процессорами. Память может быть любой памятью, способной хранить информацию, такой как оперативные запоминающие устройства (RAM), такие как RAM двойной плотности (DDR, DDR2), RAM одинарной плотности (SDRAM), статическое RAM (SRAM), динамическое RAM (DRAM), видео RAM (VRAM) и т.д. Память также может быть флеш-памятью, такой как USB, Compact Flash, SmartMedia, MMC-память, MemoryStick, SD Card, MiniSD, MicroSD, xD Card, TrancFlash, MicroDrive-память и т.д. Однако рамки изобретения не ограничены этими конкретными запоминающими устройствами.

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

В варианте осуществления устройство 50 используется в полицейском управлении или при расследовании на месте преступления.

В другом варианте осуществления устройство 50 используется в проходной системе в аэропорте, промышленной зоне или здании и т.д.

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

КОМПЬЮТЕРНЫЙ ПРОГРАММНЫЙ ПРОДУКТ

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

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

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

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

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

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

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

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

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

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

Изобретение может быть осуществлено в любой подходящей форме, включающей в себя аппаратные средства, программное обеспечение, программно-аппаратные средства или любую их комбинацию. Однако может быть полезным осуществить изобретение в качестве программного обеспечения компьютера, работающего на одном или более процессорах данных и/или процессорах цифровых сигналов. Элементы и компоненты вариантов осуществления изобретения могут быть физически, функционально и логически осуществлены любым подходящим способом. Действительно функциональность может быть осуществлена в одном блоке, во множестве блоков или как часть других функциональных блоков. По существу варианты осуществления изобретения могут быть осуществлены в одном блоке или могут быть физически и функционально распределены между разными блоками и процессорами. Со ссылкой на Фиг.5 блоки 501, 502, 503, 504, 505 могут, например, быть осуществлены в одном или более компьютерах, соединенных в локальную или распределенную сеть. Примеры таких сетей включают в себя, но не только, LAN, WAN, UMA, GAN, Bluetooth и т.д. В качестве иллюстративного примера при использовании вариантов осуществления настоящего изобретения в практике полицейского управления может быть полезно иметь блок 501 в локальном устройстве, тогда как, по меньшей мере, блок 505 осуществлен в удаленном сервере.

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

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

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

Также следует подчеркнуть, что формы единственного числа "a", "an" и "the", когда используются в данном документе, предназначены содержать также и множественные формы, пока явно не установлено иное. Будет дополнительно понятно, что термины "включает в себя/включающий в себя" и/или “содержит/содержащий” при использовании в этой спецификации используется, чтобы определить наличие изложенных признаков, целых частей, этапов, операций, элементов и/или компонентов, но не препятствует наличию или добавлению одного или более других признаков, целых частей, этапов, операций, элементов, компонентов и/или их групп.

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

Изобретение относится к области сопоставления отпечатков пальцев. Техническим результатом является обеспечение повышения скорости при поиске в базе данных, содержащей данные, относящиеся к множеству отпечатков пальцев, чтобы найти совпадение. Способ поиска в базе данных, содержащей данные, относящиеся к множеству отпечатков пальцев. На этапе 301 идентифицируются две или более характерных точек в изображении неизвестного отпечатка пальца. Множество характерных особенностей формируются на этапе 302. Множество характерных особенностей основано на двух или более характерных точках. На этапе 303 число, содержащее множество цифр, например двоичных цифр, присваивается каждой из множества характерных особенностей. На последующем этапе, этапе 304, числовое представление упомянутого отпечатка пальца формируется на основе присвоенных чисел. Числовое представление формируется посредством чередования множества цифр так, что цифры числового представления размещены чередующимся или "переплетающимся" образом в числовом представлении. На этапе 305 числовое представление используется в качестве аргумента поиска при поиске в базе данных. Изобретение также относится к устройству и читаемому компьютером носителю. 3 н. и 20 з.п. ф-лы, 7 ил.

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

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

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

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

5. Способ по п.3, в котором чередование содержит чередование всех битов из упомянутого множества битов.

6. Способ по п.4, в котором чередование содержит чередование всех битов из упомянутого множества битов.

7. Способ по п.3, в котором чередование содержит побитовое чередование множества битов.

8. Способ по любому из пп.4-6, в котором чередование содержит побитовое чередование множества битов.

9. Способ по любому из пп.1, 2, 4-7, в котором чередование содержит размещение множества битов в порядке значимости от наиболее значимых битов до наименее значимых битов в числовом представлении.

10. Способ по п.3, в котором чередование содержит размещение множества битов в порядке значимости от наиболее значимых битов до наименее значимых битов в числовом представлении.

11. Способ по п.8, в котором чередование содержит размещение множества битов в порядке значимости от наиболее значимых битов до наименее значимых битов в числовом представлении.

12. Способ по п.3, в котором присваивание содержит присваивание соответствующего двоичного числа а₃ а₂ а₁ a₀, b₃ b₂ b₁ b₀, c₃ c₂ c₁ c₀, d₃ d₂ d₁ d₀… N₃ N₂ N₁ N₀ каждой из множества характерных особенностей, а формирование содержит формирование числового представления посредством размещения множества битов в следующем порядке: N₃…d₃ С₃ b₃ а₃ N₂… d₂ c₂ b₂ а₂ N₁… d₁ c₁ b₁ a₁ N₀… d₀ c₀ b₀ a₀.

13. Способ по п.3, в котором присваивание содержит присваивание соответствующего двоичного числа а₃ а₂ a₁ a₀, b₃ b₂ b₁ b₀, c₃ c₂ c₁ c₀, d₃ d₂ d₁ d₀… N₃ N₂ N₁ N₀ каждой из множества характерных особенностей, а формирование содержит формирование числового представления посредством размещения множества битов в следующем порядке: а₃ b₃ c₃ d₃… N₃ а₂ b₂ c₂ d₂… N₂ a₁ b₁ C₁ d₁… N₁ a₀ b₀ C₀ d₀… N₀.

14. Способ по п.3, в котором присваивание содержит присваивание соответствующего двоичного числа a₇ а₆ a₅ a₄ а₃ а₂ a₁ a₀, b₇ b₆ b₅ b₄ b₃ b₂ b₁ b₀, c₇ c₆ c₅ c₄ c₃ c₂ c₁ c₀, d₇ d₆ d₅ d₄ d₃ d₂ d₁ d₀… N₇ N₆ N₅ N₄ N₃ N₂ N₁ N₀ каждой из множества характерных особенностей, а формирование содержит формирование числового представления посредством размещения множества битов в следующем порядке: N₇… d₇ C₇ b₇ a₇ N₆… d₆ c₆ b₆ а₆ N₅… d₅ c₅ b₅ a₅ N₄… d₄ c₄ b₄ a₄ N₃… d₃ С₃ b₃ а₃ N₂… d₂ с₂ b₂ а₂ N₁… d₁ c₁ b₁ a₁ N₀… d₀ c₀ b₀ a₀.

15. Способ по п.3, в котором присваивание содержит присваивание соответствующего двоичного числа a₇ a₆ a₅ a₄ а₃ а₂ a₁ a₀, b₇ b₆ b₅ b₄ b₃ b₂ b₁ b₀, c₇ c₆ c₅ c₄ с₃ c₂ c₁ c₀, d₇ d₆ d₅ d₄ d₃ d₂ d₁ d₀… N₇ N₆ N₅ N₄ N₃ N₂ N₁ N₀ каждой из множества характерных особенностей, а формирование содержит формирование числового представления посредством размещения множества битов в следующем порядке: a₇ b₇ c₇ d₇… N₇ a₆ b₆ c₆ d₆… N₆ a₅ b₅ c₅ d₅… N₅ a₄ b₄ c₄ d₄… N₄ а₃ b₃ c₃ d₃… N₃ а₂ b₂ c₂ d₂… N₃ a₁ b₁ c₁ d₁… N₁ a₀ b₀ c₀ d₀… N₀.

16. Способ по п.3, в котором присваивание содержит присваивание соответствующего двоичного числа a₇ a₆ a₅ а₄ а₃ а₂ а₁ a₀, b₇ b₆ b₅ b₄ b₃ b₂ b₁ b₀, c₇ c₆ c₅ c₄ c₃ c₂ c₁ c₀, d₇ d₆ d₅ d₄ d₃ d₂ d₁ d₀… N₇ N₆ N₅ N₄ N₃ N₂ N₁ N₀ каждой из множества характерных особенностей, а формирование содержит формирование числового представления посредством размещения множества битов в следующем порядке: а₇ а₆ а₅ a₄ а₃ а₂ а₁ a₀ а₇ b₇ c₇ d₇… N₇ b₆ c₆ d₆… N₆ b₅ c₅ d₅… N₅ b₄ c₄ d₄… N₄ b₃ c₃ d₃… N₃ b₂ c₂ d₂… N₂ b₁ c₁ d₁… N₁ b₀ c₀ d₀… N₀.

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

18. Способ по любому из пп.4-7, 10-15, дополнительно содержащий этап, на котором:
маскируют, по меньшей мере, некоторые из наименее значимых битов упомянутого множества битов.

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

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

21. Способ по любому из пп.1, 2, 4-7, 10-17, 19, 20, содержащий после этапа присваивания (303) этап, на котором:
группируют множество характерных особенностей в множество поднаборов характерных особенностей, при этом формирование (304) содержит формирование множества числовых представлений упомянутого отпечатка пальца на основе упомянутых поднаборов характерных особенностей, и при этом каждое из числовых представлений формируется посредством, по меньшей мере, частичного чередования упомянутого множества цифр, а использование (305) содержит использование числовых представлений в качестве аргументов поиска при поиске в базе данных.

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

23. Устройство (50) для поиска в базе данных, содержащей данные, относящиеся к множеству отпечатков пальцев, содержащее:
блок (501) идентификации, выполненный с возможностью идентифицировать, по меньшей мере, две характерные точки в изображении неизвестного отпечатка пальца;
первый блок (502) формирования, выполненный с возможностью формировать множество характерных особенностей на основе, по меньшей мере, двух характерных точек;
блок (503) присваивания, выполненный с возможностью присваивать число, содержащее множество цифр, каждой из множества характерных особенностей;
второй блок (504) формирования, выполненный с возможностью формировать числовое представление упомянутого отпечатка пальца на основе присвоенных чисел; и
блок (505) поиска, выполненный с возможностью использовать числовое представление в качестве аргумента поиска при поиске в базе данных;
отличающееся тем, что второй блок (504) формирования выполнен с возможностью формировать упомянутое числовое представление посредством, по меньшей мере, частичного чередования упомянутого множества цифр.