Method and apparatus for combining multiple image scans for enhanced resolution

• US 5,767,987 A
• Filed: 09/26/1994
• Issued: 06/16/1998
• Est. Priority Date: 09/26/1994
• Status: Expired due to Fees

• Current Assignee: Ricoh Company Limited, Ricoh Corporation (Ricoh Company Limited)
• Original Assignee: Ricoh Company Limited, Ricoh Corporation (Ricoh Company Limited)
• Inventors: Van Steenkiste, Regis J., Wolff, Gregory J.
• Primary Examiner(s): Coles, Sr., Edward L.
• Assistant Examiner(s): Williams, Kimberly A.
• Application Number:
  US08/312,141
• Time in Patent Office: 1,359 Days
• Field of Search: 358/447, 358/448, 358/455, 358/456, 358/458, 358/459, 358/534, 382/299, 348/584, 348/448, 348/449, 348/452, 345/132
• US Class Current: 358/447
• CPC Class Codes: H04N 1/04 Scanning arrangements , i.e. arrangements for the displacement of active reading or reproducing elements relative to the original or reproducing medium, or vice versaH04N1/387 takes precedence
• CPC Class Codes: H04N 1/4092 Edge or detail enhancement
• CPC Class Codes: H04N 2201/0458 Additional arrangements for improving or optimising scanning resolution or quality

Abstract

An apparatus and method for producing an enhanced resolution image from a set of lower resolution pixel image scans uses jitter and cogging errors introduced by the scanner to provide the additional information about the image that is required to produce the high resolution. One of the image scans is selected as a prototype image and is interpolated to produce an image of higher density samples (mixels). Each of the remaining pixel image scans is aligned with the interpolated prototype. The mixel values of the prototype are iteratively adjusted by minimizing an error metric representing the difference between pixel values computed from the prototype and the corresponding pixel values of each of the lower resolution pixel image scans. The method and apparatus are suitable for use in document copying system, high resolution television imaging, facsimile system, and character regeneration systems.

Claims

1. A system for producing an enhanced resolution image from a set of lower resolution raster scanned images of an original image, the system comprising:

(a) a scanner with a point-spread-function (PSF) represented by a two-dimensional set of known values for raster scanning the original image subject and for producing as an output a multiplicity of signals, one for each raster scanned representation of the original image and having means for introducing tracking errors to ensure adequate variety in each raster scan of the original image for efficient reconstruction of an enhanced resolution raster scan image;

(b) converter means for uniformly sampling and quantizing the scanner output signal for producing a multiplicity of pixel value sets, one pixel value set for each scanner output signal;

(c) a memory for temporary storage of the multiplicity of pixel value sets produced by the converter means; and

(d) a numerical processor coupled to the memory for access to the stored pixel value sets, for storing of processed pixel value sets, and for executing a stored image resolution enhancement program, the numerical processor including means for,

(i) selecting one of the multiplicity of pixel value sets as a prototype scan from memory, the non-selected pixel value sets referred to as remaining pixel scans,

(ii) interpolating the prototype scan pixel values to produce an interpolated prototype scan with a higher density of sampled and quantized pixel values, the higher density of pixel values referred to as mixels,

(iii) aligning the interpolated prototype scan with a selected pixel scan of the remaining pixel scans,

(iv) adjusting the aligned interpolated prototype scan mixel values by minimizing an error cost function representative of a difference measure between a selected pixel of the selected pixel scan and a pixel value computed from the mixel values of the interpolated prototype scan using the scanner means known PSF to produce a computed pixel value from the interpolated prototype scan mixel values, for producing a modified prototype scan, and

(v) repeating the use of the means for aligning the interpolated prototype scan and the means for adjusting the aligned prototype scan for each of the non-selected remaining pixel scans using the modified prototype scan as the interpolated prototype scan so that after all remaining pixel scans are processed, the modified prototype scan is an enhanced resolution raster scan image of the original image.

2. The system of claim 1 further comprising a recorder means for accepting from the memory the enhanced resolution prototype scan and producing therefrom an enhanced resolution image.

3. The system of claim 1 wherein the tracking errors are of a known form.

4. The system of claim 3 wherein the numerical processor further comprises means for removing the tracking errors of known form from each of the multiplicity of pixel value sets.

5. The system of claim 1 wherein the means for adjusting the aligned interpolated prototype scan mixel values minimizes the error cost function by an iterative gradient descent algorithm.

6. The system of claim 1 wherein the means for aligning the interpolated prototype scan with a selected pixel scan is performed by minimizing a distance metric representative of the difference between the selected pixel scan and corresponding mixel values of the interpolated prototype scan.

7. The system of claim 6 wherein the distance metric is a quadratic distance metric.

8. The system of claim 6 wherein the distance metric is based on the absolute difference between the selected pixel scan and corresponding mixel values of the interpolated prototype scan.

9. The system of claim 6 wherein the means for aligning the prototype scan with a selected pixel scan is performed by maximizing a two-dimensional cross-covariance function.

10. A system for producing an enhanced resolution image from a set of lower resolution raster scanned images of an original image, the system comprising:

(a) a scanner with a point-spread-function (PSF) represented by a set of known values for raster scanning the original image subject and for producing as an output a multiplicity of signals, one for each raster scanned representation of the original image and having means for introducing tracking errors to ensure adequate variety in each raster scan of the original image for efficient reconstruction of an enhanced resolution raster scan image;

(b) converter means for uniformly sampling and quantizing the scanner output signal for producing a multiplicity of pixel value sets, one pixel value set for each scanner output signal;

(c) a memory for temporary storage of the multiplicity of pixel value sets produced by the converter means; and

(d) a numerical processor coupled to the memory for access to the stored pixel value sets, for storing of processed pixel value sets, and for executing a stored image resolution enhancement program, the numerical processor including means for,

(i) selecting one of the multiplicity of pixel value sets as a prototype scan from memory, the non-selected pixel value sets referred to as remaining pixel scans,

(ii) interpolating the prototype scan pixel values to produce an interpolated prototype scan with a higher density of sampled and quantized pixel values, the higher density of pixel values referred to as mixels,

(iii) aligning the interpolated prototype scan with a selected pixel scan of the remaining pixel scans,

(iv) adjusting the aligned interpolated prototype scan mixel values by minimizing an error cost function representative of a difference measure between a selected pixel of the selected pixel scan and a pixel value computed from the mixel values of the interpolated prototype scan using the scanner means known PSF to produce a computed pixel value from the interpolated prototype scan mixel values, for producing a modified prototype scan, the means for adjusting the aligned interpolated prototype scan mixel values including means for

(aa) forming overlapping cluster zones from contiguous prototype mixel elements contained within a rectangular array,

(bb) forming an associated mixel zone vector, one vector associated with each overlapping cluster zone, having elements corresponding to the prototype scan mixel values included within the associated overlapping cluster zone,

(cc) forming a zone matrix, each row having elements representative of known PSF values, which when multiplied by the associated mixel zone vector produces a vector of pixel value representative of the pixel elements included within the associated overlapping cluster zone, and

(dd) sequentially solving for each associated mixel zone vector using any overlapping elements of the associated mixel zone vector, as obtained, for updating the prototype scan mixel values, and

(v) repeating the use of the means for aligning the interpolated prototype scan and the means for adjusting the aligned prototype scan for each of the non-selected remaining pixel scans using the modified prototype scan as the interpolated prototype scan so that after all remaining pixel scans are processed, the modified prototype scan is an enhanced resolution raster scan image of the original image.

11. The system of claim 10 further comprising a recorder means for accepting from the memory the enhanced resolution prototype scan and producing therefrom an enhanced resolution image.

12. An image enhancement processor for use with a facsimile point-of-origin image scanner for producing a signal representative of an enhanced resolution image, the image enhancement processor connected to the output of the facsimile point-of-origin image scanner, the image scanner output represented by a multiplicity of sampled and quantized raster scans, each sampled and quantized raster scans forming a set of pixel values, the image enhancement processor comprising:

(a) a memory for temporary storage of the multiplicity of pixel value sets; and

(b) a numerical processor coupled to the memory for access to the stored pixel value sets, for storing of processed pixel value sets, and for executing a stored image resolution enhancement program the numerical processor including means for,

(i) selecting one of the multiplicity of pixel value sets as a prototype scan from memory, the non-selected pixel value sets referred to as remaining pixel scans,

(ii) interpolating the prototype scan pixel values to produce an interpolated prototype scan with a higher density of sampled and quantized pixel values, the higher density of pixel values referred to as mixels,

(iii) aligning the interpolated prototype scan with a selected pixel scan of the remaining pixel scans,

(iv) adjusting the aligned interpolated prototype scan mixel values by minimizing an error cost function representative of a difference measure between a selected pixel of the selected pixel scan and a pixel value computed from the mixel values of the interpolated prototype scan using the scanner means PSF to produce a computed pixel value from the interpolated prototype scan mixel values, for producing a modified prototype scan, and the means for adjusting the aligned interpolated prototype scan mixel values including means for

(aa) forming overlapping cluster zones from contiguous prototype mixel elements contained within a rectangular array;

(bb) forming an associated mixel zone vector, one vector associated with each overlapping cluster zone, having elements corresponding to the prototype scan mixel values included within the associated overlapping cluster zone,

(cc) forming a zone matrix, each row having elements representative of known PSF values, which when multiplied by the associated mixel zone vector produces a vector of pixel value representative of the pixel elements included within the associated overlapping cluster zone, and

(dd) sequentially solving for each associated mixel zone vector using any overlapping elements of the associated mixel zone vector, as obtained, for updating the prototype scan mixel values; and

(v) repeating the use of the means for aligning the interpolated prototype scan and the means for adjusting the aligned prototype scan for each of the non-selected remaining pixel scans using the modified prototype scan as the interpolated prototype scan so that after all remaining pixel scans are processed, the modified prototype scan is an enhanced resolution raster scan image of the original image.

13. An image enhancement point-of-origin facsimile scanner system for producing an enhanced resolution image for transmission, the system comprising:

(a) a scanner with a known point-spread-function (PSF) for raster scanning the original image subject and for producing as an output a multiplicity of signals, one for each raster scanned representation of the original image;

(b) converter means for uniformly sampling and quantizing the scanner output signal for producing a multiplicity of pixel value sets, one pixel value set for each scanner output signal;

(c) a memory for temporary storage of the multiplicity of pixel value sets produced by the converter means; and

(d) a numerical processor coupled to the memory for access to the stored pixel value sets, for storing of processed pixel values, and for executing a stored image resolution enhancement program the numerical processor including means for,

(i) selecting one of the multiplicity of pixel value sets as a prototype scan from memory, the non-selected pixel value sets referred to as remaining pixel scans,

(ii) interpolating the prototype scan pixel values to produce an interpolated prototype scan with a higher density of sampled and quantized pixel values, the higher density of pixel values referred to as mixels,

(iii) aligning the interpolated prototype scan with a selected pixel scan of the remaining pixel scans,

(iv) adjusting the aligned interpolated prototype scan mixel values by minimizing an error cost function representative of a difference measure between a selected pixel of the selected pixel scan and a pixel value computed from the mixel values of the interpolated prototype scan using the scanner means PSF to produce a computed pixel value from the interpolated prototype scan mixel values, for producing a modified prototype scan, and the means for adjusting the aligned interpolated prototype scan mixel values including means for

(aa) forming overlapping cluster zones from contiguous prototype mixel elements contained within a rectangular array;

(bb) forming an associated mixel zone vector, one vector associated with each overlapping cluster zone, having elements corresponding to the prototype scan mixel values included within the associated overlapping cluster zone,

(cc) forming a zone matrix, each row having elements representative of known PSF values, which when multiplied by the associated mixel zone vector produces a vector of pixel value representative of the pixel elements included within the associated overlapping cluster zone, and

(dd) sequentially solving for each associated mixel zone vector using any overlapping elements of the associated mixel zone vector, as obtained, for updating the prototype scan mixel values; and

(v) repeating the use of the means for aligning the interpolated prototype scan and the means for adjusting the aligned prototype scan for each of the non-selected remaining pixel scans using the modified prototype scan as the interpolated prototype scan so that after all remaining pixel scans are processed, the modified prototype scan is an enhanced resolution raster scan image of the original image.

14. The system of claim 13 further comprising means for perturbing the scanner by introducing offset errors in order to ensure adequate variety in each raster scan representation of the original image for efficient reconstruction of an enhanced resolution scan image using a minimum number of raster scans for a given level of enhancement.

15. The system of claim 14 wherein the offset errors are of a known form.

16. The system of claim 15 wherein the numerical processor further comprises means for removing the offset errors of a known form from each of the multiplicity of pixel value sets.

17. The system of claim 13 wherein the means for adjusting the aligned interpolated prototype scan mixel values minimizes the error cost function by an iterative gradient descent algorithm.

18. The system of claim 13 wherein the means for aligning the interpolated prototype scan with a selected pixel scan is performed by minimizing a distance metric representative of the difference between the selected pixel scan and corresponding mixel values of the interpolated prototype scan.

19. The system of claim 18 wherein the distance metric is a quadratic distance metric.

20. The system of claim 18 wherein the distance metric is based on the absolute difference between the selected pixel scan and corresponding mixel values of the interpolated prototype scan.

21. The system of claim 18 wherein the means for aligning the prototype scan with a selected pixel scan is performed by maximizing a two-dimensional cross-covariance function.

22. An image enhancement processor system for use with a destination facsimile receiver for producing an enhanced resolution image from a multiplicity of received lower resolution sampled and quantized raster scanned images, each sampled and quantized raster scan image represented by a pixel value set, the image enhancement processor system comprising:

(a) a memory for temporary storage of the multiplicity of pixel value sets; and

(b) a numerical processor coupled to the memory for access to the stored sets of pixel value sets, for storing of processed pixel values, and for executing a stored image resolution enhancement program the numerical processor including means for,

(i) selecting one of the multiplicity of pixel value sets as a prototype scan from memory, the non-selected pixel value sets referred to as remaining pixel scans,

(ii) interpolating the prototype scan pixel values to produce an interpolated prototype scan with a higher density of sampled and quantized pixel values, the higher density of pixel values referred to as mixels,

(iii) aligning the interpolated prototype scan with a selected pixel scan of the remaining pixel scans,

(iv) adjusting the aligned interpolated prototype scan mixel values by minimizing an error cost function representative of a difference measure between a selected pixel of the selected pixel scan and a pixel value computed from the mixel values of the interpolated prototype scan using the scanner means PSF to produce a computed pixel value from the interpolated prototype scan mixel values, for producing a modified prototype scan, and the means for adjusting the aligned interpolated prototype scan mixel values including means for

(aa) forming overlapping cluster zones from contiguous prototype mixel elements contained within a rectangular array;

(bb) forming an associated mixel zone vector, one vector associated with each overlapping cluster zone, having elements corresponding to the prototype scan mixel values included within the associated overlapping cluster zone,

(cc) forming a zone matrix, each row having elements representative of known PSF values, which when multiplied by the associated mixel zone vector produces a vector of pixel value representative of the pixel elements included within the associated overlapping cluster zone, and

(dd) sequentially solving for each associated mixel zone vector using any overlapping elements of the associated mixel zone vector, as obtained, for updating the prototype scan mixel values; and

(v) repeating the use of the means for aligning the interpolated prototype scan and the means for adjusting the aligned prototype scan for each of the non-selected remaining pixel scans using the modified prototype scan as the interpolated prototype scan so that after all remaining pixel scans are processed, the modified prototype scan is an enhanced resolution raster scan image of the original image.

23. The image enhancement processor system of claim 22 wherein the means for adjusting the aligned integrated prototype scan mixel values minimizes the error cost function by an iterative gradient descent algorithm.

24. The image enhancement processor system of claim 22 wherein the means for aligning the interpolated prototype scan with a selected pixel scan in performed by minimizing a distance metric representative of the difference between the selected pixel scan and corresponding mixel values of the interpolated prototype scan.

25. The image enhancement processor system of claim 22 wherein the means for aligning the prototype scan with a selected pixel scan is performed by maximizing a two-dimensional cross-covariance function.

26. A method for producing an enhanced resolution image from a multiplicity of lower resolution raster scan images produced by a scanner with known point-spread-function (PSF), each represented by a set of uniformly sampled and quantized pixel values, the method comprising the following steps:

(a) storing the multiplicity of lower resolution raster scan images;

(b) selecting one of the multiplicity of pixel value sets as a prototype scan from memory, the non-selected pixel value sets referred to as remaining pixel scans,

(c) interpolating the prototype scan pixel values to produce an interpolated prototype scan with a higher density of sampled and quantized pixel values, the higher density of pixel values referred to as mixels,

(d) aligning the interpolated prototype scan with a selected pixel scan of the remaining pixel scans,

(e) adjusting the aligned interpolated prototype scan mixel values by minimizing an error cost function representative of a difference measure between a selected pixel of the selected pixel scan and a pixel value computed from the mixel values of the interpolated prototype scan using the scanner means PSF to produce a computed pixel value from the interpolated prototype scan mixel values, for producing a modified prototype scan, the steps of adjusting the aligned interpolated prototype scan mixel values including

(i) forming overlapping cluster zones from contiguous prototype mixel elements contained within a rectangular array,

(ii) forming an associated mixel zone vector, one vector associated with each overlapping cluster zone, having elements corresponding to the prototype scan mixel values included within the associated overlapping cluster zone,

(iii) forming a zone matrix, each row having elements representative of known PSF values, which when multiplied by the associated mixel zone vector produces a vector of pixel values representative of the pixel elements included within the associated overlapping cluster zone, and

(iv) sequentially solving for each associated mixel zone vector using any overlapping elements of the associated mixel zone vector, as obtained, for updating the prototype scan mixel values; and

(f) repeating the use of the step for aligning the interpolated prototype scan and the step for adjusting the aligned prototype scan for each of the non-selected remaining pixel scans using the modified prototype scan as the interpolated prototype scan so that after all remaining pixel scans are processed, the modified prototype scan is an enhanced resolution raster scan image of the original image.

27. The method of claim 26 wherein the known point-spread-function (PSF) is estimated from any known physical characteristics of the scanner.

28. The method of claim 26 further comprising:

scanning an original image more than once with a scanner having a known point-spread-function (PSF); and

perturbing the scanner with offset errors of known form.

29. The method of claim 28 further comprising the step of removing any known offset errors from the multiplicity of stored lower resolution raster scan images.

30. The method of claim 29 wherein the step of adjusting the aligned interpolated prototype scan mixel values minimizes the error cost function by use of an iterative gradient descent algorithm.

31. The method of claim 28 wherein the step of perturbing the scanner with offset errors are fixed horizontal and vertical displacements, respectively, that differ for each raster scan.

32. The method of claim 26 wherein the step for aligning the interpolated prototype scan with a selected pixel scan is performed by minimizing a distance metric representative of the difference between the selected pixel scan and corresponding mixel values of the interpolated prototype scan.

33. The method of claim 26 wherein the step for aligning the prototype scan with a selected pixel scan is performed by maximizing a two-dimensional cross-covariance function.

34. A method for reconstructing often used characters from raster scanned documents containing multiple examples of the often used characters, the method comprising the following steps:

(a) raster scanning at least one document containing multiple examples of each character to be reconstructed using a scanner with known point-spread-function (PSF) and producing a uniformly sampled and quantized pixel raster scan;

(b) storing each scanned pixel raster scan;

(c) selecting a set of scanned exemplars of a given character from one or more pixel raster scan;

(d) selecting one of the set of scanned exemplars as a prototype of the given character;

(e) interpolating the prototype of a given character to produce a high resolution mixel image of the prototype;

(f) aligning the interpolated prototype with a remaining scanned example of selected set of scanned exemplars of the given character;

(g) adjusting the aligned interpolated prototype mixel values by computing a pixel value using the known PSF as a convolution kernel and comparing the computed pixel value with the corresponding pixel value of the scanned example of the given character for producing an updated prototype character with improved resolution;

(h) repeating steps (f) and (g) for all secured examples selected in step (c); and

(i) using the updated prototype character, after all scanned exemplars selected in step (c) are processed in steps (f) and (g) as the reconstructed given character.

35. The method of claim 34 wherein the known PSF is estimated from any known physical characteristics of the scanner.

36. The method of claim 34 further comprising thresholding of the reconstructed given character for producing a sharpened character image.

37. The method of claim 34 wherein the step of raster scanning further comprises introducing tracking errors to ensure adequate variety in each raster scan of the original image for efficient reconstruction of an enhanced resolution raster scan image.

38. The method of claim 34 wherein the step of adjusting the aligned interpolated prototype mixel values uses an iterative gradient descent algorithm.

39. The method of claim 34 wherein the step of adjusting the aligned interpolated prototype mixel values comprises adjusting the aligned interpolated prototype scan mixel values by minimizing an error cost function representative of a difference measure between a selected pixel of the selected pixel scan and a pixel value computed from the mixel values of the interpolated prototype scan using the scanner PSF to produce a computed pixel value from the interpolated prototype scan mixel values, for producing a modified prototype scan, the steps of adjusting the aligned interpolated prototype scan mixel values including:

(a) forming overlapping cluster zones from contiguous prototype mixel elements contained within a rectangular array;

(b) forming an associated mixel zone vector, one vector associated with each overlapping cluster zone, having elements corresponding to the prototype scan mixel values included within the associated overlapping cluster zone;

(c) forming a zone matrix, each row having elements representative of known PSF values, which when multiplied by the associated mixel zone vector produces a vector of pixel values representative of the pixel elements included within the associated overlapping cluster zone; and

(d) sequentially solving for each associated mixel zone vector using any overlapping elements of the associated mixel zone vector, as obtained, for updating the prototype scan mixel values.