Note: Descriptions are shown in the official language in which they were submitted.
~ 131~2
DQCUMENT IMAGE PROCESSING SYSTEM
Field and Backqround of the Invention
This invention relates to the high speed
processing of documents, such as bank checks, and more
particularly to a system and method for the high speed
capturing, processing and storage of video image data
from documents.
Documents such as bank checks are
conventionally processed on a high speed reader/sorter
which operates at a relatively high rate of speed on the
order of about 2400 documents per minute. As the
documents are proaessed through the reader/sorter, they
are directed past an MICR reader which reads the
magnetic ink characters on the documents. The documents
may also be directed pàst a microfillning station which
microfilms both the front and back of the document. The
document is subsequently sorted into one of a number of
output bins. In order to be sure that a legible image
of the documents was captured on microfilm, it is
necessary to hold the documents until the microfilm has
been removed rom the machine and developed, which could
take as long as several days. However, in the case of
bank checks, the financial institutions desire to
process and forward the checks as quickly as possible to
reduce the "float time". Consequently, the institutions
are faced with releasing and forwarding the documents
CT9-86-009 ~
, .
.,.t 1 31 4~2
--2--
before they have obtained con~irmation that the
microfilming was successful, or holding the documents
until the microfilm has been developed and incurring the
added cost associated with this delay.
In order to overcome this problem, it has been
proposed that the images on the documents be captured
electronically rather than on microfilm, using video
imaging technology. However, until now this approach
has been technologically infeasible, due to the high
volume~of documents which must be processed and the
large amount of video image data which is required to
~reproduce the images on the documents. ~Indeed, a recent
study conducted by the Federal Reserve Bank concluded
that the high speed capture and storage of video image
data from bank checks is infeasible with existing video
processing technology.
To obtain a high quality image, it is
desirable to use a relatively high resolution, of for
example, 240 pels per inch. In order to acceptably
reproduce high contrast information surh as numbers and
signatures, as well as lower contrast information such
as stamps and endorsements, the image needs to be
captured at a high resolution in a mlmber of levels of
gray. To capture gray scale data for each side of a
bank check at 240 pels per inch resolution and 256 gray
levels would re~lire 1.48 megabytes of video image data.
Thus, to support the processing of checks at a feed rate
of 40 documents per second would require the handling of
approximately 118 megabytes of video image data per
second.
- It will thus be readily appreciated that the
high speed processing of video image data from checks
generates extremely high volumes of video image data.
To be able to handle data at this high volume for a
sustained period of time presents very significant
CT9-86-009 _
.~
1 3 1 ~q~2
--3--
technological challenges. Furthermore, since a document
processing system employing this technology would need
to provide storage for the oheck images over extended
periods of time ranging from days to months or even
years, significant challenges are also presented in
providing a feasible way to store and retrieve massive
amounts of video image data. Whila the image data could
theoretically be stored on high speed mass data storage
devices, such as magnetic DASD (Direct Access Storage
Device~, the cost of this type of storage becomes
prohibitive when considering the volume requirements for
oseveral months or even days worth of check image data.
While optical storage devices are available which
. . ~ . .
provide a lower cost alternative to mass data storage,
the data transfer rates for the presently available
optical data storage devices are considerably slower
than the data transfer rate of magn~tic DASD and would
be incapable of accepting the video image data at the
rate at which it is being generated, even if
sophisticated and powerful data compression techniques
are employed.
With the foregoing in mind it is an important
object of the present invention to provide a system and
method which enables the high speed capture, processing
and storage of video image data from documents, such as
bank checks.
A further object of the invention is to
provide a system which can provide these capabilities at
an economically feasible cost.
Because of the very high rate of dzta capture
- and storage, it is important to provide an assurance
that the video image data which is being captured from
the documents is of a quality sufficient for reproducing
an acceptable quality image of the document. In
particular, it would be desirable to have the capability
CT9-86-009 _~
r 1 3 1 4 q 8 2
--4
to monitor image quality on a real time basis so that
corrective actions can ~e taken immediately if the
images captured from the documents are of unacceptable
quality. Thus, still another object of the invention is
to provide a system and method of the type described
which provides for real time monitoring of image qualîty
so that appropriate corrective action can be taken
immediately if the image quality from the documents
becomes unacceptable.
~` Summary of the Invention
These and other objects, features, and
-advantages of the present invention are~achieved by a
unique image processing system architecture and related
method, as hereinafter more fully described.
In one of its aspects, the image processing
system of the present invention includes a document
transport for transporting a series of successive
documents along a predetermined path, and a document
scanner cooperating with the transport for optically
scanning the successive documents andl for converting
optically perceptible images on the clocuments into video
image data. The video image data from the scanner is
compressed by data compression teGhniques, and the
compressed data is sent over a high speed data channel
to a high speed mass data storage device which receives
and temporarily stores the compressed video image data.
The high speed mass data storage device may, for
example, comprise a direct access magnetic storage
device. A relatively lvwer speed mass data storage
device, such as an optical disk, is connected for
- receiving at a lower data transfer rate the compressed
video image data from the high speed data storage device
and for storing the video image data for subsequent
retrieval. In a preferred embodiment, the document
transport comprises a high speed document reader/sorter
CT9-8S-009 _
.. 1 3 1 4q82
--5--
which is capable of transporting documents therethrough
at a relatively high rate in excess of 1,000 documents
per minute.
The system preferably also includes a pre-
channel data buffer connected between the datacompression device and the high speed data channel for
receiving and buffering the flow of data to the high
speed data channel. The buffer serves to avoid loss of
data in the event that the rate of data transfer from
the da~a compression device temporarily exceeds the data
transfer rate of the high speed data channel.
~Additionally, the system also desirably~includes a post-
channel data buffer connected between the high speed
data channel and the high speed mass data storage
device. The post-channel data buffer serves for
receiving and buffering the flow of data to the high
speed mass data storage device to avoid loss of data in
the event that the rate of data transfer from the high
speed data channel temporarily exc~eds the rate at which
the high speed mass data storage device can accept data.
For scanning banX checks, the document scanner
is constructed for optically scanning both the front and
the back of each document. The high speed data storage
device, as well as the low speed data storage device,
store video image data for both the front and the back
of each document. The video image data which is
captured by the document scanner is directed to an image
processor which converts the scanner data into digital
high resolution gray scale video image data. To further
reduce the volume o~ image data, the image processor
includes resolution reduction means for reducing the
digital high resolution gray scale video image data
(e.g. 240 pels per inch) into digital low resolution
gray scale video image data (e.g. 80 pels per inch), as
well as a thresholding device for converting the digital
CT9-86-009 ~
r 1 3 1 4 9 ~ 2
-6-
high resolution gray scale video image data into digital
high resolution black and white video image data. The
low resolution gray scale video image data and the high
resolution black and white video image data are then
each compressed by data compression techniques for
storage.
The present invention also provides the
capability of monitoring the quality of the images which
are captured from the documents in real time as the
documeh'ts are being processed. One real time image
quality control technique involves monitoring the degree
~of compression of the image data by the~data compression
unit. If the data compresses to a degree which falls
outside of a predetermined parameter which is indicative
of acceptable image quality, then a malfunction signal
is generated. Thus, for example, if the video image
data compresses too much, indicating that the video
image data is too sparss or non-existent, a malfunction
signal would be generated. The malfunction signal can
be utilized for immediately stopping the document
transport so as to thereby immediately halt the
generation of unacceptable quality image data from the
documents.
Another real time image quality control
technigue involves monitoring the characteristics of the
video image data and ~enerating a malfunction signal if
the video image data characteristics are outside of a
predetermined prescribed range of values which is
indicative of acceptable image quality. Thus, for
exampla, the system may monitor the distribution of gray
scale values of the digital high resolution gray scale
video image data. Acceptable quality images would have
a gray scale distribution or "histogram" within certain
prescribed limits. If the gray scale values fell
outside of these limits, this would be indicative of
CT9-86-009 _~
. .
~ 1 3 1 4 9 8 2
--7--
poor image quality and a malfunction signal is
generated. The malfunction signal may, in turn, be
utilized to immediately stop the document transport and
to thereby immediately halt the generation of
unacceptable quality image data from the documents.
To attain the necessary rate of data
throughput, several of the processing steps are
performed concurrently (for the processing of document
front and back images) and in parallel (for the
processing of all document front images or the
processing of all document back images). The number of
-parallel paths required for processing is a function of
the transport throughput rate. Thus, a`document
transport with a high throughput rate would require more
parallel processing paths than a document transport with
a lower throughput rate. This architecture allows the
same basic image scanning system to be installed on
document transports of a wide range of processing
speeds.
The processing of data through the paths is
under programmable logic control. Status of the data
processing in each path is provided t:o the control
logic. Based o~ this status, the control logic decides
which path receives the next document image to be
processed. -Thus, if the image in a particular path has
not completed processing, that path can be skipped and
the next available path will be used for processing the
image. Also, if a hardware malfunction is detected in a
particular processing path, that path can be skipped by
the control logic until it has been repaired (the
throughput of the document transport will be decreased
due to the loss of the processing path but use of the
system is not lost - the user can still pxocess
documents at a slower rate rather than loosing full use
of the image processing system).
CT9-86-009
~ 131~9~2
-8-
The system employs a series of parallel
processing paths for processing document ~ront images
and a second series of parallel processing paths for
processing document back images. Thus, for example, thP
system may employ a plurality of image processing units
functioning in par~llel for simultaneously processing
image data from the ~ront and back of documents.
Brief Descri~tion of the Drawinqs
Some of the features and advantages of the
invent~on having been sta~ed, others will become
apparent from the detailed description which follows and
~from the accompanying drawinys in whic~--
Figure 1 is a schematic functional diagram of
the video image processing system of this invention,
Figure 2 is a schématic system diagram showing
in more detail image scanning and compression subsystem,
and
Figure 3 is a schematic system diagram of the
image processing and compression units.
Descri~tion of Illustrated ~mbodiment
The document image processing system of the
present invention may utilize a comm~ercially available
high speed document reader/sorter such as the IBM 3890
reader/sorter for handling documents at a high rate o~
speed on the order of about 2400 documents per minute.
A document reader/sorter of this type is indicated
schematically in Figure 1 by the reference character 10,
and includes a control unit 11 which may be operatively
connected in a known manner to other components 12 of a
check processing system. The reader/sorter includes a
document feed 13, typically including a hopper for
receiving a supply of documents and a feed mechanism for
directing the successive documents from the hopper to a
document transport 14. As the documents are transported
through the reader~sorter by the transpoxt 14, they may
CT9-86-009 ` _,
1 31 4982
g
be directed past an MICR module 15 which reads
information encoded on magnetic ink characters on the
documents. The documents may also be directed past an
optional microfllm module 16 where images of the front
and back of each document are captured by microfilm.
The documents are ultimately transported to a stacker 17
which may include a series of output bins into which the
documents are sorted. All of the foregoing components
are conventionally provided in a high speed document
reade~sorter. In accordance with the present invention
an image scanner 20 is incorporated in the reader/sorter
~in lieu of or in addition to the micro~ilm module so
that as the documents flow through the reader, the front
and back surfaces of the documents are scanned and
optically perceptible information contained on the
clocuments is transformed into video image data. The
image scanner 20 may, for example, comprise a charge
coupled device (CCD) scanner array which generates a
sequence of analog values representing light and dark
areas defining the image on the document. As shown in
Figure 2, the image scanner 20 includes a front scanner
20a and a back scanner 20b arranged for simultaneously
scanning both the front and the back of the documents.
The scanner arrays 20at 20b are connected respectively
to analog to digital converters 2~a, 21b-which convert
the analog values into discrete binary gray scale
values, of for example, 256 gray scale levels.
As represented in Figure 1 at 23, the high
resolution gray scale image data from the scanner is
directed to an image data preprocessor in which the
image data may be enhanced and/or smoothed, and which
also serves to locate the edges of successive documents
and discard irrelevant data between documents. If the
documents are slightly skewed, the image preprocessor 23
CT9-86-009 -j~
1 31 49~2
--10--
can perform rotation on the image data to facilitate
subsequent processing.
The characteristics of the video image data
are monitored for unacceptable image quality as
indicated at 24, and if necessa~y, the document
transport operation may be altered or stopped to prevent
the capturing of bad image data. For example, the image
quality unit 24 may monitor the distribution of gray
scale values in the image data and create a "histogram".
Exper~nce has shown that acceptable quality images
would have a distribution of gray scale values within
-certain prescribed limits. If the gray~ scale
distribution of the histogram fell outside of these
prescribed limits, this would be indicative of poor
image quality and a malfunction signal is generated.
The malfunction signal may in turn be u~ilized to stop
the document transport, as represented by the control
signal line 24a in Figure l. Following image quality
monitoring, the image data is subjected to image da~a
reduction and compression techniques as indicated at 26
to thereby reduce the image data bandwidth and storage
requirements. The compressed image data is thereafter
transferred over a high speed data channel 30 for
temporary storage on an image buffer 40. The image
buffer 40 may comprise a high speed magnetic disk
storage unit.
The amount of video image data per document
may vary depending upon the size and nature of the
document and the efficiency of the data compression and
reduction for tha~ particular document~ To insure that
no data is lost in the event that the volume of image
data may temporarily exceed the transfer capacity of the
high speed data channel 30, a pre-channel buffer 28 is
interposed prior to the data channel 30. The capacity
of the pre-channel buffer is continually monitored and
CT9-86-009
1 31 ~9~2
as indicated at 29, inEormat,.ion regarding the capacity
of the pre-channel buffer is routed back to the document
feed 13 and document transport 14 so that appropriate
action can be -taken~ if necessary, to avoid overfilling
of the pre-channel buffer and loss of video image data.
This function is descri.becl more :E~llly in commonly
owned U.S. Patent number 4, 8a8 ~ 8:L2 issued on December
19, -L989 . Reference may be made -to khis U.S. Patent
fcr a more detailed explanation o.E the pre-channel
buffer monitoring and contro]. functions.
Image data from the high speed data channel 30
is read into a post-channel buffer 32. Image data from
the post-channel buffer 32 is ultimately received by the
central processing unit of a host computer,
represented in Figure 1 by the reference character 50.
The input and output data channels associated with the
processor 50 are indicated broadly at 52.
The compressed vldeo lmage data which ls received over
the high speecl data channel 'lO is initially routed by
an image buffer data channel 5~a to the image buffer
40 for temporary storage. The image buffer 40 is preferably
of a size capable of storing the image data
from at least several batches or runs of checks, and
most de~irably would he capab].e of holding and storing
several days worth of image da-ta. The post-channel
buffer 32 functions to prevent any loss of data
in the event that the rate of data transfer over the
high speed data channel 30 may temporarily exceed the
capacity o:E the image buEfer 40 or image buffer data
channel 52 to recei.ve and handle data.
At convenient times, such as during periods of low
processlng demancls, the records Erom the image
buffer 40 are transferred t.o a slower speed longer term
CT9- 86- 009
1 31 4')82
-12-
image storage device 54, such as optical disks. As
represented in Figure 1, this transfer of image data is
achieved by reading the records from the image buffer ~0
over the image buffer data channel 52a to the central
processor 50 which, in turn, directs the data via image
storage data channel 52c to the image storage unit 5~.
The video processing system also employs a
number of image workstations for retrieval of the
captured video image data. One such image workstation
is rep~resented in Figure 1 at 60 and includes an imaye
display device 61 such as a CRT screen, as well as an
~image printer 62. Records from either ~he image buffer
40 or from the image storage unit 54 can be retrieved by
an image workstation 60 via an image retrieval data
channel 52d. ~rO facilitate retrieval of the images, the
image buffer 40 and the image storage unit 54 may
include suitable indexes. Thus, for example, the images
may be indexed by the se~uence number assigned to the
documents at the time of scanning.
To accommodate the high sustained volumes of
data generated in the document processing system, the
architecture of this system employs multiple identical
parallel paths for the image data flow. Thus, as best
seen in Figure 2, image data from th~ front scanner 20a
and from the back scanner ~Ob flow along parallel data
paths for simultaneous processing. An image analysis
unit 70 associated with each data path samples the
digitized video data as it is transferred into each
image preprocessing and compress.ion unit 74. By
comparing each pel's value to a predetermined threshold
value, the pels associated with the document image can
be distinguished from those of the unneeded video region
surrounding and between the documents~ The boundary
locations for the document edges are determined, and the
locations of these boundaries are passed to the image
CT9-86-009 _~
Ot
1 3 ~ ~9~2
-13-
preprocessing and compression units. The image analysis
unit also monitors the characteristics of the video
image by generating a histogram of the pel values in the
image. The histogram is then compared to the histograms
of known modes of ~ailure, such as those for an image
too dark, an image too light, and faulty scanner output.
The results of this comparison can be used to generate a
malfunction signal to an operator so the appropriate
repair action can be taken.
~ As seen in Figure 2, the data from the front
and back scanners is handled in a substantially
~identical fashion. For each data path there is provided
a series of image processing and compression units 74.
The programmable process control logic 71 determines
which unit 74 is to be loaded with a document image and
monitors the processing of image data through all image
processing and compression units. If a particular unit
74 is busy or not functional, that unit can be skipped
and the next available unit will be Loaded with the
document image. The number of image processing and
compression units required for attaining the necessary
image processing throughput rate is determined by the
document transport throughput rate - the higher the
document transport throughput rate, the more image
processing and compression units required. The
processed and compressed image data from the respective
image processing and compression units is then directed
to the pre-channel buffer 28 and thereafter to the high
speed data channel 30.
Figure 3 shows the operation of the image
processing and compression units in greater detail.
Each such unit 74 includes a raw image data buffer 75
into which the image data is initially written. An edge
discard and rotation module 76 is associated with the
raw image data buffer. The document location parameters
CT9-86-009 ~
. .
1 31 49~2
-14-
determined by the imaye analysis unit 70 are transerred
to the edge discard ancl rotation module 76. The parameters
are used for generating the address of each pel on the
document as stored in -the raw image data bu~fer 75. The
edges of the image arouncl the document are discarded by not
addressing these pels, such that on].y pels detarmi.ned to be
part of the document s image are add.ressed. Each addressed
pel is transferred out of the raw image data b~ffer 75 for
black and whi-te thresholding 77 and gray scale resolution
reduction 78. As the pels are accessed, they are addressed
in a manner which follows along the edges of the image in
memory. This has the effect of rotating the image so that
when the image is later displayed, i-t will appear squarely
on the desired display screen or print-out.
At this point, a further reduction ln the volume of
image data i.s achieved by creating two separate
versions of the image data for storage, a full
resolution black and white imal~e and a lower resolution
gray scale image. This approach y.ields significant
data reduction and maintalns both yood high contrast
definition for sharp lines and st-.rokes, and good quality
soft edged faint de~inition or endorsement stamps,
background signatu.res and the .l.ike. These -two separate
images can ba later comhinecl with a suitable mixing
algorithm to produce a reconstructecl high resolution
gray scale video image data. One suitable method for
recombining the separate forms of image is described in
commonly owned U.S. :Patent Nc>. 4,888,812 issued on
December 19, 1989.
Again referring to Figure 3, the high resolution gray
scale image data is converted to black and white binary
image data at the capture resolution by a black an~ white
thresholding unit 77. This enables
CT9-86-009
~;
1 31 4982
-15-
the data ~or each picture element (pel) to be stored in
a bit instead of a ~yte required for the 256 level gray
scale representation. The black and white thresholding
is done using dynamic or adaptive thresholding that
tracks and corrects for background shading and
determines if a pel should be black or white. This
adaptive thresholding provides a comparison of a pels
gray-scale value with those of its neighbors and adopts
a Laplacian edge enhancement approach. A nonlinear
adapti~e rate factor will also be used to provide
additional noise rejection.
~ Determination of the binary output decision is
based on whether the pel under consideration is
significantly blacker than its surroundings. The
surrounding area to be considered will be at least as
large as a printed or stamped character that is being
discriminated against its background. A single pass,
running average approach to generate the background
value is preferred. If the contrast ratio of the
character to the background is high, then the threshold
level will be increased by an additional amount to
reduce "noise" ~rom dirt, smudges, background printing,
etc. The average must adapt quickly after leaving a
very dark character so that a following lighter
character will not be eliminated. Use of a nonlinear
update ratio (or weighting value for the average) allows
the average to adjust rapidly to large high contrast
signals and to have a tendency to follow the blacker
peaks of the stroke pels.
~he high resolution gray scale image data from
- the raw image data buffer 75 is also directed to a gray
scale resolution reduction unit 78. A lower resolution
gray scale image will be generated by the resolution
reduction unit by averaging contiguous groups of higher
resolution pels. For example, the resolution may be
CT9-86-009 _
~ p
-16- 131 a9~2
reduced by one third from 240 pels per inch to 80 pels
per inch. In this instance, each low resolution pel
covers a 3 x 3 pel area and hence its gray scale value
is computed by averaging the gray scale values of the 9
corresponding high resolution pels.
The originally captureà gray scale values were
represented by one byte values able to represent 256
distinct gray levels. The data volume may be further
reduced ~y using only half a byte per pel (~ bits)
rather`-than a full byte, allowing the storage of 16
distinct levels of gray ~cale values. These distinct
~values will be uniformly spread over the 0-255
originally gray scale values.
The reduced resolution gray scale image data
and the thresholded black and white image data are ea~h
directed to respective image compression units 80, 81.
Suitable data compression units have been developed
which are capable of relatively rapid rates of data
compression on the order of about 5 megabytes per second
employing known compression techniques such as one
dimensional, modified Huf~man coding, two dimensional,
modi~`ied xead coding with programmab:Le R-parameter, and
adaptive arithmetic coding. The thus compressed low
resolution gray scale image data and high resolution
black and white image data are directed to the pre-
channel buffer 28 along data channel 30 for subseguent
separate storage and retrieval.
CT9-86-009
