In many studies, a bounding box specifies spatial locations and classes (e.g., cars and trees). A bounding box is widely used in point cloud data to simplify the complex set of points as a representative box and apply collision detection ^[1]. Among the several types of bounding boxes, the oriented bounding box (OBB) is the smallest rectangle with an inclined axis around the object (Figure 1). In contrast, an axis-aligned bounding box (AABB) is a minimum bounding hexahedron that envelops an object and conforms to a set of fixed orthogonal axes. Owing to its simple geometry, the AABB has less memory and is tested faster (Figure 1). However, describing the directional information of a given object is difficult.

In contrast, a discrete-orientation polytope (DOP) is a bounding polyhedron defined with the k number of axes. DOP can bind the object better than AABB but requires more memory (Figure 1). Comparing these two bounding boxes, the OBB is the optimal bounding box for road marking extraction regarding memory and direction information.

To generate OBBs, it is essential to establish a set of basis axes and u- and v-axes (Figure 1). The u-axis was aligned in the direction of the OBB, which acted as a reference line for defining the OBB, and the v-axis was perpendicular to the u-axis. For the OBBs of the road boundaries, the u-axis can be extracted by identifying the boundary line of the floor plane consisting of points with a normal vector of 90°. Therefore, the u-axis can be determined with the edge of the plane, which defines the OBB of the road boundaries.

A floor plane can be generated by identifying the lowest points in the search area. Applying the search area can decrease the randomness and noise in the point cloud data. In particular, this search step determined the lowest points because the lowest point of the point clouds collected from the MMS represents the road surface. Therefore, defining the proper size and location of the search area is essential in terms of accuracy and conformity to extract the edge because it ends up being a reference line aligned with the u-axis of the OBB. The radius of the search area was set as 50 cm (Figure 2b). If it is set to a radius of 1 m, the road’s curvature is ignored; instead, a straight line is generated (Figure 2a).

The location of the search area is also associated with not only the accurate extraction of the u-axis reference line of the OBB but also the generation of the road surface. Selecting the proper location of the search area can eliminate the need to pre-process the point cloud data. To generate an accurate reference line for the OBB, the search area should be located where the following conditions should be met: first, the boundaries of the road surface are clear, the direction can be confirmed, and the data should be acquired in areas with no lost data. For example, when the position of the search area is such that the boundary is identified, as shown in Figure 3a, the reference line for creating an OBB can be extracted accurately, as shown in Figure 3b.

Moreover, it is essential to encompass both road boundary and road surface within the search area. If the search area is located outside an area not in contact with the road boundary, the edge detection causes errors, as shown in Figure 4a. Moreover, if all the portions of the search area occupied the road surface, they failed to identify the edges (Figure 4b).

The plane fitted to the lowest points is defined by calculating the normal vectors of the points. Each point has a position in the point cloud data (x, y, z). Each point is collected, which together form a group of points to represent the appearance of an object. The higher the density of the point group, the more detailed the shape that can be expressed. Moreover, the point cloud data acquired from ground MMS surveys have an average precision of 2 cm; therefore, points with 2 cm errors along the y-axis were also included to fit the plane. In point cloud data, the edge of the road plane can be extracted by calculating the normal vectors based on the coordinates of each point and fitting the points to a plane. The normal vector is perpendicular to the plane. Assuming that there are three points (P1, P2, and P3) on the plane, the normal vector (N) to the plane can be obtained by calculating the cross product of the two vectors 𝑃2−𝑃1 and 𝑃3−𝑃1 (Figure 5).

The normal vector is calculated with Equation (1) or Equation (2).

An algorithm to calculate a normal vector is described as Algorithm 1.

Algorithm 1: Calculating a normal vector (N)

1 Input: point p1, point p2, point p3 2 Output: normal vector N(x, y, z) 3 vector 𝑢=𝑝0–𝑝1 4 vector 𝑣=𝑝0–𝑝2 5 6 //Calculating a plane to find normal vector 7  vector N = crossProduct(u, v) //perform cross product of two lines on the plane 8 9 If vectorSize(N) > 0 10  m_n = normalize(N) // after normalization, assign it into a new variable m_n 11 12 𝑚_𝑑=𝑚_𝑛∗𝐴 // the distance between the origin point and the plane 13 End 14 15 //Calculating normal vector using orientation values 16 𝑙𝑒𝑛𝑔𝑡ℎ=𝑠𝑞𝑟𝑡(𝑥∗𝑥+𝑦∗𝑦+𝑧∗𝑧) 17 𝑥=𝑥/𝑙𝑒𝑛𝑔𝑡ℎ 18 𝑦=𝑦/𝑙𝑒𝑛𝑔𝑡ℎ 19 𝑧=𝑧/𝑙𝑒𝑛𝑔𝑡ℎ

As mentioned above, the normal vectors of the points were calculated (Figure 6a), and points whose normal vectors were nearly 90° (approximately over 85°) were fitted to a plane by applying the k-NN clustering algorithm (Figure 6b). The boundary line is formed by connecting the edge’s endpoints where the plane from the points ends. The points on the edge of the plane were connected, creating a reference line aligned with the u-axis of the OBB (Figure 6c). This method applied the width of the OBB, which was aligned with the v-axis up to 50 cm. When the radius of the search area is 50 cm, the length of the edge can be generated to be utile 1 m. However, to create a rectangular OBB for directionality, the researchers applied an OBB width of up to 50 cm.

The point cloud data store the intensity and position values. In the point cloud data, the intensity values are stored as a short (unsigned short) type, and the value ranges from 0 to 255, where the higher the number, the higher the reflection rate. Linear road markings, which are edge and lane markings, are more likely to have a higher intensity than the surrounding environment because of the glass beads. Therefore, using intensity values, this study classifies linear road markings from point cloud data.

A range of intensity values must be established to distinguish between linear road markings. However, the intensity values are distributed depending on the measurement environment, such as weather, sunlight, and shadows. This means the intensity distribution can differ for each measurement even if the same area is resurveyed. Therefore, the intensity corresponding to linear road markings should be checked and set to include its value. After setting the range of intensity values that classified the linear road markings and road surfaces, the points of the extracted linear road markings were combined to determine the fitted plane (Figure 7).

Similar to the generation of the OBB of the road boundaries in the previous section, the points included in the search area are selected first. Subsequently, a reference line to generate the OBB of linear road markings was determined by connecting the endpoints of the point group included in the intensity value range. The centerline of the corresponding road markings was set as a reference line aligned with the u-axis of the OBB, and the width was defined as the width of the extracted linear road markings, which was 20 cm (Figure 8a). The search area, including the road marking areas, must be located to generate the OBB (Figure 8b). Even if the search area included the marking area, linear road markings with intensity values outside the set range cannot be detected, as shown in Figure 8c. None of the markings are identified if the search area excludes the marking area (Figure 8d).

Using the generated OBBs for the road boundaries and linear road markings, linear data can be automatically extracted by setting a search radius based on these data. The OBB collision-detection algorithm is used to extract the linear data automatically. The OBB collision-detection algorithm operates based on the separating axis theorem (SAT), in which polygons are projected onto one axis and recognized as colliding objects when the projection sections overlap. In this study, the OBB was a rectangle parallel to the road-driving direction.

If an OBB rectangle is created, the OBB collision-detection algorithm connects the centerline of the conflicting OBB to build linear data based on the object. The separation axis of the figure used for applying the OBB collision-detection algorithm should apply a normal vector from the reference axis. In this study, the direction of the road was defined as the reference axis for extracting the road boundaries and lanes. If the road direction was set to that of the separation axis, the following process calculated the collision. The normal vector of the reference axis was used to check for collisions (Zhang et al. (2019) ^[2]), as shown in Figure 9: if the distance between the center point of 𝑂𝐵𝐵 𝐴 and that of 𝑂𝐵𝐵 𝐵 is defined as 𝑇, 𝑇 is a vector with directionality. The value projected from the vector with directionality becomes 𝑇·𝐿 (Figure 9). In addition, if the sum of the length of 𝑃𝐴 projecting the longest point from the center point of 𝐴 to the direction of 𝐵 and the length of 𝑃𝐵 projecting the long point from the center point of 𝐵 to the direction of A is greater than 𝑇·𝐿, a collision has occurred (Figure 9).

The collision calculation method of the separation axis theory is defined in Equations (3)–(5):

To automatically extract the linear data, the reference data to which the first acquired OBB is applied are used to check whether a line connects forward and backward. The search method obtains the range’s start- and endpoint groups by applying a search interval. Because the road may not be horizontal, an OBB was generated by applying a height equal to the search width. Subsequently, the OBB was generated at a position corresponding to the forward and backward intervals. The OBB is connected to the corresponding OBB and reference data to connect the lines (Figure 10).

The pseudocode for the OBB collision-detection algorithm is as follows (Algorithm 2).

Algorithm 2: Overlapped OBB collision detection algorithm

1 function OverlapOBB (OBB 𝐴,OBB 𝐵,normal Vector ): 2     for(𝑖 = 0; 𝑖 < 𝐴.𝐴𝑙𝑙𝑁𝑜𝑑𝑒𝑠; 𝑖++): 3        𝑡= 𝐴.𝑉.𝑁𝑜𝑑𝑒[𝑖] 4        𝑑𝑀𝑖𝑛 = t 5         𝑑𝑀𝑎𝑥 = t 6        // calculate the length between nodes 7        for (c = 1; c < 𝐴.𝑉.𝑁𝑜𝑑𝑒𝑠[𝑖]; c++): 8            𝑡 = (𝑡 + 𝐴.𝑉.𝑁𝑜𝑑𝑒𝑠[𝑖]) / 2 9            if (𝑡<𝑑𝑀𝑖𝑛): 10              𝑑𝑀𝑖𝑛=𝑡 11            elseif (𝑡>𝑑𝑀𝑎𝑥): 12              𝑑𝑀𝑎𝑥=𝑡 13            // check the length is in the range between dMin and dMax 14        if ((𝑑𝑀𝑖𝑛>𝑡)||(𝑑𝑀𝑎𝑥<𝑡): 15             // The OBBs are not overlapped 16             return false 17        return true

The two elements of the initial settings were search intervals: search length and width. The proper setting of search intervals is essential because the proposed automatic extraction method can be applied to straight and curved roads. Therefore, the search length and width are the parameters of this method based on the conditions of the applied site, which should be applied differently depending on the shape of the road. For example, highly accurate linear data can be extracted from straight roads by increasing the search length and applying a narrow search width. The search length should be shortened for curved roads, and a wide search width should be applied. The procedure for generating linear data by applying the OBB collision-detection algorithm is shown in Figure 11.

𝑂𝐵𝐵 𝐴 generated as reference data was moved using a search length based on the road direction to generate 𝑂𝐵𝐵𝐴′ in the corresponding direction. The normal vector is then obtained from the direction of 𝑂𝐵𝐵 𝐴′, and the point at which the normal vector meets the direction of the road is obtained. After that, the normal vector is calculated at the corresponding point, and 𝑂𝐵𝐵 𝐵 is generated based on the road direction and normal vector. Subsequently, 𝑂𝐵𝐵 𝐴′ and 𝑂𝐵𝐵 𝐵 were inspected for collisions using the OBB collision-detection algorithm (Figure 12a). Collision detection was performed in the above order. When a collision was detected, linear data were generated by connecting the center points of 𝑂𝐵𝐵 𝐴 and 𝑂𝐵𝐵 𝐵 (Figure 12b).