Title: Efficient and Accurate Image Provenance Analysis: A Scalable Pipeline for Large-scale Images Show Chinese title

Title: 高效且准确的图像来源分析：一种适用于大规模图像的可扩展流程

Abstract: The rapid proliferation of modified images on social networks that are driven by widely accessible editing tools demands robust forensic tools for digital governance. Image provenance analysis, which filters various query image variants and constructs a directed graph to trace their phylogeny history, has emerged as a critical solution. However, existing methods face two fundamental limitations: First, accuracy issues arise from overlooking heavily modified images due to low similarity while failing to exclude unrelated images and determine modification directions under diverse modification scenarios. Second, scalability bottlenecks stem from pairwise image analysis incurs quadratic complexity, hindering application in large-scale scenarios. This paper presents a scalable end-to-end pipeline for image provenance analysis that achieves high precision with linear complexity. This improves filtering effectiveness through modification relationship tracing, which enables the comprehensive discovery of image variants regardless of their visual similarity to the query. In addition, the proposed pipeline integrates local features matching and compression artifact capturing, enhancing robustness against diverse modifications and enabling accurate analysis of images' relationships. This allows the generation of a directed provenance graph that accurately characterizes the image's phylogeny history. Furthermore, by optimizing similarity calculations and eliminating redundant pairwise analysis during graph construction, the pipeline achieves a linear time complexity, ensuring its scalability for large-scale scenarios. Experiments demonstrate pipeline's superior performance, achieving a 16.7-56.1% accuracy improvement. Notably, it exhibits significant scalability with an average 3.0-second response time on 10 million scale images, which is far shorter than the SOTA approach's 12-minute duration. Show Chinese abstract

Abstract: 社交媒体上由广泛可用的编辑工具驱动的修改图像的快速传播，要求有强大的法医工具用于数字治理。 图像来源分析通过过滤各种查询图像变体并构建有向图以追踪其进化历史，已成为关键解决方案。 然而，现有方法面临两个基本限制：首先，在低相似性情况下忽略严重修改的图像会导致准确性问题，同时在多种修改场景下无法排除不相关的图像并确定修改方向。 其次，成对图像分析导致二次复杂度，造成可扩展性瓶颈，阻碍了在大规模场景中的应用。 本文提出了一种可扩展的端到端图像来源分析管道，实现了线性复杂度下的高精度。 通过修改关系追踪提高了过滤效果，从而无论查询图像的视觉相似性如何，都能全面发现图像变体。 此外，所提出的管道集成了局部特征匹配和压缩伪影捕捉，增强了对各种修改的鲁棒性，并实现了图像关系的准确分析。 这使得能够生成准确描述图像进化历史的有向来源图。 此外，通过优化相似性计算并在图构建过程中消除冗余的成对分析，该管道实现了线性时间复杂度，确保其在大规模场景中的可扩展性。 实验表明该管道性能优越，准确率提高了16.7-56.1%。 值得注意的是，它在1000万规模的图像上表现出显著的可扩展性，平均响应时间为3.0秒，远短于最先进方法的12分钟。