Image authentication patterning

• US 5,987,136 A
• Filed: 12/16/1997
• Issued: 11/16/1999
• Est. Priority Date: 08/04/1997
• Status: Expired due to Term

• Current Assignee: Trimble Navigation Limited (Trimble Inc.)
• Original Assignee: Trimble Navigation Limited (Trimble Inc.)
• Inventors: Pelley, Allan M., Schipper, John F.
• Primary Examiner(s): CANGIALOSI, SALVATORE A
• Application Number:
  US08/991,314
• Time in Patent Office: 700 Days
• Field of Search: 380/25, 380/54
• US Class Current: 713/176
• CPC Class Codes: G01S 17/86 Combinations of lidar systems with systems other than lidar, radar or sonar, e.g. with direction finders
• CPC Class Codes: G01S 19/53 Determining attitude
• CPC Class Codes: H04N 1/32203 Spatial or amplitude domain methods H04N1/32309 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/3233 of authentication information, e.g. digital signature, watermark
• CPC Class Codes: H04N 2201/3235 Checking or certification of the authentication information, e.g. by comparison with data stored independently
• CPC Class Codes: H04N 2201/3236 Details of authentication information generation
• 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

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 and/or distance from the camera to a selected object. 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, including a digital image-forming lens that forms a digitally expressed image ("digital image") of a selected view as an array of pixel values, with each pixel value corresponding to a pixel in an array of pixels;

a position determination mechanism, 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, the time a digital image is formed, and an estimated distance from a selected object to the digital image camera, at the time the digital image camera forms a digitally image;

digital image storage means for receiving a digital image from the digital image camera, for receiving the position information from the position determination mechanism, 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 pixels is reformed as a modified pixel value to contain a portion of the position information, for storing the modified array of pixel values, and for providing an authentication indicium that indicates the chosen subset CS of the modified array of pixels; and

an authentication mechanism, connected to the digital image storage means, for receiving putative position information for a selected digital image, for using the authentication indicium to retrieve the position information from the digital image storage mechanism, for comparing the putative position information with the retrieved position information, and for taking at least one of the following actions;

(i) withholding authentication of the selected digital image if the putative position information does not substantially agree with the retrieved position information and (ii) authenticating the selected digital image if the putative position information substantially agrees with the retrieved position information.

2. 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.

3. The apparatus of claim 1, wherein said position determination mechanism 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 at least one of (ii) the location of the SATPS antenna and (ii) a time of receipt of at least one SATPS signal.

4. The apparatus of claim 3, further comprising angular orientation determination mechanism, attached to said digital camera, for determining the angular orientation of said digital camera at least partly independently of said SATPS signals received from said SATPS signal sources.

5. The apparatus of claim 3, wherein said position determination mechanism further comprises:

at least three SATPS signal antennas, arranged non-collinearly to each receive SATPS signals transmitted from said 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 the at least three 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:

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

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

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

(4) said authentication indicium I is defined by ##EQU12##

7. The apparatus of claim 1, wherein:

(1) said pixel bit values in said array of pixel values are numbered n=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 unique prime number p(n) in a sequence of distinct prime numbers;

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

(4) said authentication indicium I is defined by ##EQU13##

8. The apparatus of claim 1, wherein:

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

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

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

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

10. The apparatus of claim 1, wherein:

(1) said pixel bit values in said array of pixel values are numbered n=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'"'"'(n)=1 if said pixel bit value numbered m belongs to said chosen subset CS of pixel bit values and is assigned a number r'"'"'(n)=0 if said pixel bit value numbered m does not belong to said chosen subset CS of pixel bit values; and

(3) said indicium I is defined by ##EQU15## 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 said authentication mechanism 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-indicium (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 indicium I from the collection of sub-indicia {(g, I_g)}_g determined for the polygons p_g in the overlay.

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

14. The apparatus of claim 1, wherein said chosen subset CS of said array PA of pixel locations 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.

15. The apparatus of claim 1, wherein said chosen subset CS of said array PA of pixel locations 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.

16. 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 that includes 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 selected 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 pixel value array to contain a portion of the position information, and storing the modified pixel value array in a digital image storage mechanism; and

providing an authentication indicium that indicates the chosen subset CS of the array of modified pixel values;

receiving putative position information for a selected digital image;

using the authentication indicium to retrieve the position information from the digital image storage mechanism;

comparing the putative position information with the retrieved position information; and

taking at least one of the following actions;

(i) withholding authentication of the selected digital image if the putative position information does not substantially agree with the retrieved position information and (ii) authenticating the selected digital image if the putative position information substantially agrees with the retrieved position information.

17. The method of claim 16, further comprising the step of displaying selected information contained in said modified digital image in at least one of electronically perceptible form, visually perceptible form and audibly perceptible form.

18. The method of claim 16, wherein said step of determining said position information comprises:

receiving SATPS signals transmitted from at least three SATPS signal sources; and

receiving and processing the SATPS signals to determine the location of said digital camera.

19. The method of claim 18, further comprising the step of providing an angular orientation determination mechanism, attached to said digital camera, for determining the angular orientation of said digital camera at least partly independently of said SATPS signals received from said SATPS signal sources.

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

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

receiving and processing SATPS signals from the SATPS antennas to determine the location of each of the SATPS antennas and the angular orientation of a plane containing the at least three 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.

21. The method of claim 16, further comprising the steps of:

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

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

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

(4) defining said authentication indicium I as ##EQU16##

22. The method of claim 16, further comprising the steps of:

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

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

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

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

(4) defining said authentication indicium I as ##EQU17##

23. The method of claim 16, further comprising the steps of:

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

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

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

24. The method of claim 23, further comprising the step of selecting said number Z to be equal to 2.

25. The method of claim 16, further comprising the steps of:

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

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

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

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

26. The method of claim 25, further comprising the step of selecting said number Z to be equal to 2.

27. The method of claim 16, wherein said step of providing said authentication mechanism comprises the steps of:

providing a set 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-indicium (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 indicium I from the collection of sub-indicia {(g, I_g)}_g determined for the polygons p_g in the overlay.

28. The method of claim 27, further comprising the step of drawing said polygons p_g in said overlay from a group of polygons consisting of isoceles triangles, equilateral triangles, squares, rectangles, parallelograms, equilateral regular hexagons and non-equilateral regular hexagons.

29. The method of claim 16, further comprising the step of choosing said chosen subset CS of said array PA of pixel locations 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.

30. The method of claim 16, further comprising the step of choosing said subset CS of said array PA of pixel locations 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.