Obstacle detection using stereo vision

[0001] This application relates to a system and method for obstacle detection using stereo vision.

[0002] Monocular machine vision may offer limited capability in supporting obstacle detection for vehicles. An obstacle may be detected by identifying a monocular image feature that violates expected scene information. For example, monocular vision data may be used to potentially identify objects in a field that do not meet a soil image profile or a plant image profile as an obstacle. However, monocular vision data may be deficient in providing reliable identification of obstacles based on size, shape, depth, and other three dimensional geometric characteristics. Monocular machine vision tends to be over-inclusive or under-inclusive in obstacle identification because of the absence of three-dimensional data on the size and shape of a perceived obstacle. Further, the collection of monocular vision data is susceptible to distortion or inaccuracy arising from variations in illumination across a field of view. Although three-dimensional shape data of an object may be collected via a laser range finder that scans the surface of the object, the process may be too slow to be practical for vehicular navigation. Thus, there is need for an obstacle detection method and system that uses stereo vision to reliably identify obstacles.

[0003] In accordance with one aspect of the invention, a system and method for detecting an obstacle comprises determining a vegetation height of a vegetation canopy at corresponding coordinates within a field. An object height is detected, where the object height of an object exceeds the vegetation height. A range of the object is estimated. The range of the object may be referenced to a vehicle location, a reference location, or absolute coordinates. Dimensions associated with the object are estimated. An obstacle avoidance zone is established for the vehicle based on the estimated range and dimensions.

[0017] In accordance with one embodiment, FIG. 1 illustrates a detection system 11 for detecting an obstacle in a field of view around a vehicle. The detection system 11 comprises an image collection system 15 coupled to an image processor 20. In turn, the image processor 20 is coupled to a vehicular guidance system 32.

[0018] The image collection system 15 comprises a left imaging unit 10 and a right imaging unit 12 that are coupled to an image combiner 14 (e.g., an interlacer). The image combiner 14 may be coupled to an interface 16. The interface 16 provides a communications interface (or a data buffer) for the stereo vision data transmitted from the image collection system to the image processor 20. An imaging system controller 18 may control the optical characteristics of the left imaging unit 10, the right imaging unit 12, or the format of stereo vision data or image data outputted by the interface 16, for example.

[0019] The optical characteristics of the imaging units (10, 12) may include any of the following: the aperture of one or both imaging units (10,12), the effective or actual focal length of one or both imaging units (10,12), lens parameters of one or both imaging units (10,12), the sensitivity to luminance and frequency response of one or both imaging units or their components (e.g., charge coupled devices (CCD) or other detectors), resolution of one or both imaging units (10, 12) (e.g., expressed as number of pixels per image or pixel dimensions) and filtering of the output of one or both imaging units (10,12) for noise, optical distortion, chrominance distortion, luminance distortion, or for lighting variations (e.g., shade versus sunlight). The frequency response of one or both imaging units (10,12) may support the collection of images in the following frequency spectrum of the electromagnetic spectrum: humanly visible light, a portion of the visible light spectrum (e.g., red light spectrum, green light spectrum and blue light spectrum or other color portions of the humanly visible light spectrum), near-infrared frequency range, the infrared frequency range, and any combination of the foregoing frequency ranges.

[0020] The left imaging unit 10 and right imaging unit 12 gather a pair of raw stereo scene images of the object from spatially offset perspectives at a common time. The left imaging unit 10 and the right imaging unit 12 are offset by a fixed, known spatial amount, which may be referred to as the stereo baseline. The image combiner 14 combines the raw stereo scene images to produce composite image data or a composite data stream. For example, the composite data stream or stereo vision data may consist of alternating frames, alternating lines of frames, alternating words, bytes, bits, or data packets of left image data from the left imaging unit 10 and right image data from the right imaging unit 12. In one embodiment, the image combiner 14 comprises an interlacer that accepts an input of a left image data stream and a right image data stream and provides an output of an interlaced data stream that contains bytes from both the left image data stream and the right image data stream. The image collection system 15 supports synchronization of images collected from the left imaging unit 10 and the right imaging unit 12 such that images captured at the substantially the same time are associated with one another.

[0021] The image processor 20 comprises an image disparity module 22, a three dimensional image former 23, an object estimator 25, a pattern recognition module 21, and a communications interface 30. In one embodiment, the image disparity module 22 communicates with the three dimensional image former 23. In turn, the three dimensional image former 23 communicates with the object estimator 25, the pattern recognition module, 21, or both. The pattern recognition module 21 communicates with the communications interface 30. The communications interface 30 is an intermediary that manages communications between the image processor 20 and the vehicle guidance system 32.

[0022] In one embodiment, the image processor 20 facilitates the determination of a range of the object and the dimensions of an object. The image processor 20 is well suited for creating a three dimensional representation of the object or a scene based on the disparity map image and the stereo vision data.

[0023] The image disparity module 22 creates a disparity map image that represents disparity between the raw stereo scene images from the left imaging unit 10 and the right imaging unit 12. The three-dimensional image former 23 accepts an input of a disparity image or other stereo vision image data (e.g., interlaced data stream) of a scene (or object) and produces a three-dimensional representation of the scene (or object) as an output.

[0024] In one embodiment, the three dimensional image former 23 may create or form the three-dimensional image representation based on one or more of the following types of input data: the disparity image, raw left image data, and raw right image data, stereo vision data, and interlaced image data. The three-dimensional representation may comprise a constellation of data points that lie on the surface of the object (e.g., obstacle), a framework of planar patches or a grid that lie on the surface of the object, a rough block or cubic representation of the maximum dimensions of the obstacle, or another three-dimensional model of the object. The data points on the object, framework that models the object, or another three-dimensional model may be referenced to a position or location data for a moving or stationary vehicle, a stationary reference point, an absolute coordinate system, or otherwise.

[0025] The object estimator 25 may determine or estimate one or more of the following: (1) the range (depth 50) of the object from the image collection system 15 or with respect to the vehicle, (2) the three-dimensional dimensions of the object (e.g., width, depth and height), (3) two-dimensional dimensions of the object (e.g., width and length) and range to the object; (4) whether the object is stationary or moving, (5) velocity, acceleration, speed, or heading of the object relative to the vehicle or relative to a stationary reference point, and (6) an estimated center of mass or geometric center of the object. The range of the object may represent the distance between a surface point on the object and a reference point associated with the vehicle (e.g., a baseline of the imaging units (10, 12)).

[0026] In an alternative embodiment, the range of the object may represent the distance between a geometric center or center of mass of the object and the vehicle or a reference point associated therewith. In yet another alternate embodiment, the range of the object may represent the distance between the vehicle and some reference point that lies on or within the object.

[0027] The pattern recognition module 21 is associated with the object estimator 25 and the three dimensional image former 23. The pattern recognition module 21 may facilitate the identification of an object in a scene from stereo image data and the extraction of an object from background data within the stereo vision data based on one or more of the following: (1) color information (e.g., pixels or voxels) associated with the image, (2) luminance information (e.g., pixels or voxels) associated with the image, (3) three-dimensional shape data on the object, and (3) dimensions of the object. For example, an object may have a generally uniform color which is distinct from the background data or a particular luminance value of pixels that is distinct from the background data. A voxel refers to a volume pixel or pixel of a three-dimensional image.

[0028] The pattern recognition module 21 comprises an obstacle detection module 26 and row detection module 28. The obstacle detection module 26 detects an object height of an object that exceeds the vegetation height. The obstacle detection module 26 facilitates identification of one or more objects or obstacles within a scene, collected image data or collected stereo vision data. The row detection module 28 may facilitate identification of the positions of one or more rows of crops or cultivated plants within a field. In one embodiment, the row detection module 28 determines a vegetation height of a vegetation canopy at corresponding coordinates within a field.

[0029] For example, the obstacle detection module 26 may differentiate an object or obstacle from the background or remainder of an image by one or more of the following techniques: (1) comparing collected color parameters of pixels (or voxels) in an image or portion of an image to reference color parameters of pixels (or voxels) within one or more depth zones or a three-dimensional image, where the reference color parameters represent expected color parameters for an obstruction-free image, (2) comparing derivative collected data derived from collected color parameters to derivative reference data derived from the reference pixel color parameters, (3) comparing a detected image size to a reference object profile size (e.g., typical dimensions of animals, humans, trees, bushes, telephone poles, machines or vehicles) within one or more depth zones of a three-dimensional image. In one embodiment, to identify an object or obstacle in an image or scene around the vehicle, the obstacle detection module 26 may apply a data processing resources of the image processor 20 first to a candidate path plan of the vehicle and a safety clearance zone about the vehicle or such candidate path plan, and secondarily to the entire field of view of the image collection system 15.

[0030] The communications interface 30 communicates pattern recognition data, row location data, obstacle location data, obstacle avoidance data, object dimension data, and object range data to a vehicular guidance system 32.

[0031] The vehicular guidance system 32 is associated with a location-determining receiver 33, a path planner 35, and a vehicular controller 31. The location determining receiver 33 may comprise a Global Positioning System Receiver (e.g., GPS receiver) with differential correction that provides location data (e.g., instantaneous or real time location data) of the vehicle in terms of coordinates or otherwise.

[0032] The path planner 35 may consider the crop rows or planned crop rows to develop a path plan for the vehicle. The path planner 35 updates a candidate path plan 34 to obtain an actual path plan or obstacle-avoiding path plan 36 based on the presence, location, velocity and bearing of objects around the vehicle to avoid collisions between the vehicle and the object. In one embodiment, a vehicular guidance system 32 or path planner 35 establishes an obstacle avoidance zone for the vehicle based on the estimated range and dimensions of the object. In another embodiment, the vehicular guidance system 32 or path planner establishes an obstacle avoidance zone based the on estimated range of the object, dimensions of the object, and movement of the object. In still another embodiment, the vehicular guidance system 32 or path planner establishes an obstacle avoidance zone based the on estimated range of the object, dimensions of the object, and a candidate path plan 34.

[0033] The vehicular controller 31 may be associated with a braking system, a steering system, and a propulsion system to control the acceleration, movement direction, stopping of a vehicle, or general driving of the vehicle.

[0034] In one embodiment, the vehicle is permitted to travel in travel rows between the crop rows in a candidate path plan 34. The candidate path plan 34 may be interrupted, stopped, or changed based on one or more of the following: obstacle avoidance zone, row location data, obstacle location data, object dimension data, and object range data. In one embodiment, the row alignment may be sacrificed to avoid striking or running over an object such that the actual path plan 36 or obstacle-avoiding path plan 36 differs from the candidate path plan 34.

[0035] FIG. 2 is a method for detecting an obstacle in accordance with the invention. The method of FIG. 2 begins in step S96. Prior to step S96, the image collection system 15 collects one or more images (e.g., stereo vision data) of the field and makes the image or images available to the image processor 20.

[0036] In step S96, an image processor 20 or obstacle detection module 26 identifies an object in a field by analyzing one or more images in color space. The object is extracted from or distinguished from the background of the image in color space by applying one or more of the following techniques to the image or a portion of an image: color differentiation, color histogram analysis, probability density function analysis, and edge analysis in an image region within the boundaries of the object and immediately outside the boundaries of the object. In one embodiment, to differentiate obstacles from the background of the image or scene, the obstacle detection module 26 may apply a data processing resources of the image processor 20 first to a candidate path plan of the vehicle and a safety clearance zone about the vehicle or such candidate path plan, and secondarily to the entire field of view of the image collection system 15.

[0037] In step S96, a collected derivative data set of the collected image is compared to a reference derivative data set of a reference image. In one embodiment, the collected derivative data set may represent a probability density function or a color histogram analysis applied to a collected image or a portion thereof. For example, the reference derivative data set of a reference image is defined as a probability density function of color parameters (e.g., color, tone, hue, or intensity) or color histogram of color parameters derived from a reference image that may be collected from the obstacle-free portion of a field (or obstacle-free field) in question with a substantially similar color palette or presence of a particular crop (e.g., corn or soybeans) at a particular growth stage (e.g., early season, mid-season, or mature-harvest time) with defined illumination characteristics (e.g., full sun, partly cloudy, overcast). The particular crop type, growth stage, and defined illumination characteristics of the reference image are preferably substantially similar to those applicable to the subject field at the collection time of the images.

[0038] The reference image may be obtained in accordance with one or more techniques that may be applied individually or cumulatively. Under a first technique, a reference image is collected of the present subject field when the present subject field is in a known state that is free of all obstacles (e.g., people, animals and machines.) Under a second technique, a reference image is selected from a library of reference images based on one or more of the following: the type of crop, planting date of the crop, historic weather data, cloud cover data, illumination data, crop inputs, and geographic location or zone. For example, the reference derivative data set for a mid-season corn field may provide a substantially uniform color attributes to be used generically in many different fields.

[0039] In step S96, the image processor 20 or the obstacle detection module 26 determines differences or correlation between the collected derivative data set and the reference derivative data set to identify the presence of an object or obstacle in (pixels or voxels of) the collected image with one or more colors or color attributes that are sufficiently distinct from the obstacle-free image or obstacle-free portion of the field. Where a portion of the (pixels or voxels) of the collected image has colors that do not match or are not sufficiently correlated to the reference image, the object is identified as present. In one embodiment, the image processor 20 or obstacle detection module 26 identifies the outline, object boundary, or edges of the object by distinguishing the interior color of the object from the background or a material color transition between the boundary of the object and the background through comparisons of groups of pixels or voxels in the region of the image.

[0040] Advantageously, in step S96 the application of color differentiation, color probability density function, histogram and edge analysis may be completed rapidly to identify objects in a structured environment, such as a field (e.g., a corn field). In one embodiment, to reduce computational time and data processing resources, the image processor 20 or obstacle detection module 26 limits the analysis of step S96 to any of the following: (1) a particular region of depth of a three-dimensional image, (2) a two dimensional depth slice of uniform depth of three-dimensional image, (3) an image (e.g., a two-dimensional image) from one of the imaging units (19 or 12).

[0041] In step S98, an image processor 20 or object estimator 25 estimates object height of the object identified in step S96. For example, if step S96 provides an estimated outline of the object through a color differentiation technique, the image processor 20 or object estimator 25 determines a maximum height of the object through selective stereo processing in the region of the object for the extraction of three-dimensional depth data.

[0042] In step S98, the image processor 20 or the three-dimensional image former 23 may apply selective stereo image processing in a limited region of the object where the outline, boundary, or edges of the object has a maximum height or dimension along the y axis. The depth (d) of the object is estimated by correlation of common data points in the limited region of the object in a left image and a corresponding right image of a stereo image. Once the depth is available, real world y data for a generally linear vertical strip within the limited region of the outline, boundary or edges of the object may be computed by reference to either the right image or the left image. The real world y data provides an estimate the maximum height of the object. By processing only a limited region or generally linear vertical strip within the outline, boundary or edges of the object, the data processing resources are minimized and time reduced to practice the method of FIG. 2.

[0043] In an alternate procedure for carrying out step S98, the image processor 20 may use field-of-focus processing, instead of stereo vision techniques to estimate depth information or other three-dimensional information in a scene. Field-of-focus processing may be used to rapidly estimate a depth or three-dimensional location of the object. For example, an image processing unit (10 or 12) takes one or more images from the same location or approximately the same location with different focus or lens adjustment of the imaging unit (10 or 12) and the image processor 20 determines the real word depth of an object from the lens based on distance of the of the focused image of the object from the lens and the focal length of the lens associated with the imaging unit (10 or 12).

[0044] In step S100, a vegetation height or top surface of a vegetation canopy is determined at corresponding coordinates or locations within a field. For example, the image collection system 15 collects one or more images indicative of the vegetation height of the vegetation canopy at one or more locations throughout a field and the image processor 20 processes the collected image or images to determine the vegetation height. The top surface of the vegetation canopy refers to the generally planar or other area that intercepts vegetation heights at some or all locations throughout the field. The vegetation height may be clustered around a mean value for each field or soil growing zone within a field for a particular crop variety that is treated with the same crop inputs, for example. The mean value of the vegetation height may be extracted from as few as one image, or mean values of the vegetation height may derived from multiple images. In one embodiment, each mean value may be associated with corresponding coordinates or a location within a field.

[0045] In step S100 the image processor 20 determines a vegetation height or top surface of a vegetation canopy through one or more of the following techniques, which may be applied separately or cumulatively: (1) identifying a crop height at an edge of the field, (2) identifying a crop height at a transition edge between a harvested and unharvested crop (e.g., by fitting a step function to pixels of an image of the transition edge in color space (e.g., RGB space)), (3) identifying a crop height relative to one or more visual reference markers (e.g., optically readable yard sticks) with vertical measurements placed thereon and distributed throughout a field, (4) identifying a generally planar surface or a top surface parallel to the ground without registering the height of the elevated surface above the ground, (5) an operator measuring a vertical height of the top of the crop to the ground level at various corresponding test points (e.g., with coordinates of test points determined by Global Positioning System with differential correction) in a field, and (6) an operator entering a vegetation height range, a maximum vegetation height, or a minimum vegetation height based on the crop type or horticultural practices. For instance, corn may be limited to a minimum and maximum height based on a particular variety of the corn; soybeans may be limited to a certain minimum and maximum height based on particular variety of soybeans; grape vines, apples or other fruit crops may be limited in height by pruning, genetics, or other horticultural practices.

[0046] In any of the above techniques for executing step S100, the image processor 20 or pattern recognition module 21 may distinguish the vegetation canopy from surrounding soil, sky, horizon, background, or weeds, or other materials by a color parameter (e.g., shade of green and the variation thereof) of the vegetation canopy from (1) one image of a stereo image, (2) a monocular image, or (3) one or more stereo vision images. The detected color parameter (e.g., detected color, tone, hue or tint or shade, and intensity, which may be defined in color space or otherwise) of a candidate “vegetation” pixel or voxel is compared against a reference color range (e.g., reference color range, tone range, hue, tint or shade range, and intensity range, which may be defined in color space or otherwise) for a particular crop or variety of crop to determine whether the candidate vegetation pixel or voxel qualifies as part of the vegetation canopy or not. The image processor 20 may execute such color comparisons or analysis in any color space, such as the RGB color space, YUV color space, or any other color space. The RGB color space allows red, green, and blue pixels to be combined additively to create other colors. In the YUV color space, Y represents the luminance component (e.g., brightness) and U and V are chrominance components. The U component represents a subtraction of the Y from the blue signal of the RGB signal, and V represents a subtraction of Y from the red signal of the RGB signal.

[0047] In step S102, an image processor 20 determines whether an object height of the object exceeds the vegetation height by a minimum threshold. The minimum threshold may be selected based upon the statistical variation or standard deviation of the ground level in a field, the statistical variation or standard deviation of a vegetation height in a field such that the highest points of the vegetation canopy or ground are not over-inclusively identified as objects or obstacles. The screening or filtering process of step S102 may be used to identify an object that has a material or significant height that may present an obstacle to the vehicle, as opposed to nuisance, an image artifact, or distortion and to efficiently use the processing resources of the image processor 20. If the object height of any object does not exceed the vegetation height (or top surface of the vegetation canopy) by more than a minimum threshold, the method continues with step S104. However, if the object height of any object does exceed the vegetation height (or the top surface) of the vegetation canopy by more than a minimum threshold, the method continues with step S106.

[0048] Step S102 is conducted in a stereo vision mode or any other three-dimensional technique that provides depth perception or depth estimation of the scene or obstacle.

[0049] In step S104, the image processor 20 or the obstacle detection module 26 may determine that no material obstacle is present in the volume above the vegetation height of the vegetation canopy. The finding of no material obstacle in step S104 may be subject to any qualifications based on sensor limitations, sensor specifications (e.g., sensor radiation pattern, field of view of the sensor, sensor sensitivity, or maximum reliable range) or other technical factors. For example, the volume above the vegetation canopy may be limited to the vertical field of view of the left imaging unit 10, the right imaging unit 12, or both.

[0050] In step S106, the object estimator 25 estimates range and dimensions associated with the screened object in accordance with a stereo vision data processing scheme. A screened object is an object that has an object height that exceeds a target height (e.g., vegetation height in accordance with the screening process of step S102) by a minimum threshold. A screened object has a material or significant height that may present an obstacle to the vehicle, as opposed to nuisance, an image artifact, ordistortion. Step S106 may be carried out in accordance with various techniques that may be applied alternately or cumulatively. Under a first technique, the object estimator 25 or image processor 20 estimates range and dimensions of an object in accordance with the procedure of FIG. 3. Under a second technique, the object estimator 25 or image processor 20 estimates range and dimensions of an object in accordance with the stereo imaging equations presented in conjunction with FIG. 4. The procedure of FIG. 3 and the equations presented in conjunction with FIG. 4 are described later herein, but such descriptions shall apply to FIG. 2 as if fully set forth in conjunction with step S106.

[0051] In an alternate embodiment for conducting step S106, the image processor 20 may estimate the range and dimensions of an object, by using field-of-focus processing instead of or in addition to the stereo vision data processing.

[0052] In step S107, the image processor 20 or classifier 29 classifies the object or obstacle based on the dimensions and compliance with a dimension reference profile. The image processor 20 or classifier 29 may facilitate the retrieval of dimension reference profiles from data storage, where such dimension reference profiles represent common obstacles, such as humans, animals, trees, bushes, machines, and vehicles. For example, a basic dimension reference profile might represent a range of expected height and a range of widths expected for humans, whereas a more complex reference profile might provide dimensions for a two dimensional or three dimensional expected side profile shape or an expected front profile shape.

[0053] In one embodiment, the dimension reference profile comprises one or more of the following: a height range and width range for a front human profile, a height range and width range for a side human profile, a height and width range for a front animal profile, a height and width range for a side animal profile, a height and width range for front of a machine, a height and width range for a side of a machine, a height and width range for a tree, a dimension range for a corresponding front outline of human, a dimension range for a corresponding side outline of a human, a dimension range for a corresponding front outline of an animal, dimension range for a front outline of a machine, dimension range for a side outline of a machine, and dimension range for a tree, a three dimensional model human profile, a three dimensional model animal profile, a three dimensional model tree profile, and a two-dimensional representation of an object associated with a uniform depth zone of a three dimensional representation of the object.

[0054] Step S107 may classify an observed object as compliant (e.g., matching) or non-compliant with a dimensional reference profile for a corresponding known object or object type. Step S107 works in conjunction with other steps of the method of FIG. 2, such as S96, S98, and S102, to identify reliably and accurately objects or obstacles in a field of view. Accordingly, step S107 contributes toward avoiding false positive and false negative determinations or observations of objects or obstacles that require evasive measures or changes to the candidate path plan 34 of the vehicle.

[0055] In step S108, an obstacle avoidance zone is established for the vehicle based on the estimated range and dimensions. For example, the path planner 35 may have a candidate path plan 34 that is updated to an obstacle-avoiding path plan 36 based on the estimated range and dimensions of the object or obstacle from step S106. The obstacle-avoiding path plan 36 is determined to avoid any possible collision between the object and the vehicle. If the object is stationary in the field of view of the image collection system 15, the image processor 20 may use a single frame or stereo image to provide sufficient information to avoid a collision. However, it is understood that if the object or obstacle is moving, the image processor 20 may need multiple frames or stereo images to identify the velocity (speed and direction) and acceleration or deceleration of such movement to effectively avoid a collision. FIG. 11 provides an illustrative example of three-dimensional obstacle avoidance zone and the description of FIG. 11 may be applied to step S108.

[0056] FIG. 3 is a flow chart that shows one possible technique for carrying out the process or step S106 of FIG. 2 in greater detail. Step S106 may include steps S200, S202 and S204 as shown in FIG. 3. The process of FIG. 3 begins in step S200.

[0057] In step S200, the image collection system 15 gathers (e.g., simultaneously gathers) a pair of raw stereo scene images of the object from spatially offset perspectives. The spatially offset perspective is preferably one in which the focal axis of the first imaging unit 10 and the second imaging unit 12 are separated by a known distance and orientation (e.g., fixed linear distance called stereo baseline b in FIG. 4).

[0058] In step S202, an image disparity module 22 or image processor 20 combines raw stereo scene images to produce a disparity map that represents disparity between the raw stereo scene images collected in step S200. The raw stereo images may be expressed as or converted into greyscale images as inputs to the disparity module 22. The disparity module 22 uses a disparity algorithm (e.g., correlation of common points in each raw stereo image or a sum of absolute differences applied to such common points) to form a disparity map based on a spatial relationship between each point in one raw stereo image its corresponding point in the other stereo image. The disparity module creates a disparity map for each pixel in one of the raw stereo scene images. The disparity map may be stored as a single greyscale image or a monochrome image in which disparity is a function of x and y in one raw stereo scene image or d (x,y), for example.

[0059] Stereo disparity (d) is inversely proportional to the depth of an object. The stereo disparity (d) is defined as d=bf/z, where b is the stereo baseline, f is the focal length of the imaging units (10 and 12), and z is the depth of an object from the imaging units (10 and 12). The disparity map is a representation that facilitates the removal of some redundant data from the two raw stereo images collected in step S200.

[0060] In step S204, the three dimensional image former 23 or the image processor 20 creates a three-dimensional representation of the object or the scene based on the disparity map image and at least one of the raw stereo scene images gathered in step S200. In one example for carrying out step S204, the three dimensional image former 23 may accept an input of the disparity map, which has information about x,y,d for the scene or an object, and map the x,y,d information to x,y,z coordinates for the scene or any object in the scene.

[0061] In another example for carrying out step S204, the three dimensional image former 23 extracts the three-dimensional map from the disparity map and at least one of the raw stereo scene images through (a) application of the stereo vision equations discussed in more detail in FIG. 4 to estimate the three-dimensional real world coordinates of the object from one or more perspectives of the vehicle and (b) construction of a surface model of the object based on the estimate of three dimensional world coordinates.

[0062] The construction of the surface model may use a grid of voxels that generally defines the three-dimensional shape of an object to form interconnect the nearest neighbor points with linear segments or tangent planar grids, for example. Although greater resolution of the surface model of the object is useful for object classification or the application of pattern recognition techniques, the surface model can be crude t produce a rapid navigation solution for obstacle avoidance of objects and detection or objects that are in motion.

[0063] FIG. 4 is an illustration of a typical representation of how three-dimensional information on an object is extracted from an image collection system 15 that collects stereo vision images. A right lens center 45 and a left lens center 44 are associated with the right imaging unit 12 and the left imaging unit 10, respectively. The right lens center 45 and left lens center 44 may represent central regions of the lenses of the imaging units. A dashed reference line, labeled “b” for stereo baseline b, interconnects the right lens center 45 and the left lens center 44. The first imaging unit 10 and the second imaging unit 12 are separated by a distance associated with the stereo baseline (b). The optical axes of each imaging unit is perpendicular to the stereo base line. An object is shown as a plant 48 here and is separated from baseline b by a depth 50. A group of points on the plant 48 may be expressed as three dimensional information that define the shape, size, and spatial dimensions of the object or plant 48.

[0064] The three-dimensional information may be represented in a Cartesian coordinate system, a polar coordinate system, a spherical coordinate system, or otherwise. As illustrated in FIG. 4, the three dimensional information is expressed in accordance with Cartesian coordinates. For example, the three dimensional information may include coordinate values (e.g., x, y, z) for each point on the surface of the plant 48. As illustrated in FIG. 4, the three dimensional information is referenced to an x-y image plane generally parallel to base line b of the imaging units (10 and 12). A z-axis is perpendicular to or normal to the x-y image plane.

[0065] The left image 40 and the right image 42 lie in the image plane (i.e., the x-y plane) in FIG. 4. The left image 40 represents a view of the object (e.g., plant 48 and surrounding image) from the perspective of the left imaging unit 10, which includes the left lens center 44. The right image 42 represents a view of the object (e.g., plant 48 and surrounding image) from the perspective of the right imaging unit 12, which includes the right lens center 45. The right image 42 lies behind the right lens center 45 by a focal length, designed f_r; the left image 40 lies behind the left lens center 44 by a focal length designated f_l. A left image coordinate system is defined on the left image plane as x_l, y_l. A right image coordinate system is defined n the right image plane, as x_r, y_r.

[0066] The three dimensional world coordinates of a point in a scene or on an object in the scene are as follows:

[0067] $x=\frac{b\left(x_l^{\prime }-x_r^{\prime }\right)}{2d},y=\frac{b\left(y_l^{\prime }-y_r^{\prime }\right)}{2d},\mathrm{and}$ $z=\frac{\mathrm{bf}}{d}$

[0068] where b is the stereo baseline distance between the optical centers of the two imaging units, d is the disparity, which is x′_l-x′_r, and f is the effective focal length of the imaging units for the case where f=f_r=f_l, x′_l is the x_l coordinate on the left image of the image plane corresponding to the point on the object, y′_l is y_l coordinate on the coordinate on the left image plane, x′_r is the x_r coordinate on the right image of the image plane corresponding to the point on the object, and y′_r is y_r coordinate on the coordinate on the right image plane. The z dimension is synonymous with the depth of a point on the object.

[0069] The above equations may be applied repeatedly as a vehicle equipped with the obstacle detection system 11 moves throughout a work area or its environment to capture a group of stereo scene images on one or more objects from different perspectives. As a vehicle moves additional stereo images may be used to extract further three-dimensional information on the same object. Accordingly, a three-dimensional reconstruction of the dimensions and range of object may be based on three dimensional image points calculated from different perspective locations of the vehicle and registered to a common reference or coordinate system with respect on one another. Registration of different stereo images taken from different positions may be accomplished by selecting portions of the scenes and matching for luminance or intensity of the pixels or voxels. Corresponding luminance values, and color values (e.g., in RGB color space, or otherwise) may be associated with each data point to form a voxel or another multidimensional representation

[0070] FIG. 5 is a flow chart of a method for detecting an obstacle. The method of FIG. 5 begins in step S300.

[0071] In step S300, a row detection module 28 or image processor 20 determines a corresponding position and contour of crop rows of a field. In one example for carrying out step S300, a disparity module 22 or image processor 20 may create a disparity map that can be used to identify the position and contour of crop rows in a field. In another example for carrying out step S300, a three dimensional image former 23 or the image processor 20 forms a graphical, mathematical, tabular, or database representation of the position and contour of the crop rows in the field.

[0072] In step S302, a path planner 35 establishes a path plan for a vehicle to travel in one or more travel rows interspersed among the crop rows. The defined crop rows of step S300 may form spatial boundaries for the travel rows.

[0073] In step S304, an image processor 20 identifies a ground level in a vegetation-free portion of the travel row. For example, the pattern recognition module 21 or image processor 20 may compare pixels or voxels in color space to determine whether a vegetation-free portion of the travel row is visible or present. One or more images (e.g., stereo vision data) of soil color parameters may be compared to reference soil color ranges to determine whether a vegetation-free portion of the travel row is visible or present.

[0074] In step S305, the obstacle detection module 26 or image processor 20 identifies an object in the vegetation-free portion of the travel row. For example, an image processor 20 or obstacle detection module 26 identifies an object in the vegetation-free portion of the travel row by analyzing one or more images in color space. The object is extracted from or distinguished from the background of the image in color space by applying one or more of the following techniques to the image or a portion of an image: color differentiation, color histogram analysis, probability density function analysis, and edge analysis in an image region within the boundaries of the object and immediately outside the boundaries of the object. In one embodiment, to differentiate obstacles from the background of the image or scene, the obstacle detection module 26 may apply a data processing resources of the image processor 20 first to a candidate path plan of the vehicle and a safety clearance zone about the vehicle or such candidate path plan, and secondarily to the entire field of view of the image collection system 15.

[0075] In step S305, a collected derivative data set of the collected image is compared to a reference derivative data set of a reference image. In one embodiment, the collected derivative data set may represent a probability density function or a color histogram analysis applied to a collected image or a portion thereof. For example, the reference derivative data set of a reference image is defined as a probability density function of color parameters (e.g., color, tone, hue, or intensity) or color histogram of color parameters derived from a reference image that may be collected from the obstacle-free, vegetation free portion of the travel row in question with a substantially similar color palette or presence of a particular crop (e.g., corn or soybeans) at a particular growth stage (e.g., early season, mid-season, or mature-harvest time) with defined illumination characteristics (e.g., full sun, partly cloudy, overcast). The particular crop type, growth stage, and defined illumination characteristics of the reference image are preferably substantially similar to those applicable to the obstacle-free, vegetation free portion of the travel row at the collection time of the images.

[0076] In step S98, an image processor 20 or object estimator 25 estimates an object height (e.g., a maximum height of the object). Step 98 was previously described in conjunction with FIG. 2 and such description applies equally to FIG. 5.

[0077] In step S306, an image processor 20 or object estimator 25 determines if an object in the travel row exceeds a threshold height above the ground level. For example, the image processor 20 or the object estimator 25 determines if the object exceeds a threshold height above the ground level through a stereo vision mode. In one embodiment, the image processor 20 or image disparity module 22 determines depth information for an object by reading a disparity image or by correlation between points on stereo images. The height information (e.g., actual or real world height) is obtained from the object in at least one of the raw stereo images (or stereo vision data) with reference to its depth.

[0078] If the object in the travel row exceeds a threshold height, then the method continues with step S106. However, if the object in the travel row does not exceed the threshold height, the method ends in step S308. In step S308, the image processor 20 determines that no obstacle or object is present in the volume above the ground level in the vegetation-free portion.

[0079] In step S106, an object estimator 25 estimates a range and dimensions associated with the object. Step S106 may be executed as described in accordance with the method of FIG. 2, FIG. 3 or the equations of FIG. 4 as previously described.

[0080] In step S108, the vehicular guidance system 32 or path planner 35 estimates an obstacle avoidance zone for the vehicle based on the estimated range and dimensions. Like reference numbers in FIG. 2 and FIG. 5 indicate like procedures or steps.

[0081] The method of FIG. 6 is similar to the method of FIG. 5, except the method of FIG. 6 replaces steps S304, S305, S306 and S308 with corresponding steps S400, S401, S402, and S404. Like reference numbers in FIG. 5 and FIG. 6 indicate like elements.

[0082] Steps S300 and S302 have already been described in conjunction with FIG. 5 and apply equally here to FIG. 6. Step S400 follows step S302.

[0083] In step S400, the image processor 20 identifies a weed canopy height in at least a portion of the travel row. The same techniques in step S100 of FIG. 2 that apply to the determining the vegetation height of the vegetation canopy apply of step to step S400 here, except that the row detection module 28 is used as a mask to digitally or virtually remove portions of the vegetation that lie within crop rows and are likely to be crops. Step S400 may also apply the pattern recognition module 21 or image processor 20 to conduct color differentiation in color space of pixels (or voxels) between the crop rows to determine if the vegetation color, shape, or dimensions are more consistent with the known vegetation color, shape or dimensional attributes of the crop, or weeds.

[0084] In step S401, the image processor 20 or obstacle detection module 26 identifies an object in a weedy portion of the travel row. For example, the pattern recognition module 21 or image processor 20 may compare pixels or voxels in color space to determine whether an object in weedy portion of the travel row is visible or present. One or more images (e.g., stereo vision data) in the weedy portion of the travel row may be compared to reference weed color ranges to determine whether an object is present in a weedy portion of the travel row.

[0085] In step S98, the image processor 20 or object estimator 25 estimates an object height (e.g., maximum height of the object.) Step 98 was previously described in conjunction with FIG. 2 and such description applies equally to FIG. 5.

[0086] In step S402, the image processor 20 determines if an object in the travel row exceeds a threshold height above the weed canopy height. The image processor 20 may be programmed and trained to recognize weed types by one or more of the following: color, appearance, and height range. For example, height ranges may be associated with different weed types comprising the weed canopy. If an object in the travel row exceeds a threshold height above the weed canopy height, the method continues in step S106. However, if the object in the travel row does not exceed a threshold height above the weed canopy height, the method continues in step S404.

[0087] In step S404, the image processor 20 determines that no obstacle is present in the volume above the weed canopy.

[0088] In step S106, the image processor 20 or object estimator 25 estimates a range and dimensions associated with an object. Following step S106, step S108 is executed. Steps S106 and S108 were already described in conjunction with FIG. 2 and such discussion applies with equal force to the method of FIG. 6.

[0089] FIG. 7A and FIG. 7B provide a typical representation of the collection of three-dimensional information. FIG. 7A is left image of a stereo pair and FIG. 7B is a right image of a stereo pair. The left image and the right image show a common scene at a generally simultaneous time and are separated by a known spatial distance. Although the scene may include any environment in which a vehicle (equipped with an obstacle detection system 11) may travel or be present, the scene shown in FIG. 7A and FIG. 7B is that of a corn field during mid season. FIG. 7 A and FIG. 7B are representative of an illustrative example of step S200 of FIG. 3.

[0090] FIG. 8 is a graphical representation of a disparity map that represents various disparities in the left and right images (of FIG. 7A and FIG. 7B) as shades of green color. The disparity map of FIG. 8 may be produced by processing the data from the left image and the right image of FIG. 7A and FIG. 7B as described in step S202 of FIG. 3, for example. Any shade of color could be used to represent the disparity and a greyscale might be used under circumstances where resolution permits.

[0091] In FIG. 8, the brighter the intensity represents the larger disparities and objects that are closer. The disparity decreases with distance away from the left imaging unit 10 and right imaging unit 12. As can been seen in the disparity image below, linear regions of higher disparity depict a row structure representative of row crops. Lower disparity regions are present between adjacent rows and are darker. Accordingly, the differential disparity of different pixels in the image can be used to extract row positions of row crops. The linear regions of the higher disparity may be used by the row detection module 28 to identify crop rows from stereo vision data. For instance, the linear regions of higher disparity might be applied to step S300 of FIG. 5 to determine the position and contour of crop rows in a field.

[0092] FIG. 9 shows a three-dimensional representation of the scene which may be produced from the disparity map of FIG. 8. The three-dimensional representation gives an X-Y-Z representation in Cartesian coordinates relative to the camera coordinate system. The coordinate system is determined in a calibration process. The three dimensional representation of FIG. 9 might be produced by application of the procedure described in step S204 of FIG. 3, for example.

[0093] The pattern recognition module 21 may apply pattern recognition to two dimensional image data, three dimensional image data, monocular vision data, or stereo vision data identify or isolate an object in a scene in any of the methods or embodiments discussed in this document. In particular, the pattern recognition module 21 may be applied effectively to a three-dimensional representation (e.g., the three dimensional representation of FIG. 9). For example, the pattern recognition module 21 may apply pattern recognition after the dimensions and range of an object are determined. In one embodiment, the image processor 20 or pattern recognition module 21 performs image processing on the three-dimensional representation of the scenes to classify scene characteristics for a vehicular guidance system 32. The three dimensional representation may be expressed as a series of two dimensional images (e.g., slices) that are stacked in memory or data storage and separated by known distances representative of a sampled real-world volume. The object may be classified into a classification (e.g., human being, vehicle, tree, rock, boulder, machine, telephone pole, tower or building) in accordance with rules that define the dimensions and shape of the object.

[0094] For simplification, consider the case where the x-coordinate of the scene are to the right from the camera, y-coordinate forward and z-coordinate upward. Furthermore, the ground plane in front of the vehicle is known to be at z=0. Also, crop vegetation planted in rows in the ground plane at a row spacing of 30 inches and the crop canopy is soybeans that reaches a maximum height of 24 inches. In this case, row-crop guidance information can be based on image processing in the coordinate system volume containing the crop. With appropriate image processing, the three dimensional voxels representing vegetation could be used to assess soybean canopy growth and development from the beginning of the season to the period of maximum growth. Obstacle detection occurs when there are objects that appear in the same scene that violate one or more measures of expectation of the crop canopy. For example, any object that stands out above the volume of expected crop growth would be a potential obstacle. With more advanced pattern recognition, the stereo images can be used to extract and label the scene characteristics.

[0095] FIG. 10 is another representation of the three dimensional cloud data that shows the ground surface and crop row features. FIG. 10 may be viewed as an alternate three-dimensional to representation of FIG. 9. The image processor 20 may process any three-dimensional representation disclosed hereunder, including those of FIG. 9 or FIG. 10, as described in conjunction with FIG. 9 or otherwise.

[0096] FIG. 11 is an illustrative graphical representation of a field-of-view volume 500 that contains an obstacle avoidance zone 506. A vehicle equipped with a obstacle detection system 11 may be situated at the vehicle point of view 502 facing inward, upward as illustrated in FIG. 11. The obstacle avoidance zone 506 is equal to or greater than the obstacle size and obstacle dimensions 504. Although the obstacle avoidance zone 506 may be coextensive with the three dimensional data points that define the physical shape and size of the obstacle, such an obstacle avoidance zone 506 may only reflect the instantaneous position of the obstacle and may need to be updated based on one or more of the following: obstacle path, obstacle heading, obstacle acceleration, obstacle velocity, and obstacle speed. Further, the obstacle avoidance zone 506 may be expanded to represent a greater volume about the physical obstacle to represent uncertainty in the stereo vision modeling or perception of dimensions, unexpected movements of the obstacle, or the like. In practice, the graphical representation of FIG. 11 may be expressed in Cartesian, polar, or spherical coordinates, in two or three dimensions. The graphical representation could be expressed in tabular format or in a database or as linear or curve equations.

[0097] The system and method disclosed herein overcomes certain limitations of monocular vision for machine perception; particularly, when applied to vehicle navigation and obstacle detection. First, stereovision is more illumination tolerant than approaches based on monocular vision. Second, stereovision is more insensitive to the effects of the growth and development of crops. Plant vegetation height creates perspective effects on monocular vision due to the uncertainty of range. The stereo pair recovers range information to remove this problem.

[0098] Third, monocular vision has not proven useful for obstacle detection except to look for image features that violate the expected scene information (e.g., look for objects that are not classified as a crop or classified as soil). Range information provided by stereovision can provide the additional dimensionality to allow for identification of obstacles based on size, shape, and other three dimensional geometric characteristics. Accordingly, the system and method of this invention facilitates a general-purpose perception sensor for vehicle guidance and navigation that is not possible with a monocular imaging system.

[0099] Having described the preferred embodiment, it will become apparent that various modifications can be made without departing from the scope of the invention as defined in the accompanying claims.