Topological transformation system

• US 4,192,004 A
• Filed: 09/08/1977
• Issued: 03/04/1980
• Est. Priority Date: 09/08/1977
• Status: Expired due to Term

• Current Assignee: Walter R. Buerger
• Original Assignee: Walter R. Buerger
• Inventors: Buerger, Walter R.
• Primary Examiner(s): Gruber, Felix D.
• Application Number:
  US05/831,390
• Time in Patent Office: 908 Days
• Field of Search: 364/514, 364/515, 364/518, 340/146.3 F, 340/146.3 Q, 340/146.3 H, 340/146.3 MA
• US Class Current: 382/204
• 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

Abstract

A topological transformation system for transforming and extracting data from distributed images in n-dimensional spaces. The system is disclosed in two-dimensional form as principally comprising an iterative array of logical cells, each of which may be used to contain duplicates of each element of the distributed image. The duplicates are translatable with respect to each other simultaneously in all possible directions, and comparisons may be made at each translational step between the current image and previous or transformed versions of the image. An example is described for deriving the center points of holes in a two-dimensional image, and a four-dimensional iterative array is also disclosed.

Claims

1. A topological transformation system for transforming and analyzing data distributions residing in topological n-dimensional metric spaces, said system comprising:

transducer means for converting a data distribution in an n-dimensional space into electrical signals;

an iterative array of storage cells, wherein each cell represents one elemental portion of the original space and each cell contains a plurality of storage block pairs which hold pairs of elements of duplicate images;

means for inputting said electrical signals, representative of the original data distribution, to said iterative array;

means for manipulating the contents of said iterative array by simultaneously translating contained duplicate pairs of images of the data distribution in a multiplicity of contravariant or opposing directions along preplanned trajectories in the n-dimensional space, to allow transformation of the data distribution into another form; and

,

means for comparing the contents of storage block pairs within a cell during translation of the duplicate image pairs, and thereby detecting features relating to forms within or the topology of the original data distribution;

where n is an integer such as 1, 2, 3 or 4.

2. A topological transformation system as set forth in claim 1, wherein:

each of said cells includes 2n primary storage blocks and a plurality of secondary storage blocks associated with each primary storage block;

each of said primary storage blocks is associated with a different particular direction of shifting; and

,

said means for manipulating includes means for transferring data from each of said primary storage blocks to its counterpart in an adjacent cell in the direction with which said primary storage block is associated, and means for transferring data between each of said primary storage blocks and each of said associated secondary storage blocks;

whereby the duplicate images may be initially stored in said primary storage blocks, then shifted in as many as 2n different directions simultaneously in a predefined manner along predetermined trajectories, said secondary storage blocks being employed to store intermediate results or values representative of prior cell content, and whereby said means for comparing may be employed to extract information concerning the form and features of the original image.

3. A topological transformation system as set forth in claim 2, wherein said means for transferring data includes:

data path means providing a plurality of paths between corresponding ones of said primary storage blocks and between each of said primary storage blocks and its associated secondary storage blocks;

gate means coupled to each of said data path means to control flow of data therethrough; and

,

control means to provide an appropriate sequence of control signals to said gate means, to effect transfer of data from cell to cell and between storage blocks within each cell.

4. A two-dimensional image-processing system comprising:

a two-dimensional iterative array of storage cells, wherein each cell initially represents one discrete binary element of a two-dimensional image, and each cell contains four primary storage blocks, each of which is associated with a different shifting direction, and a plurality of secondary storage blocks associated with each primary storage block;

means for transferring data from each of said primary storage blocks to its counterpart in an adjacent cell in the direction with which the primary storage block is associated;

means for transferring data between each of said primary storage blocks and its associated secondary storage blocks; and

means for comparing data in said primary and secondary storage blocks and storing comparison results in one of said secondary storage blocks;

whereby duplicates of the original image can be stored in said four primary storage blocks, then shifted in four directions simultaneously and compared to determine particular form and feature characteristics of the original image, and wherein separate step sequences may use combinations of the four directions to create data trajectories of various directions and routes;

and wherein said means for transferring and said means for comparing each include gated interconnection means coupled to said primary and secondary storage blocks, and said system further includes control means for generating sequences of control signals to control said gated interconnection means in a desired sequence to effect shifting and comparison of the image duplicates stored in said array.

5. A two-dimensional image-processing system as set forth in claim 4, wherein:

each of said primary and secondary storage blocks includes a flip-flop for storing one bit of data; and

,

said gated interconnection means comprises a plurality of AND-type gates, each of which is enabled by a specific signal line from said control means, thereby to pass data from one block to another.

6. Apparatus for performing transformations on two-dimensional images, said apparatus comprising:

means for transducing the image into a set of binary electrical signals;

an iterative array of identical storage cells, each of which can represent one discrete element of the image and each of which contains four primary storage cells and four equal pluralities of secondary storage cells associated respectively with each of said primary storage cells;

means for inputting said binary electrical signals to a first set of primary storage cells of said array;

means for transferring data from cell to adjacent cell, simultaneously in a plurality of selected trajectories through corresponding primary storage blocks of adjacent cells;

means for transferring data between storage blocks within said cells;

comparison means, for comparing data in storage blocks within said cells;

gating means to control said means for transferring data and said comparison means; and

,

control means for generating digital signals to control said gating means, and thereby to control said means for transferring data and said comparison means;

whereby the original image can be duplicated in all four primary storage blocks, then shifted and compared to transform the original image and to extract features therefrom.

7. Apparatus as set forth in claim 6, wherein said control means is a programmable computer.

8. A topological transformation system for transforming and analyzing data distributions residing in topological n-dimensional metric spaces, said system comprising:

transducer means for converting a data distribution in an n-dimensional space into electrical signals;

a set of storage media pairs, wherein each element thereof represents one portion of the original space and each element possesses an associated means of recording activities related to it;

means for inputting said electrical signals, representative of the original data distribution, to said storage media pairs;

means for manipulating the contents of said storage media pairs by simultaneously translating contained duplicate pairs of images of the data distribution in a multiplicity of contravariant or opposing directions along preplanned trajectories in the n-dimensional space, to allow transformation of the data distribution into another form; and

,

means for comparing the contents of the recording means associated with an element during translation of the various contravariant image pairs, and thereby detecting features relating to forms within or the topology of the original data distribution;

wherein n is an integer such as 1, 2, 3 or 4.

9. A method for analyzing a two-dimensional image to locate images of holes, said method comprising the steps of:

storing a two-dimensional image in electrical form in an iterative array of storage cells each of which has four primary storage blocks and a plurality of secondary storage blocks;

copying the image into all four primary storage blocks to provide four copies of the image;

shifting the four image copies simultaneously in four respective directions, one cell at a time, by shifting the contents of each primary storage element to its counterpart in the adjacent cell in the direction of shifting;

comparing on each shift the content in each cell of the left- and right-shifted images and of the up- and down- shifted images, to determine overlap or non-overlap of the images;

determining on each such shift and for each cell whether there was a transition from an overlapping to a non-overlapping condition, or vice versa, for both the left- and right-shifted images and the up- and down-shifted images;

recording such transitions in one of said secondary storage blocks to indicate centers of holes in an up/down and a left/right sense;

logically combining the transitions to determine the exact hole centers; and

,

displaying the results in a display device.

10. A method as set forth in claim 9, and further comprising the step of:

initially shifting the four copies simultaneously in the four respective directions, by a preselected number of shifts, without any comparing step on each of such initial shifting steps.

11. A method for analyzing a two-dimensional image to locate images of holes, said method comprising the steps of:

clearing the contents of a two-dimensional iterative array of storage cells;

loading the iterative array with data obtained from a two-dimensional camera image, wherein each storage cell is employed to store a single picture element of the image;

copying each picture element of the image into duplicate storage blocks in each cell to produce four duplicate images in the array of cells;

shifting the images in four respective directions by a predetermined number of picture elements;

shifting the images by one further picture element and immediately comparing the current content of each cell with its previous content;

detecting transitions between overlapping and non-overlapping pairs of images by logically combining the results of said shifting and comparing step;

repeating said shifting and comparing step and said detecting step until a transition defining the location of a hole center is detected.