Method and apparatus for performing neighborhood operations on a processing plane

• US 5,270,963 A
• Filed: 07/06/1990
• Issued: 12/14/1993
• Est. Priority Date: 08/10/1988
• Status: Expired due to Term

• Current Assignee: Foveon, Inc. (Avis Budget Group Incorporated)
• Original Assignee: Synaptics Incorporated
• Inventors: Allen, Timothy P., Faggin, Federico, Wall, Michael F.
• Primary Examiner(s): Smith, Jerry
• Assistant Examiner(s): TRAMMELL, JAMES P
• Application Number:
  US07/549,423
• Time in Patent Office: 1,257 Days
• Field of Search: 364/807, 364/861, 364/844, 364/841, 364/825, 364/602, 364/606, 364/757, 364/760, 364/767, 364/754
• US Class Current: 708/801
• CPC Class Codes: G06N 3/065 Analogue means
• CPC Class Codes: G06T 5/20 using local operators
• CPC Class Codes: G06V 10/20 Image preprocessing
• CPC Class Codes: G06V 10/36 Applying a local operator, i.e. means to operate on image points situated in the vicinity of a given point; Non-linear local filtering operations, e.g. median filtering
• CPC Class Codes: G06V 10/955 using specific electronic processors

Abstract

The present invention is a method and apparatus for performing neighborhood processing operations on an n dimensional processing plane. In a simple, two dimensional, example, an M by N processing plane is successively scanned by rows. The output information from each row is presented on column lines. The analog data resulting from a fixed number of successive scans are temporarily held in a multi-stage analog buffer. A computing array is configured to perform the neighborhood operations or other limited co-operand operations on the shifted data. The computing array examines information from a slice made up of selected numbers of successive rows of the entire array, performs the operations on that portion, and provides a series of output signals representative of the result. The analog buffer is pipelined; information from a new row represents only a single row of new data and the contents of the latch stage containing the oldest information is replaced with this new analog data, causing the information from the transducers of the oldest row to be lost. The operation is then performed on the new slice. This sequence is repeated until all representative slices of the total array have had the neighborhood operations performed on them.

Claims

1. Apparatus for performing operations on analog data obtained from a portion of a processing plane, said portion organizable into N rows, where N is an integer greater than one, and M columns, where M is an integer greater than one, said rows and columns forming intersections, said processing plane having information elements at the intersections of selected ones of said rows and columns, said apparatus including:

storage means for temporarily storing analog data from information elements at M columns and n contiguous rows of said processing plane, where 1<

n<

N, said rows identifiable by n successive integers between 1 and N, to form a n×

M operation plane,

n×

m sources of weighting information, associated with a process to be performed on a neighborhood of said processing plane, said neighborhood comprising a plurality of elements arranged as a local subset of n rows and m columns of said processing plane, where 1<

m<

M, said sources of weighting information mapped with a one to one correspondence to the elements of said neighborhood,

combining means for simultaneously combining said n×

m sources of weighting information with selected n×

m neighborhoods of said n×

M operation plane, said combining means adapted to associate said sources of weighting information with said analog data such that the row order of the weighting information corresponds to the row order of the analog data and the same weight is used for the same relative position within each of said neighborhoods.

2. The apparatus of claim 1 wherein said selected n×

m neighborhoods are all possible contiguous neighborhoods.

3. The apparatus of claim 1 wherein said neighborhood comprises a plurality of elements arranged as a local subject of n contiguous rows and a m contiguous columns of said processing plane.

4. The apparatus of claim 1 wherein said combining means includes means for multiplying said analog data by said weighting information.

5. Apparatus for performing operations on analog data obtained from a vector of M analog input signals, where M is an integer greater than one, including:

n×

M storage elements for temporarily storing analog data, said elements arranged in n rows of M columns each to form an operating plane, each row representing a separate time sample of said input vector,

n×

m sources of weighting information, associated with a process to be performed on a plurality of neighborhoods of said operating plane, each of said neighborhoods comprising a plurality of elements arranged as a local subset of n rows and m columns of said operating plane, were 1<

m<

M, said sources of weighting information mapped with a one to one correspondence to the elements of said neighborhood,

combining means for simultaneously combining said n×

m sources of weighting information with selected n×

m neighborhoods of said n×

M operating plane, said combining means adapted to combine said sources of weighting information with said analog data such that the row order of the weighting information corresponds to the row order of the analog data and to combine the same source of weighting information with the analog data in the same relative position within each of said neighborhoods.

6. The apparatus of claim 5 wherein said selected n×

m neighborhoods are all possible contiguous neighborhoods.

7. The apparatus of claim 5 wherein said neighborhood comprises a plurality of elements arranged as a local subset of n contiguous rows and m contiguous columns of said processing plane.

8. The apparatus of claim 5 wherein said combining means includes means for multiplying said analog data by said weighting information.

9. Apparatus for performing operations on analog data obtained from a vector of M analog input signals, where M is an integer greater than one, including:

n×

M storage elements for temporarily storing analog data, said elements arranged in n rows of M columns each to form an operating plane, each row representing a separate time sample of said input vector, said rows identifiable by n successive integers, the order of said integers indicating the relative time at which said data are sampled,

means for selectively storing each new sample of said input vector in the row of said storage elements which si presently storing the oldest one of said samples,

n×

m sources of weighting information, associated with a process to be performed on a neighborhood of said operating plane, said neighborhood comprising a plurality of elements arranged as a local subset of n rows and m columns of said operating plane, where 1<

m<

M, each said source of weighting information identifiable by a row and column position within said neighborhood with which it will be used,

combining means for simultaneously combining said n×

m sources of weighting information with the analog data in selected n×

m neighborhoods of said n×

M operating plane, said combining means adapted to combine each of said n×

m sources of weighting information with the analog data in the corresponding row and column position within each of said neighborhoods.

means, responsive to the storage of each new sample and cooperating with said combining means, for associating said sources of weighting information with said analog data in said combining means such that the row order of the weighting information corresponds to the row order of the analog data.

10. The apparatus of claim 9 Wherein said selected n×

m neighborhoods are all possible contiguous neighborhoods.

11. The apparatus of claim 9 wherein said neighborhood comprises a plurality of elements arranged as a local subset of n contiguous rows and m contiguous columns of said processing plane.

12. The apparatus of claim 9 wherein said combining means includes means for multiplying said analog data by said weighting information.

13. Apparatus for performing operations on analog data obtained from a vector of M analog input signals, where M is an integer greater than one, including:

n×

m storage elements for temporarily storing analog data, said elements arranged in n rows of M columns each to form an operating plane, each row representing a separate time sample of said input vector, said rows identifiable by successive integers between 1 and n, the order of said successive integers indicating the relative time at which said data are sampled,

means for selectively storing each new sample of said input vector in the row of said storage elements which is presently storing the oldest one of said samples,

n×

m sources of weighting information, associated with a process to be performed on a neighborhood of said operating plane, said neighborhood comprising a plurality of elements arranged as a local subset of n rows and m columns of said operating plane, where 1<

m<

M, each said source of weighting information identifiable by a row and column position within said neighborhood with which it will be used, said row positions being identifiable in order by successive integers between 1 and n,

a set of m processing elements associated with each of said storage elements, each of said processing elements having a first input connected to the output of one of said storage elements in the same row as the storage element with which it is associated, a second input connected to the source of weighting information corresponding to the row and column location within the neighborhood computed by said processing element, and an output,

means, responsive to the storage of each new sample, for re-associating said sources of weighting information with said processing elements such that the order of the successive integers identifying the rows of storage elements and the order of the successive integers identifying the rows of said sources of weighting information connected to the first and second inputs of said processing elements match,

means for combining the outputs of all members of all sets of m processing elements within each column in said operating plane.

14. The apparatus of claim 13 wherein the outputs of said processing elements are currents, and said means for combining the outputs of said processing elements is a wire connected to the outputs of all n×

m processors associated with each neighborhood.

15. The apparatus of claim 13 wherein each of said processing elements comprises a transconductance amplifier having a non-inverting input, an inverting input, a bias input, and an output, said non-inverting input being said first input, said inverting input being connected to said output, and said bias input being said second input, and wherein said means for combining is a conductor connected to the output of all said transconductance amplifiers associated with a given neighborhood.

16. The apparatus of claim 13 wherein each of said processing elements comprises a transconductance amplifier having a non-inverting input, an inverting input, a bias input, and an output, said non-inverting input being said first input, said inverting input being connected to a source of reference voltage, and said bias input being said second input, and wherein said means for combining is a conductor connected to the output of all said transconductance amplifiers associated with a given neighborhood.

17. The apparatus of claim 13 wherein each of said processing elements comprises a first and a second MOS transistor, said first MOS transistor having its drain connected to a conductor, its source connected to the drain of said second MOS transistor and the source of said second MOS transistor connected to a source of fixed voltage, the gate of said first MOS transistor acting as said first input, the gate of said second MOS transistor serving as said second input and wherein said means for combining is said conductor connected to the drains of all said first MOS transistors associated with a given neighborhood.

18. A parallel process for computing a neighborhood operation on an input vector of analog voltages, said process including the steps of:

temporarily storing analog data from said input vector in storage elements arranged in n rows of M columns each, where n and M are integers greater than 1, to form an operating plane, each row representing a separate time sample of said input vector, said rows identifiable by successive integers indicating the relative time at which said data are sampled,

selectively storing each new sample of said input vector in the row of said storage elements which is presently storing the oldest one of said samples,

providing n×

m sources of weighting information, where m is an integer greater than one, associated with a process to be performed on a set of neighborhoods of said operating plane, each neighborhood in said set comprising a plurality of elements arranged as a local subset of n rows and m columns of said operating plane, where 1<

m<

M, each said source of weighting information identifiable by a row and column position within said neighborhood with which it will be used, said row positions being identifiable in order by successive integers between 1 and n,

re-associating said weighting information with said analog data after the storage of each new ample in a manner so as to match the order of the successive integers identifying the rows of storage elements and the order of the successive integers identifying the rows of said sources of weighting information,

simultaneously combining each source of weighting information with the corresponding element of stored data within each of said neighborhoods to form a set of intermediate values,

simultaneously combining said intermediate values associated with each of said neighborhoods to form a set of final outputs, one such output for each neighborhood.

19. A parallel process for computing a neighborhood operation on an input vector of analog voltages, said process including the steps of:

temporarily storing analog data from said input vector in capacitive storage elements arranged in n rows of M columns each, to form an operating plane, each row representing a separate time sample of said input vector,

selectively storing each new sample of said input vector in the row of said storage elements which si presently storing the oldest one of said samples,

providing n×

m sources of voltage representing weighting information associated with a computation to be performed on a set of neighborhoods of said operating plane, each neighborhood in said set comprising a plurality of said storage elements arranged as a local subset of n rows and m columns of said operating plane, where 1<

m<

M, each said source of weighting information identifiable by a row and column position within said neighborhood with which it will be used,

distributing the output of each said source of weighting information on a conductor passing along the row containing the processing elements with which it will be used,

simultaneously combining in a plurality of processing elements each source of weighting information with the corresponding element of stored data within each of said neighborhoods to form an output current,

simultaneously summing the output currents associated with all processing elements of each said neighborhoods to form a set of final output currents, one such output current for each neighborhood.