KR102775219B1 - Apparatus and method for creating map - Google Patents

Abstract

A map generation method of a map generation device according to one embodiment includes a step of generating a three-dimensional voxel map in which weights are assigned to voxels of three-dimensional estimated positions of landmarks included in collected landmark data and voxels surrounding the voxels, and a step of generating a map including identification information of at least one landmark among the landmarks based on a comparison result of the weights of the three-dimensional voxel maps.

Description

{APPARATUS AND METHOD FOR CREATING MAP}

The present invention relates to a method and device for generating a map, and more particularly, to a method for generating a map and a device capable of performing the method for generating a map.

For positioning of autonomous vehicles such as automobiles and robots, an electronic map is required.

To create a map, a 3D point cloud and image data for the road can be collected using a MMS (Mobile Mapping System) vehicle, and then the map can be created using this.

Meanwhile, image data collected for map production contains information on various landmarks such as lanes, stop lines, traffic lights, signs, and milestones on the road, and because these landmarks must be distinguished or their types and properties determined, manual work by humans is currently being relied on.

Korean Patent Publication, No. 10-2019-0034130 (Published on April 1, 2019)

The problem to be solved by the present invention is to provide a method and device for generating a map including identification information of landmarks included in collected data.

However, the problems to be solved by the present invention are not limited to those mentioned above, and other problems to be solved that are not mentioned can be clearly understood by a person having ordinary skill in the art to which the present invention belongs from the description below.

A map generation method of a map generation device according to a first aspect includes a step of generating a three-dimensional voxel map in which weights are assigned to voxels of three-dimensional estimated positions of landmarks included in collected landmark data and voxels surrounding the voxels, and a step of generating a map including identification information of at least one of the landmarks based on a comparison result of the weights of the three-dimensional voxel maps.

According to the second aspect, a computer-readable recording medium storing a computer program includes instructions for causing a processor to perform the above map generation method.

According to a third aspect, a computer program stored on a computer-readable recording medium includes instructions for causing a processor to perform the above map generation method.

A map generation device according to a fourth aspect includes a data collection unit that collects landmark data, and a control unit that generates a map based on the collected landmark data, wherein the control unit generates a three-dimensional voxel map in which weights are assigned to voxels of three-dimensional estimated positions of landmarks included in the collected landmark data and voxels surrounding the voxels, and generates the map including identification information of at least one landmark among the landmarks based on a comparison result of the weights of the three-dimensional voxel maps.

According to one embodiment, a map including identification information of landmarks included in the collected data can be automatically generated and provided. The map generated in this way can be used for positioning for autonomous driving of automobiles, robots, etc., and since it does not rely on manual work by humans, it has the effect of reducing the cost required for producing, updating, and maintaining the map.

Figure 1 is a configuration diagram of a map generation device according to one embodiment.
FIGS. 2 and 3 are flowcharts illustrating a map generation method according to one embodiment.
FIG. 4 is a drawing illustrating a three-dimensional voxel map generated by a map generating device according to one embodiment.
Figure 5 is a diagram illustrating the relationship between the average μ and the 3D position p of a landmark in a 3D voxel.
Figure 6 is a diagram illustrating a two-dimensional grid for calculating weights when the location of a landmark is expressed in two dimensions.
Figure 7 is an example of converting a 3D voxel map of a continuous landmark into a 2D weighted grid map and displaying it.
Figure 8 is an example of converting a 3D voxel map of a discrete landmark into a 2D weighted grid map and displaying it.
Figures 9 and 10 are examples of comparing the weights of voxels to find voxels representing representative landmarks.
Figure 11 is an example of converting voxels with the highest weights relative to the surrounding area for clustering continuous landmarks into a two-dimensional weighted grid map and displaying them.
Figure 12 is an example of converting voxels with the highest weights relative to the surrounding area for clustering discrete landmarks into a two-dimensional weight grid map and displaying them.
Figures 13 and 14 illustrate the positions and covariances of three-dimensional landmarks finally obtained according to one embodiment, with Figure 13 being a three-dimensional view and Figure 14 being a two-dimensional view.

The advantages and features of the present invention, and the methods for achieving them, will become clear with reference to the embodiments described in detail below together with the accompanying drawings. However, the present invention is not limited to the embodiments disclosed below, but may be implemented in various different forms, and these embodiments are provided only to make the disclosure of the present invention complete and to fully inform those skilled in the art of the scope of the invention, and the present invention is defined only by the scope of the claims.

In describing embodiments of the present invention, if it is judged that a detailed description of a known function or configuration may unnecessarily obscure the gist of the present invention, the detailed description will be omitted. In addition, the terms described below are terms defined in consideration of functions in the embodiments of the present invention, and these may vary depending on the intention or custom of the user or operator. Therefore, the definitions should be made based on the contents throughout this specification.

In this specification, singular expressions include plural expressions unless the context clearly indicates otherwise. In this application, it should be understood that terms such as "comprise" or "comprises" are intended to specify the presence of a feature, number, step, operation, component, part or combination thereof described in the specification, but do not exclude in advance the possibility of the presence or addition of one or more other features, numbers, steps, operations, components, parts or combinations thereof.

In addition, in the embodiment of the present invention, when it is said that a part is connected to another part, this includes not only a direct connection but also an indirect connection through another medium. In addition, when it is said that a part includes a certain component, it means that it may further include other components, rather than excluding other components, unless there is a specific description to the contrary.

Figure 1 is a configuration diagram of a map generation device according to one embodiment.

As shown in FIG. 1, a map generation device (100) according to one embodiment includes a data collection unit (110) and a control unit (120), and may further include an output unit (130).

The data collection unit (110) collects landmark data including information about landmarks and provides the data to the control unit (120). For example, the data collection unit (110) can collect landmark data including information about various landmarks such as lanes, stop lines, traffic lights, signs, and milestones existing on the road. The data collection unit (110) can include a photographing means such as a camera, and can be mounted on an autonomous vehicle such as a car or a robot, and can photograph images including various landmarks while the autonomous vehicle is in operation and provide the images to the control unit (120). Alternatively, the data collection unit (110) can include a communication means and can receive landmark data acquired from another terminal device from another terminal device through a communication channel.

The control unit (120) generates a three-dimensional voxel map in which weights are assigned to voxels of three-dimensional estimated positions of landmarks included in landmark data collected by the data collection unit (110) and voxels surrounding the voxels, and generates a map including identification information of at least one landmark among the landmarks based on the comparison result of the weights of the three-dimensional voxel maps. The control unit (120) may include computing means such as a microprocessor, for example. For example, the control unit (120) may detect landmarks from an image including various landmarks such as lanes, stop lines, traffic lights, signs, and milestones through a known deep learning-based algorithm, and lanes and stop lines may be classified as continuous landmarks, while traffic lights, signs, and milestones may be classified as discrete landmarks. The control unit (120) may cluster identical landmarks among the detected landmarks, and recognize identical landmarks as one landmark. To this end, the control unit (120) can generate a three-dimensional voxel map that assigns weights to voxels based on probability, and can generate a map that includes identification information of at least one landmark among the landmarks based on the comparison result of the weights of the three-dimensional voxel map.

When generating a 3D voxel map, the control unit (120) can express an error or uncertainty for a 3D estimated position of a specific landmark as a Gaussian probability distribution including covariance, and when the covariance is relatively large, weights can be calculated and added for a relatively wider range of surrounding voxels than when the covariance is relatively small. In addition, the control unit (120) can generate a 3D voxel map corresponding to a continuous landmark and a 3D voxel map corresponding to a discrete landmark, respectively.

When generating a map including landmark identification information, the control unit (120) may select a group of voxel candidates representing a representative landmark among landmarks based on the comparison results of weights from a three-dimensional voxel map. Here, the control unit (120) may determine a specific voxel as a voxel representing a representative landmark if the weight of the specific voxel is greater than the weights of surrounding voxels within a predefined threshold distance.

The control unit (120) can estimate the type, properties, and location of the representative landmark from the voxel candidate group of the representative landmark, and can generate a map including the type, properties, and location of the estimated representative landmark as identification information of the corresponding landmark. Here, the voxel corresponding to the selected voxel candidate group can have a list of the types and properties of the landmarks used to calculate the weights, and the control unit (120) can use voting to determine the type and property of the corresponding landmark according to one of the lists. For example, the control unit (120) can estimate the location by using a landmark corresponding to the type and properties determined through voting among the landmarks used to calculate the weights.

The output unit (130) can output the map generated by the control unit (120). For example, the output unit (130) can output the map in a form stored in a computer-readable recording medium such as a memory. Alternatively, the output unit (130) can include a communication means, and can transmit data including the map generated by the control unit (120) from another terminal device through a communication channel. In addition, when the control unit (120) stores the map in the internal memory and then uses it for positioning, the map generating device (100) may not include the output unit (130).

Hereinafter, a map generation method performed by a map generation device (100) according to one embodiment will be described in detail with reference to FIGS. 1 to 13.

First, the data collection unit (110) collects landmark data containing information about landmarks and provides it to the control unit (120). For example, the data collection unit (110) can collect landmark data containing information about various landmarks such as lanes, stop lines, traffic lights, signs, and milestones existing on the road in the form of images, and provide the collected image data to the control unit (120) (S210).

Then, the control unit (120) that receives landmark data from the data collection unit (110) can generate a three-dimensional voxel map as illustrated in Fig. 4 to cluster landmarks (S220). For example, if the landmark data is provided in the form of image data, the control unit (120) can detect various landmarks such as lanes, stop lines, traffic lights, signs, and milestones included in the image through a known deep learning-based algorithm.

And, the control unit (120) can generate a map including identification information of at least one landmark among the landmarks using a three-dimensional voxel map (S230).

In this way, the process of the control unit (120) generating a map through steps S220 and S230 will be examined in more detail.

The control unit (120) can create a three-dimensional voxel map by using a method of adding weights to voxels within a 3 sigma range using covariance representing an error or uncertainty about the location of a landmark. Initially, the weights of all voxels can be set to '0', and the weights of voxels can be updated by adding the weights calculated by each landmark.

If the 3D position of a specific landmark is modeled as a Gaussian error, it can be expressed by the mean μ and covariance C, and mathematical expression 1 represents the Gaussian probability distribution function for a multidimensional random variable.

Here, d is 3 because it expresses the landmark's location in three dimensions. The average μ represents the estimated location of the landmark, and the probability value varies depending on the three-dimensional location p value. The probability is the highest when p is μ, and the probability decreases as the |p-μ| value increases.

Figure 5 is a drawing showing the relationship between μ and p to calculate the weight of a voxel corresponding to an average μ and its surrounding voxels using mathematical expression 1 from one landmark. The control unit (120) calculates the Mahalanobis distance (=) among the surrounding voxels. ) can be weighted up to voxels where the covariance C is below a threshold (for example, 3*standard deviation), and weights can be added to the surrounding voxels. Here, the meaning of the covariance C is that the error or uncertainty about the estimated position of the landmark is expressed as a Gaussian probability distribution. The larger the covariance C, the higher the probability that a position error will occur, and conversely, the smaller the covariance C, the higher the probability that a position error will occur. For this reason, the control unit (120) can calculate and add weights for a relatively wider range of surrounding voxels when the covariance C is large than when the covariance C is small, and conversely, can calculate and add weights for a relatively smaller range of surrounding voxels when the covariance C is small than when the covariance C is large. FIG. 6 shows an example in which an area where the Mahalanobis distance is below a specific threshold in a two-dimensional Gaussian probability distribution is indicated by a green ellipse. The shape and size of the ellipse in FIG. 6 vary depending on the covariance. When the location of a landmark is expressed in two dimensions, a two-dimensional grid for which weights are to be calculated is indicated by an ellipse. In a two-dimensional Gaussian probability distribution, a portion corresponding to an area where the Mahalanobis distance satisfies a specific threshold or less is indicated by an ellipse, and if the location of a landmark is expressed in two dimensions, weights are calculated for the two-dimensional grid corresponding to the ellipse and the corresponding weights are updated. In this process, the control unit (120) can perform updates by distinguishing a three-dimensional voxel map for a continuous landmark and a three-dimensional voxel map for a discrete landmark, calculating weights for voxels for which weights are to be calculated, and continuously adding the previous weight of each voxel to the newly calculated weight.

Fig. 7 is an example of converting a 3D voxel map of a continuous landmark into a 2D grid map by projecting it onto the x, y plane about the z axis, and displaying it, and shows weight values obtained from all continuous landmarks. Fig. 8 is an example of converting a 3D voxel map of a discrete landmark into a 2D grid map by projecting it onto the x, y plane about the z axis, and displaying it, and shows weight values obtained from all discrete landmarks. In Figs. 7 and 8, a lower weight value is expressed darker, and a higher weight value is expressed closer to white.

Thereafter, the control unit (120) can select a group of voxel candidates representing representative landmarks among the landmarks based on the comparison results of the weights assigned to each voxel from the 3D voxel map (S310).

FIGS. 9 and 10 illustrate comparison of weights of surrounding voxels to determine whether voxel v(i,j,k) has the highest weight in order to find a voxel representing a representative landmark. The control unit (120) can compare the weight of each voxel with the weight values of surrounding voxels to find a voxel representing a representative landmark, and determine a voxel having a weight value greater than the weight values of the surrounding voxels as a voxel representing a representative landmark. The surrounding voxels correspond to adjacent voxels in a three-dimensional space, and can compare weights with voxels that are less than a predefined threshold distance from a reference voxel v(i,j,k).

Fig. 11 is an example of displaying the voxels with the highest weights relative to the surrounding area for clustering continuous landmarks by converting them into a two-dimensional weighted grid map. In Fig. 7, the voxels corresponding to the continuous landmarks with the highest weights relative to the local area are indicated with red dots. Fig. 12 is an example of displaying the voxels with the highest weights relative to the surrounding area for clustering discrete landmarks by converting them into a two-dimensional weighted grid map. In Fig. 8, the voxels corresponding to the discrete landmarks with the highest weights relative to the local area are indicated with red dots.

The control unit (120) can estimate the type and properties of the recognized object and the 3D landmark position from voxels corresponding to the representative landmark candidate group (S320). If the landmark data is provided in the form of image data from the data collection unit (110), the control unit (120) can recognize landmarks such as lanes, stop lines, traffic lights, signs, and milestones in the image using a deep learning-based algorithm, and at this time, it has the type and property information of the recognition object. Here, the type of the recognition object may mean a lane, a stop line, a traffic light, a sign, and a milestone, and as property information of each landmark, the lane may be a dotted line, a solid line, a double lane, etc., the stop line may be a solid line, and the traffic light may be divided into horizontal, vertical, two lights, three lights, and four lights, and the sign may be a maximum/minimum speed sign, a towable area sign, a driving guide sign, etc., and the milestone may be information indicating the direction of each lane, etc.

Meanwhile, the voxel corresponding to the representative landmark candidate group has multiple lists of the 3D position and covariance for the landmark used to calculate the weight, and the recognition target type and attribute information. Therefore, a landmark of one recognition target type and attribute should be determined from the corresponding voxel, and for this purpose, the control unit (120) can use a voting method. For example, the control unit (120) can set the recognition target type and attribute information as one voting target and determine the recognition target type and attribute information with the most votes as the final recognition target type and attribute information. For example, if the number of votes for 'Top speed sign/60 km' is 5, the number of votes for 'Milestone/Bundang-gu Office direction' is 2, and the number of votes for 'Traffic light/3 horizontal lights' is 1, the 'Top speed sign' can be the recognition target type, and '60 km' can be the finally determined attribute information for the corresponding voxel.

And, the control unit (120) accurately obtains the 3D position and covariance (error) of the landmark by using only the landmarks corresponding to the finally determined recognition target type and attribute information among the landmarks used to calculate the weights in the voxel. For example, the control unit (120) can obtain the mean μ ⁺ corresponding to the 3D position of the landmark to be finally obtained and the covariance C ⁺ corresponding to the landmark position error by using a standard Kalman filter such as Equations 2 and 3.

Here, n is assumed to be the number of valid landmarks to finally estimate the location and covariance of the landmarks.

Thereafter, the control unit (120) can generate a map including the type, properties, and location of the estimated representative landmark as identification information, as in the examples of FIGS. 13 and 14 (S330).

Figures 13 and 14 show the positions and covariances of the three-dimensional landmarks finally obtained by the control unit (120). Figure 13 is a three-dimensional view, and Figure 14 is a two-dimensional view. In Figures 13 and 14, blue dots represent lanes, red dots represent signs, and purple dots represent traffic lights.

And, the output unit (130) can output the map generated by the control unit (120). For example, the output unit (130) can output the map in a form stored in a computer-readable recording medium such as a memory. Alternatively, the output unit (130) can transmit data including the map generated by the control unit (120) from another terminal device through a communication channel.

As described so far, according to the embodiments of the present invention, a map including identification information of landmarks included in collected data can be automatically generated and provided. The map generated in this way can be used for positioning for autonomous driving of automobiles or robots, and since it does not depend on manual work by humans, the cost required for producing, updating, and maintaining the map is reduced.

The combination of each step of each flowchart attached to the present invention may be performed by computer program instructions. These computer program instructions may be installed in a processor of a general-purpose computer, a special-purpose computer, or other programmable data processing equipment, so that the instructions executed by the processor of the computer or other programmable data processing equipment create a means for performing the functions described in each step of the flowchart. These computer program instructions may also be stored in a computer-usable or computer-readable recording medium that can direct a computer or other programmable data processing equipment to implement the function in a specific manner, so that the instructions stored in the computer-usable or computer-readable recording medium can also produce an article of manufacture including an instruction means for performing the functions described in each step of the flowchart. Since the computer program instructions can also be installed on a computer or other programmable data processing apparatus, a series of operational steps are performed on the computer or other programmable data processing apparatus to create a computer-executable process, so that the instructions that cause the computer or other programmable data processing apparatus to perform the steps for performing the functions described at each step of the flowchart can also provide steps for performing the functions described at each step of the flowchart.

Additionally, each step may represent a module, segment, or portion of code that includes one or more executable instructions for performing a particular logical function(s). It should also be noted that in some alternative embodiments, the functions mentioned in the steps may occur out of order. For example, two steps depicted in succession may in fact be performed substantially concurrently, or the steps may sometimes be performed in reverse order, depending on the functionality involved.

The above description is merely an illustrative description of the technical idea of the present invention, and those skilled in the art will appreciate that various modifications and variations may be made without departing from the essential characteristics of the present invention. Accordingly, the embodiments disclosed in the present invention are not intended to limit the technical idea of the present invention but to explain it, and the scope of the technical idea of the present invention is not limited by these embodiments. The protection scope of the present invention should be interpreted by the following claims, and all technical ideas within a scope equivalent thereto should be interpreted as being included in the scope of the rights of the present invention.

According to one embodiment, a map including identification information of landmarks included in collected data can be automatically generated and provided. The present invention can be applied to various fields that utilize autonomous vehicles such as automobiles and robots.

100: Map generator
110: Data Collection Department
120: Control Unit
130: Output section

Claims (10)

As a map generation method of a map generation device,
A step of generating a 3D voxel map in which weights are applied to voxels of 3D estimated locations of landmarks included in the collected landmark data and to voxels around them,
For each voxel of the above 3D voxel map, a step of comparing the weight of each voxel with the weights of surrounding voxels located below a predefined threshold distance from each voxel, and determining that the voxel is a voxel representing a representative landmark if the weight of each voxel is the maximum value compared to the weights of the surrounding voxels;
A step of generating a map including identification information of at least the representative landmark among the landmarks based on the comparison result of the weights of the three-dimensional voxel maps.
How to create a map. In paragraph 1,
The steps for generating the above map are:
A step of selecting a group of voxel candidates representing the representative landmark among the landmarks based on the comparison result of the weights from the three-dimensional voxel map,
A step of estimating the type, properties and location of the representative landmark from the above-mentioned selected voxel candidate group,
A step of generating the map including the type, properties and location of the estimated representative landmark as the identification information.
How to create a map. In paragraph 1,
The step of generating the above 3D voxel map is to express the error or uncertainty for the 3D estimated position of a specific landmark as a Gaussian probability distribution including covariance, and when the covariance is relatively large, calculate and add the weight for a relatively wider range of surrounding voxels than when the covariance is relatively small.
How to create a map. In paragraph 1,
The step of generating the above 3D voxel map classifies the landmarks into continuous landmarks and discrete landmarks, and generates a 3D voxel map corresponding to the continuous landmarks and a 3D voxel map corresponding to the discrete landmarks, respectively.
How to create a map. delete In the second paragraph,
The step of estimating the type, properties and location of the representative landmark includes having a list of the types and properties of landmarks used to calculate the weights for the voxels corresponding to the selected voxel candidates, and using voting to determine the type and properties of the landmark according to one of the lists.
How to create a map. In paragraph 6,
Among the landmarks used to calculate the above weights, the location is estimated using the landmark corresponding to the type and properties determined through the above voting.
How to create a map. A computer-readable recording medium storing a computer program,
A method comprising instructions for causing a processor to perform any one of the methods of claims 1 to 4 and claims 6 to 7.
Computer readable recording medium. A computer program stored on a computer-readable recording medium,
A method comprising instructions for causing a processor to perform any one of the methods of claims 1 to 4 and claims 6 to 7.
Computer program. A data collection unit that collects landmark data,
A control unit for generating a map based on the collected landmark data is included.
The control unit generates a three-dimensional voxel map in which weights are assigned to voxels of three-dimensional estimated locations of landmarks included in the collected landmark data and to voxels surrounding the voxels, and for each voxel of the three-dimensional voxel map, compares the weight of each voxel with the weights of surrounding voxels located below a predefined threshold distance from each voxel, and determines the voxel as a voxel representing a representative landmark if the weight of each voxel is a maximum value compared to the weights of the surrounding voxels, and generates the map including identification information of at least the representative landmark among the landmarks based on the comparison result of the weights of the three-dimensional voxel map.
Map generating device.

Images