COPY-MOVE DETECTION ALGORITHM EFFICIENCY INCREASE USING BINARY SPACE PARTITIONING TREES

Andrey Kuznetsov, Evgeny Myasnikov2016 · DOI

Abstract

Duplicates embedding is one of the most frequently used types of digital image manipulation. The copy-move procedure involves copying an image fragment and pasting it into another part of the same image, often with transformations like rotation or scaling. Existing detection methods typically involve feature calculation in overlapping windows followed by a nearest-neighbor search in Euclidean space. This paper proposes using Vantage-Point (VP) trees for the search step, demonstrating significant speed improvements over the traditional KD-tree approach.

Introduction

Copy-move forgery is a prevalent technique in digital image manipulation. Detecting these forgeries is computationally intensive because it requires comparing thousands of image fragments to find near-duplicates. As image resolutions increase, the number of feature vectors grows, making brute-force search ($O(N^2)$) impractical. While KD-trees are commonly used to optimize this search, they still face efficiency challenges in high-dimensional spaces.

Methodology

The authors focus on optimizing the "similar features search" stage of the detection pipeline. The standard process involves several distinct phases: preprocessing, key point detection or overlapping window extraction, feature calculation, and finally, the search for similar features.

The standard pipeline for copy-move forgery detection, highlighting the search stage.

The proposed improvement replaces the KD-tree with a Vantage-Point (VP) tree during the search phase. While a KD-tree partitions space using hyperplanes orthogonal to coordinate axes, a VP-tree uses a "vantage point" to partition data based on spherical distances. This shift is intended to better handle the distribution of image features in Euclidean space.

The core advantage of the VP-tree lies in its alignment with the search metric. Since feature vectors are compared using Euclidean distance, partitioning space into spherical shells is more efficient than the rectangular boxes of a KD-tree. This allows the algorithm to prune larger sections of the search space more effectively.

Visual comparison of space partitioning: (a) KD-tree axis-aligned partitioning versus (b) VP-tree distance-based partitioning.

Results

The authors evaluated the performance using synthetic feature sets of varying sizes. The results indicate that the VP-tree consistently outperforms both brute force and KD-trees as the dataset size increases.

Sample Size (Vectors) Brute Force (sec) KD-tree (sec) VP-tree (sec)
5,000 9.6 5.7 4.6
10,000 39.0 24.5 22.1
15,000 90.0 49.0 47.2

At the 15,000 vector mark, the VP-tree is approximately 4% faster than the KD-tree and nearly twice as fast as the brute-force approach. The authors note that the efficiency gains become more pronounced as the volume of data grows, which is critical for high-resolution image analysis.

Conclusion

Replacing KD-trees with VP-trees in the copy-move detection pipeline offers a measurable increase in efficiency. By utilizing distance-based partitioning, the VP-tree reduces the computational bottleneck of the nearest-neighbor search. Future work could explore optimized vantage point selection and the impact of feature dimensionality on search performance to further refine detection speeds.

Summary updated

Abstract

Duplicates embedding is one of the most frequently used type of digital image change. The copy-move procedure includes copying an image fragment from one part and pasting it to another part of the same image. Moreover, this fragment can be changed using some transformations, like affine or contrast enhancement. Existing copy-move detection methods consist of two main steps: feature calculation in overlapping processing windows and the nearest feature search in Euclidean space using lexicographic sorting or kd-tree search. In this paper we suggest to use binary space partitioning trees on the second step of the detection algorithm – vp-tree (vantage-point tree). We present the search speed comparison using vp-tree and kd-tree. The results show advantage of the proposed solution over kd-tree use.
BibTeX
@misc{kuznetsov2016copy,
  author = {Andrey Kuznetsov and Evgeny Myasnikov},
  title = {{COPY-MOVE DETECTION ALGORITHM EFFICIENCY INCREASE USING BINARY SPACE PARTITIONING TREES}},
  year = {2016},
  doi = {10.18287/1613-0073-2016-1638-373-378},
}
Figure