Triangle and pyramid signal transforms and apparatus
First Claim
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 2N+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.
6 Assignments
0 Petitions
Accused Products
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.
-
Citations
57 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 2N+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. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
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. - View Dependent Claims (8, 9, 10)
- said transform method comprising;
-
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 2N+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. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22)
-
-
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 2N+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. - View Dependent Claims (24, 25, 26)
-
-
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. - View Dependent Claims (28, 29, 30, 31)
-
-
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. - View Dependent Claims (33, 34, 35, 36, 37)
- said transform and coding method comprising;
-
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 2N+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 2N+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. - View Dependent Claims (40, 41, 42)
-
-
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. - View Dependent Claims (45, 46, 47, 48)
-
-
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 2N+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. - View Dependent Claims (50, 51, 52)
-
-
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. - View Dependent Claims (54, 55, 56, 57)
-
Specification