Speeding Up Image Processing Routines by Using Special-Purpose Data Structure
Original Publication Date: 1991-Apr-01
Included in the Prior Art Database: 2005-Apr-02
Aronson, E: AUTHOR [+3]
This article relates to a process of: preprocessing scanned input data to create an indexed data structure; processing the data in that structure, and re-creating the standard raster form.
Speeding Up Image Processing Routines by Using
relates to a process of: preprocessing
scanned input data to create an indexed data structure; processing
the data in that structure, and re-creating the standard raster form.
Proposed is a
two-layer indexing structure for files so that
only a single byte will be required for each index producing a
compact file form. Files can be transformed to a second form with
the indices expanded to an integer number (2 bytes or more). A
vector of pointers to the starting points on each line is provided.
This redundant information gives a convenient random-access point to
each line of the image. Improvement in the processing time of
various binary image processing applications results. A background
knowledge of efficient image processing, data compression techniques,
and paperless office systems is assumed.
Essential Elements of the Algorithm
consists of four stages as follows.
1. Block Segmentation
The image is
partitioned into mutually exclusive blocks having
256x256 pixels. If actual image size does not fit into an integer
number of blocks, it is padded with zeros for translation purposes.
Since the image header contains the size of the original image, the
original can be easily retrieved from individual block images.
2. Block Orientated Transformation
code is preceded by a vector of pointers having 256
entries - one for each line of the image. Each entry contains the
number of black sections (the number of runs of "1's"). Since each
line can have only up to 128 sections, a single byte suffices for
each entry or 256 bytes for the entire vector. To such a pointer
vector, index information is concatenated. The program traverses the
image line by line and writes down locations of the "start" and "end"
points of each segment. When block size has been reduced to 256
columns, a single byte only is required in order to express each
3. Performing Processing on the Transformed Data
In order to
avail of the proposed technique, all the data
processing must be adapted accordingly. Since the proposed approach
is well suited for a variety of binary image processing kernels, this
can be done efficiently. Examples are as follows:
* Performing Boolean operations on two images (such as logic "OR",
logic "AND" or logic "XOR") depends on relative locations of the
"start" and "end" points, and as a result the number of computations
involved is proportional to the number of sections, which is much
smaller than the number of pixels.
* Performing logical negation requires, basically, only shift in