Image authentication patterning

• US 5,764,770 A
• Filed: 08/04/1997
• Issued: 06/09/1998
• Est. Priority Date: 11/07/1995
• Status: Expired due to Term

• Current Assignee: Trimble Navigation Limited (Trimble Inc.)
• Original Assignee: Trimble Navigation Limited (Trimble Inc.)
• Inventors: Schipper, John F., Pelley, Allan M.
• Primary Examiner(s): CANGIALOSI, SALVATORE A
• Application Number:
  US08/905,842
• Time in Patent Office: 309 Days
• Field of Search: 380/20, 380/21, 380/23-25, 380/54, 382/209
• US Class Current: 713/176
• CPC Class Codes: G01S 19/14 specially adapted for specific applications
• CPC Class Codes: H04N 1/32122 in a separate device, e.g. in a memory or on a display separate from image data
• CPC Class Codes: H04N 1/32144 embedded in the image data, i.e. enclosed or integrated in the image, e.g. watermark, super-imposed logo or stamp
• CPC Class Codes: H04N 1/32208 involving changing the magnitude of selected pixels, e.g. overlay of information or super-imposition H04N1/32219, H04N1/32224 take precedence
• CPC Class Codes: H04N 1/32229 with selective or adaptive application of the additional information, e.g. in selected regions of the image H04N1/32213 takes precedence
• CPC Class Codes: H04N 1/32251 in multilevel data, e.g. greyscale or continuous tone data
• CPC Class Codes: H04N 1/32261 in binary data H04N1/32256 takes precedence
• CPC Class Codes: H04N 2101/00 Still video cameras
• CPC Class Codes: H04N 2201/3215 of a time or duration
• CPC Class Codes: H04N 2201/3225 of data relating to an image, a page or a document
• CPC Class Codes: H04N 2201/3233 of authentication information, e.g. digital signature, watermark
• CPC Class Codes: H04N 2201/3253 Position information, e.g. geographical position at time of capture, GPS data
• CPC Class Codes: H04N 2201/3254 Orientation, e.g. landscape or portrait; Location or order of the image data, e.g. in memory
• CPC Class Codes: H04N 2201/3274 Storage or retrieval of prestored additional information
• CPC Class Codes: H04N 2201/3281 Encryption; Ciphering

Abstract

Apparatus for producing a self-authenticating visual image of a selected view, using a digital image forming means, such as a digital camera, together with a position determining system that provides position information, including location and/or angular orientation and/or time of observation at the time a digital image is formed. The digital image of the selected view is presented as an array of pixels with associated pixel values. The position information is incorporated in the digital image by altering selected pixel bit values for a selected authentication pattern P of pixels in a chosen subset CS of the pixel array; and this selected pattern may be determined using the position information. The position information may be encrypted, using an encryption key based on position information, and may be stored separate from, or as part of, the digital image. The authentication pattern is represented by an authentication key or indicium, a single number or an ordered sequence of numbers, that is transmitted with the modified digital image and incorporated position information. The authentication pattern P is preferably chosen so that any circle or other connected pixel region of diameter at least equal to a selected number D contains at least one pixel from the subset CS. The pixel array may be overlaid by a set of polygons, such as triangles, rectangles, parallelograms or hexagons, with at least one pixel from the subset CS in each polygon.

Claims

1. Apparatus for producing a self-authenticating image, the apparatus comprising:

a digital image camera that forms a digitally expressed image of a selected view as an array of pixel values, with each pixel value corresponding to a pixel in an array of pixels;

position determination means, including a digital computer, for determining position information that includes at least one of the location of the digital camera, the angular orientation of the digital camera and the time at which the digital image camera forms a digitally expressed image; and

digital image storage means for receiving a digital image from the digital image camera, for receiving the position information from the position determination means, for combining the digital image with the position information to form a modified digital image in which each pixel value in a chosen subset CS of the array of pixel values is reformed as a modified array to contain a portion of the position information, for storing this modified array of pixel values, and for providing an authentication key that indicates the chosen subset CS of the array of pixels for which the pixel values have been modified to form the modified digital image.

2. The apparatus of claim 1, further comprising:

authentication means, connected to said digital image storage means, for receiving a putative authentication key and putative position information for a selected digital image, for retrieving from said digital image storage means said position information that was combined with said selected digital image by using said putative authentication key, for comparing the putative position information with said retrieved position information that was combined with said selected digital image, for authenticating said selected digital image if the putative position information substantially agrees with said retrieved position information, and for withholding authentication of said selected digital image if the putative position information does not substantially agree with said retrieved position information.

3. The apparatus of claim 1, further comprising display means, connected to said digital image storage means, for providing information contained in a modified digital image in at least one of electronically perceptible form, visually perceptible form and audibly perceptible form.

4. The apparatus of claim 1, wherein said position determination means comprises:

a Satellite Positioning System ("SATPS") signal antenna that receives SATPS signals transmitted from at least three SATPS signal sources; and

an SATPS signal receiver/processor to receive and process SATPS signals from the SATPS antenna and to determine the location of the SATPS antenna.

5. The apparatus of claim 1, wherein said position determination means comprises:

at least three SATPS signal antennas, arranged non-collinearly to each receive SATPS signals transmitted from at least three SATPS signal sources; and

an SATPS signal receiver/processor to receive and process SATPS signals from the SATPS antennas and to determine the location of each of the SATPS antennas and the angular orientation of a plane containing at least three of the SATPS antennas and of a selected line lying in this plane, where this selected line has a known angular orientation relative to said digital camera.

6. The apparatus of claim 1, wherein said position determination means comprises:

an SATPS signal antenna that receives SATPS signals transmitted from at least three SATPS signal sources;

an SATPS signal receiver/processor to receive and process SATPS signals from the SATPS antenna and to determine the location of the SATPS antenna; and

angular orientation determination means, attached to said digital camera, for determining the angular orientation of said digital camera at least partly independently of the SATPS signals received from the SATPS signal sources.

7. The apparatus of claim 1, wherein said position determination means comprises:

an SATPS signal antenna that receives SATPS signals transmitted from at least three SATPS signal sources; and

an SATPS signal receiver/processor to receive and process SATPS signals from the SATPS antennas and to determine the times of receipt of the SATPS signals at the SATPS antenna.

8. The apparatus of claim 1, wherein:

(1) said pixel values in said array of pixel values are numbered m=1, 2, . . . , N;

(2) said pixel value number m is assigned a unique prime number p(m) in a sequence of distinct prime numbers;

(3) said pixel value number m is assigned a number q(m)=p(m) if said pixel value numbered m belongs to said chosen subset CS of pixel values and is assigned a number q(m)=1 if said pixel value numbered m does not belong to said chosen subset CS of pixel values; and

(4) said key I is defined by ##EQU11##

9. The apparatus of claim 1, wherein:

(1) said pixel bit values in said array of pixel values are numbered m=1, 2, . . . , K·

N, where K is the number of bits used to express a pixel value;

(2) said pixel bit value number m is assigned a unique prime number p(m) in a sequence of distinct prime numbers;

(3) said pixel bit value number n is assigned a number q'"'"'(m)=p(m) if said pixel bit value numbered m belongs to said chosen subset CS of pixel bit values and is assigned a number q(m)=1 if said pixel bit value numbered m does not belong to said chosen subset CS of pixel bit values; and

(4) said key I is defined by ##EQU12##

10. The apparatus of claim 1, wherein:

(1) said pixel values in said array of pixel values are numbered m=1, 2, . . . , N;

(2) said pixel value number m is assigned a number r(m)=1 if said pixel value numbered m belongs to said chosen subset CS of pixel values and is assigned a number r(m)=0 if said pixel value numbered m does not belong to said chosen subset CS of pixel values; and

(3) said key I is defined by ##EQU13## where Z is a selected real number greater than 1.

11. The apparatus of claim 10, wherein said real number Z is selected to be equal to 2.

12. The apparatus of claim 1, wherein:

(1) said pixel bit values in said array of pixel values are numbered m=1, 2, . . . , K·

N, where K is the number of bits used to express a pixel value;

(2) said pixel bit value number n is assigned a number r'"'"'(m)=1 if said pixel bit value numbered m belongs to said chosen subset CS of pixel bit values and is assigned a number r'"'"'(m)=0 if said pixel bit value numbered m does not belong to said chosen subset CS of pixel bit values; and

(3) said key I is defined by ##EQU14## where Z is a selected real number greater than 1.

13. The apparatus of claim 12, wherein said real number Z is selected to be equal to 2.

14. The apparatus of claim 1, wherein said authentication means provides an overlay of polygons p_g, numbered g=1, 2, . . . , G (G≧

2), of substantially identical shape and size that overlays said array of pixel locations, assigns each pixel location in said array of pixel locations to one polygon in the overlay, assigns at least one pixel location in said chosen subset CS to each polygon in the overlay, computes a sub-key (g,I_g) for each polygon p_g that indicates the members of said chosen subset CS that are assigned to the polygon p_g, and determines said authentication key I from the collection of sub-key {(g, I_g)}_g determined for the polygons p_g in the overlay.

15. The apparatus of claim 14, wherein said polygons p_g in said overlay are drawn from a class of polygons consisting of isoceles triangles, equilateral triangles, squares, rectangles, parallelograms, equilateral regular hexagons and non-equilateral regular hexagons.

16. The apparatus of claim 1, wherein said chosen subset CS of said array PA of pixel values is chosen so that, for any pixel in said pixel array PA a circle, centered at this pixel and having a diameter at least equal to a selected threshold number D, contains at least one pixel belonging to said chosen subset CS, where D is at least four times the pixel-to-pixel nearest neighbor distance.

17. The apparatus of claim 1, wherein said chosen subset CS of said array PA of pixel values includes at least one of the following patterns of pixels:

a substantially straight line containing contiguous pixels, a substantially straight line containing non-contiguous pixels, a curved line containing contiguous pixels, and a curved line containing non-contiguous pixels.

18. A method for producing a self-authenticating digital image, the method comprising the steps of:

forming a digitally expressed image of a selected view as an array of pixel values, using a digital camera, with each pixel value corresponding to a pixel in an array of pixels;

determining position information including at least one of the location of the digital camera, the angular orientation of the digital camera and the time at which a digital image was formed;

receiving a digital image from the digital camera;

receiving the position information for the digital image;

combining the digital image with the position information to form a modified digital image in which each pixel value in a chosen subset CS of the array of pixels is reformed as a modified array to contain a portion of the position information, and storing the modified array of pixel values in a digital image storage module; and

providing an authentication key that indicates the chosen subset CS of the modified array of pixels.

19. The method of claim 18, further comprising the steps of:

providing authentication means, connected to said digital image storage module, for receiving a putative authentication key and putative position information for a selected digital image, for retrieving from said digital image storage means said position information that was combined with said selected digital image by using the putative authentication key, for comparing the putative position information with said retrieved position information that was combined with the selected digital image;

authenticating the selected digital image if the putative position information substantially agrees with said retrieved position information; and

withholding authentication of the selected digital image if the putative position information does not substantially agree with said retrieved position information.

20. The apparatus of claim 18, further comprising the step of providing display means, connected to said digital image storage module, for presenting information contained in a modified digital image in at least one of electronically perceptible form, visually perceptible form and audibly perceptible form.

21. The apparatus of claim 18, wherein said step of determining said position information comprises:

providing a Satellite Positioning System ("SATPS") signal antenna that receives SATPS signals transmitted from at least three SATPS signal sources; and

providing an SATPS signal receiver/processor to receive and process SATPS signals from the SATPS antenna and to determine the location of the SATPS antenna.

22. The apparatus of claim 18, wherein said step of determining said position information comprises:

providing at least three SATPS signal antennas, arranged non-collinearly to each receive SATPS signals transmitted from at least three SATPS signal sources; and

providing an SATPS signal receiver/processor to receive and process SATPS signals from the SATPS antennas and to determine the location of each of the SATPS antennas and the angular orientation of a plane containing at least three of the SATPS antennas and of a selected line lying in this plane, where this selected line has a known angular orientation relative to said digital camera.

23. The apparatus of claim 18, wherein said step of determining said position information comprises:

providing an SATPS signal antenna that receives SATPS signals transmitted from at least three SATPS signal sources;

providing an SATPS signal receiver/processor to receive and process SATPS signals from the SATPS antenna and to determine the location of the SATPS antenna; and

providing angular orientation determination means, attached to said digital camera, for determining the angular orientation of said digital camera independently of the SATPS signals received from the SATPS signal sources.

24. The apparatus of claim 18, wherein said step of determining said position information comprises:

providing an SATPS signal antenna that receives SATPS signals transmitted from at least three SATPS signal sources; and

providing an SATPS signal receiver/processor to receive and process SATPS signals from the SATPS antennas and to determine the time of receipt of the SATPS signals at the SATPS antenna.

25. The apparatus of claim 18, wherein said step of providing an authentication key I comprises the steps of:

(1) numbering said pixel values in said array of pixel values m=1, 2, . . . , N;

(2) assigning to said pixel value number m a unique prime number p(m) in a sequence of distinct prime numbers;

(3) assigning to said pixel value number n a number q(m)=p(m) if said pixel value numbered m belongs to said chosen subset CS of pixel values and

(4) defining said key I by ##EQU15##

26. The apparatus of claim 18, wherein said step of providing said authentication key I comprises the steps of:

(1) numbering said pixel bit values in said array of pixel values m=1, 2, . . . , N;

(2) assigning to said pixel bit value number a unique prime number p(m) in a sequence of distinct prime numbers;

(3) assigning to said pixel bit value number m a number q'"'"'(m)=p(m) if said pixel bit value numbered m belongs to said chosen subset CS of pixel bit values and assigning a number q(m)=1 if said pixel bit value numbered m does not belong to said chosen subset CS of pixel bit values; and

(4) defining said key I by ##EQU16##

27. The apparatus of claim 18, wherein said step of providing said authentication key I comprises the steps of:

(1) numbering said pixel values in said array of pixel values m=1, 2, . . . , N;

(2) assigning to said pixel value number m a number r(m)=1 if said pixel value numbered m belongs to said chosen subset CS of pixel values and r(m)=0 if said pixel value numbered m does not belong to said chosen subset CS of pixel values; and

(3) defining said key I by ##EQU17## where Z is a selected real number greater than 1.

28. The apparatus of claim 27, further comprising the step of selecting said real number Z to be equal to 2.

29. The apparatus of claim 18, wherein said step of providing said authentication key I comprises the steps of:

(1) numbering said pixel bit values in said array of pixel values m=1, 2, . . . , K·

N, where K is the number of bits used to express a pixel value;

(2) assigning said pixel bit value number m a number r'"'"'(m)=1 if said pixel bit value numbered m belongs to said chosen subset CS of pixel bit values and r'"'"'(m)=0 if said pixel bit value numbered m does not belong to said chosen subset CS of pixel bit values; and

(3) defining said key I by ##EQU18## where Z is a selected real number greater than 1.

30. The apparatus of claim 29, further comprising the step of selecting said real number Z to be equal to 2.

31. The apparatus of claim 18, wherein said step of providing said authentication key I comprises the steps of:

providing an overlay of polygons p_g, numbered g=1, 2, . . . , G (G≧

2), of substantially identical shape and size that overlays said array of pixel locations;

assigning each pixel location in said array of pixel locations to one polygon in the overlay;

assigning at least one pixel location in said chosen subset CS to each polygon in the overlay;

computing a sub-key (g,I_g) for each polygon p_g that indicates the members of said chosen subset CS that are assigned to the polygon p_g ; and

determining said authentication key I from the collection of sub-keys {(g,I_g)}_g determined for the polygons p_g in the overlay.

32. The method of claim 31, further comprising the step of choosing said polygons p_g in said overlay from a class of polygons consisting of isoceles triangles, equilateral triangles, squares, rectangles, parallelograms, equilateral regular hexagons and non-equilateral regular hexagons.

33. The apparatus of claim 18, further comprising the step of choosing said chosen subset CS of said array PA of pixels so that, for any pixel in said pixel array PA a circle, centered at this pixel and having a diameter at least equal to a selected threshold number D, contains at least one pixel belonging to said chosen subset CS, where D is at least four times the pixel-to-pixel nearest neighbor distance.

34. The apparatus of claim 18, further comprising the step of choosing said chosen subset CS of said array PA of pixels to include at least one of the following patterns of pixels:

a substantially straight line containing contiguous pixels, a substantially straight line containing non-contiguous pixels, a curved line containing contiguous pixels, and a curved line containing non-contiguous pixels.