Technical Paper Title: Secure Authentication Watermarking for Binary Images using Pattern Matching
Authors: D.Geetha prasanna & P.Jyothi, 3rd BTech, CSE
College: Prakasam Engineering College, Kandukur
Abstract:
In image authentication watermarking, hidden data is inserted into an image to detect any accidental or malicious image alteration. In the literature, quite a small number of cryptography based secure authentication methods are available for binary images. In a cryptography based authentication watermarking, a message authentication code (or digital signature) of the whole image is computed and the resulting code is inserted into the image itself. This paper proposes a new authentication watermarking method for binary images. The main idea is to use the prioritized sub-blocks by pattern matching scheme to embed the code. Shuffling is applied before embedding to equalize the un even embedding capacity. It detects any alteration while maintaining good visual quality for all types of binary images. The security of the algorithm lies only on the secrecy of a secret or private keys used.
Key Words:
Authentication Watermarking – Binary Images – Pattern Matching – Shuffling.
1. Introduction
Data hiding represents a class of processes used to embed data, such as copyright information into various forms of media such as image, audio, or text with a minimum amount of perceivable degradation to the “host” signal; its goal is not to restrict or regulate access to the host signal, but rather to ensure that embedded data remains inviolate and recoverable.
A watermarking technique makes use of a data hiding scheme to insert some information in the host image, in order to make an assertion about the image later. In this paper, data hiding scheme simply means the technique to embed a sequence of bits in a still image and to extract it after wards.
Water marking techniques can be classified as either “robust” or “fragile.” Robust water marks are useful for copyright and ownership assertion purposes. They cannot be easily removed and should resist common image manipulation procedures. On the other hand, fragile watermarks (or authentication watermarks) are easily corrupted by any image processing procedure. However, watermarks for checking the image integrity and authenticity can be fragile because if the watermark is removed, the watermark detection algorithm will correctly report the corruption of the image .
In a cryptography based authentication water marking, an authentication signature (AS) is computed from the whole image and inserted into the image itself. In cryptography, an AS is called message authentication code (MAC) using a secret-key cipher or digital signature(DS) using a public/private-key cipher. An AS contains information about the host image content that may be checked to verify its integrity. However, inserting the MAC/DS alters the image and consequently alters its MAC/DS, invalidating the watermarking. To avoid this problem, for continuous-tone images, many authentication techniques compute the AS from the image clearing the least significant bits (LSB s) and insert the AS in LSB s. In other words, those bits where the watermark is to be inserted are not taken into account when computing MAC/DS. The same idea can be applied to binary images for computing MAC/DS.
A possible use of this technique is to send authenticated faxes and documents over networks and the Internet. In this case, the receiver of a document can verify its integrity for a given originator.
2. Data Hiding and Authentication Watermarking
In the literature, there are many authentication watermarking techniques for continuous-tone images .Also, there are many techniques for data hiding in binary and halftone images. There are many papers on data hiding in binary images but there is no authentication water marking.
How ever, quite a small number of secure authentication watermarking techniques are available for binary and halftone images. Only some techniques used the cryptography-based secure authentication water marking. It was given for dispersed-dot halftone images but the visual quality for a binary image is poor. The ratio of black versus white pixels is used. Although the algorithm aims at robustly hiding information in binary image, it is not secure enough to be directly applied for authentication or other fragile use.
Some times PWLC does not correctly extract the hidden data, and fails to recover perfectly the original cover image. In summary, these previously proposed approaches either cannot be easily extended to other binary images, or can only embed a small amount of data.
In secure authentication watermarking using some data hiding technique for binary image, one must compute a hashing function of the binary image F, obtaining the hash value H = H(F). After encryption, it becomes MAC /DS. This MAC/DS must be inserted into F itself, obtaining the marked image F′.
In this paper, a Secure Authentication Water marking Technique for binary images using Pattern Matching scheme is proposed (SAWT-PM). The hidden data can be extracted without using the original unmarked image. The approach can be used to verify whether a binary document has been tampered with or not and also authenticates the originator.
The original image is represented as F. It is partitioned into m × n sub blocks (say 3 × 3). In each sub block only the middle pixel is used to hide the information. Each 3 ×3 sub-block is checked against predefined patterns. If a Sub-block matches with any of the valid patterns, it is ready to hide the information. It is referred as Ready Block, and the middle pixel of it can be used to hide the information.
But, the idea of computing an AS of the whole binary image and inserting it into the same image fails. Since the insertion will modify the image fingerprint, it can not be verified at the receiver side. A modified idea to insert the AS without modifying the image fingerprint is to divide the image into two regions: The first region is small in size, called AS Region (ASR) where AS will be inserted and the second region is the original image excluding ASR, called Non-AS Region (NASR) from where AS will be computed. Using this technique, the image authenticity can be verified at the receiver side.
3. The SAWT-PM
In SAWT-PM, only a few pixels are modified and the positions of sub-blocks containing those pixels are known both in the insertion and extraction phases. SAWT-PM flips only low-visibility pixels to hide the information and consequently the watermarked image has excellent visual quality and do not have salt-and-pepper noise.
3.1 Finding Ready Blocks
The original image is represented as F. It is partitioned into m × n sub-blocks Fi. In each sub-block only the Middle pixel is used to hide the information. But, not all the sub-blocks are used for hiding the information. Among the 512, 3 × 3 sub-blocks several blocks were rejected due to various reasons like, high visibility, Non reversible at receiver side etc. Only 120 patterns are considered to be valid for data hiding.
The Figure 1 depicts the valid patterns. The hatched middle pixel may either be black or white. The change of middle pixel is less noticeable. Mirrors, transposes and reverses of the patterns are also used for hiding the information.
Each 3 × 3 sub-block is checked against various constraints to identify that whether it matches with any of the valid 120 patterns or not. If a sub-block matches with any of the valid patterns, it is a Ready Block.
The patterns are selected based on the following constraints:
Fig 1: The 3 × 3 patterns used for hiding the information. The hatched middle pixel may either be black or white. The change of middle pixel is less noticeable. Mirrors, transposes and reverses of the above patterns are also used for hiding the information. The remaining patterns are not used.
(a) The number of white pixels in a sub-block should be greater than 2 and less than 6 excluding the
middle pixel. That is, 3, 4, 5 or 6 white pixels and6, 5, 4 or 3 black pixels respectively.
I1: X1 < SUM (Fi) < X2, i =1 to n; X1=2;X2=6
Where ,
Fi – a sub-block,
n – total number of sub-blocks
SUM – a function that counts the number of ones (white pixels) in the sub- block.
X1 and X2 – minimum and maximum number of ones in the sub-block respectively.
(b) If there are only 3 white/black pixels, they should not be in same row/column.
If a sub-block satisfies the above constraints, it will become Ready Block, and ready to hide the information.
Authentication Signature
Let k be the length of the adopted AS. To insert k bits of AS, it needs k, m × n Ready Blocks in the image. The image is divided into two regions: The first region is small in size, called AS Region (ASR) where AS will be inserted and the second region is the original image excluding ASR, called Non-AS Region (NASR) from where AS will be computed. Using this technique, the image authenticity can be verified at the receiver side.
Once the Ready Blocks are found, it is clearly understood that the middle pixels of all the Ready Blocks forms the ASR. So, before calculating the hash value of the image, the ASR is made to be darkened. The new Image is referred as (ZASR –Zeros inserted at AS Region).The ZASR is actually the whole image with zeros in ASR. Now, the hash value is calculated for ZASR, encrypted using the secret- or public key ks, obtaining the MAC/DS and is inserted in ASR .
At the receiving side, the receiver uses the same technique to identify the Ready Blocks. ASR is separated, encrypted AS inserted in that are retrieved and decrypted using the secret- or public key ks, obtaining the AS. Then in the received original image, middle pixels of ASR are made to be darkened. It is referred as ZASR*. Compute H(ZASR*) and if H (ZASR*) =AS, then image integrity is verified. Otherwise, image has been modified or a wrong key was used.
3.3 Data Hiding Scheme
This technique ensures that for any pixel that is modified in the host image, its visibility is very less. Thus, the existence of secret information in the host image is difficult to detect.
The data hiding scheme is very simple. In each block, the position of the pixel to be used for hiding the information is fixed, that is, the middle pixel. Hence the complexity is not in identifying the position, but in identifying the sub-blocks that are ready to hide the information (Ready Blocks).
Since the middle pixel is used to hide the information always, another level of security is introduced by shuffling of the Ready Blocks. This provides another advantage also. It distributes the hidden information in all parts of the image. It is an efficient and effective tool to equalize uneven embedding capacity.
The Ready Blocks are shuffled and permuted order is generated randomly. A secret key, called Shuffling Key shared by the sender and the receiver, is used as the seed for pseudo random number generator.
Let the original image F is partitioned into m × n sub blocks Fi.
Step 1: If Fi is completely black or blank, simply keep Fi intact (not hidden with any information) and skip the following steps. Otherwise, perform the following:
Step 2: Identify the Ready Blocks by comparing each sub block Fi with the predefined patterns specified in Section 3.1.
Step 3: Use the secret key to generate the permuted order of Read y Blocks.
Step 4: If the middle bit of the Ready Block and the bit to be hidden are same, then no change is made to the sub-block Fi; otherwise, the middle bit is flipped to store the information.
3.4 Authentication Watermarking
The Figure 2 and Figure 3 depict the block diagram of embedding and extraction process in binary image Authentication .
SAWT-PM insertion algorithm is:
1. Let F be a binary image to be watermarked and k be the length of AS.
2. Partition the image F into m × n size sub- blocks Fi. To insert k bits of AS, it needs k, m ×n blocks in the image.
3. Find the Ready Blocks by comparing each sub block Fi with the predefined patterns specified.
4. The middle pixels of Ready Blocks forms AS Region. Clear ASR, obtaining ZASR.
5. Compute the hash vale H=H (ZASR).
6. Encrypt H using the secret- or public key ks, obtaining the digital signature S (MAC/DS).
7. Use the secret key to generate the permuted order of Ready Blocks.
8. Insert S into ASR.
The SAWT-PM extraction algorithm is :
1. Let F* be the watermarked image received.
2. Partition the image F into m × n size sub- blocks.
3. Find the Ready Blocks by comparing each sub block Fi with the predefined patterns specified.
4. The middle pixels of Ready Blocks forms AS Region. Clear ASR, obtaining ZASR*.
5. Compute the hash vale H*=H(ZASR*).
6. Use the secret key to generate the permuted order of Ready Blocks.
7. Extract the watermark from the Ready Blocks of F* and decrypt the result using the secret- or public key ks, obtaining the digital signature S*
8. If S* and H* are equal the watermark is verified. Otherwise, the marked image F* has been
modified.
4. Experimental Results and Distortion Measure
In this section, experimental results are illustrated to demonstrate the validity of SAWT-PM data hiding scheme. Various binary images and document images, such as Mickey Mouse, English text are taken as the sample images in the experiment. The experimental results reveal that the SAWT-PM data hiding scheme exhibits very good performance.
4.1 Experimental results
Experimental results of some samples are given in Appendix – A. It shows the original image, watermarked image and modified pixels in the watermarked image of various samples taken. By observing the watermarked image, it is clear that the visual quality generated by CAPM data hiding scheme is very good.
4.2 Distortion Measure
Two of the metrics used to compare the watermarked image and the original image are the Mean Square Error (MSE) and the Peak Signal to Noise Ratio (PSNR). The MSE is the cumulative squared error between the compressed and the original image, whereas PSNR is a measure of the peak error. It uses a standard mathematical Model to measure an objective difference between two images. The mathematical formulae for the two are,
Where I(x, y) is the original host image and I'(x, y) is the watermarked image and M,N are the dimensions of the images. A lower value for MSE means lesser error, and as seen from the inverse relation between the MSE and PSNR, this translates to a high value of PSNR. Logically, a higher value of PSNR is good because it means that the ratio of Signal to Noise is higher. Here, the ‘signal’ is the original image, and the ‘noise’ is the modified pixels in water marked image. So, if a data embedding scheme having a lower MSE (and a high PSNR), it is recognized as a better one. The PSNR and MSE obtained for the various categories of sample images are tabulated in Table 1. It reveals that water marked images of good visual quality are obtained in the SAWT-PM data hiding scheme.
5. Conclusion:
This paper has proposed secure authentication water marking for binary images using pattern matching (SAWT-PM). Shuffling is applied before embedding to equalize the uneven embedding capacity. The good performance is shown by experimental results. The proposed technique is suitable to watermark most binary images with good visual quality without causing a noticeable loss of quality. The applicable images include line-drawing images, cartoon images, maps etc. It can also be applied to provide basic proof of copyrights ownership and to electronically sign binary documents.