Browse Prior Art Database

Fast Algorithm for Reducing a Bit Image by a Factor of Two in Both Dimensions

IP.com Disclosure Number: IPCOM000044280D
Original Publication Date: 1984-Nov-01
Included in the Prior Art Database: 2005-Feb-05
Document File: 3 page(s) / 61K

Publishing Venue

IBM

Related People

Anderson, KL: AUTHOR [+3]

Abstract

Exploiting the fact that a binary image typically includes large white areas, by omitting calculation of output halfwords when related input halfwords are all zero, using a table lookup method to remove alternate bits in the horizontal dimension, and reducing pairs of rows in the original image to single rows in the output image, provides a very fast two-dimensional 2:1 image reduction. The fast reduction algorithm quickly reduces a binary image by a factor of two, in both the horizontal and vertical dimensions, by reducing each 2 x 2 cluster of pels (picture elements) in the image to a single pel whose value is the logical OR of the four original pels. The algorithm proposed uses a novel combination of techniques to produce code which is significantly faster than current methods. These techniques include: 1.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 49% of the total text.

Page 1 of 3

Fast Algorithm for Reducing a Bit Image by a Factor of Two in Both Dimensions

Exploiting the fact that a binary image typically includes large white areas, by omitting calculation of output halfwords when related input halfwords are all zero, using a table lookup method to remove alternate bits in the horizontal dimension, and reducing pairs of rows in the original image to single rows in the output image, provides a very fast two-dimensional 2:1 image reduction. The fast reduction algorithm quickly reduces a binary image by a factor of two, in both the horizontal and vertical dimensions, by reducing each 2 x 2 cluster of pels (picture elements) in the image to a single pel whose value is the logical OR of the four original pels. The algorithm proposed uses a novel combination of techniques to produce code which is significantly faster than current methods. These techniques include: 1. Exploiting the fact that a binary image 11 typically includes large areas containing only zero (white) picture elements, by zeroing the output area for a row before calculating the values of the bits in the row, and then omitting the calculation and storage of an output halfword when the two input words used to create it both contain only zero bits. 2. Using a fast method involving a table lookup to remove alternate bits in the horizontal dimension after adjacent horizontal bits have been ORed together. Fig. 1 shows the image storage for the original and reduced images. The bits making up the original image 9 and the subimage to be reduced 11 are assumed to be stored packed eight to a byte, with each row beginning and ending on a byte boundary. The output image 10 and the reduced subimage 12 are represented in storage in the same way. The rows of the original image 9 and the output image 10 are to be arranged sequentially in storage. If the number of bytes per row in the original subimage 11 is odd, this implementation pads each row of the reduced subimage 12 on the right with four zero bits. The subimage 11 to be reduced may in fact be the original image 9; similarly the reduced subimage 12 may be the entire output image 10. A subimage 11 may be reduced in situ; this requires that the beginning 13 of the subimage 11 to be reduced be also the beginning 14 of the reduced subimage 12. Alternatively, this algorithm may be used to extract the rectangular subimage 11 and insert the reduced subimage 12 into a rectangular portion of the same image or of another image. This is done by skipping over the data in the portions of the rows of the original image 9 which are not part of the subimage 11 to be reduced, and similarly leaving an appropriate amount of space between the rows of the reduced subimage 12; in this case the implementation requires that the original 11 and reduced subimages 12 do not overlap. The procedure for reducing the image may be summarized as follows: 1. A temporary storage area is zeroed, and the first row of the reduced subimage 12 i...