Methods and means for image and voice compression

Claim 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 0 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 0 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 0 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 0 l-1 , corresponding within said average distortion tolerance level per data unit to said string, u 0 l-1 , and (ii) appending said new database substring, v 0 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.

Claim 2

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 0 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 0 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 0 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 0 l-1 , corresponding within said average distortion tolerance level per data unit to said string, u 0 l-1 , and (ii) appending said new database substring, v 0 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.