Template formation method and apparatus

• US 6,011,866 A
• Filed: 05/16/1996
• Issued: 01/04/2000
• Est. Priority Date: 05/22/1995
• Status: Expired due to Term

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Donelly, Ross Alexander, Demetriou, Stamatios
• Primary Examiner(s): Chang, Jon
• Application Number:
  US08/649,074
• Time in Patent Office: 1,328 Days
• Field of Search: 382/209, 382/218, 382/195, 382/294, 382/295, 382/296, 382/297, 382/298, 382/216, 382/217, 382/205, 382/190, 382/135, 382/124, 382/125
• US Class Current: 382/216
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors

Abstract

A method of determining an indicator for the presence of an image is disclosed in which the image is comprised of a two dimensional array of pixels. The method finds particular use in the prevention of fraudulent copying of images, such as bank notes using colour laser copiers and printers. The method firstly imposes a grid of cells over a portion of the image. Then a representative value for each of the cells is determined. Next, a measure of the difference between the representative values of adjacent cells of the grid is determined over the whole of the grid. The first three steps are then repeated for substantially all possible positions of the grid of cells to determine a grid position having an overall maximum positional difference. Finally, the grid position and the representative value for each of said cells is used as a representation of the image. The representation can thus comprise a template used in an image detection system.

Claims

1. A method of determining an indicator for a presence of an image, said image notionally being made up of a two dimensional array of pixels, said method comprising the steps of:

(a) imposing a grid of cells over a portion of the image;

(b) determining a representative value for each of said cells;

(c) determining a measure of the difference between representative values of adjacent cells of said grid, said measure being determined over the whole of said grid;

(d) repeating steps (a) to (c) for substantially all possible positions of said grid of cells to determine an optimal grid position in which at least an adjacent pair of cells returns a maximum difference measure;

(e) for each cell within said grid corresponding to said optimal grid position in which at least an adjacent pair of said cells returns a maximum difference measure, determining a range of representative values for said cells, said range being derived from the maximum and minimum representative values for said cell when said grid is subjected to a predetermined amount of rotation, scaling and translation or any combination thereof; and

(f) utilizing said grid optimal position and said range of representative values for each cell within said grid corresponding to said grid position as an indicator of said image.

2. The method according to claim 1, wherein step (f) further comprises expanding endpoint values of said ranges so that said endpoint values can be represented by a predetermined number of binary digits.

3. A method of deriving an indicator of the presence of an image, said method comprising the steps of:

(a) determining representations of a multiplicity of substantially non-overlapping portions of said image;

(b) determining positional information relating to a pair of said representations, said positional information comprising a measure of a distance between said pair of representations, wherein said distance measure includes a range of values to allow for a predetermined amount of rotation, translation and scaling of said image or any combination thereof; and

(c) utilizing said representations and said positional information as an indicator of said image.

4. The method according to claim 3, herein said distance measure includes a magnitude and directional components.

5. A method of determining a position of a pair of templates of an image, said image notionally being made up of a two dimensional array of pixels, said method comprising the steps of:

(a) scanning said image and extracting a single color component of said image and storing an image of the colour component; and

(b) for each of a predetermined number of required rotations denoted θ

, performing the following steps;

(i) rotating the colour component image by a current rotating angle θ

;

(ii) low pass filtering the colour component image through a convolution of the colour component image with a square box function;

(iii) for each possible position of a template in said image, calculating a merit value of said template from said low pass filtered colour component image;

(iv) for substantially all possible pairs of template positions in the image which do not substantially overlap, calculating a product for each template position merit value for a pair of templates in each possible pair of template positions; and

(v) choosing the pair of templates having the highest of said product values to represent the image.

6. The method according to claim 5, wherein said merit is calculated from the sum of differences between adjacent filtered pixel values of said low pass filtered colour component image.

7. The method according to claim 5, wherein said merit value includes a measure of how much the brightness varies over the whole of the template.

8. The method according to claim 5, wherein said merit value includes a measure of the range of values of the template of said low pass filtered colour component image.

9. The method according to claim 5, further comprising the steps of:

(vi) dividing the template covering said low pass filtered colour component image into an array of cells, each of said cells comprising an array of pixels; and

(vii) calculating for each cell in the template, a minimum and maximum number of pixel values in said low pass filtered colour component image.

10. The method according to claim 9, wherein said step (vii) further comprises allowing the position of each cell in a template to vary by a predetermined amount so as to take into account the effects of translation, rotation or scaling of said image.

11. The method according to claim 5, wherein said possible positions of said template in said image are those where all four corners of said template lie within the original image and those where two opposite corners lie outside the image.

12. The method according to claim 5, wherein said single colour component is magenta.

13. The method according to claim 5, wherein said image is scanned at the resolution at which it may be printed on a predetermined output device.

14. The method according to claim 5, wherein predetermined rotations denoted θ

lie between zero and ninety degrees.

15. An apparatus for determining an indicator for a presence of an image, said image notionally being made up for a two dimensional array of pixels, said apparatus comprising:

means for imposing a grid of cells over a portion of the image;

means for determining a representative value for each of said cells;

means for determining a measure of the difference between representative values of adjacent cells of said grid, said measure being determined over the whole of said grid;

means for determining an optimal grid position, for substantially all possible positions of said grid of cells, in which at least an adjacent pair of cells returns a maximum difference measure;

means for determining a range of representative values for each cell within said grid corresponding to said optimal grid position in which at least an adjacent pair of said cells returns a maximum difference measure, for said cell, said range being derived from the maximum and minimum representative values for said cell when said grid is subjected to a predetermined amount of rotation, scaling and translation or any combination thereof; and

means for utilizing said grid optimal position and said range of representative values for each cell within said grid corresponding to said grid position as said indicator of said image.

16. The apparatus according to claim 15, further comprising a means for expanding endpoint values of said ranges so that said endpoint values can be represented by a predetermined number of binary digits.

17. An apparatus for deriving an indicator of the presence of an image, said apparatus comprising:

means for determining representations of a multiplicity of substantially non-overlapping portions of said image;

means for determining positional information relating to a pair of said representations, wherein said positional information comprises a measure of a distance between said pair of representations, and wherein said distance measure includes a range of values to allow for a predetermined amount of rotation, translation and scaling of said image of any combination thereof; and

means for utilizing said representations and said positional information as said indicator of said image.

18. The apparatus according to claim 17, wherein said distance measure includes a magnitude and directional components.

19. An apparatus for determining a position of a pair of templates of an image, said image notionally being made up of a two dimensional array of pixels, said apparatus comprising:

means for scanning said image and extracting a single colour component of said image and storing an image of the colour component; and

means for performing the following steps;

rotating the colour component image by a current rotation angle θ

for each of a predetermined number of required rotations denoted θ

;

low pass filtering the colour component image through a convolution of the colour component image with a square box function;

calculating a merit value of said template from said low pass filtered colour component image, for each possible position of the template in said image;

calculating a product of each template position merit value of a pair of templates, for substantially all possible pairs of template positions in the image which do not substantially overlap; and

choosing the pair of templates having the highest of said product values to represent the image.

20. The apparatus according to claim 19, wherein said merit is calculated from the sum of differences between adjacent filtered pixel values of said low pass filtered colour component image.

21. The apparatus according to claim 19, wherein said merit value includes a measure of how much the brightness varies over the whole of the template.

22. The apparatus according to claim 19, wherein said merit value includes a measure of the range of values of the template of said low pass filtered colour component image.

23. The apparatus according to claim 19, further comprising:

means for dividing the template covering said low pass filtered colour component image into an array of cells, each of said cells comprising an array of pixels; and

means for calculating, for each cell in the template, a minimum and maximum number of pixel values in said low pass filtered colour component image.

24. The apparatus according to claim 23, further comprising means for allowing the position of each cell in a template to vary by a predetermined amount so as to take into account the effects of translation, rotation or scaling of said image.

25. The apparatus according to claim 19, wherein said possible positions of said template in said image are those where all four corners of said template lie within the original image and those where two opposite corners lie outside the image.

26. The apparatus according to claim 19, wherein said single colour component is magenta.

27. The apparatus according to claim 19, wherein said image is scanned at the resolution at which it may be printed on a predetermined output device.

28. The apparatus according to claim 19, wherein predetermined rotations denoted θ

lie between zero and ninety degrees.

29. A computer program product comprising a computer readable medium having a computer program recorded therein for deriving an indicator of the presence of an image, said image notionally being made up a two dimensional array of pixels, said computer program product comprising:

means for imposing a grid of cells over a portion of the image;

means for determining a representative value for each of said cells;

means for determining a measure of the difference between representative values of adjacent cells of said grid, said measure being determined over the whole of said grid;

means for determining an optimal grid position, for substantially all possible positions of said grid of cells, in which at least an adjacent pair of cells returns a maximum difference measure;

means for determining a range of representative values for each cells within said grid corresponding to said optimal grid position in which at least an adjacent pair of said cells returns a maximum difference measure, for said cell, said range being derived from the maximum and minimum representative values for said cell when said grid is subjected to a predetermined amount of rotation, scaling and translation of any combination thereof; and

means for utilizing said grid optimal position and said range of representative values for each cell within said grid corresponding to said grid position as said indicator of said image.

30. The computer program product according to claim 29, further comprising means for expanding endpoint values of said ranges so that said endpoint values can be represented by a predetermined number of binary digits.

31. A computer program product comprising a computer readable medium having a computer program recorded therein for deriving an indicator of a presence of an image, said image notionally being made up of a two dimensional array of pixels, said computer program product comprising:

means for determining representations of a multiplicity of substantially non-overlapping positions of said image;

means for determining positional information relating to a pair of said representations, wherein said positional information comprises a measure of a distance between said pair of representations, and wherein said distance measure includes a range of values to allow for a predetermined amount of rotation, translation and scaling of said image or any combination thereof; and

means for utilizing said representations and said positional information as said indicator of said image.

32. The computer program product according to claim 31, wherein said distance measure includes a magnitude and directional components.

33. A computer program product comprising a readable medium having a computer program recorded therein for determining a position of a pair of templates of an image, said image notionally being made up of a two dimensional array of pixels, said computer program product comprising:

(a) means for scanning said image and extracting a single colour component of said image and storing an image of the colour component; and

(b) for each of a predetermined number of required rotations denoted θ

, means for performing the following steps;

(i) rotating the colour component image by a current rotating angle θ

;

(ii) low pass filtering the colour component image through a convolution of the colour component image with a square box function;

(iii) for each possible position of a template in said image, calculating a merit value of said template from said low pass filtered colour component image;

(iv) for substantially all possible pairs of template positions in the image which do not substantially overlap, calculating a product for each template position merit value for a pair of templates in each possible pair of template positions; and

(v) choosing the pair of templates having the highest of said product values to represent the image.