Image phylogeny tree reconstruction based on region selection

Nowadays, everyone can download, edit and republish any picture on the web, thus contributing to the diffusion of near-duplicate (ND) images. In order to gain an interesting insight on the way NDs are distributed online, recent works have focused on the reconstruction of the image phylogeny tree (IPT), i.e., an acyclic graph describing the genealogical relationship between ND image pairs. IPT reconstruction methods typically leverage the possibility of reconstructing one image from another one only if they are in parent-child relationship. However, as estimating the possible parent-child transformation is computationally expensive, usually a limited set of global editing operations is considered (i.e., compression, geometric and colour transformations applied to the whole image). However, in a real-world scenario it is customary to edit images also using local operations (e.g., logo insertion, object removal, splicing, etc.), which hinder the possibility of correctly estimating the parent-child relationship. In this paper, we propose an algorithm for IPT reconstruction that deals with the presence of local editing operations.