Halftone imaging method and apparatus utilizing pyramidol error convergence

• US 5,109,282 A
• Filed: 06/20/1990
• Issued: 04/28/1992
• Est. Priority Date: 06/20/1990
• Status: Expired due to Fees

• Current Assignee: The Schepens Eye Research Institute Inc (Mass General Brigham, Inc.)
• Original Assignee: EYE Research Institute Of Retina Foundation
• Inventors: Peli, Eli
• Primary Examiner(s): Fuller, Benjamin R.
• Assistant Examiner(s): Frahm, Eric
• Application Number:
  US07/540,685
• Time in Patent Office: 678 Days
• Field of Search: 358/298, 358/443, 358/455, 358/456, 358/457, 358/458, 358/463, 358/465, 358/466
• US Class Current: 358/3.14
• CPC Class Codes: H04N 1/4051 producing a dispersed dots halftone pattern, the dots having substantially the same size different sizes H04N1/4057

Abstract

Apparatus and methods for converting continuous grey tone images into high resolution halftone images utilize an iterative, multi-level, multi-resolution error convergence process. The continuous grey tone image is first binarized. At each level of the process, the binarized image is compared with the grey tone image over a larger window of pixels. Within each window, selected binarized image pixels are tested for possible change in binary assignment. The binary assignment of a given test pixel is changed if the change would result in a lower average error over the entire window. By varying the selection of test pixels, the process can provide clustered dot patterns and dithering.

Claims

1. Apparatus for transforming a multiple gray scale image into a halftone image, the multiple gray scale image having a range of gray scale levels including a lightest shade and a darkest shade, the apparatus comprising

A. means for converting said gray scale image into a first corresponding halftone image by converting each pixel value of the gray scale image into one of two opposing extreme pixel values, each extreme pixel value corresponding to the lightest and darkest shade in the range of gray scale levels of the multiple gray scale image.

B. means for generating an error matrix representative of a difference between each pixel value in the first halftone image and a corresponding pixel value in the gray scale image, and

C. means for modifying the first halftone image by a pyramidal error convergence for successively larger sized blocks of pixels for a predetermined number of levels, where said means for modifying comprises

means for calculating a first error average, the first error average being an average of the corresponding pixel values in the error matrix, for each of a plurality of equal sized blocks of pixels in the first halftone image, each block being centered around a preselected pixel position,

means for calculating, for each said block, a second error average, the second error average representing what the first error average would be if (i) the value of the preselected pixel position in the first halftone image was changed to an opposing extreme pixel value, and a corresponding error value in an error matrix was recalculated accordingly, and

means for changing, in each said block, the value of the preselected pixel position in the first halftone image to the opposing extreme pixel value if the second error average is less than the first error average.

2. A method for transforming a multiple gray scale image into a halftone image, the multiple gray scale image having a range of gray scale levels including a lightest shade and a darkest shade, the method comprising the steps of:

A. generating a first halftone image corresponding to said multiple gray scale image by converting each pixel value of the gray scale image into one of two opposing extreme pixel values, each extreme pixel value corresponding to the lightest and darkest shade in the range of gray scale levels of the multiple gray scale image,

B. generating an error matrix representative of a difference between each pixel value in the first halftone image and a corresponding pixel value in the gray scale image, and

C. modifying the first halftone image by a pyramidal error convergence means for successively larger sized blocks of pixels for a predetermined number of levels, where each level of the pyramidal error convergence means comprises the further steps of;

calculating a first error average, the first error average being the average of an corresponding pixel values in the error matrix for each of a plurality of equal sized blocks of pixels in the first halftone image, each block of pixels being centered around a preselected position,

calculating a second error average, the second error average representing what the first error average would be for each said block if the value of the preselected pixel position in the first halftone image was changed to an opposing extreme pixel value, and a corresponding error value in the error matrix was recalculated accordingly, and

changing, for each said block, the value of the preselected pixel position in the first halftone image to the opposing extreme pixel value if the second error average is less than the first error average.

3. A method for transforming an array of elements to minimize errors in the array, the method comprising the steps of:

averaging error values over each of a plurality of equal-sized blocks of elements, each block surrounding and being centered around a preselected element, each preselected element having an associated value,

changing the associated value of each preselected element if the change results in a lower averaged error value of the block of elements centered around the preselected element, and

successively repeating the above steps for increasingly larger-sized blocks of elements, with a different set of preselected centered-element positions for each block-size stage.