Triangle and pyramid signal transforms and apparatus

Claim 2

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.

Claim 3

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.

Claim 4

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.

Claim 5

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.

Claim 6

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.

Claim 7

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.

Claim 8

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.

Claim 9

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.

Claim 10

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.

Claim 11

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.

Claim 12

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.

Claim 13

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.

Claim 14

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.

Claim 15

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.

Claim 16

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

Claim 17

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.

Claim 18

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.

Claim 19

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

Claim 20

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

Claim 21

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

Claim 22

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.

Claim 23

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.

Claim 24

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.

Claim 25

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.

Claim 26

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.

Claim 27

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.

Claim 28

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

Claim 29

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.

Claim 30

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.

Claim 31

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.

Claim 32

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.

Claim 33

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.

Claim 34

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.

Claim 35

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.

Claim 36

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

Claim 37

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.

Claim 38

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.

Claim 39

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.

Claim 40

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.

Claim 41

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.

Claim 42

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.

Claim 43

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.

Claim 44

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.

Claim 45

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.

Claim 46

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.

Claim 47

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.

Claim 48

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.

Claim 49

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.

Claim 50

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.

Claim 51

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.

Claim 52

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.

Claim 53

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.

Claim 54

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.

Claim 55

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.

Claim 56

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.

Claim 57

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.

Claim 58

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.

Claim 59

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.

Claim 60

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.

Claim 61

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.

Claim 62

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.

Claim 63

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.

Claim 64

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.

Claim 65

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.

Claim 66

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.

Claim 67

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.

Claim 68

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.

Claim 69

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.