Position detecting method and apparatus

Claims

What is claimed as new and desired to be secured by Letters Patent of the United States is:

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 clai