Methods and means for image and voice compression

• US 5,836,003 A
• Filed: 12/13/1996
• Issued: 11/10/1998
• Est. Priority Date: 08/26/1993
• Status: Expired due to Term

• Current Assignee: Amstr Investments 2 KG LLC (Intellectual Ventures LLC)
• Original Assignee: Visnet Ltd.
• Inventors: Sadeh, Ilan
• Primary Examiner(s): Williams, Howard L.
• Application Number:
  US08/763,376
• Time in Patent Office: 697 Days
• Field of Search: 341/51
• US Class Current: 341/51
• CPC Class Codes: H03M 7/3084 using adaptive string matching, e.g. the Lempel-Ziv method

Abstract

A system for lossy compression of digital data for transmission to a remote location or to a storage medium and subsequently reconstructing the digital data includes an encoder which compares sequences of characters with an encoder database of data records to generate a compressed code. The compressed code includes pointer information relating to locations within the encoder database of data records corresponding within a given average distortion tolerance level per character to the sequences, and update information for the addition to the encoder database of new data records corresponding within the average distortion tolerance level per character to the sequences. The system also includes a decoder for receiving the compressed code, the receiver processing the compressed code to substantially reconstruct the digital data.

Claims

1. A method for lossy compression of source data for transmission to a remote location or to a storage medium, the source data being made up of data units u_i from a first alphabet U, a string of the source data units u_i to u_j being denoted u_i^j, the source data units being mappable on to code data units v_i of a second alphabet V, there being defined a distortion measure d(u_i,v_i) indicative of the distortion caused by encoding source data unit u_i as code data unit v_j, the method comprising the steps of:

(a) inputting a string of l source data units, u₀^l-1 ;

(b) searching within a database, v_-n^-1, starting from v_-l^-1, for a database substring, v_-p^-p+l-I, corresponding within a given non-zero average distortion tolerance level per data unit to said string, u₀^l-1 ;

(c) in a case that such a said database substring is found;

(i) transmitting a compressed data signal indicative of;

(A) the finding of said database substring, and

(B) the position of said database substring within said database, and

(ii) appending said database substring to said database as v₀^l-1, and re-indexing said database; and

(d) in a case that no such said database substring is found;

(i) transmitting a compressed data signal indicative of;

(A) the non-finding of a said database substring, and

(B) a new database substring, v₀^l-1, corresponding within said average distortion tolerance level per data unit to said string, u₀^l-1, and

(ii) appending said new database substring, v₀^l-1, to said database and re-indexing said database,

wherein said new database substring is selected by use of a block-coding algorithm subject to a fidelity criterion, said block-coding algorithm being based on information about a frequency distribution of the source data, said information being built up empirically from the source data.

2. The method of claim 1, wherein the method is repeated, l being chosen randomly for each repetition.

3. The method of claim 1, wherein the method is repeated, l remaining constant between repetitions.

4. The method of claim 1, wherein said database is of finite length L, such that the step of appending said new database substring, v₀^l-1, to said database and re-indexing said database includes the discarding of a substring v_-L^-L+l-1 corresponding to the l oldest data units of said database.