Perceptual Image Hashing Using Latent Low-Rank Representation and Uniform LBP

Abstract

Robustness and discriminability are the two most important features of perceptual image hashing (PIH) schemes. In order to achieve a good balance between perceptual robustness and discriminability, a novel PIH algorithm is proposed by combining latent low-rank representation (LLRR) and rotation invariant uniform local binary patterns (RiuLBP). LLRR is first applied on resized original images to the principal feature matrix and to the salient feature matrix, since it can automatically extract salient features from corrupted images. Following this, Riulocal bin features are extracted from each non-overlapping block of the principal feature matrix and of the salient feature matrix, respectively. All features are concatenated and scrambled to generate final binary hash code. Experimental results show that the proposed hashing algorithm is robust against many types of distortions and attacks, such as noise addition, low-pass filtering, rotation, scaling, and JPEG compression. It outperforms other local binary patterns (LBP) based image hashing schemes in terms of perceptual robustness and discriminability.

1. Introduction

With the rapid development of multimedia information processing technology and the growing popularity of the Internet, the dissemination of digital contents such as digital images, audio and video via internet has become more and more popular. At the same time, however, the contents of digital data can easily be modified or forged without leaving any visible traces [1,2,3]. To verify the authenticity of digital images and to protect their intellectual property, perceptual image hashing (PIH) has emerged as an effective technology for image security and authentication and has attracted extensive attention [4,5]. A PIH function maps an input image to a fixed size binary string called image hash, based on an image’s appearance to human eyes [6,7]. The hash values can be used to represent digital image contents, which should tolerate content preserving distortions but should reject malicious attacks that change image contents. Consequently, images with the same visual appearance should have similar hash values, while visually distinct images should have totally different hash values [8,9,10].

General PIH schemes consist of three steps: pre-processing, feature extraction and hash generation, which in the past decades have found extensive applications in many fields, such as image authentication, image retrieval, image recognition and digital watermarking [11,12,13,14,15,16,17]. One of the key steps in a PIH scheme is robust features extraction. A high performance PIH scheme is dependent on suitable features. A local binary pattern (LBP) is originally proposed by Ojala et al. [18] and is always an effective texture feature extraction method, due to its rotation and scale invariance [19,20,21]. To achieve good robustness of image hashes, LBP has been exploited to extract suitable features in PIH schemes in recent years, and many LBP based PIH schemes have been reported in the literature. Bai and Hatzinakos [22] proposed a biometric hashing method based on LBP, and the biometric hash code that is generated from the LBP based histogram sequence is robust to lighting changes; however, the robustness against other content preserving operations has not been demonstrated. Davarzani et al. [23] employed a center-symmetric local binary pattern (CSLBP) to extract image features from non-overlapping image blocks and to obtain hash values. This PIH scheme can distinguish non-malicious manipulations from malicious distortions, but it has a weak balance between robustness and discriminability. To increase the robustness, they improved the scheme by combining the singular value decomposition (SVD) before the feature extraction [24]. However, the improved PIH algorithm is not robust against geometrical distortions. Chen et al. [25] used block truncation coding and CSLBP to produce an image hash, but it does not have a high robustness against noise addition. Qin et al. [26] first applied SVD to create a secondary image, and then employed block truncation coding (BTC) and CSLBP to generate a compact binary hash. The results showed a satisfactory robustness to common content preserving manipulations, as well as good uniqueness, but there is no good robustness against large geometrical distortions. Patil and Sarode [27,28,29,30] designed some new PIH schemes by using improved CSLBP methods. First, original images are divided into sub-blocks in these algorithms, and some modified CSLBP approaches are used to extract 8-bin histograms as image features. Finally, double bit quantization is employed to generate a hash code for original images. Experimental results proved that the proposed schemes are robust against content preserving manipulation and that they are sensitive to content changing and structural tampering. But these PIH algorithms have low robustness against serious geometrical distortion. Considering the good performance of Noise Resistant LBP (NRLBP) in a noisy environment, Abbas et al. [31] presented a PIH scheme based on SVD and NRLBP, which uses SVD transformation and NRLBP to obtain suitable features for the generation of perceptual image hash values. It has enhanced the robustness to content preserving operations but does not obtain a good tradeoff between robustness and discriminability.

The above mentioned PIH schemes based on LBP directly extract features from the original image and do not produce a robust secondary image with primary features. It is hard for them to achieve a good balance between robustness and discriminability. To obtain different perceptual image hash values for visually different images, a novel PIH scheme is proposed in this paper by using latent low rank representation (LLRR) and rotation invariant uniform local binary patterns (RiuLBP); LLRR is exploited to extract principal and salient features since it is able to effectively extract salient features from corrupted data; following this, a RiuLBP features extraction from principal and salient components is used to generate a final hash code.

This paper is organized as follows. In Section 2, the principle of low-rank representation and the local binary pattern is introduced. Section 3 describes the proposed PIH scheme. The experiments and analysis are given in Section 4. Section 5 concludes the paper.

2. Low-Rank Representation and Local Binary Pattern

2.1. Latent Low-Rank Representation

The low-rank representation (LRR) method aims at finding the lowest-rank representation among all the candidates. When the observed data matrix is used as the dictionary A, recovering the low-rank representation from the given observation $X_o$ can be written as the following convex optimization problem [32,33]:

$$\begin{array}{l}\underset{Z,E}{min}{\Vert Z\Vert }_{\ast }+\lambda {\Vert E\Vert }_1,\\ s.t.X_o=AZ+E\left(X_o=X_{o}Z+E\right),\end{array}$$

(1)

where ${\Vert ·\Vert }_{\ast }$ denotes the nuclear norm of a matrix, i.e., the sum of the singular values of the matrix. ${\Vert ·\Vert }_1$ is the L1-norm characterizing the sparse noise E. $\lambda >0$ is a regularization parameter for balancing the influences of the sparsity error term. Wang et al. [33] applied LRR to multi-view spectral clustering by separately imposing a low-rank constraint on each view and achieved the multi-view agreement via an iterative fashion.

While $A=X_o$, this assumption may be invalid, and the data sampling is insufficient. So, LRR may not represent the subspaces effectively, and the recovery robustness may be weakened. LLRR can be regarded as an enhanced version of LRR, which constructs the dictionary A using both observed data $X_o$ and unobserved hidden data $X_H$; it is more accurate and robust to noise than LRR for subspace representation [34,35]. To resolve the problem of insufficient sampling and to improve the robustness to noise corruption, LLRR is exploited to extract suitable image features during the PIH generation. An approximate recovery can be achieved by analyzing the properties of the hidden effects as follows:

$$\begin{array}{l}\underset{Z,E}{min}{\Vert Z\Vert }_{\ast }+\lambda {\Vert E\Vert }_1\\ s.t.X_o=\left[X_o,X_H\right]Z+E.\end{array}$$

(2)

The hidden effects recovery problem for corrupted data in Equation (2) can be solved by the following convex optimization problem:

$$\begin{array}{l}min{\Vert Z_{O|H}\Vert }_{\ast }+{\Vert L_{H|O}\Vert }_{\ast }+\lambda {\Vert E\Vert }_1\\ s.t.X_o=X_o{Z}_{O|H}+L_{H|O}{X}_O+E,\end{array}$$

(3)

where $Z_{O|H}$ and $L_{H|O}$ correspond to the principal component and the salient component, respectively. For the sake of simplicity, we replace $X_o$, $Z_{O|H}$ and $L_{H|O}$ with X, Z and L, respectively. Thus, the convex optimization problem in Equation (3) can be rewritten as:

$$\begin{array}{l}min{\Vert Z\Vert }_{\ast }+{\Vert L\Vert }_{\ast }+\lambda {\Vert E\Vert }_1\\ s.t.X=XZ+LX+E,\end{array}$$

(4)

where $X\in {ℝ}^{d\times n}$, $Z\in {ℝ}^{n\times n}$ and $L\in {ℝ}^{d\times d}$. The parameters d and n are the feature vector size and the number of features, respectively. This problem can be solved via the Augmented Lagrange Multiplier (ALM) [36] method.

2.2. Local Binary Pattern

There are many LBP operators and LBP feature extraction methods are reported in image recognition and image security fields, among which the RiuLBP operator is one of most popular texture operators due to its rotation invariance and low dimension [37]. The basic LBP is a gray-scale invariant which transforms the neighborhood pixels into a set of binary codes by taking the center pixel as a threshold representing the center pixel, and it is defined as follows:

$$LB{P}_{P,R}={\displaystyle \sum _{p=0}^{P-1}s\left(g_p-g_c\right)2^p},$$

(5)

where R denotes the scale of the radius of neighborhoods, P denotes the number of sampling points, $g_c$ is the gray value of the center pixel, $g_p$ is the circularly symmetric neighbor, and s(*) is the sign function that returns the sign of the specified number.

When there are at most two bitwise 0/1 transitions, the pattern is called a uniform one. The number of uniform patterns is $P\left(P-1\right)+2$, which is less than the number $2^P$ of the basic LBP feature. A function $U(\Delta )$ is defined to return the number of spatial transitions (bitwise 0/1 transitions) in the pattern $\Delta$, and it can be written as:

$$U\left(LB{P}_{P,R}\right)={\displaystyle \sum _{p=0}^{P-1}\left|s\left(g_{\mathrm{Mod}\left(p+1,P\right)}-g_c\right)-s\left(g_p-g_c\right)\right|,}$$

(6)

where the function $Mod\left(x,y\right)$ returns the remainder after a number x is divided by a divisor y.

In order to achieve good discriminability and robustness of the perceptual image hash, the RiuLBP feature descriptor is utilized to extract stable image features. Instead of the ordered binary coding of the basic LBP, the center pixel of RiuLBP is denoted by simply counting ones in the basic LBP coding for uniform patterns [38], denoted by $LB{P}_{P,R}^{riu}$, as shown below:

$$LB{P}_{P,R}^{riu}=\{\begin{array}{lll}{\displaystyle \sum _{p=0}^{P-1}s}\left(g_p-g_c\right)\hfill & & if\mathrm{U}\left(LB{P}_{P,R}\right)\le 2,\hfill \\ P+1\hfill & & otherwise.\hfill \end{array}$$

(7)

From Equation (7), we can see that the RiuLBP feature only has P + 2 distinct patterns.

3. Proposed Perceptual Image Hashing Algorithm

In order to achieve a good balance between discriminability and robustness, a new PIH scheme is proposed in this paper by combining LLRR and LBP features (called LLRR-RiuLBP). In the proposed scheme, LLRR is first employed in order to obtain the principal and salient components of the original images, considering its robustness of salient feature extraction to corrupted data; following this, the RiuLBP feature extraction is applied to the principal and salient components and generates the perceptual hash. The proposed PIH scheme consists of three main stages: pre-processing, feature extraction, and hash generation. The block diagram of the proposed image hashing scheme is shown in Figure 1, and the whole hash generation process is depicted as follows.

Step 1:

For color images, only the luminance component is considered because it contains significant information on the input images. An original color image I is first converted to a grayscale image I_g.

Step 2:

In order to produce a fixed-length hash code, the image normalization of the bilinear interpolation is applied to the grayscale image, and a resized image I_r is generated with a $M\times M$ size.

Step 3:

Following this, a pixel-wise adaptive Wiener filter is applied to the resized input image I_r in order to reduce disturbances caused by the image operation, such as noise addition and lossy compression; a filtered input image I_f is then generated.

Step 4:

LLRR is applied to the resized input image I_r in order to obtain the principle feature matrix Z, salient feature matrix L and error matrix E using Equation (4).

Step 5:

The principle feature matrix Z and salient feature matrix L are divided respectively into non-overlapping sub-blocks with a $b\times b$ size. For each image sub-block, the normalized histogram of the CSLBP codes is computed as follows. Consequently, two histograms $H^r,r\in \left\{Z,L\right\}$, are built according to the principle feature matrix Z and salient feature matrix L, respectively.

$$H^r\left(t\right)=\frac{1}{b^2}{\displaystyle \sum _{i=1}^b{\displaystyle \sum _{j=1}^{b}f\left(LB{P}_{P,R}^{riu}\left(i,j\right),t\right)}},t=0,1,\dots ,P+1,r\in \left\{Z,L\right\},$$

(8)

where

$$f\left(x,y\right)=\{\begin{array}{lll}1\hfill & & ifx=y\hfill \\ 0\hfill & & else.\hfill \end{array}$$

(9)

Step 6:

To reduce feature redundancy, zero-mean normalization is applied to the histogram feature to produce a normalized histogram feature ${\overline{H}}^r$ by using Equation (10):

$${\overline{H}}^r=\frac{H^r-\mu }{\delta +\epsilon },r\in \left\{Z,L\right\},$$

(10)

where $\mu$ and $\delta$ are the mean and standard deviations of the feature set $H^r$, and where $\epsilon$ is a minimal value in order to avoid division by zero.

Step 7:

The normalized histogram ${\overline{H}}^r$ is a P + 2 bins histogram, and the features of all the blocks are concatenated in order to generate a final LLRR-RiuLBP feature.

$$H=\left[{\overline{H}}_1^Z,\dots ,{\overline{H}}_q^Z,{\overline{H}}_1^L,\dots ,{\overline{H}}_q^L\right],q=\left(P+2\right)\times {\left(\frac{M}{b}\right)}^2.$$

(11)

Step 8:

The principal component analysis (PCA) is applied on the feature vector H in order to obtain an effective perceptual feature; the process can be written as follows:

$$H_{PCA}=\left[{H^{\prime }}_1,\cdots ,{H^{\prime }}_m\right]m<2q,$$

(12)

where m denotes the feature dimension after the dimension reduction, and where ${H^{\prime }}_{i}i=1,\cdots ,m$ are the principal components after the PCA feature reduction [39].

Step 9:

A binary sequence of perceptual features V is generated by mapping $H_{PCA}$ onto the binary bits.

$$V\left(i\right)=\{\begin{array}{lll}1\hfill & & if{H}_{PCA}\left(i\right)\ge 0.5\hfill \\ 0\hfill & & else\hfill \end{array}i=1,\dots ,m.$$

(13)

Step 10:

A secret key k is used in order to produce pseudorandom sequences W with the use of a chaotic logistic map [40].

$$W=\left\{w\left(i\right)|w\left(i\right)\in \{0,1\}\right\},i=1,\dots ,m.$$

(14)

In order to ensure the security of the PHI scheme, the sequence W is used to scramble the sequence W via a pixel-wise exclusive-or (XOR) operation between the V and W sequences; the scramble feature vector is the final image hash $H_f$.

$$H_f=XOR\left(V,W\right).$$

(15)

4. Experiments and Analysis

To test the performances of the proposed PIH scheme, extensive experiments are conducted on many standard images with a 256 × 256 size, which can be obtained from the CVG-UGR (Computer Vision Group, University of Granada) image database [41]. The normalized Hamming distance was adopted in our experiments in order to measure the similarity between two hashes.

$$Dis\left(H_f,H_f^{\prime }\right)=\frac{1}{m}{\displaystyle \sum _{i=1}^m\left|H_f\left(i\right)-H_f^{\prime }\left(i\right)\right|},$$

(16)

where $H_f$ and $H_f^{\prime }$ are two hash sequences, and where m is the hash length.

In the experiments, the parameters of the resized image size M, sub-block size b, LBP radius R, LBP pixel number P of the neighbor, and final perceptual hash length m are set to 256, 4, 1, 8 and 500, respectively.

All the experiments are tested on a laptop, the Intel Core i-3630QM 2.66 GHz CPU (Intel Corp., Santa Clara, CA, USA), with an 8 GB memory and running MATLAB 2016a (Mathworks Inc., Natick, MA, USA). The average time cost is computed on test images with a 256 × 256 size, and the average running times of the different PIH methods [13,24,26] are listed in

Table 1. The average running times of different PIH methods.

Methods	Average Running Time
Liu et al.’s scheme [13]	2.36
Davarzani et al.’s scheme [24]	1.49
Qin et al.’s scheme [26]	1.62
Proposed scheme	2.58

. Our method and Qin et al.’s method [13] need more time cost than the other two methods [24,26] because of the use of the LRR operations.

4.1. Perceptual Robustness

In order to evaluate the perceptual robustness of the proposed PIH scheme (LLRR-RiuLBP), we conducted some robustness experiments under the common content-preserving attacks, such as JPEG compression, Gaussian filtering, median filtering, noise addition, scaling and rotation (as listed in

Table 2. The content-preserving attacks for robustness testing.

Attacks	Parameters
JPEG compression	Quality factor $\in$ [10, 90]
Gaussian filtering	Standard deviation 0.4, 0.6, …, 1.8
median filtering	Filter size $\in$ [3, 15]
Salt & pepper noise	noise density $\in$ [5%, 15%]
scaling	Scaling ratio $\in$ [0.2, 2.0]
rotation	Rotation angle $\in$ [0, 5.0]

), based on the CVG-UGR image database [41]. Four of the standard test images derived from them are shown in Figure 2. The robustness comparison experiments with previous image hashing schemes, such as Liu et al.’s [13], Davarzani et al.’s [24] and Qin et al.’s [26] schemes are illustrated in Figure 3 in terms of the normalized Hamming distance. Note that each average normalized Hamming distance in Figure 3 is calculated according to all the hash pairs of all the test images and the corresponding attacked images.

It can be seen that the average normalized Hamming distance of the proposed scheme (LLRR-RuiLBP) is less than Liu et al.’s and Qin et al.’s methods. That is to say, our PIH scheme is more robust to content-preserving attacks than existing schemes [13,24,26]. This is partly because the LLRR adopted in the proposed scheme can effectively extract principle features from corrupted data.

4.2. Discriminability

To evaluate the anti-collision performance of image hashing, 696 hash codes are generated via the proposed PIH scheme, based on 696 test images from the CVG-UGR image database [41]; following this, 378,400 normalized Hamming distances are calculated between the hash pairs of different images. The histogram of the normalized Hamming distances is shown in Figure 4. One finds that the distribution of the normalized Hamming distance proximately obeys a normal distribution with a mean of μ = 0.4825 and with a standard variation of δ = 0.0451. Consequently, given the threshold $\tau <\mu$, the collision probability $P_c$ can be computed as follows:

$$P_c\left(\tau \right)=\frac{1}{\sqrt{2\pi }\delta }{\displaystyle {\int }_{-\infty }^{\tau }{e}^{\left(-\frac{\left(x-\mu \right)}{2{\delta }^2}\right)}dx}=\frac{1}{2}erfc\left(-\frac{\tau -\mu }{\sqrt{2}\delta }\right),$$

(17)

where $erfc(•)$ is a Gauss error function. The collision probabilities of the proposed PIH scheme for different thresholds $\tau$ are shown in

Table 3. A comparison of collision probability of different schemes under various thresholds.

Threshold τ	Collision Probability
	Liu et al.’s Scheme [13]	Davarzani et al.’s Scheme [24]	Qin et al.’s Scheme [26]	Proposed Scheme
0.26	0.3694	2.1125 × 10−6	1.5412 × 10−5	4.0388 × 10−6
0.24	0.1351	1.1043 × 10−6	2.2805 × 10−6	3.7881 × 10−8
0.22	0.0306	5.6748 × 10−7	2.2853 × 10−7	2.9354 × 10−9
0.20	0.0041	2.8665 × 10−7	3.0222 × 10−8	1.8778 × 10−10
0.18	3.2451 × 10−4	1.4233 × 10−7	2.7002 × 10−9	9.9118 × 10−12
0.16	1.4608 × 10−5	6.9462 × 10−8	2.0399 × 10−10	4.3144 × 10−13
0.14	3.7352 × 10−7	3.3320 × 10−8	1.2995 × 10−11	1.5481 × 10−14
0.12	5.3909 × 10−9	1.5710 × 10−8	6.9822 × 10−13	4.5771 × 10−16
0.10	4.3729 × 10−11	7.2801 × 10−8	3.1634 × 10−14	1.1149 × 10−17

. From this table, it can be concluded that the collision probability decreases with a decreasing threshold $\tau$. Additionally, the hashes generated by the proposed PIH scheme have a better discriminability than some of the existing image hashing schemes [13,24,26].

4.3. Security

In our scheme, the image hash is dependent on the secret key, and different secret keys will produce distinct hashes. Figure 5 tests the security of the proposed PIH scheme based on the average normalized Hamming distance sequences (with a size of 1001), between the hash pairs generated by one correct secret key and those generated by 1000 wrong secret keys. One can observe that only the 500th normalized Hamming distance (with the correct secret key) is located in the vicinity of 0, and it is very difficult for an unauthorized user to get the same hash without the correct secret key. The proposed PIH scheme is therefore key-dependently secure.

5. Conclusions

In this paper, we propose an effective PIH scheme based on LLRR and rotation invariant uniform LBP. LLRR is first employed to obtain a principal feature matrix and a salient feature matrix. Following this, rotation invariant uniform LBP is used to extract robust features for perceptual hash generation. The ability of LLRR to extract salient features, along with the effective texture feature extraction ability of LBP, are both helpful to robustness and discriminability. Experiments show that our proposed perceptual hashing scheme is robust to content-preserving attacks such as JEPG compression, low-pass filter, noise addition, slight rotation and scaling, and that it has better robustness and discriminability performance than existing hashing schemes. In addition, the hashing scheme has high key-dependent security.