Loose-gray-scale template matching

• US 6,678,414 B1
• Filed: 02/17/2000
• Issued: 01/13/2004
• Est. Priority Date: 02/17/2000
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Loce, Robert P., Cuciurean-Zapan, Clara, Williams, Leon C.
• Primary Examiner(s): Au, Amelia M.
• Assistant Examiner(s): Le, Brian Q.
• Application Number:
  US09/505,875
• Time in Patent Office: 1,426 Days
• Field of Search: 382/205, 382/209, 382/217, 382/218, 382/219, 382/220, 382/221, 382/270, 382/261, 382/271, 382/141, 382/183, 382/173, 358/1.2
• US Class Current: 382/209
• CPC Class Codes: G06V 10/36 Applying a local operator, i.e. means to operate on image points situated in the vicinity of a given point; Non-linear local filtering operations, e.g. median filtering
• CPC Class Codes: G06V 10/443 by matching or filtering
• CPC Class Codes: H04N 1/40075 Descreening, i.e. converting a halftone signal into a corresponding continuous-tone signal; Rescreening, i.e. combined descreening and halftoning

Abstract

An apparatus and method of template fitting for fitting a plurality of templates in correspondence with a gray-scale image, including receiving gray-scale image information of an observed image; defining a window of the gray-scale image information so as to enable a loose-gray-scale fit between the defined window and the plurality of templates; extracting a plurality of pixels of the image information and using the window to which to fit at least one of the plurality of templates. Further, fitting one of the plurality of templates to the defined window within a threshold looseness interval associated with the template wherein a looseness interval between the window of image data and the template is less than the threshold looseness interval.

Claims

1. A method for fitting a plurality of candidate templates in correspondence with a gray-scale image, comprising:

receiving gray-scale image information of an observed image;

defining a window which bounds a neighborhood about a target area within said image;

extracting gray-scale image information relating to said bounded neighborhood;

extracting gray-scale information from said candidate templates;

for all candidate templates, determining at least one looseness interval value by an application of a pre-defined looseness interval function f(x,t) where x is said extracted gray-scale image information and t is said extracted gray-scale information from said candidate template information;

defining at least one looseness threshold δ

for each determined looseness interval value;

comparing each of said looseness interval values to its respective looseness threshold δ

such that templates having a looseness value less than or equal to its respective looseness threshold δ

are identified as loosely fitting templates;

designating any of the identified loosely fitting templates as a match; and

fitting at least one of any of said Identified matching templates to said defined window of image data.

2. The method of claim 1 further generating using processing circuitry a looseness interval between window of received image and each template associated therewith;

and

comparing the threshold looseness interval to the looseness Interval using the processing circuitry.

3. The method of claim 2, wherein said templates and said threshold looseness intervals are stored in a representation which enables fitting one of a plurality of singular or families of templates to said defined window.

4. The method of claim 3, wherein said representation being either one or more of:

multiple nominal pixel values with incremental corresponding upper and lower threshold values, a lower value and upper value associated with the threshold interval, or a reduced quantization state with respect to a quantization state of the received image. The method of claim 2 further said matching step using template-wise looseness intervals instead of said pixel-wise looseness interval values.

5. The method of claim 2, wherein processing circuitry includes algorithmic operations for associating the templates with the gray-scale image Information.

6. The template fitting method of claim 1 further corresponding candidate templates either in a parallel or serial process.

7. The method of claim 1 further outputting gray-scale, high addressability, image statistics or templates match identifiers generated by said determining step.

8. The method of claim 1, wherein said extracted gray-scale image information comprises pixel tile information of a predetermined matrix size.

9. The method of claim 8 wherein the outputted enhanced tile information being high addressability information.

10. The method of claim 8 wherein said matching step generates a match identifier to match said pixel tile information.

11. The method of claim 8, wherein pixel-wise looseness interval values are generated.

12. The method of claim 11 further combining said pixel-wise looseness values to form template-wise looseness values.

13. The method of claim 11 further storing template pixel tile information and said pixel-wise looseness values.

14. The method of claim 13 wherein said templates and said pixel-wise threshold looseness intervals are stored in a representation which enables fitting one of a plurality of single or families of templates to said pixel tile information.

15. The method of claim 14 comprising;

wherein said representation being either multiple nominal pixel values with incremental corresponding upper and lower threshold values, a lower value and upper value associated with the threshold interval, a reduced quantization state with respect to a quantization state of the received image.

16. The method of claim 11 further using arithmetic or algorithmic processes to calculate the pixel-wise looseness interval values.

17. The method of claim 8 further said matching step using template-wise looseness intervals instead of said pixel-wise looseness interval values.

18. The method of claim 17 further using arithmetic or algorithmic processes to calculate the template-wise looseness values.

19. The method of claim 17 further storing said templates and template-wise looseness values.