Electrical computers and digital processing systems: support – Multiple computer communication using cryptography – Particular communication authentication technique
Reexamination Certificate
1999-01-22
2003-03-11
Barron, Gilberto (Department: 2132)
Electrical computers and digital processing systems: support
Multiple computer communication using cryptography
Particular communication authentication technique
C380S216000, C380S217000
Reexamination Certificate
active
06532541
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to image authentication, and more particularly relates to methods and apparatus for image authentication which distinguish unauthorized content-altering image alterations from content preserving manipulations, such as image compression.
2. Description of Related Art
With the recent growth in accessability of computers and digital cameras, the importance of digital images is constantly increasing. Digital images offer advantages over traditional photographic processes in ease of manipulation, storage and processing. However, the ease in which digital images can be altered significantly reduces the reliability which was once inherent in a photographic image.
To enhance the reliability of digital images, image authentication techniques have been pursued to detect malicious manipulation of an image. Previously, two techniques have been investigated: 1) generating a digital signature of the image at the point of origin, i.e., at the digital camera; and 2) embedding a secret code, or “watermark,” related to the content of the image within the image.
The first method employs an encrypted digital signature which is generated by the image capturing device. Generally, the digital signature is based on a public key encryption method. In this type of method, a private key, known only to the capturing device, is used to encrypt a hashed version of an image to form the “signature” of the image which travels with the image. A public key is used to decrypt the signature. The public key is also used to hash the image and compare the codes of the current image to the original signature. If the codes match, the present image is considered authentic.
In the second method, a checksum value is generated corresponding to the bit values of the pixels forming the image. The checksum value is considered a fragile “watermark” for the image, as any alteration of the image will alter the checksum value and destroy the watermark. To authenticate an image, the current checksum value of the image is compared against the value of the watermark to verify that the values are equal.
Both of the above image authentication methods are limited in that any change in the image will result in a verification failure. However, certain image manipulations do not significantly alter the meaning of the image content and are considered desirable. For example, digital images are generally compressed prior to storage and data transmission in order to optimize the use of computer storage and data transmission resources. However, a very common image compression standard, JPEG (Joint Photographic Experts Group), results in a “lossy” compression of image data which irrevocably alters certain pixels in the image. Because JPEG compression alters the content of the image, the above described authentication methods cannot successfully verify an image after such lossy compression is applied.
FIGS. 1A and 1B
illustrate systems known in the art for performing JPEG compression and decompression of a digital image, respectively. Referring to
FIG. 1A
, the source image
100
, X, is grouped into &rgr; nonoverlapping 8×8 blocks, O FPIXELS i.e., X=∪
p=1
&rgr;
X
p
. Each block is sent sequentially to a Discrete Cosine Transform (DCT) processor
102
to extract DCT coefficients for each block. Instead of representing each block, X
p
, as a 8×8 matrix, each block can be represented as a 64×1 vector following the “zig-zag” order of the original matrix. Therefore, the DCT coefficients F
p
, of the vector, X
p
, can be considered as a linear transformation of X
p
with a 64×64 transformation matrix D, s.t.,
F
p
=DX
p
. (1)
Each of the 64 DCT coefficients is applied to a quantizer
104
where the DCT coefficients are quantized with a 64-element quantization table Q
106
. In JPEG compression, this table is used on all blocks of an image. (For color images, there could be three quantization tables for CrCb domains, respectively.) Quantization is defined as the division of each DCT coefficient by its corresponding quantizer step size, followed by rounding to the nearest integer:
f
~
p
(
v
)
≡
Integer
Round
(
F
p
(
v
)
Q
(
v
)
)
(
2
)
where &ngr;=1 . . . 64. In eq.(2), {tilde over (f)}
p
is the output of the quantizer. For the convenience of later discussion, we can define {tilde over (F)}
p
, a quantized approximation of F
p
, as
{tilde over (F)}
p
(&ngr;)≡
{tilde over (F)}
p
(&ngr;)·
Q
(&ngr;). (3)
After quantization, the inter-block differences of DC coefficients are encoded by an entropy encoder
108
. The AC terms are ordered following the “zig-zag” order. Both DC and AC coefficients are then entropy encoded. The final JPEG file, {tilde over (B)} includes the Huffman table
110
, the quantization table
106
, the encoded data and some other information.
FIG. 1B
illustrate a decoder suitable for decompressing an image subjected to JPEG compression. First, the decoder extracts and reconstructs the Huffman table
110
and quantization table
106
from the compressed image. Then the bitstream is sent to an entropy decoder
112
and a dequantizer
114
to substantially reconstruct the DCT coefficients of the original image. The output of dequantizer, {tilde over (F)}
p
, is the same as that defined above in equation(3). An Inverse DCT (IDCT) processor
116
is then used to convert {tilde over (F)}
p
to the spatial-domain image block {tilde over (X)}
p
.
{tilde over (X)}
p
=D
−1
{tilde over (F)}
p
. (4)
All blocks are then tiled to form a decoded image frame.
Theoretically, the results of the IDCT process will be real numbers. However, the brightness of an image is usually represented by an 8-bit integer from 0 to 255. Therefore, a rounding process which maps those real numbers to integers may be necessary. This process is performed after the IDCT processor
116
by processing block
118
.
In addition to image compression, it is also desirable to allow certain other manipulations to an image while still verifying the remaining content as authentic. In some cases image cropping, image translation, image masking, global intensity alteration etc. may be allowable. However, as with lossy compression, present image authentication techniques cannot verify an image once such allowable image manipulations are performed.
The above-described prior art techniques fail to satisfy the growing need for robust image authentication which can distinguish between allowable image manipulations and malicious, content altering manipulations which are impermissible.
SUMMARY OF THE INVENTION
An object of the present invention is to provide robust image authentication methods and apparatus which distinguish malicious content based attacks of an image from allowable transformations of an image.
A further object of the present invention is to provide an image authenticator which accepts and authenticates images subjected to format transformation, lossless compression as well as acceptable forms of lossy compression.
Another object of the present invention is to provide an image authenticator which accepts and authenticates images subjected to user specified content manipulations, such as cropping, shifting and image intensity adjustment.
Yet another object of the present invention is to provide an image authenticator which accepts and authenticates images subjected to JPEG image compression.
In accordance with a first embodiment of the present invention a system for authentication of a digital image includes a signature generator and an authentication processor. The signature generator includes an image analyzer which receives an original digital image, parses the image into block pair and generates invariant features of the image based on a relationship between corresponding pixels in the block pairs. Preferably, the signature generator also includes an encryption processor for encoding the invariant features generated by th
Chang Shih-Fu
Lin Ching-Yung
Baker & Botts LLP
Barron Gilberto
The Trustees of Columbia University in the City of New York
Zand Kambiz
LandOfFree
Method and apparatus for image authentication does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for image authentication, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for image authentication will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3078406