самый быстрый способ сопоставить отпечатки пальцев?

Question

Я пытаюсь проверить, совпадает ли отпечаток пальца в огромной коллекции отпечатков пальцев (100 000 отпечатков пальцев) Для последовательного поиска совпадений потребуется больше времени. Есть ли лучший способ поиска совпадения? Можно ли организовать отпечатки пальцев в бинарной древовидной структуре, чтобы уменьшить количество сравнений? если да, как мы можем это сделать? было бы полезно, если бы ответы были в перспективе Java.

редактирование:

У меня есть все отпечатки пальцев в виде изображений .gif. Как я могу преобразовать изображения отпечатков пальцев в данные?

Спасибо.

Answer 1

1) Вам необходимо использовать алгоритм сжатия вейвлета для кодирования отпечатка пальца в последовательности параметров сжатия вейвлета:

0, -1, 2,4, 5.6.7.7, 32.-1.5 и т. Д.

2) Вам необходимо определить функцию соответствия, которая найдет некоторые сходства, есть два варианта:

- геометрический подход (сравниваем квадранты с квадрантами, все поля разнесены в непрерывные блоки по некоторому пространственному алгоритму)

Плюсы:

Алгоритм сопоставления пикселей с аппаратным ускорением (SSE), нормализация всех отпечатков пальцев к стандартной основе с использованием аффинного преобразования, например в квадрат 512x512 px

Минусы:

Высокая чувствительность к качеству отпечатка пальца (если часть найденного отпечатка пальца полностью опущена)

- топологический подход (связность линий, дуг, точек останова, взаимное расположение друг друга)

Плюсы:

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

Минусы:

Низкая скорость анализа, сильно зависит от качества функции классификации,

3) Вам необходимо определить какой-то генетический алгоритм для обучения функции оценки на известном набореотпечатки пальцев

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

Answer 2

Это не моя область знаний (я веб-разработчик), но я думаю, вам стоит заглянуть в нейронные сети.Однажды я скачал демо-код и поэкспериментировал с распознаванием символов.Было удивительно видеть, как нейронная сеть, которую я настроил, могла распознавать символы, которые я нарисовал на экране.Но прежде чем он смог это сделать, он сначала должен был научиться (обратное распространение).

Вот слайд-шоу, которое дает схему: http://www.slideshare.net/alessandrobaffa/fingerprints-recognition-using-neural-networks

Последний слайд содержит дополнительные ссылки.

Удачи!

/ Томас Кан

Answer 3

Я не могу комментировать лучший подход полностью сделай сам, но у меня есть большой опыт в этой области. Все крупные (дорогие!) Коммерческие продукты имеют 2 или более алгоритма для сопоставления отпечатков пальцев в больших наборах данных. Есть некоторые, которые используют классы отпечатков пальцев (петли, обороты и т. Д.), Чтобы выполнить некоторую предварительную фильтрацию, но в целом отпечатки пальцев не очень хорошо индексируются, вам придется использовать их с умом. Вот где в игру вступают несколько алгоритмов.

Существует несколько классов алгоритмов, которые могут выполнять очень быстрое сравнение отпечатков пальцев (форма гребня), но они очень восприимчивы к ошибкам, поэтому сами по себе не являются достаточно точными для разумной идентификации в базах данных разумного размера. Таким образом, эти алгоритмы обычно используются в качестве первого этапа. Если алгоритм вызывает сомнения, он переходит к следующему этапу. Это может быть какой-то алгоритм «среднего класса», например, спектральные детали или «медленный и точный» алгоритм, например то, что на самом деле сравнивает все мелочи. Чистый эффект состоит в том, что вторичные стадии обычно корректны для большинства ложных восприятий первой стадии. Единственная невосстановимая потеря - ложные отклонения на первом (и втором) этапе. В зависимости от предметной области это может быть незначительным или довольно высоким. Это компромисс между точностью и производительностью. В нашей собственной тестовой среде мы видели скорость, превышающую 100 000 000 отпечатков пальцев, сравниваемых таким образом в секунду на одном (мощном) рабочем столе, что позволило решить исходную проблему за ~ 1 мс. Это сложный, дорогой и очень специализированный программный продукт.

Answer 4

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

Есть несколько вопросов: - 1) Есть лиМожно ли как можно быстрее найти соответствие отпечатка пальца для крупномасштабных баз данных?

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

Ссылка, созданная Питером Ковеси ниже, предоставляет код для поля ориентации и извлечения мелочей для сопоставления: - http://www.csse.uwa.edu.au/~pk/research/matlabfns/#fingerprints Обнаружение особых точек и поля ориентации помогают в идентификацииклассы.Это можно найти по ссылке.

2) Как преобразовать изображения отпечатков пальцев в данные?Ответ: Хорошо, не имеет значения, в каком формате изображение, я использую TIFF.Вы должны знать, что отпечатки пальцев состоят из гребней и долин.Гряды представлены более темной линией.Вам нужно применить так называемую сегментацию гребня, чтобы отбросить фон и извлечь только гребни.Это хранится в маске.

3) «существующее изображение и сканированное изображение не будут в точности похожи. Это моя проблема»

Ответ: На него влияют шум, вращение,перевод и т. д. Уменьшение шума, использование методов улучшения.Для поворота используйте контрольные точки и выровняйте отпечатки пальцев.

Я знаю, что это краткий обзор, однако я надеюсь, что он направит вашу волю в правильном направлении.Удачи!

Answer 5

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

Я гуглил по fingerprint encoding standard и получил несколько интересных результатов, включая Энциклопедию биометрии , в которой упоминается "качество в различных стандартах кодирования отпечатков пальцев", и статью говорит о стандарте кодирования изображений ФБР (между прочим)

Answer 6

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

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

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

Биометрические алгоритмы не идеальны, и там производительность измеряется по их частоте ложных приемов (FAR) и частоте ложных браков (FRR).Эти две меры обратно связаны друг с другом, и это означает, что по мере повышения безопасности (уменьшения FAR) вы увеличиваете FRR.