Halftone imaging method and apparatus utilizing pyramidol error convergence

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

Claim 3

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.

Claim 4

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.

Claim 5

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.

Claim 6

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.