Signal processing device and method

• US 5,073,964 A
• Filed: 08/04/1989
• Issued: 12/17/1991
• Est. Priority Date: 08/04/1989
• Status: Expired due to Fees

• Current Assignee: Aware Incorporated (Crowley Holdings Preferred LLC)
• Original Assignee: Aware Incorporated (Crowley Holdings Preferred LLC)
• Inventors: Resnikoff, Howard
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Johns, Andrew W.
• Application Number:
  US07/389,592
• Time in Patent Office: 865 Days
• Field of Search: 382/41, 382/43
• US Class Current: 382/277
• CPC Class Codes: G06F 17/145 Square transforms, e.g. Hadamard, Walsh, Haar, Hough, Slant transforms
• CPC Class Codes: G06F 17/147 Discrete orthonormal transforms, e.g. discrete cosine transform, discrete sine transform, and variations therefrom, e.g. modified discrete cosine transform, integer transforms approximating the discrete cosine transform G06F17/145 takes precedence

Abstract

A signal processing device for generating an output signal corresponding to a multi-dimensional input signal such as a two-dimensional image and a method of processing such a signal. The device includes an array of processing elements which are congruent and shaped so that they can be arranged on a processing element so that adjacent pairs of elements considered as a unit are geometrically similar to each processing element. Output signals of individual processing units are linearly ordered in such a manner as to maintain adjacency of signals from adjacent processing elements in the array. The ordering facilitates one-dimensional Haar transform processing of the signals in such as a manner as to localize signal energy.

Claims

1. A signal processing device, comprising 2^N successively adjacent substantially congruent Nth-order processing elements positioned on a surface, each of said processing elements comprising a transducing member, where N is a positive integer, each of said 2^N Nth-order processing elements being aggregatable into one of 2^N-k (N-k)th-order non-overlapping aggregates of 2^k successively adjacent Nth-order processing elements for all values of k, where 0<

k≦

N;

the Nth-order processing elements of each (N-k)th-order aggregate substantially covering a substantially continuous portion of said surface and defining an (N-k)th-order processing element, being congruent to every other (N-k)th-order processing element for the same value of k, and having a shape which is substantially geometrically similar to the shape of each (N-k)th-order processing element for all other values of k;

each Nth-order processing element receiving energy input thereto and converting said input energy to an output signal proportional to said input energy.

2. A signal processing device as in claim 1, which further comprises register means for receiving the output signals from said Nth-order processing elements, said register means storing said output signals and generating a series of register output signals each of which corresponds to the output signal of one of said Nth-order processing elements.

3. A signal processing device as in claim 2, wherein each of said Nth-order processing elements comprises at least one CCD element.

4. A signal processing device as in claim 1, which further comprises means for identifying the output signals from the respective Nth-order processing elements in which they were generated and linearly ordering the signals in a predetermined order such that for each (N-k)th-order aggregate each output signal generated by an Nth-order processing element among the 2^k Nth-order processing elements in a particular (N-k)th-order aggregate is contained in a same group of 2^k successively adjacent output signals after the linear ordering.

5. A signal processing device as in claim 4, further comprising means for performing a Haar transform on said output signals after the linear ordering thereof.

6. A signal processing device as in claim 1, wherein each of said Nth-order processing elements is rectangular, has a short side and a longer side, the ratio of its short side to its longer side being substantially 1:

√

2, the longer of said sides of all of said Nth-order processing elements being parallel.

7. A signal processing device as in claim 4, wherein each of said Nth-order processing elements is rectangular, has a short side and a longer side, the ratio of its short side to its longer side being substantially 1:

√

2, the longer of said sides of all of said Nth-order processing elements being parallel.

8. A signal processing device as in claim 7, wherein defining a Cartesian x,y plane with said Nth-order processing elements arrayed with their shorter sides parallel to an X axis, the longer sides parallel to a y axis perpendicular to the x axis, and with a scale such that the shorter sides have unit length on the x axis and the longer sides have a length substantially equal to √

2, the 2^N Nth-order processing elements forming a two-dimensional array, the location of each Nth-order processing element being defined by the coordinates of its upper left hand corner and a first one of the Nth-order processing elements having coordinates (0,0), the formula;

##EQU5## defines the positions of the Nth-order processing elements and the linear ordering of the signals therefrom wherein b_j is the jth ordered bit of the sequence of bits b₁, b₂, b₃, ....., b_N representing the relative position in the linear ordering of the Nth-order processing element located at the coordinates (x,y) and i represents the square root of -1.

9. A signal processing device as in claim 4, wherein said Nth order processing elements have a pseudo-fractal shape and wherein, defining a Cartesian x,y plane with said Nth-order processing elements arrayed thereon and the Nth-order processing elements thereby forming a two-dimensional array, the formula:

##EQU6## defines the positions of the Nth-order processing elements and the linear ordering of the signals therefrom wherein b_j is the jth ordered bit of the sequence of bits b₁, b₂, b₃, ...., b_N, the sequence of bits b₁, b₂, b₃,...., b_N representing the relative position of the signals in the linear ordering of the signals from the Nth-order processing elements with the Nth-order processing elements located at the coordinates (x,y) and i represents the square root of -1.

10. A signal processing device as in claim 9, wherein each of said Nth-order processing elements is formed of a plurality of successively adjacent square shaped processing subelements 2^P in number, P being an integer greater that 2, and wherein, defining a Euclidean x,y plane with said processing subelements arrayed with two opposite sides parallel to an x axis and the other two opposite sides parallel to a y axis perpendicular to the x axis and with a scale such that all of said sides have unit length the 2^N processing elements forming a two-dimensional array, the location of each processing subelement being defined by the coordinates of its upper left hand corner and a first one of the processing subelements having coordinates (0,0), the formula:

##EQU7## defines the positions of the processing subelements with said processing subelements being located at the coordinates (x+Δ

x,y+Δ

y) wherein b_j is the jth order bit of the sequence of bits b₁, b₂, b₃, ..., b_N+P, the sequence of bits bits b₁, b₂, b₃, ..., b_N representing the relative position of the signals in the linear ordering of the signals from the Nth-order processing elements located at the coordinates (x,y) given by the formula ##EQU8## and i represents the square root of -1.

11. A signal processing device as in claim 4, wherein said Nth-order processing elements have a pseudo-fractal shape and wherein, defining a Cartesian x,y plane with said Nth-order processing elements arrayed thereon and the processing elements thereby forming a two-dimensional array, the formula:

##EQU9## defines the positions of the Nth-order processing elements and the linear ordering of the signals therefrom wherein b_j is the jth ordered bit of the sequence of bits b₁, b₂, b₃, ... .., b_N, the sequence of bits b₁, b₂, b₃, ..., b_N representing the relative position of the signals in the linear ordering of the signals from said Nth-order processing elements with (x,y) and i represents the square root of -1.

12. A signal processing device as in claim 11, wherein each of said Nth-order processing elements is formed of a plurality of successively adjacent parallelogram-shaped processing subelements 2^P in number, P being an integer greater that 2, and wherein, defining a first Cartesian x,y plane with said processing subelements arrayed with two opposite sides parallel to an x axis and the other two opposite sides parallel to a y axis perpendicular to a common line making an angle of substantially arctan √

7 with the x axis and with a scale such that all of said sides have unit length the 2^N processing elements forming a two-dimensional array, the location of each processing subelement being defined by the coordinates of its upper left hand corner and a first one of the processing subelements having coordinates (0,0), the formula;

##EQU10## defines the positions of the processing subelements with said processing subelements being located at the coordinates (x+Δ

x,y+Δ

y) and the linear ordering of the signals therefrom wherein b_j is the jth ordered bit of the sequence of bits b₁, b₂, b₃, ...., b_N+P, the sequence of bits b₁, b₂, b₃, ... .., b_N representing the relative position of the signals in the linear ordering of the signals from the Nth-order processing elements located at the coordinates (x,y) given by the formula ##EQU11## and i represents the square root of -1.

13. A device as in claim 1, wherein said 2^N Nth-order processing elements form a display screen, each of said Nth-order processing elements comprising an individual pixel.

14. A device as in claim 10, further comprising an output, and a substrate having a first surface in said plane and a second surface parallel to said plane, said identifying and ordering means including transfer members on said second surface, said 2^N+P processing elements being formed on said first surface with said transfer numbers coupling said 2^N+P processing subelements to said output, said storing means for each Nth-order processing element comprising means for storing a respective portion of the signal on the respective processing subelements thereof, the formula further defining the order of the signal portion from the respective processing subelements in the linear ordering, the sequence of bits b₁, b₂, b₃, ....., b_N+P representing the relative position of the signal portions in the linear ordering, said identifying and ordering means further comprising means for transferring the signal portions stored on said processing subelements in a predetermined order.

15. A device as in claim 12, further comprising an output, and a substrate having a first surface in said plane and a second surface parallel to said first plane, said identifying and ordering means including transfer members on said second surface, said transfer members coupling said 2^N+P processing subelements to said output, said storing means for each Nth-order processing element comprising means for storing a respective portion of the signal on the respective processing subelements thereof, the formula further defining the order of the signal portions from the respective processing subelements in the linear ordering, the sequence of bits b₁, b₂, b₃, ...., b_N+P representing the relative position of the signals in the linear ordering of the processing subelements, said identifying and ordering means further comprising means for transferring the signal portions stored on said processing subelements in a predetermined order.

16. A signal processing device as in claim 4, wherein said Nth order processing elements have a pseudo-fractal shape and wherein, defining a Cartesian x,y plane with said Nth-order processing elements arrayed thereon and the Nth-order processing elements thereby forming a two-dimensional array, the formula:

##EQU12## defines the positions of the Nth-order processing elements and the linear ordering of the signals therefrom wherein b_j is the jth ordered bit of the sequence of bits b₁, b₂, b₃, .. ..., b_N, and i represents the square root of -1.

17. A signal processing device as in claim 4, wherein said Nth-order processing elements have a pseudo-fractal shape and wherein, defining a Cartesian x,y plane with said Nth-order processing elements arrayed thereon and the processing elements thereby forming a two-dimensional array, the formula:

##EQU13## defines the positions of the Nth-order processing elements and the linear ordering of the signals therefrom wherein b_j is the jth ordered bit of the sequence of bits b₁, b₂, b₃, ... ..., b_N, and i represents the square root of -1.

18. A signal processing device as in claim 2, wherein said register means includes means for identifying the output signals from the respective Nth-order processing elements in which they were generated and linearly ordering the signals in such a manner that for each (N-k)th-order aggregate, each output signal generated by a processing element among the 2^k processing elements in a particular (N-k)th-order aggregate is contained in a same group of 2^k successively adjacent register output signals after the linear ordering.

19. A device as in claim 1, wherein each of said processing elements comprises at least one CCD.

20. A method of processing two-dimensional input signals, comprising the steps of:

forming a first-order transducer including 2^N Nth-order transducers formed in a continuous subprocessing element, N being a positive integer, said Nth-order transducers being adjacently arranged in a non-overlapping manner in a planar surface, the Nth-order transducers having substantially congruent shapes in said surface, each of the 2^N Nth-order transducers being aggregatable into one of 2^N-k (N-k)th-order non-overlapping aggregates of 2^k successively adjacent Nth-order transducers, for all values of k, where 0<

k≦

N;

each of the (N-k)th-order aggregates consisting of two adjacent (N-k+1)th-order aggregates for each value of k, the Nth-order transducers of each (N-k)th-order aggregate together covering a continuous surface area of said surface and defining an (N-k)th-order transducer, being congruent to every other (N-k)th-order transducer for the same value of k, and having a shape which is substantially geometrically similar to the shape of each (N-k)th-order processing element for all other values of k;

each Nth-order transducer having means for receiving energy substantially evenly thereover in said planar surface;

receiving a two-dimensional signal on the Nth-order transducers in said planar surface;

storing the two-dimensional signal in the respective Nth-order processing elements as respective Nth-order signals;

linearly ordering the Nth-order signals such that the Nth-order signals stored in each (N-k)th-order aggregate of 2^k transducers for each positive integer value of k up to and including N, is contained in a same group of 2^K successively adjacent ones of Nth-order signals after the linear ordering;

outputting the Nth-order signals from the first-order transducer; and

performing a mathematical one-dimensional transform of the linearly ordered Nth-order signals.

21. A method as in claim 20, wherein said step of performing a mathematical one-dimensional transform comprises the step of performing a one-dimensional Haar transform of the linearly ordered Nth-order signals.