Method and apparatus for processing or resizing digital images, such as images of bar code symbols

• US 5,987,192 A
• Filed: 09/18/1997
• Issued: 11/16/1999
• Est. Priority Date: 09/18/1997
• Status: Expired due to Term

• Current Assignee: Intermec IP Corporation (Honeywell International Inc.)
• Original Assignee: Intermec IP Corporation (Honeywell International Inc.)
• Inventors: Maltsev, Pavel A., Coffman, Ken
• Primary Examiner(s): Couso, Jose L.
• Assistant Examiner(s): DESIRE, GREGORY M
• Application Number:
  US08/932,873
• Time in Patent Office: 789 Days
• Field of Search: 382/298, 382/299, 382/300, 382/176, 382/205, 382/237, 382/282, 382/318, 382/319, 235/462, 358/451
• US Class Current: 382/298
• CPC Class Codes: G06T 3/4007 based on interpolation, e.g. bilinear interpolation image demosaicing G06T3/4015; edge-driven or edge-based scaling G06T3/403

Abstract

A method and apparatus for resizing or processing images initially retrieves a one-dimensional sample of the image, such as a line of pixels. The image can be of a machine-readable symbol, or other data. A moving window having, for example, five pixels, includes a center "hard core" and four surrounding pixels. Two or more structural sets or multisets are applied to the window to produce a set of pixels greater than the set of pixels in the original image. For example, the center pixel is repeated three times, while immediately adjacent left and right pixels are repeated twice. Thus, a series of nine pixels results. The resulting nine pixels are then sorted based on descending gray scale levels. The n-th largest pixels is selected, such as the third largest. The image is updated, the window moved, and the method repeats again. Pyramid filtering, cubic convolution interpolation, or other techniques can be used to reduce the size of an image, and more complex windows and structural sets can be employed.

Claims

1. Bar code reading apparatus for imaging a data collection symbol representing encoded information, the apparatus comprising:

a sensor that receives light reflected from the symbol and produces an output signal therefrom that represents the reflectance of the bars and spaces of the symbol;

a memory for storing at least a portion of an image of the symbol, the stored image being comprised of pixels in at least one dimension, each pixel having an intensity value; and

image processing circuitry that retrieves a set of M pixels from the memory and applies an M-pixel sized window to the set of M pixels, replicates a first pixel in the set of M pixels in the window j times and replicates at least a second pixel in the set of M pixels in the window k times, sorts the M set of pixels and replicated pixels, selects an n-th largest pixel in the sorted pixels where the n-th largest pixel is not a largest pixel in the sorted pixels, stores the selected pixel in the memory, and repeatedly retrieves another set of M pixels and again replicates, sorts, selects and stores for the another set of M pixels to generate a reduced size image based on the stored image, and wherein j is greater than k, and j and k are greater than one.

2. The apparatus of claim 1 wherein the image processing circuitry includes:

a plurality of storage elements for storing the set of M pixels from the memory;

magnitude comparator circuitry coupled to the plurality of storage elements that compares magnitudes of pixel values;

replicating logic coupled to replicate selected pixels in the stored set of M pixels;

an ordered set of memory elements coupled to the replicating logic that stores the set of M pixels and the replicated pixels in order of magnitude; and

a multiplexing circuit coupled to the ordered set of memory elements that outputs an n-th largest magnitude pixel stored in the ordered set of memory elements.

3. The apparatus of claim 1 wherein the image processing circuitry includes a microprocessor that is programmed to retrieve, replicate, sort, select and store pixels.

4. The apparatus of claim 1 wherein the image processing circuitry is configured to retrieve a set of first, second, third, fourth and fifth adjacent pixels positioned along a row of the stored image, and to replicate the third pixel three times and the second and fourth pixels twice.

5. The apparatus of claim 1 wherein the image processing circuitry is configured to sort the M set of pixels and replicated pixels in descending order of intensity, determine a quality of the stored image, determine a value for n, and then select the n-th largest pixel in the sorted pixels.

6. The apparatus of claim 1 wherein the stored image includes rows of pixels, and wherein the image processing circuitry retrieves, replicates, sorts, selects and stores for each row of pixels in the stored image to produce an intermediate image having a reduced number of pixels from the stored image, and then retrieves, replicates, sorts, selects and stores rows of pixels in the intermediate image to produce a final image having a reduced number of pixels from the intermediate image.

7. The apparatus of claim 1 wherein the image processing circuitry is configured to pyramid filter the stored image to produce a final image having fewer pixels than the stored image.

8. An apparatus for processing a stored image, the stored image being comprised of a plurality of pixels and at least a portion of the image being stored in a memory, the apparatus comprising pixel analysis circuitry that retrieves a set of M pixels from the stored image and applies an M-pixel sized window to the set of M pixels, replicates a first pixel in the set of M pixels in the window j times and replicates at least a second pixel in the set of M pixels in the window k times, sorts the M set of pixels and replicated pixels, selects an n-th largest pixel in the sorted pixels where the n-th largest pixel is not a largest pixel in the sorted pixels, stores the selected pixel in the memory, and retrieves another set of M pixels and again replicates, sorts, selects and stores for the another set of M pixels to generate a reduced size image based on the stored image, and wherein j is greater than k, and j and k are greater than one.

9. The apparatus of claim 8 wherein the pixel analysis circuitry includes:

magnitude comparator circuitry coupled to receive a set of M pixels from the memory and compare magnitudes of pixel values;

replicating logic coupled to replicate selected pixels in the set of M pixels;

a series of memory elements coupled to the replicating logic that stores the set of M pixels and the replicated pixels in magnitude order; and

an output circuit coupled to the memory elements that outputs an n-th largest magnitude pixel stored in the memory elements.

10. The apparatus of claim 8 wherein the pixel analysis circuitry includes a microprocessor that is programmed to retrieve, replicate, sort, select and store pixels.

11. The apparatus of claim 8 wherein the pixel analysis circuitry is configured to retrieve a two-dimension set of adjacent pixels as a window from the stored image, and to replicate a center pixel j times and replicate pixels immediately surrounding the center pixel k times.

12. The apparatus of claim 8 wherein the pixel analysis circuitry is configured to sort the M set of pixels and replicated pixels in descending order of intensity, determine a quality of the stored image, determine a value for n, and then select the n-th largest pixel in the sorted pixels.

13. The apparatus of claim 8 wherein the stored image includes rows and columns of pixels, and wherein the pixel analysis circuitry retrieves, replicates, sorts, selects and stores for each row of pixels in the stored image to produce an intermediate image having a reduced number of pixels from the stored image, and then retrieves, replicates, sorts, selects and stores rows of pixels in the intermediate image to produce a final image having a reduced number of pixels from the intermediate image.

14. The apparatus of claim 8 wherein the stored image includes rows and columns of pixels, and wherein the pixel analysis circuitry retrieves, replicates, sorts, selects and stores for each row of pixels in the stored image, and then retrieves, replicates, sorts, selects and stores for each column of pixels in the stored image.

15. The apparatus of claim 8 wherein the pixel analysis circuitry pixel reduction filtering of the stored image to produce a final image having fewer pixels than the stored image.

16. A method of reducing the size of a stored image comprising:

storing an image, the image being comprised of a plurality of pixels;

retrieving a set of M pixels from the memory and applying an M-pixel sized window to the M set of pixels;

replicating a first pixel in the set of M pixels in the window j times and replicating at least a second pixel in the set of M pixels in the window k times;

sorting the M set of pixels and replicated pixels;

selecting an n-th largest pixel in the sorted pixels, wherein the n-th largest pixel is not a largest pixel in the sorted pixels;

storing the selected pixel in the memory;

repeatedly retrieving another set of M pixels and again performing the replicating, sorting, selecting and storing for the another set of M pixels, and wherein j is greater than k, and j and k are greater than one; and

generating a reduced size image based on the stored image and the acts of retrieving, replicating, sorting, selecting, storing and repeatedly retrieving the selected pixel.

17. The method of claim 16 wherein the selecting includes alternatively selecting the n-th largest pixel and a (n-1)-th pixel.

18. The method of claim 16 wherein the choosing includes retrieving a set of first, second, third, fourth and fifth adjacent pixels positioned along a row of the stored image, and wherein the replicating includes replicating the third pixel three times and the second and fourth pixels twice.

19. The method of claim 16 wherein the sorting includes sorting the M set of pixels and replicated pixels in descending order of intensity, and wherein the selecting includes determining a quality of the stored image, determining a value for n, and then selecting the n-th largest pixel in the sorted pixels.

20. The method of claim 16 wherein the stored image includes rows of pixels, and wherein the retrieving, replicating, sorting, selecting and storing are performed for each row of pixels in the stored image to produce an intermediate image having a reduced number of pixels from the stored image, and then the retrieving, replicating, sorting, selecting and storing are performed for rows of pixels in the intermediate image to produce a final image having a reduced number of pixels from the intermediate image.

21. The method of claim 16 wherein the stored image includes rows and columns of pixels, and the retrieving, replicating, sorting, selecting and storing are performed for each row of pixels in the stored image, and then the retrieving, replicating, sorting, selecting and storing are performed for each column of pixels in the stored image.

22. The method of claim 16, further comprising the pyramid filtering the stored image to produce a final image having fewer pixels than the stored image.

23. The method of claim 16 wherein the acts are performed in the order of:

retrieving, replicating, sorting, selecting and storing.

24. A computer implemented method of processing a stored image, the stored image being comprised of a plurality of pixels, the method comprising:

choosing a set of M pixels from the memory and applying an M-pixel sized window to the M set of pixels;

replicating a first pixel in the set of M pixels in the window j times and replicating at least a second pixel in the set of M pixels in the window k times;

sorting the M set of pixels and replicated pixels;

selecting an n-th largest pixel in the sorted pixels, wherein the n-th largest pixel is not a largest pixel in the sorted pixels;

storing the selected pixel in the memory;

repeatedly choosing another set of M pixels and again performing the replicating, sorting, selecting and storing for the another set of M pixels, and wherein j is greater than k, and j and k are greater than one, and generating a reduced size image based on the stored image and the acts of choosing, replicating, sorting, selecting, storing and repeatedly choosing.

25. The method of claim 24 wherein the selecting includes alternatively selecting the n-th largest pixel and a (n-1)-th pixel.

26. The method of claim 24 wherein the choosing includes retrieving a two-dimension set of adjacent pixels as a window from the stored image, and wherein the replicating includes replicating a center pixel j times and replicate pixels immediately surrounding the center pixel k times.

27. The method of claim 24 wherein the sorting includes sorting the M set of pixels and replicated pixels in descending order of intensity, and wherein the selecting includes determining a quality of the stored image, determining a value for n, and then selecting the n-th largest pixel in the sorted pixels.

28. The method of claim 24 wherein the stored image includes rows of pixels, and wherein the choosing, replicating, sorting, selecting and storing are performed for each row of pixels in the stored image to produce an intermediate image having a reduced number of pixels from the stored image, and then the choosing, replicating, sorting, selecting and storing are performed for rows of pixels in the intermediate image to produce a final image having a reduced number of pixels from the intermediate image.

29. The method of claim 24 wherein the stored image includes rows and columns of pixels, and the choosing, replicating, sorting, selecting and storing are performed for each row of pixels in the stored image, and then the choosing, replicating, sorting, selecting and storing are performed for each column of pixels in the stored image.

30. The method of claim 24, further comprising filtering the stored image to produce a final image having fewer pixels than the stored image.

31. The method of claim 24 wherein the acts are performed in the order of:

choosing, replicating, sorting, selecting and storing.

32. The method of claim 24 wherein the choosing includes retrieving a cross-shaped, two-dimensional set of adjacent pixels as a window from the stored image.

33. The method of claim 24 further comprising the cubic convolution interpolating at least a portion of the plurality of pixels of the stored image.

34. A computer-readable medium containing instructions for causing a computer system to resize a stored image, the stored image being comprised of a plurality of pixels, the instructions causing the computer to perform a method comprising:

choosing a set of M pixels from the memory and applying an M-pixel sized window to the M set of pixels;

replicating a first pixel in the set of M pixels in the window j times and replicating at least a second pixel in the set of M pixels in the window k times;

sorting the M set of pixels and replicated pixels;

selecting an n-th largest pixel in the sorted pixels, wherein the n-th largest pixel is not a largest pixel in the sorted pixels;

storing the selected pixel in the memory;

repeatedly choosing another set of M pixels and again performing the replicating, sorting, selecting and storing for the another set of M pixels, and wherein j is greater than k, and j and k arc greater than one; and

generating a reduced size image based on the stored image and the acts of choosing, replicating, sorting, selecting, storing and repeatedly choosing.