Triangle and pyramid signal transforms and apparatus

• US 4,447,886 A
• Filed: 07/31/1981
• Issued: 05/08/1984
• Est. Priority Date: 07/31/1981
• Status: Expired due to Fees

• Current Assignee: DVCS Limited Partnership
• Original Assignee: DVCS Limited Partnership
• Inventors: Meeker, G. William
• Primary Examiner(s): Atkinson, Charles E.
• Application Number:
  US06/288,936
• Time in Patent Office: 1,012 Days
• Field of Search: 364/723, 364/725, 364/727, 358/133, 358/260, 358/261, 358/263, 382/43
• US Class Current: 708/400
• CPC Class Codes: G06F 17/14 Fourier, Walsh or analogous domain transformations , e.g. Laplace, Hilbert, Karhunen-Loeve, transforms for correlation function computation G06F17/156; spectrum analysers G01R23/16
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H04N 11/044 involving transform coding
• CPC Class Codes: H04N 19/30 using hierarchical techniques, e.g. scalability H04N19/63 takes precedence
• CPC Class Codes: H04N 19/60 using transform coding

Abstract

Transform techniques for transforming numerical signal data into a transform domain and subsequent reconstruction, for purposes such as compression (bandwidth reduction) for communication or storage. The subject transforms involve several defined basis functions which operate on input data points. The basis functions of the invention are essentially weighting functions such that terms and coefficients (in the transform domain) calculated in accordance with the basis functions are each a particularly weighted average of the values of a selected consecutive plurality of input data points. An important basis function is a triangular weighting function. Successive terms and coefficients generated in accordance with each of the defined basis functions are calculated from successive consecutive pluralities of the input data points, with overlap of input data points depending on the particular basis function. The transforms are organized into a plurality of bands or levels N. Band N is the highest, and Band 1 the lowest. For forward transformation, calculation begins with the highest band, Band N, and works down. For inverse transformation (reconstruction), calculation begins with the lowest band, Band 1, and works up. Results of processing in each band are then employed as inputs for processing in the next lower band until the last band is reached. Many of the calculated coefficients have zero values, and there is also disclosed an efficient coding technique which permits the transmission of only the non-zero coefficients.

Claims

1. A transform method for operating on a one-dimensional set of input data points to provide output terms and coefficients in a transform domain organized into one or more bands, N, where N is an integer greater than zero, Band N is the highest band, and Band 1 is the lowest band, said transform method comprising:

generating and outputting at least one term for Band 1 as a B function defined as a triangularly-weighted average of the values of 2^N+1 -1 consecutive input data points;

generating and outputting coefficients for each band as predetermined functions defined as weighted averages of selected consecutive pluralities of input data points, the number of input data points contributing to each coefficient being the least for Band N, and the number of input data points contributing to each coefficient increasing by powers of two for each successive band below Band N, and the predetermined functions being selected so as to enable reconstruction of the values of the input data points from the B-function term for Band 1 and the coefficients for Bands N through 1.

2. A transform method in accordance with claim 1, comprising generating a stream of B-function terms for Band 1, with overlap of the input data points contributing to each B-function term for Band 1 such that the beginning input data point for each successive B-function term for Band 1 shifts ahead by 2^N input data points.

3. A transform method in accordance with claim 2, wherein the predetermined functions are selected so as to enable reconstruction of the values of the input data points as a build-up from Band 1 upwards of linear interpolation between B-function terms for Band 1, with departures from linear interpolation being indicated by non-zero coefficients.

4. A transform method in accordance with claim 1, which further comprises representing the values of any of the coefficients which are non-zero by means of a variable length code.

5. A transform method in accordance with claim 2, which further comprises:

outputting only coefficients having non-zero values; and

developing map components to describe the location in the transform domain of the non-zero coefficients, the map components being organized in a branched manner beginning with a plurality of map components for Band 1 and continuing with two conditionally-existing map components for successive higher bands branched from each next lower band map component, each map component corresponding to coefficients in a particular band developed from a particular plurality of input sample points, and each map component including;

a directory word,

conditionally a contents word, and

conditionally an existence word,

the directory words indicating whether a contents word is present and whether an existence word is present,

the contents words being present if there are any non-zero coefficients, and the contents words indicating which coefficients are non-zero,

the existence words being present if there are further branches, and the existence words indicating which branches are present.

6. A transform method in accordance with claim 5, which further comprises representing the values of the non-zero coefficients by means of a variable length code to further minimize the number of bits output.

7. A transform method for operating on a two-dimensional set of input data points to provide output terms and coefficients in a transform domain organized into one or more bands N, where N is an integer greater than zero, Band N is the highest band, and Band 1 is the lowest band;

said transform method comprising;

performing a first partial one-dimensional transform for Band N on either each row or each column of the input data points by a single-band triangle transform process to generate B-function terms each defined as a triangularly-weighted average of three consecutive data points, with overlap such that the last of the three data points contributing to one B-function term is the first of the three data points contributing to the next successive B-function term, and to generate coefficients as predetermined functions defined as weighted averages of selected consecutive pluralities of data points, the predetermined functions being selected so as to enable reconstruction of the values of the input data points upon completion of the entire transform method;

ordering the results of the triangle transform process on each row or each column of the data points by rows or columns, as the case may be, by band number and horizontal or vertical position, as the case may be;

performing by the triangle transform process a second partial one-dimensional single-band transform on each column or row, as the case may be, on the ordered results of the first single-band transform performed;

outputting the coefficients generated by the second one-dimensional single-band transform as two-dimensional coefficients for the band just processed;

successively repeating, for successive lower bands employing as data points the B-function terms resulting from the first and second partial one-dimensional triangle transforms of the next higher band arranged in two dimensions, the steps of performing a first partial one-dimensional triangle transform, ordering the results, performing a second partial one-dimensional triangle transform, and outputting the coefficients generated, until processing for Band 1 is completed; and

outputting the B-function term resulting from the first and second partial one-dimensional triangle transforms for Band 1.

8. A transform method in accordance with claim 7, wherein the partial triangle transform processes generate a stream of B-function terms for Band 1, with overlap of the input data points contributing to each B-function term for Band 1 such that the beginning input data point for each ensuing successive B-function term for Band 1 shifts ahead by 2^N input data points in at least one of the two directions of the two-dimensional set of input data points.

9. A transform method in accordance with claim 7, wherein the partial triangle transform processes generate a stream of B-function terms for Band 1, with overlap of the input data points contributing to each B-function term for Band 1 such that the beginning input data point for each ensuing successive B-function term for Band 1 shifts ahead by 2^N input data points in both of the two directions of the two-dimensional set of input data points.

10. A transform method in accordance with claim 7, which further comprises representing the values of any non-zero coefficients by means of a variable length code to further minimize the number of bits output.

11. A transform method for operating on a one-dimensional set of input data points to provide output terms and coefficients in a transform domain organized into one or more bands, N, where N is an integer greater than zero, Band N is the highest band, and Band 1 is the lowest band, said transform method comprising:

generating and outputting at least one term for Band 1 as a B function defined as a triangularly-weighted average of the values of 2^N+1 -1 consecutive input data points;

generating and outputting selected coefficients for each band as D-functions defined, for Band N, as a -1/4, +1/2, -1/4-weighted average of three consecutive input data points and, for all bands below Band N, as a -1/4, +1/2, -1/4-weighted average of three successive B-function terms of the next higher band, the B-function terms in turn each defined, for Band N, as a 1/4, 1/2, 1/4-weighted average of three consecutive input data points, with overlap such that the last of the three input data points contributing to one B-function term is the first of the three input data points contributing to the next successive B-function term, and in turn each defined, for all bands below Band N, as a 1/4, 1/2, 1/4-weighted average of three consecutive B-function terms of the next higher band, with overlap such that the last of the three higher-band B-function terms contributing to each lower-band B-function term is the first of the higher-band B-function terms contributing to the next successive lower-band B-function term.

12. A transform method in accordance with claim 11, comprising a fast method which includes the steps of calculating B-function terms for all bands and employing these calculated B-function terms to generate B-function terms and D-function coefficients for successive lower bands.

13. A transform method in accordance with claim 11, wherein the selected D-function coefficients comprise every D-function coefficient which is defined.

14. A transform method in accordance with claim 11, comprising generating a stream of B-function terms for Band 1, with overlap of the input data points contributing to each B-function term for Band 1 such that the beginning input data point for each successive B-function term for Band 1 shifts ahead by 2^N input data points.

15. A transform method in accordance with claim 11, which further comprises:

generating selected coefficients for each band as S-functions defined, for Band N, as a -1/2, 0, +1/2-weighted average of three consecutive input data points and, for all bands below Band N, as a -1/2, 0, +1/2-weighted average of three successive B-function terms of the next higher band, the B-function terms in turn each defined, for Band N, as a 1/4, 1/2, 1/4-weighted average of three consecutive input data points, with overlap such that the last of the three input data points contributing to one B-function term is the first of the three input data points contributing to the next successive B-function term, and in turn each defined, for all bands below Band N, as a 1/4, 1/2, 1/4-weighted average of three consecutive B-function terms of the next higher band, with overlap such that the last of the three higher-band B-function terms contributing to each lower-band B-function term is the first of the higher-band B-function terms contributing to the next successive lower-band B-function term.

16. A transform method in accordance with claim 15, which comprise outputting the S-function coefficients.

17. A transform method in accordance with claim 15, which comprises outputting both S-function and D-function coefficients.

18. A transform method in accordance with claim 15, which comprises outputting linear combinations of S-function and D-function coefficients.

19. A transform method in accordance with claim 15, which further comprises:

normalizing the S-function coefficients to generate normalized S-function coefficients having the property of having zero value for sequences of input sample points of constant value slope; and

outputting the normalized S-function coefficients.

20. A transform method in accordance with claim 15, which further comprises:

normalizing the S-function coefficients to generate normalized S-function coefficients having the property of having zero value for sequences of input sample points of constant value slope; and

outputting both normalized S-functions and D-functions.

21. A transform method in accordance with claim 15 which further comprises:

normalizing the S-function coefficients to generate normalized S-function coefficients having the property of having zero value for sequences of input samples of constant value slope; and

outputting linear combinations of normalized S-functions and D-functions.

22. A transform method in accordance with claim 11, which further comprises:

outputting only coefficients having non-zero values; and

developing map components to describe the location in the transform domain of the non-zero coefficients, the map components being organized in a branched manner beginning with a plurality of map components for Band 1 and continuing with two conditionally-existing map components for successive higher bands branched from each next lower band map component, each map component corresponding to coefficients in a particular band developed from a particualr plurality of input sample points, and each map component including;

a directory word,

conditionally a contents word, and

conditionally an existence word,

the directory words indicating whether a contents word is present and whether an existence word is present,

the contents words being present if there are any non-zero coefficients, and the contents words indicating which coefficients are non-zero,

the existence words being present if there are further branches, and the existence words indicating which branches are present.

23. A transform method for operating on a two-dimensional set of input data points to provide output terms and coefficients in a transform domain organized into one or more bands, N, where N is an integer greater than zero, Band N is the highest band, and Band 1 is the lowest band, said transform method comprising:

generating and outputting at least one term for Band 1 as a two-dimensional B-function defined as a pyramid-weighted average of the values of a square array of adjacent input data points, each side of the square containing 2^N+1 -1 consecutive input data points by first calculating one-dimensional intermediate terms as one-dimensional B-functions defined as a triangularly weighted average of the values of the data points in each row or each column of the input data points and ordering in a column or row as the case may be, and then performing a second one-dimensional B-function calculation on the column or row of ordered results of the first calculation; and

generating and outputting selected coefficients for each band as predetermined functions defined as weighted averages of selected rectangular pluralities of input data points and the predetermined function being selected so as to enable reconstruction of the value of the B-function term for Band 1 and the coefficients for Bands N through 1, said coefficients being generated by first calculating intermediate one-dimensional coefficients for each row or each column of the input data points and ordering the results in a column or row as the case may be, and then performing a second calculation of one-dimensional B-function terms and one-dimensional coefficients on each column or row of the ordered results of the first calculation, with the exception that no second one-dimensional B-function caclulation on the solely B-function results of the first calculation is needed.

24. A transform method in accordance with claim 23 which comprises outputting only non-zero coefficients.

25. A transform method in accordance with claim 23 which further comprises representing the values of coefficients by means of a variable length code to further minimize the number of bits output.

26. A transform method in accordance with claim 23 which comprises outputting only non-zero coefficients and representing the values of the non-zero coefficients by means of a variable length code to further minimize the number of bits output.

27. A map coding process for transmitting information concerning the location in a transform domain of non-zero valued coefficients resulting from a transform process characterized generally by operating on the values of input data points, employing finite-length basis functions to generate values, being organized into a hierarchial or tree structure of discrete levels, the number of input data points contributing to each value increasing by a predetermined factor and the number of values decreasing by the predetermined factor for each successive level progressing from tree branch to tree trunk until an ultimate value results at the tree trunk level, and with coefficients at each level determined so as to enable reconstruction of the values of the input data points from the ultimate value at the tree trunk and the coefficients for all levels, said map coding process comprising:

outputting only the non-zero valued coefficients;

developing a map including components to describe the location in the transform domain of the non-zero coefficients, the map components being organized in a branched manner beginning with a plurality of map components at the tree trunk level and continuing with a predetermined number of conditionally-existing map components for successive levels branched from each next preceeding level map component, each map component corresponding to coefficients in a particular level, and each map component including;

a directory word,

conditionally a contents word, and

conditionally an existence word,

the directory words indicating whether a contents word is present and whether an existence word is present,

the contents words being present if there are any non-zero coefficients, and the contents words indicating which coefficients are non-zero,

the existence words being present if there are further branches, and the existence words indicating which branches are present.

28. A map coding process in accordance with claim 27, which further comprises representing the values of the non-zero coefficients by means of a variable length code to further minimize the number of bits output.

29. A map coding process in accordance with claim 27, which comprises developing a plurality of maps such that the maps in combination describe the location in the transform domain of the non-zero coefficients, with each map contributing separately or in combination with other maps to the location of a subset of non-zero coefficients and other map components.

30. A map coding process in accordance with claim 29 which further comprises representing the values of the non-zero coefficients by means of a variable length code to further minimize the number of bits output.

31. A map coding process in accordance with claim 30, wherein the subsets of non-zero coefficients have different directional properties.

32. A transform and transformed coefficient map coding method for operating on three two-dimensional sets of input data points, the three sets respectively being sampled data points of "Y", "I" and "Q" video signals representing a color television image, the "Y" signal being the equivalent of a monochrome signal and the "I" and "Q" signals being color-difference signals, said transform and coding method providing three respective sets of ouput terms and coefficients in a transform domain organized into one or more bands N, where N is an integer greater than zero, Band N is the highest band, and Band 1 is the lowest band;

said transform and coding method comprising;

performing a first partial one-dimensional transform for Band N on either each row or each column of each of the three sets of input data points by a single-band triangle transform process to generate B-function terms each defined as a triangularly-weighted average of three consecutive data points, with overlap such that the last of the three data points contributing to one B-function term is the first of the three data points contributing to the next successive B-function term, and to generate coefficients as predetermined functions defined as weighted averages of selected consecutive pluralities of data points, the predetermined functions being selected so as to enable reconstruction of the values of the input data points upon completion of the entire transform method;

ordering the results of each triangle transform process on each row or each column of the data points by rows or columns, as the case may be, by band number and horizontal or vertical position, as the case may be;

performing by the triangle transform process a second partial one-dimensional single-band transform on each column or row, as the case may be, on the ordered results of the first single-band trnsform performed to generate two-dimensional coefficients for the band just processed;

successively repeating, for each set of input data and for successive lower bands employing as data points the B-function terms resulting from the first and second partial one-dimensional triangle transforms of the next higher band arranged in two dimensions, the steps of performing a first partial one-dimensional triangle transform, ordering the results, performing a second partial one-dimensional triangle transform, and outputting the coefficients generated, until processing for Band 1 is completed;

for each set of input data outputting the B-function terms resulting from the first and second partial one-dimensional triangle transforms for Band 1;

outputting only selected and corresponding coefficients for each of the three sets of input data; and

developing a common set of map components to describe the location in the transform domain of the selected coefficients.

33. A transform and coding method according to claim 32, which comprises selecting coefficients for outputting and mapping if any one of three corresponding coefficients respectively resulting from transformation of the "Y" input data, the "I" input data, or the "Q" input data is non-zero.

34. A transform and coding method according to claim 32 which comprises selecting corresponding coefficients for outputting and maping only if a particular coefficient resulting from transformation of the "Y" input data is non-zero.

35. A transform method according to claim 32, which comprises organizing the map components in a branched manner beginning with a plurality of map components for Band 1 and continuing with a predetermined number of conditionally-existing map components for successive higher bands branched from each next lower band map component, each map component corresponding to coefficients in a particular band developed from a particular plurality of input sample points, and each map component including:

a directory word,

conditionally a contents word, and

conditionally an existence word,

the directory words indicating whether a contents word is present and whether an existence word is present,

the contents words being present if there are any selected coefficients, and the contents words indicating which coefficients are selected,

the existence words being present if there are further branches, and the existence words indicating which branches are present.

36. A transform and coding method according to claim 35, which comprises selecting coefficients for outputting and mapping if any one of three corresponding coefficients respectively resulting from transformation of the "Y" input data, the "I" input data, or the "Q" input data is non-zero.

37. A transform and coding method according to claim 36 which comprises selecting corresponding coefficients for outputting and mapping only if a particular coefficient resulting from transformation of the "Y" input data is non-zero.

38. A transform apparatus for operating on a set of input data points to provide output terms and coefficients in a transform domain organized into one or more bands, N, where N is an integer greater than zero, Band N is the highest band, and Band 1 is the lowest band, said transform apparatus compising:

a plurality of interconnected processing blocks organized adjacent one another for each band, the number of processing blocks being greatest for Band N and decreasing for each successive lower band;

said processing blocks together arranged to generate and output at least one term for Band 1 and a B function defined as a triangularly-weighted average of the values of 2^N+1 -1 consecutive input data points and to generate and output coefficients for each band as predetermined functions defined as weighted averages of selected consecutive pluralities of input data points, the number of input data points contributing to each coefficient being the least for Band N, and the number of input data points contributing to each coefficient increasing by powers of two for each successive band below Band N, and the predetermined functions being selected so as to enable reconstruction of the values of the input data points from the B-function term for Band 1 and the coefficients for bands N through 1;

each of said interconnected processing blocks including elements for implementing the smallest set of processing steps which of themselves do not repeat, but which, when taken with other processing blocks, repeat as a set without any additional processing steps being required to interconnect them and are sufficient to perform the transform over the space of an arbitrarily large set of input data points.

39. A transform apparatus for operating on a one-dimensional set of input data points to provide output terms and coefficients in a transform domain organized into one or more bands, N, where N is an integer greater than zero, Band N is the highest band, and Band 1 is the lowest band, said transform apparatus comprising:

means for generating and outputting at least one term for Band 1 as a B function defined as a triangularly-weighted average of the values of 2^N+1 -1 consecutive input data points;

means for generating and outputting coefficients for each band as predetermined functions as weighted averages of selected consecutive pluralities of input data points, the number of input data points contributing to each coefficient being the least for Band N, and the number of input data points contributing to each coefficient increasing by powers of two for each successive band below Band N, and the predetermined functions being selected so as to enable reconstruction of the values of the input data points from the B-function term for Band 1 and the coefficients for bands N through 1.

40. A transform apparatus in accordance with claim 39, which generates a stream of B-function terms for Band 1, with overlap of the input data points contributing to each B-function term for Band 1 such that the beginning input data point for each successive B-function term for Band 1 shifts ahead by 2^N input data points.

41. A transform apparatus in accordance with claim 40, wherein the predetermined functions are selected so as to enable reconstruction of the values of the input data points as a build-up from Band 1 upwards of linear interpolation between B-function terms for Band 1, with departures from linear interpolation being indicated by non-zero coefficients.

42. A transform apparatus in accordance with claim 40, which further comprises:

means for selecting and outputting only coefficients having non-zero values; and

means for developing map components to describe the location in the transform domain of the non-zero coefficients, the map components being organized in a branched manner beginning with a plurality of map components for Band 1 and continuing with two conditionally-existing map components for successive higher bands branched from each next lower band map component, each map component corresponding to coefficients in a particular band developed from a particular plurality of input sample points, and each map component including;

a directory word,

conditionally a contents word, and

conditionally an existence word,

the directory words indicating whether a contents word is present and whether an existence word is present,

the contents words being present if there are any non-zero coefficients, and the contents words indicating which coefficients are non-zero,

the existence words being present if there are further branches, and the existence words indicating which branches are present.

43. A transform apparatus for operating on a set of input data points to provide output terms and coefficients in a transform domain organized into one or more bands, N, where N is an integer greater than zero, Band N is the highest band, and Band 1 is the lowest band, said transform apparatus comprising:

a plurality of interconnected processing blocks organized adjacent one another for each band, the number of processing blocks being greatest for Band N and decreasing for each successive band;

said processing blocks together arranged to generate and output at least one term for Band 1 as a two-dimensional B-function defined as a pyramid-weighted average of the values of a square array of adjacent input data points, said square being 2.sup.(N+1) -1 consecutive points on a side, and to generate and output coefficients for each band as predetermined functions defined as weighted averages of selected rectangular pluralities of input data points, the number of input data points contributing to each coefficient being the least for Band N and the number on input data points contributing to each coefficient increasing by powers of four for each successive band below Band N, and the predetermined functions being selected so as to enable reconstruction of the values of the input data points from the B-function terms for Band 1 and the coefficients for Band N through 1;

each of said interconnected processing blocks including elements for inplementing the smallest set of processing steps which of themselves do not repeat, but which when taken with other processing blocks, repeat as a set with out any additional processing steps being required to interconnect them and are sufficient to perform the transform over the space of an arbitrarily large set of input data points.

44. A transform apparatus for operating on a two-dimensional set of input data points to provide output terms and coefficients in a transform domain organized into one or more bands, N, where N is an integer greater than zero, Band N is the highest band, and Band 1 is the lowest band, said transform apparatus comprising:

means for generating and outputting at least one term for Band 1 as a two-dimension B-function defined as a pyramid-weighted average of the values of a square set of input data points said square being 2.sup.(N+1) -1 consecutive data points on a side; and

means for generating and outputting coefficients for each band as predetermined functions defined as weighted averages of selected rectangular pluralities of input data points, the number of input data points contributing to each coefficient being the least for Band N, and the number of input data points contributing to each coefficient increasing by powers of four for each successive band below Band N, and the predetermined functions being selected so as to enable reconstruction of the values of the input data points from the B-function terms for Band 1 and the coefficients for Bands N through 1.

45. A transform apparatus in accordance with claim 44 which generates a two-dimensional array of B-function terms for Band 1 with overlap of the input data points contributing to each B-function term for Band 1 such that each successive B-function term for Band 1 shifts ahead by 2^N input data points in at least one of the two dimensions of the two-dimensionsal set of input data points.

46. A transform apparatus in accordance with claim 44 which generates a two-dimensional array of B-function terms for each Band 1 with overlap of the input data points contributing to each B-function term for Band 1 such that each successive B-function term for Band 1 shifts ahead by 2^N input data points in at least one of the two dimensions of the two-dimensional set of input data points.

47. A transform apparatus in accordance with claim 45 wherein the predetermined functions are selected so as to enable two-dimensional reconstruction of the values of the input data points as a build-up from Band 1 upwards of linear interpolation in two dimensions between B-function terms for Band 1, with departures from linear interpolation being indicated by non-zero coefficients.

48. A transform apparatus in accordance with claim 45, which further comprises:

means for selecting and outputting only coefficients having non-zero values; and

means for developing map components to describe the location in the transform domain of the non-zero coefficients, the map components being organized in a branched manner beginning with a plurality of map components for Band 1 and continuing with four conditionally-existing map components for successive higher bands branched from each lower band map component, each map component corresponding to coefficients in a particular band developed from a particular plurality of input sample points, and each map component including;

a directory word,

conditionally a contents word, and

conditionally an existence word

the directory words indicating whether a contents word is present and whether an existence word is present, and

the contents words being present if there are any non-zero coefficients, and the contents words indicating which coefficnets are non-zero, and

the existence words being present if there are further branches, and the existence words indicating which branches are present.

49. A digital communication system for communicating a set of input data points, said digital communication system comprising at a transmitting terminal:

a forward transformer for operating on the set of input data points to provide output terms and coefficients in a transform domain organized into one or more bands, N, where N is an integer greater than zero, Band N is the highest band, and Band 1 is the lowest band, said forward transformer including;

means for generating and outputting at least one term for Band 1 as a B function defined as a triangularly-weighted average of the values of 2^N+1 -1 consecutive input data points;

means for generating and outputting coefficients for each band as predetermined functions defined as weighted averages of selected consecutive pluralities of input data points, the number of input data points contributing to each coefficient being the least for Band N, and the number of input data points contributing to each coefficient increasing by powers of two for each successive band below Band N, and the predetermined functions being selected so as to enable reconstruction of the values of the input data points from the B-function term for Band 1 and the coefficients for Bands N through 1.

50. A digital communication system in accordance with claim 49, wherein said forward transformer generates a stream of B-function terms for Band 1, with overlap of the input data points contributing to each B-function term for Band 1 such that the beginning input data for each successive B-function term for Band 1 shifts ahead by 2^N input data points.

51. A digital communication system in accordance with claim 50, wherein the predetermined functions are selected so as to enable reconstruction of the values of the input data points as a build-up from Band 1 upwards of linear interpolation between B-function terms for Band 1, with departures from linear interpolation being indicated by non-zero coefficients.

52. A digital communication system in accordance with claim 50, which further comprises:

means for selecting and outputting only coefficients having non-zero values; and

means for developing map components to describe the location in the transform domain of the non-zero coefficients, the map components being organized in a branched manner beginning with a plurality of map components for Band 1 and continuing with two conditionally-existing map components for successive higher bands branched from each next lower band map component, each map component corresponding to coefficients in a particular band developed from a particular plurality of input sample points, and each map component including;

a directory word,

conditionally a contents word, and

conditionally an existence word,

the directory words indicating whether a contents word is present and whether an existence word is present,

the contents words being present if there are any non-zero coefficients, and the contents words indicating which coefficients are non-zero,

the existence words being present if there are further branches, and indicating which branches are present.

53. A digital communication system for communicating a two-dimensional set of input data points, said digital communication system comprising at a transmitting terminal:

a forward transformer for operating on the set of input data points to provide output terms and coefficients in a transform domain organized into one or more bands, N, where N is an integer greater than zero, Band N is the highest band, and Band 1 is the lowest band, said forward transformer including;

means for generating and outputting at least one term for Band 1 as a B-function defined as a pyramid-weighted average of the values of a square array of adjacent input data points, said square having 2.sup.(N+1) -1 consecutive points on a side;

means for generating and outputting coefficients for each band as predetermined functions defined as weighted averages of selected rectangular pluralities of input data points, the number of input data points contributing to each coefficient being the least for Band N, and the number on input data points contributing to each coefficient increasing by powers of four for each successive band below Band N, and the predetermined functions being selected so as to enable reconstruction of the values of the input data points from the B-function terms for Band 1 and the coeficients for Bands N through 1.

54. A digital communication system in accordance with claim 53, wherein said forward transformer generates a two-dimensional array of B-function terms for Band 1 with overlap of the input data points contributing to each B-function term for Band 1 such that each successive B-function terms for Band 1 shifts ahead by 2^N input data points in at least one of the dimensions of the two-dimensional set of input data points.

55. A digital communication system in acordance with claim 53, wherein said forward transformer generates a two-dimensional array of B-function terms for Band 1 with overlap of the input data points contributing to each B-function term for Band 1 such that each successive B-function term for Band 1 shifts ahead by 2^N input data points in both of the two dimensions of the two-dimensional set of input data points.

56. A digital communication system in accordance with claim 53, wherein the predetermined functions are selected so as to enable two-dimensional reconstruction of the values of the input data points as a build-up from Band 1 upwards of linear interpolation being indicated by non-zero coefficients.

57. A digital communication system in accordance with claim 54, which further comprises:

means for selecting and outputting only coefficients having non-zero values; and

means for developing map components to describe the location in the transform domain of the non-zero coefficients, the map components being organized in a branched manner beginning with a plurality of map components for Band 1 and continuing with four conditionally-existing map components for successive higher bands branched from each lower band map component, each map component corresponding to coefficients in a particular band developed from a particular plurality of input sample points, and each map component including;

a directory word,

conditionally a contents word, and

conditionally an existence word,

the directory words indicating whether a contents word is present and whether an existence word is present, the contents words being present if there are any non-zero coefficients, and the contents words indicating which coefficients are non-zero,

the existence words being present if there are further branches, and the existence words indicating which branches are present.