Повышение эффективности обнаружения дубликатов с использованием деревьев двоичного разбиения пространства

Abstract

Встраивание дубликатов является одним из самых часто применяемых методов сокрытия информации на цифровых изображениях. Процесс встраивания заключается в копировании фрагмента изображения из одной области в другую область того же изображения. При этом копируемый фрагмент может быть подвержен различным преобразованиям. Существующие подходы к поиску искажённых таким способом областей состоят из двух ключевых этапов: вычисление векторов признаков в рамках окна обработки с перекрытием и поиск близких векторов в евклидовом пространстве с применением лексикографической сортировки или kd-дерева. В данной работе мы предлагаем использовать на этапе поиска другой вид деревьев двоичного разбиения пространства (binary space partitioning tree) – vp-дерево. В работе представлено сравнение скорости поиска с его помощью и с помощью kd-дерева. Результаты демонстрируют преимущество предлагаемого подхода перед kd-деревом.