System and method for calculating movement direction and position of an unmanned vehicle

• US 4,819,169 A
• Filed: 09/24/1987
• Issued: 04/04/1989
• Est. Priority Date: 09/24/1986
• Status: Expired due to Term

• Current Assignee: Nissan Motor Co., Ltd.
• Original Assignee: Nissan Motor Co., Ltd.
• Inventors: Saitoh, Hiroshi, Kurami, Kunihiko, Kishi, Norimasa, Noso, Kazunori
• Primary Examiner(s): LaRoche, Eugene R.
• Assistant Examiner(s): MIS, DAVID C
• Application Number:
  US07/100,581
• Time in Patent Office: 558 Days
• Field of Search: 364/424, 180/167, 180/168, 180/169
• US Class Current: 701/28
• CPC Class Codes: G05D 1/0246 using a video camera in combination with image processing means
• CPC Class Codes: G06T 7/73 using feature-based methods

Abstract

A system for calculating a movement direction and position of a movable object such as an unmanned vehicle running within a factory and a method therefor are disclosed in which an image pick up camera such as a video camera photographs a background of the movable object to generate a background two-dimensional image. Positions of vanishing point and side ends of a passage on which the movable object is to move are derived from the background photographed two-dimensional image. The movement direction of the movable object is derived from the detected vanishing point. Distances of the movable object from both sides ends of the passage are derived on the basis of the detected vanishing point and positions of side ends of the passage. the movement direction and position of the movable object thus detected are used to control movement of the movable object. The vanishing point is detected on the basis of edge directions at all points constituting and edge on the background two-dimensional image.

Claims

1. A system for calculating movement direction and position of a movable object, comprising:

(a) first means for photographing a background of the movable object in a direction of which the movable object moves;

(b) second means for detecting a vanishing point from a photographed background two-dimensional image derived by the first means;

(c) third means for detecting a position of an end of a passage on which the movable object is to move from the photographed background image derived by the first means;

(d) fourth means for calculating a direction of the movable object from a position of the vanishing point detected by the second means; and

(e) fifth means for calculating a distance of the movable object from the position of the passage end detected by the third means on the basis of the detected position of the passage end and vanishing point.

2. The system as recited in claim 1, which further comprises sixth means for controlling the movement direction and position of the movable object on the basis of the calculated forwarding direction and distance of the movable object by the fourth and fifth means.

3. The system as recited in claim 1, wherein the first means comprises a video camera having a lens of a focal distance (f) and the fourth means calculates the forwarding direction (θ

) the movable object using the following equation;

##EQU4## wherein q denotes a lateral size of a pixel of the photographed image when a longitudinal size of the pixel is denoted by p, X denotes an X-axis coordinate of the detected vanishing point when a Y-axis coordinate of the detected vanishing point is denoted by Y, and N denotes the number of pixels in the lateral direction of the photographed image when the number of pixels in the longitudinal direction thereof is denoted by M pixels.

4. The system as recited in claim 3, wherein the fifth means reads an X-axis coordinate (X_A) representing the position of the detected passage end on a lowermost stage line of the photographed image and calculates the distance (W₁) using the following equation:

##EQU5## wherein h denotes a height o the video camera with respect to a floor, ω

_r denotes a vertical picture angle of the video camera lens, and δ

denotes a depression angle of the video camera lens.

5. The system as recited in claim 4, wherein the third means detect the position of another end of the passage opposite to the end with respect to the movable object and wherein the fifth means another X-axis coordinate (X_C) representing the position of the detected other passage end on the lowermost stage line of the photographed image and calculates the distance (W₂) using the following equation:

##EQU6##

6. The system as recited in claim 2, wherein the movable object is an unmanned vehicle automatically moving from one working station to another working station in a factory.

7. The system as recited in claim 1, wherein the second means comprises:

(a) sixth means for extracting an edge information from the photographed image in the first means and calculating a direction of the edge;

(b) seventh means for generating a straight line on the basis of the edge direction calculated by the sixth means and accumulating the generated straight line to provide a straight line accumulated image; and

(c) eighth means for detecting a position as the vanishing point at which a maximum accumulated value is given from the accumulated straight line accumulated image.

8. The system as recited in claim 7, wherein the sixth means comprises:

(a) a longitudinal edge extracting part for extracting a longitudinal edge component from the photographed two-dimensional image;

(b) a lateral edge extracting part for extracting a lateral edge component from the photographed two-dimensional image;

(c) a fine linearizing processing part for linearing the edge extracted by the longitudinal and lateral edge extracting parts into a fine line;

(d) an isolation region eliminating part for eliminating an isolation region of image from the image after the edge is linearized into the fine line by means of the fine linearizing part;

(e) a first image memory for storing the image in which the fine linearization and isolation region elimination are carried out for the extracted longitudinal edge by the longitudinal edge extracting part;

(f) a second image memory for storing the image in which the fine linearization and isolation region elimination are carried out for the extracted lateral edge by the lateral edge extracting part; and

(g) an edge direction calculating part for calculating the edge directions for all points constituting the edge stored in the first and second image memories.

9. The system as recited in claim 8, wherein the longitudinal edge extracting part applies longitudinal edge extracting differential operators to the photographed two-dimensional image to derive a change in density values in the lateral direction of the photographed two dimensional image, carries out a density transformation for a data of the density value change, eliminates parts of the density-transformed density value change data which are weak in an edge intensity, and carries out a binary coding for the density-transformed density value change data whose parts weak in the edge intensities are eliminated to generate a binary-coded longitudinal edge image.

10. The system as recited in claim 9 wherein the lateral edge extracting part applies lateral edge extracting differential operators to the photographed two-dimensional image to derive a change in density values in the longitudinal direction of the photographed two dimensional image, carries out a density transformation for a data of the density value change, eliminates parts of the density-transformed density value change data which are weak in an edge intensity, and carries out a binary coding for the density-transformed density value change data whose parts weak in the edge intensities are eliminated to generate a binary-coded lateral edge image.

11. The system as recited in claim 10, wherein the fine linearizing processing part linearizes the longitudinal edge image and lateral edge image extracted by the longitudinal edge extracting part and lateral edge extracting part into the fine line and extract substantially center lines of the longitudinal edge image and lateral edge image each having a given width to take out edge information having a width of "1".

12. The system as recited in claim 11, wherein the isolation region eliminating part sets a mask having predetermined longitudinal and lateral lengths and replaces pixel values in the mask with all "0"s when pixel values on an outmost periphery of the mask are all "0"s.

13. The system as recited in claim 12, wherein the edge direction calculating part calculates a gradient of the edge at each pixel from the binary-coded and fine linearized longitudinal edge information and lateral edge information stored in the first and second image memories.

14. The system as recited in claim 13, wherein the seventh means comprises a straight line generating part which generates straight line having the gradient which corresponds to the gradient of the edge at each pixel calculated by the edge direction calculating part.

15. The system as recited in claim 14, wherein the seventh means generates the straight line through a given algorithm called a Digital Differential Analizer.

16. The system as recited in claim 14, wherein the seventh means further comprises a straight line accumulating part for adding "1" to an accumulated value before a passage point of the generated straight line so that the straight line is accumulated and a third image memory for storing the result of the accumulation of the straight line accumulating part.

17. The system as recited in claim 16, wherein the eighth means detects one of the passage points of the accumulated straight lines which has a largest accumulated value as the vanishing point.

18. The system as recited in claim 9, wherein the longitudinal edge extracting part applies the longitudinal edge extracting differential operators expressed as follows to the photographed two-dimensional image represented by h(x, y):

space="preserve" listing-type="tabular">______________________________________ "1" "0" "1" "2" "0" "2" "-1" "0" "1" ______________________________________

so that the result thereof is expressed as;

h (x+1, y+1) +2h (x+1, y)+h (x+1, y+1)-h (x-1, y+1) +2h (x+1, y)+h (x+1, y+1)-h )x-1, y+1)-2h (x-1, y)-h (x-1, y-1), thereby the density value change in the longitudinal (x-axis direction) direction of the photographed two-dimensional image h (x, y) can be derived, the density value change therein representing the intensity of the longitudinal edge within the photographed two-dimensional image.

19. The system as recited in claim 10, wherein the lateral edge extracting part applies the lateral edge extracting differential operators expressed as follows to the photographed two-dimensional image represented by h (x, y):

space="preserve" listing-type="tabular">______________________________________ "-1" "-2" "-1" "0" "0" "0" "1" "2" "1" ______________________________________

so that the result thereof is expressed as;

h(x-1, y-1) +2h (x, y-1)+h (x+1, y+1)-h (x-1, y+1)-2h (x, y+1)-h (x+1, y+1), thereby the density value change in the lateral (y-axis direction) direction of the photographed two-dimensional image h (x, y) can be derived, the density value change therein representing the intensity of the lateral edge within the photographed two-dimensional image.

20. The system as recited in claim 18, wherein each pixel of the photographed two-dimensional image derived from the first means has an eight-bit image information and the longitudinal edge extracting part carries out the density transformation for the data of the density value change in such a way that if an output after the application of the longitudinal edge extracting differential operators to the photographed two-dimensional image is F (x, y), the F (x, y) is transformed through the density transformation into F (x, y)=(F (x, y)+1024)/8.

21. The system as recited in claim 20, wherein the longitudinal edge extracting part eliminates predetermined parts in an edge intensity range which are represented by "120" to "136" after the density transformation by turning all density values of pixels which fall in the predetermined parts to "0"s.

22. The system as recited in claim 21, wherein the longitudinal edge extracting part carries out the binary coding with a predetermined threshold so as to generate the longitudinal edge image having a binary-coded level of either "0" or "1".

23. The system as recited in claim 21, wherein the edge direction calculating part derives the edge direction depending on whether one pixel value f (X, Y) at a coordinate value (X, Y) in the first image memory indicates "0" and one pixel value g (x, y) at the coordinate value (X, Y) in the second image memory indicates "1".

24. The system as recited in claim 21, wherein the edge direction calculating part derives the edge direction on the basis of one pixel value f (X, Y) at a coordinate value (X, Y) in the first image memory, one pixel value g (X, Y) at the coordinate value (X, Y) in the second image memory, and pixel values at coordinate values surrounding the coordinate value (X, Y).

25. The system as recited in claim 1, wherein the second means comprises:

(a) a longitudinal edge extracting part for extracting a longitudinal edge component from the photographed two-dimensional image;

(b) a lateral edge extracting part for extracting a lateral edge component from the photographed two-dimensional image;

(c) a fine linearizing processing part for linearizing the edge extracted by the longitudinal and lateral edge extracting parts into a fine line;

(d) an isolation region eliminating part for eliminating an isolation region of image from the image after the edge is linearized into the fine line by means of the fine linearizing part;

(e) a first image memory for storing the image in which the fine linearization processing and isolation region elimination processing are carried out for the longitudinal edge extracted by the longitudinal edge extracting part;

(f) a second image memory for storing the image in which the fine linearization processing and isolation region elimination are carried out for the extracted lateral edge by the lateral edge extracting part;

(g) an edge direction calculating part for calculating the edge directions for all points constituting the edge stored in the first and second memories;

(h) a vanishing point candidate calculating part for calculating vanishing point candidates using information on all points constituting the edge having the calculated edge directions;

(i) a histogram generating part for generating a histogram on a predetermined direction position of the calculated vanishing point candidates; and

(j) a vanishing point calculating part for determining the vanishing point position on the basis of the generated histogram.

26. The system as recited in claim 25, wherein the vanishing point candidate calculating part derives an intersection between a predetermined line and a straight line in the edge direction derived from each point constituting the edge as one of the vanishing point candidates, the histogram generating part generates the histogram representing a frequency distribution of intersections for all points constituting the edge, and the vanishing point calculating part determines a coordinate value of one of the intersections distributed in the histogram with respect to the frequency which gives a maximum frequency as the coordinate value of the vanishing points.

27. The system as recited in claim 26, wherein the predetermined line is on a horizontal direction of the edge information image in the edge direction calculating part.

28. A system for calculating movement direction and position of an unmanned conveying vehicle automatically moving within a limited space, the system comprising:

(a) first means for photographing a background of the limited space viewed from the unmanned vehicle in a direction of which the unmanned vehicle moves;

(b) second means for detecting a vanishing point from a photographed background two-dimensional image derived by the first means;

(c) third means for detecting positions of side ends of a passage on which the unmanned vehicle is to move from the photographed image derived by the first means;

(d) fourth means for calculating a moving direction of the unmanned vehicle from a position of the vanishing point detected by the second means; and

(e) fifth means for calculating each distance of the unmanned vehicle from the side ends of the passage detected by the third means on the basis of the detected positions of the side ends and vanishing point.

29. A method for calculating movement direction and position of a movable object within a limited space, the method comprising the steps of:

(a) photographing a background of the limited space viewed from the movable object in a direction of which the movable object moves;

(b) detecting a vanishing point from a photographed background image derived in the step (a);

(c) detecting positions of side ends of a passage on which the movable object is to move from the photographed image derived in the step (a); and

(d) calculating a moving direction of the movable object from a position of the vanishing point detected in the step (b) and each distance of the movable object from the side ends of the passage detected in the step (c) on the basis of the detected positions of the side ends and vanishing point.