Цифровой отпечаток изображения для сравнения подобия многих изображений
Без java.io.* это можно сделать следующим образом.
String trace = e.toString() + "\n";
for (StackTraceElement e1 : e.getStackTrace()) {
trace += "\t at " + e1.toString() + "\n";
}
И тогда переменная trace содержит вашу трассировку стека. Вывод также содержит начальную причину, выход идентичен printStackTrace()
Пример: printStackTrace() дает:
java.io.FileNotFoundException: / (Is a directory)
at java.io.FileOutputStream.open0(Native Method)
at java.io.FileOutputStream.open(FileOutputStream.java:270)
at java.io.FileOutputStream.<init>(FileOutputStream.java:213)
at java.io.FileOutputStream.<init>(FileOutputStream.java:101)
at Test.main(Test.java:9)
Строка trace выполняется, когда она напечатана на stdout
java.io.FileNotFoundException: / (Is a directory)
at java.io.FileOutputStream.open0(Native Method)
at java.io.FileOutputStream.open(FileOutputStream.java:270)
at java.io.FileOutputStream.<init>(FileOutputStream.java:213)
at java.io.FileOutputStream.<init>(FileOutputStream.java:101)
at Test.main(Test.java:9)
9 ответов
Подобный ответу Ic - Вы могли бы попытаться сравнить изображения в нескольких разрешениях. Таким образом, каждый образ сохраняется как 1x1, 2x2, 4x4.. 800x800. Если самое низкое разрешение не соответствует (подвергающийся порогу), можно сразу отклонить его. Если это действительно соответствует, можно сравнить их в следующем более высоком разрешении и так далее..
Также - если изображения совместно используют какую-либо подобную структуру, такую как медицинские изображения, Вы могли бы быть в состоянии извлечь ту структуру в описание, которое более легко/быстрее сравнить.
Одним путем можно ли сделать, это должно изменить размеры изображения и значительно отбросить разрешение (к 200x200, возможно?), храня меньшую (усредненную пикселем) версию для того, чтобы сделать сравнение. Тогда определите порог допуска и сравните каждый пиксель. Если RGB всех пикселей в рамках допуска, у Вас есть соответствие.
Ваша начальная буква пробегает, O (n^2), но если Вы каталогизируете все соответствия, каждое новое изображение является просто O (n) алгоритм для сравнения (только необходимо сравнить его с каждым ранее вставленным изображением). Это в конечном счете сломается однако, поскольку список изображений для сравнения становится больше, но я думаю, что Вы в безопасности некоторое время.
После 400 дней выполнения, у Вас будет 500 000 изображений, что означает (дисконтирование времени изменять размеры изображения вниз) 200(H)*200(W)*500,000(images)*3(RGB) = 60,000,000,000 сравнений. Если каждое изображение является точным совпадением, Вы собираетесь быть отставанием, но это, вероятно, не будет иметь место, исправляться? Помните, можно обесценить изображение как соответствие, как только единственное сравнение выходит за пределы порога.
Вы буквально хотите сравнить каждое изображение с другими? Каково приложение? Возможно, Вам просто нужны некоторая индексация и извлечение изображений на основе определенных дескрипторов? Тогда, например, можно посмотреть на стандарт MPEG-7 для Интерфейса Описания Мультимедийного контента. Тогда Вы могли сравнить различные дескрипторы изображения, которые будут не настолько точными, но намного быстрее.
Кажется, что специализированные алгоритмы хеширования изображения являются областью активного исследования, но возможно нормальное вычисление хеша байтов изображения добилось бы цели.
Вы ищущий идентичные байту изображения вместо того, чтобы искать изображения, которые получены из того же источника, но могут быть другим форматом или разрешением (который кажется мне довольно тяжелой проблемой).
Существует гораздо менее специальный подход, чем предложенные здесь варианты уменьшенных изображений, которые сохраняют свой общий характер, но дают гораздо более строгую математическую основу для происходящего. .
Возьмите вейвлет Хаара изображения. По сути, вейвлет Хаара - это последовательность различий между изображениями с более низким разрешением и каждым изображением с более высоким разрешением, но взвешенных в зависимости от того, насколько глубоко вы находитесь в «дереве» MIP-карт. Расчет прост. Затем, как только у вас будет взвешенный вейвлет Хаара, отбросьте все коэффициенты, кроме k наибольших (по абсолютной величине), нормализуйте вектор и сохраните его.
Если вы возьмете скалярное произведение двух из этих нормализованных векторов, оно даст у вас есть мера сходства, где 1 почти идентичен.
Давным-давно я работал над системой с некоторыми похожими характеристиками, и это приближение алгоритма, которому мы следовали:
- Разделите изображение на зоны. В нашем случае мы имели дело с видео с разрешением 4: 3, поэтому мы использовали 12 зон. При этом разрешение исходных изображений не учитывается.
- Для каждой зоны рассчитайте общий цвет - среднее значение всех пикселей в зоне.
- Для всего изображения рассчитайте общий цвет - среднее значение все зоны
Итак, для каждого изображения вы сохраняете n + 1 целочисленных значений, где n - количество отслеживаемых зон.
Для сравнения: вам также необходимо рассматривать каждый цветовой канал отдельно.
- Для всего изображения сравните цветовые каналы для общих цветов, чтобы увидеть, находятся ли они в пределах определенного порогового значения, скажем, 10%
- Если изображения находятся в пределах порогового значения, затем сравните каждую зону. Если все зоны также находятся в пределах порогового значения, изображения являются достаточно точными, чтобы вы могли, по крайней мере, пометить их для дальнейшего сравнения.
Это позволяет быстро отбрасывать изображения, которые не совпадают; вы также можете использовать больше зон и / или применять алгоритм рекурсивно, чтобы повысить достоверность совпадения.
Обычные алгоритмы хеширования или вычисления CRC плохо работают с данными изображения. Необходимо принимать во внимание размерный характер информации.
Если вам требуется чрезвычайно надежный отпечаток пальца, такой, что учитываются аффинные преобразования (масштабирование, поворот, перевод, переворачивание), вы можете использовать преобразование Радона в источнике изображения , чтобы произвести нормативное отображение данных изображения - сохранить его с каждым изображением, а затем сравнить только отпечатки пальцев. Это сложный алгоритм и не для слабонервных.
Возможны несколько простых решений:
- Создать гистограмму яркости для изображения в виде отпечатка пальца
- Создать уменьшенные версии каждого изображения в виде отпечатка пальца
- Объедините технику (1) и (2) в гибридный подход для улучшения качества сравнения
Гистограмма яркости (особенно та, которая разделена на компоненты RGB) является разумным отпечатком пальца для изображения - и может быть реализована довольно эффективно. Вычитание одной гистограммы из другой даст новую историограмму, которую вы можете обработать, чтобы определить, насколько похожи два изображения. Гистограммы, потому что единственный инструмент для оценки распределения и появления информации о яркости / цвете довольно хорошо обрабатывает аффинные преобразования. Если квантовать информацию о яркости каждого цветового компонента до 8-битного значения, 768 байт памяти будет достаточно для отпечатка пальца изображения практически любого разумного размера. Гистограммы яркости дают ложные негативы при изменении информации о цвете в изображении. Если вы примените преобразования, такие как контраст / яркость, постеризация, смещение цвета, информация о яркости изменится. Ложные срабатывания также возможны с определенными типами изображений ... такими как пейзажи и изображения, где один цвет доминирует над другими.
Использование масштабированных изображений - еще один способ снизить информационную плотность изображения до уровня, который легче сравнивать . При уменьшении менее 10% от исходного размера изображения обычно теряется слишком много информации, чтобы его можно было использовать - поэтому изображение размером 800x800 пикселей можно уменьшить до 80x80 и при этом предоставить достаточно информации для выполнения достойного снятия отпечатков пальцев. В отличие от данных гистограммы, вы должны выполнить анизотропное масштабирование данных изображения, когда исходные разрешения имеют разные соотношения сторон. Другими словами, уменьшение изображения 300x800 до миниатюры 80x80 вызывает деформацию изображения, так что по сравнению с изображением 300x500 (это очень похоже) будет вызывать ложноотрицательные результаты. Отпечатки миниатюр также часто приводят к ложным отрицаниям, когда задействованы аффинные преобразования. Если вы перевернете или поверните изображение, его эскиз будет сильно отличаться от оригинала и может привести к ложному срабатыванию.
Сочетание обоих методов - разумный способ хеджировать ваши ставки и уменьшить количество ложноположительных и ложноотрицательных результатов.
Итак, вы хотите выполнить «сопоставление отпечатков пальцев», которое сильно отличается от «сопоставления изображений». Анализ отпечатков пальцев был глубоко изучен в течение последних 20 лет, и было разработано несколько интересных алгоритмов для обеспечения правильной скорости обнаружения (в отношении показателей FAR и FRR - Коэффициент ложного принятия и Коэффициент ложного отклонения ).
Я предлагаю вам лучше взглянуть на LFA (Анализ локальных характеристик) класс методов обнаружения, в основном основанный на проверке мелких деталей . Мелкие детали - это особые характеристики любого отпечатка пальца, которые были разделены на несколько классов. Сопоставление растрового изображения с картой мелких деталей - это то, что на самом деле большинство государственных органов делают для регистрации преступников или террористов.
Для сравнения изображений iPhone и разработки сходства изображений посетите: http://sites.google.com/site/imagecomparison/
Чтобы увидеть это в действии, ознакомьтесь с визуальным поиском eyeBuy в iTunes AppStore.