Position detecting method and apparatus

• US 4,547,800 A
• Filed: 03/02/1981
• Issued: 10/15/1985
• Est. Priority Date: 12/25/1978
• Status: Expired due to Term

• Current Assignee: Unimation, Inc. (Stäubli Holding AG)
• Original Assignee: Unimation, Inc. (Stäubli Holding AG)
• Inventors: Masaki, Ichiro
• Primary Examiner(s): Masinick, Michael A.
• Assistant Examiner(s): Coles, Edward L.
• Application Number:
  US06/239,621
• Time in Patent Office: 1,688 Days
• Field of Search: 358/93, 358/101, 358/106, 358/107, 358/105, 358/125, 358/126, 250/578, 356/400, 356/399, 364/559, 364/400, 364/474, 340/146.3 H, 340/146.3 Q, 382/30, 382/42
• US Class Current: 348/95
• CPC Class Codes: G01B 11/00 Measuring arrangements characterised by the use of optical techniques
• CPC Class Codes: G01B 11/022 by means of tv-camera scanning

Abstract

There is provided a method of detecting any positional deviation of a workpiece from a reference position with the aid of an image sensor. First, a sample workpiece is put at the predetermined position, and is detected by the image sensor to provide reference image information. Likewise, a workpiece under inspection is detected by the image sensor to provide workpiece image information. The reference information is subjected to a parallel transformation and/or rotation and is compared with the workpiece image which remains in the original state, to detect the correlation degree between the two sets of information. The detection of the correlation degree is repeated for each incremental parallel transformation and/or rotation of the reference information. The maximum correlation degree is selected from among the accumulated correlation degrees, whereby the positional deviation of the workpiece, if any, from the reference position is represented by the amount and the direction of the parallel transformation and/or rotation which give the maximum correlation degree.

Claims

1. Apparatus for detecting the positional deviation of an object with respect to a reference position comprising:

means for storing data representing a reference image in a data array format of data elements with the object at a reference position;

object image storing means for acquiring and storing data representing an image of the object in a data array format of data elements;

means responsive to said stored data in said reference image storing means and said object image storing means for comparing respective corresponding portions of said reference image and said object image on a data element by data element basis at a predetermined number of shifted positions of said reference image with respect to said object image to obtain the correlation between said data at said shifted positions, said comparing means comprising means for serially reading out said reference image data elements and said object image data elements and means for simultaneously and in parallel calculating the correlation for each of said shifted positions; and

deviation detecting means for determining the shifted position at which the maximum correlation is obtained between said reference image and said object image, said shifted position at which the maximum correlation is obtained representing the deviation between said reference position and said object position, said deviation detecting means being responsive to said comparing means.

2. The apparatus of claim 1 wherein said shifted positions are incrementally displaced one from another in one or more direction defined by the coordinate axes of said object image.

3. The apparatus of claim 1 wherein said shifted positions are defined by incrementally displaced rotational shifts of said reference image with respect to said object image.

4. The apparatus of claim 1 wherein said reference image data array format of data elements are arranged in m columns and n rows, said object image data array format of data elements being arranged in M columns and N rows, where M is greater than m and where N is greater than n, said simultaneous and parallel calculating means further comprising a predetermined number of correlation accumulating means equal in number to M-m+1, said comparing means being operative over N-n+1 defined steps of operation, said serially reading out means being operative to read out said reference image data and said object image data in a serial manner row by row during each of said defined steps of operation, each of said correlation accumulating means after each defined step of operation including a correlation value for a different shifted position of N-n+1 total shifted positions representing the incremental shifting of said reference image by 1 column, each of said defined steps of operations representing the incremental shifting of said reference image by one row.

5. The apparatus of claim 1 wherein said shifted positions are defined by parallel transformation and rotation of said reference image with respect to said object image.

6. The apparatus of claim 1 further comprising means for controlling said serially reading out means to successively read out said reference image data elements and predetermined elements of said object image data elements, each read out corresponding to said shifted positions of said refrence image with respect to said object image along a first dimension of said object image data array format, each successive read out corresponding to different shifted positions of said reference image with respect to said object image at a different point along a second dimension of said object image data array format, said controlling means controlling said serially reading out means to read out said predetermined elements of said object image for each read out that correspond to the data elements overlaid by said reference image at each of said respective shifted positions for the respective read out.

7. The apparatus of claim 1 further comprising step control means for controlling operation of said comparing means in a predetermined plurality of defined steps of operation, said step control means controlling said serially reading out means to read out said reference image data elements once during each step and to read out a different predetermined portion of said object image data elements during each step, each step corresponding to a different position of said reference image with respect to said object image in a first direction and shifting of said reference image with respect to said object image in a second direction in a plurality of shifted positions.

8. The apparatus of claim 1 wherein each of said reference image data and said object image data are arranged in image frames being defined by respective predetermined frames having image data points arranged in a predetermined number of columns and a predetermined number of rows, each of said image data points including data representing the intensity of said respective image point.

9. The apparatus of claim 1 or 8 wherein said serially reading out means comprises means for reading out said complete reference image data in a serial fashion and for reading out a predetermined portion of said object image data in a serial fashion during a defined step of operation, said predetermined portion of said object image data being defined by the portion overlaid by said shifted positions of said reference image with respect to said object image that are compared by said comparing means in said defined step of operation of said apparatus.

10. The apparatus of claim 9 wherein said comparing means compares said reference image data with said object image data on an image point by image point basis such that each image point of said reference image and each image point of said predetermined portion of said object image are compared that correspond to respective overlying positions of said reference image and said object image defined by said shifted positions in said defined step of operation.

11. The apparatus of claim 9 wherein said comparing means is operated over a predetermined plurality of said defined steps of operation, in each step of operation said comparing means comparing said reference image and the overlied portions of said object image at a predetermined plurality of shifted positions along a first coordinate axis of said object image frame, in each successive step of operation said comparing means comparing said reference image and the overlied portion of said object image at a predetermined plurality of shifted positions different from said shifted positions of previous steps as defined along a second coordinate axis of said object image frame.

12. The apparatus of claim 1 wherein said simultaneous and parallel calculating means comprises shift register means having a plurality of stages for successively shifting data received at a data input, said read out reference image data being connected to said data input and said shift register means performing a data shift upon the occurrence of each serial data bit at said data input, said simultaneous and parallel calculating means further comprising correlation accumulating means responsive to the data in said plurality of stages of said shift register means and having an object data input connected to said serially read out object image data for accumulating a count representing the correlation between said compared reference image and said object image at each of said predetermined number of shifted positions.

13. The apparatus of claim 12 wherein said deviation detecting means comprises maximum value detector means responsive to said correlation accumulating means for comparing each of said correlation counts and for outputting shift data representing the incremental shift between said reference image and said object image that results in the maximum correlation count accumulated by said correlation accumulating means.

14. The apparatus of claim 13 wherein said data reading out means further comprises means for reading out said reference image data once during a defined step of operation and for reading out the portion of said object image data that corresponds to the object image portions overlied by said reference image over said predetermined number of shifted positions during a defined step of operation, said correlation accumulating means simultaneously accumulating said correlation count for each of said predetermined number of shifted positions during a defined step of operation.

15. The apparatus of claim 14 wherein said object image acquiring means is operative to acquire a plurality p frames of object image data, said maximum value detector means being operative to successively output shift data representing the shifted positions resulting in the maximum correlation value over said plurality of defined steps of operation for each of said plurality of object images, said apparatus further comprising median value detector means responsive to said maximum value detector means for generating an output representing the shifted position equal to the median value of said plurality of maximum correlation values for said plurality of object images.

16. The apparatus of claim 14 wherein said correlation accumulating means comprises double shifting mode control means for operating said apparatus to determine an approximate maximum correlation count in a first shifting mode wherein each of said first shifting mode steps of operation corresponds to a shift in said second coordinate axis equal to a predetermined multiple number of incremental shifts nt where t is the incremental shift for a defined step of operation and n is the predetermined multiple, said double shifting mode control means further comprising second shifting mode means responsive to the maximum correlation count in said maximum value detector means for operating said apparatus in a second shifting mode wherein said second shifting mode steps of operation correspond to incremental shifts t, said shifting range of operation of said second shifting mode being equal to 2nt over 2n defined second shifting mode steps of operation centered about the shifted position corresponding to the approximate maximum correlation count obtained from said first shifting mode.

17. The apparatus of claim 14 wherein said apparatus is operable in a predetermined number of said defined steps of operation, each of said defined steps of operation corresponding to a predetermined number of shifted positions of said reference image with respect to said object image along a first coordinate axis of said object image, successive defined steps of operation corresponding to incrementally shifted positions of said reference image with respect to said object image along a second coordinate axis of said object image.

18. The apparatus of claim 17 wherein said maximum value detector means further comprises step means for determining the maximum correlation value obtained over said total number of defined steps of operation.

19. The apparatus of claim 14 or 17 wherein said correlation accumulating means further comprises a plurality of counter means equal in number to said number of shifted positions in each defined step of operations.

20. The apparatus of claim 19 wherein each of said counter means includes a first input connected to a corresponding respective one of said shift register stages and a second input connected to said output data input.

21. The apparatus of claim 20 wherein each of said counter means accumulates said correlation count for a corresponding respective one of said predetermined number of shifted positions.

22. The apparatus of claim 21 wherein each of said counter means is advanced in count whenever the inputted reference image data and the object image data exhibit a predetermined combinational binary relationship.

23. The apparatus of claim 22 wherein said maximum value detector means comprises current step comparator means for comparing the value of an input with a previously stored value and for storing the maximum value of said input value or said previously stored value and means for sequentially connecting the output of each of said counter means to said input of said current step comparator means.

24. The apparatus of claim 23 wherein said maximum value detector means further comprises total step comparator means for comparing said stored value in said current step comparator means for all of said defined steps of operation and for storing the maximum value.

25. The apparatus of claim 24 wherein said maximum value detector means further comprises first means for storing the number of said counter that corresponds to said stored maximum value in said current step comparator means and second means for storing the step number that corresponds to said maximum value stored in said total step comparator.

26. The apparatus of claim 25 wherein said counter number corresponds to said shift along said first coordinate axis and said step number corresponds to said shift along said second coordinate axis.

27. The apparatus of claim 1 further comprising valid object image checking means responsive to said object image data and a valid limit input for determining if the object image data represents a valid image capable of being accurately utilized by said apparatus to determine the maximum correlation and the deviation between said reference position and said object position.

28. The apparatus of claim 27 wherein said valid object image checking means comprises means responsive to said object image data storing means for accumulating the total count of image data points in said object image that have a predetermined binary intensity status and valid comparing means for comparing said valid limit input with said accumulated count, said valid comparing means comprising means for inhibiting correlation operation of said apparatus when said accumulated count exceeds said valid limit input.

29. A method of detecting any positional deviation of an object from a reference position with the aid of an image sensor, the method comprising the steps of:

obtaining reference image data of an object in a data array format of data elements representing the orientation of the object at a reference position;

obtaining object image data of the object by means of the image sensor in a data array format of data elements;

comparing respective corresponding portions of the object image data and the reference image data on a data element by data element basic at a predetermined number of shifted positions of the reference image relative to the actual image to obtain the correlation between the data at the shifted positions, said comparing step comprising the steps of serially reading out said reference image data and said object image data and simultaneously and in parallel calculating the correlation of said shifted positions; and

determining the shifted position at which the maximum correlation is obtained between said reference image and said actual image over said predetermined number of shifted and compared positions.

30. The method of claim 29 wherein said predetermined number of shifted positions are defined by parallel transformations and/or rotations.

31. A method of detecting any positional deviation of an object from a reference position with the aid of an image sensor, the method comprising the steps of preparing reference image information as data elements in a data array;

obtaining image information of the object as data elements in a data array by means of the image sensor;

subjecting one of said two sets of information to a plurality of linear, incremental parallel transformations in predetermined increments in at least two directions by serially reading out said data elements of said object and reference image information;

simultaneously and in parallel detecting the correlation degree between said two sets of information for each incremental parallel transformation in a first of said two directions by comparing respective overlaid data elements of said object and reference image information;

repeating said detecting step for each linear incremental parallel transformation in said second direction; and

selecting the maximum correlation degree from among the so obtained correlation degrees to determine the positional deviation of the object from the reference information on the basis of the amount and the direction of the parallel transformation which gives the maximum correlation degree.

32. A method as set forth in claim 31 in which said reference information and said information of the object comprise a plurality of information bits and are converted into corresponding binary information, respectively, and one of the two sets of information thus treated is subjected to the parallel transformation and is compared bit by bit with the other set of binary information which remains in the original state to count the correlation degree determined by the positionally corresponding bits which are in the same predetermined condition in the two sets of binary information.

33. A method as set forth in claim 32 in which said predetermined condition is the binary number 1.

34. A method as set forth in claim 32 in which said predetermined condition is the binary number 0.

35. A method as set forth in claim 32 in which said predetermined condition is the binary number 1 or 0.

36. A method as set forth in claim 32 in which said image sensor is a television camera and said two sets of binary information each comprises a plurality of black-and-white picture elements, and in which said binary reference information is subjected to a parallel transformation and is compared with the binary image information of the object to detect, as the correlation degree, how many picture elements in the same coordinate positions are in the same predetermined optical condition.

37. A method as set forth in claim 36 in which said predetermined optical condition is only the white state.

38. A method as set forth in claim 36 in which said predetermined optical condition is only the black state.

39. A method as set forth in claim 36 in which said predetermined optical condition is either the white state or the black state.

40. A method as set forth in claim 32 or 36 in which the frame of the reference information is reduced by a predetermined maximum amount of the parallel transformation in each direction of the coordinate plane on which the reference information exists.

41. An apparatus for detecting the positional deviation of an object from a reference position comprising a first memory for storing binary reference image information;

first reading means for reading out the binary reference information from said first memory;

image sensor means for detecting an object to provide image information of the object into corresponding binary information to supply the binary information to a second memory;

second reading means for reading out the binary information of the object from said second memory;

means responsive to the binary reference image information from the first reading means and the binary image information of the object from the second reading means for simultaneously and in parallel calculating the correlation degree between the two sets of information as determined by a comparison of the corresponding binary information of said two sets of information represented by different shifted positions of said reference image information with respect to said object image information; and

means responsive to the correlation degree thus obtained for determining the positional deviation of the object from the reference position.

42. An apparatus as set forth in claim 41 wherein said second reading means further comprises second reading control means for successively reading out said object image information stored in said second reading means with each successive read out of the object image information starting from a different point of said object image.

43. An apparatus as set forth in claim 42 further including a third memory for storing a very large amount of reference information, third reading means for reading out one frame of reference information from said third memory to supply it to said first memory.

44. An apparatus as set forth in claim 41, 42 or 43 further including shift register means having one input adapted to receive the binary reference information through said first reading device, said shift register means having a plurality of stages, said calculating means including calculating units of the same number as the number of the stages of said shift register means, each calculating unit having a first input connected to the output of the corresponding stage of said shift register means and a second input adapted to receive the binary information of the object from said second reading device, said calculating units being effective to simultaneously calculate the correlation degrees corresponding to different incremental parallel shiftings of the reference information in accordance with the operation of said shift register means.

45. Apparatus for detecting the positional deviation of an object with respect to a reference position comprising:

means for storing data representing a reference image with the object at a reference position;

object image storing means for acquiring and storing data representing a plurality of images of the object;

means responsive to said stored data in said reference image storing means and said object image storing means for comparing said reference image and each of said object images at a predetermined number of shifted positions of said reference image with respect to each of said object images to obtain the correlation between said data at said shifted positions;

deviation detecting means for determining the maximum correlation value and the corresponding shifted position at which the maximum correlation is obtained between said reference image and each of said object images, said shifted position at which the maximum correlation is obtained representing the deviation between said reference position and said object position, said deviation detecting means being responsive to said comparing means; and

median value detector means responsive to said deviation detecting means for generating an output representing the shifted position determined by the median value of said plurality of said maximum correlation values for said plurality of object images.

46. The apparatus of claim 45 wherein said median value detector means comprises means for successively comparing said deviation of said shifted position for each of said object images at which the maximum correlation is obtained, for ordering each of said deviations in numerical order and for selecting and outputting the middle value of said deviations.

47. The apparatus of claim 46 wherein said deviation representing said shifted position includes two dimensions, said apparatus comprising median value detector means for each of said two dimensions.

48. Apparatus for detecting the positional deviation of an object with respect to a reference position comprising:

means for storing data representing a reference image in a data array format of data elements with the object at a reference position;

object image storing means for acquiring and storing data representing an image of the object in a data array format of data elements;

means responsive to said stored data in said reference image storing means and said object image storing means for comparing respective overlying portions of said reference image and said object image on a data element by data element basis at a predetermined number of shifted positions of said reference image with respect to said object image and for outputting the correlation value for each of said shifted positions representing the correlation between said data at said shifted positions; and

maximum value detecting means responsive to said correlation values for determining the shifted position at which the maximum correlation value is obtained and for outputting shift data representing the incremental shift between said reference image and said object image that results in said maximum correlation value, said shift data defining the deviation between said reference position and said object, said maximum value detecting means comprising means for sampling each of said correlation values, means for successively comparing each sampled correlation value with the highest previous sampled correlation value, means for storing said highest sampled correlation value and means for storing the shift data corresponding to said highest correlation value.

49. Apparatus for detecting the positional deviation of an object with respect to a reference position comprising:

means for storing data representing a reference image in a two dimension data array format of data elements with the object at a reference position;

object image storing means for acquiring and storing data representing an image of the object in a two dimension data array format of data elements; and

means responsive to said stored data in said reference image storing means and said object image storing means for comparing predetermined array size portions of said reference image and said object image at a plurality of shifted positions with respect to each other over said two dimensions in a first coarse mode of operation and a second fine mode of operation, said comparing means comprising means for outputting the correlation value for each of said shifted positions representing the correlation between said data at said shifted positions, said first coarse mode of operation including a first predetermined number of shifted positions mn over a full range of shifting of said reference image and said object image, where m corresponds to a number of positions in a direction along a first dimension of said object data array format and n corresponds to a number of equally spaced apart positions in a direction along the second dimension of said object data array format, where each of said n positions are spaced apart by q shifted positions of said reference image and said object image along said second dimension, said second fine mode of operation including a second predetermined number of shifted positions (2q+1)m of said reference image and said object image arranged about the shifted position of said first coarse mode of operation that results in the highest correlation value during said first mode of operation, said comparing means further comprising means for serially reading out said reference image data elements and said object image data elements and means for simultaneously and in parallel calculating the correlation for each of said shifted positions m along said first dimension in a defined step of operation, said apparatus further comprising step control means for controlling operation of said comparing means in n steps of operation in said first coarse mode and in 2q+1 steps of operation in said second fine mode.

50. Apparatus for determining the positional deviation of an object with respect to a reference position comprising:

means for storing data representing a reference image in a two dimensional array format of data elements with the object at a reference position;

object image storing means for acquiring and storing data representing an image of the object in a two dimensional array format of data elements; and

means responsive to said stored data in said reference image storing means and said object image storing means for comparing respective overlying portions of said reference image and said object image on a data element by data element basis and for outputting the correlation value representing the correlation between said data, said comparing means comprising double shifting mode means for comparing said data in a first shifting mode operation at a first predetermined number of shifted positions of said reference image with respect to said object image over a predetermined full range of shifted positions and outputting corresponding correlation values and for comparing said data in a second shifting mode of operation at a period predetermined number of shifted positions of said reference image with respect to said object image over a predetermined range of shifted positions defined about one of said first predetermined number of shifted positions; and

deviation detecting means responsive to said comparing means and said outputted correlation values during said first shifting mode operation for detecting the shifted position of said first predetermined number at which the highest correlation value is obtained and for determining the maximum correlation value during said second shifting mode operation and the corresponding shifted position representing the deviation between said reference position and said object position, said comparing means being responsive to said deviation detecting means during said second shifting mode operation to determine said one of said first predetermined number of shifted positions, each of said reference image data and said object image data being arranged in image frames having a predetermined number of data elements in a two dimensional array defined by two coordinate axes, said first and second predetermined number of shifted positions being along a first of said coordinate axes, said comparing means including means operative at each of said first predetermined number of shifted positions and each of said second predetermined number of shifted positions to compare said respective reference image data and said object image data simultaneously and in parallel over a predetermined number of shifted positions along said second coordinate axis.

51. Valid object image checking apparatus for image processor apparatus of the type that compares acquired object image data with stored reference image data comprising valid object image means responsive to the object image data and a valid limit input for determining if the object image data represents a valid image capable of being accurately utilized by the image processor apparatus, said valid object image determining means comprising means responsive to the object image data for accumulating the total count of image data points in the object image that have a predetermined binary intensity status and valid comparing means for comparing said valid limit input with said accumulated count, said valid comparing means comprising means for generating an image processor apparatus inhibit signal when said accumulated count exceeds said valid limit input.

52. Image processor apparatus for determining the positional deviation of an object with respect to a reference position comprising:

means for storing data representing a reference image in a data array format of data elements arranged in at least two dimensions with the object at a reference position;

means for storing data representing an image of an object in a data array format of data elements arranged in at least two dimensions;

means for comparing respective overlying portions of said reference image data and said object image data on a data element by data element basis at a predetermined number of shifted positions in said two dimensions of said reference image with respect to said object image to obtain the correlation between said data at each of said shifted positions, said correlation being defined by the sum of all individual comparisons of corresponding overlying data elements of said reference image and said object image at each of said shifted positions, said comparing means being operative over a predetermined number of steps of operation corresponding to n shifted positions in a first of said two dimensions of said arrays, said comparing means further comprising means operative during each step of operation to obtain the correlation between overlaid portions of said reference image data and said object image data for a predetermined number p of shifted positions in said second dimension, said comparing means further comprising means responsive to said p times n correlations to provide the shifted position in said two dimensions at which the correlation is maximum, said shifted position representing the deviation between said reference position and said object position, said comparing means further comprising means operative during each of said n steps of operation for shifting said overlying portion of said reference image and object image data elements and simultaneously and in parallel accumulating said correlations for each of said p shifted positions.

53. The image processor apparatus of claim 52 wherein said n shifted positions are equally spaced in said first dimension and said p shifted positions are equally spaced in said second dimension, said shifted position corresponding to the maximum correlation being defined by one of said n positions along said first dimension and one of said p positions along said second dimension.

54. The image processor apparatus of claim 52 further comprising means for serially reading out said reference image data bit by bit and row by row and means for simultaneously and synchronously serially reading out said object image data bit by bit and row by row, said comparing means further comprising shift register means having p stages for successively shifting data received at a data input, said read out reference image data being connected to said data input and said shift register means performing a data shift upon the occurrence of each serial bit, said comparing means further comparing correlation accumulating means having p stages, each of said p correlation accumulation stages being connected to be responsive to the data in a respective one of said p shift register stages, each of said p correlation accumulation stages having an object data input connected to said serially read out object information data, each of said p correlation accumulation stages accumulating a count representing the correlation between said reference image and said object image corresponding to a different one of said p shifted positions, said object image in said second dimensions having p data elements more than said reference image, said reference image data read out means and said object image data read out means being operative during each step n of operation to read out said respective reference image data of said object image data.

55. The image processor apparatus of claim 54 wherein said comparing means further comprises means responsive to said p correlation accumulator stages for determining over said n steps of operation the correlation accumulator stage that provides the maximum correlation count and the step n during which said correlation accumulation stage provided the maximum correlation count.

56. The image processor of claim 55 wherein said object image data includes n data elements more than said reference image data in said first dimension.

57. Apparatus for obtaining the deviation between a position represented by an object image from a reference image position, the object image and the reference image each being defined by an array of data elements in at least two dimensions, the object image array including a greater number of data elements than said reference image array in at least one dimension, the apparatus comprising:

object image read out means having stored therein said object image array for serially reading out said data elements defining said object image array;

reference image read out means having stored therein said reference image array for serially reading out said data elements defining said reference image array;

means responsive to said serial read-out data from said object image read out means and said reference image read out means for simultaneously and in parallel calculating the correlation values between said respective data elements of said reference image and said object image corresponding to a plurality of shifted positions of said reference image with respect to overlaid corresponding portions of said object image in said one dimension by comparing said respective data elements of said object image and said reference image; and

means responsive to said correlation values for detecting the deviation between said object image and said reference image on the basis of the shifted position that results in the maximum correlation value.

58. The apparatus of claim 57 wherein said correlation value calculating means comprises shift register means having said serially read out reference image data elements connected at a data input and a plurality of shift register stages equal in number to said plurality of shifted positions and correlation accumulator means responsive to said data in said shift register stages and said serially read out object image data elements, said object image read out means and said references image read out means being controlled by said comparing means to read out data on a data element by data element basis in a synchronous manner, said shift register means shifting data through said shift register stages by one shift upon the occurrence of each read out data element.

59. The apparatus of claim 57 wherein said object image array includes a larger number of data elements than said reference image array in said second dimension, said apparatus further comprising step means for operating said comparing means for a plurality of steps corresponding to different shifted positions corresponding to shifting of said reference image with respect to said object image in said second dimension.

60. The apparatus of claim 59 wherein said step means further comprises means for controlling the object image read out means to start the read out of said object image data elements corresponding to the overlied portions of said object image by said reference image for said different shifted positions in said second dimension for each of said steps of operation.

61. The apparatus of claim 57 further comprising coordinate rotating means for rotating said reference image array as stored in said reference image read out means.

62. The apparatus of claim 57 further comprising coordinate rotating means for rotating said reference image array relative to said object image array for storage as said image array data in one of said respective object image read out means or said reference image read out means.

63. Apparatus for detecting the positional deviation of an object with respect to a reference position comprising:

means for storing data representing a reference image in a data array format of data elements with the object at a reference position;

object image storing means for acquiring and storing data representing an image of the object in a data array format of data elements;

means responsive to said stored data in said reference image storing means and said object image storing means for comparing respective overlying portions of said reference image and said object image on a data element by data element basis at a predetermined number of shifted positions of said reference image with respect to said object image to obtain the correlation between said data at said shifted positions; and

deviation detecting means for determining the shifted position at which the maximum correlation is obtained between said reference image and said object image, said shifted position at which the maximum correlation is obtained representing the deviation between said reference position and said object position, said deviation detecting means being responsive to said comparing means, said comparing means comprising means for reading out said data from said reference image storing means and said object image storing means in a predetermined manner and means for comparing said read out data in a predetermined manner, said reference image data representing a reference image frame of elements arranged in m columns and n rows, said object image data representing an object image frame of elements being arranged in M columns and N rows, where M is greater than m and where N is greater than n, said data of each of said frames being read out and compared on an element-by-element basis, said comparing means further comprising a predetermined number of correlation accumulating means equal in number to M-m+1, said comparing means being operative over N-n+1 defined steps of operation, said data reading out means being operative to read out said reference image frame data and said object image frame data in a serial manner row by row during each of said defined steps of operation, each of said correlation accumulating means after each defined step of operation including a correlation value for a different shifted position of N-n+1 total shifted positions representing the incremental shifting of said reference image by 1 column, each of said defined steps of operations representing the incremental shifting of said reference image by one row.

64. Apparatus for detecting the positional deviation of an object with respect to a reference position comprising:

means for storing data representing a reference image in a data array format of data elements with the object at a reference position;

object image storing means for acquiring and storing data representing an image of the object in a data array format of data elements;

means responsive to said stored data in said reference image storing means and said object image storing means for comparing respective overlying portions of said reference image and said object image on a data element by data element basis at a predetermined number of shifted positions of said reference image with respect to said object image to obtain the correlation between said data at said shifted positions; and

deviation detecting means for determining the shifted position at which the maximum correlation is obtained between said reference image and said object image, said shifted position at which the maximum correlation is obtained representing the deviation between said reference position and said object position, said deviation detecting means being responsive to said comparing means, said comparing means comprising means for serially reading out said reference image data and for serially reading out said object image data bit by bit, and shift register means having a plurality of stages for successively shifting data received at a data input, said read out reference image data being connected to said data input and said shift register means performing a data shift upon the occurrence of each serial data bit at said data input, said comparing means further comprising correlation accumulating means responsive to the data in said plurality of stages of said shift register means and having an object data input connected to said serially read out object information data for accumulating a count representing the correlation between said compared reference image and said object image at each of said predetermined number of shifted positions.

65. A method for determining the shifted positions of a reference image with respect to an object image that results in the maximum correlation, each of the reference and object images being arranged in a respective data array format of data elements, the maximum correlation being defined by the accumulated data element by data element comparison of corresponding data elements of overlaid portions of the reference image and the object image, the method comprising the steps of:

serially reading out said reference image data elements and said object image data elements;

shifting and storing said serially read out reference image data elements at a number of shifted outputs equal in number to the desired number of shifted positions in one direction between the reference image and the object image;

comparing in parallel said shifted and stored reference image data elements with each of said serially read out object image data elements;

accumulating the results of the parallel comparisons of said comparing step at each of said shifted outputs; and

determining the shifted position that results in the maximum correlation as the number of the shifted output that provides the highest accumulated comparison count.

66. Apparatus for obtaining the positional deviation between the position of an object represented by an object image and the position of an object at a reference position represented by a reference image, the object image and the reference image each being defined by an array of data elements in two dimensions, the reference image array being defined by m columns by n rows of data elements, the object image array being defined by M columns by N rows of data elements, where M is greater than m and N is greater than or equal to n, the apparatus comprising:

object image serial read out means for serially reading out said data elements of said object image;

reference image serial read out means for serially reading out said data elements of said reference image;

parallel output serial shift register means including P stages where P=N-m+1 and being responsive to said reference image serial read out means for providing at the outputs of said P stages said serial read out reference image data elements and for successively shifting said serial read out reference image data as said data is serially presented;

counter means responsive to said object image serial read out means and said parallel output shift register means for accumulating the correlation degree of said object image and reference image data as determined by the comparison of the corresponding data elements of said reference image and said object image for different shifted positions of said reference image and corresponding overlaid portions of said object image, said counter means comprising means for comparing each of said respective outputs of said parallel output serial shift register means with said serial read out object image data elements and accumulating the results of each of said comparisons, the accumulated comparisons of each of said outputs of said parallel output serial shift register means with said serial read out object image data elements corresponding to the total correlation on a data element basis between said reference image array and overlied portions of said object image array at a different predetermined shifted position of said reference image array with respect to said object image array, the shifted position being defined by a shift in columns; and

means responsive to said counter means for determining the deviation of the position of the object from said reference position based on the maximum correlation count of said counter means.

68. A method of detecting any positional deviation between the position of an object represented by an object image and the position of an object at a reference position represented by a reference image, the object image and the reference image each being defined by an array of data elements in tow dimensions, the reference image array being defined by m columns by n rows of data elements, the object image array being defined by M columns by N rows of data elements, where M is greater than m and N is greater than or equal to n, the method comprising the steps of:

serially reading out said reference image data elements and said object image data elements on a one to one basis in time succession;

accumulating the correlation between said reference image array and said object image array corresponding to a predetermined number of shifted positions of said reference image array with respect to said object image array in a first direction by comparing said serially read out image data elements and said object image data elements, the correlation being defined and accumulated by the sum of all individual comparisons of corresponding overlaid data elements of said reference image array and said object image array at each of said shifted positions; and

determining the shifted position at which the maximum correlation is obtained between said reference image array and said object image array over said predetermined number of shifted positions,

said accumulating step including the step of serially shifting each serially read out reference imag data element through a plural stage register, the number of stages being equal to the number of shifted positions for which the correlation is obtained, the correlation for each shifted position in the accumulating step being accomplished by the step of summing the comparisons of the data contents of a respective register of said plural stage register with the serial read out object image data element, said shifting step through said plural stage register occurring on a one for one basis with said serial reading out of each reference image data element, said reference image data and said object image data being read out once for the accumulation of the correlation for said predetermined number of shifted positions.

69. The method of claim 68 wherein N is greater than n and further comprising the step of repeating said serially reading out step a number of times equal to the number of shifted positions in a second direction for which correlation is obtained between said reference image array and said object image array, each of said serial reading out steps starting at the same point of said reference image array and at a different point of said object image array, said determining step determining the shifted position at which the maximum correlation is obtained by comparing the correlation for all shifted positions in said first and second directions.

70. Apparatus for determining the shifted position of a reference image with respect to an object image that results in the maximum correlation, each of the reference and object images being arranged in a respective data array format of data elements, the maximum correlation being defined by the accumulated data element by data element comparison of corresponding data elements of overlaid portions of the reference image and the object image, the apparatus comprising:

means for serially reading out said reference image data elements and said object image data elements;

means for shifting and storing said serially read out reference image data elements at a number of shifted outputs equal in number to the desired number of shifted positions in one direction between the reference image and the object image;

means for comparing in parallel said shifted and stored reference image data elements with each of said serially read out object image data elements;

means for accumulating the results of the parallel comparisons at each of said shifted outputs; and

means for determining the shifted position that results in the maximum correlation as the number of the shifted output that provides the highest accumulated comparison count.

67. The apparatus of claim 70 where N is greater than n and further comprising control means for controlling said object image serial read out means and said reference image serial read out means to read out said respective reference image array and said object image array R times during R steps of operation, where R=N-n+1, each of said R steps corresponding to said counter means accumulating the correlation degree for shifted positions of said reference image array with respect to said object image array, the shifted position being defined by a shift in rows for each successive step, said control means further comprising means for starting the read out of object image data elements by said object image serial read out means at a different row for each successive step.