Введение
Недавно наткнулся на статью, размещенную на Хабрахабре, посвященную сравнению изображений «Выглядит похоже». Как работает перцептивный хэш. Так как я сам достаточно долго занимался этой тематикой (являюсь автором программы AntiDupl), то мне захотелось поделиться здесь своим опытом по данному вопросу. В статье я приведу два варианта алгоритма сравнения похожих изображений — базовый и улучшенный. Все они были проверены автором на практике в рамках указанного выше проекта. Изложение мое будет вестись без строгих доказательств, сложных формул и специальной математической терминологии. Надеюсь, что читатели простят меня за это.
Базовый Алгоритм
Мера схожести изображений
При сравнении похожих изображений первым встает вопрос: что считать мерой схожести изображений? Очевидно, что это величина имеет значение обратное различию изображений друг от друга. Следственно нужно выбрать некую метрику, характеризующую различие изображений друг от друга. Тогда схожими изображениями будут считаться изображения, отличие между которыми меньше некоторого порога. Для изображений с одинаковыми габаритами, обычно такой мерой различия служит среднеквадратическое отклонение пикселей одного изображения от другого. Хотя конечно, нам ни что не мешает выбрать другую метрику, например усредненную абсолютную разность пикселей изображений друг от друга.
Картинки разных размеров
Вопрос несколько усложняется, если нужно сравнить изображения разных размеров. Однако достаточно очевидным решением этой проблемы является приведение всех изображений к одинаковому размеру. Остается выбрать это размер — если выбрать его слишком маленьким, то очевидно, что различия между изображениями тогда будут нивелироваться, и у нас будет много ложно положительных срабатываний. При слишком большом размере неоправданно повышается ресурсоёмкость алгоритма сравнения. Опыт показывает, что наиболее оптимальным является размер приведенного изображения от 16х16 до 64х64. Так же опыт показывает, что цветовые характеристики изображения оказывают гораздо меньшее влияние на визуальные ощущения схожести изображений по сравнению с яркостными, потому их можно отбросить.
Основные шаги
Итак, простейший вариант алгоритма сравнения похожих изображений будет включать в себя следующие шаги:
- Приведение всех изображений к одному размеру (возьмем для определенности размер 32х32).
- Отбрасыванию цветовой информации (преобразование в серое изображение).
- Нахождение среднеквадратической разности для каждой пары уменьшенных серых изображений.
- Сравнение полученной среднеквадратической разности с некоторым порогом.
Здесь порог определяет меру схожести изображений. Так если выбрать порогом 0%, то алгоритм найдет только полностью идентичные изображения. При 5% пороге алгоритм сможет найти также визуально похожие изображения, которые могут различаться разрешениям, качеством сжатия, наличием мелких надписей, кропом и т.д. при незначительном количестве ложных срабатываний. При пороге выше 10%, как правило, количество ложных срабатываний может превышать число положительных срабатываний. Несомненно, данный алгоритм в том или ином варианте должен быть реализован в любой программе, осуществляющей поиск похожих изображений. Вариации обычно касаются способа получения уменьшенного изображения, размеров уменьшенного изображения и способов его квантования по цветовой палитре, выбора метрики, определяющей степень различия изображений.
Недостатки базового алгоритма
К недостаткам данного алгоритма, можно отнести его плохую чувствительность при сравнении слабо контрастных изображений, а также изображений без крупномасштабных особенностей (контурные рисунки, изображения текста). Слабая чувствительность объясняется тем, что при уменьшении исходного изображения до размера 32х32, как правило все такие изображения становятся не различимыми друг от друга. Также недостатком данного подхода можно считать квадратическую зависимость времени исполнения алгоритма в зависимости от общего числа изображений, так как нужно провести сравнение для каждой пары изображений. Так для сравнения пары отнормированных изображений друг с другом алгоритму нужно выполнить порядка 10^3 арифметических операций, то для тысячи изображений это уже порядка 10^9 операций, а для миллиона изображений — 10^15 операций. Конечно не у каждого пользователя есть коллекции изображений с миллионом картинок, но даже для сравнения 100 тысяч изображений (что не является такой уж редкостью для фотолюбителей) нам требуется выполнения порядка 10^13 операций, что может занять существенное время даже на современном железе.
Быстрый алгоритм
Как уже было сказано, у данной базовой реализации алгоритма две проблемы — невысокая точность на изображениях без крупномасштабных особенностей и квадратичная зависимость времени исполнения от общего числа изображений. Первая проблема достаточно специфична и характерна для довольно узкого круга изображений, потому далее мы сосредоточимся на решении второй проблемы. Очевидно, что данный алгоритм хорошо распараллеливается и векторизуется. Однако, в рамках данной статьи мне хотелось бы остановиться не на программной, а на алгоритмической оптимизации данного алгоритма.
Соотношение сторон
Визуально одинаковые изображения, как правило, обладают близкими соотношениями ширины и высоты. Отсюда логичный вывод — сравнивать только изображения с близкими соотношениями сторон. На практике, большинство изображений в одной коллекции, как правило, имеет одинаковое соотношение сторон (например — 3:4), но имеет разную ориентацию (вертикальную или горизонтальную). Таким образом, мы получаем два изолированных класса изображений, которые не обязательно сравнивать друг с другом. Приблизительное ускорение алгоритмов от этого факта — около двух раз.
Предварительное сравнение
Первый самый очевидный шаг: если мы один раз уменьшили изображение, то почему бы не сделать это снова? Делаем из картинки 32х32 картинку размером 4х4, где каждая точка уменьшенного изображения представляет собой усредненную яркость соответствующей части исходного изображения размером 8х8. Можно математически строго доказать, что среднеквадратическая разность для этого уменьшенного изображения будет не больше, чем среднеквадратическая разность исходного изображения. Следовательно, мы можем путем предварительного сравнения уменьшенных изображений размером 4х4 создать своеобразный фильтр, который будет отсеивать большую часть кандидатов на полноценное сравнение (при условии, что в выборке большая часть изображений относительно уникальны). Таким несложным приемом можно достичь, как несложно подсчитать, практически 50-и кратного ускорения. Однако, очевидно, что чем выше порог, с которым мы сравниваем изображения, тем меньше эффективность данного фильтра.
Одномерное индексирование изображений
Как известно, поиск в упорядоченном массиве данных может быть осуществлен за время порядка О(ln(N)), в отличие от неупорядоченного, которое требует О(N). Таким образом, если каким-то образом нам удастся упорядочить изображения, то теоретически можно свести квадратичную сложность поиска О(N^2) к квазилинейной — О(N*ln(N)). И так попытаемся создать индекс, с помощью которого мы будем производить сортировку изображений. Для этого берем нашу уменьшенную картинку размером 4х4 и уменьшаем ее еще в два раза до размера 2х2. Из этой картинки легко сформировать первый индекс:
i[0] = (p[0][0] + p[0][1] + p[1][0] + p[1][1])/4,
который представляет собой среднюю яркость нашего изображения. Фактически, это изображение, уменьшенное до размера 1х1. Среднеквадратическая разность исходных изображений, будет не меньше, чем разность их интенсивностей. Таким образом, если порог для сравнения изображений имеет значение t, то все возможные кандидаты на сравнение должны иметь среднюю яркость в диапазоне от i[0] — t до i[0] + t. Фактически, если мы отсортируем все изображения по индексу i[0], то можем проводить сравнение со значительно меньшим числом изображений — 2*t/255. Не сложно подсчитать, что для типичного порога в 5% — имеем теоретический выигрыш в 10 раз. Практически, выигрыш будет меньше, так как статистическое распределение изображений по средней яркости не равномерно в диапазоне [0...255], а имеет колоколообразный максимум вблизи значения 127 и спадает по краям диапазона. Его фактическая ширина, а следственно и практический выигрыш алгоритма от теоретически возможного составляет порядка 70-80%.
Многомерное индексирование изображений
Помимо средней яркости i[0], из изображения размером 2x2 можно построить еще 3 дополнительных индекса:
i[1] = 128 + (p[0][0] — p[0][1] + p[1][0] — p[1][1])/4,
i[2] = 128 + (p[0][0] + p[0][1] — p[1][0] — p[1][1])/4,
i[3] = 128 + (p[0][0] — p[0][1] — p[1][0] + p[1][1])/4,
которые имеют простой физический смысл: индекс i[1] показывает на сколько левая часть изображения ярче чем правая, i[2] — на сколько верхняя часть ярче нижней, а i[3] — на сколько отличаются диагонали изображения. По всем этим индексам можно также отсортировать изображения, как и по первому, причем все возможные кандидаты на сравнение будут лежать в диапазонах от i[j] — t до i[j] + t. Т.е. в четырехмерном пространстве, образованном этими индексами область поиска будет представлять 4-х мерный куб со стороной 2*t и центром с координатами, образованными индексами искомого изображения. Теоретическое ускорение, равно отношению объема этого 4-мерного куба к общему объему индексного пространства и равна (2*t/255)^4 = 1/10000. Практическое ускорение значительно скромнее, так как эффективная ширина распределения изображений по индексам i[1] и i[2] составляет порядка 40-50%, а i[3] — всего 20-30% от максимально возможного. Из-за узкого фактического диапазона, на практике использование последнего индекса часто вообще не целесообразно, потому можно ограничиться первыми 3-мя индексами. Тем не менее практически достижимое ускорение достигает двух порядков (для пороговой разности в 5%).
Основные этапы улучшенного алгоритма
И так, можно обобщить наши рассуждения и привести основные шаги, которые необходимо сделать в рамка алгоритма быстрого сравнения изображений.
- Приведение всех изображений к одному размеру (32х32) и отбрасывание цветовой информации.
- Нахождение уменьшенного изображения для предварительного сравнения размером 4х4.
- Построение n-мерного индекса изображения на основании изображения для предварительного сравнения.
- Определение границ области поиска в n-мерном индексном пространстве.
- Проверка соотношения сторон у кандидатов из этой области.
- Проведение предварительного сравнения изображений с кандидатами прошедшими предыдущий пункт.
- Проведение полноценного сравнения изображений с кандидатами прошедшими предыдущие пункты.
Недостатки быстрого алгоритма
В целом эффективность индексирования сильно зависит от порога схожести изображения — при нулевом пороге сложность поиска похожих изображений приближается к линейной О(N), а при большом пороге к квадратичной О(N^2). Тем не менее, это является значительным прогрессом, так как в базовом варианте алгоритма сложность поиска всегда квадратична О(N^2). Также стоит отметить, что на практике для реализации сортировки по n-мерному индексному пространству приходится организовывать n-мерный массив со списками изображений, лежащих в определенном диапазоне индексов. Что вносит дополнительные накладные расходы и делает неоправданным использование индексирования большой размерности, а также не эффективность такого индексирования для небольших коллекций изображений.
Заключение
В целом, если суммировать все улучшения, которые применяются в улучшенном варианте алгоритма, то получаем выигрыш на 3-4 порядка по сравнению с базовой реализацией. Тесты на больших коллекциях изображений показывают, что это действительно так. Так непосредственно сравнение изображений друг с другом занимает порядка 30 сек на одноядерном процессоре для коллекции 100 тысяч изображений. На практике, скорость сравнения становится несущественным фактором в общем процессе поиска изображений — ведь их еще нужно найти, считать с диска и сформировать уменьшенные изображения (хотя конечно последние два пункта можно выполнять только 1 раз, так как очевидно, что уменьшенные изображения весом всего по 1000 байт целесообразно сохранять для повторного использования).
Надеюсь, что читателей заинтересовало мое изложение. Возможно, даже кому-то показалось полезным. Жду отзывов.
P.S. Програмная реализация
C момента написания данной статьи прошло достаточно много времени. Я решил сделать небольше дополнение к ней. В рамках проекта Simd был написан класс на C++ ImageMatcher, который реализует алгоритм, описанный в данной статье. Приятного использования!
