Image analysis – Image compression or coding – Lossless compression
Reexamination Certificate
2000-12-20
2003-04-15
Tran, Phuoc (Department: 2621)
Image analysis
Image compression or coding
Lossless compression
C382S246000, C382S119000, C382S187000, C382S232000, C382S233000, C382S235000, C382S245000
Reexamination Certificate
active
06549675
ABSTRACT:
FIELD OF THE INVENTION
The present invention is directed to methods and apparatus for compression of digital information, for uses such as digital ink and electronic images, as well as more generalized compression and reconstruction applications.
BACKGROUND OF THE INVENTION
Recently, there has been an explosion in the market for very small computer devices that are highly portable, pocketable or even wearable. Entering textual information into these devices, however, is a challenge. Because of their small size, many of these devices cannot support a full keyboard. A natural way to enter information into such a small device is by using an electronic digitizer such as a pen or stylus to write data directly on the display of the computer. A small computer that interprets handwriting input via a pen is often referred to as a “pen-based” computer. As shown in
FIG. 1
, a pen-based computer system
10
includes a display
12
and a writing instrument, such as a pen
14
or stylus. A user can input information by “writing” directly on the display
12
. In a typical pen-based computer system
10
, the user touches the pen
14
to the display
12
and writes as if on a piece of paper—that is, by making a series of pen strokes to form letters, words, drawings or other patterns. A resulting line or curve appears on the display
12
, following the path of travel of the pen point so that the pen strokes appear on the display
12
as digital “ink” just as handwritten ink would appear on a notebook page. Thus, by digital ink, it is meant the dynamic trace produced by the user when using a writing device to enter information into a computer device, such as a pen-based computer. A pen-based computer system
10
may capture digital ink in the form of one or more strokes. A stroke is a line or curve between the point where the tip of the stylus makes contact with the writing surface and the point where the tip of the stylus leaves the writing surface. Typically, the pen based computer system
10
digitizes the position of pen
14
or stylus as a function of time to create a digital ink vector.
The pen-based computer system
10
typically samples points along each handwritten stroke at a predetermined sampling frequency. Pen-based computer systems may typically sample handwritten data at a rate of up to 200 sampled points per second. If the computer sampling rate is constant, the number of sampled points along a stroke varies inversely with the speed with which the graphic data is handwritten: the faster the handwriting, the fewer the number of sampled points along the stroke; and the slower the handwriting, the greater the number of sampled points along the stroke. Further, the higher the sampling rate, the greater the number of sampled points per stroke, and the lower the sampling rate, the fewer the number of samples points per stroke. For example, at a sampling rate of 100 points per second, stroke
42
in
FIG. 2
contains 1000 sampled points if it takes the user one second to write. A typical page of digital ink may contain hundreds of strokes and tens of thousands of sampled points.
The pen-based computer system
10
includes a central processing unit (CPU) that receives the sampled points as a data stream and stores the points in memory, such as dynamic random access memory (DRAM) as shown in FIG.
3
. The points may be further processed by software routines stored in flash memory as shown in FIG.
3
. Further, the pen-based computer system is often wirelessly connected to a host computer system such that the digital ink may be transmitted from the pen-based computer
10
to the remote computer. If the digital ink is transmitted as generated by the pen-based computer
10
, then a large number of sampled points need to be transferred. For example, in uncompressed form, the 1000 sampled points of stroke
42
in
FIG. 2
comprises 4000 bytes, where each point is represented as 4 bytes.
A particular problem with having such large data streams is that the memory storage requirements are large. Being able to compress the digital ink allows for less memory to be utilized in the pen-based computer system. This in turn, allows for the pen-based computer system to be designed and manufactured smaller. Thus, it would be desirable for a pen-based computer system to store digital ink efficiently and thus operate free of excessive memory. Another problem with large data streams is that it takes longer to transmit to a remote computer, particularly when using low-bandwidth communication channels such as wireless modems. Generally, transferring digital ink or other image data across a wireless link may take a significant amount of time, which becomes a “bottleneck”, or limiting factor for the system performance. Waiting for the system fully render and transfer the ink may impede or interrupt the user's work flow or train of thought, or may be simply frustrating and irritating to the user. Thus, it would be desirable for a pen-based computer system to transmit digital ink efficiently and thus operate more quickly.
To reduce the size of the data stream, pen-based computers may perform compression on the sampled points of the digital ink to compactly represent the data. It is known in the art to store compression software in a pen-based computer system and have the CPU execute the software to perform compression of the data stream. If the digital ink when captured by the display takes X bytes of storage in Cartesian or vector coordinates, compression will reduce the X bytes to C*X bytes where C<1. C represents the compression ratio, or amount of compression performed by the compression software. Thus, if C=0.50, then a captured digital ink of 1000 bytes may be reduced to 500 bytes by performing compression on the captured data stream.
The compressed data stream will eventually be decompressed, perhaps by decompression software executed by the remote computer. Ideally, the decompressed data stream will be the same as the captured data stream. If it is the same, then the compression routine is termed “lossless compression;” that is, the compression involved no loss of information. However, if the decompressed data stream is different, even slightly different, than the captured data stream, the compression routine is termed “lossy compression.” Some information was “lost” during compression and so the captured data stream could not be recovered exactly.
Some applications require that the compression be performed losslessly. For example, a pen-based computer used in commercial transactions may require that signatures transmitted to facilitate credit card payments be transmitted losslessly. Understandably, a merchant and customer may demand that signature verification be performed with the highest respect for integrity of the data stream and that no information be lost during compression. In contrast, the transmission of animated cartoons may be performed in a lossy manner. Even though the original data stream is not faithfully recovered or extracted, the user of the pen-based computer may not care and may tolerate the loss of information.
U.S. Pat. No. 6,011,873 to Desai, et al. (Penware, Inc.) describes a compression algorithm for lossless compression of signature data. The Desai algorithm computes the differential between consecutive points in a data stream to achieve compression. This algorithm discards duplicate data points and achieves some compression of the captured data stream for certain types of digital ink. Only discarding duplicate data points and only taking the differential between consecutive points limits the amount of compression that is achieved. If the consecutive points in the data stream are not highly correlated (e.g., such as with jittery handwritten lines, computer images or graphic animations), then using the Desai algorithm to perform compression produces a compressed data stream which is not optimally compressed, and may even be larger than the captured data stream.
Improved compression systems and methods would be desirable, particularly for very small portable device
Alavi Amir
Motorola Inc.
Watanabe Hisashi D.
LandOfFree
Compression of digital ink does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Compression of digital ink, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Compression of digital ink will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3097822