Image reduction/enlargement technique

• US 5,740,285 A
• Filed: 01/29/1993
• Issued: 04/14/1998
• Est. Priority Date: 12/08/1989
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Davies, Daniel, Bloomberg, Dan S.
• Primary Examiner(s): Razavi, Michael T.
• Assistant Examiner(s): CHANG, JON CARLTON
• Application Number:
  US08/010,825
• Time in Patent Office: 1,901 Days
• Field of Search: 382/47, 382/55, 382/44, 382/257, 382/299, 382/298, 382/308, 345/129, 345/127, 395/102, 395/139, 358/451, 358/528
• US Class Current: 382/299
• CPC Class Codes: G06T 3/4023 based on decimating pixels or lines of pixels; based on inserting pixels or lines of pixels

Abstract

In brief, a method of reducing an M X N input binary image (M rows of N pixels each) by a factor of m vertically and n horizontally includes the steps of performing at least one logical operation between bits in consecutive groups of m adjacent rows to provide a resultant single row for each group of m rows, and performing at least one logical operation between bits in consecutive groups of n adjacent columns to provide a resultant single column for each groups of n columns. For certain types of reductions, the resulting reduced image will be the desired output image, while for other types, the resultant image will be one of a required plurality of intermediate images, which are then combined to provide the desired output image.

Claims

1. A method of reducing a binary input image to a binary reduced image, via one or more intermediate images, each intermediate image being of the same size as the reduced image and being produced by operating on the input image, wherein the input image includes non-overlapping subregions, each subregion having m rows of n pixels, each subregion corresponding to a respective pixel in the reduced image, the pixel in the reduced image corresponding to a given subregion in the input image being ON if and only if the number of ON pixels in the given subregion is no less than a designated threshold value, the threshold value being greater than 1 and less than mn, the method comprising the steps of:

performing a set of logical operations between the rows of the input image or one of the intermediate images, designated row operations; and

performing a set of logical operations between the columns of the input image or one of the intermediate images, designated column operations;

wherein at least one of the column and row operations is a logical AND and at least one of the column and row operations is a logical OR;

the sets of column and row operations depending on the values of m, n, and the threshold value, and resulting in the reduced image.

2. The method of claim 1 wherein said step of performing column operations includes the use of a lookup table.

3. A method of reducing a binary input image to a binary reduced image, via one or more intermediate images, each intermediate image being of the same size as the reduced image and being produced by operating on the input image, wherein the input binary image includes non-overlapping subregions, each subregion having m rows of n pixels, each subregion corresponding to a respective pixel in the reduced image, the pixel in the reduced image corresponding to a given subregion in the input image being ON if and only if the number of ON pixels in the given subregion is no less than a designated threshold value, the threshold value being greater than 1 and less than mn, the method comprising the steps of:

performing a set of operations between the rows of the input image or one of the intermediate images, designated row operations; and

performing a set of operations between the columns of the input image or one of the intermediate images, designated column operations;

wherein at least one of the column and row operations is a logical AND and at least one of the column and row operations is a logical OR; and

wherein said step of performing column operations includes the step of performing a particular column operation on a particular image, the particular image being the input image or one of the intermediate images, the step of performing the particular column operation on the particular image including the substeps of

copying a part of a row of the particular image,

shifting the copy of the part of the row of the particular image,

logically combining the part of the row and the copy of the part of the row, so shifted, and

extracting a subset of the bits representing a part of the image resulting from performing the particular operation on the particular image and corresponding to the part of the row of the particular image;

the sets of column and row operations depending on the values of m, n, and the threshold value, and resulting in the reduced image.

4. The method of claim 3 wherein said substeps are performed in special-purpose hardware.

5. A method of reducing a binary input image to a binary reduced image wherein the input image includes non-overlapping subregions, each subregion having m rows of n pixels, each subregion corresponding to a respective pixel in the reduced image, the pixel in the reduced image corresponding to a given subregion in the input image being ON if and only if the number of ON pixels in the given subregion is no less than a designated threshold value, the threshold value being greater than 1 and less than mn, the method comprising the steps of:

producing a plurality of intermediate images, each intermediate image being of the same size as the reduced image and being produced by operating on the input image, the step of producing a particular one of the intermediate images including the substeps of

performing a set of operations consisting solely of logical operations between all the rows in consecutive groups of m adjacent rows in the input image to produce a smaller image having a number of rows reduced by a factor of m, and

performing a set of operations consisting solely of logical operations between all the columns in consecutive groups of n adjacent columns in the smaller image to produce the intermediate image having a number of columns reduced by a factor of n; and

performing at least one logical operation between the intermediate images to obtain the reduced image;

the sets of operations between rows, the sets of operations between columns, and the at least one logical operation between the intermediate images depending on the values of m, n, and the threshold value, and resulting in the reduced image.

6. The method of claim 5 wherein said step of performing column operations includes the use of a lookup table.

7. The method of claim 5, wherein:

m is equal to 4;

n is equal to 4;

the threshold value is equal to 11;

said step of performing a set of logical operations between all the rows in each consecutive group of m adjacent rows in the input image comprises;

(a) ORing the first row of the group with the second row of the group;

(b) Oring the third row of the group with the fourth row of the group;

(c) ANDing the result of step (a) with the result of step (b);

(d) ORing the first row of the group with the fourth row of the group;

(e) ORing the second row of the group with the third row of the group;

(f) ANDing the result of step (d) with the result of step (e); and

(g) ORing the result of step (c) with the result of step (f) to obtain a row in the smaller image corresponding to the group of four rows in the input image; and

said step of performing a set of logical operations between all the columns in each consecutive group of n adjacent columns in the smaller image comprises;

(h) ANDing the first column of the group with the second column of the group;

(i) ORing the third column of the group with the fourth column of the group;

(j) ANDing the result of step (h) with the result of step (i);

(k) ORing the first column of the group with the second column of the group;

(l) ANDing the third column of the group with the fourth column of the group;

(m) ANDing the result of step (k) with the result of step (1); and

(n) ORing the result of step (j) with the result of step (m) to obtain a column in the particular intermediate image corresponding to the group of four columns in the smaller image.

8. The method of claim 5, wherein the substep of performing a set of operations consisting solely of logical operations between all the rows is performed prior to the substep of performing a set of operations consisting solely of logical operations between all the columns.

9. The method of claim 5, wherein the substep of performing a set of operations consisting solely of logical operations between all the rows is intermingled with the substep of performing a set of operations consisting solely of logical operations between all the columns.

10. A method of reducing a binary input image to a binary reduced image wherein the input image includes non-overlapping subregions, each subregion having m rows of n pixels, each subregion corresponding to a respective pixel in the reduced image, the pixel in the reduced image corresponding to a given subregion in the input image being ON if and only if the number of ON pixels in the given subregions is no less than a designated threshold value, the threshold value being greater than 1 and less than mn, the method comprising the steps of:

producing a plurality of intermediate images, each intermediate image being the same size as the reduced image, the step of producing a particular one of the plurality of intermediate images including the substeps of

performing a set of logical operations between the rows of the input image to obtain a smaller image, each row of the smaller image corresponding to a respective group of m adjacent rows in the input image, and

performing a set of logical operations between the columns of the smaller image to obtain the particular intermediate image, each column in the particular intermediate image corresponding to a respective group of n adjacent columns in the smaller image; and

performing at least one logical operation between the intermediate images to obtain the reduced image;

the sets of operations between rows, the sets of operations between columns, and the at least one logical operation between the intermediate images depending on the values of m, n, and the threshold value, and resulting in the reduced image;

wherein said step of performing a set of logical operations between the columns of the smaller image to obtain the particular intermediate image includes the substeps of

copying a part of a row of the smaller image,

shifting the copy of the part of the row of the smaller image,

logically combining the part of the row and the copy of the part of the row, so shifted, and

extracting a subset of the bits representing a part of the particular intermediate image corresponding to the part of the row of the smaller image.

11. The method of claim 10 wherein said substeps are performed in special-purpose hardware.

12. A method of performing a 2×

2 reduction with a threshold of 2 on a binary input image to produce a reduced image, the method comprising the steps of;

logically ORing pairs of adjacent rows in the input image to provide a first intermediate image having a reduced number of rows;

logically ANDing pairs of adjacent columns in the first intermediate image to provide a second intermediate image having a reduced number of rows and columns;

logically ANDing pairs of adjacent rows in the input image to provide a third intermediate image having a reduced number of rows;

logically ORing pairs of adjacent columns in the third intermediate image to provide a fourth intermediate image having a reduced number of rows and columns; and

logically ORing the second and fourth intermediate images to provide the reduced image.

13. The method of claim 12 wherein each of said steps of ANDING and ORING adjacent columns includes the use of a lookup.

14. The method of claim 12 wherein said step of logically ANDING pairs of adjacent columns in the first intermediate image includes the substeps of:

copying part of a row of the first intermediate image;

shifting the copy of the part of the row;

logically ANDing the part of the row and the copy of the part of the row, so shifted; and

extracting a subset of the bits representing a part of the second intermediate image corresponding to the part of the row of the first intermediate image.

15. The method of claim 14 wherein said substeps are performed in special-purpose hardware.

16. The method of claim 12 wherein said step of logically ORing pairs of adjacent columns in the third intermediate image includes the substeps of:

copying a part of a row of the third intermediate image;

shifting the copy of the part of the row;

logically ORing the part of the row and the copy of the part of the row, so shifted; and

extracting a subset of the bits representing a part of the fourth intermediate image corresponding to the part of the row of the third intermediate image.

17. The method of claim 16 wherein said substeps are performed in special-purpose hardware.

18. The method of claim 12 wherein said step of logically ORing pairs of adjacent columns in the in the third intermediate image includes the substeps of:

copying a part of a row of the third intermediate image;

shifting the copy of the part of the row;

logically ORing the part of the row and the copy of the part of the row, so shifted; and

extracting a subset of the bits representing a part of the fourth intermediate image corresponding to the part of the row of the third intermediate image.

19. The method of claim 18 wherein said substeps are performed in special-purpose hardware.

26. The method of claim 15 wherein:

the solid 1×

2 SE has its center at the right; and

the solid 2×

1 SE has its center at the bottom; and

the predetermined position of each 2×

2 array of pixels is the upper left.

20. A method of performing a 2×

2 reduction with a threshold of 3 on a binary input image to produce a reduced image, the method comprising the steps of;

logically ORing pairs of adjacent rows in the input image to provide a first intermediate image having a reduced number of rows;

logically ANDing pairs of adjacent columns in the first intermediate image to provide a second intermediate image having a reduced number of rows and columns;

logically ANDing pairs of adjacent rows in the input image to provide a third intermediate image having a reduced number of rows;

logically ORing pairs of adjacent columns in the third intermediate image to provide a fourth intermediate image having a reduced number of rows and columns; and

logically ANDing the second and fourth intermediate images to provide the reduced image.

21. The method of claim 20 wherein each of said steps of ANDING and ORING columns includes the use of a lookup table.

22. The method of claim 21 wherein said step of logically ANDING pairs of adjacent columns in the first intermediate image includes the substeps of:

copying a part of a row of the first intermediate image;

shifting the copy of the part of the row;

logically ANDing the part of the row and the copy of the part of the row, so shifted; and

extracting a subset of the bits representing a part of the second intermediate image corresponding to the part of the row of the first intermediate image.

23. The method of claim 22 wherein said substeps are performed in special-purpose hardware.

24. A method of performing an m-by-n thresholded reduction on a binary input image to obtain a binary reduced image, the thresholded reduction being characterized by a threshold value that is greater than 1 and less than mn, the method comprising the steps of:

producing a plurality of intermediate images, each intermediate image being the same size as the input image and including one or more non-overlapping m-by-n rectangular arrays of pixels;

a particular one of the plurality of intermediate images being produced by subjecting the input image to a corresponding particular one of a plurality of sequences of morphological operations, each morphological operation in the particular one of the plurality of sequences being performed with a solid structuring element (SE);

performing at least one logical operation among the intermediate images to produce a final intermediate image; and

subsampling the final intermediate image by selecting the pixel located in a predetermined position of each m-by-n array of pixels, thereby producing the reduced image;

the plurality of sequences of morphological operations, and the at least one logical operation among the intermediate images depending on the values of m, n, and the threshold value, and resulting in the reduced image.

25. A method of performing a 2×

2 reduction with a threshold of 1 on a binary input image to obtain a binary reduced image, the method comprising the steps of;

subjecting the input image to a dilation operation with a respective solid 1×

2 horizontal structuring element (SE) having its center at a respective predetermined position to produce a resultant image;

subjecting the resultant image to a dilation operation with a solid 2×

1 vertical SE having its center at a respective predetermined position to produce an intermediate image, wherein the intermediate image comprises one or more non-overlapping 2×

2 rectangular arrays of pixels; and

subsampling the intermediate image by selecting the pixel located in a predetermined position of each array of pixels, thereby producing the reduced image.

27. A method of performing a 2×

2 reduction with a threshold of 4 on a binary input image to obtain a binary reduced image, the method comprising the steps of;

subjecting the input image to an erosion operation with a respective solid 1×

2 horizontal structuring element (SE) having its center at a respective predetermined position to produce a resultant image;

subjecting the resultant image to an erosion operation with a solid 2×

1 vertical SE having its center at a respective predetermined position to produce an intermediate image, wherein the intermediate image comprises one or more non-overlapping 2×

2 rectangular arrays of pixels; and

subsampling the intermediate image by selecting the pixel located in a predetermined position of each array of pixels, thereby producing the reduced image.

28. The method of claim 27 wherein:

the solid 1×

2 SE has its center at the left; and

the solid 2×

1 SE has its center at the top; and

the predetermined position of each 2×

2 array of pixels is the upper left.

29. A method of performing a 2×

2 reduction with a threshold of 2 on a binary input image to obtain a binary reduced image, the method comprising the steps of;

dilating the input image with a first solid 1×

2 horizontal structuring element (SE) to provide a first intermediate image;

eroding the first intermediate image with a first solid 2×

1 vertical SE to produce a second intermediate image;

eroding the input image with a second solid 1×

2 horizontal SE to produce a third intermediate image;

dilating the third intermediate image with a second solid 2×

1 vertical SE to produce a fourth intermediate image; and

logically ORing the second and fourth intermediate images to provide a fifth intermediate image, wherein the fifth intermediate image comprises one or more non-overlapping 2×

2 rectangular arrays of pixels;

subsampling the fifth intermediate image by selecting the pixel located in a predetermined position of each array of pixels, thereby producing the reduced image.

30. The method of claim 29 wherein:

the first solid 1×

2 horizontal SE has its center at the right;

the first solid 2×

1 vertical SE has its center at the top;

the second solid 2×

1 vertical SE has its center at the left;

the second solid 1×

2 horizontal SE has its center at the bottom; and

the predetermined position of each 2×

2 array of pixels is the upper left.

31. A method of performing a 2×

2 reduction with a threshold of 3 on a binary input image to obtain a binary reduced image, the method comprising the steps of;

dilating the input image with a first solid 1×

2 horizontal structuring element (SE) to provide a first intermediate image;

eroding the first intermediate image with a first solid 2×

1 vertical SE to produce a second intermediate image;

eroding the input image with a second solid 1×

2 horizontal SE to produce a third intermediate image;

dilating the third intermediate image with a second solid 2×

1 vertical SE to produce a fourth intermediate image; and

logically ANDing the second and fourth intermediate images to provide a fifth intermediate image, wherein the fifth intermediate image comprises one or more non-overlapping 2×

2 rectangular arrays of pixels;

subsampling the fifth intermediate image by selecting the pixel located in a predetermined position of each array of pixels, thereby producing the reduced image.

32. The method of claim 31 wherein:

the first solid 1×

2 horizontal SE has its center at the right;

the first solid 2×

1 vertical SE has its center at the top;

the second solid 2×

1 vertical SE has its center at the left;

the second solid 1×

2 horizontal SE has its center at the bottom; and

the predetermined position of each array of pixels is the upper left.

33. A method of performing a 2×

2 reduction with a threshold of 2 on a binary input image to produce a reduced image, the method comprising the steps of;

logically ANDing pairs of adjacent columns in the input image to provide a first intermediate image having a reduced number of rows and columns;

logically ORing pairs of adjacent rows in the first intermediate image to provide a second intermediate image having a reduced number of rows;

logically ORing pairs of adjacent columns in the input image to provide a third intermediate image having a reduced number of rows and columns;

logically ANDing pairs of adjacent rows in the third intermediate image to provide a fourth intermediate image having a reduced number of rows; and

logically ORing the second and fourth intermediate images to provide the reduced image with a threshold of 2.

34. The method of claim 33 wherein each of said steps of ANDING and ORING adjacent columns includes the use of a lookup table.

35. The method of claim 33 wherein said step of logically ANDING pairs of adjacent columns in the input image includes the substeps of:

copying a part of a row of the input image;

shifting the copy of the part of the row;

logically ANDing the part of the row and the copy of the part of the row, so shifted; and

extracting a subset of the bits representing a part of the first intermediate image corresponding to the part of the row of the input image.

36. The method of claim 35 wherein said substeps are performed in special-purpose hardware.

37. A method of performing a 2×

2 reduction with a threshold of 3 on a binary input image to produce a reduced image, the method comprising the steps of;

logically ANDing pairs of adjacent columns in the input image to provide a first intermediate image having a reduced number of rows and columns;

logically ORing pairs of adjacent rows in the first intermediate image to provide a second intermediate image having a reduced number of rows;

logically ORing pairs of adjacent columns in the input image to provide a third intermediate image having a reduced number of rows and columns;

logically ANDing pairs of adjacent rows in the third intermediate image to provide a fourth intermediate image having a reduced number of rows; and

logically ANDing the second and fourth intermediate images to provide the reduced image with a threshold of 3.

38. The method of claim 37 wherein each of said steps of ANDING and ORING columns includes the use of a lookup table.

39. The method of claim 37 wherein said step of logically ANDING pairs of adjacent columns in the input image includes the substeps of:

copying a part of a row of the input image;

shifting the copy of the part of the row;

logically ANDing the part of the row and the copy of the part of the row, so shifted; and

extracting a subset of the bits representing a part of the first intermediate image corresponding to the part of the row of the input image.

40. The method of claim 39 wherein said substeps are performed in special-purpose hardware.

41. A method of reducing a binary input image to a reduced image wherein the input image includes non-overlapping subregions, each subregion having m rows of n pixels, each subregion corresponding to a respective pixel in the reduced image, the pixel in the reduced image corresponding to a given subregion in the input image being ON if and only if the number of ON pixels in the given subregion is no less than a designated threshold value, the threshold value being greater than 1 and less than mn, the method comprising the steps of:

producing a plurality of intermediate images, each intermediate image being of the same size as the reduced image and being produced by operating on the input image, the step of producing a particular one of the intermediate images including the substeps of

performing a set of operations consisting solely of logical operations between all the columns in consecutive groups of n adjacent columns in the input image to produce a smaller image having a number of columns reduced by a factor of n, and

performing a set of operations consisting solely of logical operations between all the rows in consecutive groups of m adjacent rows in the smaller image to produce the intermediate image having a number of rows reduced by a factor of m; and

performing at least one logical operation between the intermediate images to obtain the reduced image.

42. The method of claim 41 wherein said step of performing column operations includes the use of a lookup table.

43. A method of performing an m-by-n thresholded reduction on a binary input image to obtain a binary reduced image, the method comprising the steps of:

subjecting the input image to a plurality of sequences of morphological operations, each morphological operation with a respective solid structuring element (SE), to produce a corresponding plurality of intermediate images, wherein each intermediate image comprises one or more non-overlapping m-by-n rectangular arrays of pixels;

performing at least one logical operation among the intermediate images to produce a final intermediate image; and

subsampling the final intermediate image by selecting the pixel located in a predetermined position of each array of pixels, thereby producing the reduced image, wherein one of the sequences comprises;

dilating the input image with a solid horizontal SE having its center at a respective predetermined position to produce a resultant image; and

eroding the resultant image with a solid vertical SE having its center at a respective predetermined position to produce the intermediate image.

44. A method of performing an m-by-n thresholded reduction on a binary input image to obtain a binary reduced image, the method comprising the steps of:

subjecting the input image to a plurality of sequences of morphological operations, each morphological operation with a respective solid structuring element (SE), to produce a corresponding plurality of intermediate images, wherein each intermediate image comprises one or more non-overlapping m-by-n rectangular arrays of pixels;

performing at least one logical operation among the intermediate images to produce a final intermediate image; and

subsampling the final intermediate image by selecting the pixel located in a predetermined position of each array of pixels, thereby producing the reduced image, wherein one of the sequences comprises;

eroding the input image with a solid horizontal SE having its center at a respective predetermined position to produce a resultant image; and

dilating the resultant image with a solid vertical SE having its center at a respective predetermined position to produce the intermediate image.