Table of Contents: |
|
|
Purpose |
|
In 2005,
the document handling was a $19 billion industry (from IDC), but,
(from ImageTag) "Current paper-to-digital solutions capture less
than 1% of the paper headed for the file cabinet." Digital documents
have cost, access, speed, organization, durability, efficiency,
environmental, competitive, discovery, and other compelling
advantages over paper documents, but conventional technology will
offer either a good image or compression but not both simultaneously
which leaves no feasible solution. In this paper, we will analyze
and demonstrate the methods needed to get both quality images and
unprecedented compression at the same time. |
|
|
Introduction |
|
Paper-based filing systems are several thousand years old and found
in every office across the world, yet digital documents could exude
many clear advantages over paper-based filing systems if they
simultaneously exhibited good compression and quality images.
|
|
|
| 1. |
Cost: Digital documents
are nearly free, and they are getting cheaper with each
passing day. Hard and other disk drives keep increasing in
capacity, but their prices remain the same. With state of the
art compression, such as Pac-n-Zoom®, a 10 page document only
requires about 10 KBytes which is 1 KByte per page. A 250
GByte hard drive currently costs about $80.00. Then, 1 page
can be stored for 80.00 / 250G * 1K = 32 millionths of a cent,
and it can be backed up for much less than that. By
comparison, it costs about .8 cents for the paper and another
2.4 cents for the ink to print a sheet of paper. This means
that it costs about (.8 + 2.4) / .000032 or 100,000
times as much to print a page as it does to write it to a
disk. Copying all of these papers takes an average of 3% of
all revenue generated by US businesses. If we assume 20%
margins, then office copies cost us 15% of our income. Besides
having numerous other competitive advantages, digital
documents are much cheaper.
|
| 2. |
Access: The value of a
document is realized when someone views it. The cost of
copying a digital document is less than a billionth of a cent,
and the copies can be simultaneously shipped at the speed of
light to most places in all 7 continents. With the mobile and
far-flung work force of today, it is increasingly unlikely
that the needed document will be in the same office as the
employee who needs it. There are many times when files need to
viewed by people outside the company. Digital storage can
provide cheap and manageable access to the IRS, SEC, or civil
subpoenas. By providing access to vendors and other
outsourcing agents, many processes can be optimized. Digital
documents can be served to almost anyone in anyplace for next
to nothing.
|
| 3. |
Speed: Any accountant can
tell you that time is money. In a well designed system it
takes less than two seconds to click on a link and retrieve a
digital document, but on the average, it takes about 20
minutes to search, retrieve, deliver, and re-file a document.
There is no need to put the digital document back. When these
facts are taken together, digital files are about 600 times
faster then paper files even when paper files are in an ideal
setting which is an increasingly bad assumption. Faster access
equals a quicker response to the customer's needs which
translates to greater profits.
|
| 4. |
Organization: Even if a
filing clerk is able to label the files in a way that the
files can be found, there is almost no chance that the
appropriate and necessary cross-references are included. Very
few documents have the luxury of starting at the beginning and
telling the whole story through to the finish. Most documents
are a thread in a tapestry of thought, and without the
appropriate cross references, most paper documents are out of
context. The author of a digital document can link in cross
references, and the organization is not left to the filing
clerk who probably doesn't know what they should be. Without
these vital links, 60% of employees waste more than 60 minutes
each day by duplicating work that has already been done (from
www.openarchive.com). Paper files are so much trouble that the
average disorganized office manager has 3,000 documents just
"lying around" (from a study by US News and Report). The costs
from late fees, premium prices, and other chaos expenses can
eat up to 20% of the entire budget. 80% of a company's
information exists as unstructured data that is scattered
throughout the enterprise (from KMWorld). The paper files are
ironically the most disorganized part of many organizations.
Digital files are easier to find, integrate, and organize.
|
| 5. |
Durable: (From
World-scan.com) "More than 70% of today's business would fail
within 3 weeks if they suffered a catastrophic loss of
paper-based records due to fire or flood." For their part,
digital documents tend to survive these unforeseen events. For
example, nearly all the paper documents were lost but almost
all the digital documents survived the World Trade Center
tragedy. It doesn't take a catastrophe to lose paper. 22% of
all documents get lost and 7.5% are never found which wipes
out 15% of all profits. For their part, digital files are not
normally removed from the filing cabinet which dramatically
reduces the chance of losing the document.
|
| 6. |
Efficiency: In many
cases, it easier to outsource some corporate function than it
is to "reinvent the wheel" in-house. The primary problem of
small companies (according to the Boulder County Business
survey of companies in Boulder County) is the handling of
government paperwork. The second largest problem these
companies have (according to the same survey) is the handling
of personnel. A company could specialize in handling of
government paperwork or personnel issues and be far more
efficient than everyone doing the same things paperwork
themselves, but the specialized companies would need access to
the necessary files which digital files allow. Digital files
allow managers to easily verify the existence and accuracy of
all the paper trails which is nearly impossible with paper
files. In these and many other ways, digital files make a
company much more efficient than paper files.
|
| 7. |
Environmental: In 1993 US
businesses used 2 million tons of copy paper, and in 2000 this
waste grew to 4.6 million tons or more than 92 billion sheets
of paper (Document Magazine). Since it takes 17 trees to make
a ton of paper, the US used 78 million trees worth of paper in
2000. To make matters worth, the use of paper is constantly
and quickly increasing. As shown above, the use of paper more
than doubled within 7 years, and paper already accounts for
40% of the municipal solid waste stream. Digital copies leave
almost no environmental scars.
|
| 8. |
Competitive: A winning
team plays together. While businesses increasingly organize
and automate around the computer, paper documents resist
efforts to increase productivity. When a company automates
paper processes, they gain a clear advantage over their
competitors. Competitive companies are trying to move faster.
For example, law firms manage millions of pages of documents,
and it is imperative to a court case that the right documents
and case files are available to the right person at the right
time. To quote Ali Shahidi of Alschuler, Grossman, Stein, and
Kahan LLP, a Santa Monica law firm, "We're doing things we
couldn't have imagined a few years ago. We're smarter, better,
and more nimble." At the present time, 99% of the paper
documents can not be analyzed, automated, and organized by a
computer. The paper part of the office is a remnant from the
last century, and it doesn't allow a company to move forward
with the modern techniques of the information age.
|
| 9. |
Discovery: As the
Internet has proven, digital information is the easiest
information to find. In a typical office, if an important
document is viewed by an employee, there is significant chance
that the document will be lost forever. The average white
collar worker spends 1 hour each day looking for lost
documents (from Esselte). Since digital documents are not
removed from the filing cabinet, they are unlikely to be lost.
The searcher may not know what label the file was filed under.
With the ability to contain links, digital documents are
easier to cross reference and maintain context. The text of
most digital documents can be recognized by the computer which
allows the searcher to search for phrases inside the document.
Digital documents are easier to find than paper files because
digital documents are unlikely to be lost and digital text is
searchable by a computer.
| |
|
|
Paper-based filing systems are several thousand years old and found
in every office across the world, yet digital documents could exude
many clear advantages over paper-based filing systems if they
simultaneously exhibited good compression and quality images.
As we have shown, digital files have many
advantages over paper, but only about 1% of the files in the filing
cabinet have been digitized. With current technology, it is not
practical to digitize a large percentage of the documents. Users can
get a good image (e.g., JPEG) or good compression (e.g., TIFF G4), but they can not get both a high
quality image and small file size at the same time.
If the text is big and black and if the
paper is clean and white (with no writing), a threshold segmenter followed by a statistical compressor, such as TIFF
G4, yields file sizes that are useable (if not a little annoying) on
a LAN. Threshold segmentation is not
the, "silver bullet" people need, and the files image to a FAX-like
quality. If we were looking at the yellow carbon copy of a receipt,
much of the information would be lost. With threshold segmentation,
TIFF G4 has adequate compression but poor image quality.
JPEG has moderately good image quality
because it skips segmentation altogether, and simply
performs a discreet cosine transform (with huffman encoding) on the image. The
quality comes with a price. Since all the noise is left in the
image, the compression is relative small. The user will have to wait
long times for the file to serve, transmit, and load. If the file
was being transmitted over the Internet, the user could easily be
waiting 10s of seconds to view a single page. Without segmentation,
JPEG has a good image but poor compression.
To move the files from the filing cabinet
to the computer, we need a solution that has both a good image and
high compression. |
|
|
Human-Like
Segmentation |
|
Threshold segmentation is usually not
good enough to handle the spectrum of document needs a business has.
For example, a common receipt might have
blue printing on yellow paper with a red number in the upper
right-hand corner. It is not uncommon for some of the blue printing
to be very fine while the issuing company's name is in big bold
print. People often write and stamp on the receipt. The colors they
use don't have to conform to those on the receipt. The receipt might
be a carbon copy with the attendant image degradation. The handling
of the receipt might be an issue. It might have gotten dirty or
crumpled, and these are only a small sample of image degradation
possibilities.
A simple receipt can
challenge the computer's ability to store the image without loss
while achieving useable compression, and there are many applications
(such as X-rays, drawings, and others) that are even more difficult.
Threshold segmentation is fast and easy,
but the quality of segmentation often falls short of what
is needed to do the job. In fact, the standard that everyone is held
to is human-like segmentation. If people can't see what is on the
receipt, then the receipt carries the blame.
Few things shed blame as well as humans.
A compression project with less segmentation than a human will dam
the river of blame and divert it through the IT department.
Maybe the accounts payable person did
write "paid" on the invoice that was paid twice, or maybe the
necessary scrawl was omitted. Either way the computer will be blamed
if it has a reputation for missing such things. To avoid all of
these accusations, the document imaging system needs to
segment like a human (or better).
This
means that threshold segmentation is not good enough except in
certain conditions where image quality can be guaranteed. In fact,
the only acceptable segmentation for most of the paper in the office
is human-like segmentation. Humans set the standard.
When the computer industry started moving
paper documents onto the computer, segmentation was used to create a
higher contrast (or sharper) image. A segmented image is more easily
compressed, because there are fewer artifacts to compress.
Segmentation removes many small defects (we call noise) out of the
picture.
These are all convenient reasons
to use segmentation, but unlike our conventional document imaging
methodology, humans require segmentation to achieve extraction.
When we use our senses to perceive something, we are actually
performing several steps. Since we use our senses so much, these
steps have become second nature to us, and may even be performed in
the subconscious.
The first step, which
we call segmentation, is that of grouping like shades together. Let
us use a black letter 'e' on a white background as an example. The
black would probably be many different shades up and down the 'e'
(here is a typical example of a black 'e' scanned
from a white sheet of paper), but we would need to group all of them
together before we could recognize the letter 'e'.
While segmentation might seem as if it
adds artificiality to the picture, recognition requires
segmentation. In other words, if we want the picture to mean
anything to us, we will have to segment it in our head.
The process of finding a shape (or any feature) of an object is called
extraction. The extracted shape is compared to memory (probably a
database but isn't necessarily limited to template matching). If we can match
the shape to a shape stored in memory, we recognize the shape. In
our example, the segmentation must bring the "e" in as a single region, or we will extract a shape not
recognized by the database. In other words, when parts of a letter
are missing, it is difficult to identify the partial letter.
The document imaging industry's use of
segmentation to achieve OCR extraction is similar, but threshold
segmentation is often a fatal shortcut that prevents robust
extraction. For example, a computer can not perform OCR extraction
with the accuracy a human can in a multiple color environment.
As computers get stronger, they can
afford to forsake threshold segmentation for the more robust edge
detection segmentation that is more intelligent and human-like.
A computer with intelligent human-like
segmentation isn't limited to more accurate extraction. As the
computer begins to aggregate the image through edge detection
segmentation, it can also achieve much better compression than it
could with threshold segmentation.
To
understand how these things occur, let's backtrack to explain the
details of each type of segmentation.
|
|
|
Threshold
Segmentation |
|
Threshold segmentation is the simplest
type of segmentation. In a simple example, if we had black text on
white paper, we could set the threshold to gray. All of the text
that is darker than the gray threshold would be considered black,
and any background that was lighter than the gray threshold would be
considered white. When the segmentation is complete, there are two
colors in the picture.
Threshold
segmentation can be much more complicated than this. For example, a
histogram of colors could be taken
across a region or an entire picture. The more
predominant colors can be considered the foreground and background.
The threshold could be set at the middle color between the
foreground and background colors. Of course as threshold
segmentation becomes more complicated, it runs slower.
In a standard 8.5 inch by 11 inch sheet
of paper scanned in at 300 dots per inch with all three primary colors, we have 8.5 * 11 * 300
* 300 * 3 or 25,245 KBytes of data, if we assume 8 bits
per primary color. Even today's computers take a noticeable amount
of time to chew through 25 MBytes of data. Therefore, threshold
segmentation (typically a simple variety) is usually used.
Threshold segmentation should be
considered a fast but coarse segmentation. Threshold segmentation
does not address a number of segmentation problems required by
human-like segmentation.
For example, transition distortions are usually the
largest distortion introduced by a scanner, and threshold
segmentation does not find or rebuild the border. In many cases, a pattern of
colors is mixed together to provide some information (for example a
logo), and threshold segmentation will not be able to sort through
the color complexities with human-like intelligence.
|
|
|
Edge Detection
Segmentation |
|
To segment like a human, the segmenter
needs to mimic the human process of edge detection segmentation. For
about 30 years, people have been trying to achieve high quality with
edge detection segmentation, but it
has only recently been accomplished.
Edge
detection segmentation does a better job of supporting image restoration. The edge of a blob is distorted in a variety of
ways, and the edge needs to be discovered before it can be restored.
In the past, most edge detection
segmentation was too coarse to be used in document imaging, but computers can
theoretically handle edge detection better than humans. Humans can
only see about 200,000 colors, but computers typically work with 16
million colors. The optoelectronic sensing technology is capable of
many more.
When the computer does a
better job of segmenting, it can do a better job compressing. If the
picture is over segmented, the baby is thrown out with the bath
water. In other words, the data washes out along with the noise.
With better segmentation, more noise can be corrected while leaving
the data.
The input distortion from the
optoelectronic capture appliance (usually a scanner) prevents high
levels of compression in color documents; so a big size and quality
difference can currently be found between color documents created on
a computer and those scanned from a paper.
For example, a scanned color document can
be compressed about 3 times with a statistical compressor, but the same
file created on the computer could be compressed about 100 times.
Furthermore, the computer generated document would be much cleaner
and clearer.
Edge detection segmentation
is a much more complicated and computer intensive segmentation
technique. At first, edge detection might seem simple, but it is
complicated be several factors.
|
|
|
| 1. |
Continuous Tone:
We may not be segmenting along a clear color transition. In fact, the
image could be continuous tone with nearly unlimited color
variations.
|
| 2. |
Image Distortion: Clear color
transitions are usually smeared 4 or 5 pixels in two directions. Finer
details become blurry, and humans are able to segment some of
this. Then the humans expect the computer to segment at human
level.
|
| 3. |
Fine Artifacts: Text (of a specific
font) comes with a finite set of artifacts, and they have a
minimum size. Artifacts below the minimum can be ignored in
text, but they must be segmented in continuous tone.
| |
|
|
As we
would expect, edge detection segmentation takes much longer than threshold segmentation.
|
| |
