Apparatus and method for pattern recognition

• US 6,272,245 B1
• Filed: 01/23/1998
• Issued: 08/07/2001
• Est. Priority Date: 01/23/1998
• Status: Expired due to Term

• Current Assignee: Northeastern University
• Original Assignee: Seiko Epson Corporation (Seiko Group)
• Inventors: Lin, Shang-Hung
• Primary Examiner(s): Au, Amelia M.
• Assistant Examiner(s): MILLER, MARTIN E
• Application Number:
  US09/012,901
• Time in Patent Office: 1,292 Days
• Field of Search: 382/205, 382/195, 382/135, 382/218, 382/219, 382/169, 358/504, 358/515, 358/518, 358/522
• US Class Current: 382/195
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors
• CPC Class Codes: G06V 30/414 Extracting the geometrical structure, e.g. layout tree; Block segmentation, e.g. bounding boxes for graphics or text

Abstract

Features characterizing at least two significant portions or regions of the printed pattern on a model document are extracted from a scanned-in image of the model document. Statistical characteristics of each significant region are calculated from the extracted features and saved in a memory. In addition, geometrical relationships, e.g. distances and angles, between the regions are also saved in a memory. The geometrical relationships are represented by the coordinates of the regions in a predetermined coordinate system, e.g. the x-y coordinate system corresponding to the scan area on the platen of a scanner. When a new or trial document is scanned and examined through a search window, features are extracted from the search window blocks and compared to the statistical characteristics of the model document previously stored in memory. If there is a match, the coordinates of the search window having the matching features in the trial document are recorded in a candidate list. After the entire trial document has been processed, the geometric relationships between the window blocks on the candidate list are compared with the geometrical relationships of the matching significant region blocks of the model document and if the relationships correspond the trial document is considered a match.

Claims

1. An apparatus for recognizing patterns in a trial image comprising:

a scanner for scanning in said trial image and for scanning in a model image and an image buffer for storing a scanned-in model image;

a region extractor for extracting region image blocks from said model image stored in said image buffer and a region buffer for storing said extracted region image blocks;

an affine transformer for translating and rotating said region image blocks to create additional region image blocks for storage in said region buffer;

a feature extractor for extracting features from window image blocks in said trial image, said window image blocks having respective coordinates in a coordinate space;

said feature extractor being coupled to said region buffer for extracting characteristics of said region image blocks of said model image;

a memory for storing said characteristics of said region image blocks of said model image, said region image blocks having respective coordinates in said coordinate space;

a similarity comparator for comparing said extracted features to said characteristics of said region image blocks and for indicating features similar to said region characteristics;

a candidate list for storing coordinates of window image blocks with features indicated by said comparator as having similar region characteristics and for storing coordinates of corresponding similar regions;

an analyzer for determining a window image block geometric relationship between at least two window image blocks in said candidate list from said respective coordinates and for determining a region geometric relationship between at least two corresponding regions from said respective coordinates; and

a geometry comparator for comparing said window image block geometric relationship to said region geometric relationship for recognizing said trial image as corresponding to said model image when said window image block geometric relationship is the same as said region geometric relationship.

2. An apparatus as in claim 1 wherein said feature extractor comprises a histogram equalizer for redistributing pixel gray levels in an area of said trial image.

3. An apparatus as in claim 2 wherein said feature extractor comprises an x-y direction projector for forming a feature vector from said trial image area with redistributed pixel gray levels.

4. An apparatus as in claim 1 wherein said feature extractor comprises a histogram equalizer for redistributing pixel gray levels in an area of said model image.

5. An apparatus as in claim 4 wherein said feature extractor comprises an x-y direction projector for forming a feature vector from said model image area with redistributed pixel gray levels.

6. An apparatus as in claim 5 further comprising a vector statistical analyzer for forming statistical vectors characterizing regions of said model image.

7. An apparatus as in claim 1 wherein said analyzer comprises a distance calculator for calculating a distance between said at least two window image blocks and a distance between said at least two corresponding regions.

8. An apparatus as in claim 7 wherein said analyzer comprises an angle calculator for calculating an angle between said at least two window image blocks and an angle between said at least two corresponding regions.

9. A method for recognizing patterns in a trial image comprising:

scanning in a model image and storing said scanned-in model image in an image buffer;

extracting region image blocks from said model image stored in said image buffer and storing said extracted region image blocks in a region buffer;

translating and rotating said region image blocks to create additional region image blocks for storage in said region buffer;

extracting characteristics of said region image blocks of said model image;

storing characteristics of said region image blocks of said model image, said region image blocks having respective coordinates in said coordinate space;

scanning in a trial image and extracting features from window image blocks in said trial image, said window image blocks having respective coordinates in a coordinate space;

comparing said extracted features to said characteristics of said region image blocks and indicating features similar to said region characteristics;

storing coordinates of window image blocks with features indicated by said comparator as having similar region characteristics and storing coordinates of corresponding similar regions;

determining a window image block geometric relationship between at least two window image blocks from said respective coordinates and determining a region geometric relationship between at least two corresponding regions from said respective coordinates; and

comparing said window image block geometric relationship to said region geometric relationship and recognizing said trial image as corresponding to said model image when said window image block geometric relationship is the same as said region geometric relationship.

10. A method as in claim 9 wherein said feature extracting step comprises histogram equalizing an extracted feature for redistributing pixel gray levels in an area of said trial image.

11. A method as in claim 10 wherein said feature extracting step comprises x-y direction projecting said redistributed pixel gray levels of said trial image area and forming a feature vector.

12. A method as in claim 9 wherein said region feature extracting step comprises histogram equalizing an extracted region feature to redistribute pixel gray levels in an area of said model image.

13. A method as in claim 12 wherein said region feature extracting step comprises x-y direction projecting said histogram equalized region feature and forming a feature vector from said model image area with redistributed pixel gray levels.

14. A method as in claim 13 further comprising statistically analyzing feature vectors and forming statistical vectors characterizing regions of said model image.

15. A method as in claim 9 wherein said determining step comprises calculating a distance between said at least two window image blocks and a distance between said at least two corresponding regions.

16. A method as in claim 15 wherein said determining step comprises calculating an angle between said at least two window image blocks and an angle between said at least two corresponding regions.

17. A medium readable by a machine embodying a program of instructions executable by said machine to perform a method of recognizing patterns in a trial image, said pattern recognizing method comprising:

scanning in a model image and storing said scanned-in model image in an image buffer;

extracting region image blocks from said model image stored in said image buffer and storing said extracted region image blocks in a region buffer;

translating and rotating said region image blocks to create additional region image blocks for storage in said region buffer;

extracting characteristics of said region image blocks of said model image;

storing characteristics of said region image blocks of said model image, said region image blocks having respective coordinates in said coordinate space;

scanning in a trial image and extracting features from window image blocks in said trial image, said window image blocks having respective coordinates in a coordinate space;

comparing said extracted features to said characteristics of said region image blocks and indicating features similar to said region characteristics;

storing coordinates of window image blocks with features indicated by said comparator as having similar region characteristics and storing coordinates of corresponding similar regions;

determining a window image block geometric relationship between at least two window image blocks from said respective coordinates and determining a region geometric relationship between at least two corresponding regions from said respective coordinates; and

comparing said window image block geometric relationship to said region geometric relationship and recognizing said trial image as corresponding to said model image when said window image block geometric relationship is the same as said region geometric relationship.

18. A medium as in claim 17 wherein in said pattern recognizing method said feature extracting step comprises histogram equalizing an extracted feature for redistributing pixel gray levels in an area of said trial image.

19. A medium as in claim 18 wherein in said pattern recognizing method said feature extracting step comprises x-y direction projecting said redistributed pixel gray levels of said trial image area and forming a feature vector.

23. A medium as in claim 17 wherein in said pattern recognizing method said determining step comprises calculating a distance between said at least two window image blocks and a distance between said at least two corresponding regions.

24. A medium as in claim 23 wherein in said pattern recognizing method said determining step comprises calculating an angle between said at least two window image blocks and an angle between said at least two corresponding regions.

20. A medium as in 17 wherein in said pattern recognizing method said region feature extracting step comprises histogram equalizing an extracted region feature to redistribute pixel gray levels in an area of said model image.

21. A medium as in claim 20 wherein in said pattern recognizing method said region feature extracting step comprises x-y direction projecting said histogram equalized region feature and forming a feature vector from said model image area with redistributed pixel gray levels.

22. A medium as in claim 21 wherein said pattern recognizing method further comprises statistically analyzing feature vectors and forming statistical vectors characterizing regions of said model image.

25. A system for comparing a trial document to a model document and for preventing copying of a trial document matching said model document comprising:

a scanner for scanning in said model document and said trial document;

an image buffer for storing a scanned-in model document;

a region extractor for extracting region image blocks from said model document stored in said image buffer and a region buffer for storing said extracted region image blocks;

an affine transformer for translating and rotating said region image blocks to create additional region image blocks for storage in said region buffer;

a feature extractor for extracting trial document features from window image blocks in said trial document and for determining characteristics of said region image blocks of said model document, said window image blocks having respective coordinates in a scan coordinate space;

a memory for storing said characteristics of said region image blocks of said model document, said region image blocks having respective coordinates in said scan coordinate space;

a similarity comparator for comparing said extracted features to said characteristics of said region image blocks and for indicating features similar to said region characteristics;

a candidate list for storing coordinates of window image blocks with features indicated by said comparator as having similar regions and for storing coordinates of corresponding similar regions;

an analyzer for determining a window image block geometric relationship between at least two window image blocks in said candidate list from said respective coordinates and for determining a region geometric relationship between at least two corresponding regions from said respective coordinates; and

a geometry comparator for comparing said window image block geometric relationship to said region geometric relationship for recognizing said trial document as matching said model document when said window image block geometric relationship is the same as said region geometric relationship;

a printer;

an action unit coupled to said geometry comparator and said printer for preventing copying of said trial document if it matches said model document.

26. A system for comparing a trial document to a model document and for preventing copying of a trial document matching said model document comprising:

an input device for inputting an image of said model document and an image of said trial document;

an image buffer for storing an input model document;

a region extractor for extracting region image blocks from said model document stored in said image buffer and a region buffer for storing said extracted region image blocks;

an affine transformer for translating and rotating said region image blocks to create additional region image blocks for storage in said region buffer;

a feature extractor for extracting trial document features from window image blocks in said trial document and for determining characteristics of said region image blocks of said model document, said window image blocks having respective coordinates in a scan coordinate space;

a memory for storing said characteristics of said region image blocks of said model document, said region image blocks having respective coordinates in said scan coordinate space;

a similarity comparator for comparing said extracted features to said characteristics of said region image blocks and for indicating features similar to said region characteristics;

a candidate list for storing coordinates of window image blocks with features indicated by said comparator as having similar region characteristics and for storing coordinates of corresponding similar regions;

an analyzer for determining a window image block geometric relationship between at least two window image blocks in said candidate list from said respective coordinates and for determining a region geometric relationship between at least two corresponding regions from said respective coordinates; and

a geometry comparator for comparing said window image block geometric relationship to said region geometric relationship for recognizing said trial document as matching said model document when said window image block geometric relationship is the same as said region geometric relationship;

an output device;

an action unit coupled to said geometry comparator and said output device for preventing copying of said trial document if it matches said model document.

27. A system as in claim 26 wherein said input device is a digital camera.

28. A system as in claim 26 wherein said input device is a computer.

29. A system as in claim 26 wherein said input device is a scanner.

30. A system as in claim 26 wherein said output device is a printer.