# Structural Correlation Based Method for Image Forgery Classification and Localization
## 4 Image Forgery Clustering
```
Input: Image set \(\mathbb{S}\) Output: Clusters of relevant images /* Each image is classified into only 1 cluster */
1 functionquery\((\mathbf{Q},\mathbb{S},\theta)\)
2 Query \(\mathbf{Q}\) in \(\mathbb{S}\) return\(\{\mathbf{P}|\mathbf{P}\in\mathbb{S},\Omega_{\mathbf{Q}}^{\mathbf{P}}\geq \theta\}\)// \(\Omega_{\mathbf{Q}}^{\mathbf{P}}\): similarity score of \(\mathbf{P}\) and \(\mathbf{Q}\) defined in (4)
3 procedureCluster\((\mathbb{S})\) repeat
4 Randomly select an image \(\mathbf{Q}\) in \(\mathbb{S}\) \(\mathbb{L}_{1}\leftarrow\textit{Query}\ (\mathbf{Q},\mathbb{S},\theta)\) Select \(\mathbf{D}_{2}\), the second highest ranking image in the list \(\mathbb{L}_{1}\) \(\mathbb{L}_{2}\leftarrow\textit{Query}\ (\mathbf{D}_{2},\mathbb{S},\theta)\) \(\mathbb{C}\leftarrow\mathbb{L}_{1}\cup\mathbb{L}_{2}\) foreach\(\mathbf{U}\in\mathbb{C}\)do
5 foreach\(\mathbf{V}\in\mathbb{C},\mathbf{V}\
eq\mathbf{U}\)do
6 Compute \(s_{\mathbf{UV}}\)// number of keypoints matching Compute \(\hat{s}_{\mathbf{UV}}\)// number of keypoints matching at relevant position Compute \(l_{\mathbf{UV}}\)// luminance similarity index
7\(\mathbf{T}\leftarrow\underset{\mathbf{U}\in\mathbb{C}}{\arg\max}\ \sum\limits_{\mathbf{V}\in\mathbb{C}}\left(l_{\mathbf{UV}}+\frac{\hat{s}_{ \mathbf{UV}}}{s_{\mathbf{UV}}}\right)\)// Determine centroid \(\mathbf{T}\) of cluster \(\mathbb{C}\) foreach\(\mathbf{V}\in\mathbb{C}\)do
8 if\(\hat{s}_{\mathbf{TV}}<s_{\mathbf{TV}}/2\)then
9\(\mathbb{C}\leftarrow\mathbb{C}\setminus\mathbf{V}\)
10\(\mathbb{C}\) is a new image cluster with centroid \(\mathbf{T}\) \(\mathbb{S}\leftarrow\mathbb{S}\setminus\mathbb{C}\) until\(\mathbb{S}=\emptyset\)
```  
**Algorithm 1**Image forgery clustering  
In addition, we denote by \(\mathbf{U}_{Y}(x,y)\) the luminance value of image \(\mathbf{U}\) at pixel \((x,y)\), which can be calculated as follows [43]:  
\[\mathbf{U}_{Y}(x,y)=0.299\mathbf{U}_{R}(x,y)+0.587\mathbf{U}_{G}(x,y)+0.114 \mathbf{U}_{B}(x,y), \tag{7}\]  
where \(\mathbf{U}_{R}(x,y)\), \(\mathbf{U}_{G}(x,y)\), and \(\mathbf{U}_{B}(x,y)\) are the red, green, and blue color values of \(\mathbf{U}\) at pixel \((x,y)\), respectively. We define \(l_{\mathbf{UV}}\),where \(H\) and \(W\) are height and width of \(\mathbf{U}\), respectively and  
\[\phi(\gamma)= \begin{cases}1,&\text{if }|\gamma|\leq 3,\\ 0,&\text{otherwise}.\end{cases}  \tag{9}\]  
We determine \(\mathbf{T}\), the centroid of image cluster \(\mathbb{C}\) as follows:  
\[\mathbf{T}=\operatorname*{arg\,max}_{\mathbf{U}\in\mathbb{C}}\;\sum_{\mathbf{ V}\in\mathbb{C}}\bigg{(}l_{\mathbf{UV}}+\frac{\hat{s}_{\mathbf{UV}}}{s_{ \mathbf{UV}}}\bigg{)}. \tag{10}\]  
Afterwards, we refine the image cluster by discarding irrelevant images \(\mathbf{V}\) to \(\mathbf{T}\) where \(\hat{\mathbf{V}}\
eq\mathbf{T}\) as follows  
\[\frac{\hat{s}_{\mathbf{TV}}}{s_{\mathbf{TV}}}<0.5. \tag{11}\]  
Therefore, all the retrieved authentic images, with the exception of the centroid image \(\mathbf{T}\), are discarded from the cluster. In other words, \(\mathbf{T}\) is the unique authentic image in \(\mathbb{C}\). Figure 2 illustrates an example of discarding an image from the cluster according to Equation (11). Figure 3 depicts an example of image database indexing and one iteration of the proposed image forgery clustering algorithm to obtain one image cluster with. After each iteration of the proposed clustering algorithm, all the images of the new cluster are excluded from the image database. We repeatedly perform querying and clustering process until the database \(\mathbb{S}\) is empty. Finally, each input image belongs to only one cluster. Figure 2: Image (**d**,**e**) are the illustrations of keypoints matching between couples of images (**a**,**b**), (**b**,**c**), respectively. Although (**b**,**c**) have many matching keypoints, the positions of those keypoints in relative images are different. In this example, image (**c**) is discarded from the cluster.