Patent Description:
The demand for parking spaces is continuously rising along with increasing car ownership. Street parking can be notoriously difficult to locate, particularly in inner city areas, unfamiliar neighborhoods and/or during times when demand is high. Currently, many services exist that provide users with estimates of parking occupancy, based on location, time, historical data and other parameters. To provide users with parking occupancy, such services need to collect data relating to street parking spots in a given region and preferably their typical occupancy. This is currently mainly done by regular manual surveys, street parking sensors or other similar means. Protototypes of using video from CCTV or dashboard cameras have also recently been proposed.

Satellite images have been used for various mapping purposes for some time. However, the resolution of satellite images that are publically and/or commercially available has generally not been high enough to extract detailed information, such as information relating to potential parking spaces and/or vehicles occupying them. Currently, new satellites such as WorldView <NUM>, <NUM>, <NUM> and <NUM> allow for a much more detailed resolution of about <NUM>-<NUM> per pixel, which allows for easier vehicle detection.

Recently, better methods of processing satellite images are being developed. For example, <CIT> discloses methods and apparatus to estimate commercial characteristics based on aerial images.

Due to the increased car ownership and use, as well as other factors, finding parking in cities is becoming more and more challenging. Providing only parking space occupancy in a given area (in percentage) may not be sufficient for a driver, as they also need information about how many individual spots are in a desired area. For example, it is easier to park a car on a street with <NUM> individual spots and <NUM>% occupancy (that is, <NUM> free spots) than on a street with a total of <NUM> spots and <NUM>% occupancy rate.

However, number of unique on-street parking spots in a city is usually not available, or the estimate is highly inaccurate. For example, in Seattle, a local government used fixed length of a parking spot to count the number of spots regardless of whether vehicles park there perpendicularly or in parallel. In addition, further information about how vehicles park on a street (e.g., in parallel or perpendicularly) is also often not digitally available.

In light of the above, it is the object of the present invention to disclose a method of satellite and/or aerial image processing. It is also the object of the present invention to disclose methods of extracting specific information from satellite or aerial images, particularly information related to parking spaces and vehicles occupying them. It is also the object of the present invention to provide a map of parking spaces in a certain region or area based on the information extracted from satellite or aerial images. It is also the object of the invention to build and maintain a parking occupancy map based only on satellite or aerial images as an input. Furthermore, it is the object of the invention to provide a tool for comparing existing parking maps and for determining their accuracy based on the information extracted from satellite or aerial images.

Even further, the present disclosure proposes a new method of processing of satellite or aerial images that comprises:.

In a first embodiment, a method for identifying and evaluating on-street parking spots of an area based on at least one of satellite and aerial images of said area is disclosed. The method comprises retrieving and processing a plurality of at least one of satellite and aerial images by at least quality benchmarking and georeferencing the images. The method also comprises, for each image, detecting objects of interest comprising at least detected vehicles, computing street sections based on map data corresponding to the images, and assigning the detected objects to at least street sections. The method further comprises, for each street section, identifying on-street vehicle lanes based on the detected objects of interest. The method also comprises combining street sections based on the on-street vehicle lanes from the plurality of at least one of satellite and aerial images. The method further comprises, in the combined sections, identifying parking lanes and deriving individual parking spots comprised thereon.

The present method can be useful for users wishing to find a street parking space. It can also be useful for map providers, as an add-on showing expecting parking occupancy in an area. In one concrete example, the method can be used as part of an application for a user's personal mobile device (such as a smartphone) which assists the user with parking spot search. In another example, the method can be used as part of a service provided (for example, as an API) for third parties interested in monitoring parking occupancy in a city and the specific location of on-street parking spaces. For example, GPS manufactures, mapping and directions companies, car companies might all be interested in obtaining this data in order to provide their customers information related to parking spaces in a certain area.

As described in the present disclosure, the method can use satellite and/or aerial images as inputs. Satellite images refer to images taken by various public and/or commercial satellites in orbit. Aerial images can refer to images taken from planes, helicopters, air balloons and/or images taken by drones. While the present disclosure mostly exemplifies the use of satellite images for the parking spot identification, aerial images with a corresponding resolution can be used just as well.

Retrieving the images can refer to finding them in a database and/or finding them on a server and/or obtaining them from a publically accessible storage, a partner and/or a commercial provider. Processing the images can refer at least to verifying that the quality of the images is sufficient and georeferencing them. The quality itself can refer to the resolution, the level of obstruction from, for example, clouds and/or shadows and any blurring. Georeferencing can refer to determining the location or the area of the image. This step is useful for combining images with map data: since a precise location is needed for this.

The objects of interest generally comprise vehicles in the present disclosure, but can also refer to buildings, landmarks and/or other features easily recognizable in the images. These can be useful for additional georeferencing for example.

Map data can refer to publically and/or commercially available maps of areas of interest. For example, Open Street Map data can be used. Street sections refer to straight line segments that streets can be subdivided into. This is further explained and exemplified below.

On-street vehicle lanes refer to lanes present on a given traffic road. Parking lanes are included in the on-street vehicle lanes.

Parking spots can be referred here as on-street areas where vehicles are generally allowed to park. These can have a corresponding size and orientation assigned to them based on further analysis.

In some embodiments, the method can further comprise consolidating and interpreting data related to the identified individual parking spots. That is, as mentioned above, the detected parking spots can be further evaluated. Parking rules and regulations applying to the parking spots can also be determined based on the parking habits as seen in different images for example. Sizes can also be assigned to parking spots. For example, some street parking spots may be suitable only for cars below a certain maximum width or length based on street geometry. The orientation of the parking spot with respect to street orientation can also be computed. Further processing and determining of characteristics associated with the parking spots is also possible.

In some embodiments, the method can further comprise computing parking space occupancy of the identified parking lanes. That is, a parking space occupancy in terms of percentage and/or another metric can be computed and outputted to a prospective interested user. The occupancy can also be presented as a function of time, for example, by using historic occupancy. Various parameters can influence parking space occupancy. If data that is not real-time is used, forecasting of the parking occupancy can be performed based on time of day, any holidays, the precise location, events, weather and further factors.

In some embodiments, the method can further comprise computing the availability of parking spaces in a given neighborhood at a given time. As mentioned above, forecasting based on historic data can be used for this. Additionally or alternatively, real-time data (for example, images taken by drones) can be used to continuously update this information. Parking space availability can be very useful to the end user, who might, for example, decide to take a different mode of transport if there are few parking spaces available.

In some embodiments, the method can further comprise using a plurality of at least one of satellite and aerial images of an area taken over a certain period of time to identify at least time-dependent parking space availability. That is, the availability of on-street parking spots can depend, among other things, on the time of day (and/or day of the week). This dependency can be determined by using images taken at different times. Advantageously, an output with an estimated parking occupancy (that is, the amount of free and/or occupied spaces) can be output as a function of time.

In some embodiments, the method can further comprise identifying parking rules based on the interpreted identified individual parking spots. As mentioned above, this can be done, for example, by observing the parking behavior of vehicles in the parking spots (for example, some spots might only be available between certain hours, which can be deduced by looking at a plurality of images taken at different times).

In some embodiments, the method can further comprise providing the interpreted data to a user interested in finding an on-street parking spot. The user can be particularly interested in an estimate of parking occupancy at a certain time, or just on historical parking occupancy of a particular spot (and/or area).

In some embodiments, identifying on-street vehicle lanes can further comprise eliminating street sections inaccessible to vehicles. That is, the method can comprise detecting street sections inaccessible to vehicles (such as, for example, sidewalks and/or private roads). These street segments can then be discarded from the parking space computation.

Identifying on-street vehicle lanes comprises computing a closest street section for each detected vehicle and recursively identifying on-street vehicle lanes based on a plurality of vehicles present in each street section. The closest street section to each vehicle can be obtained, for example, by projecting the center of a bounding box or a bounding ellipse of a vehicle (that is, a geometrical object determining the bounds of the vehicle and generally obtained at the stage of detecting objects of interest in the images) to each street segment and selecting the one with the shortest resulting distance as the closest one. Note, that since street sections are determined based on map data, and vehicles are found in images, the two types of data need to be combined first. This can be done by superimposing the map data onto the images based on their georeferencing.

Recursive identification of on-street vehicles is further detailed below. Generally a plurality of hypotheses on the configuration of lanes can be generated and tested against all of the vehicles present in all of the images. In the end, only statistically significant lane hypotheses should remain.

In other words, the traffic or vehicle lanes (denoted here as on-street vehicle lanes) can be detected based on the cars detected in the images. Prior to this step, cars that are not in the street are preferably removed from consideration. This results in a robust and reliable way of locating traffic lanes, contributing to the general effectiveness of the present method.

The recursively identified on-street vehicle lanes is quality controlled by at least comparing their slope with that of the respective street section. That is, the street sections detected in map data can serve as a sort of sanity check or guidance when the lanes are identified based on the vehicles from images. In other words, street segments can serve as a benchmark for the identified on-street vehicle lanes. Compliance with quality control can be determined, for example, based on a preset threshold of allowed deviation of the traffic lane slope from the street segment slope.

In some such embodiments, the recursively identified on-street vehicle lanes not compliant with the quality control can be further compared to similar lanes compliant with the quality control and adjusted to comply as well by recursively adapting their slope. Recursive slope adaptation can refer to performing an identification of the non-compliant on-street vehicle lanes again, and including similar lanes that are compliant as a reference. The similar lanes can be identified, for example, based on a similar bearing.

In some embodiments, combining street sections can comprise inputting a plurality of intersecting images, removing vehicles likely located off-street, and consolidating on-street vehicle lanes between the street sections. That is, images can be combined into intersecting visualization of a certain area. The on-street vehicle lanes can then also be combined based on the known relationships between the street sections (which can be known from the map data based on which the street sections are computed).

In some embodiments, combining street sections can further comprise computing a true number of lanes for each street. The true number of lanes can be computed by comparing and analyzing a plurality of images with possibly different lanes occupied in some of them. The large number of images makes it very likely that all of the lanes will be occupied in at least one of the images, which can then be confirmed as the true number of lanes.

In some embodiments, the method can further comprise assigning an identification parameter to each on-street vehicle lane. For example, the detected lanes can be simply numbered from left to right. The parking lanes are then generally the first and the last lane. However, some streets have only one or zero parking lanes.

In some such embodiments, identifying parking lanes can comprise filtering all vehicles located on inner lanes as identified by the identification parameter. The inner lanes are all lanes except the first and the last one as per the identification. In other words, the outermost lanes are examined.

In some embodiments, identifying parking lanes can further comprise computing the distance between the vehicles located in each on-street vehicle lane. This is particularly advantageous, as it can allow determining whether a particular road has parking lanes at all. Vehicles in parking lanes are generally located much closer to each other than vehicles in traffic lanes. Therefore, this allows for another robust way of identifying parking lanes.

In some embodiments, identifying individual parking spots can comprise computing a mean and minimal distance between neighboring vehicles. Parked cars usually try to minimize distance between neighboring vehicles, but this often ends up non-representative, since drivers might have different preconceptions about the desired distance between vehicles and/or due to the random parking spot filling, some vehicles might be parked closer and some further. Using both the mean and minimal distance to estimate true parking spots can include objectivity into the determination process.

In some embodiments, identifying individual parking spots can further comprise determining orientation of parked vehicles with respect to their respective parking lane. That is, some roads have parallel parking spaces, while others have perpendicular. Sometimes both are present on different stretches of the road and/or on different sides of the road. Based on the shape of the detected vehicle, its orientation can be determined.

In a second embodiment, a method for identifying on-street parking spots of an area based on at least one of satellite and aerial images of said area is disclosed. The method comprises retrieving and processing a plurality of at least one of satellite and aerial images by at least quality benchmarking and georeferencing the images. The method further comprises detecting vehicles and street sections in the georeferenced images. The method also comprises identifying on-street vehicle lanes based on the detected street sections and vehicles. The method further comprises identifying parking lanes and deriving individual parking spots on them. The method also comprises consolidating data from the plurality of at least one of satellite and aerial images of the area to compute an average parking occupancy in this area.

Advantageously, the present method outputs a parking occupancy of an area. The consolidated data can include images taken at different times, allowing to present a historical parking occupancy survey, as well as potentially a forecasted parking occupancy. As compared to the first embodiment, the present method is more specifically geared towards an end user. While the first embodiment advantageously allows to determine the existence of parking spaces in a given area, the present embodiment yields the parking occupancy. Each embodiments is useful on its own, and both can be combined. The features discussed above can also be applicable with respect to the present embodiment.

In some embodiments, the method can further comprise deriving rules related to parking from the consolidated data. That is, images taken at different times of day, day of the week, month, on a holiday or not can be processed, and parking rules can be obtained from them. For example, if certain parking spots allow for parking only during certain hours, this can be deduced. Such parking rules can then also be outputted together with the parking occupancy. For end users, this can be very useful, since different rules might indicate whether parking is allowed in a certain spot at a certain time or not.

In some embodiments, identifying on-street vehicle lanes can comprise recursively assigning vehicles on a given street section to possible on-street vehicle lanes until an optimal solution yielding at least one lane is obtained. That is, the detected vehicles can be added one by one to an algorithm which can compute a general fit for each progressive set of vehicles. The optimal solution can refer to a solution satisfying some minimum requirements such as a minimum probability of a lane being correctly identified.

In some embodiments, the method can further comprise consolidating the detected street sections with the respective identified lanes and identifying the parking lanes as the outermost lanes in the resulting consolidated street sections. The consolidating can be done based on a plurality of satellite images and on map data. That is, map data can be used to obtain street geometry, and this can be combined with a plurality of images in order to input any missing lanes onto the streets.

In some embodiments, the parking spot derivation can comprise at least computing distance between nearest neighbor vehicles on each parking lane, determining types of vehicles and parking orientation and obtaining an average parking spot with a corresponding size based on the above. That is, the individual parking spots can be identified based on the detected space between vehicles, their orientation and size. For example, if it is detected that a few vans or trucks are parked in a certain area, the true number of parking spots might be larger than what it appears to be, since those can take more space than an average vehicle.

In a third embodiment, a computer-implemented system for identifying on-street parking spots based on at least one of satellite and aerial images is disclosed. The system comprises a storage component configured to store a plurality of at least one of satellite and aerial images and map data. The system also comprises a processing component configured for the following operations or uses.

The processing component is configured for retrieving and processing a plurality of at least one of satellite and aerial images from the storage component by at least quality controlling and georeferencing the images. The processing component is also configured for detecting objects of interest comprising at least detected vehicles for each image, computing street sections based on map data corresponding to the images, and assigning each detected object to a street section for each street section, identifying on-street vehicle lanes based on the detected objects of interest. The processing component is also configured for combining street sections based on the on-street vehicle lanes from the plurality of at least one of satellite and aerial images. The processing component is also configured for identifying parking lanes and individual parking spots comprised thereon in the combined sections;
The system further comprises an output component configured to output the individual parking spots determined by the processing component.

The system can be implemented, for example, via a server (either local or distributed, such as a cloud server).

The memory component can comprise a physical memory storage device such as a hard drive. It can also comprise memory located on remote servers or distributed memory.

The output component can comprise an application for a user's personal computing device (such as a smartphone) that assists a user with parking spot finding. Additionally or alternatively, the output component can comprise an interface, such as an API, for third parties (that is, partners, business users or other such entities) to obtain access to known parking spots in a given area and optionally the parking occupation.

The features and steps described in relation to the method embodiments can generally be applied to the system as well, with the processing component being configured to perform the additional tasks.

In a fourth embodiment, a computer program comprising instructions is disclosed. When the program is executed by a computer, it causes the computer to carry out the method described in any of the previous embodiments.

In a fifth embodiment, a non-transient computer-readable medium comprising instructions is disclosed. When executed by a computer, it causes the computer to carry out the method described in any of the previous embodiments.

The present invention is defined by the the claims.

Some aspects of the present invention are discussed in a more detailed and quantitative way below.

Note, that the present disclosure describes detailed ways of extracting parking space information from satellite images. However, the method can be analogously used with aerial images. For example, images taken from planes, balloons or drones can be used as an input in addition to or instead of satellite images.

As a first part of the present method, vehicles are identified in satellite images. The input for this comprises satellite images of a defined area. The output comprises a list of identified vehicles with (at least) the following attributes for each vehicle:.

The output of the vehicle detection in satellite images can be obtained in the form of GeoJSON. Vehicle identification from aerial/satellite image is a well-known problem, and current state of the art is to use recurrent neural networks (also known as Deep Learning techniques). The accuracy of this method depends mainly on the size of training data sets, i.e., number of the annotated images, that is used to train the network. To satisfy this requirements, all available sources of annotated images, e.g., ImageNet, are used. In addition, training sets containing a specific situation (e.g. vehicles in shadows) might be manually created.

Information obtained from the previous module, that is, the georeferenced vehicles with further attributes is input into this module. Further inputs can include a table containing geometries of each streets and additional features available for each street (e.g., street width, number of traffic lanes, vehicles accessibility, parking rules, etc.). Planar projection appropriate for the area can also be an input.

The output can comprise a table containing simple sections with following columns:.

The output can also comprise a table containing identified vehicles with following columns:.

Note, that simple sections are described below.

Street geometry can be defined by at least two spatial points, and, in most cases, it is defined by many more points. For example, see <FIG> illustrating this. If a street geometry is defined using more than two points, it needs to be divided into simple sections such that exactly two points define each simple section (start and end).

The above procedure can be performed for each street.

Each simple section is then equipped with a unique ID and additional useful
features such as:.

Finally, each simple section is converted into appropriate planar coordinates.

For a given vehicle, represented by its center point (x,y), its distance to simple sections from the previous section can be minimized. This can be expressed as<MAT> where S represents a set of all simple sections, and dist is a function that returns a distance (in meters) for a pair of spatial objects.

Note, that the following minimization is preferably performed in planar coordinates.

An exemplary result of this step is shown in <FIG>, which shows an exemplary output of a vehicle map section matching procedure. Vehicles matched to the same section are marked with the same color in the figure.

When a closest section for each vehicle is identified, it should be determined which side of the sections the vehicle is located on. This is performed by using the following procedure.

If α < <NUM>, then the vehicle is located on the left side. If α > <NUM>, then the vehicle is located on the right side.

This is illustrated, for example, in <FIG>, which shows vehicles matched to a section, and connected to their projection onto the section. Vehicles identified to be on the different sided are marked using different colors.

As an input, all of outputs from vehicle map matching are taken. This module outputs a number of different on-street vehicle lanes t. It further outputs a table that contains all vehicles, and an ID number of the lane that each vehicle belongs to.

Denote v<NUM>,. ,vk the vehicles assigned to a section s, and denote <MAT>.

As before, the center of the vehicle vj projected onto the section s is denoted by (x̂J,ŷJ).

If vehicles v<NUM>,. ,vk are located in t lanes, and, without loss of generality, assuming that there exist numbers <MAT> such that vehicles vji, vji+<NUM>,. , vji+<NUM>-<NUM> are on lane i, then <MAT> where δij = <NUM> if vehicle vj is in lane i and <NUM> otherwise, and <MAT>.

There are a number of difficulties to overcome at this point in the procedure.

To illustrate difficulties with estimating parameters a,b<NUM>,. ,bt, assume that one assigns <NUM> vehicles to a plurality of traffic lines. The correct number of lanes is not known, so the parameters a,b<NUM>,. ,bt need to be estimated for each t = <NUM>,. Note, that at least two cars should be in one lane, or the parameters cannot be estimated. That is, for each t, there are <MAT> options for assigning the vehicles to lanes. Therefore, there are <MAT> sets of possible parameters. If the number of vehicles is <NUM>, there are more than a million possible sets of parameters. This problem can be addressed by combining hierarchical clustering with total least squares regression to bypass computational and other issues. For this, an oriented distance is defined for each vehicle as <MAT> where <MAT> and dj is defined above. Then, for vehicles v<NUM>,. ,vk, the lane assignment algorithm can be performed as follows:.

For each vehicle vj, its line number cj ∈ {<NUM>,. , t} is obtained. Also obtained are the t + <NUM> parameters ã,b̃<NUM>,. ,b̃t that define the lines corresponding to on-street vehicle lanes.

Additional filtering and quality control can be performed to ensure that the assignment was done correctly.

For example, recall that vehicles v<NUM>,. ,vk were matched to section s, and vehicle vj belongs to lane number cj, which is defined using two real parameters a,bcj. Now, a line can be constructed passing through the middle point of section s and with a slope a. Such line obviously intersects with section s, but in general is not parallel to it. The angle between these two lines can be denoted γ. If γ is too large, the filtering can be done as follows:.

The adjustment of the cost function can be done as follows:.

After completing the above steps vehicles, assigned to section s are either removed, or their assignment is adjusted.

The result of this module of the algorithm is illustrated, for example, in <FIG>.

As the next step of the algorithm, parking lanes are identified. The input to this module comprises the number of different on-street vehicle lanes, and well as the assignment of each vehicle to a specific lane. Furthermore, simple street sections are also inputted.

The output comprises vehicles that are identified to be parked and the definition of lanes that they are parked in.

Suppose I images are available, each with street sections s<NUM>,. For each section s and each image I, there are vehicles <MAT> assigned to this section. The vehicles are assigned to on-street vehicle lanes <MAT>, where <MAT>. In other words, ts,i is the number of lanes identified on section s on image i. Now, define a function Δs,i(m,n) that returns the distance between traffic lanes m,n ∈ {<NUM>,. ,ts,i}, and numbers <MAT> where <MAT> is the distance between lane m and the middle point of section s.

With this notation, the parking lanes can be identified based on the following:.

If both conditions are satisfied, lane m is marked as a parking lane.

The input of this module comprises parked vehicles, parking lanes and the sectioning of map data (that is, the simple sections).

The output comprises the number of free parking spots for each section and the number of occupied spots for each section.

First, it is assumed that vehicles v<NUM>,. ,vk have been assigned to a parking lane m that belongs to a section s. Denote by v̂<NUM>,. ,v̂k the projection of the center point of vehicles to lane m to get the distance matrix D: <MAT>.

If there are multiple intersecting images covering one lane, there are multiple matrices D. Based on minimal values of D (excepting the diagonal ones), the minimal distance between two neighboring parking spots can be derived. This distance can be used to mark parking spots between any two cars sufficiently far away from each other. This is, for example, illustrated in <FIG>. The minimal value distance between neighboring parking spots can be stored in an internal table as an additional property of the section. In addition, this property can be used to determine the number of spots on similar streets with fever vehicles observed.

The present technology will now be discussed with reference to the accompanying drawings.

<FIG> depicts an embodiment of a method according to one aspect of the invention. The method comprises using satellite images to identify on-street parking spaces. The present method is particularly useful for mapping parking areas in a city, providing an overview of a parking situation to interested parties, or generating forecasts regarding parking occupancy.

In step S1, satellite images are retrieved and processed. This can comprise retrieving images from a plurality of storage systems such as databases, harmonizing them, quality controlling them, geotagging them and further prepare them to be used as part of the method.

In step S2, objects of interest are detected in the images. Those typically comprise vehicles, but can also comprise landmarks, buildings, or other objects allowing for further data extraction and use. Furthermore, segmentation analysis is performed on each satellite image.

That is, a plurality of image surfaces is identified, a plurality of street sections is identified in map data, and each identified object is assigned to a street section. This is further detailed below.

In step S3, on-street traffic lanes are identified among the street sections. This can be performed by analyzing the detected vehicles and fitting them to a plurality of lines that represent the lanes.

In step S4, on-street traffic lanes from different street section are combined. This can be done both per image (provided multiple street sections belonging to the same street are present in the image, or there are multiple sections with similar properties, e.g., heading of the section) and for a plurality of images covering a certain area. Note, that for this step, a reference map such as Open Street Map can be used to assist with the combining.

In step S5, parking lanes are identified among the on-street traffic lanes. Furthermore, individual parking spots are derived.

Step S6 comprises consolidating and interpreting data related to parking spots. For example, images depicting the same area at different times can be analyzed. The obtained data can be processed to obtain an average or time-based parking occupancy in a given area. Further, different areas can be combined to obtain an on-street parking map for a neighborhood, a town, a city, a country and/or the world.

Given the number of parking spots found in step or submodule S5, the following information can be extracted:.

Note, that although the present method is geared towards satellite images, aerial images can also be used in the same manner to obtain on-street parking spots. Furthermore, a combination of aerial and satellite images is possible as well. For example, images obtained by drones can be used with the present method.

<FIG> depicts an alternative method for on-street parking spot identification based on satellite images.

As before, satellite images are retrieved and processed in step S1'. Following this, objects of interest (preferably at least vehicles) are detected in S2'. In S3', images are matched with a reference map. That is, satellite image streets are matched with a known map of the area, such as, for example, Open Street Map. Then, traffic lines in images are identified and verified with the reference map in S4'. In S5', the images are combined into image blocks which correspond to a certain area or patch of a map. In the image blocks, parking lines are identified and additional error correction is performed as part of step S6'. In step S7', the number of parked cars and free spaces per image block is computed. Note, that lines are used here interchangeably with lanes.

<FIG> depicts a schematic embodiment of a system for identifying on-street parking spaces based on satellite images. The system can comprise at least a storage component <NUM>, a processing component <NUM>, and an output component <NUM>. The system can be implemented on a server, or on a local computing device such as a personal computer. The system can be implemented as a standalone software-based tool for identifying on-street parking. Additionally or alternatively, the system can be implemented as part of an app which assists users with locating an on-street parking spot. The system can also be implemented as part of driver assistance systems and/or navigational hardware and software.

The storage component <NUM> can comprise local or online databases comprising satellite images. The images can originate from a plurality of different sources (such as different satellite systems). Therefore, the storage component <NUM> can have a plurality of sub-components, each corresponding to a separate database or the like. Note, that the storage component <NUM> can comprise a database located on an online server and/or a collection of servers such as a cloud. Additionally or alternatively, the storage component <NUM> can comprise a physical storage device such as a hard drive.

The processing component <NUM> can comprise a processor in a computer and/or a server. The processing component <NUM> can be programmed to execute all of the steps of the algorithm resulting in identifying on-street parking spots. Note, that the processing component <NUM> can also comprise a local and/or a cloud-based processor.

The output component <NUM> can comprise a user interface that is configured to display the results of the algorithm identifying parking spots and/or further information such as parking occupancy. The output component <NUM> can comprise a browser, an app, or a front end of a program designed to run on a computing device such as a smartphone, a laptop, a driver assistance system, a tablet, a GPS unit or the like. Additionally or alternatively, the output component <NUM> can also comprise a back end serving another application or program, that is, an API.

<FIG> depicts a more detailed embodiment of step S1 shown in <FIG> and <FIG>. Satellite images <NUM> are input into a submodule image retrieval S11. First, this submodule connects to all available databases that store satellite images <NUM>, and requests all images that cover a predefined area. The databases can be locally stored, or they might be located at external partners, e.g., satellite provides, and connected by a defined API. The submodule also requests a number of features for each image such as:.

In case some of the above-mentioned features are not available for an image, the module attempts to fill this missing value from another database.

From there, a submodule image quality check S12 takes over. In this submodule, a quality control is performed. In this step, satellite images, or parts of the images that do not meet requirements for further analysis are excluded. This can also be referred to as quality benchmarking. Additional features about images might be counted in this step, and additional information about the area of interest might be used to count these features, e.g., average building height in the area together with sun azimuth and sun elevation might be used to count the probability that further analysis will be affected by shadows. Example of potential image requirements comprise:.

Following quality benchmarking, image georeferencing S13 is performed. Images that successfully pass the QC (quality control) phase are then georeferenced. Existing georeferencing algorithms can be used for this. These algorithms can be based on providing automatic/automated tie point search between satellites, and estimate a model relating ground coordinates to image coordinates.

<FIG> depict embodiments of step S2 as shown in <FIG>. Note, that <FIG> show image processing, while <FIG> show map data processing. In step S2, objects are identified and surface segmentation of satellite images into surfaces is performed. Furthermore, map data is used to extract a plurality of street sections. Note, that all of those outputs are independent, and can be computed in parallel.

<FIG> demonstrates an embodiment of the detected objects <NUM> in an exemplary satellite image <NUM>. Here, the detected objects of interest <NUM> comprise vehicles. However, they can also comprise other objects such as landmarks, buildings or similar structures. For the purpose of the present disclosure, the objects of interest <NUM> generally refer to vehicles <NUM>. Existing object detection algorithms can be used to detect vehicles <NUM> and other objects of relevance, as well as their features. Examples of additional features include:.

<FIG> depicts an exemplary image <NUM> divided into a plurality of surfaces. Different colours indicate different types of terrain automatically recognized. Existing segmentation algorithms can be used to classify types of surfaces captured in an image. These algorithms identify areas on an image with the same surface, and classify them into predefined categories. These categories can include: urban, non-urban, clouds, water, roads, forest, building, etc..

<FIG> depict map data <NUM> of an exemplary street with a plurality of sections <NUM>. In <FIG>, map data <NUM> of a typical street is shown. The street is represented by a linestring (blue solid line). The linestring is defined as an order sequence of points (red dots). For further processing, each linestring has to be separated such that each new linestring contains exactly two points. In <FIG>, results of the separation algorithm applied on 4c is shown, and different sections are indicated by different colour shades.

Note, that map data <NUM> can correspond to publically available map data such as that provided by Open Street Map, and/or comprise proprietary map data.

<FIG> depict more detailed embodiments of step S3 as presented in <FIG>. The object of this subroutine is to identify on-street vehicle lanes in street sections.

<FIG> depicts a schematic flow of the present subroutine. Inputs comprise the identified objects <NUM> and map data comprising street sections <NUM>. The inputs are fed into an object grouping subroutine S31. First, only street sections <NUM> where vehicles <NUM> are allowed to enter are extracted from the map data. This can be done based on the underlying map such as Open Street Map, or by other methods.

Second, recognized objects <NUM> and these street sections <NUM> are merged together. That is, for each object <NUM>, the closest street section <NUM> is assigned to it. Special care must be taken when an object <NUM> is similarly close to two or more street sections <NUM>, as libraries counting spatial distances have limited precision. In such cases, additional features of objects, e.g., vehicle orientation can be taken into account when assigning the closest street sections <NUM>.

Then, a lane identification subroutine S32 is performed. This is described in more detail in <FIG>, which depict more detailed representations of this submodule. First, empirical lane identification S321 is performed. This is followed by quality assurance S322 and lane adjustment S323. <FIG> presents step S321 in more detail. The empirical lane identification S321 subroutine comprises the following steps (as also illustrated by <FIG>).

Back to <FIG>, for each street section <NUM>, its slope (bearing) is compared with the slope of the empirical lane identified in the previous step S321. If the difference is too high, the street section <NUM> is flagged. This happens, e.g., in situations when there are only few vehicles <NUM> identified on a street section <NUM>. In this way, quality assurance S322 is performed.

Finally lanes flagged during quality assurance S322 are adjusted as in step S323. If a street section is flagged, a similar non-flagged section or sections are identified (based on bearing of the sections and other section features), and Empirical lane identification S321 is performed again, but this time stop criteria penalize estimated slope using slopes of similar sections.

<FIG> depict typical outputs of step S3 as depicted in <FIG>.

<FIG> depicts an exemplary output of matching vehicles <NUM> to street sections <NUM> as part of the object grouping step S31. Vehicles <NUM> matched to the same street section <NUM> are marked with the same colour.

<FIG> depicts another part of the object grouping step S31. Vehicles matched to one street section <NUM> are identified as belonging to its one side or another. Left side vehicles <NUM> (shown on the left side of the figure) are shown with a red line, and right side vehicles <NUM>' (shown on the right side of the figure) are shown with a green line.

<FIG> depicts a typical final output of the on-street vehicle lane identification module. A street section <NUM> is shown as a line through the satellite image. Vehicles <NUM> are grouped to a first lane, vehicles <NUM>' to a second line, and vehicle <NUM>" to a third lane. Note, that the third lane comprises only one vehicle.

<FIG> depict exemplary and more detailed embodiments of S4 as shown in <FIG>. That is, they depict consolidation of on-street vehicle lanes from different street sections. This module combines data coming from multiple images, and it creates a uniform notation for on-street vehicle lanes <NUM> across images, as same lane might have different IDs on data from different locations.

<FIG> shows two satellite images of a same area (with a different timestamp) with estimated lanes <NUM>, <NUM>' (with the individual lines denoted 120a, 120b, 120c and 120a', 120b', 120c' left to right respectively). On the left image, there are red vehicles assigned to lane 120a and blue vehicles assigned to lane 120c. On the right figure, there are red vehicles assigned to lane 120a', green to 120b', and blue to 120c'. The middle lane on the left image (lane 120b) is artificial, and comprises an output of the whole module. That is, even if one street section did not have a certain lane (based on the vehicles present in it), it can be added in based on the different street sections (and/or different images).

<FIG> depicts a more detailed breakdown of the lane consolidation submodule. A plurality of satellite images <NUM> serve as inputs. In S41, off-street vehicles are removed. If vehicles <NUM> located off-street are assigned to the street sections <NUM>, they are assigned to one or more separate lanes. These lanes can be easily identified, as their intercepts (that is, offset with respect to the other lanes) are much higher in absolute value than intercept of vehicle lanes <NUM>. Then, the number of lanes <NUM> is determined in step S42. As the number of images increases, this number will simply approach a maximal number of lanes <NUM>, since the probability that there is at least one picture where each lane <NUM> is occupied increases. If the number of pictures is low, additional information about street sections <NUM> might be taken in to account and the number of lanes <NUM> is determined based on offsets of estimated lanes. In step S43, lane identification is established. Here, uniform lane number is assigned to lanes, so that lane number <NUM> is the leftmost vehicle lane, and the rightmost vehicle lane gets the highest number. g, on <FIG>, lane <NUM> is 120a and <NUM> a', <NUM> - 120b (artificial) and 120b', etc..

<FIG> depict more detailed and exemplary embodiments of step S5 as shown in <FIG>. That is, parking lanes <NUM> are identified and parking spaces <NUM> derived. This module can be run independently on each street section <NUM> (but use data from all satellite images <NUM> covering this section) and all vehicles <NUM> assigned to this street section <NUM>.

<FIG> shows a more detailed overview of step S5. Parking lane filtering subroutine S51 comprises determining which on-street vehicle lanes <NUM> are parking lanes <NUM>. From the previous module (the one described in relation to <FIG>), there is a uniform notation of on-street vehicle lanes <NUM>. Obviously, only vehicles in the leftmost and rightmost lanes might be used for parking. Hence, vehicles <NUM> from inner lanes <NUM> are removed from the data set.

In the second step, these potential parking lanes are confirmed to contain parked cars. This is done based on:.

At the end of the process, a list of all parking lanes <NUM> that are used for parking in an area is obtained.

Parking spot features extraction submodule S52 comprises extracting information about additional features for each parking lane <NUM>. The additional information can comprise:.

Spot identification submodule S53 comprises using the features extracted in the previous submodule to identify parking spots <NUM>.

<FIG> schematically depicts a typical street. Two parking lanes <NUM> are present on the extremities. In the middle, street middle line <NUM> is shown. Between the two on each side, moving traffic lane <NUM> or traffic lane <NUM> is depicted.

<FIG> depicts a typical result of step S5 as shown in <FIG>. Parking spots <NUM> and <NUM>' are identified in the depicted satellite image. Note, that parking spots <NUM> are configured for diagonal or perpendicular parking, while parking spots <NUM>' are configured for parallel parking.

Whenever a relative term, such as "about", "substantially" or "approximately" is used in this specification, such a term should also be construed to also include the exact term. That is, e.g., "substantially straight" should be construed to also include "(exactly) straight".

Claim 1:
A method for identifying on-street parking spots (<NUM>, <NUM>') of an area based on at least one of satellite and aerial images (<NUM>) of said area, the method comprising
retrieving and processing a plurality of at least one of satellite and aerial images (<NUM>) by at least quality benchmarking and georeferencing the images (<NUM>); and for each image (<NUM>), detecting objects of interest (<NUM>) comprising at least detected vehicles (<NUM>), computing street sections (<NUM>) based on map data (<NUM>) corresponding to the images (<NUM>), wherein street sections (<NUM>) refer to straight line segments that streets can be subdivided into, and assigning the detected objects (<NUM>) to at least one of the street sections (<NUM>) by computing a closest street section for each detected vehicle; and
for each street section (<NUM>), identifying on-street vehicle lanes (<NUM>, <NUM>') based on the detected objects of interest (<NUM>), wherein identifying on-street vehicle lanes (<NUM>, <NUM>') further comprises recursively identifying on-street vehicle lanes (<NUM>, <NUM>') based on a plurality of detected vehicles assigned to each street section (<NUM>), wherein the recursively identified on-street vehicle lanes (<NUM>, <NUM>') are quality controlled by at least comparing their slope with that of the respective street section (<NUM>); and
combining street sections (<NUM>) based on the identified on-street vehicle lanes (<NUM>, <NUM>') from the plurality of at least one of satellite and aerial images (<NUM>); and
in the combined street sections (<NUM>), identifying parking lanes (<NUM>) and deriving individual parking spots (<NUM>, <NUM>') comprised thereon.