Одним из наиболее важных инструментов, которыми располагает ФБР, является идентификация по отпечаткам пальцев.

Они собирают отпечатки пальцев с места преступления, как вы видели в кино.

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

Вот тут-то и появляются синусоиды и БПФ.

Отказ от ответственности!!!

Теперь я просто милый парень из Нигерии, который сейчас учится в Литве.

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

Это только в образовательных целях. Я даже не вижу никаких опасных возможностей. 🤷‍♀️

Постановка задачи ясна. ФБР нужен был способ сжатия отпечатков пальцев. Это упростит их хранение и доступ к ним.

Решение, предложенное ФБР, заключалось в использовании преобразования Фурье.

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

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

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

Сжимаем отпечатки пальцев в питоне

  • Загрузите изображение отпечатка пальца.
  • Преобразуйте его в оттенки серого (черно-белый)
from PIL import Image
im = Image.open('fingerprint.jpg').convert('L')

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

Мы можем сделать это, используя метод fft2() из модуля NumPy, который выполняет 2D-преобразование Фурье для массива:

import numpy as np
im_fft = np.fft.fft2(im)

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

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

im_fft_mag = np.abs(im_fft)

Наконец, мы можем сжать отпечаток пальца, сохранив только подмножество коэффициентов с наивысшей величиной.

Это можно сделать с помощью метода argsort() для сортировки коэффициентов по величине. Затем мы индексируем массив, чтобы сохранить первые N коэффициентов:

N = 100
im_fft_mag_flat = im_fft_mag.flatten()
idx = np.argsort(im_fft_mag_flat)[::-1][:N]
im_fft_mag_compressed = np.zeros_like(im_fft_mag_flat)
im_fft_mag_compressed[idx] = im_fft_mag_flat[idx]
im_fft_compressed = im_fft_mag_compressed.reshape(im_fft.shape)

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

У всего хорошего есть уродливая черта.

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

Есть и другие методы:

  • Вейвлет-сжатие
  • Нейросетевые подходы

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

Реализация на Python очень проста. Его можно оптимизировать по скорости и использованию памяти. Но это дает что-то близкое к решению, которое использовало ФБР.

Спасибо за прочтение.

Вы можете закончить здесь или изучить науку, стоящую за всем этим, в следующем разделе.

Следите за моей работой

👉 Следите за моими историями и уроками на YouTube.

👉 Получите членство по моей реферальной ссылке.

👉 Подпишитесь на мою Информационную рассылку,

  • Читать бесплатно, если у вас нет подписки на премиум-среду.
  • Или для обновлений, когда я публикую.

👉Подпишитесь на меня в Linkedin и Twitter.

Изучите науку, стоящую за всем этим!!!

Что такое синусоида?

Синусоида — это гладкий волнистый узор, используемый в математике, естественных науках и технике. Он используется для моделирования таких вещей, как звук, свет и механика. Он поднимается и опускается обычным образом. Его можно описать простым уравнением y = A sin(ωt + φ).

  • А - амплитуда.
  • φ — фазовый угол.
  • ω – угловая частота.
  • это время.

Почему синусоидальная волна важна, будет объяснено в разделе БПФ.

Что такое БПФ (быстрое преобразование Фурье)?

Преобразование Фурье — это математический метод извлечения частотных составляющих сигналов.

Я впервые узнал об этом в этом видео Дерека из Veritasium.

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

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

В 1960 году ученые из Лос-Аламоса использовали созданный алгоритм преобразования Фурье для обнаружения ядерных испытаний с помощью звуковых волн. Первоначальный алгоритм был медленным и требовательным к вычислительным ресурсам.

Алгоритм быстрого преобразования Фурье (БПФ) был разработан в 1965 году. Разработчиками были Джеймс Кули и Джон Тьюки. Это сократило время расчета.

БПФ сделал возможным анализ сейсмических данных в реальном времени.

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

Как работает БПФ?

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

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

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

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

Посмотрите видео Veritasium, чтобы лучше понять его. Вы также можете посмотреть Это от 3b1b (Грант Сандерсон).

Приятного аппетита.

Следите за моей работой

👉 Следите за моими историями и уроками на YouTube.

👉 Получите членство по моей реферальной ссылке.

👉 Подпишитесь на мою Информационную рассылку,

  • Читать бесплатно, если у вас нет подписки на премиум-среду.
  • Или для обновлений, когда я публикую.

👉Подпишитесь на меня в Linkedin

Повышение уровня кодирования

Спасибо, что являетесь частью нашего сообщества! Перед тем, как ты уйдешь:

  • 👏 Хлопайте за историю и подписывайтесь на автора 👉
  • 📰 Смотрите больше контента в публикации Level Up Coding
  • 💰 Бесплатный курс собеседования по программированию ⇒ Просмотреть курс
  • 🔔 Подписывайтесь на нас: Twitter | ЛинкедИн | "Новостная рассылка"

🚀👉 Присоединяйтесь к коллективу талантов Level Up и найдите прекрасную работу