Methods and systems for camera-based autonomous parking

Camera-based autonomous parking is disclosed. An autonomous parking procedure can include detecting parking lines in images captured by a camera on a vehicle. The vehicle can be localized with respect to the parking lines based on location data for the vehicle from a GPS receiver and a location determination for the vehicle based on detected ends of the parking lines. The vehicle can further determine an occupancy state of one or more parking spaces formed by the two or more parking lines using a range sensor on the vehicle and select an empty space. A region of interest including the selected space can be identified and one or more parking lines of the selected space can be detected in an image of the region of interest. The vehicle can autonomously move to reduce errors between the location of the vehicle and the final parking position within the selected space.

FIELD OF THE DISCLOSURE

This relates generally to methods and systems for an autonomous parking procedure, and more particularly to a camera- and/or location-based autonomous parking procedure.

BACKGROUND OF THE DISCLOSURE

Vehicles, especially automobiles, increasingly include various sensors for detecting and gathering information about the vehicles' surroundings. These sensors may include camera(s), range sensor(s) and/or location (including GPS) receiver(s) for use in various vehicle operations. In some examples, these sensors can be used to operate the vehicle in a fully or partially autonomous driving mode. For example, the range sensor(s) can be used to detect objects in physical proximity to the vehicle. In some examples, the vehicle can autonomously park in a parking space, including when both spaces adjacent to the vehicle are occupied, by using the range sensor(s) to detect the parking space between the parked vehicles. However, without the adjacent spaces being occupied, the range sensor(s) may be unable to locate a parking space to autonomously park in. There exists a need in the field of fully and partially autonomous vehicles for a system and method for autonomous parking that can locate a vacant parking space with high precision.

SUMMARY OF THE DISCLOSURE

Examples of the disclosure are directed to using one or more cameras on a vehicle, one or more range sensors on the vehicle and/or one or more location (including GPS) receivers on the vehicle to perform autonomous parking operations. In some examples, the vehicle can detect parking lines in a parking lot using its one or more cameras. In some examples, the vehicle can detect the end points of the parking lines. In some examples, the vehicle can localize the car in the parking lot using the detected end points and location data (such as GPS location data). In some examples, the vehicle can determine the occupancy state(s) of candidate parking spaces in the parking lot using the one or more range sensors. In some examples, if the vehicle determines that a candidate parking space is empty, the vehicle can select the candidate parking space to autonomously park in. In some examples, the vehicle can calculate a region of interest corresponding to the selected parking space. In some examples, the vehicle can detect selected parking space lines within the field of view of a selected camera. In some examples, the vehicle can calculate one or more errors in its position relative to a final parking position within the selected parking space. The vehicle can autonomously move itself to reduce and/or minimize the errors to park in the selected parking space.

DETAILED DESCRIPTION

FIG. 1illustrates an exemplary system block diagram of vehicle control system100according to examples of the disclosure. Vehicle control system100can perform any of the methods described below with reference toFIGS. 2-9. System100can be incorporated into a vehicle, such as a consumer automobile. Other example vehicles that may incorporate the system100include, without limitation, airplanes, boats, or industrial automobiles. Vehicle control system100can include one or more cameras106capable of capturing image data (e.g., video data) of the vehicle's surroundings, as will be described with reference toFIGS. 2-9. Vehicle control system100can also include one or more other sensors107(e.g., radar, ultrasonic, LIDAR, other range sensors, etc.) capable of detecting various characteristics of the vehicle's surroundings, and a location system, such as a Global Positioning System (GPS) receiver108, capable of determining the location of the vehicle. It should be noted that other types of location system can also be used, including cellar, WiFi, or other types of wireless-based and/or satellite-based location systems. Vehicle control system100can include an on-board computer110that is operatively coupled to the cameras106, sensors107and GPS receiver108, and that is capable of receiving the image data from the cameras and/or outputs from the sensors107and the GPS receiver108. The on-board computer110can also be capable of receiving parking lot map information105(e.g., via a wireless and/or internet connection at the vehicle). It is understood by ones of ordinary skill in the art that map data can be matched to location data in map-matching functions. In accordance with one embodiment of the invention, the on-board computer110can be capable of performing autonomous parking in a parking lot using camera(s)106and GPS receiver108, as described in this disclosure. In accordance with the preferred embodiment, the on-board computer110includes storage112, memory116, and a processor114. Processor114can perform any of the methods described with reference toFIGS. 2-9. Additionally, storage112and/or memory116can store data and instructions for performing any of the methods described with reference toFIGS. 2-9. Storage112and/or memory116can be any non-transitory computer readable storage medium, such as a solid-state drive or a hard disk drive, among other possibilities. The vehicle control system100can also include a controller120capable of controlling one or more aspects of vehicle operation, such as controlling motion of the vehicle during autonomous parking in a parking lot.

In some examples, the vehicle control system100can be connected to (e.g., via controller120) one or more actuator systems130in the vehicle and one or more indicator systems140in the vehicle. The one or more actuator systems130can include, but are not limited to, a motor131or engine132, battery system133, transmission gearing134, suspension setup135, brakes136, steering system137and door system138. The vehicle control system100can control, via controller120, one or more of these actuator systems130during vehicle operation; for example, to open or close one or more of the doors of the vehicle using the door actuator system138, to control the vehicle during autonomous driving or parking operations using the motor131or engine132, battery system133, transmission gearing134, suspension setup135, brakes136and/or steering system137, etc. The one or more indicator systems140can include, but are not limited to, one or more speakers141in the vehicle (e.g., as part of an entertainment system in the vehicle), one or more lights142in the vehicle, one or more displays143in the vehicle (e.g., as part of a control or entertainment system in the vehicle) and one or more tactile actuators144in the vehicle (e.g., as part of a steering wheel or seat in the vehicle). The vehicle control system100can control, via controller120, one or more of these indicator systems140to provide indications to a driver of the vehicle of one or more aspects of the automated parking procedure of this disclosure, such as successful identification of an empty parking space, or the general progress of the vehicle in autonomously parking itself.

FIG. 2Aillustrates an exemplary camera-based autonomous parking procedure according to examples of the disclosure. In some examples, vehicle204can be positioned at an entrance of parking lot202or can have entered parking lot202(as illustrated inFIG. 2A). Parking lot202(or any other location that has parking lines, such as a road) can include one or more parking spaces delineated by pairs of parking lines formed on the ground (e.g., white lines formed on black asphalt), as illustrated. Some of the parking spaces can be occupied by parked cars206. In some examples, at least one parking space208can be empty.

In some examples, a driver of vehicle204(or any other person associated with vehicle204, or vehicle itself, autonomously) can initiate an autonomous parking procedure when vehicle204is positioned at the entrance of parking lot202. In some examples, the driver of vehicle204can initiate the autonomous parking procedure at any location, not necessarily at the entrance of parking lot202—in such examples, vehicle204, if already inside parking lot202, can initiate the autonomous parking procedure of the disclosure, and if outside of parking lot202, can autonomously navigate to the entrance of parking lot202and then initiate the autonomous parking procedure. Once the autonomous parking procedure is initiated, vehicle204can begin autonomously moving through parking lot202to identify an empty parking space (e.g., parking space208), and can autonomously park in that empty parking space. The autonomous parking procedure can be camera-based, and vehicle204can utilize one or more of its onboard range sensors (e.g., radar, LiDAR, ultrasonic, etc.), GPS receiver and/or other sensors, in conjunction with its onboard camera(s), to perform the autonomous parking procedure, as will be described in more detail below. As such, in response to a single input from a user (or from vehicle204, itself), vehicle204can autonomously identify empty parking space208, and can autonomously park in it.

FIG. 2Billustrates exemplary method210for a camera-based autonomous parking procedure according to examples of the disclosure. Additional details of the steps of method210will be provided with reference toFIGS. 3-9, below. At212, the vehicle can detect, in images/video captured by one or more of its onboard cameras (e.g., camera(s)106), the locations of parking lines within a threshold distance of the vehicle (e.g., within the field(s)-of-view (FOV) of its one or more onboard cameras). In some examples, the camera(s) used by the vehicle in method210can be wide FOV camera(s), such as camera(s) having ˜180 degree FOV. Further, in some examples, the camera(s) used by the vehicle in method210can be located on one side of the vehicle (e.g., the right side, or the left side). Step212will be described in more detail with reference toFIGS. 3A-3E.

At214, the vehicle can detect the end points of one or more parking lines detected at step212. Step214will be described below in more detail with reference toFIGS. 4A-4F.

At216, the vehicle can localize itself within a map of the parking lot using the parking line ends detected at214and/or location determinations (e.g., determined by GPS108). In some examples, the map of the parking lot can include information (e.g., map information105) such as parking lot dimensions and parking line/parking space locations and dimensions. Further, in some examples, the map of the parking lot can be a predetermined map of the parking lot (e.g., a map that the vehicle downloads via an internet connection), or can be a map of the parking lot that the vehicle itself constructs. For example, the vehicle can drive (autonomously or otherwise) through the parking lot before performing the autonomous parking procedure of the disclosure, and using one or more of its onboard cameras, GPS, range sensors (e.g., included in sensor(s)107), etc., can construct the map of the parking lot. Localizing the vehicle within the map of the parking lot can include determining the position and/or orientation of the vehicle within the map of the parking lot. Step216will be described in more detail with reference toFIGS. 5A-5D.

At218, the vehicle can detect the state (e.g., empty, occupied, unknown) of one or more parking spaces in the parking lot. For example, the vehicle can utilize one or more of LiDAR, radar, ultrasonic, or other range sensors to determine whether a particular parking space within a threshold distance of the vehicle is empty, and if so, the vehicle's control system can utilize the coordinates of the empty parking space to autonomously park the vehicle in the empty parking space (e.g., using actuator systems130) according to steps220-226. Step218will be described in more detail with reference toFIGS. 6A-6G.

At step220, the vehicle can calculate a region of interest corresponding to the selected empty parking space. The vehicle can rely on map data and one or more images captured by its one or more cameras to construct the region of interest (e.g., using onboard computer110). Step220will be described in more detail with reference toFIGS. 7A-7D.

At step222, the vehicle can detect the lines of the selected parking space within a selected field of view. In some examples, the selected field of view can be the field of view of a selected camera positioned to monitor the selected parking space throughout steps220-226of method210. For example, the selected camera can be a rear camera for a rear-in parking maneuver or a front camera for a front-in parking maneuver. The lines can be detected using algorithms, steps, and methods similar to the details of steps212and214of method210. Step222will be described in more detail with reference toFIGS. 8A-8B.

At step224, the vehicle can calculate one or more errors in its position compared to a final parking position. In some examples, the error calculation(s) can be based on the vehicle's position determined in step216, the region of interest determined in step220, and/or the lines of the selected parking space detected in step222. The error calculation(s) can inform the vehicle how to autonomously move into the selected parking space. Step224will be described in more detail with reference toFIGS. 9A-9E.

At226, the vehicle can autonomously park itself in the empty parking space detected at step218. In some examples, the vehicle can autonomously navigate to the coordinates of the empty parking space determined at218to autonomously park in the empty parking space. Autonomously parking the vehicle can comprise autonomously entering a parked state. The parked state can comprise applying a parking brake, turning off the motor131or engine132of the vehicle, and/or otherwise powering down the vehicle. During parking, the vehicle can continuously repeat steps212,214,216,218,220,222, and224to continuously detect and/or refine the location of the parking space, which can be delivered to, and for use by, the control system of the vehicle as the vehicle moves into the parking space.

FIGS. 3A-3Eillustrate exemplary details for detecting parking lines using a camera on a vehicle in a camera-based autonomous parking procedure according to examples of the disclosure.FIGS. 3A-3Ecan correspond to step212inFIG. 2B, and the vehicle of the disclosure can continuously perform step212(as part of method210) as it moves through the parking lot to identify an empty parking space.FIG. 3Aillustrates vehicle304positioned alongside parking spaces310in parking lot302, which can be delineated by parking lines312. As previously discussed, in some examples, as part of the autonomous parking procedure of the disclosure, vehicle304can autonomously move along parking spaces310in parking lot302in search of an empty parking space in which to autonomously park (e.g., in a direction that is substantially perpendicular or otherwise non-parallel to parking lines312). As vehicle304moves through the parking lot, vehicle304can identify parking lines312in its vicinity (e.g., within the FOV of camera306) using onboard camera306. In some examples, camera306can be mounted on one side of vehicle304(e.g., the right side of vehicle304), and can be a wide FOV308camera, such as a fish-eye camera. As shown inFIG. 3A, camera306can capture images of one or more parking lines312to the right of vehicle304that are within FOV308.

Once images of parking lines312are captured, as described inFIG. 3A, the images captured by camera306can be transformed such that the images look like they are captured from a camera looking down on vehicle304from above, as shown inFIG. 3B. For example, if camera306provides wide-FOV images towards the right side of vehicle304, images captured by camera306may depict parking lines312as nonlinear and incorrectly oriented with respect to vehicle304and/or each other. Therefore, it can be beneficial to transform the images captured by camera306to present a top-down view of the surface of parking lot302in which parking lines312are linear (assuming they are actually linear) and accurately oriented with respect to vehicle304and/or each other. Image301inFIG. 3Bcan illustrate an exemplary image captured by camera306after being transformed as described above, and can be referred to as a “top image.” Transforming the images captured by camera306into top images can cause features on the ground of parking lot302(e.g., parking lines312) to appear accurately, while features above the ground of parking lot302may be distorted. Importantly, after the transformation, parking lines312in top image312can appear straight (assuming parking lines312are straight), and their orientation with respect to camera306/vehicle304can be accurate (e.g., if vehicle304is oriented perpendicular to parking lines312, and camera306is oriented parallel to parking lines312, parking lines312in top image301can appear as horizontal lines, as shown inFIG. 3B). As such, top image301can provide an accurate depiction of features (e.g., dimensions, positions, orientations, etc. with respect to camera306and/or vehicle304) on the ground of parking lot302, such as parking lines312, that are within FOV308of camera306.

Any number of warping transformations known in the art can be used to create top image301. The parameters of the warping transformation used by vehicle304can be determined according to intrinsic and/or extrinsic calibration parameters of camera306, which can be determined by using standard calibration procedures known in the art. In some examples, several assumptions about the camera306, the vehicle304, and the vehicle's surroundings can be made to create the top image. For example, it can be assumed that the position of camera306relative to the ground is known and the ground is flat. Exemplary calibration procedures relating to distorting/transforming images captured by cameras are described in Shah, Shishir, and J. K. Aggarwal, “A simple calibration procedure for fish-eye (high distortion) lens camera,”IEEE International Conference on Robotics and Automation, 1994, the contents of which are hereby incorporated by reference for all purposes.

After vehicle304creates top image301, vehicle304can search for parking lines312inside top image301. In some examples, vehicle304can search all of top image301for parking lines312, and in some examples, vehicle304can select a sub-window of top image301in which to search for parking lines312. The sub-window, if selected, can correspond to an area of parking lot302in the vicinity of vehicle304(e.g., on the right side of vehicle304), such as an area that is eight meters wide and ten meters long (e.g., any-sized area in which multiple parking lines312can exist). The remainder of the disclosure will refer to image processing operations that vehicle304can perform on the entirety of top image301to detect parking lines312, but it is understood that vehicle304can analogously perform such operations on a sub-window of top image301, if selected. Vehicle304can search for parking lines312in top image301as described with reference toFIGS. 3C-3D.

Specifically, vehicle304can apply a filter to top image301to calculate the magnitude and orientation of the image gradient at each pixel in top image301, as shown inFIG. 3C. Any number of image gradient filters, such as a Sobel gradient filter, can be used. The image gradient can represent a directional change in the intensity or color in top image301, and can reflect the magnitude and direction of such change. For example, parking lines312can be substantially white, and the surface of parking lot302can be substantially black (though inFIG. 3C, parking lines312are illustrated as being black, and the surface of parking lot302is illustrated as being white, for ease of illustration). Therefore, the image gradients at the boundaries of parking lines312and the surface of parking lot302can be relatively large, while the image gradient within a substantially uniformly-colored area of the surface of parking lot302, or within substantially uniformly-colored area of parking lines312, can be relatively small.FIG. 3Cillustrates some exemplary image gradients314at the boundaries of parking lines312and the surface of parking lot302. As shown inFIG. 3C, image gradients314can indicate the normal directions of the boundaries between parking lines312and the surface of parking lot302at the pixels located on or along those boundaries. Further, it is understood that the signs (positive or negative) of image gradients314depicted inFIG. 3Care exemplary only, and can be reversed as appropriate for a specific implementation of step212of method210.

In the example ofFIG. 3C, parking lot302also includes an imperfection316(e.g., a portion of parking lot302that is lighter than the remaining surface of parking lot302). Vehicle304has also determined image gradients318associated with imperfection316, as shown. Image gradients for other pixels in top image301are not illustrated, for ease of description.

After determining the magnitudes and directions of image gradients314/318at pixels in top image301, vehicle304can use the image gradients314/318to identify line(s) in top image corresponding to the boundaries of parking lines312. For example, vehicle304can create a two-dimensional Hough transform table, as known in the art, to record scores for each potential parking line312in top image301, as illustrated inFIG. 3D. These scores can be used to identify boundaries of parking lines312in top image301, as will be described below. For example, inFIG. 3D, table320can represent an exemplary Hough transform table, and can include a plurality of cells322. Each cell322of table320can correspond to a specific line in top image301(e.g., a line with a specific slope and position in top image301). For example, cell322A can correspond to line324A, cell322B can correspond to line324B, cell322C can correspond to line324C, cell322D can correspond to line324D, cell322E can correspond to line324E, and cell322F can correspond to line324F. Other cells322in table320can similarly correspond to other lines324in top image301(not illustrated for ease of description). Table320can include sufficient cells322such that the line324angle resolution represented by table320can be 0.5 degrees, and the line324position resolution represented by table320can be one pixel in top image301. In other words, table320can represent lines324at 0.5 degree slope increments and at single pixel position increments across top image301. Other line324angle and line324position resolutions can also be implemented by table320.

In some examples, vehicle304may only need to create table320for a limited range of line324angles (i.e., vehicle304may only need to search for parking lines312within a limited angle range), because vehicle304can be searching for parking lines312having a known orientation with respect to vehicle304(e.g., perpendicular to vehicle304or at another known angle with respect to vehicle304). In some examples, vehicle304can know this orientation of parking lines312from the map of parking lot302described above. For example, vehicle304can search for parking lines312within +/−10 degrees of the expected or known orientation of parking lines312, and therefore, can construct table320to only represent lines having slopes within +/−10 degrees of the expected or known orientation of parking lines312.

Once table320is created, vehicle304can detect lines (e.g., corresponding to boundaries of parking lines312) in top image301based on a voting algorithm. Specifically, one or more pixels in top image301can “vote” for certain cells322in table320depending on pixel and line properties, as will be described below. For example, in some examples, vehicle304can only allow for voting by pixels that have an image gradient magnitude that is larger than a threshold image gradient magnitude (e.g., 100 for a Sobel edge detector), so that only “strong” edges (e.g., pixels in edges that are likely to correspond to parking line312boundaries) in top image301may be allowed to vote in table320.

For those pixels with image gradient magnitudes that are larger than the threshold image gradient magnitude (“voting pixels”), vehicle304can vote (e.g., provide a single vote unit) for all Hough cells322corresponding to lines324having normals that are within a certain angle range of those pixels, and cross within a certain number of pixels of those pixels (i.e., are within a certain distance of the voting pixels). In some examples, vehicle304can vote for Hough cells322that correspond to lines324having normals that are within +/−30 degrees of the gradient directions of the voting pixels, and within +/−3 pixels of the locations of the voting pixels, though other voting criteria may similarly be used. It should be noted that in some examples, table320only has cells322that correspond to a limited range of line angles, as described above; therefore, voting may only be possible for lines within that limited range of line angles.

For example, inFIG. 3D, pixels326A,326B,326C and326D can have image gradient magnitudes larger than the image gradient magnitude threshold. Pixels326A and326B can vote for cell322F (corresponding to line324F) in table320, because line324F can be within a threshold number of pixels of pixels326A and326B, and pixels326A and326B can have image gradient directions that are within a threshold degree range of the normal of line324(e.g., the gradient directions of pixels326A and326B can be substantially parallel to the normal of line324F). Pixels326C and326D can similarly vote for cell322C (corresponding to line324C) in table320for similar reasons. With respect to line324D, pixel326D can vote for cell322D (corresponding to line324D), because line324D can be within a threshold number of pixels of pixel326D, and pixel326D can have a gradient direction that is within a threshold degree range of the normal of line324D. However, pixel326C may not vote for cell322D (corresponding to line324D), because while line324D can have a normal that is within the threshold degree range of the image gradient direction of pixel326C, line324D may not be within the threshold number of pixels of pixel326C. No pixels may vote for cell322E (corresponding to line324E), because the above conditions may not be met for any pixels in top image301. One or more pixels on the lower parking line312in top image301may vote for cell322B (corresponding to line324B) in accordance with the above conditions, and one or more pixels on imperfection316may similarly vote for cell322A (corresponding to line324A) in accordance with the above conditions.

Because parking lines312can be composed of two lines with opposing image gradients (e.g., upper boundaries and lower boundaries of parking lines312), parking line312detection can be improved if each voting pixel in top image301votes, not only for its line(s)/cell(s) in accordance with the above conditions, but also for line(s)/cell(s) that correspond to the other boundary of the parking line312on which the voting pixels are located. For example, pixels326A and326B, in addition to voting for cell322F (corresponding to line324F), can each also vote for cell322C (corresponding to line324C), because line324C can have a normal direction that is 180 degrees (in some examples, +/−5 degrees or some other range amount) rotated with respect to the image gradients of pixels326A and326B, and line324C can be a threshold distance (in some examples, within some range amount of the threshold distance) away from pixels326A and326B (e.g., 15 cm or some other distance corresponding to the width of parking lines312). Pixels326C and326D can similarly also vote for cell322F (corresponding to line324F). Other voting pixels in top image301can similarly vote for a second cell/line in accordance with the above conditions.

After the voting eligible pixels in top image301vote for cell(s)/line(s) in accordance with the above, vehicle304can identify line(s) that likely correspond to the upper/lower boundaries of parking lines312based on the results of the voting. For example, vehicle304can identify the cell322in table320with the greatest number of votes, which can correspond to and provide the parameters (e.g., slope and position) of the strongest detected line in top image301; this line, in turn, can correspond to a parking line312boundary in top image301. Then, vehicle304can clear out (or zero out) the voting results for a certain number of cells/lines in the vicinity of the identified cell/line, because other lines with similar positions and slopes likely may not correspond to another boundary of a parking line312; other parking line312boundaries in top image301are likely at least 15 cm (or another distance corresponding to the width of a parking line312) away from the boundary line identified above. Vehicle304can then identify another cell/line with the next-highest vote total, which can correspond to and provide the parameters of the next strongest detected line in top image301. Vehicle304can, again, clear the voting results for a certain number of cells/lines in the vicinity of the identified line. Vehicle304can continue the above steps until a certain number of lines have been detected (e.g., 15, 20 or 30 lines). For example, vehicle304may identify lines324A,324B,324C and324F as potential boundaries of parking lines312after completing the above steps.

In some examples, after identifying potential parking line312boundary lines, as described above, vehicle304can rank these lines based on their voting scores, and can remove lines from contention that have voting scores less than a certain voting score threshold. In some examples, vehicle304can additionally or alternatively remove lines from contention that have voting scores that are less than half of the highest voting score for identified lines in the current top image301frame (camera306can continuously capture images/frames of the surroundings of vehicle304, and the parking line detection procedure ofFIGS. 3A-3Ecan be performed on each image/frame captured by camera306). For example, vehicle304can remove line324A from contention as a potential boundary of a parking line312, because its voting score can be less than the voting score threshold, and/or less than half of the highest voting score for top image301(e.g., because only pixels on imperfection316may have voted for line324A).

After performing the above, in some examples, vehicle304can eliminate lines from contention that are separated by distances other than specified distances (or distance ranges within those specified distances). For example, lines corresponding to the two boundaries of a parking line312should be separated from each other by a certain distance (e.g., 15 cm, or another expected parking line width), and lines corresponding to boundaries of parking lines312on either side of a parking space should be separated from each other by another certain distance (e.g., 2.75 m, or another expected parking space width). Therefore, vehicle304can eliminate lines from contention that are not within 15 cm or 2.75 m of another detected line, for example. The remaining lines after performing the above can correspond to the detected boundaries of parking lines312in top image301.

FIG. 3Eillustrates an exemplary method350of detecting lines in top image301that correspond to parking line312boundaries according to examples of the disclosure. Method350can correspond to the examples described with reference toFIGS. 3A-3D. At352, vehicle304can determine image gradients for pixels in top image301(e.g., as described with reference toFIG. 3C). At354, vehicle304can create a Hough transform table for use in pixel voting to identify lines in top image301that correspond to boundaries of parking lines312(e.g., as described with reference toFIG. 3D). At356, vehicle304can perform Hough voting for one or more lines/cells in correspondence with one or more pixels in top image301(e.g., as described with reference toFIG. 3D). At358, vehicle304can identify a subset of the lines represented by the Hough table as lines corresponding to boundaries of parking lines312in top image301(e.g., as described with reference toFIG. 3D).

After vehicle304detects a collection of lines corresponding to parking line312boundaries in top image301, vehicle304can utilize those lines as indications of local regions in top image301in which vehicle304can search for the end of each parking line312. Specifically, after detecting lines as inFIGS. 3A-3E, vehicle304may be able to determine the vertical distance/orientation of those lines with respect to a reference point on vehicle304based on the parameters (e.g., slope and position) of those lines (e.g., with respect to the center of the rear axle of vehicle304, or any other known reference point used by vehicle304as a reference for a coordinate system). However, vehicle304may not yet have knowledge of the positions of the ends of parking lines312with which to localize itself with respect to the parking spaces in parking lot302. Therefore, vehicle304can utilize the lines detected inFIGS. 3A-3Eto determine the locations of the end points of parking lines312, as will be described below.

FIGS. 4A-4Fillustrate exemplary details for detecting the locations of the ends of parking lines312in a camera-based autonomous parking procedure according to examples of the disclosure.FIGS. 4A-4Fcan correspond to step214inFIG. 2B, and the vehicle of the disclosure can continuously perform step214(as part of method210) as it moves through the parking lot to identify an empty parking space. After detecting lines inFIGS. 3A-3E, vehicle304can group the detected lines into pairs (e.g., pairs corresponding to the upper/lower boundaries of parking lines412). Specifically, the detected lines can be grouped into pairs based on a specific distance requirement (e.g., 15 cm, corresponding to the average or expected width of a parking line412); in other words, a first detected line can be paired with a second detected line that is separated from the first detected line by the specific distance requirement. If one or more detected lines are not paired at this stage (e.g., because no other detected lines are separated from those lines by the specific distance), those unpaired detected lines can be ignored by vehicle304in determining parking line412end point locations below.

After pairing the detected lines, vehicle304can, for each pair of detected lines, select sub-regions of top image301that include the detected lines, as well as a certain amount of additional image area above and below the pairs of detected lines. Each of these sub-regions can be referred to as a “line pair patch.”FIG. 4Aillustrates exemplary line pair patch401that includes the pair of detected lines424A and424B. Line pair patch401also includes parking line412, and lines424A and424B can correspond to the upper and lower boundaries of parking line412, as shown. Parking line412can include imperfection416, which can correspond to a worn or otherwise damaged or occluded portion of parking line412. Line pair patch401can extend the entire width of top image301, and a certain number of pixels above line424B (e.g., eight pixels), and a certain number of pixels below line424A (e.g., six pixels). In some examples, vehicle304can filter line pair patch401with a noise-reducing filter (e.g., a noise-reducing 2-D median filter of size 5×5).

Next, vehicle304can identify the pixels in line pair patch401that make up the top and bottom edges of parking line412. Specifically, vehicle304can determine the image gradient magnitude and orientation at each pixel in line pair patch401(e.g., by convolving a filter over line pair patch401that calculates the image gradient at each pixel, similar to as described with reference toFIG. 3C), as shown inFIG. 4B. For example, vehicle304can determine image gradients414for pixels in line pair patch401, including pixels426A,426B,426C and426D. Only image gradients414for pixels on parking line412are illustrated for ease of description, though it is understood that vehicle304can determine the image gradients of other pixels in line pair patch401as well. Pixels426A,426B and426C can be located on the top boundary of parking line412(though pixels426B and426C can be located on imperfection416), and pixel426D can be located on the bottom boundary of parking line412. Vehicle304can differentiate pixels that correspond to the top and bottom edges of parking line412based on the image gradient orientations of those pixels. For example, pixels with image gradients within a first range of orientations (e.g., orientations corresponding to the top edge of parking line412) can be determined to correspond to the top edge of parking line412, and pixels with image gradients with a second range of orientations (e.g., orientations corresponding to the bottom edge of parking line412, ˜180 rotated with respect to the range of orientations corresponding to the top edge of parking line412) can be determined to correspond to the bottom edge of parking line412. For example, vehicle304may eliminate pixels426B and426C as edge pixels, because they may not satisfy the image gradient orientation requirements, above. Additionally, vehicle304can eliminate pixels from contention that have image gradient magnitudes that are less than an image gradient threshold, because only parking line412edge pixels may be of interest to vehicle304. All pixels in line pair patch401that meet the above orientation criteria and have an image gradient magnitude that is larger than the image gradient threshold can be determined to belong to the top and bottom edges, respectively, of parking line412.

Next, vehicle304can pair top and bottom edge pixels along pixel columns in line pair patch401, as illustrated inFIG. 4C. For example, vehicle304can utilize a template that is matched when two pixels in a given column of pixels are separated by a certain distance (e.g., a certain number of pixels, such as three, four or five pixels, corresponding to the width of parking line412). Using such a template, vehicle304can start from the right-most identified edge pixels, and can move leftward in line pair patch401to determine whether (and/or the degree to which) the identified edge pixels match the template. Then, vehicle304can identify the location (e.g., row/column) in line pair patch401at which the identified top/bottom edge pixels most closely match the template. Vehicle304can use this location (e.g., location428A) as a starting point for the steps that follow. Specifically, at starting point428A, vehicle304can search for a top edge pixel above starting point428A (e.g., pixel426E), and a bottom edge pixel below starting point428A (e.g., pixel426F), and can check if the column of pixels in which starting point428A is located also includes non-edge pixels (e.g., pixels not labeled as edge pixels inFIG. 4B) above and below the top and bottom edge pixels (e.g., pixels426E and426F, respectively). If so, vehicle304can store the top-most and bottom-most edge pixel locations for the current pixel column (e.g., the locations for pixels426E and426F, respectively) for use later in creating linear models corresponding to the top and bottom edges of parking line412.

Then, vehicle304can use the pixel row of the center location (e.g., location428A) between the stored top-most and bottom-most edge pixels from the current pixel column as a starting center point for the next pixel column closest to vehicle304(e.g., the pixel column to the left of the current pixel column that includes pixels426E and426F in line pair patch401). Vehicle304can then repeat the above-described process of searching for and storing a top-most and bottom-most edge pixel in that pixel column (e.g., pixels426G and426H), identifying a center pixel location for that pixel column (e.g., location428B), and moving to the next pixel column closest to vehicle304for all columns in line pair patch401that include edge pixels identified inFIG. 4B, such that all of line pair patch401is explored for top and bottom edge pair locations.

In some examples, while searching for top and bottom edge pixel pairs, vehicle304can bridge gaps along the top or bottom edges of parking line412up to an upper limit of pixels (e.g., 100 pixels). For example, because of imperfection416in parking line412, a gap of top edge pixels may exist. While performing the above-described steps, vehicle304can disregard this gap (in some examples, up to an upper limit), and can continue past this gap in determining top and bottom edge pixel pairs, as described above. Bridging such gaps can improve parking line412detection in circumstances where one or more portions of a parking line412are occluded or missing.

If vehicle304identifies greater than a threshold number of top/bottom edge pixel pairs above (e.g., 10, 15 or 20 top/bottom edge pixel pairs), vehicle304can check one or more characteristics of those pixel pairs to validate that the pixel pairs correspond to a parking line412and/or exhibit the characteristics of a parking line412. For example, vehicle304can determine whether one or more (or all) of the following conditions are met for the identified edge pixel pairs: 1) the variance in the locations (e.g., in a specific dimension, such as the vertical dimension) of all of the top edge pixels in the top/bottom edge pixel pairs is less than a threshold amount (e.g., one pixel); 2) the variance in the locations (e.g., in a specific dimension, such as the vertical dimension) of all of the bottom edge pixels in the top/bottom edge pixel pairs is less than a threshold amount (e.g., one pixel); and 3) the variance of the difference between the locations (e.g., in a specific dimension, such as the vertical dimension) of the top and bottom edge pixels in all of the top/bottom edge pixel pairs is less than a threshold amount (e.g., two pixels).

If the top/bottom edge pixel pairs meet one or more (or all) of the conditions above, vehicle304can fit the top edge pixels in the pairs to a top linear model430B, and the bottom edge pixels in the pairs to a bottom linear model430A. Once vehicle304determines the top and bottom linear models, vehicle304can discard those edge pixel pairs that include edge pixels that are greater than a threshold distance (e.g., two pixels) away from the locations of the top or bottom linear models (e.g., because those edge pixels may poorly approximate the actual boundaries of parking line412).

In some examples, the top and bottom boundaries of parking line412can be substantially parallel. Further, vehicle304can know the expected orientation of parking lines412in top image301/line pair patch401. Therefore, if the difference in slope of the top430B and bottom430A linear models exceeds a certain threshold difference (e.g., one, two or three), the collection of top/bottom edge pixels pairs that vehicle304identified above can be discarded by vehicle304. Similarly, if the slope of either the top430B or bottom430A linear models deviates from the expected orientation of parking lines412by greater than a threshold amount, the collection of top/bottom edge pixels pairs that vehicle304identified above can be discarded by vehicle304.

After performing the above steps, the collection of top/bottom edge pixels pairs can be candidate pixel pairs for an actual parking line412. Next, vehicle304can determine the location of the end of the parking line412as will be described with reference toFIG. 4D. Specifically, vehicle304can start searching for a short line segment (e.g., corresponding to the line segment comprising the end of parking line412) that is orthogonal (or substantially orthogonal) to top linear model430B and bottom linear model430A. Vehicle304can start this search from the left-most (e.g., closest to vehicle304) pair of top/bottom edge pixels, and can move leftward (e.g., towards vehicle304) all the way to the end (e.g., left end) of line pair patch401. To find the end436of parking line412, vehicle304can utilize template432that specifies particular image gradient directions and magnitudes for pixels that would be located in the vicinity of the end436of parking line412; specifically, pixels that would be located on the top edge of parking line412(e.g., within a certain distance of the end436of parking line412), located on the end436of parking line412, and located on the bottom edge of parking line412(e.g., within a certain distance of the end436of parking line412). Vehicle304can compare template432to the image gradient orientations and magnitudes of pixels in line pair patch401between the left-most (e.g., closest to vehicle304) top/bottom edge pixel pair and the edge of line pair patch401that is closest to vehicle304. After performing this comparison to template432, vehicle304can identify the pattern of pixels in line pair patch401that most closely match the orientation and magnitude of template432as being pixels that make up the end of parking line412(e.g., the end of parking line412including end point436).

In some examples, vehicle304can further validate that the above-identified pattern of pixels indeed makes up the end436of parking line412by performing a pixel intensity variance check, as illustrated inFIG. 4E. For example, vehicle304can compare the intensity variance of all pixels to the left of end point436in line pair patch401(e.g., in region438) to an intensity variance model of pixels on the surface of the road/parking lot. The intensity variance model of pixels on the surface of the road can be built up from road surface pixels relative to their direction and distance from camera306along the direction of travel of vehicle304in parking lot302. If the intensity variance of the pixels in region438exceeds the variance model of pixels on the surface of the road, end point436can be discarded by vehicle304as a candidate end point, because if the intensity variance of the pixels in region438exceeds the variance model of pixels on the surface of the road, this can indicate that end point436may not truly correspond to the end of parking line412, but rather may correspond to some other feature on the surface of parking lot302or on another vehicle in parking lot302.

Pairs of detected lines (e.g., lines detected inFIGS. 3A-3E) in top image301that do not endure the steps described above with reference toFIGS. 4A-4Ecan be determined by vehicle304to not correspond to a parking line412.

FIG. 4Fillustrates an exemplary method450of detecting end point(s) of parking line(s) in top image301according to examples of the disclosure. Method450can correspond to the examples described with reference toFIGS. 4A-4E. At452, vehicle304can pair top and bottom lines corresponding to parking line412boundaries (e.g., as described with reference toFIG. 4A). At454, vehicle304can identify top and bottom edge pixels on boundaries of parking lines412for each top/bottom line pair (e.g., as described with reference toFIG. 4B). At456, vehicle304can match top and bottom edge pixels with one another (e.g., as described with reference toFIG. 4C). At458, vehicle304can check top and bottom edge pixel variance to ensure the variance falls within a specified variance threshold (e.g., as described with reference toFIG. 4C). At460, vehicle304can fit linear models to the identified top and bottom edge pixels (e.g., as described with reference toFIG. 4C). At462, vehicle304can discard outlier edge pixels based on the linear models (e.g., as described with reference toFIG. 4C). At464, vehicle304can identify the end of a parking line412(e.g., as described with reference toFIG. 4D). At466, vehicle304can verify the identified end of the parking line412(e.g., as described with reference toFIG. 4E).

After identifying the end point(s)436of parking line(s)412in top image301(e.g., as described with reference toFIGS. 4A-4F), vehicle304can use those end point(s) as well as GPS data to determine its position and orientation in parking lot302, as will be described with reference toFIGS. 5A-5D. Specifically, as will be described below, vehicle304can utilize a map of parking lot302(which can include at least positions of parking line-ends in parking lot302), and can fuse multiple sources of position measurements (e.g., GPS and parking line-end determinations) to determine its position and orientation in parking lot302.

FIGS. 5A-5Dillustrate exemplary details for localizing vehicle304in parking lot302using parking line512end points536and GPS measurements according to examples of the disclosure.FIGS. 5A-5Dcan correspond to step216inFIG. 2B, and the vehicle of the disclosure can continuously perform step216(as part of method210) as it moves through the parking lot to identify an empty parking space.FIG. 5Aillustrates exemplary map501of parking lot302. In some examples, map501can include location(s) of end point(s)536of parking lines512. In some examples, map501can also include orientation information for parking lines512, dimensions of parking lot302and/or parking lines512, and/or other information that may describe the physical layout of parking lot302. In some examples, map501may be predefined (e.g., provided by a third party source via an internet connection at vehicle304), or can be constructed by vehicle304itself while in parking lot302.

To localize itself within parking lot302, vehicle304can initialize a plurality of candidate vehicle locations506(also referred to as “particles) at random positions across the entirety of map501, as shown inFIG. 5B. In some examples, the number of particles506initialized by vehicle304in map501can be predetermined or based on the size of parking lot302/map501(e.g., more particles506for a larger map501, and fewer particles506for a smaller map). Each particle506can correspond to a candidate vehicle position and orientation in map501.

After initializing particles506, as described above, vehicle304can assign probabilities to particles506based on end points536of parking lines512(e.g., as determined inFIGS. 4A-4F) and GPS measurements. Specifically, vehicle304can determine its location relative to the end points536of parking lines512determined inFIGS. 4A-4F(e.g., three feet to the left of an end point536of a parking line512). For each location in map501that corresponds to this relative location of vehicle304with respect to the identified end points536, vehicle304can assign particles506that fall within a circle508of a given radius or other area of a given size (e.g., corresponding to the error expected from parking line512end536detection inFIGS. 4A-4F) a higher probability than particles506that fall outside of the circle508. In some examples, every particle506inside the circle508can be assigned the same high probability, while the probabilities assigned outside of the circle508can gradually change from the high probability at the edge of the circle508to zero probability as the particles506are further and further from the circle508. In some examples, because vehicle304may only be capturing images of a subset of parking lines512in parking lot302, and thus subset of parking line512ends536, at any given moment in time, the relative location that vehicle304determines with respect to the end points536of parking lines512may not be unique, and multiple locations in map501may correspond to the determined relative location of vehicle304(e.g., as illustrated inFIG. 5B). In some examples, as vehicle304captures images of more parking lines512at any moment in time, the number of locations on map501to which the relative location of vehicle304corresponds can become smaller.

In addition to assigning parking line512end point 536-based probabilities to particles506, vehicle304can assign GPS-based probabilities to particles506. The GPS-based probabilities assigned by vehicle304to particles506can be cumulative of the parking line512end point 536-based probabilities assigned by vehicle304to particles506. Specifically, vehicle304can determined its GPS location, and can assign particles506that fall within a circle510of a given radius or other shape of a given size (e.g., corresponding to the error expected from a location determined using a GPS receiver) centered at the determined GPS location a higher probability than particles506that fall outside of the circle510. In some examples, every particle506inside the circle510can be assigned the same high probability, while the probabilities assigned outside of the circle510can gradually change from the high probability at the edge of the circle510to zero probability as the particles506are further and further from the circle510. In some examples, the error expected from a GPS location determination can be higher than an error expected from the parking line512end point 536-based location determination, and therefore, the radius of circle510can be larger than the radius of circle508. Further, in some examples, GPS-based location can be unique, whereas parking line512end point 536-based location may not be; as such, vehicle304may only assign probabilities to particles506based on circle510at one location in map501.

After vehicle304has assigned the above probabilities to particles506, some particles506will have been assigned probabilities based only on a GPS-based location determination (e.g., particles506within only circle510), other particles506will have been assigned probabilities based on an end point 536-based location determination (e.g., particles within only circles508), and some particles506will have been assigned probabilities based on both a GPS-based location determination and an end point 536-based location determination (e.g., particles within circles508and circle510, which can, therefore, have the highest probabilities of particles506in map501). At this point, vehicle304can perform a weighted resampling of particles506in map501, such that vehicle304can pick particles506with higher probabilities as vehicle304location candidates more often than particles with lower probabilities. This resampling step can provide the final distribution for the position and orientation candidates for vehicle304. In some examples, vehicle304can approximate this distribution as a Gaussian distribution. Vehicle304can identify the mean of the distribution as the location estimate of vehicle304at the current time-step (e.g., position and orientation), and can identify the standard deviation of the distribution as the error of this estimation.

As mentioned above, vehicle304can perform the above steps to estimate its location at each of a plurality of time-steps (e.g., continuously) such that its location estimate remains accurate and current. At each time step, vehicle304can perform the steps described above, except as otherwise modified below. Specifically, at consecutive time-steps (e.g., time-steps after the initial time-step), particles506can be initialized in map501in an area (e.g., of predefined size/shape, such as a circle) surrounding the location estimate determined at the previous time step. In some examples, these particles506can replace the particles506used in the previous time step, and in other examples, these particles506can be in addition to the particles506used in the previous time step. The size of this area, and the range of orientations represented by these newly-initialized particles506, can be determined based on the amount of error expected in determining/predicting motion of vehicle304, as will be described in more detail below. Once these newly-initialized particles506are placed in map501, vehicle304can determine its location in the current time-step in the same manner as described above.

In some examples, in addition or alternatively to initializing particles506in consecutive time-steps as described above, vehicle304can split particles506into multiple particles around the original particles if vehicle304is moving (in some examples, vehicle304may not split particles506in consecutive time-steps if vehicle304is not moving, so as to reduce the likelihood that error in location estimation will increase rapidly when vehicle304is not moving). Such particle506splitting can help avoid overfitting the location estimate of vehicle304over time, and can allow for more accurate modeling of the resulting location distribution described previously. For example, referring toFIG. 5C, in consecutive time-steps if vehicle304is moving, vehicle304can propagate particles506from the previous time-step by a distance traveled by vehicle304since the previous time-step. Vehicle304can determine this distance based on a motion model, which can estimate incremental motion of vehicle304using dead-reckoning (e.g., by subtracting measurements obtained at consecutive time-steps from vehicle motion sensors such as wheel-encoders and yaw-rate sensors). The error expected in this propagation distance can be expressed in how vehicle304splits particles506based on the determined motion of vehicle304. For example, vehicle304can split particle506A into particles506B and506C. Particle506B can represent particle506A having been propagated by a maximum distance traveled by vehicle304since the last time-step, and particle506C can represent particle506B having been propagated by a minimum distance traveled by vehicle304since the last time-step. The difference in propagation distance between particles506B and506C can correspond to the error expected in the travel distance determination provided by the motion model of vehicle304. Particles506B and506C can similarly track and account for errors in orientation tracking provided by the motion model of vehicle304. Other particles506can similarly be split and propagated in map501based on the determined motion of vehicle304, as described above. Once particles506have been split and propagated, vehicle304can determine its location in the current time-step in the same manner as described above.

FIG. 5Dillustrates an exemplary method550of localizing vehicle304in parking lot302using parking line512end points536and GPS measurements according to examples of the disclosure. Method550can correspond to the examples described with reference toFIGS. 5A-5C. At552, vehicle304can initialize particles506in map501as candidate vehicle locations for a current time-step of method550(e.g., as described with reference toFIG. 5B). At554, vehicle304can assign parking line512end point 536-based location probabilities to particles506in map501(e.g., as described with reference toFIG. 5B). At556, vehicle304can assign GPS-based location probabilities to particles506in map501(e.g., as described with reference toFIG. 5B). At558, vehicle304can resample candidate vehicle location particles506in map501to create a distribution of candidate vehicle locations (e.g., as described with reference toFIG. 5B). At560, vehicle304can determine its location at the current time-step of method550based on the distribution of candidate vehicle locations (e.g., as described with reference toFIG. 5B). At562, vehicle304can initialize new particles506for a next time-step of method550(e.g., as described with reference toFIGS. 5B-5C). At564, if vehicle304has not moved since the last time-step of method550, method550can return to step554. At564, if vehicle304has moved since the last time-step of method550, vehicle304can propagate particles506from the last time-step of method550in accordance with the motion of vehicle304since the last time-step (e.g., as described with reference toFIG. 5C). In this way, vehicle304can accurately and continuously localize itself within parking lot302using one or more onboard cameras and a GPS receiver.

After localizing itself within parking lot302(e.g., as described with reference toFIGS. 5A-5D), vehicle304can identify empty parking spaces in parking lot302, as will be described with reference toFIGS. 6A-6G. Specifically, as will be described below, vehicle304can represent parking lot304by a spatial grid of cells (e.g., a two-dimensional occupancy grid including rows and columns of occupancy cells that each correspond to a two-dimensional area of parking lot302), and can assign occupancy values to these cells based on data from various onboard range sensors on vehicle304(e.g., LiDAR, ultrasonic, radar, etc.). Vehicle304can then correspond those cells with parking spaces in parking lot302to determine whether a given parking space is empty or occupied.

FIGS. 6A-6Gillustrate exemplary details for determining the occupancy states of parking spaces in parking lot302according to examples of the disclosure.FIGS. 6A-6Gcan correspond to step218inFIG. 2B, and the vehicle of the disclosure can continuously perform step218(as part of method210) as it moves through the parking lot to identify an empty parking space.FIG. 6Aillustrates an exemplary occupancy grid601with which vehicle304can represent the occupancy of parking lot302. Occupancy grid601can include rows and columns of cells602. In some examples, fewer or more cells602can be used by vehicle304to represent the occupancy of parking lot302. Vehicle304can be located inside parking lot302, as illustrated inFIG. 6A. Further, some parking spaces formed by parking lines612can be occupied by other vehicles606, while other parking spaces formed by parking lines612can be unoccupied. Vehicle304can include one or more range sensors608(e.g., LiDAR, radar, ultrasonic, etc.). In the example ofFIG. 6A, the size of a cell602can be substantially the same as the size of a parking space; however, it is understood that the examples described here can be applied in analogous manners to occupancy grids601in which the size of a cell602can be larger or smaller than the size of a parking space.

At a first time-step of determining the occupancy states of parking spaces in parking lot302, vehicle304can initialize each cell602in occupancy grid601with a zero value (or a value corresponding to a zero or unknown occupancy state value), as illustrated inFIG. 6A. For the purposes of this disclosure, cells602inFIGS. 6A-6Fthat do not include an indication of a numeric value can be assumed to have zero values.

Object detections from range sensor(s)608can be used by vehicle304to update the values of one or more cells602, as illustrated inFIG. 6B. For example, cells602in which range sensor(s) detect an object can have their existing values incremented by +1 (or another value that can be used to indicate that the cells602are occupied in a manner similar to that described here). Cells602that fall along a line (e.g., corresponding to a line travelled by a LiDAR beam) from range sensor(s)608to the cells602in which objects are detected can have their existing values incremented by −1 (i.e., decremented by +1 or another value that can be used to indicate that the cells602are occupied in a manner similar to that described here), because cells602between the cell602in which range sensor(s)608detected an object and range sensor(s) can be assumed to be empty. More generally, cells602in which range sensor(s) detect no objects can also have their existing values decremented by +1. For example, referring toFIG. 6B, range sensor(s)608can detect vehicle606in cell602A. Therefore, the value of cell602A can be incremented by +1. The values of cells602between cell602A and range sensor(s)608can be decremented by +1, such as cell602C. The value of cell602B can remain as it was before (e.g., not incremented or decremented), because cell602B can be out of sight of range sensor(s)608(e.g., blocked by vehicle606in cell602D). Other cells602in occupancy grid601can similarly have their values updated according to detections by range sensor(s)608, as described above.

After updating the values of cells602as described above, vehicle304can detect candidate parking spaces in which vehicle304can park. To do so, in some examples, vehicle304can search for parking line612ends636that are within a circle610(or other area) with a specified radius (e.g., six feet, eight feet, ten feet, etc.) of a reference point on vehicle304(e.g., its rear axle), as shown inFIG. 6C. Vehicle304can determine these parking line612ends636from previously determined parking line612ends636on the map of the parking lot (e.g., as determined inFIGS. 4A-4F). For example, as shown inFIG. 6C, vehicle304can identify three parking line612ends636to its right and three parking line612ends636to its left that are within circle610. From this collection of parking line612ends636, vehicle304can select pairs of parking line612ends636that are substantially a threshold distance apart (e.g., 2.75 meters apart, +/−a distance range, such as in a standard parking space or as reflected in the map of the parking lot) to construct a list of parking line612end636pairs. Next, using its determined position and orientation (e.g., as determined inFIGS. 5A-5D), vehicle304can discard parking line612end636pairs that appear on one side of vehicle304(e.g., the left side of vehicle304), and can keep parking line612end636pairs that appear on the other side of vehicle304(e.g., the right side of vehicle304). Vehicle304may only maintain parking line612end636pairs that are on one side of vehicle304, because in some vehicle jurisdictions, traffic etiquette and/or laws may dictate parking should occur on one side of vehicle304or another. For example, vehicle304may only maintain parking line612end pairs on its right side, and therefore, inFIG. 6C, two pairs of parking line612ends636can remain: pair636A-636B, and pair636B-636C, as shown inFIG. 6D. Using these two pairs of parking line612end636pairs, vehicle304can construct rectangular parking spaces for each pair by extending lines away from vehicle304from each parking line612end636in the above pairs. In some examples, vehicle306may not need to construct parking spaces on its own, because the map of the parking lot used by vehicle304may already include such information.

Once vehicle304has constructed (or otherwise identified) candidate parking spaces, as described above, vehicle304can evaluate the occupancy of those parking spaces based on cells602in occupancy grid601. Specifically, vehicle304can analyze the values of one or more cells602in occupancy grid601that cover or are within the area of the candidate parking spaces identified above. Vehicle304can utilize two thresholds in evaluating the occupancy of the candidate parking spaces. In some examples, the two thresholds utilized can be in the form of +/−(time constant)m, where “time constant” can be a time constant by which the values of cells602can be multiplied each time step (e.g., to “forget” the occupancy states of cells602over time), and m can correspond to the number of time steps required to forget the states (e.g., occupied/empty) of cells602. Other thresholds can similarly be used. Cell602values above +(time constant)mcan indicate an occupied cell602, cell602values below −(time constant)mcan indicate an empty cell602, and cell602values in between +(time constant)mand −(time constant)mcan indicate an unknown state for a cell602. In the examples ofFIGS. 6A-6F, “time constant” can be 0.3 and “m” can be 2, though it is understood that other “time constants” and values for “m” can similarly be utilized. When determining the occupancy of a given candidate parking space, if any cell602within the candidate parking space has a value that is greater than the positive occupancy threshold (e.g., +(time constant)m), vehicle304can determine that detection of an object within that cell602inside the candidate parking space has been observed in the last “m” time steps, and therefore, vehicle304can determine that the candidate parking space is occupied. If all of the cells602within the candidate parking space have values that are less than the negative occupancy threshold (e.g., −(time constant)m), vehicle304can determine that no detection of an object within the parking space has been observed within the last “m” time steps, and therefore, vehicle304can determine that the candidate parking space is empty. Otherwise, vehicle304can determine that the occupancy of the candidate parking space is unknown or unseen.

For example, referring again toFIG. 6D, the values of all of the cells602corresponding to the two candidate parking spots identified on the right of vehicle304can be +1, which can be greater than +0.32(0.09). Therefore, vehicle304can determine that both of the candidate parking spaces are occupied.

As previously described, in order to “forget” the occupancy states of cells602in occupancy grid601(and thus the occupancy states of parking spaces corresponding to those cells602), vehicle304can multiply the value of every cell602in occupancy grid601by “time constant” (e.g., 0.3) at the end of every time step. For example,FIG. 6Eillustrates exemplary cell602values after vehicle304multiplies the cell602values inFIG. 6Dby a time constant of 0.3. After multiplying the values of cells602by “time constant,” vehicle304can repeat the steps described above to determine the occupancy states of cells602/parking spaces for the current time step.

FIG. 6Fillustrates vehicle304having moved over multiple time steps such that vehicle304has identified two candidate parking spaces640A and640B to its right, in the manner described above. As a result of having moved, vehicle304can now detect occupancy in some cells602that it could not previously detect (e.g., cell602E), and therefore vehicle304has started updating the value(s) of those cells. Further, vehicle304can now no longer detect occupancy in some cells602that is could previously detect (e.g., cells602F and602G), and therefore vehicle304has stopped updating the value(s) of those cells. Vehicle304has continued to update the values of cells602each time step, in the manner described above. Finally, parking space640B, which was previously occupied by a vehicle606, is no longer occupied by a vehicle606.

Vehicle304can determine the occupancy states of parking spaces640A and640B in the manners previously described. Specifically, “time constant” can be 0.3, and m can be 2. Therefore, the positive occupancy threshold can be +0.09 and the negative occupancy threshold can be −0.09. Cell602corresponding to parking space640A can have a value of −0.6, which can be less than the negative threshold. Therefore, vehicle304can determine that parking space640A is empty. On the other hand, cell602corresponding to parking space640B can have a value of −0.05 (e.g., parking space640B can have been recently vacated by a vehicle606). Therefore, vehicle304can determine that the occupancy state of parking space640B is unknown, because −0.05 can be in between −0.09 and +0.09. Therefore, in the example ofFIG. 6F, vehicle304can identify parking space640A as an empty candidate parking space, and can proceed to autonomously park in parking space640A, as described with reference to step226in method210inFIG. 2B.

FIG. 6Gillustrates an exemplary method650of identifying an empty candidate parking space for autonomous parking according to examples of the disclosure. Method650can correspond to the examples described with reference toFIGS. 6A-6F. At652, vehicle304can create an occupancy grid and initialize cell values to initial values (e.g., as described with reference toFIG. 6A). At654, vehicle304can update the cell values based on range sensor(s) detections (e.g., as described with reference toFIG. 6B). At656, vehicle304can identify candidate parking spaces in the parking lot (e.g., as described with reference toFIGS. 6C-6D). At658, vehicle304can determine the occupancy states of the candidate parking spaces (e.g., as described with reference toFIG. 6D). At660, if vehicle304has determined that a valid candidate parking space is empty, vehicle304can park in that empty parking space at662(e.g., as described with reference to step226in method210inFIG. 2B). However, if vehicle304has determined that no valid parking space is empty, vehicle304can autonomously move at664(e.g., through the parking lot towards additional parking spaces), and method650can return to step654(e.g., as described with reference toFIG. 6F). Throughout method650, vehicle304can multiply the values of cells within the occupancy grid with a time constant at each time step to make vehicle304forget the occupancy of cells within the grid over time (e.g., as described with reference toFIGS. 6E-6F). In this way, vehicle304can autonomously identify and select an empty parking space in the parking lot in which to park.

FIGS. 7A-7Dillustrate exemplary details for calculating a region of interest corresponding to the selected parking space according to some examples of the disclosure.FIGS. 7A-7Dcan correspond to step220inFIG. 2B, and the vehicle of the disclosure can continuously perform step220(as part of method210) as it autonomously parks in the parking lot302.FIG. 7Aillustrates the vehicle304determining the region of interest702containing the selected parking space710. In some examples, an estimate of the region of interest702can be obtained from map data, one or more previously captured images, and/or other data relied on to locate the vehicle304as described above with reference toFIGS. 5A-5D. Selected parking space710can include final parking position704, which can correspond to the desired location of the rear axle706of vehicle304once it is finished parking, for example. In some examples, selected parking space710can be initially detected by a range sensor708of vehicle304(e.g., after determining the occupancy of the selected parking space710as described with reference toFIGS. 6A-6G). The accuracy of the region of interest702based on the range sensor708, GPS, and other data can be lower than desired for autonomous parking (e.g., within half a meter or some other margin of error). Accordingly, it can be desirable for vehicle304to move such that the region of interest702is within the field of view712of a selected camera714, for example. In some examples, the selected camera714can be a rear camera to assist in a rear-in parking operation. In some examples, the selected camera can be a front camera to assist in a front-in parking operation. Other selected cameras are possible. Capturing the region of interest702with the selected camera712can allow the vehicle304to determine its position relative to the region of interest with improved accuracy (e.g., within ten centimeters or some other margin of error).

FIG. 7Billustrates the vehicle304capturing part of the region of interest702with its selected camera714according to examples of the disclosure. As shown inFIG. 7B, vehicle304has moved so that part of the region of interest702is within the field of view712of the selected camera714. Although only part of the region of interest702can be included in the field of view712, the vehicle304can have an estimate of the entire region of interest based on previously-obtained data, for example. Further, in some examples, the vehicle can estimate the position of its rear axle706relative to the final parking position704based on the image captured by selected camera714and the estimate of the entire region of interest702. As the vehicle304continues to move, it can obtain a more precise estimate of the region of interest702based on one or more further images captured by camera714.

FIG. 7Cillustrates an exemplary region of interest image722that can correspond to a region of interest image obtained by vehicle304in the position illustrated inFIG. 7B. In some examples, the region of interest image722can be composed of a camera image724captured by selected camera714and an estimated image726determined from GPS sensor data, range sensor data, map data, and/or other sources. The camera image724can include horizontal line images728depicting portions of the horizontal lines of selected parking space710. The horizontal line images728can be identified in the camera image724according to the methods described below with reference toFIGS. 8A-8B, which can be the same or similar to the methods described above with respect toFIGS. 3A-E. The estimated image726can include estimated horizontal line images728, estimated vertical line image732, and an estimate of the final parking position734, for example. In some examples, one or more of the estimated horizontal line images728, estimated vertical line image732, and the estimate of the final parking position734can be based on one or more of the camera image724, GPS sensor data, range sensor data, map data, and/or other sources. As the vehicle moves, the region of interest image722can become more precise as the camera image724can become larger, thereby occupying a larger portion of the region of interest image and providing more data with which to generate the estimated image726.

FIG. 7Dillustrates an exemplary method750of calculating a region of interest702containing a selected parking space710according to examples of the disclosure. Method750can correspond to the examples described with reference toFIGS. 7A-7C. At752, vehicle304can estimate a region of interest702(e.g., as described with reference toFIG. 7A). At754, vehicle304can estimate its position relative to a desired final parking position within the region of interest702(e.g., as described with reference toFIG. 7A). At756, the vehicle304can move such that part of the region of interest702is captured by a selected camera714of the vehicle (e.g., as described with reference toFIG. 7B). At758, the vehicle304can update the region of interest image722(e.g., as described with reference toFIG. 7C).

As vehicle304continues to update its region of interest image722, it can refine its determined position relative to the region of interest702with increased precision. Specifically, gathering one or more camera images724including the region of interest702can be used to better determine the position of the vehicle relative to the region of interest702. However, the vehicle304may need to identify one or more parking lines of the selected parking space710within the region of interest image722to estimate its position, including distance and angular offset, relative to the region of interest702with enough specificity to autonomously park. Therefore, as will be described below, the vehicle304can identify the parking lines within the region of interest image722generated inFIGS. 7A-7C.

FIGS. 8A-8Billustrate exemplary details for detecting the lines828and834of the selected parking space810within a selected field of view812according to examples of the disclosure. In some examples, the selected field of view812can correspond to field of view712of selected camera714described with reference toFIGS. 7A-7D. As described above, a portion of horizontal lines828of selected parking space810can be captured in the selected field of view812, for example. In some examples, vehicle304can generate estimated horizontal lines830and estimated vertical lines832based on a region of interest image (e.g., region of interest image722). Additionally, the vehicle can estimate a final parking position804based on the region of interest image722, for example.

In some examples, the vehicle can detect horizontal parking lines828within selected field of view812by performing operations similar to method350described above with reference toFIGS. 3A-3E. However, the vehicle304can apply one or more constraints to method350based on estimated horizontal parking lines830to improve the efficiency and accuracy of method350. For example, one or more steps of method350may only be performed on pixels within a threshold distance of estimated horizontal parking lines830within the region of interest image722. Vehicle304may only determine pixel gradients in step352for pixels within a threshold distance of estimated horizontal parking lines830. Vehicle304may only create a Hough transform table in step354for the pixels within a threshold distance of estimated horizontal parking lines830. Vehicle304may apply heavier weights to lines within a threshold distance of estimated parking lines830as it performs Hough voting in step356. Vehicle304may restrict the subset of lines determined by Hough voting in step358to lines within a threshold distance of estimated parking lines830. Other constraints to method350are possible to leverage the estimated parking lines830to improve accuracy in localizing the parking lines828and/or increase the speed of localizing the parking lines828, for example. Once vehicle304applies one or more constraints to method350, it can identify the parking lines828. In some examples, identifying the parking lines828can include identifying the parking line ends in a method similar to method450described with reference toFIGS. 4A-4F.

FIG. 8Billustrates an exemplary method850of detecting parking lines828in a selected field of view812according to examples of the disclosure. Method850can correspond to the examples described with reference toFIG. 8A. At852, the vehicle304can capture part of a region of interest802in a selected field of view812. At854, vehicle304can apply constraints to the captured image based on a known or estimated region of interest. At step856, vehicle304can identify one or more parking lines828using one or more of methods350and450with the constraints applied. Although the example described with reference toFIG. 8Aillustrates locating the horizontal parking lines828, in some examples, vehicle304can additionally or alternatively capture an image of the vertical parking line834and detect the vertical parking line within the region of interest802.

As the vehicle304detects one or more parking lines828and/or834in the region of interest802, it can refine the region of interest image722with increased precision. Next, the vehicle304can determine its relative position to a final parking position804by calculating one or more errors in the position of the vehicle's rear axle (e.g., rear axle706) relative to the final parking position804.

FIGS. 9A-9Eillustrate exemplary details for calculating one or more errors in the position of vehicle304according to examples of the disclosure.FIG. 9Aillustrates an exemplary angular displacement of vehicle304relative to horizontal parking lines (e.g., right line928and left line929) according to examples of the disclosure. Right line928and left line929can be captured within selected field of view912and identified according to methods750and850described above. Vehicle304can determine one or more of its right angular displacement α from the right line928and its left angular displacement β from the left line929as part of determining its relative location to selected parking spot910. In some examples, a vehicle coordinate system (x, y) can be defined with its origin at the vehicle rear axle906. Based on one or more captured images (e.g., captured by the selected camera714), the vehicle304can determine a right normal938of the right line928and a left normal939of the left line929, for example. Next, vehicle304can determine one or more of the right angular displacement α as the angle between the right normal938and the y-axis and the left angular displacement β as the angle between the left normal939and the y-axis. In some examples, the right line928and the left line929can be substantially parallel and α and β can be 180 degrees different from one another. In other examples, however, right line928and left line929may not be parallel and the difference between α and β can be a different number of degrees. Once the vehicle304determines its angular displacement from the horizontal lines928and929, it can convert the region of interest image to the vehicle coordinate system for further processing.

FIG. 9Billustrates an exemplary vehicle304converting a region of interest image922to a vehicle coordinate system according to examples of the disclosure. In some examples, the region of interest image922can have its own coordinate system (v, h) along its vertical and horizontal axes (e.g., aligned with one or more of horizontal lines928-929and vertical line90). As vehicle304updates the region of interest image922and estimates its position relative to a final parking position904, it can be advantageous to convert the pixels of the region of interest image922from the region of interest coordinate system (v, h) to the vehicle coordinate system (x, y). For example, point p can have a location (v1, h1) in the region of interest coordinate system and a location (x1, y1) in the vehicle coordinate system. The vehicle coordinate system can have a rotational difference from the region of interest coordinate system defined by α and/or β and a translational difference from the region of interest coordinate system defined by a distance between the final parking position904and the vehicle rear axle906. In some examples, a top image916of the region of interest captured by one or more cameras (e.g., selected camera714or one or more other cameras of camera(s)106) of vehicle304can be used to convert the region of interest coordinate system (v, h) to the vehicle coordinate system (x, y). For example, the angles α and β can be calculated from the top image916as described with reference toFIG. 9A. Additionally, the size of the region of interest can be determined in meters from the top image916, for example. In some examples, vehicle304can assume the height of the selected camera is known and that the ground is relatively flat. Based on these assumptions, for example, the vehicle304can convert the pixel of top image916to dimensions in meters of the region of interest. In some examples, the top image916can have coordinate system (a, b) which can be parallel to vehicle coordinate system (x, y). Once the angular and translational displacement between the vehicle coordinate system (x, y) and the region of interest coordinate system (v, h) are identified, the vehicle can determine its positional errors relative to the final parking position904.

FIG. 9Cillustrates exemplary lateral (ΔL) and heading (θ) errors according to examples of the disclosure. In some examples, vehicle304can determine its longitudinal, lateral, and heading errors relative to the final parking position904. The vehicle304can determine the distance Δr between the vehicle rear axle906and the right parking line928along the y-axis and the distance Δl between the vehicle rear axle906and the left parking line929along the y-axis. The average of Δr and Δl can be the distance between the vehicle rear axle906and the final parking position904along the y-axis or the lateral error ΔL. The heading error θ can be the angle between the x-axis and the final orientation of the x-axis, xf. In some examples, one or more of α and β can be used to calculate θ. As shown inFIG. 9C, in some examples, the vertical parking line930may not be included in the selected field of view912. Until the vertical parking line930is visible in the selected field of view912, the vehicle304may be unable to calculate its longitudinal error, (e.g., the distance between the vehicle rear axle906and the final parking position904along the x-axis). As the vehicle304moves into the selected parking space910, the image captured in the selected field of view912can change and eventually include the vertical parking line930.

FIG. 9Dillustrates exemplary lateral (ΔL), longitudinal (ΔH) and heading (θ) errors according to examples of the disclosure. In some examples, vehicle304can determine its longitudinal, lateral, and heading errors relative to the final parking position904. The vehicle304can determine ΔL from Δr and Δl and can determine θ from α and/or β as described above with reference toFIG. 9C. As shown inFIG. 9D, vertical parking line930can be within selected field of view912, allowing the vehicle304to determine its longitudinal error ΔH. As the vehicle continues to move into the selected parking space, its controller (e.g., controller120) can cause the vehicle to move such that the lateral (ΔL), longitudinal (ΔH) and heading (θ) errors continue to decrease and eventually equal zero, indicating that the rear axle906is in the final parking position904.

FIG. 9Eillustrates an exemplary method950of calculating one or more errors in the position of vehicle304according to examples of the disclosure. Method950can correspond to the examples described with reference toFIGS. 9A-9D. At952, the vehicle304can calculate the angular displacement of the horizontal parking lines (e.g., as described with reference toFIG. 9A). At954, the vehicle304can convert the region of interest image to the vehicle coordinate system (e.g., as described with reference toFIG. 9B). At956, the vehicle304can calculate one or more of its heading, lateral, and/or longitudinal errors relative to a final parking position904(e.g., as described with reference toFIGS. 9C-9D). When each of the lateral, longitudinal, and heading errors are below predetermined thresholds (e.g., when the errors are substantially zero or some other small value), the vehicle can autonomously enter a parked state. The parked state can comprise applying a parking brake, turning off the motor131or engine132of the vehicle, and/or otherwise powering down the vehicle.

It should be understood that one or more of methods350,450,550,650,750,850, and950can be performed simultaneously, repetitively, and/or sequentially in any order as the vehicle304performs an autonomous parking operation. Further, one or more additional sensors of the vehicle can be used in conjunction with the methods described herein to increase the precision of vehicle localization and/or to avoid one or more hazards (e.g., pedestrians, vehicles, animals) in the parking lot.

Thus, the examples of the disclosure provide various ways that a vehicle can perform autonomous parking in parking spaces delineated by parking lines using a camera and/or a GPS receiver.

Therefore, according to the above, some examples of the disclosure are related to a vehicle comprising: a camera; a range sensor; a GPS receiver; one or more actuator systems; and one or more processors operatively coupled to the camera, the range sensor, the GPS receiver, and the one or more actuator systems, the one or more processors configured to perform a method comprising: detecting two or more parking lines in one or more images captured by the camera; localizing the vehicle with respect to the two or more parking lines based on: location data of the vehicle determined from the GPS receiver, and a location determination for the vehicle based on detected ends of the two or more parking lines; determining an occupancy state of one or more parking spaces formed by the two or more parking lines using the range sensor; in accordance with a determination that the occupancy state of a respective parking space of the one or more parking spaces is empty, selecting the respective parking space; identifying a region of interest including the selected parking space; detecting one or more selected parking lines of the selected parking space within one or more captured images including all or part of the region of interest; calculating one or more errors of a current location of the vehicle based on the one or more selected parking lines; and moving the vehicle, using the one or more actuator systems, in a direction to reduce the one or more errors. Additionally or alternatively, in some examples, detecting the two or more parking lines comprises: determining pixel gradients in the one or more images; and detecting the two or more parking lines based on the determined pixel gradients. Additionally or alternatively, in some examples, detecting the ends of the two or more parking lines comprises: matching top and bottom edge pixels for each lane line; fitting linear models to the top and bottom edge pixels; and identifying an end of each lane line based on a pixel gradient template. Additionally or alternatively, in some examples, determining the location for the vehicle based on the detected ends of the two or more parking lines comprises: initializing a plurality of candidate vehicle positions; and assigning probabilities to the plurality of candidate vehicle positions based on the detected ends of the two or more parking lines. Additionally or alternatively, in some examples, determining the location for the vehicle based on the location data for the vehicle from the GPS receiver comprises: initializing a plurality of candidate vehicle positions; and assigning probabilities to the plurality of candidate vehicle positions based on a GPS location of the vehicle. Additionally or alternatively, in some examples, determining the occupancy state of the one or more parking spaces formed by the two or more parking lines using the range sensor comprises: initializing occupancy grid cells of an occupancy grid; updating the occupancy grid cells of the occupancy grid based on detections made by the range sensor; and determining the occupancy state of the one or more parking spaces based on the occupancy grid cells of the occupancy grid. Additionally or alternatively, in some examples, identifying the region of interest comprises: estimating a location of the region of interest based on one or more of the captured images that were captured before selecting the selected parking space; and after selecting the selecting parking space, capturing one or more of the captured images including all or part of the region of interest. Additionally or alternatively, in some examples, the one or more errors comprise one or more of: a lateral error comprising a first distance between a rear axle of the vehicle and a first parking line of the selected parking space and a second distance between the rear axle and a horizontal parking line of the selected parking space, the first and second lines of the selected parking space being oriented along a first axis; a longitudinal error comprising a third distance between the rear axle of the vehicle and a third parking line of the selected parking space, the third parking line oriented along a second axis orthogonal to the first axis; and a heading error comprising an angle between the vehicle and one of the first axis or second axis. Additionally or alternatively, in some examples, detecting the one or more parking lines of the selected parking space comprises applying one or more constraints based on an estimated region of interest to one or more images captured after selecting the selected parking space. Additionally or alternatively, in some examples, the method performed by the one or more processors further comprises: when the one or more errors are below a predetermined threshold, transition the vehicle to a parked state using the one or more actuator systems.

Some examples of the disclosure are directed to a non-transitory computer-readable storage medium storing instructions that, when executed by one or more processors included in a vehicle, causes the one or more processors to perform a method, the method comprising: detecting two or more parking lines in one or more images captured by a camera; localizing a vehicle with respect to the two or more parking lines based on: location data for the vehicle from a GPS receiver, and a location determination for the vehicle based on detected ends of the two or more parking lines; determining an occupancy state of one or more parking spaces formed by the two or more parking lines using a range sensor; and in accordance with a determination that the occupancy state of a respective parking space of the one or more parking spaces is empty, selecting the respective parking space; identifying a region of interest including the selected parking space; detecting one or more selected parking lines of the selected parking space within one or more captured images including all or part of the region of interest; calculating one or more errors of a current location of the vehicle based on the one or more selected parking lines; and moving the vehicle, using one or more actuator systems of the vehicle, in a direction to reduce the one or more errors. Additionally or alternatively, in some examples, detecting the two or more parking lines comprises: determining pixel gradients in the one or more images; and detecting the two or more parking lines based on the determined pixel gradients. Additionally or alternatively, in some examples, detecting the ends of the two or more parking lines comprises: matching top and bottom edge pixels for each lane line; fitting linear models to the top and bottom edge pixels; and identifying an end of each lane line based on a pixel gradient template. Additionally or alternatively, in some examples, determining the location for the vehicle based on the detected ends of the two or more parking lines comprises: initializing a plurality of candidate vehicle positions; and assigning probabilities to the plurality of candidate vehicle positions based on the detected ends of the two or more parking lines. Additionally or alternatively, in some examples, determining the location for the vehicle based on the location data for the vehicle from the GPS receiver comprises: initializing a plurality of candidate vehicle positions; and assigning probabilities to the plurality of candidate vehicle positions based on a GPS location of the vehicle. Additionally or alternatively, in some examples, determining the occupancy state of the one or more parking spaces formed by the two or more parking lines using the range sensor comprises: initializing occupancy grid cells of an occupancy grid; updating the occupancy grid cells of the occupancy grid based on detections made by the range sensor; and determining the occupancy state of the one or more parking spaces based on the occupancy grid cells of the occupancy grid. Additionally or alternatively, in some examples, identifying the region of interest comprises: estimating a location of the region of interest based on one or more of the captured images that were captured before selecting the selected parking space; and after selecting the selecting parking space, capturing one or more of the captured images including all or part of the region of interest. Additionally or alternatively, in some examples, the one or more errors comprise one or more of: a lateral error comprising a first distance between a rear axle of the vehicle and a first parking line of the selected parking space and a second distance between the rear axle and a horizontal parking line of the selected parking space, the first and second lines of the selected parking space being oriented along a first axis; a longitudinal error comprising a third distance between the rear axle of the vehicle and a third parking line of the selected parking space, the third parking line oriented along a second axis orthogonal to the first axis; and a heading error comprising an angle between the vehicle and one of the first axis or second axis. Additionally or alternatively, in some examples, detecting the one or more parking lines of the selected parking space comprises applying one or more constraints based on an estimated region of interest to one or more images captured after selecting the selected parking space. Additionally or alternatively, in some examples, the method performed by the one or more processors further comprises: when the one or more errors are below a predetermined threshold, transition the vehicle to a parked state using the one or more actuator systems.

Some examples of the disclosure are directed to a vehicle comprising: a camera; a range sensor; a GPS receiver; and one or more processors coupled to the camera, the range sensor and the GPS receiver, the one or more processors configured to perform a method comprising: detecting two or more parking lines in one or more images captured by the camera; localizing the vehicle with respect to the two or more parking lines based on: location data for the vehicle from the GPS receiver, and a location determination for the vehicle based on detected ends of the two or more parking lines; determining an occupancy state of one or more parking spaces formed by the two or more parking lines using the range sensor; and in accordance with a determination that the occupancy state of a respective parking space of the one or more parking spaces is empty, autonomously parking the vehicle in the respective parking space. Additionally or alternatively to one or more of the examples disclosed above, in some examples, detecting the two or more parking lines comprises: determining pixel gradients in the one or more images; and detecting the two or more parking lines based on the determined pixel gradients. Additionally or alternatively to one or more of the examples disclosed above, in some examples, detecting the two or more parking lines further comprises: performing Hough voting based on the determined pixel gradients; and detecting the two or more parking lines based on the Hough voting. Additionally or alternatively to one or more of the examples disclosed above, in some examples, detecting the ends of the two or more parking lines comprises: matching top and bottom edge pixels for each lane line; fitting linear models to the top and bottom edge pixels; and identifying an end of each lane line based on a pixel gradient template. Additionally or alternatively to one or more of the examples disclosed above, in some examples, determining the location for the vehicle based on the detected ends of the two or more parking lines comprises: initializing a plurality of candidate vehicle positions; and assigning probabilities to the plurality of candidate vehicle positions based on the detected ends of the two or more parking lines. Additionally or alternatively to one or more of the examples disclosed above, in some examples, determining the location for the vehicle based on the location data for the vehicle from the GPS receiver comprises: initializing a plurality of candidate vehicle positions; and assigning probabilities to the plurality of candidate vehicle positions based on a GPS location of the vehicle. Additionally or alternatively to one or more of the examples disclosed above, in some examples, localizing the vehicle with respect to the two or more parking lines comprises: initializing a plurality of candidate vehicle positions; assigning probabilities to the plurality of candidate vehicle positions based on the detected ends of the two or more parking lines; and assigning probabilities to the plurality of candidate vehicle positions based on a GPS location of the vehicle. Additionally or alternatively to one or more of the examples disclosed above, in some examples, localizing the vehicle with respect to the two or more parking lines comprises: propagating the plurality of candidate vehicle positions based on movement of the vehicle; and determining an updated location of the vehicle based on the propagated plurality of candidate vehicle positions. Additionally or alternatively to one or more of the examples disclosed above, in some examples, determining the occupancy state of the one or more parking spaces formed by the two or more parking lines using the range sensor comprises: initializing occupancy grid cells of an occupancy grid; updating the occupancy grid cells of the occupancy grid based on detections made by the range sensor; and determining the occupancy state of the one or more parking spaces based on the occupancy grid cells of the occupancy grid. Additionally or alternatively to one or more of the examples disclosed above, in some examples, determining the occupancy state of the one or more parking spaces formed by the two or more parking lines using the range sensor further comprises updating the occupancy grid cells of the occupancy grid at and end of each time step of a plurality of time steps based on a time constant.

Some examples of the disclosure are directed to a method comprising: detecting two or more parking lines in one or more images captured by a camera; localizing a vehicle with respect to the two or more parking lines based on: location data for the vehicle from a GPS receiver, and a location determination for the vehicle based on detected ends of the two or more parking lines; determining an occupancy state of one or more parking spaces formed by the two or more parking lines using a range sensor; and in accordance with a determination that the occupancy state of a respective parking space of the one or more parking spaces is empty, autonomously parking the vehicle in the respective parking space.

Some examples of the disclosure are directed to a vehicle comprising: a camera; a range sensor; a GPS receiver; and one or more processors coupled to the camera, the range sensor and the GPS receiver, the one or more processors configured to perform a method comprising: generating a plurality of candidate location estimates for the vehicle in a parking area; assigning a respective first probability to each respective candidate location estimate of the plurality of candidate location estimates based on location data for the vehicle from the GPS receiver; assigning a respective second probability to each respective candidate location estimate of the plurality of candidate location estimates based on a location determination for the vehicle that is based on detected ends of two or more parking lines in the parking area in an image captured by the camera; and determining a location of the vehicle in the parking area to be a first respective candidate location estimate of the plurality of candidate location estimates based on a total probability, comprising the respective first probability and the respective second probability, assigned to the first respective candidate location estimate. Additionally or alternatively to one or more of the examples disclosed above, in some examples, assigning the respective first probability to each respective candidate location estimate of the plurality of candidate location estimates based on the location data for the vehicle from the GPS receiver comprises: assigning a higher probability to candidate location estimates for the vehicle that are within a region including a GPS location of the vehicle; and assigning a lower probability to candidate location estimates for the vehicle that are outside of the region including the GPS location of the vehicle. Additionally or alternatively to one or more of the examples disclosed above, in some examples, the region including the GPS location of the vehicle is a unique region in the parking area. Additionally or alternatively to one or more of the examples disclosed above, in some examples, assigning the respective second probability to each respective candidate location estimate of the plurality of candidate location estimates based on the location determination for the vehicle that is based on the detected ends of the two or more parking lines in the parking area in the image captured by the camera comprises: assigning a higher probability to candidate location estimates for the vehicle that are within a plurality of regions positioned in the parking area based on the detected ends of the two or more parking lines in the parking area; and assigning a lower probability to candidate location estimates for the vehicle that are outside of the plurality of regions positioned in the parking area based on the detected ends of the two or more parking lines in the parking area. Additionally or alternatively to one or more of the examples disclosed above, in some examples, the method further comprises: resampling the candidate location estimates for the vehicle after assigning the respective first probabilities and the respective second probabilities, and before determining the location of the vehicle based on the total probability. Additionally or alternatively to one or more of the examples disclosed above, in some examples, the first respective candidate location estimate is the location of the vehicle at a current time step, and the method further comprises: at a next time step, after the current time step, propagating the plurality of candidate location estimates for the vehicle based on a movement of the vehicle; and determining the location of the vehicle at the next time step based on the propagated plurality of candidate location estimates. Additionally or alternatively to one or more of the examples disclosed above, in some examples, the method further comprises: at the next time step, initializing a plurality of new candidate location estimates for the vehicle based on the location of the vehicle at the current time step; and determining the location of the vehicle at the next time step based on the propagated plurality of candidate location estimates and the plurality of new candidate location estimates for the vehicle.

Some examples of the disclosure are directed to a method comprising: generating a plurality of candidate location estimates for a vehicle in a parking area; assigning a respective first probability to each respective candidate location estimate of the plurality of candidate location estimates based on location data for the vehicle from a GPS receiver; assigning a respective second probability to each respective candidate location estimate of the plurality of candidate location estimates based on a location determination for the vehicle that is based on detected ends of two or more parking lines in the parking area in an image captured by a camera; and determining a location of the vehicle in the parking area to be a first respective candidate location estimate of the plurality of candidate location estimates based on a total probability, comprising the respective first probability and the respective second probability, assigned to the first respective candidate location estimate.