Browse Prior Art Database

Document Processing Using Bit Matrix Transposition

IP.com Disclosure Number: IPCOM000118026D
Original Publication Date: 1996-Aug-01
Included in the Prior Art Database: 2005-Mar-31
Document File: 4 page(s) / 157K

Publishing Venue

IBM

Related People

Chevion, DS: AUTHOR [+2]

Abstract

Document processing, including Optical Character Recognition (OCR), involves manipulation of 2_D binary images (bitmaps). Bitmap manipulation has also an important role in Fax machines in the inspection industry and many other applications. Most applications are too demanding for general purpose personal computers and require the installation of special hardware (like DSS or other adaptors) to speed up the processing. Such a solution might be unacceptably expensive, especially when many users are involved.

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

Document Processing Using Bit Matrix Transposition

      Document processing, including Optical Character Recognition
(OCR), involves manipulation of 2_D binary images (bitmaps).  Bitmap
manipulation has also an important role in Fax machines in the
inspection industry and many other applications.  Most applications
are too demanding for general purpose personal computers and require
the installation of special hardware (like DSS or other adaptors) to
speed up the processing.  Such a solution might be unacceptably
expensive, especially when many users are involved.

      Many of the functions required for manipulation of 2D bit
images are separable, which means that they can be performed as two
one dimensional functions, separately on rows and columns.  Even for
non-separable functions, 1D approximation can be found in most
cases.  While bit operations on rows can be done quite efficiently on
general purpose computers using some known "tricks" (see below),
operations on columns are too clumsy.  The reason is that computers
do not support direct operations on single bits.  The solution
described below allows efficient operation on columns, making
implementation of separable functions very efficient.  Implementation
requires a very minor  hardware addition, estimated at 5% of a
standard shift-rotate unit.

      Usually a byte (8-bit) is the smallest addressable unit as well
as the smallest operand of an instruction.  Operating on bytes or
multiples of them (half-words, words, double words) is native and so,
relatively fast.  Some operations on bit data can be performed
efficiently if an operation is applied to the whole byte as a unit.
For example, rotating a byte aligned bit string may be done byte by
byte, using 256*1 byte translation table.  If the string is not
aligned or it  is to be placed into a not aligned position, the
"trick" works, combined  with proper shifting and merging.  There is
no need to perform separate  operations on each individual bit.
Thus, moving or rotating a bitmap can be done quite efficiently on
general purpose computers.  A similar  approach may be used to
calculate the sum of bits in a string.

      However, operation on columns requires access to individual
bits.  Transposing the required rectangle of an image makes the work
on columns as simple and efficient as on rows.  Unfortunately, bit
matrix transposing itself is a very slow operation.  It is done by
building the transposed matrix bit by bit, while inserting each
single bit in a proper position may require up to 3-4 instructions:
SHIFT to the required byte offset, AND with a mask and OR with the
result (the last may require a byte aligning shift before ORing).  In
addition, updating of various counters and loop closing branch
instructions are required.  As a result, transposing bit matrices
needs more time than transposing of byte or even matrices of integers
of the same size, though an integer matrix occupies 32 t...