Method for generating road topology information and system thereof

Abstract

The present disclosure provides a method for generating road topology information performed by at least one processor. With respect to coordinate data of a road, boundary conditions between segments including topology information may be calculated to make the connection between segments flexible, and a midpoint of a curve of a segment may be detected to directly calculate control points of a B?zier curve, thereby generating a parametric B?zier curve. Accordingly, more precise road map may be generated even when the coordinate data of the segment of the road includes an error.

Claims

1. A method performed by a processor of an information processing system, the method comprising: determining a plurality of points in a target segment, wherein the target segment comprises a portion of a path of a road, and wherein each of the plurality of points corresponds to a point of the portion of the path of the road; determining at least one first point in a first adjacent segment, wherein each of the at least one first point corresponds to a point, of the path of the road, in the first adjacent segment, and wherein the first adjacent segment is adjacent to a first boundary of the target segment; determining at least one second point in a second adjacent segment, wherein each of the at least one second point corresponds to a point, of the path of the road, in the second adjacent segment, and wherein the second adjacent segment is adjacent to a second boundary of the target segment; determining a midpoint of a curve of the target segment, wherein the curve comprises at least two points of the plurality of points in the target segment, and wherein the midpoint of the curve is determined based on: the plurality of points, the at least one first point, and the at least one second point; generating, based on at least one control point, an adjusted curve corresponding to the path of the road in the target segment, wherein the at least one control point is based on: the midpoint of the curve; and a slope associated with the at least one first point and at least one of the plurality of points; outputting, based on the adjusted curve, an indication associated with adjusted coordinate data of the road; and causing, by outputting the indication associated with adjusted coordinate data of the road, at least one of: autonomous driving simulation along the path of the road; or autonomous driving control of a vehicle along the path of the road.

2. The method according to claim 1, further comprising: determining boundary conditions associated with the target segment by using: boundary points of the target segment; first coordinate data corresponding to the at least one first point in the first adjacent segment; second coordinate data corresponding to at least one of the plurality of points in the target segment; and third coordinate data corresponding to the at least one second point in the second adjacent segment.

3. The method according to claim 2, wherein the boundary conditions are determined by further using at least one of: fourth coordinate data corresponding to the at least one first point in the first adjacent segment and adjacent to the boundary points; or fifth coordinate data corresponding to the at least one second point in the second adjacent segment and adjacent to the boundary points.

4. The method according to claim 1, wherein the determining the midpoint of the curve comprises: generating an n-th degree polynomial by using boundary conditions for the curve of the target segment; and determining, based on the n-th degree polynomial, the midpoint of the curve.

5. The method according to claim 1, wherein the determining the midpoint of the curve comprises: based on a determination that an n-th degree polynomial cannot be generated by using boundary conditions for the curve of the target segment, detecting coordinate data positioned at a center among coordinate data forming the target segment, as the midpoint of the curve.

6. The method according to claim 1, wherein the determining the at least one control point comprises: determining the at least one control point by using: the midpoint of the curve; boundary points; and boundary conditions.

7. The method according to claim 1, further comprising: after generating the adjusted curve: determining an error between the adjusted curve and coordinate data of the road; and determining whether the error is out of a preset error range.

8. The method according to claim 7, further comprising, based on a determination that the error is out of the preset error range, dividing a section of the target segment into a plurality of sub-segments, and repeating the steps of claim 1 for each sub-segment of the plurality of sub-segments.

9. A computing device comprising: at least one processor; and memory storing instructions that, when executed by the at least one processor, cause the computing device to: determine a plurality of points in a target segment, wherein the target segment comprises a portion of a path of a road, and wherein each of the plurality of points corresponds to a point of the portion of the path of the road; determine at least one first point in a first adjacent segment, wherein each of the at least one first point corresponds to a point, of the path of the road, in the first adjacent segment, and wherein the first adjacent segment is adjacent to a first boundary of the target segment; determine at least one second point in a second adjacent segment, wherein each of the at least one second point corresponds to a point, of the path of the road, in the second adjacent segment, and wherein the second adjacent segment is adjacent to a second boundary of the target segment; determine a midpoint of a curve of the target segment, wherein the curve comprises at least two points of the plurality of points in the target segment, and wherein the midpoint of the curve is determined based on: the plurality of points, the at least one first point, and the at least one second point; generate, based on at least one control point, an adjusted curve corresponding to the path of the road in the target segment, wherein the at least one control point is based on: the midpoint of the curve; and a slope associated with the at least one first point and at least one of the plurality of points; output, based on the adjusted curve, an indication associated with adjusted coordinate data of the road; and causing, by outputting the indication associated with adjusted coordinate data of the road, at least one of: autonomous driving simulation along the path of the road; or autonomous driving control of a vehicle along the path of the road.

10. A non-transitory computer-readable recording medium storing instructions that, when executed by at least one processor, cause a computing device to: determine a plurality of points in a target segment, wherein the target segment comprises a portion of a path of a road, and wherein each of the plurality of points corresponds to a point of the portion of the path of the road; determine at least one first point in a first adjacent segment, wherein each of the at least one first point corresponds to a point, of the path of the road, in the first adjacent segment, and wherein the first adjacent segment is adjacent to a first boundary of the target segment; determine at least one second point in a second adjacent segment, wherein each of the at least one second point corresponds to a point, of the path of the road, in the second adjacent segment, and wherein the second adjacent segment is adjacent to a second boundary of the target segment; determine a midpoint of a curve of the target segment, wherein the curve comprises at least two points of the plurality of points in the target segment, and wherein the midpoint of the curve is determined based on: the plurality of points, the at least one first point, and the at least one second point; generate, based on at least one control point, an adjusted curve corresponding to the path of the road in the target segment, wherein the at least one control point is based on: the midpoint of the curve; and a slope associated with the at least one first point and at least one of the plurality of points; output, based on the adjusted curve, an indication associated with adjusted coordinate data of the road; and causing, by outputting the indication associated with adjusted coordinate data of the road, at least one of: autonomous driving simulation along the path of the road; or autonomous driving control of a vehicle along the path of the road.

11. The non-transitory computer-readable recording medium according to claim 10, wherein the instructions, when executed by the at least one processor, cause the computing device to: after generating the adjusted curve: determine an error between the adjusted curve and coordinate data of the road; and determine whether the error is out of a preset error range.

12. The computing device according to claim 9, wherein the instructions, when executed by the at least one processor, cause the computing device to: determine boundary conditions associated with the target segment by using: boundary points of the target segment; first coordinate data corresponding to the at least one first point in the first adjacent segment; second coordinate data corresponding to at least one of the plurality of points in the target segment; and third coordinate data corresponding to the at least one second point in the second adjacent segment.

13. The computing device according to claim 9, wherein the instructions, when executed by the at least one processor, cause the computing device to determine the midpoint of the curve by: generating an n-th degree polynomial by using boundary conditions for the curve of the target segment; and determining, based on the n-th degree polynomial, the midpoint of the curve.

14. The computing device according to claim 9, wherein the instructions, when executed by the at least one processor, cause the computing device to determine the midpoint of the curve by: based on a determination that an n-th degree polynomial cannot be generated by using boundary conditions for the curve of the target segment, detecting coordinate data positioned at a center among coordinate data forming the target segment, as the midpoint of the curve.

15. The computing device according to claim 9, wherein the instructions, when executed by the at least one processor, cause the computing device to determine the at least one control point by: determining the at least one control point by using: the midpoint of the curve; boundary points; and boundary conditions.

16. The computing device according to claim 9, wherein the instructions, when executed by the at least one processor, cause the computing device to: after generating the adjusted curve: determine an error between the adjusted curve and coordinate data of the road; and determine whether the error is out of a preset error range.

17. The computing device according to claim 16, wherein the instructions, when executed by the at least one processor, cause the computing device to: based on a determination that the error is out of the preset error range, divide a section of the target segment into a plurality of sub-segments.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) Embodiment(s) of the present disclosure will be described with reference to the accompanying drawings described below, where similar reference numerals indicate similar elements, although the embodiment(s) are not limited thereto.

(2) FIG. 1 is a view provided to explain a concept related to generation of road topology information according to an embodiment of the present disclosure.

(3) FIG. 2 is a flowchart illustrating a method for generating road topology information in virtual environment according to an embodiment of the present disclosure.

(4) FIG. 3 is a flowchart illustrating a method for generating road topology information in virtual environment according to an embodiment of the present disclosure.

(5) FIG. 4 is an exemplary graph for modeling a B?zier curve from coordinate data according to an embodiment of the present disclosure.

(6) FIG. 5 is an exemplary graph provided to explain a method for generating a parametric B?zier curve based on control points calculated by using the graph of FIG. 4.

(7) FIG. 6 is an exemplary graph provided to explain a method for generating a parametric B?zier curve based on control points calculated by using the graph of FIG. 4.

(8) FIG. 7 is an exemplary graph illustrating a parametric B?zier curve calculated by a plurality of coordinate points according to an embodiment of the present disclosure.

(9) FIG. 8 is an exemplary graph provided to explain generating a curve using the graph of FIG. 4 with the method for generating road topology information according to an embodiment of the present disclosure, in comparison with the related method.

(10) FIG. 9 is an exemplary graph provided to explain generating a curve using the graph of FIG. 4 with the method for generating road topology information according to an embodiment of the present disclosure, in comparison with the related method.

(11) FIG. 10 is an exemplary block diagram illustrating an internal configuration of an information processing system for executing a method for generating road topology information according to an embodiment of the present disclosure.

DETAILED DESCRIPTION

(12) Hereinafter, specific details for the practice of the present disclosure will be described in detail with reference to the accompanying drawings. However, in the following description, detailed descriptions of well-known functions or configurations will be omitted when it may make the subject matter of the present disclosure rather unclear.

(13) In the accompanying drawings, the same or corresponding elements are assigned the same reference numerals. In addition, in the following description of the examples, duplicate descriptions of the same or corresponding components may be omitted. However, even if descriptions of components are omitted, it is not intended that such components are not included in any embodiment.

(14) Advantages and features of the disclosed examples and methods of accomplishing the same will be apparent by referring to examples described below in connection with the accompanying drawings. However, the present disclosure is not limited to the examples disclosed below, and may be implemented in various different forms, and the present examples are merely provided to make the present disclosure complete, and to fully disclose the scope of the disclosure to those skilled in the art to which the present disclosure pertains.

(15) The terms used herein will be briefly described prior to describing the disclosed examples in detail. The terms used herein have been selected as general terms which are widely used at present in consideration of the functions of the present disclosure, and this may be altered according to the intent of an operator skilled in the art, conventional practice, or introduction of new technology. In addition, in specific cases, certain terms may be arbitrarily selected by the applicant, and the meaning of the terms will be described in detail in a corresponding description of the examples. Therefore, the terms used in the present disclosure should be defined based on the meaning of the terms and the overall content of the present disclosure rather than a simple name of each of the terms.

(16) As used herein, the singular forms a, an, and the are intended to include the plural forms as well, unless the context clearly indicates the singular forms. Further, the plural forms are intended to include the singular forms as well, unless the context clearly indicates the plural forms. Further, throughout the description, when a portion is stated as comprising (including) a component, it intends to mean that the portion may additionally comprise (or include or have) another component, rather than excluding the same, unless specified to the contrary.

(17) Further, the term module or unit used herein refers to a software or hardware component, and module or unit performs certain roles. However, the meaning of the module or unit is not limited to software or hardware. The module or unit may be configured to be in an addressable storage medium or configured to reproduce one or more processors. Accordingly, as an example, the module or unit may include components such as software components, object-oriented software components, class components, and task components, and at least one of processes, functions, attributes, procedures, subroutines, program code segments of program code, drivers, firmware, micro-codes, circuits, data, database, data structures, tables, arrays, and variables. Furthermore, functions provided in the components and the modules or units may be combined into a smaller number of components and modules or units, or further divided into additional components and modules or units.

(18) According to an embodiment, the module or unit may be implemented as a processor and a memory. The processor should be interpreted broadly to encompass a general-purpose processor, a central processing unit (CPU), a microprocessor, a digital signal processor (DSP), a controller, a microcontroller, a state machine, and so forth. Under some circumstances, the processor may refer to an application-specific integrated circuit (ASIC), a programmable logic device (PLD), a field-programmable gate array (FPGA), and so on. The processor may refer to a combination of processing devices, e.g., a combination of a DSP and a microprocessor, a plurality of microprocessors, one or more microprocessors in conjunction with a DSP core, or any other combination of such configurations. In addition, the memory should be interpreted broadly to encompass any electronic component that is capable of storing electronic information. The memory may refer to various types of processor-readable media such as random access memory (RAM), read-only memory (ROM), non-volatile random access memory (NVRAM), programmable read-only memory (PROM), erasable programmable read-only memory (EPROM), electrically erasable PROM (EEPROM), flash memory, magnetic or optical data storage, registers, and so on. The memory is said to be in electronic communication with a processor if the processor can read information from and/or write information to the memory. The memory integrated with the processor is in electronic communication with the processor.

(19) In the present disclosure, a B?zier curve refers to a mathematical curve used to express a curve of a road, and is generated through a function expression using a plurality of control points as a medium.

(20) In addition, in the present disclosure, a path of a road may be represented by a plurality of segments, in which the segments may include a relative position in relation to the previous and next segments, road topology information, for example, a plurality of coordinate data (including position and number), and the like. Segments to generate a B?zier curve according to the present disclosure are defined as target segments. In addition, it is assumed that the target segments include one or more previous and next segments for convenience of description.

(21) In addition, in the present disclosure, since the target segments are described based on the assumption that they include a series of connected segments including both the previous and next segments, connection point of the segments and boundary points of the segments may be used as having the same meaning.

(22) In addition, in the present disclosure, the coordinate data may refer to GPS coordinates or position coordinates corresponding thereto. For example, the coordinate data may refer to GPS coordinates, which are the position information acquired by operating the GPS at about 100 Hz at predetermined intervals (e.g., 10 msec).

(23) FIG. 1 is a view provided to explain a concept related to generation of road topology information according to an embodiment of the present disclosure.

(24) FIG. 1(a) illustrates certain segments among a plurality of segments generated from the segmentation of a road. Segment R goes in S direction and includes a plurality of data points. FIG. 1 illustrates a process of generating a B?zier curve with four control points P.sub.1, P.sub.2, P.sub.3 and P.sub.4. For example, two end points P.sub.1 and P.sub.4 and two midpoints P.sub.2 and P.sub.3 are used as control points, and may be defined through the following functional expression, for example, a third degree polynomial.
P(t)=(1?t).sup.3P1+3t(1?t).sup.2P2+3t.sup.2(1?t)P3+t.sup.3P4,0?t?1[Equation 1]

(25) Conventionally, in order to generate the B?zier curve as described above, a plurality of coordinate data included in the segment R are directly used as control points. However, when some of the coordinate data includes an error exceeding a reference range, and the coordinate data including the error is used as the control points, the virtual road obtained by the generation of the B?zier curve also has a large error from the actual road.

(26) Accordingly, in order to minimize the error between the actual road and the virtual road, the present disclosure proposes a method for generating a B?zier curve by using points 11 and 12 not included in the segment R as control points. When the B?zier curve is generated by using the points 11 and 12 not included in the segment R as mentioned above, it is hardly affected by the error even when there is the error in the coordinate data forming the segment R. The points 11 and 12 selected as the control points are directly calculated by using the method according to the present disclosure to minimize the error, which will be described in more detail below.

(27) FIGS. 2 and 3 are flowcharts illustrating a method for generating road topology information in virtual environment according to an embodiment of the present disclosure. In an example, the method for generating road topology information described below may be performed by one or more processors.

(28) Referring to FIG. 2, the processor calculates 210 boundary conditions between segments with respect to the coordinate data of a road. In an example, a path of the road may be represented by an appropriate number of segments, and a segmentation condition for the segments may be preset. For example, the processor may set to divide into segments when the error of the sampling data is out of a reference error range (or when it satisfies an error condition). In an example, the boundary conditions between segments is set by including some of the coordinate data included in the preceding segment and the next segment of a target segment together with the boundary points of the target segment. Accordingly, connection between the segments is more flexible, and it is possible to prevent an abrupt route change at the boundary of the segment when the autonomous vehicle is driving on the road. In addition, in an example, in order to remove the error of data after setting the boundary conditions between segments, a process of matching the coordinate data with the first differential value of a connection point positioned at the boundary of the target segment may be performed.

(29) The processor may generate a curve of the road in a polynomial form and detects 220 a midpoint of the curve. Specifically, the curve of the segment of the road is generated in the polynomial form in a coordinate system that is set according to the calculation of the boundary conditions corresponding to the process 210 described above. In the present disclosure, generating the third degree polynomial is exemplified in consideration of convenience of description and computational complexity, but examples are not limited thereto and it may be defined as an n-th degree polynomial. In order to determine a unique curve for the n-th degree polynomial, (n+1) coefficients should be determined as unique values. To this end, in the present disclosure, the x-axis may be coincided with the slope direction of the connection points through coordinate system transformation and the n-th degree polynomial may be calculated by defining the connection point as the origin (0, 0), to detect the midpoint of the curve. Meanwhile, according to an example, when it is impossible or complicated to express a function on the x, y coordinate system, coordinate data positioned in the center of the target segment may be detected as a midpoint. The processor may directly calculate 230 control points based on the detected midpoint. To this end, the midpoint detected in the process 220 described above and the slope of the connection point of the target segment may be used as parameters. For example, any control points x, y may be expressed as functions x(p) and y(p) of the interpolation parameter P, and the coefficients of x(p) and y(p) may be determined by using the midpoint and the connection point. The detailed process of calculating the functions x(p) and y(p) of the interpolation parameter P by using the midpoint and the slope of the connection point will be described in more detail below with reference to FIGS. 5 and 6.

(30) The processor may generate 240 a parametric B?zier curve by using the calculated control points. In an example, a verification process of calculating an error between the generated parametric B?zier curve and the curve of the actual road may be additionally performed. As a result of the verification, when the error is out of the reference range, segments may be additionally divided, and generating parametric B?zier curve for the divided sub-segments may be repeated. The process for this is illustrated in FIG. 3.

(31) FIG. 3 is a flowchart provided to explain a method for reducing an error of the parametric B?zier curve generated in FIG. 2. Referring to FIG. 3, the processor calculates 310 an error between the generated parametric B?zier curve and the coordinate data of the road. Then, the processor monitors 320 whether or not the calculated error exceeds a preset error range. In an example, the preset error range may be about 10 cm. When the calculated error exceeds the preset error range, it is set 330 by the processor such that the section of the road, that is, the segment section of the road is divided. In addition, although not illustrated, the processes for generating the parametric B?zier curve described above with reference to FIG. 2 are respectively performed with respect to the divided segments (e.g., first and second sub-segments). In other words, when performing the process of setting the boundary condition for the first sub-segment, generating the polynomial, detecting the midpoint, calculating the control points, and generating the parametric B?zier curve, the process of setting the boundary condition for the second sub-segment, generating the polynomial, detecting the midpoint, calculating the control points, and generating the parametric B?zier curve are performed simultaneously or sequentially. Next, the processor returns to process 320 to check the error range for the divided segment section. The processor repeatedly executes the processes described above until the divided segment section satisfies an error range within the preset error range. Meanwhile, when the calculated error is within the preset error range, the execution of the method for reducing an error is terminated.

(32) FIG. 4 is an exemplary graph modeling a B?zier curve from the coordinate data of a road according to an embodiment of the present disclosure. Specifically, FIG. 4 is a modeling of a B?zier curve from the coordinate data included in a target segment to generate a B?zier curve among a plurality of segments that can be acquired by dividing a path of a road, and describes, for example, a B?zier curve modeling for the target segment N among the plurality of segments ( . . . , N?1, N, N+1, . . . ). The boundary condition X.sub.M for the target segment N may be represented by n coordinate data having two dimensions (x, y) as values as follows.
X.sub.M={(x.sub.1,y.sub.1),(x.sub.2,y.sub.2), . . . ,(x.sub.m,y.sub.m)}[Equation 2]

(33) In order to determine the boundary condition X.sub.M for the target segment N, coordinate data included in the preceding segment N?1 and the next segment N+1 of the target segment N may be used. In an example, in order to set the boundary condition, the coordinate data, from_point=(x.sub.0, y.sub.0), of the segment N?1 preceding the first connection point (x.sub.1, y.sub.1) of the target segment N, and the coordinate data, to_point=(x.sub.n+1, y.sub.n+1), of the segment N+1 following the second connection point (x.sub.n, y.sub.n) of the target segment N may be used. Here, the first connection point (x.sub.1, y.sub.1) is a start point of the coordinate data forming the target segment N, and the second connection point (x.sub.n, y.sub.n) is an end point of the coordinate data forming the target segment N. However, examples are not limited thereto, and in another example, the boundary condition for the target segment N may be calculated by using other coordinate data forming the preceding segment N?1 and other coordinate data forming the next segment N+1, instead of from_point=(x.sub.0, y.sub.0) and to_point=(x.sub.n+1, y.sub.n+1). In addition, in order to set the boundary condition for the target segment N, three or more coordinate data, for example, two coordinate data in each of the preceding segment N?1 and the next segment N+1 may also be used. In an example, since this additional coordinate data is used also for calculating the boundary condition for the target segment, the coordinate data close to the boundary points of the target segment N should be selected, respectively.

(34) Referring to FIG. 4, in order to set the boundary condition for the target segment N, last coordinate data 411 of the preceding segment N?1 and first coordinate data 413 of the next segment N+1 are used. In this way, in addition to the connection points forming the target segment N, by setting a boundary condition with some coordinate data forming the preceding segment N?1 and the next segment N+1 of the target segment N, the boundaries between segments are more flexibly connected. Accordingly, it is possible to prevent an abrupt path change of the autonomous vehicle driving on a road corresponding to the segment boundary.

(35) For example, the slope value b(x.sub.0) of the first connection point (x.sub.1, y.sub.1) of the target segment N and the slope value b(x.sub.n) of the second connection point (x.sub.n, y.sub.n) of the target segment N may be expressed by Equation 3 below.

(36) $\begin{array}{cc}{b}^{}\left(x_0\right)=\frac{y_0-y_2}{x_0-x_2},b^{}\left(x_n\right)=\frac{y_n-y_{n+2}}{n-x_{n+2}}& \left[\mathrm{Equation}3\right]\end{array}$

(37) By calculating the boundary condition for the target segment N using the connection points between the divided segments described above, more flexible modeling of the B?zier curve is enabled. In the present disclosure, since the value of the boundary condition for the target segment N is still calculated as the same value in the boundary condition in the next segment N+1 of the target segment (the preceding segment N?1 of the target segment N is also the same), the connection between the front and rear segments is flexibly formed.

(38) If the boundary condition for the target segment N is calculated, the midpoint of the B?zier curve is now detected, and based on this, control points for generating a parametric B?zier curve according to the present disclosure is directly calculated.

(39) FIGS. 5 and 6 are exemplary graphs illustrating a method for generating a parametric B?zier curve by calculating the control points after setting the boundary condition for the target segment in FIG. 4.

(40) According to the smoothing in calculating the boundary condition described above, the coordinate system rotation may be performed using, as the X-axis, a straight line connecting the last coordinate data 411 of the preceding segment N?1 and the second coordinate data 412 of the target segment N. Accordingly, the coordinate-transformed graph (or coordinate-transformed coordinate data) as illustrated in FIG. 5 is acquired.

(41) Meanwhile, in FIG. 4, although it appears that the coordinate data forming the target segment N and the coordinate data 411 and 413 of the front and rear segments N?1 and N+1 form a single straight line, when the coordinates are transformed through the process described above, it can be seen that error is included between the coordinate data as shown in the Y axis of FIG. 5. Specifically, in FIG. 5, it can be seen that only the Y-axes of some coordinate data 411 and 412, which are the basis of rotation, are coincided, while the rest includes an error range within 0.4. Hereinafter, a method for reducing the error of the transformed coordinate data will be described.

(42) In order to reduce the error of the transformed coordinate data, in the present disclosure, rather than using the coordinate data in place of the control points, this is directly calculated and obtained. To this end, it is necessary to acquire the midpoint of the B?zier curve together with the slope (b(x.sub.0), b(x.sub.n)) values of the connection points of the target segment N.

(43) There are mainly two methods that may be applied as a method for detecting the midpoint of the B?zier curve.

(44) In an example, the first method for detecting midpoint is a method of using, as a midpoint, a positional center point among a plurality of coordinate data forming the target segment N. This may be applicable when the expression of the polynomial function on the x, y coordinate system is impossible or complicated, as illustrated in FIG. 7.

(45) In another example, the second method for detecting midpoint is a method of calculating the midpoint of the curve by using the slope (b(x.sub.0), b(x.sub.n)) values and coordinate values b(x.sub.0)=y.sub.0, b(x.sub.n)=y.sub.n of the connection points of the target segment N to determine the unique curve in a third-degree or higher polynomial. The second method for detecting midpoint may be applicable to all cases except for when there is a small amount of coordinate data forming the target segment N or it is impossible to express a polynomial function on the x, y coordinate system as illustrated in FIG. 7.

(46) The second method for detecting midpoint generally assumes that a unique curve for the section can be determined through the k?2, ?0-th order differentiation of the start point and the end point in the k-th degree polynomial. In general, in the case of n-th degree polynomial, since its coefficients are n+1, the coefficients of unique values can be determined when there are n+1 conditions for the n-th degree polynomial. In Equation 4 below, since b(x) is a third degree polynomial, four coefficients, that is, a, b, d, and c are required.
b(x)=a+bx+cx.sup.2+dx.sup.3[Equation 4]

(47) In an example, the unique values of the coefficients a, b, d, and c may be calculated by using the slope values b(x.sub.0), b(x.sub.n) described above and the coordinate values b(x.sub.0)=y.sub.0, b(x.sub.n)=y.sub.n as the conditions. Accordingly, the coefficients a, b, d, and c may be defined as follows.

(48) $\begin{array}{cc}a=y_0,b=b^{}\left(x_0\right),d=\left(\frac{b^{}\left(x_n\right)-b+\frac{2\left(-y_n+a+b*x_n\right)}{x_0}}{x_n^2}\right),c=\frac{y_n-{\mathrm{dx}}_n^3-\left(a+{\mathrm{bx}}_n\right)}{x_n^2}& \left[\mathrm{Equation}5\right]\end{array}$

(49) Then, for convenience of calculation, by coinciding the x-axis with the slope b(x.sub.0) direction through the coordinate system transformation described above, and having the connection point as the origin (0, 0), the above can be rewritten as:

(50) $\begin{array}{cc}a=0,b=0,c=\frac{y_n-{\mathrm{dx}}_n^3}{x_n^2},d=\frac{b^{}\left(x_n\right)x_n-2y_n}{x_n^3}& \left[\mathrm{Equation}6\right]\end{array}$

(51) Through the calculation described above, the midpoint (x.sub.m, y.sub.m) of the B?zier curve can be acquired. In an example, in order to calculate the midpoint (x.sub.m, y.sub.m) of the curve by using the polynomial, a point corresponding to a half the total length of the curve may be used. For example, the midpoint Pc of a B?zier curve 610 illustrated in FIG. 6 was detected by using the second method for detecting midpoint described above.

(52) If the midpoint is detected as described above, control points for generating a parametric B?zier curve according to the present disclosure is directly calculated based on the detected midpoint. Referring again to FIG. 1 to further explain this concept, it can be seen that the slopes of the start point P.sub.1 and the end point P.sub.4, that is, the boundary points of the B?zier curve shown in FIG. 1(b) are the same as the slopes of the control points P.sub.2 and P.sub.3, respectively. In addition, using the process of dividing the B?zier curve into two sections, it is possible to calculate the control points from the midpoint of the curve. In other words, when the midpoint of the curve and the slope of the boundary points are known, the control points may be calculated directly.

(53) Specifically, in FIG. 6, a plurality of straight lines may be built by using two connection points P.sub.0 and P.sub.3 of the target segment N and their respective slopes b, and two arbitrary points positioned on each of the plurality of straight lines may be set as the control points. In an example, the two arbitrary points will be referred to as P.sub.1 and P.sub.2 for convenience of description. Then, the two arbitrary points can be expressed as Equation 3 below.
P.sub.1(t)=P.sub.0+t{right arrow over (a)},P.sub.2=P.sub.2+t{right arrow over (b)}[Equation 7]

(54) Meanwhile, in the present disclosure, since the B?zier curve is represented by using the interpolation parameter P, each of the control points x and y can be expressed as a function of p as follows.
x(p)=a.sub.x|b.sub.xp|c.sub.xp.sup.2|d.sub.xp.sup.3,y(p)=a.sub.y|b.sub.yp|c.sub.yp.sup.2|d.sub.yp.sup.3[Equation 8]

(55) In an example, since Equation 8 is a third degree polynomial, a total of four values should be determined as the control points for obtaining a solution. In Equation 7, since the slopes {right arrow over (a)},{right arrow over (b)} can be expressed as b(x.sub.0),b(x.sub.n), respectively, and the coordinates of the midpoint are (x.sub.m, y.sub.m), Equation 8 can be expressed as the coordinate system using Equation 7, and expressed as Equation 9 as follows.

(56) $\begin{array}{cc}{x}_{c,1}=\frac{8\left(y_m-b^{}\left(x_0\right)x_n\right)+x_n\left(b^{}\left(x_0\right)+3b^{}\left(x_n\right)\right)-4y_n}{3\left(b^{}\left(x_n\right)-b^{}\left(x_0\right)\right)},y_{c,1}=b^{}\left(x_n\right)\left(x_{c,1}-x_n\right)+y_n,x_{c,2}=\frac{8x_m-3x_{c,1}-x_n}{3},y_{c,2}=b^{}\left(x_0\right)x_{c,2}& \left[\mathrm{Equation}9\right]\end{array}$

(57) If the control points x.sub.c,1,y.sub.c,1,x.sub.c,2,y.sub.c,2 are calculated in this way, it is now possible to generate a parametric B?zier curve for the target segment N using x.sub.c,1,y.sub.c,1,x.sub.c,2,y.sub.c,2. Here, since the directly calculated control points are not one of the coordinate data forming the target segment N, even when there is an error in some of the coordinate data forming the target segment N, a curve closer to the actual road may be generated regardless of the error.

(58) FIG. 7 is an exemplary graph illustrating a parametric B?zier curve calculated by a plurality of coordinate points according to an embodiment of the present disclosure.

(59) FIG. 7 illustrates the effect of a parametric expression of a B?zier curve generated through the process of segment boundary setting, coordinate system transformation, midpoint detection, and direct calculation of control points described above with reference to FIGS. 4 to 6. It is exemplified that the illustrated parametric B?zier curve is flexible, and in FIG. 6, the four control points are calculated to determine a unique curve for the third degree polynomial, but examples are not limited thereto. Therefore, it is possible to increase the number of control points to 5, 6, 7, and so on, and generate parametric B?zier curves for 4th degree polynomials, 5th degree polynomials, 6th degree polynomials, and so on. However, in general, the increased degree of the function means proportionally increased computational complexity and unnecessary curvature, and therefore, the present disclosure is explained using the third degree polynomial and four control points.

(60) FIGS. 8 and 9 are exemplary graphs provided to explain generating a curve with respect to the segment of FIG. 4 by using the method for generating road topology information according to an embodiment of the present disclosure, in comparison with the related method.

(61) Specifically, FIGS. 8 and 9 illustrate examples of directly applying some of the coordinate data forming the road segments as the control points for generating a B?zier curve. As an example, the B?zier curve generated by the method for generating road topology information disclosed in KR10-2017-0068021 introduced in the Background Art section is illustrated. In an example, a B?zier curve was generated as a 7th degree polynomial by using eight of the coordinate data included in the segment N as the control points.

(62) It can be seen that a curve 810 illustrated in FIG. 8 has an unnecessary curvature change in the middle, as compared with the parametric B?zier curve according to the present disclosure illustrated in FIG. 6. This is because errors that may occur during the initial measurement of the coordinate data forming the segments are included as they are. Accordingly, the flexible B?zier curve 610 as illustrated in FIG. 6 cannot be generated, but the curve 810 having many changes in curvature is generated. If the autonomous vehicle travels along the curve 810 illustrated in FIG. 8, the driving direction will be changed unnecessarily and frequently, and the driving time will also increase. In addition, it can be seen that the curve 910 illustrated in FIG. 9 has an abrupt slope change at the boundary point connected to the next segment N+1. This is a type of B?zier curve that is generated when specific coordinate data 911 forming the target segment N includes a large error. It is predictable that this type of curve 911 would also generate the abrupt curvature change when connected to a curve (not illustrated) generated in the next segment N+1. This is because the coordinate data of the current segment N?1 is not used when calculating the boundary condition for the next segment N+1. When it is assumed that the autonomous vehicle travels along the curve 910 shown in FIG. 9 as it is, it may be difficult to find the next segment N+1 of the road (the head of the autonomous vehicle is directed towards the y-axis), making it difficult to navigate. In addition, even if the next segment N+1 of the road is found, a sudden change in the driving direction is expected, which makes the driving rough.

(63) Next, FIG. 10 is an exemplary block diagram illustrating an internal configuration of an information processing system 1010 for executing a method for generating road topology information according to an embodiment of the present disclosure.

(64) FIG. 10 is a block diagram of an example computing device 1010 that may optionally be used to perform one or more aspects of the techniques described herein. In some implementations, one or more of the client computing device, user-controlled resource module, and/or other component(s) may include one or more components of the example computing device 1010.

(65) The computing device 1010 may generally include at least one processor 1014 in communication with a number of peripheral devices via a bus system 1012. This peripheral devices include a storage system 1024 including a memory 1025 and a file storage 1026, a user interface output device 1020, a user interface input device 1022, and a network interface system 1016, for example. The user interface input and output devices 1020 and 1022 allow user interaction with the computing device 1010. The network interface system 1016 provides an interface to an external network and is connected to a corresponding interface device of another computing device.

(66) The user interface input device 1022 may include a keyboard, a mouse, a trackball, a pointing device such as a touchpad or a graphics tablet, a scanner, a touch screen integrated into a display unit, an audio input device such as a voice recognition system, a microphone, and/or any other type of input devices. In general, use of the term input device is intended to include all possible types of devices and methods of entering information into the computing device 1010 or a communications network.

(67) The user interface output device 1020 may include a non-visual display, such as a display subsystem, a printer, a fax machine, or an audio output device. The display subsystem may include a cathode ray tube (CRT), a flat panel device such as a liquid crystal display (LCD), a projection device, or other mechanism for generating a visible image. The display subsystem may also provide a non-visual display via an audio output device. In general, use of the term output device is intended to include all possible types of devices and methods of outputting information from the computing device 1010 to a user or other appliance or computing device.

(68) The storage system 1024 stores programming and data structures that provide the functionality of some or all of the modules described above. For example, the storage system 1024 may include logic for not only performing the selected aspects of the methods of FIGS. 2 to 3 above, but also implementing the various methods, operations, configurations, and functions depicted with reference to FIGS. 4 to 6.

(69) Such software modules may generally be executed by the processor 1014 alone or executed in combination with other processors. The memory 1025 used in the storage system 1024 may include a number of memories including a main random access memory (RAM) 1030 for storing instructions and data during program execution, and a read-only memory (ROM) 1032 in which fixed instructions are stored. The file storage 1026 may provide permanent storage for programs and data files, and may include a hard disk drive, removable media associated with a floppy disk drive, a CD-ROM drive, an optical drive, or a removable media cartridge. Modules implementing specific implementation functions may be stored by the file storage 1026 of the storage system 1024, or stored in other devices accessible by the processor 1014.

(70) The bus system 1012 provides a mechanism that enables a communication between various components and subsystems of the computing device 1010. In FIG. 10, although the bus system 1012 is schematically illustrated as a single bus, alternative implementations of the bus system may use multiple buses.

(71) The computing device 1010 may include various types, including workstations, servers, computing clusters, blade servers, server farms, or any other data processing system or computing device. In addition, due to the ever-changing nature of computers and networks, the description of the computing device 1010 illustrated in FIG. 10 is intended only as a specific example to illustrate certain implementations. Therefore, many other configurations of the computing device 1010 may have more or fewer components than the computing device illustrated in FIG. 10.

(72) Furthermore, the method described above may be provided as a non-transitory computer-readable recording medium in which a program (or instructions) for execution in a computer is stored. The medium may be a type of medium that continuously stores a program executable by a computer, or temporarily stores the program for execution or download. In addition, the medium may be a variety of recording means or storage means having a single piece of hardware or a combination of several pieces of hardware, and is not limited to a medium that is directly connected to any computer system, and accordingly, may be present on a network in a distributed manner. An example of the medium includes a medium configured to store program instructions, including a magnetic medium such as a hard disk, a floppy disk, and a magnetic tape, an optical medium such as a CD-ROM and a DVD, a magnetic-optical medium such as a floptical disk, and a ROM, a RAM, a flash memory, and so on. In addition, other examples of the medium may include an app store that distributes applications, a site that supplies or distributes various software, and a recording medium or a storage medium managed by a server.

(73) The methods, operations, or techniques of this disclosure may be implemented by various means. For example, these techniques may be implemented in hardware, firmware, software, or a combination thereof. Those skilled in the art will further appreciate that various illustrative logical blocks, modules, circuits, and algorithm steps described in connection with the disclosure herein may be implemented in electronic hardware, computer software, or combinations of both. To clearly illustrate this interchangeability of hardware and software, various illustrative components, blocks, modules, circuits, and steps have been described above generally in terms of their functionality. Whether such a function is implemented as hardware or software varies depending on design requirements imposed on the particular application and the overall system. Those skilled in the art may implement the described functions in varying ways for each particular application, but such implementation should not be interpreted as causing a departure from the scope of the present disclosure.

(74) In a hardware implementation, processing units used to perform the techniques may be implemented in one or more ASICs, DSPs, digital signal processing devices (DSPDs), programmable logic devices (PLDs), field programmable gate arrays (FPGAs), processors, controllers, microcontrollers, microprocessors, electronic devices, other electronic units designed to perform the functions described in the disclosure, computer, or a combination thereof.

(75) Accordingly, various example logic blocks, modules, and circuits described in connection with the disclosure may be implemented or performed with general purpose processors, DSPs, ASICs, FPGAs or other programmable logic devices, discrete gate or transistor logic, discrete hardware components, or any combination of those designed to perform the functions described herein. The general purpose processor may be a microprocessor, but in the alternative, the processor may be any related processor, controller, microcontroller, or state machine. The processor may also be implemented as a combination of computing devices, for example, a DSP and microprocessor, a plurality of microprocessors, one or more microprocessors associated with a DSP core, or any other combination of the configurations.

(76) In the implementation using firmware and/or software, the techniques may be implemented with instructions stored on a computer-readable medium, such as random access memory (RAM), read-only memory (ROM), non-volatile random access memory (NVRAM), programmable read-only memory (PROM), erasable programmable read-only memory (EPROM), electrically erasable PROM (EEPROM), flash memory, compact disc (CD), magnetic or optical data storage devices, and the like. The instructions may be executable by one or more processors, and may cause the processor(s) to perform certain aspects of the functions described in the present disclosure.

(77) Although the examples described above have been described as utilizing aspects of the currently disclosed subject matter in one or more standalone computer systems, examples are not limited thereto, and may be implemented in conjunction with any computing environment, such as a network or distributed computing environment. Furthermore, the aspects of the subject matter in the present disclosure may be implemented in multiple processing chips or devices, and storage may be similarly influenced across a plurality of devices. Such devices may include PCs, network servers, and portable devices.

(78) Although the present disclosure has been described in connection with some examples herein, various modifications and changes can be made without departing from the scope of the present disclosure, which can be understood by those skilled in the art to which the present disclosure pertains. In addition, such modifications and changes should be considered within the scope of the claims appended herein.