BR112018005430B1 - SYSTEMS AND METHODS FOR DETECTING AREAS WITHOUT OBSTACLES - Google Patents

Abstract

SYSTEMS AND METHODS FOR DETECTING AREAS WITHOUT OBSTACLES. A method performed by an electronic device is described. The method includes performing vertical processing of a depth map to determine a vertical estimate of obstacle absence. The method also includes performing horizontal processing of the depth map to determine a horizontal obstacle absence estimate. The method further includes combining the vertical obstacle absence estimate and the horizontal obstacle absence estimate. The method further includes generating an obstacle absence map based on the combination of vertical and horizontal obstacle absence estimates.

Description

FIELD OF REVELATION

[0001] The present invention generally relates to electronic devices. More specifically, the present invention relates to systems and methods for detecting an obstacle-free area.

BACKGROUND

[0002] In recent decades, the use of electronic devices has become common. In particular, advances in electronic technology have reduced the cost of more complex and useful electronic devices. Cost reductions and consumer demand have proliferated the use of electronic devices so that they are practically ubiquitous in modern society. As the use of electronic devices has expanded, so has the demand for new and improved features of electronic devices. More specifically, electronic devices that perform new functions and/or that perform functions faster, more efficiently or with higher quality are often sought after.

[0003] Some electronic devices (e.g., cameras, video camcorders, digital cameras, cell phones, smart phones, computers, televisions, etc.) capture and/or use images. For example, a smart phone may capture and/or process video and/or video images. In automotive and autonomous vehicle applications, obstacle detection can be performed by processing an image. Processing images can require a relatively large amount of time, memory and power resources. The resources required may vary according to the complexity of the processing.

[0004] It may be difficult to implement some complex processing tasks. For example, some platforms may have limited processing, memory and/or power resources. Additionally, some applications may be time sensitive. As can be seen from this discussion, systems and methods that improve image processing can be beneficial.

SUMMARY

[0005] A method performed by an electronic device is described. The method includes performing vertical processing of a depth map to determine a vertical obstacle absence estimate. The method also includes performing horizontal processing of the depth map to determine a horizontal obstacle absence estimate. The method further includes combining the vertical obstacle absence estimate and the horizontal obstacle absence estimate. The method further includes generating an obstacle absence map based on the combination of vertical and horizontal obstacle absence estimates.

[0006] Performing vertical processing may include dividing the depth map into segments. At least one segment can include a number of pixels in a column. Linear model parameters can be estimated for at least one segment to determine the vertical obstacle absence estimate. A vertical reliability map that includes a reliability value for the vertical obstacle absence estimate can be generated.

[0007] Determining the vertical reliability map may include determining a segment fit error for a given segment based on a difference between estimated linear model parameters and predetermined linear model parameters. A reliability value for the given segment can be determined by comparing the segment fit error to a vertical estimate limit. The reliability value for the given segment can be applied to at least one pixel in the given segment.

[0008] Predetermined linear model parameters can be selected from a plurality of road condition models. The plurality of road condition models may have a corresponding set of linear model parameters.

[0009] Performing horizontal processing may include obtaining a depth histogram for at least one row of pixels of the depth map. A terrain line can be determined from the depth histogram. An estimate of horizontal obstacle absence can be determined based on a distance of a depth value of at least one pixel from the terrain line. A horizontal reliability map can be generated that includes a reliability value for the horizontal obstacle absence estimate.

[0010] Generation of the horizontal reliability map may include determining whether the depth value of a given pixel is within a range of a mode of the depth histogram. The given pixel can have a high reliability value when the depth value of the given pixel is within the range of the depth histogram mode.

[0011] The combination of vertical obstacle absence estimation and horizontal obstacle absence estimation may include performing vertical processing and horizontal processing in parallel. The vertical obstacle absence estimate and the horizontal obstacle absence estimate can be fused based on a vertical reliability map and a horizontal reliability map.

[0012] A given pixel can be identified as an obstacle-free area in the obstacle-free map where both the vertical reliability map and the horizontal reliability map are characterized by a high reliability value for the given pixel. A given pixel can be identified as an obstacle area in the obstacle-free map where at least one of the vertical reliability map or the horizontal reliability map is characterized by a low reliability value for the given pixel. A given pixel can be identified as an obstacle-free area or an obstacle-free area on the obstacle-free map based on a coordinate of the given pixel where the vertical reliability map and the horizontal reliability map are characterized by different reliability values for the given pixel.

[0013] The combination of the vertical obstacle absence estimate and the horizontal obstacle absence estimate may include performing vertical processing of the depth map. A vertical reliability map can be obtained based on a model fit confidence. The reliable regions of the vertical reliability map can be identified as areas of absence of obstacles. Horizontal processing can be performed on unreliable regions of the vertical reliability map to determine whether the unreliable regions are areas of absence of obstacles.

[0014] The combination of the vertical obstacle absence estimate and the horizontal obstacle absence estimate may include performing horizontal processing of the depth map. A horizontal reliability map can be obtained based on a depth histogram distance. The reliable regions of the horizontal reliability map can be identified as areas of absence of obstacles. Vertical processing on unreliable regions of the horizontal reliability map can be performed to determine whether the unreliable regions are areas of absence of obstacles.

[0015] Obstacle absence map can be used in identifying a region of interest used by at least one of an object detection algorithm or a lane detection algorithm.

[0016] An electronic device is also described. The electronic device is configured to perform vertical processing of a depth map to determine an estimate of vertical obstacle absence. The electronic device is also configured to perform horizontal processing of the depth map to determine an estimate of horizontal obstacle absence. The electronic device is further configured to combine the vertical obstacle absence estimate and the horizontal obstacle absence estimate. The electronic device is further configured to generate an obstacle absence map based on the combination of vertical and horizontal obstacle absence estimates.

[0017] An apparatus is also described. The apparatus includes means for performing vertical processing of a depth map to determine an estimate of vertical obstacle absence. The apparatus also includes means for performing horizontal processing of the depth map to determine an estimate of horizontal obstacle absence. The apparatus further includes means for combining the vertical obstacle absence estimate and the horizontal obstacle absence estimate. The apparatus further includes means for generating an obstacle absence map based on the combination of vertical and horizontal obstacle absence estimates.

[0018] A computer program product is also described. The computer program product includes a tangible, non-transitory computer-readable medium that has instructions thereon. The instructions include code to cause an electronic device to perform vertical processing of a depth map to determine an estimate of vertical obstacle absence. The instructions also include code to cause the electronic device to perform horizontal processing of the depth map to determine an estimate of the absence of a horizontal obstacle. The instructions further include code to cause the electronic device to combine the vertical obstacle absence estimate and the horizontal obstacle absence estimate. The instructions further include code for causing the electronic device to generate an obstacle absence map based on the combination of vertical and horizontal obstacle absence estimates.

BRIEF DESCRIPTION OF THE DRAWINGS

[0019] Figure 1 is a block diagram illustrating an electronic device configured to perform obstacle-free area detection;

[0020] Figure 2 is a block diagram illustrating an obstacle absence determination module;

[0021] Figure 3 is a flowchart illustrating a method for performing obstacle-free area detection;

[0022] Figures 4A -4D illustrate an example of vertical processing of a depth map;

[0023] Figure 5 is a flowchart illustrating a method for performing obstacle-free area detection using vertical processing;

[0024] Figures 6A -6D illustrate an example of a horizontal processing of a depth map;

[0025] Figure 7 is a flowchart illustrating a method for performing obstacle-free area detection using horizontal processing;

[0026] Figure 8 is a flow chart illustrating a method for combining a vertical obstacle absence estimate and a horizontal obstacle absence estimate to determine an obstacle absence map;

[0027] Figure 9 is a flowchart illustrating another method for combining a vertical obstacle absence estimate and a horizontal obstacle absence estimate to determine an obstacle absence map;

[0028] Figure 10 is a flow chart illustrating yet another method for combining a vertical obstacle absence estimate and a horizontal obstacle absence estimate to determine an obstacle absence map;

[0029] Figures 11A - 11B illustrate an example of determining areas of absence of obstacles in an image;

[0030] Figures 12A - 12B illustrate another example of determining areas of absence of obstacles in an image;

[0031] Figures 13A - 13B illustrate an example of determining distance from an obstacle-free area;

[0032] Figure 14 illustrates an example of using the obstacle absence map to identify a region of interest (ROI) used by an object detection algorithm;

[0033] Figure 15 illustrates an example of using the obstacle absence map to identify an ROI used by a lane detection algorithm;

[0034] Figure 16 is a flowchart illustrating a method for classifying a road based on estimated linear model parameters; It is

[0035] Figure 17 illustrates certain components that can be included within an electronic device.

DETAILED DESCRIPTION

[0036] In many applications, it is advantageous to identify non-object areas within a region or environment for obstacle avoidance. For example, with advanced driver assistance systems (ADAS), it is important to identify the actionable area in front of the car for obstacle avoidance. Another scenario in which obstacle avoidance is important is vehicular automation in which an autonomous vehicle (e.g., an unmanned aerial vehicle (UAV) or autonomous automobile) senses its environment and navigates without human input.

[0037] Typically, the obstacle avoidance problem is viewed from the other direction, where objects of interest (e.g., pedestrians, cars, bicycles) are detected and can be identified through object detection/recognition algorithms and alerts. are provided to the driver to take precaution. For example, obstacle detection can be used to detect and identify traffic signs (e.g. speed limit signs, stop signs, street signs, etc.), however, this approach can be slow and inaccurate. Furthermore, all object classes have to be trained in advance, which makes announcing new object classes difficult.

[0038] In the systems and methods described here, instead of identifying objects, regions are identified that are free from obstacles or objects. These regions can be referred to as mobile areas. In other words, these three-dimensional regions are areas of absence of obstacles in which movement is possible. For example, an obstacle-free area can be identified on a road. In identifying obstacle-free areas, various other applications such as road profiling, speed control, a faster and more reliable object, and lane detection can be performed using the obstacle-free area.

[0039] The systems and methods described here can be used to identify an obstacle-free area by analyzing a depth map. In one implementation, the depth map can be generated from a pair of stereo images. In a road scenario, the open space in front can be mapped to a linear model that describes the road in the depth domain. By using the depth of road segments, linear model parameters can be estimated. The estimated linear model parameters can be compared with previous ones (e.g. predetermined model parameters). If adjustment is achieved, then the segments are declared to be part of the open area. If a stereo image pair is not available, methods such as structure from motion can be used to obtain a depth map using a mono camera input sequence.

[0040] The systems and methods described here provide the determination of an obstacle absence map based on an intelligent combination of vertical processing and horizontal processing of one or more images. Systems and methods of identifying an obstacle-free area are explained in greater detail below.

[0041] Figure 1 is a block diagram illustrating an electronic device 102 configured to perform obstacle-free area detection. The electronic device 102 may also be referred to as a wireless communication device, a mobile device, mobile station, subscriber station, client, client station, user equipment (UE), remote station, access terminal, mobile terminal, terminal, user terminal, subscriber unit, etc. Examples of electronic devices include portable or desktop computers, cell phones, smart phones, wireless modems, e-readers, desktop devices, gaming systems, robots, airplanes, unmanned aerial vehicles (UAVs), automobiles, etc. Some of these devices may operate in accordance with one or more industry standards.

[0042] In many scenarios, the electronic device 102 may use an obstacle-free map 126 of a scene. In one example, a smart phone may generate an obstacle absence map 126 of a scene to identify unoccupied space. In another example, an automobile may include an advanced driver assistance system (ADAS) that may use an obstacle absence map 126 to regulate the automobile's speed, steering, parking, etc. based on detected traffic signals. signs and/or other objects. In another example, an unmanned aerial vehicle (UAV) may generate an obstacle-free map 126 from video recorded while in flight, may navigate based on detected objects (e.g., buildings, signs, people, packaging, etc.) , can capture and/or distribute a detected packet, etc. Many other examples can be implemented according to the systems and methods described here. For example, the systems and method disclosed herein could be implemented in a robot that performs one or more actions (e.g., Search for something, assemble something, search for an article, etc. 0) based on one or more detected objects using the obstacle absence map 126.

[0043] An electronic device 102 may include one or more cameras. A camera may include an image sensor 104 and an optical system 108 (e.g., lenses) that focuses images of objects that are located within the field of view of the optical system 108 onto the image sensor 104. An electronic device 102 may also include a camera software application and a display screen. When the camera application is operating, images 114 of objects that are located within the field of view of the optical system 108 can be recorded by the image sensor 104. These images 114 can be stored in a memory buffer 112. In some implementations, the camera may be separate from the electronic device 102 and the electronic device 102 may receive image data from one or more cameras external to the electronic device 102.

[0044] Although the present systems and methods are described in terms of captured images 114, the techniques discussed here can be used on any digital image. Therefore, the terms video frame and digital image can be used interchangeably here.

[0045] In many applications, it is beneficial for an electronic device 102 to identify areas that are free from obstacles. For example, in the case of ADAS, it is important to identify the actionable area in front of the car for obstacle avoidance. In some approaches, this problem is checked from the other direction. In these approaches, objects of interest (e.g. motors, bicycles, bicycles) are identified through object detection and recognition algorithms and alerts are provided to the driver to take precaution.

[0046] Other approaches can determine areas of absence of obstacles by performing either vertical processing or horizontal processing of an image 114. Each of the vertical processing and horizontal processing processes can estimate areas of absence of obstacle in an image 114 However, each approach has limitations when performed independently.

[0047] Horizontal processing may give an incorrect estimate of the absence of obstacles when a road is inclined. Vertical processing can perform segmentation on image 114. If the segments are large, then the adjustment is more reliable. However, parts of objects could be included as obstacle-free (i.e., obstacle-free) areas as well. For example, using vertical processing, the bottom and top of cars or pedestrians may be incorrectly identified as an obstacle-free area. Also, side lanes could be incorrectly identified as a non-obstacle area with the vertical processing approach. However, if the segments are small, inaccurate detection of the non-obstacle area may occur.

[0048] The systems and methods described herein provide for the determination of an obstacle-free map 126 based on an intelligent combination of vertical processing and horizontal processing of one or more images 114in the described Systems and methods, instead of identifying objects, a Obstacle absence map 126 can be determined by combining vertical processing and horizontal processing of a depth map. In one implementation, the depth map can be obtained from one or more images. In another implementation, the depth map may be obtained from a depth data acquisition process (e.g., LIDAR)

[0049] In one implementation, the electronic device 102 may include an obstacle absence determination module 116 for determining an obstacle absence map 126. The obstacle absence determination module 116 may include a depth map generator 118 to get a depth map. The obstacle absence determination module 116 may also include a vertical estimation module 120 for performing vertical processing of the depth map to determine a vertical obstacle absence estimate. The obstacle absence determination module 116 may further include a horizontal estimation module 122 for performing horizontal processing of the depth map to determine a horizontal obstacle absence estimate.

[0050] The estimate combiner 124 may combine the vertical obstacle absence estimate and the horizontal obstacle absence estimate to determine an obstacle absence map 126. In one implementation, the estimate combiner 124 may intelligently combine the estimate of absence of a vertical obstacle and the estimate of the absence of a horizontal obstacle based on the reliability values associated with the estimates. Obstacle-free map 126 may indicate which areas of one or more images 114 are obstacle-free areas and which areas are obstacle-free areas. More details on the generation of the obstacle absence map 126 are given in connection with Figure 2.

[0051] In one example, the obstacle-free map 126 may include obstacle-free areas that are free of obstacles (e.g., objects) on the roads. By combining vertical processing and horizontal processing of an image 114, false detections can be eliminated. Furthermore, a combined approach can provide a more reliable obstacle absence estimate.

[0052] The described systems and methods can be used to accelerate various other applications. For example, the electronic device 102 may use the obstacle absence map 126 for other applications such as object detection, scene understanding, road profile, and lane detection. The described systems and methods can also solve the problem of highway lane detection that current lane detection algorithms cannot handle. The systems and methods described can also help with autonomous drive, where speed is adjusted based on road terrain.

[0053] Figure 2 is a block diagram illustrating an obstacle absence determination module 216. The obstacle absence determination module 216 may be implemented within an electronic or wireless device. Obstacle absence determination module 216 may include a depth map generator 218, a vertical estimation module 220, a horizontal estimation module 222, and an estimation combiner 224. Obstacle absence determination module 216, obstacle generator depth map 218, vertical estimation module 220, a horizontal estimation module 222, and an estimation combiner 224 may be configurations of the obstacle absence determination module 116, the depth map generator 118, a vertical estimation module 120 , a horizontal estimation module 122 and an estimation combiner 124 described above in connection with Figure 1.

[0054] The depth map generator 218 may receive one or more images 214. In one configuration, the one or more images 214 may be obtained via a camera (e.g., an image sensor 104 and an optical system 108 ), as described in connection with Figure 1. In one implementation, the depth map generator 218 may receive a pair of stereo images. In another implementation, one or more images 214 may come from a mono video image. Image 214 may be a digital image consisting of pixels.

[0055] The depth map generator 218 may obtain a depth map 230 from one or more images 214. The depth map 230 may include pixels 232 corresponding to the pixels of the one or more images, each pixel 232 in the depth map 230 has a depth value of 234. The depth value of 234 indicates a distance of the pixel 232 relative to the camera. For example, a pixel 232 with a greater depth value 234 may indicate closer proximity to the camera than a pixel 232 with a lower depth value 234. An example of a depth map 230 is discussed with respect to Figures 4A - 4 D.

[0056] It should be noted that the algorithm described here does not require a depth value 234 for each pixel 232. For example, the depth map 230 may have holes. The depth value 234 of these holes can be filled before starting processing.

[0057] In the case of a stereo image pair, the depth map generator 218 may find the correspondence between the pixels 232 to estimate a disparity. From the disparity, the depth map generator 218 can determine the depth value 234 for each pixel 232. Alternatively, with a mono video image, the depth map generator 218 can determine the depth value 234 for each pixel 232 with based on the movement of the video.

[0058] The depth map 230 may be provided to the vertical estimation module 220 and the horizontal estimation module 222. The vertical estimation module 220 may perform vertical processing of the depth map 230 to determine a vertical obstacle absence estimate 242. The horizontal estimation module 222 may perform horizontal processing of the depth map 230 to determine a horizontal obstacle absence estimate 258.

[0059] The vertical estimation module 220 may divide the depth map 230 into segments 236. Each segment 236 may include a number of pixels 232 in a column of the depth map 230. In other words, the vertical estimation module 220 may process vertical segments 236 of depth map 230. A segment 236 may be a portion of a column of pixels 232 in depth map 230. For example, segment 236 may be a vector of 10-15 pixels 232. Segments 236 may or not overlap.

[0060] The vertical estimation module 220 can estimate linear model parameters for each segment 236 to determine the estimated absence of vertical obstacle 242. Each segment 236 in the vertical direction can be estimated through a linear model. The linear model can be expressed as where y is the depth value 234 of a pixel 232, x is the coordinate of the pixel 232, and p1 and p2 are the estimated linear model parameters 238. If the estimation error is less than a vertical estimation threshold 246 and linear fit has a certain slope, it can be labeled as valid free space (an area without obstacle 266). In one implementation, a slope greater than 0 indicates no obstacle, while a slope that is less than or equal to the obstacle. An example of this connection is shown in Figures 4A to 4D.

[0061] In matrix form, the linear model of Equation (1) is Given by equation (2).

[0062] In Equation (2), y is an n-by-l vector of depth values 234, x is the n-by-2 design matrix (i.e., a matrix of n rows, model coordinates in the dimension vertical, and p1 and p2 are the estimated linear model parameters 238. The value of n corresponds to the number of pixels 232 in the depth map segment 236.

[0063] In one approach, p1, and p2 can be solved using a least squares solution. In this approach, p is a vector of the unknown coefficients p1 and p2. The normal equations are given by Where X is the transpose of the design matrix

[0064] It should be noted that in an optimized implementation, the matrix inversion term is fixed based on location (i.e. coordinate a) and could be pre-calculated based on location and stored. Also, a piecewise linear model could estimate immersions and protrusions on a surface, with variation in p1, p2 and segment length. Furthermore, the primary complexity of this approach is due to the matrix multiplication of two vectors of size n in the above Equation (2). In an example, n may be 10 or the piecewise length chosen instead of 10.

[0065] The vertical estimation module 220 may determine a vertical reliability map 248 a reliability value 250 for the vertical obstacle absence estimate 242. In one implementation, the vertical estimation module 220 may determine a segment fit error 244 for each segment 236 based on the difference between the estimated linear model parameters 238 and predetermined linear model parameters 240. The predetermined model parameters may be referred to as [pM1, pM2]. The vertical estimation module 220 can check how close the predetermined model parameters are for the estimated parameters [p1, p2] comparing to a threshold {THY), e.g.

[0066] The vertical estimation threshold 246 can determine whether the estimated linear model parameters 238 fit the trained model parameters. Predetermined linear model parameters 240 may be selected from a plurality of road condition models. Each of the plurality of road condition models may have a corresponding set of linear model parameters 240. Examples of road condition models include a smooth plane, peak, valley, etc. Predetermined linear model parameters 240 can be determined by training

[0067] The vertical estimation module 220 can determine an estimated depth value using the estimated linear model parameters 238 according to Equation (5), where is the estimated depth value at the ith location.

[0068] Depth estimation error (ei) with the estimated linear model parameters 238 can be determined according to Equation (6), where yi is the depth value 234 at the ith location.

[0069] The segment fitting error 244 (s) can be determined according to equation (7), where n is the length of the segment 236.

[0070] Segment fit error 244 can be used as a reliability metric for vertical processing. The vertical estimation module 220 may determine the vertical reliability value 250 for each segment 236 by comparing the segment fit error 244 of each segment 236 to a vertical estimation threshold 246.

[0071] The vertical estimation limit 246 may be based on predetermined linear model parameters 240. The vertical estimation limit 246 may vary depending on which predetermined linear model parameters 240 are used. For example, vertical estimation limit 246 may have a value if predetermined linear model parameters 240 for a flat road are used. The vertical estimation limit 246 may have a different value if the predetermined linear model parameters 240 for a hill are used.

[0072] The vertical estimation module 220 may check the absolute value of the difference between the segment adjustment error 244 and the vertical estimation limit 246. A given segment 236 may have a high vertical reliability value 250 when the vertical estimation error segment fit 244 for the given segment 236 is less than the vertical estimation limit 246. Conversely, the given segment 236 may have a low vertical reliability value 250 when the segment fit error 244 for the given segment 236 is greater than or equal to the vertical estimation limit 246. Therefore, if the difference between the segment adjustment error 244 and the vertical estimation limit 246 is small, then the segment 236 is considered to be part of an obstacle-free area 266. If the difference is large, then the segment 236 is not considered to be part of an obstacle-free area 266.

[0073] Determining the reliability value 250 for a given segment 236, the vertical estimation module 220 may limit the vertical reliability map 248 to obtain a binary map. The reliability value 250 for a given segment 236 may be compared with a threshold to determine whether the segment 236 is a non-object area (e.g., moving) or an object area (e.g., non-moving area). vertical reliability 248 may include the reliability values 250 of the pixels 232 in the depth map 230. Therefore, the vertical reliability map 248 is a map that has a fit confidence per depth pixel 232 as well as per segment 236.

[0074] The horizontal estimation module 222 may perform horizontal processing of the depth map 230 to determine a horizontal obstacle absence estimate 258. The horizontal processing may include obtaining a depth histogram 252 for each row of pixels 232 of the map of depth 230. An example of the depth histogram 252 is described in relation to Figures 6A-6D. The depth histogram 252 may also be referred to as a disparity histogram.

[0075] In one implementation, the depth histogram 252 may be obtained by obtaining a histogram for each row in the depth map 230. For example, for a row of pixels 232 from the depth map 230, a histogram may be generated for the 234 depth values corresponding to the 232 pixels in the row.

[0076] The horizontal estimation module 222 may determine a terrain line 254 from the depth histogram 252. The y-coordinate of the endpoints of the terrain line 254 determine the nearest and furthest free space distance.

[0077] Terrain line 254 can be determined using a line extraction approach. A Hough transform can be applied to the depth histogram 252. The Hough Transform can extract multiple line segments from the depth histogram 252. For example, the Hough transform can generate 10-20 small lines. Line segments may be joined to form terrain line 254. In one implementation, the angle of terrain line 254 may be limited (e.g., between -20 degrees and -40 degrees) based on space slope characteristics. absence of obstacles.

[0078] The horizontal estimation module 222 may determine the horizontal obstacle absence estimate 258 for each pixel 232 based on the distance of the depth value 234 of each pixel 232 from the terrain line 254. And a pixel 232 that has a depth value 234 that lies within a horizontal estimation limit 260 of terrain line 254 can be identified as an unobstructed area 266. For example, if the depth value 234 of a pixel 232 lies within a certain disparity range of the terrain line 254, then the pixel 232 can be labeled as an obstacle-free area 266. If the depth value 234 of a pixel 232 falls outside the certain disparity range of the terrain line 254, then , pixel 232 can be labeled as an obstacle area 268.

[0079] The horizontal estimation module 222 may also determine a horizontal reliability map 262 based on a depth histogram distance 252. The horizontal reliability map 262 may include a reliability value 264 for the horizontal obstacle absence estimate. 258 of each 232 pixel.

[0080] The distance to mode 256 of the depth histogram 252 can be used as a reliability metric for horizontal processing. The horizontal estimation module 222 may determine whether the depth value 234 of each pixel 232 is within a reliability limit 261 of the mode 256 of the depth histogram 252. A given pixel 232 may have a high confidence value 264 when the value of depth 234 of the given pixel 232 is within the reliability limit 261 of the mode 256 of the depth histogram 252.

[0081] The estimate combiner 224 may combine the vertical obstacle absence estimate 242 and the horizontal obstacle absence estimate 258 to determine the obstacle absence map 226. This combination may be based on the vertical reliability values 250 and the horizontal reliability values 264. In one approach, vertical processing and horizontal processing can be performed in parallel and the resulting obstacle absence estimates 242, 258 fused. In another approach, vertical processing and horizontal processing can be performed sequentially and the resulting non-obstacle estimates fused.

[0082] For the parallel processing approach, both vertical processing and horizontal processing can be performed in parallel. For example, the vertical estimation module 220 may perform vertical processing and the horizontal estimation module 222 may simultaneously perform horizontal processing as described above. The estimation combiner 224 may generate the obstacle-free map 226 by identifying each pixel 232 as a non-obstacle area 266 or an obstacle area 268. This identification may be based on the vertical reliability values 250 of the vertical reliability map 248 and the horizontal reliability values 264 from the horizontal reliability map 262.

[0083] If both the vertical reliability map 248 and the horizontal reliability map 262 indicate that a pixel 232 has a high reliability, then the pixel 232 can be identified as an obstacle-free area 266 on the obstacle-free map 226. In In other words, a given pixel 232 can be identified as an obstacle-free area 266 in the obstacle-free map 226 where both the vertical reliability map 248 and the horizontal reliability map 262 are characterized by a high reliability value for the given pixel 232.

[0084] In one implementation, this can be achieved by limiting the vertical reliability map 248 and the horizontal reliability map 262 with a respective limit. For example, if a vertical reliability value 250 and a horizontal reliability value 264 of a given pixel 232 are greater than a threshold, then the pixel 232 can be identified as an obstacle-free area 266. In the case of both the vertical reliability 248 as from the horizontal reliability map 262 which indicates low reliability, the pixel 232 can be labeled as an obstacle area 268.

[0085] For the case where the vertical reliability map 248 or the horizontal reliability map 262 indicates high reliability and the other indicates low reliability, one or more different fusion approaches can be performed. In one approach, if at least one of the vertical reliability map 248 or the horizontal reliability map 262 indicates that the given pixel 232 has a low reliability, then the given pixel 232 is identified as an obstacle area 268 in the absence map. obstacle 226. In other words, a given pixel 232 can be identified as an obstacle area 268 in the obstacle absence map 226 where at least one of the indicators of the vertical reliability map 248 or the horizontal reliability map 262 is characterized by a low reliability value for the given pixel 232. In this approach, if one of the reliability maps 248, 262 is indicating low reliability, the pixel 232 can be labeled based only on that reliability map 248, 262.

[0086] In another approach, the vertical reliability map 248 and the horizontal reliability map 262 are characterized by different reliability values 250, 264 for a given pixel 232. In this case, the given pixel 232 can be identified as an area without obstacle 266 or obstacle area 268 based on the coordinate of the given pixel 232. In this approach, if both reliability maps 248, 262 are close to each other in terms of reliability (e.g., one being higher than the other), the decision can be further improved by considering 232 pixel coordinates.

[0087] In an Example, RHij is the horizontal reliability value 264 for the i-th and j-th pixel 232 from horizontal processing, and RVij is the vertical reliability value 250 from vertical processing (where both reliability values 250, 264 are normalized if obtained by different methods). If |RHij- RVij|<TH, then this will indicate proximity to confidence maps 248, 246. Additionally, RHij can be compared to RVi+n, j+n, where n is < N (e.g. N=5 for 720p resolution).

[0088] For the sequential processing approach, both vertical processing and horizontal processing can be performed first. After the first processing is performed, the reliability map (e.g., the vertical reliability map 248 or the horizontal reliability map 262) for pixels 232 where reliability is not satisfied, a second processing is called. The results of the first and second processing can be joined to obtain the obstacle absence map 226. An example of sequential processing starting with vertical processing is described in connection with Figure 9. An example of sequential processing starting with horizontal processing is described in connection with Figure 10.

[0089] The obstacle absence determination module 216 may perform further processing of the obstacle absence map 226. In one implementation, the obstacle absence determination module 216 may perform outlier removal. For example, a small number of pixels 232 may be incorrectly marked with the obstacle area 268 within a non-obstacle area 266. The obstacle-free determination module 216 may identify these strangers and change their state to obstacle-free or obstacle-free. . The obstacle absence determination module 216 may perform additional filtering of the obstacle absence map 226 to prepare it for subsequent operations.

[0090] Obstacle absence map 226 can be used for different operations. In one implementation, the obstacle absence map 226 may be used to identify a region of interest used by an object detection algorithm. This may be accomplished as described in connection with Figure 14. In another implementation, the obstacle absence map 226 may be used to identify a region of interest used by a lane detection algorithm. This can be carried out as described in connection with Figure 15

[0091] As illustrated in Figure 2, one or more of the illustrated components may optionally be implemented by a processor 228. For example, the obstacle absence determination module 216 may be implemented by a processor 228. In some configurations, different processors may be used to implement different components (e.g., one processor may implement the depth map generator 218, another processor may be used to implement the vertical estimation module 220, another processor may be used to implement the estimation module horizontal 222 and yet another processor may be used to implement the estimation combiner 224).

[0092] It should be noted that it is possible to rotate image 214 and perform diagonal processing. If an image 214 is rotated, vertical and horizontal processing may become diagonal processing. Therefore, although the terms vertical and horizontal processing are used here, it can be recognized that the processing could be applied across a different section through the rotated image with the corresponding coordinate mapping.

[0093] Figure 3 is a flowchart illustrating a method 300 for performing obstacle-free area detection. Method 300 may be implemented, with reference to Figure 1, an electronic device 102, e.g., an obstacle absence determination module 116. The electronic device 102 may obtain 302 a depth map 230 from one or more images 214. In one implementation, the electronic device 102 may generate the depth map 230 from a pair of stereo images. In another implementation, electronic device 102 may generate depth map 230 from a mono video image. Each pixel 232 in the depth map 230 can have a depth value 234.

[0094] Electronic device 102 may perform vertical processing 304 of depth map 230 to determine an unobstructed vertical estimate 242. Vertical processing may include dividing depth map 230 into segments 236. Each segment 236 may include a number of 232 pixels in a column. The electronic device 102 may estimate linear model parameters 238 for each segment 236 to determine the vertical obstacle absence estimate 242. The electronic device 102 may determine a vertical reliability map 248 that includes a reliability value 250 for the estimate of absence of vertical obstacle 242.

[0095] The electronic device 102 may perform 306 horizontal processing of the depth map 230 to determine an estimate of the absence of a horizontal obstacle 258. The horizontal processing may include obtaining a depth histogram 252 for each row of pixels 232 of the depth map. depth 230. The electronic device 102 may determine a terrain line 254 from the depth histogram 252. The electronic device 102 may determine the horizontal obstacle absence estimate 258 for each pixel 232 based on the distance of the depth value 234 from each pixel 232 from the terrain line pixel 254. The electronic device 102 may also determine a horizontal reliability map 262 that includes a reliability value 264 for the horizontal obstacle absence estimate 258 of each pixel 232.

[0096] The electronic device 102 may combine 308 the vertical obstacle absence estimate 242 and the horizontal obstacle absence estimate 258 to determine an obstacle absence map 226. In one implementation, the electronic device 102 may perform parallel vertical processing and horizontal processing. In this implementation, the electronic device 102 may combine the vertical obstacle absence estimate 242 and the horizontal obstacle absence estimate 258 as described in connection with Figure 10. In another implementation, the electronic device 102 may perform sequential processing starting with vertical processing, as described in connection with Figures 11A - 11 B in yet another implementation, the electronic device 102 can perform sequential processing starting with horizontal processing, as described in connection with Figures 12A - 12 B.

[0097] Figures 4A - 4 D illustrate an example of a vertical processing of a depth map 430. The depth map 430 can be generated from one or more images 404. The depth map 430 can include locations corresponding to the pixels of the original image(s) 404. Each location (e.g., coordinate) in the depth map 430 may have a horizontal coordinate 472 and 40T a vertical coordinate 474a corresponding to the pixels of the original image(s) 404.

[0098] The depth map 430 may match the size of the original image 404 if the depth is calculated from the original resolution. In viewing a depth map 430, the depth value 434 may be obtained from the corresponding coordinates of the original image 404. It should be noted that a visualization of the depth map 430 may or may not be generated when generating a depth map. obstacle 226.

[0099] Each pixel 232 of depth map 430 may have a depth value 434. In this example, depth values 434a may range from 0 to 120, where 0 indicates the furthest distance and 120 indicates the closest distance. It should be noted that different values can be used for the 434 depth values.

[0100] In one implementation, the disparity for depth mapping can be explained by the following equations. Z = fBld, where Z is the distance along the camera's Z axis, f is the focal length (in pixels), B is the baseline (in meters), d is the disparity (in pixels). When the disparity is small, the depth is great. Depth can be found in terms of meters.

[0101] It should be noted that depth estimation algorithms from stereo images 404 may not be completely reliable. For example, a depth estimation algorithm may not be able to assign depth 434 values in certain regions. A depth filling algorithm may be used to fill in missing depth values 434. For example, neighboring depth value 434 may be propagated to an adjacent area. The spread can be from the left or right. Alternatively, missing depth values 434 can be filled in by interpolation between left and right as well as top and bottom.

[0102] This example shows a first column 470a and a second column 470b. In a first column chart 475a, depth values 434b are shown for pixels 232 in the first column 470a. In this first column chart 475a, the depth values 434b are plotted relative to the vertical coordinates 474b of the pixels 232 of the first column 470a. It should be noted that in this example, the zero values from 0 to 40 and after 400 pixels are because there is no depth assigned there. Because stereo images can be calibrated, they may not have the corresponding field of view (FOV) after calibration. Depth estimation can only be performed within the same FOV.

[0103] In a second column chart 475b, depth values 434c are shown for pixels 232 in second column 470b. In this second column chart 475b, the depth values 434c are plotted against the vertical coordinates 474c of the pixels 232 from the second column 470b. The dashed line from 0 to 150 is the mapping that shows the same algorithm results. The mapping can only be slanted (that is, slanted) lines (which specify a non-object road area) to mapping objects (which are flat lines), then the same algorithm can be used, but the mapping parameters can be changed.

[0104] The solid line in graphs 475a, b comes from original depth values. The dashed line is generated according to the systems and methods described. It should be noted that mapping can be based on the slope of the dashed line. In these graphs 475a, b, a slope greater than 0 indicates an obstacle-free area 266. A slope less than or equal to 0 indicates an obstacle area 268.

[0105] During vertical processing, the electronic device 102 may divide the depth map 430 into segments 236. And each HPT segment 236 may include a number of pixels 232 in a column 470. For example, the segment 236 may be a 10-15 pixel vector 232. The electronic device 102 may determine an estimate of vertical obstacle absence 242 and may estimate linear model parameters 238 as described with respect to Figure 2. If the estimation error is less than a threshold 246 and the linear fit has a certain slope, then the segment 236 can be labeled as a valid obstacle-free area 266.

[0106] Figure 5 is a flowchart illustrating a method 500 for performing obstacle-free area detection using vertical processing. Method 500 may be implemented by an electronic device 102, for example, an obstacle absence determination module 116. The electronic device 102 may divide 502 a depth map 430 into segments 236. Each segment 236 may include a number n of 232 pixels in a 470 column. In one implementation, n may equal 10 232 pixels.

[0107] The electronic device 102 can estimate 504 linear model parameters 238 for each segment 236 to determine the estimated absence of vertical obstacle 242. This can be performed according to equations 1-4 described above.

[0108] The electronic device 102 may determine 506 a vertical reliability map 248 that includes a reliability value 250 for the vertical obstacle absence estimate 242. For example, the electronic device 102 may determine a segment adjustment error 244 for each segment 236 based on the difference between the estimated linear model parameters 238 and predetermined linear model parameters 240. The segment fitting error 244 can be determined according to equations 5-7 above. Predetermined linear model parameters 240 may be selected from among these values a plurality of road condition models (e.g., flat, peak, valley) Each of the plurality of road condition models may have a corresponding set of model parameters linear 240.

[0109] The electronic device 102 may determine the reliability value 250 for each segment 236 by comparing the segment adjustment error 244 of each segment 236 to a vertical estimation limit 246.' A given segment 236 may have a high reliability value 250 when the segment fitting error 244 for the given segment 236 is less than the vertical estimation limit 246.

[0110] The electronic device 102 may apply the reliability value 250 for a given segment 236 to each pixel 232 in the given segment 236. Therefore, each pixel 232 in the vertical reliability map 248 may have a reliability value 250 indicating confidence in the estimate absence of vertical obstacle 242.

[0111] Figures 6A - 6D illustrate an example of a horizontal processing of a depth map 630. The depth map 630 can be generated from one or more images 1141. The depth map 630 illustrated in Figure 6A is the same depth map 430 described in connection with Figure 4B (compressed to fit page) Depth map 630 may include locations corresponding to pixels of the original image(s) 114. Each location in depth map 630 may have a horizontal coordinate 672 and 18T a vertical coordinate 674 corresponding to pixels 232 of the original image(s) 114.

[0112] The electronic device 102 may generate a depth histogram 652. The depth histogram 652 may be generated by obtaining a histogram of depths for each row in the depth map 630. For example, the depth histogram 652 may be generated by projecting the depth map 630 onto the vertical axis.

[0113] A depth histogram 652 can be calculated for each row in an image 114. The number of bins in the depth histogram 652 corresponds to the number of maximum disparity values in the image 114. For example, it may be 150 for a 720p image , or it may be larger for a higher resolution image and smaller for a lower resolution image. The x-axis on the right side of Figure 6B corresponds to disparity values, and the intensity value in image 114 corresponds to the histogram count for that disparity value. The darker the shadow is, the greater the disparity value, the lighter the hue. It is, the smaller the disparity value of the histogram. In this example, a maximum number of disparity bins is 150. In the 652 depth histogram, the disparity values are plotted against the 674 vertical coordinates.

[0114] The electronic device 102 may apply a Hough transform to the depth histogram 652 to extract line segments 676. The Hough Transform may extract multiple line segments 676 from the depth histogram 252. For example, the Hough can generate 10-20 small 676 line segments.

[0115] Line segments 676 can be joined together to form terrain line 654. The x-coordinate of the endpoints of terrain line 254 determine the nearest and furthest free space distance. In one implementation, the angle of terrain line 254 may be limited (e.g., between -20 degrees and -40 degrees) as the obstacle-free space has certain slope characteristics.

[0116] If the depth histogram 652 gives a line with a negative slope, it corresponds to a road segment in front of the car without any obstacles. An obstacle will be represented by a straight vertical line at 90 degrees. The terrain line 254 indicates that the depth values in front of the camera are slowly decreasing as the depth values are analyzed in rows of an image 114. If there is an object, then the object will have the same depth value for a certain number of rows. In this case, the depth values will not decrease. The slope (i.e. the angle of the terrain line254) can be chosen according to the maximum slope a road can have.

[0117] Electronic device 102 may label pixels 232 with depth values 634 that lie within a horizontal estimation boundary 260 of terrain line 654 as non-boundary obstacle areas 266. Those pixels 232 with depth values 634 which lie outside the horizontal estimation boundary 260 of the terrain line 654 may be labeled as obstacle areas 268.

[0118] Figure 7 is a flowchart illustrating a method 700 for performing obstacle-free area detection using horizontal processing. The method 700 may be implemented by an electronic device 102, for example, an obstacle absence determination module 116. The electronic device 102 may obtain 702 a depth histogram 252 for each row of pixels 232 of the depth map 230. This can be carried out as described in connection with figures 6A - 6D.

[0119] The electronic device 102 may determine 704 a terrain line 254 from the depth histogram 252. This may be accomplished as described in connection with FIGS. 6A-6D.

[0120] The electronic device 102 may determine 706 a horizontal obstacle absence estimate 258 for each pixel 232 based on the distance of the depth value 234 of each pixel 232 from the terrain line pixel 254. Those pixels 232 with values of depth 634 that fall within a horizontal estimation boundary 260 of the terrain line 654 may be labeled as obstacle-free areas 266. Those pixels 232 with depth values 634 that lie outside the horizontal estimation boundary 260 of the terrain line terrain 654 can be labeled as obstacle areas 268.

[0121] Electronic device 102 may determine 708 a horizontal reliability map 262 that includes a reliability value 264 for the horizontal obstacle absence estimate 258 of each pixel 232. For example, the distance to mode 256 of the depth histogram 252 can be used as a reliability metric for horizontal processing. The electronic device 102 may determine whether the depth value 234 of each pixel 232 is within a reliability limit 261 of the mode 256 of the depth histogram 252. A given pixel 232 may have a high reliability value 264 when the depth value 234 of the given pixel 232 is within the reliability limit 261 of the mode 256 of the depth histogram 252.

[0122] Figure 8 is a flow chart illustrating a method 800 for combining a vertical obstacle absence estimate 242 and a horizontal obstacle absence estimate 258 to determine an obstacle absence map 226. The method 800 can be implemented by an electronic device 102, for example, an obstacle absence determination module 116. In this method 800, the electronic device 102 can perform vertical processing and horizontal processing in parallel.

[0123] The electronic device 102 may perform vertical processing 802 of a depth map 230 to determine an estimate of the absence of a vertical obstacle 242. This may be performed as described in connection with FIG. 5.

[0124] The electronic device 102 may obtain 804 a vertical reliability map 248 based on a model fit confidence. This can be accomplished as described in connection with Figure 5.

[0125] The electronic device 102 may perform 806 horizontal processing of the depth map 230 to determine an estimate of the absence of horizontal obstacle 258. This may be performed as described in connection with Figure 7.

[0126] Electronic device 102 may obtain 808 a horizontal reliability map 262 based on a depth histogram distance 252. This may be accomplished as described in connection with Figure 7.

[0127] It should be noted that steps 802,804,806, 808 can be performed in parallel. For example, while the electronic device 102 performs the vertical processing steps 802 and 804, the electronic device 102 may simultaneously perform the horizontal processing steps 806 and 808.

[0128] The electronic device 102 may fuse 810 the vertical obstacle-free estimate 242 and the horizontal obstacle-free estimate 258 to obtain the obstacle-free map 226. This fusion may be based on the vertical reliability map 248 and the horizontal reliability 262.

[0129] If both the vertical reliability map 248 and the horizontal reliability map 262 indicate that a pixel 232 has a high reliability, then the pixel 232 can be identified as an obstacle-free area 266 in the obstacle-free map 226. For example, if the vertical reliability map 248 indicates a high vertical reliability value 250 and the horizontal reliability map 262 indicates a high horizontal reliability value 264, then the pixel 232 can be labeled as an obstacle-free area 266 on the absence of obstacle 226.

[0130] For the case where the vertical reliability map 248 or the horizontal reliability map 262 indicates high reliability and the other indicates low reliability, one or more different fusion approaches can be performed. In one approach, if at least one of the vertical reliability map 248 or 20T and the horizontal reliability map 262 indicates that the given pixel 232 has a low reliability value 250, 264, then the given pixel 232 is identified as an obstacle area. 268 in the obstacle absence map 226. In another approach, the vertical reliability map 248 and the horizontal reliability map 262 may indicate different reliability values 250, 264. In this case, the given pixel 2332 may be identified as an area without obstacle 266 or obstacle area 268 based on the coordinate of the given pixel 232.

[0131] Figure 9 is a flowchart illustrating another method 900 for combining a vertical obstacle absence estimate 242 and a horizontal obstacle absence estimate 258 to determine an obstacle absence map 226. Method 900 can be implemented by an electronic device 102, for example, an obstacle absence determination module 116. In this method 900, the electronic device 102 may perform a sequential application of vertical processing followed by horizontal processing.

[0132] The electronic device 102 may perform vertical processing of a depth map 230 to determine an estimate of the absence of a vertical obstacle 242. This may be performed as described in connection with FIG. 5.

[0133] The electronic device 102 may obtain 904 a vertical reliability map 248 based on a model fit confidence. This can be accomplished as described in connection with Figure 5.

[0134] The electronic device 102 can identify 906 reliable regions as obstacle-free areas 266 based on the vertical reliability map 248. For example, each pixel 232 that has a high vertical reliability value 250 in the vertical reliability map 248 can be labeled as an obstacle-free area 266 on the obstacle-free map 226.

[0135] The electronic device 102 may perform horizontal processing 908 on unreliable regions of the vertical reliability map 248 to determine whether the unreliable regions are areas of absence of obstacles 266. For example, the electronic device 102 may perform horizontal processing on at least least one row of pixels 232 which has a low reliability value of 250. It should be noted that the length of one row could be as wide as the image 114 or could be shorter than the image width. Horizontal processing may be performed as described in connection with Figure 7 to determine a horizontal obstacle absence estimate 258. The obstacle absence map 226 may be updated based on the results of the horizontal reliability map 262 of the unreliable regions.

[0136] Figure 10 is a flowchart illustrating yet another method 1000 for combining a vertical obstacle-free estimate 242 and a horizontal obstacle-free estimate 258 to determine an obstacle-free map 226. Method 1000 can be implemented by a electronic device 102, for example, an obstacle absence determination module 116. In this method 1000, the electronic device 102 may perform a sequential application of horizontal processing followed by vertical processing.

[0137] The electronic device 102 may perform 1002 horizontal processing of a depth map 230 to determine an estimate of the absence of a horizontal obstacle 258. This may be performed as described in connection with Figure 7.

[0138] The electronic device 102 may obtain 1004 a horizontal reliability map 262 based on a depth histogram distance 252. This may be accomplished as described in connection with Figure 7.

[0139] The electronic device 102 can identify 1006 reliable regions as obstacle-free areas 266 based on the horizontal reliability map 262. For example, each pixel 232 that has a high horizontal reliability value 264 in the horizontal reliability map 262 can be labeled as an obstacle-free area 266 on the obstacle-free map 226.

[0140] The electronic device 102 may perform 1008 vertical processing on unreliable regions of the horizontal reliability map 262 to determine whether the unreliable regions are areas of absence of obstacles 266. For example, the electronic device 102 may perform vertical processing on a or more column(s) of pixels 232 that have a low horizontal reliability value 264. The one or more column(s) of pixels 232 may be as tall as the image 114 or could be smaller than the image height.

[0141] Vertical processing may be performed as described in connection with Figure 5 to determine a vertical no-obstacle estimate 242. The no-obstacle map 226 may be updated based on the results of the vertical reliability map 248 of the unreliable regions .

[0142] Figures 11A - 11 B illustrate an example of determining areas of absence of obstacles 1166 in an image 1114. In this Example, the original image 1114a is an image of a one-way road.

[0143] The processed image 1114b shows the obstacle-free area 1166 that is determined in accordance with the systems and methods described herein. The processed image 1114b shows an example of an intermediate step of the algorithm, not the final result. This is to show that there may be holes in the obstacle absence map 126 that must be further processed. Also this illustrates the result of vertical processing alone.

[0144] Unobstructed area 1166 includes the open area corresponding to the highway. Certain external areas 1178 in the non-obstacle area 1166 have not been identified as part of the non-obstacle area 1166. As used herein, outlier means that the depth values in the image 1114b do not fit the predetermined model. This may be due to a possible misestimation of depth values (e.g. input depth values may not be perfect), so that some areas appear as holes (or strange). These areas of compensation 1178 may be removed by performing additional processing of the image 1114.

[0145] Figures 12A - 12 b illustrate another example of determining areas of absence of obstacles 1266 in an image 1214. In this example, the original image 1214a is an image of an intersection. The processed image 1214b shows the obstacle-free area 1266 which is determined in accordance with the systems and methods described herein.

[0146] Figures 13A - 13 B illustrate an example of determining distance 1380 from an obstacle-free area 1366. This example shows the processed image 1314 of the road described in connection with Figures 11A - 11 B. The obstacle-free area 1366 is determined in accordance with the systems and methods described herein.

[0147] In the depth map 1330 of Figure 13B, the x and y coordinates are the coordinate positions and the shading is indicative of depth. In this example, depth map 1330 includes depth information for the unobstructed area 1366. Depth map 1330 indicates how far free space will be in front of the camera.

[0148] Using the depth values 234 from the depth map 1330, the electronic device 102 can determine various distances associated with the unobstructed area 1366b. For example, the electronic device 102 may determine that the furthest distance in the non-variable direction from the obstacle area 1366b is between 45-50 meters away from the image sensor 104. Similarly, the electronic device 102 may determine which cars are furthest away from the obstacle area 1366b. nearby are approximately 11 meters from image sensor 104.

[0149] Figure 14 illustrates an example of using the obstacle absence map 226 to identify a region of interest (ROI) 1482 used by an object detection algorithm. This example shows the processed image 1414 of the road described in connection with Figures 11A - 11B. The obstacle-free area 1466 is determined in accordance with the systems and methods described herein.

[0150] The electronic device 102 may then identify one or more ROI 1482 for a potential obstacle area 268 . For example, the electronic device 102 may identify obstacle areas 268 from the obstacle-free map 226. In one implementation, pixels 232 that are not marked as an obstacle-free area 1466 may be identified as an obstacle area 268. These Obstacle Areas 268 may be included in one or more channels 1482. In this example, the electronic device 102 identifies four Carriers 1482a-d as potential object areas.

[0151] The electronic device 102 may perform an object detector on the identified Receiver 1482. For example, the electronic device 102 may detect whether an ROI 1482 includes a car, traffic sign, a pedestrian, lanes, lines, etc.

[0152] Identification of the unobstructed area 1466 first results in a reduced search area for object detection. This can reduce the amount of processing that is performed for object detection.

[0153] Figure 15 illustrates an example of using the obstacle absence map 226 to identify a region of interest (ROI) 1582 used by a lane detection algorithm. This example shows the processed image 1514 of a road. The obstacle-free area 1566 is determined in accordance with the systems and methods described herein.

[0154] The electronic device 102 may then identify one or more ROI 1582 for road sides and/or medians. For example, the electronic device 102 may identify obstacle areas 268 from the obstacle-free map 226. In this example, the electronic device 102 identifies two Squeegees 1582a-b on the sides of the obstacle-free area 1566 as sides and/or undulations of potential road.

[0155] The electronic device 102 may perform a lane detector on the identified Channel 1582a-B that identifies the unobstructed area 1566 first results in a reduced search area for lane detection. This can reduce the amount of processing that is performed for lane detection.

[0156] Figure 16 is a flowchart illustrating a method 1600 for classifying a road based on estimated linear model parameters 238. The method 1600 may be implemented by an electronic device 102, e.g., an absence determination module. obstacle 116.

[0157] The electronic device 102 may obtain 1602 a depth map 230 from a road image 114. The depth map 230 may be generated as described in connection with Figure 2.

[0158] The electronic device 102 may perform a segment fit 1604 to estimate the linear model parameters 238. The estimated linear model parameters 238 may be determined as described in connection with Figure 2.

[0159] The electronic device 102 may classify 1606 the road based on the estimated linear model parameters 238. For example, the electronic device 102 may compare the estimated linear model parameters 238 with a plurality of predetermined linear model parameters 240. According described above, the predetermined linear model parameters 240 may be associated with a plurality of road condition models. Each of the plurality of road condition models may have a corresponding set of linear model parameters 240. Examples of road condition models include a smooth plane, slope (e.g., peak), valley, rough road, etc.

[0160] In one implementation, predetermined linear model parameters 240 may be obtained through training. Pre-labeled test data can be used, where pre-labeled refers to labeled images 114 and depth maps 230 of flat roads, or uneven roads, etc. With this data, predetermined linear model parameters 240 can be generated.

[0161] The electronic device 102 may determine which of the predetermined linear model parameters 240 best fit the estimated linear model parameters 238. The road may be classified 1606 according to the road condition model that best fits the estimated linear model parameters 238. Therefore, by classifying the road 1606, the electronic device 102 can determine the type of free space in the road image 114.

[0162] Figure 17 illustrates certain components that may be included within an electronic device 1702. The electronic device 1702 may be or may be included within a camera, video recorder, digital camera, cell phone, smart phone, computer ( for example, desktop computer, laptop computer, etc. Desktop device, media player, television, automobile, personal camera, action camera, security camera, mounted camera, connected camera, the robot, the aircraft, the drone, the unmanned aerial vehicle (UAV), the healthcare equipment, the game console, the Personal digital assistants (PDA), a top case, etc. the electronic device 1702 includes a processor 1728. The processor 1728 can. be a general-purpose single-chip or multi-chip microprocessor (e.g., an ARM), a special-purpose microprocessor (e.g., a digital signal processor (DSP)), a microcontroller, a programmable gate array, etc. The processor 1728 may be referred to as a central processing unit (CPU). Although only a single processor 1728 is shown in the electronic device 1702, in an alternative configuration, a combination of processors (e.g., an ARM and DSP) could be used.

[0163] Electronic device 1702 also includes memory 1739. Memory 1739 can be any electronic component capable of storing electronic information. Memory 1739 may be embodied as random access memory (RAM), read-only memory (ROM), magnetic disk storage media, optical storage media, RAM flash memory devices, on-board memory included with the processor, EPROM memory, EEPROM memory, registers and so on, including combinations thereof.

[0164] Data 1721a and instructions 1741a may be stored in memory 1739. Instructions 1741a may be executable by processor 1728 to implement one or more of the methods described herein. Executing instructions 1741a may involve using data that is stored in memory 1739. When processor 1728 executes instructions 1741, various portions of instructions 1741b may be loaded into processor 1728, and various pieces of data 1721b may be loaded into the processor. 1728.

[0165] The electronic device 1702 may also include a transmitter 1725 and a receiver 1727 to enable the transmission and reception of signals to and from the electronic device 1702. The transmitter 1725 and the receiver 1727 may be collectively referred to as a transceiver 1729. A or multiple antennas 1737a-b may be electrically coupled to the transceiver 1729. The electronic device 1702 may also include (not shown) multiple transmitters, multiple receivers, multiple transceivers and/or additional antennas.

[0166] Electronic device 1702 may include a digital signal processor (DSP) 1731. Electronic device 1702 may also include a Communication interface 1733. Communication interface 1733 may allow one or more types of input and/or output. For example, the communications interface 1733 may include one or more 3T ports and/or communications devices for connecting other devices to the electronic device 1702. Additionally or alternatively, the communications interface 1733 may include one or more other interfaces (e.g., touch screen, keyboard, keyboard, microphone, camera, etc.) for example, the communication interface 1733 may allow a user to interact with the electronic device 1702.

[0167] The various components of the electronic device 1702 may be coupled together by one or more buses, which may include a power bus, a control signal bus, a status signal bus, a data bus, etc. For clarity, the various buses are illustrated in Figure 17 as a bus system 1723.

[0168] According to the present description, a circuit, in an electronic device, can be adapted to obtain a depth map from one or more images. Each pixel in the depth map can have a depth value. The same circuit, a different circuit, or a second section of the same or different circuit may be used adapted to perform vertical processing of the depth map to determine a vertical obstacle absence estimate. The same circuit, a different circuit, or a third section of the same or different circuit may be adapted to perform horizontal processing of the depth map to determine a horizontal obstacle absence estimate. The same circuit, a different circuit, or a fourth section of the same circuit or a different circuit can be adapted to combine the vertical obstacle absence estimate and the horizontal obstacle absence estimate to determine an obstacle absence map. Additionally, the same circuit, a different circuit, or a fifth section of the same circuit or a different circuit may be adapted to control the configuration of the circuit(s) or section(s) of the circuit(s) that provide the functionality described above.

[0169] The term "determination" encompasses a wide variety of actions, and therefore "determination" may include calculation, computation, processing, derivation, investigation, searching (e.g., looking in a table, a database, or other structure data), evaluation and similar. Also, "determine" may include receiving (e.g., receiving information), accessing (e.g., accessing data in a memory), and the like. Also, "determination" may include resolution, selection, choice, establishment, and the like.

[0170] The phrase "based on" does not mean "based solely on" unless expressly specified otherwise. In other words, the phrase "based on" describes both "based only on" and "based at least on."

[0171] The term "processor" should be interpreted broadly to encompass a general-purpose processor, a central processing unit (CPU), a microprocessor, a digital signal processor (DSP), a controller, a microcontroller, a state, and so on. Under some circumstances, a "processor" may refer to an application-specific integrated circuit (ASIC), a programmable logic device (PLD), a field-programmable gate array (FPGA), etc. The term "processor" may refer to a combination of processing devices, for example, a combination of a DSP and a microprocessor, a plurality of microprocessors, one or more microprocessors in conjunction with a DSP core, or any other such configuration.

[0172] The term "memory" should be interpreted broadly to encompass any electronic component capable of storing electronic information. The term memory can refer to several types of processor-readable media such as random access memory (RAM), read-only memory (ROM), non-volatile random access memory (NVRAM), programmable read-only memory (PROM). ), erasable programmable read-only memory (EPROM), electrically erasable PROM (EEPROM), flash memory, magnetic or optical data storage, registers, etc. Memory is said to be in electronic communication with a processor if the processor can read information from and/or write information to memory. Memory that is integral to a processor is in electronic communication with the processor.

[0173] The terms "instructions" and "code" should be interpreted broadly to include any type of computer-readable statement(s). For example, the terms "instructions" and "code" may refer to one or more programs, routines, subroutines, functions, procedures, etc. "Instructions" and "code" may be according to the present invention a single computer-readable statement or many computer-readable statements.

[0174] The functions described here can be implemented in software or firmware being executed by hardware. Functions can be stored as one or more instructions in a computer-readable medium. The terms "computer-readable medium" or "computer program product" refer to any tangible storage medium that can be accessed by a computer or processor. By way of example, and not limitation, a computer-readable medium may comprise RAM, ROM, EEPROM, CD-ROM or other optical disk storage, magnetic disk storage or other magnetic storage devices, or any other medium that may be used to load or store desired program code in the form of instructions or data structures and which can be accessed by a computer. Disc and disc, as used herein, include compact disc (CD), laser disc, optical disc, digital versatile disc (DVD), floppy disc, and Blu-ray® disc where discs usually reproduce data magnetically, while discs reproduce data optically with lasers. It should be noted that a computer-readable medium can be tangible and non-transitory. The term "computer program product" refers to a computing device or processor in combination with code or instructions (e.g., a "program") that can be executed, processed, or computed by the computing device or processor. As used herein, the term "code" may refer to software, instructions, code or data that is/are executable by a computing device or processor.

[0175] Software or instructions may also be transmitted via a transmission medium. For example, if the software is transmitted from a website, server, or other remote source using a coaxial cable, fiber optic cable, twisted pair, digital subscriber line (DSL), or wireless technologies such as infrared, radio and microwave, then coaxial cable, fiber optic cable, twisted pair, DSL, or wireless technologies such as infrared, radio, and microwave are included in the definition of transmission medium.

[0176] The methods described here comprise one or more steps or actions to obtain the method described. The steps and/or actions of the method can be interchanged with each other without departing from the scope of the claims. In other words, unless a specific order of steps or actions is necessary for the proper operation of the method being described, the order and/or use of specific steps and/or actions may be modified without departing from the scope of the claims.

[0177] Furthermore, it should be appreciated that modules and/or other means suitable for carrying out the methods and techniques described herein can be downloaded and/or otherwise obtained by a device. For example, a device may be coupled to a server to facilitate the transfer of means to perform the methods described herein. Alternatively, various methods described herein may be provided by means of a storage medium (e.g. random access memory (RAM), read-only memory (ROM), a physical storage medium such as a compact disk (CD) or flexible, etc. 0), such that a device can achieve the various methods by coupling or providing the storage medium to the device.

[0178] It should be understood that the claims are not limited to the precise configuration and components illustrated above. Various modifications, changes and variations may be made in the arrangement, operation and details of the systems, methods and apparatus described herein without departing from the scope of the claims.

Claims (11)

1. A method performed by an electronic device comprising: performing a first processing of a depth map (230) to determine a first estimate of an unobstructed area, wherein performing the first processing comprises: dividing the depth map into a plurality of segments (236), each of the plurality of segments comprising a portion of a column of pixels (232) in the depth map (230); i) estimating linear model parameters for each of the plurality of segments to determine whether each of the plurality of segments is part of the first estimate of the unobstructed area; and generating a first map by: determining a value (250) for each of the plurality of segments (236) by comparing a segment fit error (244) associated with each of the plurality of segments (236) with a first limit estimate (246); and ii) applying the value for each of the plurality of segments to at least one pixel in each segment of the depth map, wherein the segment fit error (244) for each segment is determined based on a difference between the parameters estimated linear model parameters for each segment and the predetermined linear model parameters for each segment; characterized by the fact that it comprises: performing a second processing of the depth map (230) to determine a second estimate of an unobstructed area, wherein performing the second processing comprises: iii) obtaining a depth histogram (252, 652) for at least at least one depth map pixel row, wherein the depth histogram comprises depth values associated with each pixel in the pixel row; and determining a terrain line from the depth histogram (252, 652); determining the second unobstructed estimate based on a distance of each depth value associated with each pixel of the depth map from the terrain line; and generating a second map by: determining a second value (264) for each pixel in the pixel row by comparing the depth value (234) associated with each pixel (232) with a second threshold (261); combine the first value (250) from the first map and the second value (264) from the second map; and generate an obstacle-free map based on the combined values. 2. The method of claim 1, wherein the predetermined linear model parameters are selected from a plurality of road condition models, wherein the plurality of road condition models has a corresponding set of model parameters linear. 3. Method according to claim 1, characterized by the fact that performing the second processing further comprises: determining whether the depth value of a given pixel is within a range of a mode of the depth histogram, in which the data pixel has a high reliability value when the depth value of the given pixel is within the range of the depth histogram mode. 4. Method according to claim 1, characterized by the fact that combining the first estimate and the second estimate comprises: performing both the first processing and the second processing in parallel; and combining the first estimate and the second estimate based on the first map and the second map. 5. Method according to claim 4, characterized by the fact that a given pixel is identified as an obstacle-free area where both the first map and the second map comprise a high confidence value for the given pixel and/or in which a given pixel is identified as an obstacle area in which at least one of the first map or the second map comprises a low reliability value for the given pixel and/or in which a given pixel is identified as an obstacle-free area or area obstacle based on a coordinate of the given pixel where the first map and the second map comprise different reliability values for the given pixel. 6. Method according to claim 1, characterized by the fact that combining the first estimate of an area without one or more obstacles and the second estimate without obstacles comprises: performing the first processing of the depth map; obtain the first map based on a model fit confidence; identify reliable regions of the first map as areas without obstacles; and performing second processing on unreliable regions of the first map to determine whether the unreliable regions are unobstructed areas and/or combining the first unobstructed estimate and the second unobstructed estimate comprises: performing second processing of the depth map ; obtain a second reliability map based on a depth histogram distance; identify reliable regions of the second map as areas without obstacles; and performing first processing on untrusted regions of the second map to determine whether the untrusted regions are unobstructed areas and/or wherein the map of an unobstructed area is used in identifying a region of interest used by at least one of an object detection algorithm or a lane detection algorithm. 7. An apparatus comprising: means for performing the first processing of a depth map (230) to determine a first estimate of an unobstructed area, wherein performing the first processing comprises: dividing the depth map into a plurality of segments ( 236), wherein each of the plurality of segments comprises a portion of a column of pixels (232) in the depth map (230); estimating linear model parameters for one of the segments to determine whether each of the plurality of segments is part of the first determination of the unobstructed area; generating a first map by: determining a value (250) for each of the plurality of segments (236) comparing a segment fit error (244) associated with each of the plurality of segments (236) with a first estimate threshold (246); and applying the value for each of the plurality of segments to at least one pixel in each segment of the first map, wherein the segment fit error (244) for each segment is determined based on a difference between the linear model parameters estimated for each segment and the predetermined linear model parameters for each segment; characterized in that it comprises: means for performing a second processing of the depth map (230) to determine a second estimate of an unobstructed area, wherein performing the second processing comprises: obtaining a depth histogram (252, 652) for at least at least one depth map pixel row, wherein the depth histogram comprises depth values associated with each pixel in the pixel row; and wherein the means for performing the second processing further comprises means for determining a terrain line from the depth histogram (252, 652); means for determining the second unobstructed estimate based on a distance of each depth value associated with each pixel of the depth map from the terrain line; and generating a second map by: determining a second value (264) for each pixel in the pixel row by comparing the depth value (234) associated with each pixel (232) with a second threshold (261); combine the first values (250) of the first map and the second values (264) of the second map; and means for generating an unobstructed map based on the combined values. 8. The apparatus of claim 7, wherein the means for combining the first estimate and the second estimate comprises: means for performing both the first processing and the second processing in parallel; and means for combining the first estimate and the second estimate without hindrance based on the first map and the second map. 9. The apparatus of claim 7, wherein the means for combining the first estimate and the second estimate comprises: means for performing the first processing of the depth map; means for obtaining the first map based on a model fit confidence; means for identifying reliable regions of the first reliability map as unobstructed areas; and means for performing second processing on unreliable regions of the first map to determine whether the unreliable regions are unobstructed areas. 10. The apparatus of claim 7, wherein the means for combining the first estimate and the second estimate comprises: means for performing the second processing of the depth map; means for obtaining a second map based on a depth histogram distance; means for identifying reliable regions of the second map as areas without one or more obstacles; and means for performing first processing on unreliable regions of the second map to determine whether the unreliable regions are areas without one or more obstacles. 11. Computer readable memory comprising instructions stored therein, the instructions being executable by a computer to perform the method steps as defined in any one of claims 1 to 6.