Введение.

В статье «Поиск дубликатов изображений с помощью перцептуальных хешей в сравнении с методом цветовой решетки» [1] автор сравнивает два метода поиска похожих изображений – метод перцептуальных хешей, один из современных и активно развивающихся методов поиска, и метод цветовой решётки, который предлагается к использованию автором [2]. Делается вывод о том, что главным недостатком базового метода перцептуальных хешей следует считать низкую точность поиска, приводится график, иллюстрирующий разницу в количестве ошибок между поиском по методу цветовой решетки и поиском по методу перцептуальных хешей.

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

Экспериментальное оборудование и исходные данные.

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

Таблица 1 – Состав экспериментального оборудования.

В описании отдельных экспериментов указывается, какое оборудование и в каком количестве использовалось для измерений.

Исходные данные, использованные для экспериментов, представляют собой 25 миллионов изображений – фотографий объектов недвижимости и снимков интерьера. Все эти изображения предварительно было обработаны с целью извлечения существенной информации, которая использовалась для поиска. Алгоритмы и способы извлечения этой информации приводятся в статьях [1.2].

Среди этих изображений целенаправленно были сгенерированы дубликаты в количестве 10% от общего числа изображений. Таким образом, гарантируется наличие одинаковых изображений в исходных данных.

Для тестирования использовались собственные реализации алгоритма для поиска по методу цветовой решетки и алгоритма по методу перцептуальных хешей. Алгоритм для поиска по методу перцептуальных хешей был реализован в соответствии с описанием, изложенным в статье [3].

Эксперимент 1. Измерение общей скорости поиска.

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

Для измерения общей скорости поиска были проверены все изображения в исходной базе данных, а затем число изображений было разделено на время работы в секундах.

, где C – общее количество изображений, а t – время полной проверки в секундах.

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

На рисунке 1 показаны графики общей скорости поиска в зависимости от количества узлов в вычислительной системе:

Рисунок 1 – Результаты измерения общей скорости поиска.

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

Эксперимент 2. Измерение скорости поиска при условии, что все изображения имеют дубликат.

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

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

Аналогично предыдущему эксперименту база данных была размещена на одном стоечном сервере, а затем перераспределена между 2 и 4 серверами. На рисунке 2 показаны графики скорости поиска в условиях, когда каждое изображение имеет дубликат.

Рисунок 2 – Результаты измерения скорости поиска среди дубликатов.

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

Эксперимент 3. Измерение скорости поиска в зависимости от размера базы данных.

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

В этом эксперименте база данных изображений была распределена между всеми имеющимися вычислительными машинами, ее размер изначально был равен 25 000 000, затем было добавлено еще 25 000 000 (общий размер составил 50 миллионов), а затем еще 50 000 000 (общий размер составил 100 миллионов изображений).

Для всех добавленных изображений также были сгенерированы искусственные дубликаты в количестве 10% от добавляемого числа изображений.

На рисунке 3 показаны результаты измерений скорости в указанных условиях.

Рисунок 3 – Результаты измерений скорости поиска при растущем размере базы данных.

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

Заключение.

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

1. И. М. Ивкин. «Поиск дубликатов изображений с помощью перцептуальных хешей в сравнении с методом цветовой решетки». // Таганрог, Российская Федерация – Актуальные вопросы современной науки, XXIV Международная научно-практическая конференция.  – 30.07.2014.
2. И. М. Ивкин. «Масштабируемый поиск дубликатов изображений по методу цветовой решетки». // Пенза, Российская Федерация – Открытые инновации – вклад молодежи в развитие региона. Том 1. – 06.12.2013.
3. H. Kumar Sarohi, F. Khan. «Image Retrieval using Perceptual Hashing». // IOSR Journal of Computer Engineering (IOSR-JCE) – 02.2013

Все статьи автора «Toledo»