Manuscript ID : 202406191123169 Visit : 8 Page: -

Article Type: Original Research

Evaluating the Harris ,BRISK and SURF Feature Points in Watermarking Based on Histogram and Knapsack Problem

Subject Areas : Journal of Computer & Robotics

Ali Amiri ¹ , Sattar Mirzakuchaki ^{2
*}

1 - aDepartment of Electronic Engineering, Qazvin Branch, Islamic Azad University, Qazvin, Iran
2 - b Department of Electronic Engineering,Iran University of Science and Technology, Tehran, Iran

Received: 2024-06-19 Accepted : 2024-08-11 Published : 2024-11-18

Keywords: watermarking, feature points, SURF, Knapsack problem, geometric attacks,

Abstract :

With the increasing expansion of the world wide web and social networks, the use of copyright and the prevention of illegal copying in such a way that the proprietorship of the copyrighted work can be proven, has become more popular. With ever-increasing use of the Internet as well as digital audio and video, watermarking has become progressively essential for protecting copyright. In fact, digital watermarking can be a good solution to this problem. Due to having unchangeable nature, applying local features as the second generation of watermarking has gained attention for reaching more stability against attacks. Accordingly, in this article, first, by comparing point-based methods, we choose the most resistant features to attacks based on experiments from the stability perspective. Afterward, an optimal selection process is formulated as a backpack problem to select the stable non-overlapped areas, in which watermark is located. Finally, results are presented for the three feature points algorithms separately.Finally, each selected Region is normalized to obtain a geometrically fixed Region. The proposed plan can withstand various attacks, including the processing of the quasi-noise signals and geometric distortions. The results are compared using the two mentioned feature extraction algorithms and the evaluation of the results is based on the StirMark criterion

References:

[1]Deng, Ch., Gao, X., Li, X., Tao, D.,”Local histogrambased geometric invariant image watermarking”,Signal Processing, Vol. 90, pp. 3256-3264, 2010.
[2] I.J. Cox, J. Kilian, F.T. Leighton, T. Shamoon, Secure spread spectrum watermarking for multimedia, IEEE Transactions on Image Proces- sing 6 (12) (1997) 1673–1687.
[3] N. Agarwal, A. K. Singh, P. K. Singh, “Survey of robust and imperceptible watermarking,” Multimedia Tools and Applications, vol. 78, no. 7, pp. 8603-8633, Apr. 2019.
[4].F. Cayre, C. Fontaine, T. Furon, Watermarking security: theory and practice, IEEE Transaction on Signal Processing 53 (10) (2005) 3976–3987.
[5] P. Bas, J.M. Chassery, B. Macq, Geometrically invariant watermarkingusing feature points, IEEE Trans. Image Process. 11 (9)(2002) 1014–1028.
[6] Tang, C.W., Hang, H.M., “A feature-based robustdigital image watermark scheme”, IEEE Trans. SignalProcess. Vol. 51 (4), pp. 950–958, (2003).
[7] J.S. Seo, C.D. Yoo, Image watermarking based on invariant regions of scale-space representation, IEEE Transaction on Signal Processing 54 (4) (2006) 1537–1549.
[8] X. Wang, J. Wu, P. Niu, A new digital image watermarking algorithm resilient to desynchronization attacks, IEEE Transaction on Information Forensics Security 2 (4) (2007) 633–655.
[9]Singh, C., Ranade, S.K., “Geometrically invariant and high capacity image watermarking scheme usingaccurate radial transform”, Opt. Laser Technol,Vol. 54(30), pp. 176–184, 2013.
[10]D.G.Lowe,Distinctive image features from scalein variant key points,Internationa lJournal of Computer Vision 60(2)(2004)91–110
[11] C. Deng, X. Gao, X. Li, D. Tao, Local histogram based geometric invariant image watermarking, Signal Processing 90 (12) (2010) 3256–3264.
[12]Bay, H., Ess, A., Tuytelaars , T., Gool, L.V., “Speeded-Up Robust Features (SURF)”, in: Computer Vision andImage Understanding, Vol. 110(3), pp. 346-359, 2008.
[13] C. Wang, Y. Zhang, and X. Zhou, "Robust Image Watermarking Algorithm Based on ASIFT against Geometric Attacks", Appl. Sci., 8, 410, 2018.
[14] K. Asifullah M. Summuyya. Robust image watermarking technique using triangular regions and zernike moments for quantization base embedding. Multimed Tools Appl, 2017.
[15] Ch. Deng, X. Gao, X. Li, D. Tao, ”Local histogram based geometric invariant image watermarking”, Signal Processing, Vol. 90(12), December 2010, pp. 3256-3264.
[16] ZEAR, Aditi, SINGH, Amit Kumar, KUMAR, Pardeep. A proposed secure multiple watermarking technique based on DWT, DCT and SVD for application in medicine. Multimedia Tools and Applications, 2016, p. 1-20.
[17] A. Pourhadi, and H. Mahdavi-Nasab, “A robust digital image watermarking scheme based on bat algorithm optimization and SURF detector in SWT domain,” in Multimed Tools and applications, Vol. 79, no. 29, pp. 21653–21677, May 2020.
[18] Sharma V, Mir RN. An enhanced time efficient technique for image watermarking using ant colony optimization and light gradient boosting algorithm. J King Saud Univ Comput Inf Sci. 2019.
[19] B. Kazemivash and M. E. Moghaddam, “A robust digital image watermarking technique using lifting wavelet transform and firefly algorithm,” Multimed Tools Appl., vol. 76, no. 20, pp. 20499–20524, 2017.
[20] M. Amini, M. O. Ahmad and M. N. S. Swamy, “Digital watermark extraction in wavelet domain using hidden Markov model,” Multimedia Tools and Applications, vol. 75, no. 21, pp. 3731-3749, 2017.
[21] L. Zhang and D. Wei, ``Dual DCT-DWT-SVD digital watermarking algorithm based on particle swarm optimization,'' Multimedia Tools Appl., vol. 78, no. 19, pp. 28003_28023, Oct. 2019.
[22] L. Zhang and D. Wei, “Dual DCT-DWT-SVD digital watermarking algorithm based on particle swarm optimization,” Multimedia Tools and Applications, vol. 78, no. 19, pp. 28003–28023, Oct. 2019.
[23] A .Amiri and S. Mirzakuchaki “ A digital watermarking method based on NSCT transform and hybrid evolutionary algorithms with neural networks,” SN Appl Sci vol. 2,no. 10,pp.1–15,sep.2020.
[24]Leutenegger, S., Chli, M., Seigwart, R. Y., “BRISK:Binary Robust Invariant Scalable Keypoints”, IEEE,International Conference on Computer Vision, pp.2548-2555, 2011.
[25]K.Mikolajczyk,C.Schmid,Indexing based on scale in variant interestpoints,in:Proceeding softhe Eighth International Con-ference on Computer Vision,2001,pp.525–531.
[26] Lowe, D. “Distinctive image features from scaleinvariant keypoints” International Journal of Computer Vision, 60,2 (2004), pp. 91-110.
[27] Y. T. Lin, C. Y. Huang, and G. C. Lee, “Rotation, scaling, and translation resilient watermarking for images,” IET Image Processing, vol. 5, no. 4, pp. 328–340, Jun. 2011.
[28] H. Bay, A. Ess, T. Tuytelaars, L. V. Gool, “Speeded-Up Robust Features (SURF)”, in: Computer Vision and Image Understanding, Vol. 110(3), June 2008, pp.346-359.
[29] Alahi, Alexandre, Raphael Ortiz, and Pierre Vandergheynst Freak: Fast retina keypoint, IEEE Conference on
Computer Vision and Pattern Recognition (CVPR), Vol. 10, pp. 510-517, 2012.
[30]M. Assi,R. Haraty “ A Survey of the Knapsack Problem”, 2018 International Arab Conference on Information Technology (ACIT)., 25 March 2019.
[31] P.C. Chu, J.E. Beasley, A genetic algorithm for the multidimensional knapsack problem, Journal of Heuristics 4 (1) (1998) 63–86.
[32] R.J. Moraga, G.W. DePuy, G.E. Whitehouse, Meta-RaPS approach for the 0–1 multidimensional knapsack problem, Computers and Industrial Engineering 48 (1) (2005) 83–96.
[33] J.S. Tsai, W.B. Huang, C.L. Chen, Y.H. Kuo, A feature-based digital image watermarking for copyright protection and content authen- tication, in: Proceedings of the IEEE International Conference on Image Processing, 2007, pp. 469–472.
[34] C. Deng, X. Gao, X. Li, and D. Tao, “Local histogram based geometric invariant image watermarking,” Signal Process., vol. 90, no. 12, pp. 3256–3264, Dec. 2010.
[35] A. F. Qasim, R. Aspin, F. Meziane, and P. Hogg, "ROI-based reversible watermarking scheme for ensuring the integrity and authenticity of DICOM MR images," Multimedia Tools and Applications, 2018.
[36] J.S. Tsai, W.B. Huang, C.L. Chen, Y.H. Kuo, A feature-based digital image watermarking for copyright protection and content authen- tication, in: Proceedings of the IEEE International Conference on Image Processing, 2007, pp. 469–472.
[37] H. W. Tian, Y. Zhao, R. R. Ni, L. M. Qin, and X. L. Li, LDFT-based watermarking resilient to local desynchronization attacks, IEEE Trans. Cybern., vol. 43, no. 6, pp. 2190–2201, Dec. 2013.

Full-Text:

Evaluating the Harris ,BRISK and SURF Feature Points in Watermarking Based on Histogram and Knapsack Problem

Ali Amiri a, Sattar Mirzakuchaki b*

aDepartment of Electronic Engineering, Qazvin Branch, Islamic Azad University, Qazvin, Iran

b Department of Electronic Engineering,Iran University of Science and Technology, Tehran, Iran

Received 19 June 2024, Accepted 11 AUGUST 2024

Abstract

Keywords: watermarking, feature points, SURF,Knapsack problem, geometric attacks.

1.Introduction

One of the challenges in this area is the robustness of the algorithms presented against various attacks, especially geometric attacks [1]. Most of the proposed methods are resistant to geometric attacks [2]. With regard to different purposes of attacks, the two criteria of sustainability and security should be considered in the design of digital watermarking. In general, sustainable watermarking plans develop toward two types of attacks:

1-Signal Processing, and 2- Geometric Distortion.

So far, most of the watermarking methods have been developed to improve sustainability [3].Feature-based watermarking methods are introduced as the second generation of watermarking and are categorized into three sub-categories: torque-based,

histogram-based, and feature points-based. The third sub-category uses the formation of local Regions for watermarking storage and extraction. The features of an image are its edges, corners, texture, and color. The features must have properties such as resistance to image transitions, rotation, and scale changes, as well as noise and local variations. This means that they should have an invariable feature, in which the main information does not collide in attacks [4].

The idea of this research is based on the local feature based sustainability. Bass et al. used the Harris detector to extract feature points from an image [5]. In reference [2], a histogram-based method is also used using Harris feature points. Tang and Hang [6] have used image normalization to resist geometric attacks. They also used the small beat of a Mexican hat to extract Feature points along with normalization of the image and FFT for hidden watermarking.

Since the size of the Region of a feature changes when a watermark is inserted in this Region, the priority is given to selecting non-overlapped (non-shared) watermarks in order to avoid a sharp drop in image quality [7]. In [8], the corner response and the number of adjacent feature points within a Region are used to remove overlapping Feature points. However, the non-overlapped Feature points, which were selected through these parameters, cannot guarantee that the watermark Regions are well distributed in the whole image and the probability of a successful cropping attack rises because the selected Regions do not always have the highest coverage.In [9], a noise-resistant and rotation attack-resistant method is introduced based on the radial angle conversion, which is a Region-based descriptor. The obvious feature of this algorithm is its low computational cost. The coefficients of this conversion are used for binary marking using modulation, but they do not yield good results for a shear attack.

Local features of the image structure are used in many applications, such as object identification, image retrieval, and calibration (grading) of the camera [10]. These features, which are powerful references, have been successfully used in feature-based watermarking methods because they can be maintained even after enduring disturbances such as rotation or detection changes. In general, a feature detector performs a special conversion on the image to extract the local attribute for the inclusion and display of the watermark. However, the feature Region extracted by the detector cannot be used directly for digital marking for the following reasons:

1.Generally, the location and size of the extracted features are accessible to attackers.

2.Including watermark in all Regions results in high image degradation and low strength, as most features overlap[11].

Therefore, a feature-based watermarking program should specify a set of non-overlap Feature points. In addition, the high repeatability of feature points indicates the strength of geometric attacks. Generally, the location and size of the extracted features can be detected by attackers. As stated, the inclusion of watermarking in all Regions results in high degradation of the image and its low strength, since most of the features overlap and are not all fixed. Due to these reasons, we propose an exploratory algorithm to select a set of optimal non-overlap Regions for watermarking. This set also has the maximum distribution feature throughout the target image to resist cropping attacks. In addition, the selection process is applied randomly to prevent the correct identification of the watermarked Regions by attackers. This is formulated as a Multidimensional 0–1 knapsack problem(Multidimensional knapsack problem) and is solved through a genetic algorithm-based approach.

In section 2 we will introduce and compare Feature extraction methods and in section 3 we will introduce the most desirable method which is the most robust method. Then, in Part 4, we will discuss the knapsack problem and in Part 5 the proposed scheme is presented. Sections 6 and 7 describe the algorithms for cluster placement and extraction in our proposal, and finally, Section 8 concludes. As stated, in the proposed scheme after extracting feature points which, with the following experiments, the most robust feature extraction algorithms will be introduced and used in our design and extracted using the knapsack algorithm. Feature extraction algorithms have been selected for higher resistance to attack and the results will be described in detail and separately by the Feature extraction algorithms used.

2. Feature extraction algorithms

Key points are the points of the image that are in scale space of the extremum image. The image scale space contains a set of images. The images of this set are produced using the original image convolution with Gaussian filters and different scales. Simultaneous robust watermarking methods are categorized into three classes including moment-based, histogram-based, and feature-based.Some of the most important algorithms of feature points are described below.

2.1. Harris detector

In this section, the Harris-Laplace detector, constructed from an autoregressive scale matrix adapted from Laplace-Gauss scale and practice, is used [23].

Initially, the space for the input image scale I is calculated through the L function in a set of scale in order to display different levels of resolution, the equation of which is as follows:

L(x,σD) = G(x,σD)*I(x) (1)

In which, x = (x,y) represents the spatial constituents of the image, σD is the differential scale, "*" shows the convolutional action, and the uniform Gaussian kernel G is defined as:

G(x,)= (2)

Then, the autoregressive scale matrix μ(x,σ1,σD) is used in scale space to describe the local image structure and its equation is as follows:

(x,

(3)

In which, σ1 is the integral scale and Li is the first derivative calculated in path i in which the answer to the cornerstone of the principle of the curvature of this matrix through its trace and its determinants is as follows:

C(x,σ1,σD) = det(μ(x,σ1,σD))-0.04 tarce(μ(x,σ1,σD))

(4)

The feature point with a large corner response that indicates a significant rotation (curvature) has a higher repeatability. Then, the candidate points are determined if the corner response is a local maximum and larger than the threshold TR used to filter the non-stable Feature points (variables). Setting a constant value for different input images is difficult [24].

The threshold should be set on 1% of the maximum value of all extracted property regions. In order to achieve scalability variability, the integral scale of all candidate points is compared with the local scale image characteristic scale. The characteristic scale, which is relatively independent of scale change, is obtained by searching for a local extreme across multiple levels of Laplace-Gauss scale. Candidate points are determined for a set of levels of the scale σn by setting σ1 = σD and σD = 0.7σ1, where σn = {δi σ0| σ0 = 1.5, δ = 1.1, i = 1, 2, …, n}.

The value of σ should be small to achieve high accuracy, which is set to 1.1 in this work according to [25]. The level number of scale n depends on possible scale variations in a picture for different applications and set to 15 in our experiments. Laplace Gauss Candidate points are calculated as follows:

(5)

The candidate point on the ith scale iM as a characteristic point with characteristic scale σc (σc = δiσ0), if Laplace Gauss is a local extreme across the scale levels above the predefined threshold as follows:

(6)

(7)

TLoG threshold is set to 10 according to [26]. In order to achieve the invariance of rotation in the output of extraction features, each point of the property is used as the center of the conclusion of the region. The circular character corresponding to the key-dependent radius is used as follows:

(8)

r = α . σc (8)

Which is formulated using the secret key α and characteristic scale of the feature point σc. Obviously, the circular character regions obtained through autoregressive scale matrix and autoregressive scale matrix are highly distinctive and consistent with high repeatability with respect to various image distortions [25].

Key-dependent radius blocks the attacker's access to the feature area by controlling the size of its uncertainty, while watermarking is not included in the area, and the information leakage also decreases. Figure 1 shows Corners extracted Corners extracted by Harris.

Fig.1. Corners extracted by Harris algorithm.

In order to evaluate resistance of proposed feature points, we performed experiments on 3 images of peppers, Lena, and Baboon to select the most resistant one. In our procedure, after finding feature points in a step, we applied Gaussian and salt-and-peppers noises to the images and derive resutls of matching points number. This process was performed after applying a 60-degree rotation as well as a combination of 60-degree rotation and noises. It is obvious that any algorithm that could find more matching points is more resistant. Table 1 presents HARRIS feature points algorithm results. Table 2, on the other hand, shows results of applying Gaussian noises in the experiment.

Table 1 HARRIS Algorithm Performance after Applying Salt-and-Pepper Noises, Rotations, and Noises with Rotations
Image	Baboon	Lena	Peppers
After Applying Noise	0.52846%	1.3072%	10%
After 60-degree rotation	63.5188%	67.2269%	53.1037%
After 60-degree rotation and applying noise	0.64683%	2.521%	11.7241%

Table 2 HARRIS Algorithm Performance after Applying Gaussian Noises, Rotations, and Noises with Rotations.
Image	Baboon	Lena	Peppers
After Applying Noise	0.56911%	3.0501%	9.4737%
After 60-degree rotation	63.5188%	67.2269%	53.1034%
After 60-degree rotation and applying noise	0.60371%	4.2017%	8.2759%

2.2 The SIFT descript

rotation, magnification, view point change, noise, lighting, and stretching. The first step in all methods that work on specific points of the image is finding key points. In this method, Gaussian differences (DoGs) are used to find key points in the image. The process of finding these points begins by constructing a pyramid of images and the convolution of the image I (x, y) with the Gaussian filter G (x, y, σ). So the scale space is displayed as follows.

'*' Represents the convolutional operator in x and y and:

(9)

The blurring rate is controlled with the standard deviation parameter σ by the Gaussian function. The DoG scale space is also obtained by subtracting adjacent scale levels:

(10)

(11)	D(x,y,σ)=[G(x,y,kσ)- D(x,y,σ)]*I(x,y)

Using (9), then:

D(x,y,σ)=[L(x,y,kσ)-L(x,y,σ)] (12)

Fig.2.For each octave from the scale space.

The stages of producing DoG scale space are shown in Figure 2.For each octave from the scale space, the initial images are convoluted and they make the left-hand side. Adjacent Gaussian images are subtracted from each other and form the DoG set on the right. Images in each octane are halved [26,27].The next step is to find the maximum or minimum points in each octave. This is done by comparing each pixel with 26 neighbors in the 3 × 3 region of all adjacent DoG levels in the same octet. If the desired point is larger or smaller than all its neighbors, it is chosen as the point. In the key point descriptor stage, the main feature vector stage will be created. Initially, the gradient range and direction around the key point are sampled. David Low used 4 × 4 arrays with 8 directions per histogram instead of 2 × 2 arrays. Therefore, the attribute vector length is 128 = 8 × 4 × 4 elements for each point.The matching stage of the feature vectors is that the matching phase is at the diagnostic stage, by comparing each of the key points related to the training image. The best candidate points are related to the training image, the best candidate points for matching, are found through the detection of the nearest neighbor in the key points of the training image. The nearest neighbor has the smallest distance with its corresponding point [26].

Table 3 The threshold, the number of found points and the time of calculations in detectors in this comparison [18].
Detector	Threshold	Nb of points	Comp. time(ms)
FH-15	60,000	1813	160
FH-9	50,000	1411	70
Hessian-Laplace	1000	1974	700
HARRIS-Laplace	2500	1664	2100
DoG	Default	1520	400

In order to evaluate resistance of HARRIS algorithm for images of Baboon, Lena, and Peppers, after applying HARRIS algorithm, we applied salt-and-pepper noise to the images, obtaining Table 4. This table demonstrates matching feature points percentages after applying salt-and-pepper noises as well as 60-degree rotations and rotations with applying salt- and-pepper noises. According to this table, the best results of finding primary points have been obtained by applying a 60-degree rotation to the peppers image.

Table 4 SIFT Algorithm Performance After Applying salt-and-pepper, Rotations,and again salt-and-pepper with Rotations
Image	Baboon	Lena	Peppers
After Applying Noise	1.1425%	0.84746%	0.89286%
After 60-degree rotation	0.54526%	0.50847%	1.0045%
After 60-degree rotation and applying noise	0.32146%	0 %	0 %

We derived feature points by SIFT algorithm. Then, after applying Gaussian noises,and 60-degree rotation with applying Gaussian noises, we obtained points matching the original image to see to what extent this algorithm were able to find the same primary points. Results are presented in Table 5.

Table 5 SIFT Algorithm Performance After Applying Gaussian noises and again Gaussian noises with Rotations.
Image	Baboon	Lena	Peppers
After Applying Noise	1.197%	0.59322%	1.2277%
After 60-degree rotation and applying noise	0%	0%	0%

2.3 SURF feature points

SURF (speeded up robust features) is a detector and descriptor of rotation-resistant properties and scale changes, which even acts better than other methods in the field of repeatability, differentiation, and resistance, and can be much faster and more robust in comparisons and calculations .The higher speed of this algorithm is due to the use of integral image techniques [28].

(13)

However, the use of the integral image is used to quickly compute the image convolution with box filters. First, the integral matrix of the photo matrix is constructed. In order to obtain the value of each pixel in the integral matrix, the first pixel with the same address in the image matrix is considered. Then, the total of all the pixels on the left and the top of that pixel, as well as the pixel itself, is calculated and placed in the integral matrix instead of the pixel value with the address specified so that the heuristic and the smallest pixel in the integral image represents the total of all the pixels of the original image. The procedure for generating an integral image matrix is shown in the following equation.

Thus, the total pixels inside the rectangle can be calculated for any dimension in the original image with three complementary actions, regardless of the size of the rectangle using the integral image. For this reason, using the integral image method to calculate the results of applying different filters on the image increases the speed.The Freak algorithm is inspired by fast retina key points. Freak is a method that uses circular shapes that are more intense than the points nearest to the center. Each sample needs to be flattened to have less sensitivity to noise. To accommodate the retina pattern, different core sizes are used for each instance, such as the Brisk algorithm. Exponential variations in size and overlapping strings are the differences in this algorithm with the Brisk algorithm [29].

On the next page, we will give a brief overview of the most famous feature points in this section.Some geometric attacks and compression apply to standard images, and two versions of the fast Hessian detector are compared with the Gaussian filter size, which is shown alongside Hsian's fast detectors, which has the best performance for this FH-9 index.Repeatability factor is referred to as the rate between the corresponding key points and the lowest total number of visible key points in the two images. The corresponding points are identified by looking at the overlapping regions of an image and projection of the points of the region from another image. If the intersection area is larger than 50% of the union, it will be recognized as the corresponding point, which is strongly dependent on the radius of the desired circle. In the other sense, repeatability refers to the number of points discovered after attacks. This factor has been taken using the threshold of the BRISK detector during a sequence. In fair conditions, the SURF detector has been used for Hessian's threshold. A comparison chart is shown in the figure below. The number of points discovered after the attacks is displayed above the column of each of the two types of BRISK and SURF detectors. The results indicate that the SURF descriptor shows higher resistance after attacks, and thus, the more points that can be recovered after the attack has been recovered [18].Some geometric attacks and compression apply to standard images, and two versions of the fast Hessian detector are compared with the Gaussian filter size, which is shown alongside Hsian's fast detectors, which has the best performance for this FH-9 index.

Repeatability factor is referred to as the rate between the corresponding key points and the lowest total number of visible key points in the two images. The corresponding points are identified by looking at the overlapping regions of an image and projection of the points of the region from another image. If the intersection area is larger than 50% of the union, it will be recognized as the corresponding point, which is strongly dependent on the radius of the desired circle. In the other sense, repeatability refers to the number of points discovered after attacks. This factor has been taken using the threshold of the BRISK detector during a sequence. In fair conditions, the SURF detector has been used for Hessian's threshold. A comparison chart is shown in the figure below. The number of points discovered after the attacks is displayed above the column of each of the two types of BRISK and SURF detectors. The results indicate that the SURF descriptor shows higher resistance after attacks, and thus, the more points that can be recovered after the attack has been recovered [28].

Figure 3 shows the recall-precision graphs that are presented using the threshold-based similarity matching for different data types. All descriptors are extracted from one area. As shown, SURF performs well, and BRISK approaches the SURF and the SIFT results do not show a good performance. SIFT results do not show good performance, which shows the limit on the number of duplicate points in these cases.According to the explanation, the SURF descriptor shows a better performance than other detectors, such as SIFT, BRISK and GLOH, so the descriptor has been used in this study as well.

Fig.3.Comparative graph of recall-precision results among the SIFT, SURF, and BRISK algorithms [18].

Similarly to Table 1 for evaluating resistance for Baboon, Lena, and peppers images, after applying SURF algorithm, we applied salt-and-pepper noises to the images to obtain Table 6. It shows matching feature points percentages after applying salt-and-pepper noises and 60-degree rotations as well as rotations along with salt-and-pepper noises. In this experiment, the best results were obtained for applying 60-degree rotation to the Lena image. It is can be seen that SURF algorithm, after applying noises as well as rotations and rotations with noises, was able to find a considerable number of Feature points.

We derived feature points by SURF algorithm. Then, after applying salt-and-pepper noises, 60-degree rotation, and 60- degree rotation with Gaussian rotation, we obtained points matching the original image to see to what extent this algorithm were able to find the same primary points. Results are presented in Table 7. According to the results obtained for SURF and SIFT algorithms, it can be said that SURF algorithm obtained more matching points after applying noises and rotations than SIFT algorithm. Results obtained in references has also been obtained in this study, making it possible to say that SURF algorithm is more resistant than SIFT algorithm, and can show a better resistance against various attacks.

Table 7 SURF Algorithm Performance After Applying Gaussian, and again Gaussian with Rotations.
Image	Baboon	Lena	Peppers
After Applying Noise	27.9037%	44.7619%	46.8439%
After 60-degree rotation and applying noise	22.3433%	39.3586%	38.6293%

2.4 BRISK feature points

BRISK algorithm is a scalable, constant, and binary one that is very useful in machine vision. It gives useful information to describe and match key points of images without primary information on scenes and the camera.

Unlike most famous algorithms, such as SIFT and SURF whose high performance has been proved, it run more quickly. BRISK is based on the configurable circular sampling pattern that measures image shine in form of binary descriptive strings. A feature of BRISK is that it is suitable in wide range applications, particularly in real time applications with limited computation power [23,24].

Table 6 SURF Algorithm Performance After Applying salt-and-pepper, Rotations,and again salt-and-pepper with Rotations
Image	Baboon	Lena	Peppers
After Applying Noise	18.5552%	33.9683%	37.8738%
After 60-degree rotation	73.3711%	88.254%	83.0565%
After 60-degree rotation and applying noise	15.2589%	33.5277%	33.3333%

As it can be seen at Figure 4 SURF has a higher repeatability rate for images than BRISK. We performed the same experiment on Brisk as those we did on SURF and SIFT, results of which is showed in Tables 8 and 9. It is inferred from these two tables that BRISK is properly resistant.

Table8 BRISK Algorithm Performance after Applying Salt-and-Pepper Noises and Noises with Rotations
Image	Baboon	Lena	Peppers
After Applying Noise	9.1377%	25.0597%	19.1781%
After 60-degree rotation and applying noise	3.8353%	9.72850%	8.28630%

Table 9 BRISK Algorithm Performance after Applying Salt-and-Pepper Noises, Rotations, and Noises with Rotations
Image	Baboon	Lena	Peppers
After Applying Noise	19.5467%	37.4603%	38.8704%
After 60-degree rotation	73.3711%	88.2540%	83.0565%
After 60-degree rotation and applying noise	16.0763%	34.6939%	31.4642%

3. Sustainable feature extraction

SURF is a fast-moving feature points at rising speed of a detector and descriptor of rotation-resist feature and scale modification, which acts better than other extraction methods in the field of repeatability, distinctness, and resistance. Detectors and descriptors are obtained using the integral and convolutional images. In particular, the Hassian-based matrix is introduced for the detector and a distribution-based method (to achieve resistance and speed) is introduced for the descriptor [23].

Figure 4 show the comparison of precision-recalling, results and repeatability factors among the SURF and SIFT algorithms. The best performance is achieved by SURF. The comparative values of repeatability for SURF and BRISK are shown in Figure 5, in which SURF has shown the best performance in most According to the reference charts, it is expected that the use of SURF-based feature points would have better resistance to attacks.

$img0$
Fig. 4. Precision-recalling of SURF, SIFT, and BRSIK [24]

Fig.5.SURF and BRISK repeatability diagrams [24]

4. knapsack problem

Based on documents in reference [30], one of the most common types of knapsack problem is Binary Knapscak, which seems more suitable than the other types of knapsack algorithms on the basis of the number of problem variables in our proposed design. To find the best optimal solution based on the knapsack problem, we do as follows:

1. Population initialization: The initial population is randomly plotted to maintain the diversity of chromosomes. Every person in the population should represent a practical solution without violations.

2. Fitness assessment: fitness is used to assess the probability of being the best person to be.

3. Selection of Parents: this stage is the selection of people from the population to mate in order to produce new children.

4. Crossover and mutation: Generations are obtained after the selection of the parents of individuals through two crossover and mutation operators. Initially, a uniform crossover is applied to each parent in order to produce a child from the individual chromosome, which is determined by copying the corresponding bits in the parent two chromosomes. Each copied bit is selected with an equal probability from two-parent using a binary random number generator. If the random number is 1, then the bit is the first parent and otherwise the second parent is copied. Then the mutation operator is used for a short jump in the child's chromosome bits that changes them from 0 to 1 or vice versa. It should be noted that the generated child by crossover operators and mutation might not be feasible due to MDKP constraints. Here a modifier is used to overcome this problem.

5. End: A duplicate process from step 2 to this step is performed to find the best solution [31].

4.1. crossover function

1-In the crossover function, the two parent members are randomly selected from the population.

2-The crossover population is generated using initial population members and the crossover function.

3-The first child takes the first part from the first parent and the second part from the second parent. 4-The second child

takes the first part from the second parent and the second part from the first parent.

5-The crossover members of the children and their cost function consist the crossover population.

4.2 mutation function

1-The mutation population is generated using the initial population members and mutation function.

2-A member of the initial population is randomly selected. Then it changes from 0 to 1 or from 1 to 0.

3-The new population is formed by combining initial populations, crossovers, and mutations.

4-The mutant member and the value of its cost function are put in the mutation population.

5 The proposed algorithm

The purpose of this paper is to obtain non-overlapping circular Regions suitable for watermarking. The selected circular Regions should have the largest distribution of coverage on the image, so that the watermark on the image is robust against the cropping attack. We turn the issue of selecting the appropriate circle Regions into an optimization problem that has the following conditions:

1. The selected circular region should have the largest distribution of coverage on the image.

2. The selected circular region should not overlap.

The goal is to maximize the following:

(14)

In which, Nr is the total extracted circular Regions. is equal to 1 [26].

Sj= (15)

If the jth circular Region is selected, it is equal to 1, otherwise, it is 0. Rj is the radius of the circle j. ri is the weight vector of the Knapsack problem.

Maximizing the above statement should be done with the following: This relation states that the two Regions i and j (i ≠ j) should not overlap:

i=1,2,…,Nr (16)

If the ith and jth circular Regions were overlapped and i ≠ j, pij is equal to 1, otherwise, it is 0.

In the proposed genetic algorithm, this problem is of a discrete value type and the chromosome type is binary. In addition, the vector of chromosomes and the cost function value were real values. The tournament method was used to select the parent members in the crossover operation, and the random operation was used in the mutation operation.

5.1 Feature region selection

As stated, in addition to removing some overlapping Regions, the selected Feature points should have the maximum distribution across the image so that they can resist the cutting attacks and use randomization for greater security. Therefore, the proposed method is formulated as an optimally restricted problem through qualitative and overlapping conditions as follows:

maximize (17)

Subject to≤ (18)

And

≤ (19)

In which, NR is the extracted Feature points, rj is the radius of the Region j, {βj} is the key-dependent pseudo-numeric numbers with mean μ and the variance σ2, and sj is defined as:

Sj= (20)

The qj variable shows the distribution of the j watermarked region in comparison to the main Region and Tq refers to the limitation of image quality after watermarking. Equation (19) means that only one region can be overlapped in each case. The pij value depends on the overlapping state of the two region i and j.

In order to solve this compound optimization problem, we transform it into the multidimensional Knapsack (MDKP) problem by expressing its constraints as follows:

(21)

(21

(22)

)

(22)

In equation (22), the variables

and ωkt are respectively the combined weights and the constraints of the distribution of quality and the overlapping state indicated in equations (18) and (19). When k = 1, then ω1t = qt, and which is equivalent to the formulated limitation by Equation (18). Each k greater than 1 corresponds to a pair of definite indexes(i,j) and i≠j in equation (19). Thus, the constraints specified in equation (18) can be formulated again in equation (22) as follows.

By referring to Equation (19), it is obvious that

(23)

Since, si, sj, and placed in Equation (23), Equation (24) as follows:

pijsi + pijsj ≥1 (24)

Which means that

(25)

In contrast, if we have, t≠i or j ، and ωkt = 0.

Otherwise, ωkt = pij and we will have:

(26)

Equation (25) ,m = ( -NR)/2+1 is concluded by adding Equation (21) for various values.

[21] proves that the MDKP solution identified by GA is the best approximation for optimal globalization among different optimization methods. Initially, a string of binary sequences with constant order and length representing a candidate region set , in which 1 in the jth bit indicates that j Region has been selected that is a chromosome of one person in a population for the GA operator. The length S depends on the number of extracted Feature points. The GA-based search process for finding an optimal-close solution involves the following steps:

Suitability assessment: Suitability is used to evaluate the likelihood of the best possible solution for a person. Each person in the current population has his\her own personal fitness to show the degree of success as shown below:

(27)

In which, S[j] represents the jth bit in the chromosome of an individual. The fitness is in accordance with the objective

function in Eq. (20), and the maximization of this fitness leads to the best solution to the selection of the feature region.

The best member is obtained based on the maximum values of the fitness function of the primary population members.

A chromosome and a fitness value are defined for member of the genetic algorithm population.If the circle was

overlapped with the center (xc1, yc1) and radius r1 and the circle with center (xc2, yc2) and radius r2, the following

condition is hold:

(28)

Moreover, if two circle areas of i and j were selected and two circular areas were not the same, then there is an overlap.

The problem crossover is reduced by a finite amount of the maximization function.

5.2 Inserting the Watermark Bits in the LCR Circular Histogram Chart

According to the proposed algorithm, Region normalizing is done in each selected circular feature Region before placing the watermark bits to maintain the invariance of rotation and the degree of watermarking with a fixed length. Using this normalization, circular graded Regions are rotated with a user-defined radius in a uniform direction based on the histogram gradient within the region [33]. Before watermarking inside any normalized Region, the cognitive weighing process is performed to evaluate the ability to insert watermarking to avoid the high image destruction according to the noise observation function (NVF) [33]:

(29)

In which, Var (x) shows the local variance in a window to the center of the pixel in the x coordinates; the varmax is the maximum local variance in the normalized region, and z is the experimentally selected experiment to cover different images in the range of 50 to 100.

Then, the watermarking bits must be embedded in the histogram of each local region LCR.

5.3 The method of inserting the string of watermarking bits in the LCR histogram diagram

Assume BIN1 and BIN2 are two consecutive stems in the LCR histogram and the number of pixelin the BIN1 stem is equal to a and in BIN2 stem is equal to b. The law of inserting watermarking bits is as follows.

)30)

(30)

In the above equation, T is a threshold value to control the number of pixels to be corrected. T is directly related to the imprinting of the image watermarking. According to the first equation, if the watermarking bit is w(i)=1 and no operation is performed (in other words, the relation exists and does not need to change), but if w (i) = 1 and , we transfer the number of I1 = (Tb-a) / (1 + T) pixels from the BIN2 stem to the BIN1 stem to establish the relation.According to the second equation, if the watermarking bit was w(i)=0 and no operation is performed, but if w(i)=0 and , we transfer the number of I0=(Ta-b)/(1+T) from the BIN1 stem to the BIN2 stem to establish the relation .Assume BIN1 and BIN2 are two consecutive stems in the LCR histogram and the number of pixels in the BIN1 stem is equal to a and in BIN2 stem is equal to b. The law of inserting watermarking bits is as follows.

(31)

In the above equation, T is a threshold value to control the number of pixels to be corrected. T is directly related to the imprinting of the image watermarking. According to the first equation, if the watermarking bit is w(i)=1 and no operation is performed (in other words, the relation exists and does not need to change), but if w (i) = 1 and , we transfer the number of I1 = (Tb-a) / (1 + T) pixels from the BIN2 stem to the BIN1 stem to establish the relation . According to the second equation, if the watermarking bit was w(i)=0 and no operation is performed, but if w(i)=0 and , we transfer the number of I0=(Ta-b)/(1+T) from the BIN1 stem to the BIN2 stem to establish the relation . Figure 6 displays the feature points extracted by the proposed scheme and Figure 7 shows applying the proposed algorithm to the Lena’s image.

Fig.6. All feature points and extracted circular Regions by MATLAB software in the proposed scheme (right) are the optimal and non-overlapping circle Regions, which are selected using the genetic algorithm and the Knapsack problem (left).

Untitled-70 Untitled-71 Untitled-72

A B C

Fig.7. Applying the proposed algorithm to the Lena’s image.(A)Lena's image before putting the watermark(B) Lena's image after putting the watermark (C) Difference between the watermarked image and the original image.

5.4 Watermark detection

Similarly, when placing watermark bits, Feature points are detected through the feature detector used in the watermark insertion process. Each circular feature Region is normalized by normalizing the Region in a normal way. Since the watermarking included in the spatial domain can be considered as noise, the Weiner filter [33] is used blindly to extract the watermarking sequence from the normalized Region. The Veiner filter is considered as a noise cancellation operation to estimate the watermark of the target image. It is commonly used in the watermark detection and is considered as an effective strategy for marking-based features [33]. We initially extract hidden information from the normalized Region and obtain the image feature point. For each feature point (x, y) we extract a local LCR region from the image. The center of the circle of point (x, y) and radius of the circle is obtained from the relation r = α.σn. In this respect, σn is the scale of the feature and α is a positive integer. Using the genetic algorithm and the Knapsack problem, from among these circular regions, we must select a certain number of regions so that the circular regions do not overlap and also have the maximum possible radius values.

We extract the watermarking bits from each of the LCR circular Regions. If the extracted watermarking bits were equal to at least one circular Region of the LCR with the same basic bitmaps or the same Wbits, the watermarking operation is performed correctly. Otherwise, if the watermark bits extracted from any of the LCR Regions are not equal to the original watermark bits, we conclude that the image has not been watermarked.

5.5 The method of extracting watermarks from histograms

We divide the histogram into groups of two neighboring stems. Assuming that BIN1 and BIN2 are two consecutive stems in the histogram, a number of stem pins of BIN1 and b is the number of pins of the BIN2 stem.

Using the following equation, you can extract the watermark bits. By repeating this relationship for all successive neighboring stems on the histogram, we can get all of the watermark bits:

(32)

[23]

Thus, if , then the value of the watermark bit is 1 and otherwise, if, the bit value of the watermark is 0.

6. Results of examinations and review of results

The present experimental research is a GA-based search with coding in Matlab, which is tested on a personal computer with an Intel Core i3 1.90 GHz processor and the runtime used to search for an optimal solution-close to about 1.45 minutes for all trial images in all experiments.

Experiments are performed on four well-known images of 512 × 512 from Lena, Baboon, and Pepper, these images are converted to gray-level images for testing. Figure 10 shows these images.


C	B	A

Fig. 8. Host images. (A) Baboon (B) Pepper (C) Lena


B		A

Fig.9. Watermarking images . (A) 128 × 128 (B) 64×64

The examined cover images for watermarking are two types of binary image and bit string. The watermarking images are used with 128×128, 64×64, and 16-bit bit string. The applied watermarking images are shown in Figure 9 And host images in Figure 8.

The feature Region selection process will affect the watermark strength. To review and evaluate the effectiveness of the proposed selection process, we initially assessed the proportion of replication capability between selected Feature points in the overall image and attacked version for the tested images. In this assessment, we conducted attacks according to most of the StirMark criteria.

The applied attacks to the tested images were as follows:

1. Print-Scan attack

2. Cropping attack that involves centralized cropping, ROI (Region of Interest )[24]

3. cropping, and random cropping attack

It should be noted that for a print-scan attack, images were printed with the Canon i-SENSYS LBP3010B printer and a resolution of 300 dpi. The printed images were scanned by the scanner Hp Scanjet G2710 and then cropped and changed to their original size using the Adobe Photo Shop software.

Focused cropping attack crops the area around the image and eliminates undesirable ROI cropping attacks. The random cropping attack saves a random-sized Region in the target image and eliminates the remainder of that image.

In Tables 10 and 11, which are shown on page 12, a comparison is made between the PSNR values for the images tested by the proposed algorithm. The

Surf algorithm for each of the three tested images shows better results in our design.

Table10

Peak of signal to noise rate (PSNR) between the cover image and the watermarked image with Feature Point Harris algorithm

PSNR	Image name
43.21 db	Lena
41.19 db	Baboon
43.33 db	Pepper
43 db	Airplane

Table11

Peak of signal to noise rate (PSNR) between the cover image and the watermarked image with Feature Point Surf algorithm

PSNR	Image name
50.89 db	Lena
47.56 db	Baboon
49.21 db	Pepper
51 db	Airplane

In Table 13 and Table 14, the BER value and the repeatability percentage are for the test images, and the results are reported as average for each attack.From the results of the test cases in the above tables, it can be deduced that the proposed algorithm obtains relatively better results using Harris feature points. Therefore, the regions selected by this algorithm are more stable and more durable, and can withstand most of these attacks. Table 12 shows The number of extracted feature points by the Harris algorithm in the Lena’s image. Figure 10 shows Brisk algoritm in Proposed metod. and Figures 11 and 12 shows Harris and SURF algoritms in Proposed metod.

Table 13 The Repeatability Ratio of Selected Region and the Results of watermarking detection Against Geometric Attacks and Quasi Noise Signal Processing by the proposed scheme with the Feature Points Harris algorithm.
BE R	Percentage of repeatability	Attack
0/20	0/45	crop10
0/19	0/30	crop25
0/21	0/9	crop50
0/21	0/46	GaussianFilter
0/25	0/40	Median3x3
0/26	0/13	Median5x5
0/24	0/50	Print-Scan
0/21	0/15	ROIcropping
0/17	0/40	Rotation5
0/16	0/28	Rotation15
0/19	0/20	Rotation30
0/19	0/16	Rotation45
0/20	0/15	Scaling_.75
0/21	0/55	Scaling_0.9
0/19	0/70	Scaling_1.1
0/19	0/25	Scaling_1.5
0/23	0/54	SharpeningFilter
0/28	0/65	JPEG 30
0/26	0/70	JPEG50

Table 12.The number of extracted feature points by the Harris algorithm in the Lena’s image.

Image

SURF

Harris

Fast

BRISK

Lena

Baboon

pepers

HARRIS

Fig. 10. Brisk algoritm in Proposed metod.

SURF

Fig. 11. Harris algoritm in Proposed metod.

BRISK

Fig. 12. SURF algoritm in Proposed metod.

Table 14 The Repeatability Ratio of Selected Region and the Results of watermarking detection Against Geometric Attacks and Quasi Noise Signal Processing by the proposed scheme with the Feature Points SURF Algorithm
BE R	Percentage of repeatability	Attack
0/28	0/40	crop10
0/29	0/23	crop25
0/30	0/6	crop50
0/29	0/40	GaussianFilter
0/33	0/38	Median3x3
0/35	0/9	Median5x5
0/28	0/42	Print-Scan
0/25	0/11	ROIcropping
0/26	0/31	Rotation5
0/22	0/24	Rotation15
0/24	0/14	Rotation30
0/25	0/10	Rotation45
0/23	0/10	Scaling_.75
0/25	0/50	Scaling_0.9
0/22	0/61	Scaling_1.1
0/22	0/20	Scaling_1.5
0/27	0/56	SharpeningFilter
0/35	0/55	JPEG 30
0/30	0/50	JPEG50

Table.15

Results of various attacks on the proposed algorithm and evaluation by the Lena’s image and comparing it with the results of another three reference.

Image Lena

Ref. [37]

Ref [36]

Ref. [34]

Ours Metod with SURF

Ours Metod with Harris

Ours Metod with BIRISK

Attacks

8/9

7/9

18.8

6.3

7/13

5/13

7/13

8/13

5/13

7/13

10/13

11/13

17/36

18/36

15/36

17/36

11/36

10/36

8/36

9/36

11/36

10/36

11/36

7/36

5/36

3/36

6/36

8/36

10/36

7/36

12/36

17/36

13/28

11/28

8/28

12/28

7/28

5/28

3/28

1/28

6/28

28/2

28/4

3/28

1/28

28/1

1/28

2/28

1/28

6/28

10/28

12/28

7/9

5/9

8/9

4/9

6/9

8/9

12/9

2/9

16/9

15/19

15/9

14/9

12/9

11/9

9/9

19/9

18/9

15/9

16/9

crop10

crop25

crop50

GaussianFilter

Median3x3

Median5x5

Print-Scan

ROIcropping

RandomBending

RandomCropping

Rotation5

Rotation15

Rotation30

Rotation45

Scaling_.7

Scaling_0.9

Scaling_1.1

Scaling_1.5

SharpeningFilter

JPEG 30

JPEG 50

Determining COVID-19 Tweet Check-Worthiness: Based On Deep Learning Approach
Print Date : 2023-01-01
IMPTCHA: A Creative Image CAPTCHA
Print Date : 2020-12-01
A New Approach to Improve Tracking Performance of Moving Objects with Partial Occlusion.
Print Date : 2019-06-01
Application of Numerical Iterative Methods for Solving Benjamin-Bona-Mahony Equation
Print Date : 2019-12-01
Copy-Move Forgery Detection by an Optimal Keypoint on SIFT (OKSIFT) Method.
Print Date : 2021-07-01
Reliability Measurement’s in Depression Detection Using a Data Mining Approach Based on Fuzzy-Genetics
Print Date : 2020-12-01

Share To

Article Url

Evaluating the Harris ,BRISK and SURF Feature Points in Watermarking Based on Histogram and Knapsack Problem