446
Схема алгоритма.Наш алгоритм был структурирован так, чтобы иден-
тифицировать круговые строки из сохраненного отпечатка пальца и ввода с
наибольшей длиной: asmf/acdm использовался для проверки того,
что отно-
сительное вращение круговой строки ввода соответствует вращению сохра-
ненного изображения отпечатка пальца. Кроме того, для проверки точности
совмещения использовался алгоритм аппроксимации Нидлмана-Вунша [3].
Основным компонентом, определяющим скорость выполнения, является
извлечение мелких деталей из изображения и построение круговой строки,
которая многократно вызывается на протяжении всего процесса. Мы описали
полный процесс сопоставления отпечатков пальцев, как показано ниже:
1.
Формирование базы данных: была создана база данных круговых
строк с центром изображения, классифицированным как эффективный центр.
2.
Формирование концентрических кругов к строкам: были нарисованы
концентрические круги, а затем (с помощью быстрого извлечения мелких
деталей) преобразованы в строки, состоящие из нулей и единиц.
Например,
предполагая, что
Cir - круговая строка
i-го изображения с радиусом
r, все
повороты каждой из круговых строк сохраняются в базе данных. Если позво-
лить
DbRir быть коллекцией повернутых строк из
Cir;
Cir = «0111» означает,
что
DRir будет содержать значения «0111», «1011», «1101», «1110». И
наоборот, если позволить
DbRir быть набором повернутых строк из
Cir;
Cir =
«0111» будет означать, что
DRir будет содержать значения «0111», «1011»,
«1101», «1110».
3.
Формирование двоичной строки: после предыдущей фазы, быстрое
извлечение новых мелочей было повторено, чтобы построить круговые
двоичные строки для каждого круга.
4
. Формирование списка CsR: после формирования двоичной строки
процесс затем приступил к созданию
отсортированного списка CsR из пар
радиусов и круговых строк (<
CStr, Radius>) в порядке убывания длины
CStr.
5.
Сравнение ротации: после формирования списка метод asmf / acdmf
был применен вместе с алгоритмом Нидлмана-Вунша. Это позволяло
сравнивать чередования, в результате чего процент совпадающих строк,
записанных как выше определенного порога (
tS), приводил к сохранению
суммы процента совпадений.
I-е изображение было помечено как
«изображение-кандидат», а затем было выбрано (
i + 1) -е изображение до тех
пор, пока все изображения в базе данных не были использованы. Следуя
этому
процессу, этот этап можно повторить после выбора другой
центральной точки.
6.
Сопоставление изображений: после предыдущих этапов процесс
наконец возвращается к сопоставленным изображениям для проверки.
Результаты исследования. Мы стремились улучшить производитель-
ность извлечения мелких деталей, чтобы сократить общее время выполнения
процесса. Сравнивая время, необходимое в миллисекундах для каждого
метода, становится ясно, что наш алгоритм решения обеспечивает лучшие
результаты для общего времени выполнения извлечения деталей из изобра-
447
жения и
построения круговой строки, которая многократно вызывается на
протяжении всего процесса. Это представлено в таблице 1 и на рисунке 1.
Таблица 1. Результаты экспериментов
Размер базы
данных
Время, необходимое для
новых методов
(миллисекунд)
Время, необходимое для
быстрых методов
(миллисекунд)
50
881300
67765
100
3276930
1290428
Таблица 1 показывает, что есть два основных фактора, которые
обеспечивают точность и производительность предложенного алгоритма. Это
размер базы данных и время, необходимое для извлечения мельчайших
деталей из изображения и создания круговой цепочки, которая многократно
вызывается на протяжении всего процесса.
В таблице 1 показаны результаты для двух баз данных разных размеров.
Для всех входных данных мы зафиксировали время,
необходимое для
каждого метода, и результаты сравниваются на рис. 1.
новые методы
быстрые методы
Рис. 1. Сравнение быстрых методов с новыми методами
Понятно, что наш алгоритм решения обеспечивает лучшие результаты
с точки зрения общего времени выполнения, и по мере увеличения размера
базы данных он уменьшает время, необходимое для извлечения деталей из
изображения и построения круговой строки, которая многократно
вызывается на протяжении всего процесса.
Заключение.
С увеличением количества устройств, использующих рас-
познавание отпечатков пальцев, это заставит производителей переоценить
существующие методы сопоставления деталей и изучить усовершенствован-
ные модели, которые лучше адаптированы к
невертикальной ориентации
ввода, которая становится распространенной среди мобильных устройств.
В целом, это исследование является примером того, как математические
алгоритмы могут быть использованы для расширения функциональных
возможностей вычислительной функции с целью более точного модели-
рования окружающей среды устройства. Кроме того, помимо учета более
реалистичного разнообразия ориентации пользователя при распознавании
отпечатков пальцев, эта предлагаемая система может также улучшить
модели, выходящие за рамки биоинформатики, которые сталкиваются с
аналогичным ростом мобильности устройств и
диапазоном ориентации
портативных устройств.
448
Список использованной литературы
1. Alshammary M.H., Alanezi F.A.: A review of recent developments in NOMA and SCMA
schemes for 5G technology. In: IEEE Communications (2017).
2. Ajala O.I., Iliopoulos C.S., Khan M.R.: Identification of fingerprints using circular string
approximation for mobile devices. In: PATTERNS 2016, Computer Science and
Information
Systems.
ACSIS,
vol.
13,
pp.
193–197
(2016).
URL:
https://doi.org/10.15439/2017f3. ISSN 2300-5963
3. Landau G.M., Vishkin U.: Fast string matching with k differences*. J. Comput. Syst. Sci.
37, pp. 63–78 (1998).
Do'stlaringiz bilan baham: