Fuzzy methaheuristic model for copy-move forgery detection on images

Abstract

Many methods have been proposed to detect the originality of an image. One of the most commonly used method, the Copy - move forgery detection (CMFD), is considered here. The contribution of this paper is the application of the new fuzzy distances in clustering using metaheuristics. The family of the used fuzzy distances satisfies the axioms of the fuzzy metric. CMFD method, which includes Variable Neighborhood Search (VNS) and Bee Colony Optimization (BCO) metaheuristics, has been tested and compared with similar methods. The proposed method with the proposed new metric used in this research gave better results than the existing methods. The proposed fuzzy metrics in this paper as well as the problem of $p-$median clustering applied to the problem and compared with existing research in this field give better results.

1 Introduction

Thanks to the constant development of technologies, mobile phones and digital cameras, the use of digital photos is represented in everyday life. They are used as sources of information, but often also as compelling evidence in forensic research, as evidence in court, in journalism, and etc. Modifying the content of such images has become very simple, through certain software tools, so we cannot be sure of the originality of the image. Changes occur by adding or removing certain image content, or making multiple images into a single image, all with the aim of misrepresenting information. For these reasons, it is important to develop new methods for detecting such changes. One of the most common changes is the so-called Copy Move Forgery Detection (CMFD). Changes occur by copying and pasting part of an image to another part within the same image. Such changes can be subsequently scaled, rotated, copied multiple times, and the like. Since the copied and pasted parts are from the same image, their detection becomes even more complex, because the characteristics of the copied and pasted parts are very similar (noise components, color temperatures, gloss, and etc). The image is by its very nature suitable for the application of fuzzy theory system [1]. Here it is the case with fuzzy distance. The parameter that gives the fuzzy nature of that distance can be varied and so come to some of its value which gives good results in concrete in the case of the application of that distance. They are discussed in the second section notions fuzzy T and fuzzy S metrics [2], i.e. distances with appropriate properties. For the distance classes, we use in applications have been shown to be fuzzy metric. The aim of this research is a new fuzzy distance and its application in clustering [1, 3] using metaheuristics. Thus, two metaheuristics are described in the third section were used: VNS (variable neighborhood search) and BCO (bee colony optimization). We compared the results with the results from the literature and showed the success of the proposed methods. All implemented in programming language $C\#.$

This paper is divided into 6 sections. In the following, we present an overview of the literature. The techniques used in this paper, the metaheuristics as well as the distance used in them are given in Section 3 and Section 4. The results we obtained with the proposed techniques as well as the description of the database can be found in Section 5, while Section 6 contains the conclusion of the research and suggestions for further research.

2 Literature review

The forgery regions are determined by computing the similarity between block features. Wang et al. [4] proposed block-based forensics to detect region duplication for an image. The method mainly used the mean intensities of a circle with different radii around the center of the block to represent the features of the block. Ryu et al. [5, 6] used Zernike moments as block features. The method can identify the forged region by copy-rotate-move forgery. Huang et al. [7] proposed a discrete cosine transform (DCT)-based forgery detection method. The image is first divided into overlapping blocks and the DCT is applied, thus the DCT coefficients for each block are quantized by fixed step size q and then rounded to the nearest integer. Wang et al. [8] proposed a forgery method that combines the discrete wavelet transform (DWT) and the DCT. The DWT and DCT are applied to each image block to extract features.

Research gap and objectives are not much clear. Bravo-Solorio and Nandi [9] proposed a polar-based forgery detection method to detect copy-move attacks for an image. This method subdivided an image into overlapping blocks of pixels. Davarazni et al. [10] used multiresolution local binary patterns (MLBP) for forgery detection. This method used LBP operations to extract feature vectors for each block, and then sorted these vectors based on lexicographical order. Lee et al. [11] used a histogram of oriented gradients (HOG) of each block as features; these features are ordered by using lexicographical sorting. The duplicated image blocks are detected by measuring similar block pairs. Li et al. [12] used a polar harmonic transform to extract the rotation and scaling invariant features as block features (similar to the method of Lee et al. [11].

In the paper [19], the authors propose a hybrid model for the problem copy move forgery detection. Their model successfully recognizes different sizes of altered regions. They combine different techniques to improve detection. Using SWT, DCT and SVD techniques reduce the feature vectors. One of the mathematical models was used in the paper [21]. Our proposed model is based on strict mathematical proofs. Improved block-based matching algorithm (IBMA) to solve the problem. Experiment results show that the improved block-based matching algorithm is better than the classical block-based matching algorithm when an image was distorted by Gaussian noise, salt-pepper noise, or JPEG compression. When it comes to problems with different dimensions of images [20], the proposed model passive forensic approach effectively detects copy-move forged regions in medium and large size images. The proposed model reduces the search space before performing actual counterfeit detection. Forgery analysis on a reduced search domain reduces the computation time without compromising the accuracy of the results. On average, it is quite effective at accurately detecting counterfeits and keeps false positive rates low.

3 Fuzzy metrics

In the literature, the notion distance means a mapping that can satisfy many different traits and, depending on them, find their applications. On a set of all fuzzy sets, defined over a set, distance can be considered according to certain properties and applications.

Kramosil and Michalek [13] in 1975 they expanded the concept of Menger’s probabilitic metric spaces at the concept stage and thus first defined the term fuzzy metric space. Among the many results, modified approaches to the concept stage, a significant place is occupied by the results published by Gregory and Sapena with associates (see e.g. [14]) and start from a slightly modified definition of the fuzzy metric space, introduced by George and Veeramani [15]. Dualized definition the S and T fuzzy metric space were introduced in the paper. Some of the applications of such a defined distance in image filtering and segmentation can be found, for example, in [2, 14, 16].

We focused on fuzzy metrics because they are better due to their properties. In this section, we consider the fuzzy $S-$metric and the fuzzy T metric defined in [2].

Definition 1

Fuzzy S-metric space is a triple $(X,\varvec{s},S)$ such that X is a non-empty set, S is a continuous t-conorm and $\varvec{s}$ is a fuzzy set at $X\times X\times (0,+\infty )$ that satisfies the following conditions for all $a,b,c \in X,\alpha , \beta > 0$:

$Sm_1$:

$\varvec{s}(a,b,\alpha )\in [0,1);$

$Sm_2$:

$\varvec{s}(a,b,\alpha )=0 \Leftrightarrow a=b;$

$Sm_3$:

$\varvec{s}(a,b,\alpha )=\varvec{s}(b,a,\alpha );$

$Sm_4$:

$S(\varvec{s}(a,b,\alpha ),\varvec{s}(b,c,\beta ))\ge \varvec{s}(a,c,\alpha +\beta );$

$Sm_5$:

$\varvec{s}(a,b,{}_{-}):(0,+\infty )\rightarrow [0,1]$ is an continuous function.

The fuzzy set $\varvec{s}$ is called a fuzzy S-metric. If instead of $Sfm_1$), we have $\varvec{s}(a,b,\alpha )\in [0,1],$ for the fuzzy set $\varvec{s}$ we say it is a fuzzy S-metric in the broader sense, and $(X,\varvec{s},S)$ is a fuzzy S-metric space in the broader sense.

Definition 2

Fuzzy T-metric space is an ordered triple $(X,\varvec{t},T)$ such that X is a non-empty set, T is a continuous t-norm and $\varvec{t}$ is a fuzzy set at $X\times X\times (0,+\infty )$ that satisfies the following conditions for all $a,b,c \in X,\alpha , \beta > 0$:

$Tm_1$:

$\varvec{t}(a,b,\alpha )\in (0,1];$

$Tm_2$:

$\varvec{t}(a,b,\alpha )=1 \Leftrightarrow a=b;$

$Tm_3$:

$\varvec{t}(a,b,\alpha )=\varvec{t}(b,a,\alpha );$

$Tm_4$:

$T(\varvec{t}(a,b,\alpha ),\varvec{t}(b,c,\beta ))\le \varvec{t}(a,c,\alpha +\beta );$

$Tm_5$:

$\varvec{t}(a,b,{}_{-}):(0,+\infty )\rightarrow [0,1]$ is a continuous function.

The fuzzy set $\varvec{t}$ is called fuzzy T-metric. If instead of $Tfm_1$), we have $\varvec{t}(a,b,\alpha )\in [0,1],$ for the fuzzy set $\varvec{t}$ we say it is a fuzzy T-metric in the broader sense, and $(X,\varvec{t},T)$ is a fuzzy T-metric space in the broader sense.

Definition 3

Fuzzy S-metric $\varvec{s}$ ($T-$metric $\varvec{t}$) is stationary on X if $\varvec{s}$ ($\varvec{t}$) does not depend of $\alpha$, i.e. if for all fixed $a,b \in X,$ function $\varvec{s}_{a,b}(\alpha )=\varvec{s}(a,b,\alpha )$ ($\varvec{t}_{a,b}(\alpha )=\varvec{t}(a,b,\alpha )$) is a constant.

Remark 1

The triangular norm, shorter $t-$norm (triangular conorm, shorter $t-$conorm) is a binary operation $T: [0,1]^2\rightarrow [0,1]$ ($S:[0,1]^2\rightarrow [0,1]$) which satisfies: monotonicity, commutativity, associativity and neutral element is 1 (0).

Theorem 1

[2] If $(X,\varvec{s},S)$ is a fuzzy $S-$metric space and the T $t-$norm dual to $t-$conorm S with respect to the continuous involutive fuzzy complement $\textsf {c},$ then $(X,\textsf{c}\circ \varvec{s},T)$ is a fuzzy $T-$metric space.

If $(X,\varvec{t},T)$ is a fuzzy $T-$metric space and S $t-$conorm dual to the norm T with respect to a continuous involutive fuzzy complement ${\textsf {c}},$ then $(X,{\textsf {c}}\circ \varvec{t},S)$ is a fuzzy $S-$metric space.

Remark 2

The non-increasing function ${\textsf {c}}: [0,1]\rightarrow [0,1]$ is a continuous fuzzy complement, if ${\textsf {c}}(0) = 1$ and ${\textsf {c}}(1) = 0$ hold. If ${\textsf {c}}$ is a continuous function, ${\textsf {c}}$ is said to be a continuous fuzzy complement. Fuzzy complement ${\textsf {c}}$ is involutive if ${\textsf {c}}({\textsf {c}}(a)) = a$ holds for every $a\in [0,1].$

Example 1

[2, 14] The mapping ${{\textbf {t}}}:\mathbb R^+\times \mathbb {R}^+ \rightarrow \mathbb R$ defined by ${{\textbf {t}}}(a,b,{\textsf {K}})=\frac{\min \{a,b\}+{\textsf {K}}}{\max \{a,b\}+{\textsf {K}}},$ where ${\textsf {K}}>0$, is the fuzzy T-metric with respect to multiplication, and ${{\textbf {s}}}(a,b,{\textsf {K}})=\frac{|a - b |}{\max }(a,b)+{\textsf {K}}$ is a fuzzy S-metric with respect to the algebraic sum, $S (a,b) = 1- (1-a) (1-b) = a + b-ab$ is dual it with respect to standard fuzzy complement.

Example 2

[2, 14] If (X, d) is a metric space then the mapping ${{\textbf {t}}}:X\times X \times \mathbb R^+\rightarrow \mathbb R$ defined by

$${{\textbf {t}}}(a,b,{\textsf {K}})=\frac{{\textsf {K}}}{{\textsf {K}}+d(a,b)},$$

is the fuzzy T-metric with respect to the multiplication and its dual (with respect to the standard fuzzy complement) ${{\textbf {s}}}(a,b,{\textsf {K}})=1-{{\textbf {t}}}(a,b,{\textsf {K}})=\frac{d(a,b)}{{\textsf {K}}+d(a,b)}$ is the fuzzy S-metric with respect to the algebraic sum.

Example 3

[2] Mapping ${{\textbf {t}}}:\mathbb R^+\times \mathbb R^+ \rightarrow \mathbb R$ defined by ${{\textbf {t}}}(a,b,{\textsf {K}})=\frac{\frac{a+b}{2}+{\textsf {K}}}{\max \{a,b\}+{\textsf {K}}},$ where ${\textsf {K}}>0$ is a fuzzy T-metric with respect to multiplication, and ${{\textbf {s}}}(a,b,{\textsf {K}})=\frac{|a - b |}{2(\max (a,b)+{\textsf {K}})}$ is the fuzzy S-metric with respect to the algebraic sum, is dual to it with respect to standard fuzzy complement.

Theorem 2

Mapping ${{\textbf {t}}}:\mathbb R^+\times \mathbb R^+ \rightarrow \mathbb R,$ $p\ge 1$ defined by

$$\begin{aligned} {{\textbf {t}}}_{\textsf {K}}(a,b)={{\textbf {t}}}(a,b,{\textsf {K}})=\frac{\root p \of {\frac{a^p+b^p}{2}}+{\textsf {K}}}{\max \{a,b\}+{\textsf {K}}}, \end{aligned}$$

(1)

where ${\textsf {K}}>0$, is a fuzzy T-metric with respect to multiplication.

Proof

We will carry out the proof for the case $p> 1$ (for $p=1$ see [2]). $Tfm_1$) $\;a,b\in \mathbb {R}^+.$ Without loosing any fact, let $a\le b.$ Then we have $a^p\le b^p \Rightarrow a^p+b^p\le 2b^p \Rightarrow \frac{a^p+b^p}{2}\le b^p\Rightarrow \root p \of { \frac{a^p+b^p}{2}}+{\textsf {K}}\le b+{\textsf {K}}=\max \{a,b\}+{\textsf {K}}$, i.e. $1\ge {{\textbf {t}}}_{\textsf {K}}(a,b)=\frac{\root p \of {\frac{a^p+b^p}{2}}+{\textsf {K}}}{\max \{a,b\}+{\textsf {K}}}>0.$

$$\begin{aligned}{} & {} \qquad Tfm_2) (\Leftarrow )\; a=b \Rightarrow \;{{\textbf {t}}}_{\textsf {K}}(a,b)=\frac{\root p \of {\frac{a^p+a^p}{2}}+{\textsf {K}}}{\max \{a,a\}+{\textsf {K}}}=\frac{\root p \of {\frac{2a^p}{2}}+{\textsf {K}}}{a+{\textsf {K}}}=1.\\{} & {} (\Rightarrow )\;{{\textbf {t}}}_{\textsf {K}}(a,b)=1 \Leftrightarrow \root p \of {\frac{a^p+b^p}{2}+{\textsf {K}}}=\max \{a,b\}+{\textsf {K}}\Leftrightarrow \root p \of {\frac{a^p+b^p}{2}}=\max \{a,b\}\\{} & {} a\le b\Rightarrow \root p \of {\frac{a^p+b^p}{2}}=b\Rightarrow \frac{a^p+b^p}{2}=b^p\Rightarrow a^p=b^p \;(a,b> 0) \Rightarrow a=b,\\{} & {} b\le a\Rightarrow \root p \of {\frac{a^p+b^p}{2}}=a\Rightarrow \frac{a^p+b^p}{2}=a^p\Rightarrow b^p=a^p \;(a,b > 0) \Rightarrow b=a. \end{aligned}$$

$Tfm_3$) ${{\textbf {t}}}_{\textsf {K}}(a,b)=\frac{\root p \of {\frac{a^p+b^p}{2}}+{\textsf {K}}}{\max \{a,b\}+{\textsf {K}}}=\frac{\root p \of {\frac{b^p+a^p}{2}}+{\textsf {K}}}{\max \{b,a\}+{\textsf {K}}}={{\textbf {t}}}_{\textsf {K}}(b,a).$

$Tfm_4$) Let us prove inequality

$$\begin{aligned} {{\textbf {t}}}_{\textsf {K}}(a,b) \cdot {{\textbf {t}}}_{\textsf {K}}(b,c)\le {{\textbf {t}}}_{\textsf {K}}(a,c). \end{aligned}$$

(2)

(2)$\Leftrightarrow \frac{\root p \of {\frac{a^p+b^p}{2}}+{\textsf {K}}}{\max \{a,b\}+{\textsf {K}}}\cdot \frac{\root p \of {\frac{b^p+c^p}{2}}+{\textsf {K}}}{\max \{b,c\}+{\textsf {K}}} \le \frac{\root p \of {\frac{a^p+c^p}{2}}+{\textsf {K}}}{\max \{a,c\}+{\textsf {K}}}$

$\Leftrightarrow \frac{\root p \of {\frac{(a/K)^p+(b/K)^p}{2}}+1}{\max \{a/{\textsf {K}},b/{\textsf {K}}\}+1}\cdot \frac{\root p \of {\frac{(b/{\textsf {K}})^p+(c/{\textsf {K}})^p}{2}}+1}{\max \{b/{\textsf {K}},c/{\textsf {K}}\}+1} \le \frac{\root p \of {\frac{(a/{\textsf {K}})^p+(c/{\textsf {K}})^p}{2}}+1}{\max \{a/{\textsf {K}},c/{\textsf {K}}\}+1}.$ For simplicity of writing, we introduce the replacements: $\;\;A=a/{\textsf {K}}, B=b/{\textsf {K}}, C=c/{\textsf {K}},$ so we get

$$\begin{aligned} \frac{\root p \of {\frac{A^p+B^p}{2}}+1}{\max \{A,B\}+1}\cdot \frac{\root p \of {\frac{B^p+C^p}{2}}+1}{\max \{B,C\}+1} \le \frac{\root p \of {\frac{A^p+C^p}{2}}+1}{\max \{A,C\}+1}. \end{aligned}$$

(3)

We have six cases: $\;1)\;A\le B\le C,$ $\;2)\; A\le C\le B,$ $\;3)\;B\le A\le C,$ $\;4)\;C\le B\le A,$ $\;5)\;C\le A\le B,$ $\;6)\;B\le C\le A,\;$ it is enough to examine the first three because from changing the place A and C: ${{\textbf {t}}}_{\textsf {K}}(A,B) \cdot {{\textbf {t}}}_{\textsf {K}}(B,C)\le {{\textbf {t}}}_{\textsf {K}}(A,C)\;\Leftrightarrow {{\textbf {t}}}_{\textsf {K}}(C,B) \cdot {{\textbf {t}}}_{\textsf {K}}(B,A)\le {{\textbf {t}}}_{\textsf {K}}(C,A)$ follow the remaining three.

$$\begin{aligned}{} & {} 1)\quad (3)\Leftrightarrow \frac{\root p \of {\frac{A^p+B^p}{2}}+1}{B+1}\cdot \frac{\root p \of {\frac{B^p+C^p}{2}}+1}{C+1} \le \frac{\root p \of {\frac{A^p+C^p}{2}}+1}{C+1}\\{} & {} \Leftrightarrow \root p \of {\frac{A^p+B^p}{2}}\cdot \root p \of {\frac{B^p+C^p}{2}}+\root p \of {\frac{A^p+B^p}{2}}+\root p \of {\frac{B^p+C^p}{2}}+1\\{} & {} \le B\root p \of {\frac{A^p+C^p}{2}}+B+\root p \of {\frac{A^p+C^p}{2}}+1,\\ \end{aligned}$$

which is true because it is:

$$\begin{aligned}{} & {} \qquad i) \root p \of {\frac{A^p+B^p}{2}}\cdot \root p \of {\frac{B^p+C^p}{2}} \le B\root p \of {\frac{A^p+C^p}{2}}\\{} & {} \Leftrightarrow \; (A^p+B^p)(B^p+C^p)\le 2B^p(A^p+C^p)\\{} & {} \Leftrightarrow \;(B^p)^2+A^pC^p\le B^pA^p+B^pC^p\\{} & {} \Leftrightarrow \;0\le B^p(C^p-B^p)-A^p(C^p-B^p)\\{} & {} \Leftrightarrow \;0\le (B^p-A^p)(C^p-B^p)\\{} & {} \Leftrightarrow \;\top , \\ \end{aligned}$$

$$\begin{aligned}{} & {} ii) \root p \of {\frac{A^p+B^p}{2}}+\root p \of {\frac{B^p+C^p}{2}}\le B+\root p \of {\frac{A^p+C^p}{2}}\\{} & {} \Leftrightarrow \root p \of {\frac{B^p+C^p}{2}}-B \le \root p \of {\frac{A^p+C^p}{2}}-\root p \of {\frac{A^p+B^p}{2}}=f(A) \\{} & {} \qquad f'(A)= \frac{1}{p}(\frac{A^p+C^p}{2})^{\frac{1}{p}-1}\cdot \frac{1}{2}pA^{p-1}-\frac{1}{p}(\frac{A^p+B^p}{2})^{\frac{1}{p}-1}\cdot \frac{1}{2}pA^{p-1}= \\{} & {} \frac{1}{2}A^{p-1}[(\frac{A^p+C^p}{2})^{\frac{1}{p}-1}\!-(\frac{A^p+B^p}{2})^{\frac{1}{p}-1}] \!\le \! 0\Rightarrow f\downarrow \wedge A\!\le \! B\Rightarrow f(A) \!\ge \! f(A_{max})\!=\\{} & {} f(B)=\root p \of {\frac{B^p+C^p}{2}}-\root p \of {\frac{B^p+B^p}{2}}=\root p \of {\frac{B^p+C^p}{2}}-B; \end{aligned}$$

$$\begin{aligned}{} & {} \qquad 2)\quad (3)\Leftrightarrow \frac{\root p \of {\frac{A^p+B^p}{2}}+1}{B+1}\cdot \frac{\root p \of {\frac{B^p+C^p}{2}}+1}{B+1} \le \frac{\root p \of {\frac{A^p+C^p}{2}}+1}{C+1}\\{} & {} \Leftrightarrow (C+1)(\root p \of {\frac{A^p+B^p}{2}}+1)(\root p \of {\frac{B^p+C^p}{2}}+1) \le (B+1)^2(\root p \of {\frac{A^p+C^p}{2}}+1)\\{} & {} \Leftrightarrow C\root p \of {\frac{A^p+B^p}{2}}\cdot \root p \of {\frac{B^p+C^p}{2}}+ C\root p \of {\frac{A^p+B^p}{2}}+C\root p \of {\frac{B^p+C^p}{2}}+C\\{} & {} +\root p \of {\frac{A^p+B^p}{2}}\cdot \root p \of {\frac{B^p+C^p}{2}}+\root p \of {\frac{A^p+B^p}{2}}+\root p \of {\frac{B^p+C^p}{2}}+1\\{} & {} \le B^2\root p \of {\frac{A^p+C^p}{2}}+B^2+B\root p \of {\frac{A^p+C^p}{2}}+B + B\root p \of {\frac{A^p+C^p}{2}} +B+\root p \of {\frac{A^p+C^p}{2}}+1,\\ \end{aligned}$$

which is true because it is:

$$\begin{aligned}{} & {} \qquad i) \quad C\root p \of {\frac{A^p+B^p}{2}}\cdot \root p \of {\frac{B^p+C^p}{2}} \le B^2\root p \of {\frac{A^p+C^p}{2}}\\{} & {} \Leftrightarrow \; C^p(A^p+B^p)(B^p+C^p)\le 2B^{2p}(A^p+C^p)\\{} & {} \Leftrightarrow \;B^{2p}C^p+B^pA^pC^p+B^pC^{2p}+A^pC^{2p} \le 2B^{2p}A^p+2B^{2p}C^p\\{} & {} \Leftrightarrow \;\top ,\\ \end{aligned}$$

because $B^p A^pC^p\le B^{2p}A^p\wedge B^pC^{2p}\le B^{2p}C^p\wedge A^pC^{2p}\le B^{2p}C^p,$

$$\begin{aligned} ii)\; C +\root p \of {\frac{A^p+B^p}{2}} \le B+\root p \of {\frac{A^p+C^p}{2}} \end{aligned}$$

(4)

$$\begin{aligned}{} & {} \Leftrightarrow f(A)=\root p \of {\frac{A^p+B^p}{2}}-\root p \of {\frac{A^p+C^p}{2}} \le B-C\\{} & {} f'(A)\!=\! \frac{1}{p}(\frac{A^p\!+B^p}{2})^{\frac{1}{p}-1}\cdot \! \frac{1}{2}pA^{p-1}\!-\frac{1}{p}(\frac{A^p\!+C^p}{2})^{\frac{1}{p}-1}\!\cdot \frac{1}{2}pA^{p-1}\!=\!\frac{1}{2}A^{p-1}[(\frac{A^p\!+B^p}{2})^{\frac{1}{p}-1}\!-\\{} & {} (\frac{A^p+C^p}{2})^{\frac{1}{p}-1}] \le 0\Rightarrow f\downarrow \wedge 0\le A\Rightarrow f(A)\le f(A_{min})=f(0)=\root p \of {\frac{0^p+C^p}{2}}-\\{} & {} \root p \of {\frac{0^p+B^p}{2}}=\frac{1}{\root p \of {2}}(B-C)\le B-C, \\ \end{aligned}$$

$$\begin{aligned} iii)\quad C\root p \of {\frac{A^p+B^p}{2}} \le B\root p \of {\frac{A^p+C^p}{2}}\Leftrightarrow C^p A^p+C^pB^p \le B^pA^p+B^pC^p \Leftrightarrow \;\top , \end{aligned}$$

$$\begin{aligned}{} & {} \qquad iv)\quad C\root p \of {\frac{B^p+C^p}{2}}+\root p \of {\frac{A^p+B^p}{2}}\cdot \root p \of {\frac{B^p+C^p}{2}}+\root p \of {\frac{B^p+C^p}{2}}\\{} & {} \le B^2+ B\root p \of {\frac{A^p+C^p}{2}}+B\Leftrightarrow \; \root p \of {\frac{B^p+C^p}{2}}[C+\root p \of {\frac{A^p+B^p}{2}}+1]\\{} & {} \le B[B+\root p \of {\frac{A^p+C^p}{2}}+1]\Leftrightarrow \;\top ,\\ \end{aligned}$$

because $\root p \of {\frac{B^p+C^p}{2}}\le B \Leftrightarrow \; B^p+C^p\le 2B^p\Leftrightarrow \;\top ,$ and inequality (4);

$$\begin{aligned}{} & {} \qquad 3)\,\, (3)\Leftrightarrow \frac{\root p \of {\frac{A^p+B^p}{2}}+1}{A+1}\cdot \frac{\root p \of {\frac{B^p+C^p}{2}}+1}{C+1}\le \frac{\root p \of {\frac{A^p+C^p}{2}}+1}{C+1}\\{} & {} \Leftrightarrow \root p \of {\frac{A^p+B^p}{2}}\cdot \root p \of {\frac{B^p+C^p}{2}}+\root p \of {\frac{A^p+B^p}{2}}+\root p \of {\frac{B^p+C^p}{2}}+1\\{} & {} \le A\root p \of {\frac{A^p+C^p}{2}}+A+\root p \of {\frac{A^p+C^p}{2}}+1,\\ \end{aligned}$$

which is true because it is

i):

$\root p \of {\frac{A^p+B^p}{2}}\cdot \root p \of {\frac{B^p+C^p}{2}} \le A\root p \of {\frac{A^p+C^p}{2}}$ $\Leftrightarrow \; (A^p+B^p)(B^p+C^p)\le 2A^p(A^p+C^p)$ $\Leftrightarrow \;A^pB^p+A^pC^p+B^{2p}+B^pC^p\le 2A^{2p}+2A^pC^p$ $\Leftrightarrow \;\top ,$ because $A^pB^p\le A^{2p}\wedge B^{2p}\le A^{2p} \wedge B^{p}C^p\le A^{p}C^p,$

ii):

$\root p \of {\frac{A^p+B^p}{2}}\le A\Leftrightarrow A^p+B^p\le 2 A^p\Leftrightarrow \;\top ,$

iii):

$\root p \of {\frac{B^p+C^p}{2}} \le \root p \of {\frac{A^p+C^p}{2}}\Leftrightarrow B^p \le A^p\Leftrightarrow \;\top .$ The function $F({\textsf {K}})=\frac{a+{\textsf {K}}}{b+{\textsf {K}}},$ where $a,b,{\textsf {K}}>0$, $a<b$, is monotonously increasing, so ${{\textbf {t}}}(a,b,{\textsf {K}}_1) \le {{\textbf {t}}}(a,b,{\textsf {K}}_1+{\textsf {K}}_2),\;\;\;{{\textbf {t}}}(b,c,{\textsf {K}}_2)\le {{\textbf {t}}}(b,c,{\textsf {K}}_1+{\textsf {K}}_2),$ i.e., (2) implies:

$$ {{\textbf {t}}}_{{\textsf {K}}_1}(a,b) \cdot {{\textbf {t}}}_{{\textsf {K}}_2}(b,c)={{\textbf {t}}}(a,b,{\textsf {K}}_1) \cdot {{\textbf {t}}}(b,c,{\textsf {K}}_2) \le {{\textbf {t}}}(a,b,{\textsf {K}}_1+{\textsf {K}}_2) \cdot {{\textbf {t}}}(b,c,{\textsf {K}}_1+{\textsf {K}}_2)$$

$$\le {{\textbf {t}}}(a,c,{\textsf {K}}_1+{\textsf {K}}_2)={{\textbf {t}}}_{{\textsf {K}}_1+{\textsf {K}}_2}(a,c).$$

$Tfm_5$) Obviously, ${{\textbf {t}}}(a,b,-)$ is a continuous function (by parameter ${\textsf {K}}$).$\square$

Remark 3

The inequality (2) does not corect in the case when $p <1.$ This is easy to see by taking for example that $p = \frac{1}{3}$ and $a = \frac{1}{3},$ $b = \frac{1}{2},$ $c = \frac{3}{4}$ ${\textsf {K}}=10,$ or ${\textsf {K}}=0.7$.

Some fuzzy metric spaces satisfy the inequality (2), which is the case in the previous theorem. If $p\in (0,1),$ although (2) is not valid, it does not mean that the inequality of the triangle is not true, but the proof cannot be carried out as in the theorem.

Each of these mappings contains a parameter ${\textsf {K}}$ whose meaning is the distance ${{\textbf {t}}}_{\textsf {K}}(a,b)$ from point a to point b is one fuzzy set defined the domain of parameter ${\textsf {K}}$. Especially if ${\textsf {K}}$ is a constant positive number then the value is distance a crisp number.

By proving this theorem, we confirmed that the proposed function is a distance. When we apply this distance to the CMFD problem, we get that a and b are the pixel values within the blocks, and the sum of all these values within the block represents the distance between the two blocks. K and p are parameters that can be varied. More details in the following sections.

4 Methodology

The $p-$median problem and its extensions are useful to model many real word situations. Problem clustering can formulated as:

$$\begin{aligned} \begin{array}{cc} \min \sum \limits _i\sum \limits _j d_{ij}x_{ij} &{} \\ \text{ Subject } \text{ to } &{} \\ \sum \limits _j x_{ij}=1, &{} \forall i\\ x_{ij}<y_j &{} \forall i,j\\ \sum \limits _j y_{j}=p, &{} \\ x_{ij},y_j\in \{0,1\} &{}. \end{array} \end{aligned}$$

Where are values $x_{ij}$ and $y_j$ binary. $x_{ij} = 1$ if object i belongs to the cluster j, 0 otherwise. $y_j = 1$ if object j represented cluster, 0 otherwise.

Proposed metaheuristics applied to CMFD the problem are given in the step-by-step below:

Step 1::

the tested image a RGB color image we turn it to grayscale

Step 2::

Input image is divided into blocks different dimension (see next section)

Step 3::

For the each block calculated a feature vector

Step 4::

We used metaheuristic to solved problem CMFD (next step)

Step 5. 1::

When used VNS metaheuristic Initialization: We calculate based on the proposed fuzzy metric the distance between each block and thus create a distance matrix. We also define a stop criterion, in this case it was until the values of the objective function are repeated consecutively. We choose the initial solution x (in this case, two blocks representing the clustering centroids) and set STOP = 0 see Fig. 1.

Step 5. 2::

When used BCO metaheuristic see Fig. 2

Fig. 1

VNS algorithm

Fig. 2

BCO algorithm

We used the fuzzy metric presented in the section above for the image processing problem by incorporating it into a metaheuristic. From metaheuristics, we used VNS methods and BCO. We chose metaheuristics for several reasons. Firstly, because the p-median is np difficult problem, and secondly, because they have their own parameters, the variation of which can help us reach the best possible results.

5 The experimental evaluation (Results)

The RVNS, BVNS, and BCO methods are implemented in the $C \#$ programming language on the HP-15-d055 computer, running Windows 10 Pro. Due to the stochastic nature of the method, 200 restarts were performed. and the maximum execution time is set as the stop criterion, $B = 7,$ $NC = 3.$ It is set to the operating time of the CPLEX commercial solver whenever it finds the optimal solutions or to five minutes for the examples from the literature.

Table 1 The results obtained when the image is divided into blocks of dimensions $8\times 8$

Table 2 The results obtained when the image is divided into blocks of dimensions $8\times 8$

When it comes to the blocks themselves, the proposed method is the block-based method, because it works on non-overlapping blocks of the image that is of interest. The possibility of this method for detecting copy-move changes is analyzed, and the influence of the block size on the detection performance of falsified regions, in terms of the false positive FP (False Positive) and the false negative FN (False Negative), is also investigated. The block size varies from $8\times 8,$ $16\times 16$ to $32\times 32$ pixels (Tables 1, 2 and 3). All the described methods and algorithms in this part of the research were applied to a specific example of a publicly available database https://www5.cs.fau.de/research/data/image-manipulation/ (Fig. 3) and compared with the results from the literature [17].

Table 3 The results obtained when the image is divided into blocks of dimensions $16\times 16$

Fig. 3

Images tested I, II, III, IV, V, VI, VII, VIII, IX

The performance of the proposed methods is most often measured in terms of precision and recall. The precision indicates the probability that the blocks which have been changed, have really been detected. The revocation indicates the probability (possibility) of detecting the altered blocks in an image. The true positive (TP) is the number of blocks that have been modified, which have been classified as modified. The false positive (FP) represents the number of original (authentic) blocks that have been classified as modified, while the false negative (FN) represents the number of the blocks that have been modified but classified as original (authentic):

$$\begin{aligned} \mathrm {Precision=TP/(TP+FP)} \end{aligned}$$

(5)

$$\begin{aligned} \mathrm {Revocation=TP/(TP+FN)} \end{aligned}$$

(6)

Column Pic. tells which picture was considered. The second column shows the results from the corresponding work. The other columns show the results obtained by the above method and the fuzzy metric parameter p.

R - Revocation (%)

P -Precision (%)

We used that the value of the parameter in the fuzzy metric is ${\textsf {K}} = 1$.

Tables 1, 2, 3 and 4 show the results of the proposed algorithms when we vary the parameter p from the proposed T fuzzy metric. When looking at and analyzing the proposed approaches of this research are either better and have achieved the same success. When the average success was calculated, the proposed methods were more successful. BCO proved to be better than VNS. A similar conclusion can be made in Tables 5 and 6 when comparing VNS and BCO because no results were found for $32\times 32$ blocks in the literature. We were not able to make a comparison. The results achieved with these methods can be seen in the picture Figs. 4, 5, 6 and 7.

The graphical presentation (Figs. 1, 2, 3, 4 and 5) aims to visually show on different blocks the success of the proposed methods in this paper in relation to the results from the literature.

Table 4 The results obtained when the image is divided into blocks of dimensions $16\times 16$

Table 5 The results obtained when the image is divided into blocks of dimensions $32\times 32$

Table 6 The results obtained when the image is divided into blocks of dimensions $32\times 32$

Fig. 4

Revocation $8\times 8$

Fig. 5

Precision $8\times 8$

Fig. 6

Revocation $16\times 16$

Fig. 7

Precision $16\times 16$

6 Conclusion

The application of the metaheuristics, based on new class of fuzzy metrics, to the problem of the copy move forgery detection images in comparison with the methods applied to the researcher in other papers has shown greater success it.

The proposed methods with fuzzy metrics that we have presented in this research represent an advantage because in their basis there are parameters (metaheuristic and in fuzzy metrics) that can be adjusted and works on their optimality to further improve the performance of the proposed method. In this paper, as an example, we illustrated the changes in the metric parameter by two values. It is also possible to adjust the parameters of the heuristic method and in that way try to make the time success of the algorithm higher.

Further research is considered in the direction of researching the impact of the application of some other fuzzy $T-$metrics and $S-$metrics on the problem of clustering. It is expected that by varying the parameters in the fuzzy metrics as well as in metaheuristics, better results are obtained than before, and in relation to other techniques with which comparisons are made.

The advantages of this research in relation to others is that it gives the possibility to “find out” about fuzzy metrics. This type of distance is characterized by the parameters that appear in it (K and p) and allow choosing the best distance for a specific example of application. There are many other distances that give good results in specific applications, but they are neither metric nor fuzzy metric.