 |
|
|
|
|
|
 Title: |
US6798362:
Polynomial-time, sequential, adaptive system and method for lossy data compression
[ Derwent Title ]
>> View Certificate of Correction for this publication
|
| Country: |
US United States of America
|
| |
| Inventor: |
Modha, Dharmendra Shantilal; San Jose, CA
|
| Assignee: |
International Business Machines Corporation, Armonk, NY
other patents from INTERNATIONAL BUSINESS MACHINES CORPORATION (280070) (approx. 44,393)
News, Profiles, Stocks and More about this company
|
| Published / Filed: |
2004-09-28
/ 2002-10-30
|
| Application Number: |
US2002000285131
|
| IPC Code: |
Advanced:
H03M 7/30;
Core:
more...
IPC-7:
H03M 7/34;
|
| ECLA Code: |
H03M7/30Z2;
|
| U.S. Class: |
341/051;
341/050;
|
| Field of Search: |
341/051,50,67
382/040
704/260
|
| Priority Number: |
| 2002-10-30 |
US2002000285131 |
|
| Abstract: |
A system and method are provided for lossy compression of finite alphabet source sequences subject to an average-per-letter distortion constraint. The source sequence is sequentially parsed into phrases and each source phrase is mapped to a distorted phrase such that average per-letter distortion between the two phrases does not exceed the desired distortion. The present system adaptively maintains a codebook as the collection of all one-letter extensions of previously emitted distorted phrases. The present system uses approximate string matching and carries out a sequential procedure by iterating the following steps: (i) given the current codebook find the longest source phrase that can be transmitted at a given distortion, (ii) from all codewords that match the source phrase carefully choose that which is most likely to be useful in the future. For every new source phrase, the present system judiciously selects one of the many approximately matching codewords to balance between the code rate for the current phrase versus the code rate from resulting codebooks for the future source phrases. The present system outputs a distorted sequence that can be naturally losslessly compressed using the Lempel-Ziv algorithm or any variation thereof. Such judicious codeword selection is intended to iteratively improve the codebook quality. The entire present sequence can be implemented in quadratic-time in the length of the source sequence. The present system is sequential and adaptive.
|
| Attorney, Agent or Firm: |
Kassatly, Samuel A. ;
|
| Primary / Asst. Examiners: |
Young, Brian; Lauture, Joseph
|
| Maintenance Status: |
CC Certificate of Correction issued
View Certificate of Correction
|
| INPADOC Legal Status: |
Show legal status actions
Family Legal Status Report
|
| Family: |
Show 2 known family members
|
First Claim:
Show all 60 claims |
What is claimed is:
1. A lossy data compression method for converting a source sequence over a source alphabet to a distorted sequence over a reproduction alphabet by intentionally introducing errors, the method comprising:
- parsing the source sequence into a plurality of source phrases;
- mapping each source phrase to a distorted phrase of equal length and that includes a distortion that is less than an allowed per-symbol distortion budget; and
- synthesizing the distorted sequence by concatenating the distorted phrases.
|
| Background / Summary: |
Show background / summary
|
| Drawing Descriptions: |
Show drawing descriptions
|
| Description: |
Show description
|
| Forward References: |
Show 5 U.S. patent(s) that reference this one
|
|
|
|
|
|
|
| Foreign References: |
Buy
PDF |
Publication |
Date |
IPC Code |
Assignee |
Title |
| |
JP11252569
|
1999-09 |
H04N 7/32
|
|
|
|
| Other References: |
R. Zamir et al., "Towards Lossy Lempel-Ziv: Natural Type Selection," Dept. of Elect. & Comp. Eng., University of California, Santa Barbara, CA.
Y. Kochman et al., "Adaptive Parametric Vector Quantization By Natural Type Selection," Proceedings of the Data Compression Conference, Jan. 11, 2002.
Kar-Ming Cheung, et al., "A Locally Adaptive Source Coding Scheme," Communication, Control, and Signal Processing, 1990, pp. 1473-1482.
M. Atallah, et al., "A Pattern Matching Approach to Image Compression," Department of Computer Science, Purdue University, IN.
T. Berger, et al., "Lossy Source Coding," IEEE Transactions on Information Theory, vol. 44, No. 6, Oct. 1998, pp. 2693-2723.
(31 pages)
[ISI abstract]
|
|
 Nominate this for the Gallery...
|
|
