Image processing system

• US 4,267,573 A
• Filed: 06/14/1978
• Issued: 05/12/1981
• Est. Priority Date: 06/14/1978
• Status: Expired due to Term

• Current Assignee: Old Dominion University Research Foundation
• Original Assignee: Old Dominion University Research Foundation
• Inventors: Weiman, Carl F. R., Chaikin, George M.
• Primary Examiner(s): Krass, Errol A.
• Application Number:
  US05/915,453
• Time in Patent Office: 1,063 Days
• Field of Search: 364/515, 364/518, 364/570, 364/520, 364/822, 364/825, 340/723-728, 340/731, 340/743, 365/18, 365/25, 365/10, 307/221 R, 328/225
• US Class Current: 382/296
• CPC Class Codes: G06T 3/02 Affine transformations for image registration G06T3/147; for image mosaicing G06T3/4038
• CPC Class Codes: G06V 10/32 Normalisation of the pattern dimensions
• CPC Class Codes: G06V 30/144 using a slot moved over the image; using discrete sensing elements at predetermined points; using automatic curve following means

Abstract

An image processing system is described in which an image is converted into a plurality of image elements or cells which are arranged in a predetermined pattern. These cells are then simultaneously rearranged into a second predetermined pattern to provide a transformed representation of the original image. In this transformed state, the positions of all of the cells may be simultaneously shifted in a manner which produces modifications of the original image, such as scaling or rotating. The highly parallel manner in which the present system manipulates the image cells allows the desired image modifications to be effected more simply and rapidly than has been previously possible. In a preferred embodiment of the invention these image cell manipulations are performed in a three dimensional shift register of novel design. A number of alternative embodiments of the invention are set forth which are of particular value in pattern recognition systems and in graphic display systems in which the ability to modify or animate images is desired.

Claims

1. An image processing system comprising:

means for converting the image to be processed into a plurality of representative image cells; and

means for concurrently arranging representations of said cells in accordance with a predetermined pattern to produce a geometrically transformed representation of the image, successive geometric transformations of the image being congruent irrespective of changes in scale or angular orientation of the image.

2. The system of claim 1 in which said converting means comprises a plurality of light receptors arranged in an array defining an image-receiving plane.

3. The system of claim 2 in which said arranging means comprises an array of light-responsive elements each of which is optically connected to a corresponding one of said receptors such that each of said elements produces a signal representative of one of said image cells.

4. The system of claim 2 in which said light receptors are arranged in a grid pattern defining a complex logarithmic coordinate system.

5. The system of claim 3 or 4 in which said light-responsive elements are arranged in an image-display pattern defining a rectilinear coordinate system.

6. The system of claim 4 in which said light receptors are arranged in a pattern defined by a plurality of exponentially spaced concentric rings intersected by a plurality of equilangularly spaced radial lines.

7. A system as in any one of claims 1-4 or 6 in combination with:

means providing a transformed representation of a template of said image with selected scale and rotational orientation;

a comparator for comparing said template transformed representation with said image transformed representation to indicate positional correspondence between such representations;

means for operating on said image transformed representation to simulate incremental scale and rotational changes of said image to shift said image transformed representation to achieve a match with the selected scale and rotational orientation of said template transformed representation thereby to determine scale and rotational difference between said predetermined representations; and

means for indicating the respective number of incremental scale and rotational changes required to determine a match between said image and template representations.

8. A system as in claim 7 for handling an object providing said image, in combination with:

means for producing said image from said object, and

means responsive to the magnitude and direction of said shift for manipulating said object.

9. A system as in any one of claims 1-4 or 6 in combination with:

means providing a transformed representation of a template of said image with selected scale and rotational orientation;

a comparator for comparing said template transformed representation with said image transformed representation to indicate positional correspondence between such representations;

means for shifting one of said transformed representations relative to the other until said comparator indicates positional correspondence therebetween, whereby the amount and direction of such shift is indicative of the scale relationship and angular relationship between said image and said template.

10. A system as in claim 9 for handling an object providing said image, in combination with:

means for producing said image from said object, and

means responsive to the magnitude and direction of said shift for manipulating said object.

11. An image-processing system comprising:

means producing a plurality of picture cells representative of an image to be processed; and

means for concurrently converting said cells into respective transformed cells representative of a transformed version of said image, which image version is invariant in size and shape with respect to rotations and dilations of said image.

12. A system as in claim 11, wherein each of said transformed cells is derived from an original cell by a complex logarithmic transformation.

13. A system as in claim 11 wherein each of said transformed cells is derived from an original cell by a tranformation from an exponential ray/ring grid to a Cartesian grid.

14. A system as in claim 12 wherein each of said transformed cells is derived from an original cell by a transformation from a grid formed by orthogonal logarithmic spirals to a skewed Cartesian grid.

15. A system as in claim 12 wherein each of said transformed cells is derived from an original cell by a tranformation from a lattice of angularly related logarithmic spirals to an equilateral triangular lattice.

16. A system for processing an image represented by a plurality of picture cells arranged in a Cartesian coordinate system, comprising:

means for converting the arrangement of said cells to a logarithmic spiral coordinate system;

means for shifting all said cells in said logarithmic spiral coordinate system by an amount representing a desired rotation and dilation of said image; and

means deriving an image-producing signal from said shifting means wherein said signal represents a second image which is essentially identical to said first image in all respects other than scale or angular orientation.

17. A system for processing an image represented by a plurality of picture cells arranged in a Cartesian coordinate system, comprising:

means for converting the arrangement of said cells to a ray and exponentially spaced ring coordinate system;

means for shifting all said cells in said ray and ring coodinate system by an amount representing a desired rotation and dilation of said image; and

means deriving an image-producing signal from said shifting means wherein said signal represents a second image which is essentially identical to said first image in all respects other than scale or angular orientation.

18. A system for processing an image represented by a plurality of picture cells arranged in a grid laid out in accordance with a log spiral coordinate system, comprising:

means for concurrently shifting the position of each of said picture cells by a fixed amount representing desired image rotation and/or dilation; and

means for converting the arrangement of said shifted cells to a grid laid out in accordance with a Cartesian coordinate sytem, whereby an image-producing set of picture cells representing a rotated and/or dilated version of said image is produced.

19. A system for processing an image represented by a plurality of picture cells arranged in a grid laid out in accordance with a log spiral coordinate system, comprising:

means for horizontally shifting all said picture cells by a fixed amount representing desired image dilation; and

means for converting the arrangement of said shifted cells to a grid laid out in accordance with a Cartesian coordinate system, whereby an image-producing set of picture cells representing a dilated version of said image is produced.

20. A system for processing an image represented by a plurality of picture cells arranged in a grid laid out in accordance with a log spiral coordinate system, comprising:

means for vertically shifting all said picture cells by a fixed amount representing desired image rotation; and

means for converting the arrangement of said shifted cells to a grid laid out in accordance with a Cartesian coordinate system, whereby an image-producing set of picture cells representing a rotated version of said image is produced.

21. An image-processing system for a digitized image signal representative of an image having a plurality of picture cells arranged in a Cartesian grid with equally spaced rows and columns of cells, with one of said cells being an origin, and with each of said cells having a location defined by a set of individual Cartesian coordinates, and also having a state defined by respective data associated with said coordinates, said system comprising:

means for transferring the data of each cell to a location having transformed coordinates representing a mapping of the cell'"'"'s Cartesian coordinates upon a log-spiral coordinate system;

means for shifting the locations of all said transformed coordinate cell data by the same amount representative of a desired image rotational displacement; and

means for re-transferring said shifted-coordinate cell data to locations with re-transformed coordinates representing a mapping of log-spiral coordinates upon a Cartesian coordinate system, to produce a digitized image signal representative of a rotated version of said original image.

23. A system as in claim 21 or 22, further including:

means for normalizing said digitized image signal by shifting the data of each of said cells to new coordinates differing from its original coordinates by an amount representing the displacement from said origin of a desired point of image rotation and/or dilation.

24. A system as in claim 23, further including:

means for denormalizing said produced digitized image signal by shifting each cell data to new coordinates differing from its re-transformed coordinates by said displacement from origin.

25. A system as in claim 21 or 22 wherein said mapping is represented by

26. A system as in claim 21 or 22 wherein each ordinate line of the Cartesian grid is mapped into a circle of the log spiral coordinate system, and each abscissa line of the Cartesian grid is mapped into a radial line of said log spiral coordinate system.

27. A system as in claim 21 or 22, wherein said mapping is effected by transforming orthogonal lines of the Cartesian grid into respective orthogonal logarithmic spirals.

28. A system as in claim 21 or 22 wherein said mapping is effected by transforming an equilateral triangular lattice of the Cartesian grid into a lattice formed of angularly related logarithmic spirals.

22. An image-processing system for a digitized image signal representative of an image having a plurality of picture cells arranged in a Cartesian grid with equally spaced rows and columns of cells, with one of said cells being an origin, and with each of said cells having a location defined by a set of individual Cartesian coordinates, and also having a state defined by respective data associated with said coordinates, said system comprising:

means for transferring the data of each cell to a location having transformed coordinates representing a mapping of the cell'"'"'s Cartesian coordinates upon a log-spiral coordinate system;

means for shifting the locations of all said transformed coordinate cell data by the same amount representative of a desired image dilation; and

means for re-transferring said shifted-coordinate cell data to locations with re-transformed coordinates representing a mapping of log-spiral coordinates upon a Cartesian coordinate system, to produce a digitized image signal representative of a dilated version of said original image.

29. An image-processing system for an image having a plurality of picture cells arranged in a Cartesian grid with equally spaced rows and columns of cells, and one of said cells being an origin, comprising:

means for digitizing said cells;

means for normalizing said cells to transfer said origin to a desired point of image rotation and/or dilation;

means for transferring each of said cells having a Cartesian grid location defined by the complex number W=u+iv to a respective cell of a log spiral coordinate grid having a location defined by the complex number Z=e^W ;

means for shifting said latter cells vertically by an amount corresponding to desired image rotation;

means for shifting said latter cells horizontally by an amount corresponding to a desired image dilation;

means for re-transferring said shifted cells to respective corresponding locations in said Cartesian grid;

means for denormalizing said cells to transfer said point of image rotation and/or dilation to said origin; and

means for displaying said denormalized cells to provide an image which is a rotated and/or dilated version of said original image.

30. A two-dimensional shift register comprising:

a plurality of storage elements allocated to N columns and M rows, each of said columns containing M of said storage elements and each of said rows containing N of said storage elements;

a first one of said rows being designated as an uppermost row, and an Mth one of said rows being designated as a lowermost row;

a first one of said columns being designated as a leftmost column and an Nth one of said columns being designated as a rightmost column;

each of said storage elements being adapted to have data entered into or read out of said storage element;

means responsive to a first (e.g. "Shift Left") or a second (e.g. "Shift Right") predetermined signal for moving the data stored in each of said storage elements of certain columns to a corresponding one of said storage elements in the same row and a preselected number of columns closer to said "leftmost" column for said first signal or closer to said "rightmost" column for said second signal; and

means responsive to a third (e.g. "Shift Up") or fourth (e.g. "Shift Down") signal for moving the data stored in each of said storage elements to a corresponding one of said storage elements in the same column and a preselected number of rows closer to said "uppermost" row for said third signal or closer to said "lowermost" row for said fourth signal.

31. A two-dimensional shift register in accordance with claim 30 further comprising:

means responsive to said third signal for moving the data contained in each of said storage elements of said "uppermost" row to a corresponding one of said storage elements in the same column and a preselected number of rows from, said "lowermost" row; and

means responsive to said fourth signal for moving the data contained in each of said storage elements of said "lowermost" row to a corresponding one of said storage elements in the same column and a preselected number of rows from, said "uppermost" row.

32. A two-dimensional shift register in accordance with claim 31 further comprising:

means responsive to said second signal for storing into each of said storage elements of said "leftmost" column the data which was contained in that storage element previous to the activation of said second signal.

33. A two-dimensional shift register in accordance with claim 31, further comprising:

means responsive to the activation of said first (e.g. "Shift Left") signal for resetting to zero each of said storage elements of said "rightmost" column.

34. Apparatus for performing transformations upon an image which is displayable within an image space which is divided into a plurality of picture cells arranged in a predetermined pattern for displaying in each cell a portion of said image, comprising:

means for generating one or more control signals;

a two-dimensional shift register including a plurality of storage elements arranged in N columns and M rows of said shift register, each of said columns containing M of said storage elements and each of said rows containing N of said storage elements, said register also including

means for storing data representing the portion of said image displayable by each cell into the corresponding storage element or for reading data out of said storage elements,

means responsive to a first one (e.g. SHIFT LEFT) of said control signals or a second one (e.g. SHIFT RIGHT) of said control signals for moving the data stored in each of said storage elements to a corresponding storage element in the same row and a preselected number of columns to the left or to the right, respectively,

means responsive to a third one (e.g. SHIFT UP) of said transformation signals or a fourth one (e.g. SHIFT DOWN) of said transformation signals for moving the data stored in each of said storage elements to a corresponding storage element in the same column of storage elements and a preselected number of rows up or down, respectively; and

means for displaying a transformed image including means for activating each of said picture cells in a predetermined manner responsive to the data stored in its corresponding ones of said storage elements.

35. Apparatus in accordance with claim 34 wherein:

said picture cells are arranged as a Cartesian grid comprising equally spaced rows and columns of said cells, one of said cells comprising an origin point of said grid;

each one of said columns of cells corresponding to one of said columns of storage elements of said two-dimensional shift register; and

each one of said rows of cells corresponding to one of said rows of storage elements of said two-dimensional shift register.

36. A method of processing an image comprising the steps of:

deriving from the image a plurality of representative image cells; and

arranging representations of said cells in a concurrent manner in accordance with a predetermined pattern to produce a geometrically transformed version of the image, successive geometric transformations of the image being congruent irrespective of changes in scale or angular orientation of the image.

37. A method as in claim 36 wherein said pattern is derived from a cartesian lattice by a complex logarithmic transformation.

43. A method as in claim 36 or 38 further including the steps of:

producing signals representative of a transformed version of a template of said image with selected scale and selected rotational orientation;

shifting one of said transformed versions in simulation of incremental scale and rotational changes of said image until said shifted transformed version matches the other transformed representation match, whereby the nature of said shift is indicative of the scale and orientational relationship between said template image and said original image.

44. A method as in claim 43 wherein said image is derived from each of a plurality of geometrically similar physical objects of random orientations, and further comprising the step of:

orienting each said physical object in accordance with said scale and orientational relationship, to provide a uniform orientation for said objects.

38. A method of processing an image comprising the steps of

producing a plurality of picture cells representative of said image;

and

converting said cells in a concurrent manner into respective transformed cells representative of a transformed version of said image which transformed version is invariant in size and shape with respect to dilations and rotations of the image to be processed.

39. A method as in claim 38 wherein said converting comprises deriving the location of each of said transformed cells from that of an original cell by a complex logarithmic transformation.

40. A method as in claim 39 wherein said transformation is from a cartesian grid to an exponential ray/ring grid.

41. A method as in claim 39 wherein said transformation is from a skewed cartesian grid to a grid formed by orthogonal logarithmic spirals.

42. A method as in claim 39 wherein said transformation is from an equilateral triangular lattice to a lattice of angularly related logarithmic spirals.

45. A method of processing an image represented by a plurality of picture cells arranged in a Cartesian coordinate system comprising the steps of:

converting the locations of said cells to corresponding locations in a logarithmic spiral coordinate system;

shifting the locations of all said converted cells in a concurrent manner by an amount representing a desired rotation and/or translation of said image being processed; and

deriving an image-producing signal from said shifted cells.

46. A method for processing an image represented by a plurality of picture cells arranged in a Cartesian coordinate system comprising the steps of:

converting the locations of said cells to corresponding locations in a ray and exponentially spaced ring coordinate system; and

shifting the locations of all said converted cells in a concurrent manner by an amount representing a desired rotation and/or translation of said image being processed; and

deriving from said shifted cells an image producing signal.

47. A method for processing an image represented by a plurality of picture cells arranged in a log-spiral coordinate system comprising the steps of:

shifting the locations of all said picture cells in a concurrent manner by a fixed amount representing desired image rotation and/or dilation; and

converting said shifted cells to a Cartesian coordinate system for producing an image-producing signal representing a rotated and/or dilated version of said image.

48. A method as in claim 47 wherein said shifting is performed horizontally on all picture cells by a fixed amount representing desired image dilation, for producing a signal representing a dilated version of said original image.

49. A method as in claim 47 wherein said shifting is performed vertically on all said picture cells by a fixed amount representing a desired image rotation, for producing a signal representing a rotated version of said original image.

50. Data processing apparatus comprising:

a first set of data storage elements allocated respectively to the cells of a first (e.g. exponential ring and ray) coordinate grid;

a second set of data storage elements allocated respectively to the cells of a second (e.g. Cartesian) coordinate grid;

a data path coupling each storage element of said first set to the respective element of said second set having substantially the same coordinate values in said second coordinate grid as said first-set storage element has in said first coordinate grid;

said data paths being adapted to transmit data between each storage element and its respective coupled storage element; and

further data paths from each second-set elements having substantially the same value of either coordinate of said second-set storage element.