Image analysis – Applications
Reexamination Certificate
1998-09-23
2001-07-24
Boudreau, Leo (Department: 2621)
Image analysis
Applications
C382S244000, C380S268000, C713S186000
Reexamination Certificate
active
06266429
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates generally to the field of signal encryption and more specifically, to a method for identifying whether digital images, transmitted with a loss, have been unaltered and have been sent from a specific source. This is accomplished through the creation of a specialized fingerprint and “signature”.
Methods exist for encrypting digital signals to prevent tampering such as disclosed in U.S. Pat. No. 5,499,294, keep a malicious adversary from altering the signal. A fingerprint or “hash” is taken of the digital image. Hashing algorithms (i.e. one-way functions) are well known and easy to calculate but very difficult to mathematically invert. The fingerprint is typically encrypted with an encryption key to prove or authenticate the creator of the signature. The encryption itself is a standard public/private key cryptology with the source station utilizing a private key. The resulting signature can be decrypted by a receiving station with the source's public key.
The hash-key combination along with the original image, is then sent to the receiving station which uses the public key of the presumed transmitter in decrypting the encrypted hash. The receiving station performs the same hash algorithm on the received image and compares it to the decrypted hash. If these two hashes are identical, there has been no noise in the transmission and the image has not been modified (tampered) by a third party. If the image was modified or the wrong public key is used, the two hashes will not be identical.
The same technique would generally not work in a transmission where information is lost. Generally, a digitized version of a received image includes lost bits or noise which corrupt the received digitized image. Consequently, it is difficult to confirm whether a received image has been tampered with based upon a comparison of the received fingerprint of the source image to a digitized fingerprint generated based on the received digitized image.
Another attempt to solve the problem in a JPEG transmission is described in “A Robust Image Authentication Algorithm Distinguishing JPEG Compression from Malicious Manipulations” by Ching-Yun Lin and Shih-Fu Chang, published in ISLT/SPIE Symposium on Electronic Imaging: Science and Technology, Jan 1998, San Jose, Calif. pages 77-80. Their method is to compare the same block in subsequent frames of a JPEG compressed transmission. This comparison is performed to ensure the range of difference in value between these two blocks remains the same ever after compression and decompression is performed. A signature is created by comparing the difference between two blocks and a threshold. A binary “0” or “1” is entered into the signature depending on whether the difference is above or below that threshold. This signature is sent along with the transmitted image and the method continues as discussed above.
The Lin/Chang method is deficient in that it relies on the inherent structure of JPEG compression and would not work with other transmissions (including lossy transmissions) which do not follow the JPEG format. Further, The Lin/Chang method allows the possibility of tampering. Since the signature is completely based upon a comparison of consecutive frames with a threshold, a malicious adversary could create a completely different data stream and send it to the receiver as long as the differences between consecutive frames is approximately (within the range of the chosen threshold) the same.
Still another technique known in the art is watermarking. A set of bits (a mark) is added to a transmitted image. This mark should be complete enough so that it can be detected by a receiver but should not alter the nature of image. The technique is often used in copyright situations where piracy is a concern. A defendant who alleges he did not copy the image will then be forced to explain why the watermark is still within the image. Watermarking is an efficient way of proving origination. However, it does not indicate when tampering has occurred.
Therefore, it is desirable to provide an improved method for confirming whether a received image has been altered. The method should include a fingerprint which is simple to compute from the image but difficult to create an image that has a given fingerprint. The fingerprint method also should have the characteristic that it would be difficult to generate two images that have the same fingerprint. The fingerprint method should be operable when losses are experienced through transmission of the digitized signal.
OBJECTS AND SUMMARY OF THE INVENTION
One aspect of the invention is a method for confirming the integrity of a transmitted image including the steps of dividing the image into a first plurality of cells having a first sequence, generating a random seed and generating a first plurality of pseudo random numbers based upon said random seed. The method further includes the steps of creating the image into a second plurality of cells based upon the first plurality of pseudo random numbers and the first plurality of cells and generating a second plurality of pseudo random numbers, the second plurality of pseudo random numbers forming a second sequence. The method also includes the steps of comparing cells corresponding to the first sequence with cells corresponding to the second sequence, in forming a first fingerprint, and transmitting the fingerprint, the image, and the random seed to a receiver. The method still further includes the steps of producing a second fingerprint, by the receiver, using the image and the random seed that was received, and comparing the first and second fingerprints.
This method makes it difficult for a third party to manipulate an image without changing the fingerprint of that image. The fingerprint itself is easy to create if one knows the seed. But, this seed will be unknown by a third party. Even though the image will be sent with losses, the fingerprint will not change and so it still can be used to monitor the integrity of the image.
Another aspect of the present invention is a method for creating a fingerprint of an image including the steps of dividing the image into a first plurality of cells having a first sequence, generating a random seed, generating a first plurality of pseudo random numbers based upon the random seed, and dividing the image into a second plurality of cells based upon the first plurality of pseudo random numbers and the first plurality of cells. The method also includes the steps of generating a second plurality of pseudo random numbers, the second plurality of pseudo random numbers forming a second sequence, and comparing cells corresponding to the first sequence with cells corresponding to the second sequence, in forming the fingerprint. This fingerprint has the same benefits as the fingerprint state above.
In yet another aspect of the invention a computer readable storage medium includes a fingerprint representing an image, the medium has a series of representations, each representation resulting from a comparison between a threshold and a difference between a first number and a second number. The first number corresponds to a value of a first cell of a first plurality of cells of the image. The second number corresponds to a value of a second cell of a second plurality of cells of the image. The first plurality of cells is formed by dividing the image into a third plurality of cells and manipulating the third plurality of cells based upon a first plurality of pseudo random numbers. The second plurality of cells are equal in number to said first plurality of cells and have a sequence dictated by said second plurality of pseudo random numbers.
In still yet another aspect of the present invention, a computer readable storage medium has encoded data for dividing an image into a first plurality of cells having a first sequence, generating a random seed, and generating a first plurality of pseudo random numbers based upon the random seed. The medium further has data for creating the image into a second plurality of cell
Abdel-Mottaleb Mohamed
Epstein Michael
Lord William P.
Boudreau Leo
Choobin M B
Philips Electronics North America Corporation
LandOfFree
Method for confirming the integrity of an image transmitted... 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 for confirming the integrity of an image transmitted..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for confirming the integrity of an image transmitted... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2542099