Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Speeding Up Image Processing Routines by Using Special-Purpose Data Structure

IP.com Disclosure Number: IPCOM000120304D
Original Publication Date: 1991-Apr-01
Included in the Prior Art Database: 2005-Apr-02
Document File: 3 page(s) / 114K

Publishing Venue

IBM

Related People

Aronson, E: AUTHOR [+4]

Abstract

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.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Speeding Up Image Processing Routines by Using Special-Purpose Data
Structure

      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.

      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

      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

      Each block 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
location.
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
inde...