Browse Prior Art Database

Multi-Dimensional Run-Length Coding And Decoding of Binary Images On Mite-Like Configurable, Network Image Processing Systems

IP.com Disclosure Number: IPCOM000102450D
Original Publication Date: 1990-Nov-01
Included in the Prior Art Database: 2005-Mar-17
Document File: 5 page(s) / 247K

Publishing Venue

IBM

Related People

Jaffe, RS: AUTHOR [+4]

Abstract

Disclosed is a method for extending one-dimensional run-length encoding and decoding to multi-dimensions. This can substantially improve compression for many binary images typically encountered in industrial inspection applications and in the worst case, is at least as good as one-dimensional encoding. Also disclosed is a relatively inexpensive, straightforward and fast hardware means to implement the method on MITE-like systems (1,2).

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

Multi-Dimensional Run-Length Coding And Decoding of Binary Images On Mite-Like Configurable, Network Image Processing Systems

       Disclosed is a method for extending one-dimensional
run-length encoding and decoding to multi-dimensions.  This can
substantially improve compression for many binary images typically
encountered in industrial inspection applications and in the worst
case, is at least as good as one-dimensional encoding.  Also
disclosed is a relatively inexpensive, straightforward and fast
hardware means to implement the method on MITE-like systems (1,2).

      There are many forms of one-dimensional run-length encoding,
all functionally equivalent to the approach shown in the figure
above.  At A in the figure there is a binary image, a nine by nine
matrix of binary valued elements or pixels, five by five of which are
ON.  The ON pixels labelled I are a pixel run, more particularly a
row run, being adjacent in the X or row direction.  In image B the ON
pixels labelled J each have an OFF pixel as their left neighbor.
Similarly the OFF pixels labelled o have left neighbors which are ON.
Pixels J and o pixels are  the ON and OFF transition pixels,
respectively.  The transition pixels constitute the transition image,
image C.  The set of paired numbers indicating the matrix row and
column index of each transition pixel is the transition set.  For
example the transition set of A is (3,3)(8,3)(3,4)(8,4),...,(8,7).
Any image can be converted into a set of paired indices for the ON
pixels.  Such a set will be called a point set. Generalizing from the
horizontal to the vertical direction, the binary image of A is
labelled in D to show the ON and OFF column transition pixels as T
and q, respectively.  An image transformation such as one producing C
given A is known as a transform function.  The process of producing a
transition or point set from the transition or isolated pixel image
is done by an enumerate function.

      One-dimensional encoding is a one-to-one transformation
(loss-less encoding) of a binary image to a transition set whose
elements are the coordinates of all transition pixels in the image.
It achieves compression because images of interest typically contain
only a few regions, each one consisting of a relatively large
proportion of row runs greater than a few pixels.

      One-dimensional run-length decoding is the functional inverse
of encoding.  It regenerates a binary image from its associated
transition set.  Decoding is composed of two steps, denumerate and
fill.  The denumerate function is the inverse of the enumerate
function.  Given an element (i,j) in a transition set or point set,
denumerate creates an ON pixel at the i,j index location.  The fill
function recreates each run from a transition image by turning ON all
pixels in the row including the ON transition pixel up to but not
including the OFF transition pixel.

      The above discussion assumes for convenience an...