JP7453586B2 - Merge area detection method, merge area detection device and program - Google Patents

Description

The present invention relates to a merge area detection method, a merge area detection device, and a program.

It is predicted that opportunities to acquire point cloud data in space will increase in the future using devices such as fixed LiDAR (Light Detection and Ranging), vehicle-mounted LiDAR, drone-mounted LiDAR, and MMS (Mobile Mapping System). Due to this increase in opportunities, the amount and number of point cloud data to be stored will also increase. Point cloud data is often encoded when the data is stored. Therefore, for example, G-PCC (Geometry based Point Cloud Compression) is used to encode point cloud data (see, for example, Non-Patent Document 1).

Point cloud data is a set of points acquired for a certain subspace in a continuous real space. Therefore, point cloud data has boundaries in space. When using point cloud data, it is not always necessary to handle the data only in the acquired units. For example, a plurality of spatially continuous point cloud data may be merged. When performing this merging, it is necessary to decode the encoded point cloud data once. Note that the explanation here assumes that there is no coordinate shift between the data to be merged.

"Information technology - MPEG-I (Coded Representation of Immersive Media) - Part 9: Geometry-based Point Cloud Compression", ISO/IEC DIS 23090-9, 2019.

A possible method for automatically merging point cloud data is to add all the point groups represented by two point cloud data without worrying about the coordinates of the point clouds in space. However, in general, point cloud data is not acquired neatly divided into adjacent subspaces. In other words, there is a possibility that both point groups exist within the same area. In the following, a region where such point clouds of two point cloud data exist will be referred to as a "region where the point clouds overlap."

Two point cloud data to be merged may be acquired at different times. Furthermore, while the point cloud data was acquired, the state of the structure within the region where the point clouds overlap may have changed. Examples include when a new building is built, or when the car that was parked last time is no longer there. Even though the situation of the structure is changing in this way, if all the point clouds are added together, it is considered difficult to accurately grasp the state of the space.

Of the two point cloud data to be merged, which one is the prioritized point cloud data (hereinafter referred to as "updated data") and which is the non-prioritized point cloud data (hereinafter referred to as "old data"). In some cases, it has already been decided whether there is one or not. In that case, it is considered possible to create point cloud data that accurately represents the state of the space by merging the areas where the point clouds overlap, leaving only the updated data without using the old data.

On the other hand, point cloud data is basically measured using reflected waves from a laser at a certain position. Therefore, the range of the acquired point clouds varies. In order to clearly divide these regions, it is generally necessary to use manual methods or detailed point cloud analysis methods. These processes are performed while checking the structures represented by the point cloud, so there is a possibility that the merge can be performed accurately. However, since the processing is time-consuming, it is expected that human costs and time costs will increase.

In view of the above circumstances, an object of the present invention is to provide a merge area detection method, a merge area detection device, and a program that can determine an area when merging point cloud data that overlap in the target space. .

One aspect of the present invention is that first point cloud data including information on the position of each point in a part of a predetermined space is divided into tree-structured regions having a plurality of hierarchies. an acquisition step of acquiring tree-structured data represented by information on the presence or absence of points in each region; and a step of acquiring the first point group in the predetermined space based on the highest hierarchy in which points exist in the hierarchy of the tree-structured data. a boundary determining step of determining a merging boundary, which is a boundary when merging the data and second point cloud data including information on each point in at least a part of the predetermined space, in units of the area; A merge region detection method has the following steps.

One aspect of the present invention is that first point cloud data including information on the position of each point in a part of a predetermined space is divided into tree-structured regions having a plurality of hierarchies. an acquisition unit that acquires tree structure data represented by information on the presence or absence of points in each region; and an acquisition unit that acquires the first point group in the predetermined space based on the highest layer in which points exist in the hierarchy of the tree structure data. a boundary determining unit that determines a merging boundary, which is a boundary when merging the data and second point cloud data including information on each point in at least a part of the predetermined space, in units of the area; A merge area detection device includes:

One aspect of the present invention is a program for causing a computer to execute the above-described merge area detection method.

According to the present invention, it is possible to define an area for merging point cloud data that overlap in the target space.

FIG. 1 is a block diagram showing the configuration of a merge area detection device according to a first embodiment. It is a figure which shows the parent block and child block of spatial area division used for the same embodiment. FIG. 3 is a diagram showing division of a spatial region including point cloud data used in the same embodiment. FIG. 3 is a diagram showing an example of an 8-ary tree used in the embodiment. FIG. 3 is a flow diagram showing the operation of the merge area detection device in the same embodiment. FIG. 3 is a flow diagram showing the operation of the merge area detection device in the same embodiment. FIG. 3 is a diagram for explaining the operation of the merge area detection device in the same embodiment. FIG. 3 is a diagram for explaining the operation of the merge area detection device in the same embodiment. FIG. 3 is a diagram for explaining the operation of the merge area detection device in the same embodiment. FIG. 3 is a diagram for explaining the operation of the merge area detection device in the same embodiment. FIG. 3 is a flow diagram showing the operation of the merge area detection device in the same embodiment. FIG. 3 is a diagram for explaining the operation of the merge area detection device in the same embodiment. FIG. 2 is a block diagram showing the configuration of a merge area detection device according to a second embodiment. FIG. 7 is a diagram for explaining conversion from 8-branch tree data to quadruple-tree data in the same embodiment. FIG. 6 is a diagram for explaining the generation of tree structure data using the coordinates of points projected onto a two-dimensional plane in the same embodiment. FIG. 3 is a flow diagram showing the operation of the merge area detection device in the same embodiment. FIG. 2 is a diagram showing a hardware configuration of a merge area detection device in first and second embodiments.

Embodiments of the present invention will be described in detail below with reference to the drawings. In this embodiment, a region is determined in which point cloud data of old data and point cloud data of updated data are to be merged without using manual or detailed analysis methods. This area is an area where old data is replaced with updated data, or an area where old data is combined with updated data. In this embodiment, regions to be merged can be determined at high speed by using tree structure data in which point cloud data is expressed in a tree structure such as an 8-ary tree.

(First embodiment)
FIG. 1 is a block diagram showing the configuration of a merge area detection device 1 according to the first embodiment. The merge area detection device 1 includes a storage section 11 , an input section 12 , a division section 13 , a conversion section 14 , a replacement section 15 , a boundary determination section 16 , and a merging section 17 .

The storage unit 11 stores point cloud data of old data and point cloud data of updated data. The point cloud data includes data of a set of coordinate values where points exist in a spatial domain. The coordinate values of the points included in the old data and the coordinate values of the points included in the updated data are values in the same coordinate space. The spatial area of the old data and the spatial area of the updated data partially overlap.

The input unit 12 inputs data. Input may be receiving data from other devices or reading data from other devices or recording media. Further, the input may include inputting data using an existing input device such as a keyboard or a touch panel. The input unit 12 inputs old data and updated data, and writes these input data into the storage unit 11.

The dividing unit 13 divides the old data spatial area and the updated data spatial area into divided areas, respectively. A divided area is a unit for converting point cloud data into tree structure data. The tree structure data is data in which a divided space including points in a spatial region from which a set of points indicated by the point cloud data is obtained is expressed in an 8-ary tree structure. A common dividing area is used for dividing old data and dividing updated data.

The conversion unit 14 converts the point group indicated by the old data into tree structure data for each divided area. The conversion unit 14 adds header information indicating the size and position of the divided area to the converted tree structure data. Similarly, the conversion unit 14 converts the point group indicated by the update data into tree structure data for each divided area, and adds header information indicating the size and position of the divided area to the converted tree structure data. Thereby, the old data and the updated data can be represented by tree structure data for each common divided area, regardless of the spatial area of the old data and the spatial area of the updated data.

The replacement unit 15 replaces an area of the old data corresponding to the real space represented by the updated data with the updated data. Alternatively, the replacement unit 15 replaces a divided area in which no updated data exists with a divided area of old data in the updated data.

The boundary determining unit 16 determines a merge boundary for a divided area that includes a space where the point clouds of old data and updated data overlap. The merge boundary is a boundary where old data is replaced with updated data or a boundary where old data is added to updated data. The merging unit 17 merges the point cloud data of the old data and the point cloud data of the updated data in the divided area according to the merging boundary determined by the boundary determining unit 16.

Tree structure data of point cloud data will be explained using FIGS. 2 to 4. In this embodiment, the coordinate value of each point included in the point cloud data is represented by the value of each component in the xyz coordinates, that is, the x coordinate value, the y coordinate value, and the z coordinate value.

FIG. 2 is a diagram showing parent blocks and child blocks used for spatial region division when generating tree-structured data. By dividing the parent block B, which is a cubic space, into two equal parts in each of the three mutually orthogonal directions (x-axis, y-axis, z-axis), eight cubic child blocks B-0 ~ B-7 is generated.

FIG. 3 is a diagram showing the division of a spatial region to generate tree-structured data. Block B0 is a cube with 2 ⁿ sides. Block B0 corresponds to a divided region used when the dividing unit 13 divides the spatial region of old data and the spatial region of updated data. To simplify calculation processing, the coordinate values of the point cloud data are converted to coordinate values of a relative coordinate system. Specifically, the coordinates of the point group data are translated in such a way that the minimum value of each component of x, y, and z becomes 0. As a result, the coordinates of one vertex of block B0 become (0, 0, 0). Each side of block B0, x=2 ⁿ , y=2 ⁿ , z=2 ⁿ , does not include a point. n takes a positive integer. n may be determined based on the size of the point group to be encoded.

When the spatial region division shown in FIG. 2 is performed using block B0 as a parent block, eight child blocks, blocks B1-0 to B1-7, are generated. Next, among blocks B1-0 to B1-7, block B1-i (i is an integer from 0 to 7) containing one or more points is used as a parent block to perform spatial region division as shown in FIG. Eight child blocks, blocks B2-i-0 to B2-i-7, are generated. No division is performed for block B1-i that does not include any points.

Among blocks B2-i-0 to B2-i-7, the spatial region division shown in FIG. It will be done. As a result, blocks B3-ij-0 to B3-ij-7, which are eight child blocks, are generated. Furthermore, the process of performing spatial region division using a child block containing one or more points as a parent block is repeated a predetermined number of times. Note that a child block generated by the m-th division (m is an integer of 1 or more) is referred to as an m-th layer block.

FIG. 4 is a diagram showing an example of an 8-ary tree. The point cloud data is expressed by an octree corresponding to the divided three-dimensional space as shown in FIG. The highest node N0 corresponds to block B0. Node N0 is connected to eight nodes N1-0 to N1-7 on the first layer. Node N1-i corresponds to block B1-i. A node corresponding to a block including points will be described as a node including points, and a node corresponding to a block not including points will be described as a node not including points.

Node N1-i including a point is connected to eight nodes N2-i-0 to N2-i-7 on the second layer. Node N2-ij corresponds to block B2-ij. Since a block B1-i that does not include a point is not divided, the node N1-i corresponding to that block B1-i is not connected to a node on the second layer. In FIG. 4, nodes N1-0 to N1-6 that do not include points are not connected to nodes in the second layer. Further, the node N1-7 including the point is connected to the nodes N2-7-0 to N2-7-7 on the second layer. Nodes N2-7-0 and N2-7-2 to N2-7-7 that do not include a point are not connected to the third layer node. The node N2-7-2 including the point is connected to eight nodes N3-7-1-0 to N3-7-1-7 on the third layer.

Tree-structured nodes corresponding to the spatial regions divided as described above are generated from the point cloud data. A node corresponding to a block containing a point is assigned a block value indicating whether or not each child block whose parent block is the block includes a point. In other words, a node corresponding to a block containing a point is given a block value indicating whether each node one layer below the node contains a point. This block value is expressed as in equation (1). x _k is a code indicating whether a point is included in the k-th child block (k is an integer from 0 to 7) among the eight child blocks. "1" indicates that a point is included, and "0" indicates that a point is not included.

For example, if only blocks B1-2 and B1-7 among the child blocks of block B0 include points, the block value of the node corresponding to block B0 is f(0, 0, 1, 0, 0, 0, 0 , 1)=33. Further, when all eight child blocks of a certain block include points, the block value is expressed as f(1, 1, 1, 1, 1, 1, 1, 1)=255. In this way, each node is given a block value representing the position of the point as a value from 0 to 255 using equation (1).

FIG. 5 is a flow diagram showing the processing of the merge area detection device 1. FIG. 5 shows a process for merging updated data with old data. The input unit 12 of the merge area detection device 1 inputs data A and data B (step S110). The storage unit 11 stores input data A and data B. Data A and data B are point cloud data. Data A and data B may be data structured into an 8-branch tree for each divided area. The dividing unit 13 sets data A as old data and sets data B as updated data according to the instruction inputted by the input unit 12.

If the data A and data B are not data that has an 8-ary tree structure for each divided area, the dividing unit 13 divides the old data and the updated data into divided areas, respectively (step S120). The conversion unit 14 converts the data A into tree-structured data that is structured into an 8-ary tree for each divided region. Similarly, the conversion unit 14 converts data B into tree-structured data that is structured into an 8-branch tree for each divided region. The conversion unit 14 adds header information indicating the size, position, etc. of the divided area to the tree structure data of each divided area. The position of the divided area is expressed, for example, by coordinate values in the coordinate system before conversion to the relative coordinate system.

The replacement unit 15 replaces the divided area of the old data corresponding to the real space expressed by the updated data with the divided area of the updated data (step S130). The boundary determination unit 16 sets a divided area that partially or completely overlaps the updated data as a processing target divided area among the divided areas where the old data exists. The boundary determining unit 16 determines a merge boundary for each divided region to be processed. The merging unit 17 merges the updated data with the old data according to the merging boundary determined by the boundary determining unit 16 (step S140).

FIG. 6 is a flow diagram showing the merge boundary determination process of the merge area detection device 1. FIG. 6 shows details of the process of step S140 in FIG. The boundary determination unit 16 performs the process shown in FIG. 6 for each divided area to be processed.

First, the boundary determination unit 16 determines whether update data exists in all divided regions adjacent to the processing target divided region, based on the tree structure data of each divided region of the update data (step S210). The boundary determination unit 16 determines whether update data exists in all the divided regions adjacent to the divided region to be processed, using the size of the divided region and the tree-structured data of the divided region, instead of the tree-structured data. The determination may be made based on header information indicating the location or the like. If the boundary determination unit 16 determines that update data exists in all the divided regions adjacent to the divided region to be processed (step S210: YES), it determines to replace all the divided regions to be processed with updated data. Information on the processing target divided area is notified to the replacement unit 15. The replacement unit 15 replaces all the processing target divided regions of the update data with the update data of the processing target divided regions (step S220).

If the boundary determination unit 16 determines that there is a divided region adjacent to the processing target divided region that has no update data (step S210: NO), it performs the process of step S230. The boundary determining unit 16 acquires information on the hierarchy set by the user (step S230). The hierarchy set by the user is the hierarchy that is the target of the process of determining the update target area. This hierarchy corresponds to the tree structure hierarchy shown in FIG. The boundary determination unit 16 may read the hierarchy information from the storage unit 11 or may acquire the hierarchy information input by the input unit 12. It is assumed that the hierarchy set by the user is from hierarchy N1 (N1 is an integer of 1 or more) to hierarchy N2 (N2 is an integer of N1 or more).

The boundary determining unit 16 sets the processing target layer n to the layer N1 (step S240). The boundary determining unit 16 identifies the boundary between the processing target divided area and an adjacent divided area that does not have update data, based on the header information added to the tree structure data of each divided area of the update data. The boundary determination unit 16 sets the specified boundary as the initial value merge boundary (step S250).

The boundary determining unit 16 refers to the tree structure data of the processing target divided area indicated by the update data, and determines whether each block Bn of layer n includes the area of the update data. The boundary determining unit 16 determines that the block Bn includes the area of the update data when it is set in the tree structure data of the update data that the block Bn has a point. On the other hand, if it is set in the tree structure data of the update data that the block Bn does not have a point, the boundary determination unit 16 determines that the block Bn does not include the area of the update data. Note that it is not possible to distinguish between areas where there is no updated data, whether the point cloud is not measured, or where the point group is measured but no points are detected. The boundary determining unit 16 assigns "1" to a block Bn that includes an area for updated data, and assigns "0" to a block Bn that does not include an area for updated data.

The boundary determination unit 16 detects the first block Bn to which 1 is assigned for each row of blocks Bn in the processing target divided area starting from the initial value of the merge boundary. For each column, the boundary determining unit 16 moves the merge boundary of that column to the boundary between the detected block Bn and the block Bn adjacent to the merge boundary side of the same column as the detected block Bn (step S260 ). When the merge boundaries between adjacent columns become discontinuous due to this movement, the boundary determination unit 16 connects the discontinuous merge boundaries along the boundary of block Bn.

If the current processing target hierarchy n has not reached the lower limit N2 of the hierarchy, the boundary determination unit 16 determines that there is a next hierarchy (step S270: YES). The boundary determining unit 16 updates the processing target hierarchy n to the hierarchy (n+1) that is one level below the current processing target hierarchy n (step S280). The boundary determining unit 16 repeats the processing from step S260.

As described above, the boundary determining unit 16 repeats the processing from step S260 to step S280. When the boundary determining unit 16 determines that the hierarchy n to be processed has reached the lower limit N2 of the hierarchy (step S270: NO), the boundary determining unit 16 notifies the merging unit 17 of the divided area to be processed and the merging boundary. The merging unit 17 replaces, among the blocks within the processing target divided area of the old data, a block closer to the adjacent divided area where updated data exists than the determined merge boundary with the updated data of that block (step S290). . The replacement may be performed using a point group or by replacing the target location in the tree structure data.

The process in FIG. 6 will be explained using FIGS. 7 to 10. In FIGS. 7 to 10, the divided regions and each block are represented by planes for simplicity.

FIG. 7 is a diagram showing a processing target divided area and an adjacent divided area. The processing target divided region D1 and the divided regions D2 to D5 adjacent to the processing target divided region D1 each correspond to block B0 in FIG. 3. FIG. 7A shows a case where update data exists in all divided regions adjacent to the processing target divided region D1. In this case, the boundary determining unit 16 determines that all the processing target divided regions D1 of the old data are replaced with the processing target divided regions D1 of the updated data (step S210: YES, step S220).

FIG. 7B shows a case where there is a divided region adjacent to the processing target divided region D1 that does not have update data. In FIG. 7B, update data exists in adjacent divided areas D4 and D5. However, there is no updated data in adjacent divided areas D2 and D3. In this case, the boundary determining unit 16 performs the processing from step S230 on the processing target divided region D1.

FIGS. 8 to 10 are diagrams for explaining the determination of the merge boundary in the processing target divided region D1. The case where the hierarchy N1 acquired in step S230 of FIG. 6 is 1 and the hierarchy N2 is 3 will be described. The boundary determination unit 16 sets the processing target layer n to N1 (=1) (step S240 in FIG. 6).

FIG. 8 shows the process when the hierarchy n is 1. Area E represents an area where updated data is obtained. In the processing target divided area D1, an area that is not included in the updated data area E is an area where old data is present but updated data is not obtained.

Among the divided regions adjacent to the processing target divided region D1, update data does not exist in the divided region D2 and divided region D3. Therefore, the boundary determining unit 16 sets the boundary between the processing target divided region D1 and the divided regions D2 and D3 as the initial value merging boundary R (step S250 in FIG. 6).

Next, the boundary determining unit 16 refers to the tree structure data of the update data and determines whether each block B1-i of the hierarchy 1 in the processing target divided region D1 includes a point of the update data. Note that FIG. 8 shows four blocks B1-0 to B1-3 of layer 1.

The boundary determination unit 16 assigns 1 to the block B1-i that includes the updated data point, and assigns 0 to the block B1-i that does not include the updated data point. The boundary determining unit 16 detects the first block B1-i to which 1 is assigned for each column of blocks B1-i starting from the initial value of the merge boundary R. That is, the boundary determining unit 16 detects the block closest to the current (initial value) merging boundary R among the blocks B1-i whose value is 1 in each column.

The boundary determining unit 16 detects the block B1-3 that is close to the current merge boundary R, since both blocks B1-3 and B1-2 forming the vertical column L1 have a value of 1. Since the detected block B1-3 includes the merge boundary R, the boundary determination unit 16 does not move the merge boundary R for the column L1 (step S260 in FIG. 6).

The boundary determining unit 16 detects the block B1-1 that is close to the current merge boundary R because the values of both blocks B1-1 and B1-0 constituting the vertical column L2 are 1. Since the detected block B1-1 includes the merge boundary R, the boundary determining unit 16 does not move the merge boundary R for the column L2 (step S260 in FIG. 6).

The boundary determination unit 16 detects the block B1-3 that is close to the current merge boundary R because the values of both blocks B1-3 and B1-1 constituting the horizontal column L3 are 1. Since the detected block B1-3 includes the merge boundary R, the boundary determination unit 16 does not move the merge boundary R for the column L3 (step S260 in FIG. 6).

Since the values of blocks B1-2 and B1-0 constituting the horizontal column L4 are both 1, the boundary determining unit 16 detects the block B1-2 that is close to the current merge boundary R. Since the detected block B1-2 includes the merge boundary R, the boundary determination unit 16 does not move the merge boundary R for the column L4 (step S260 in FIG. 6).

Since the layer n to be processed has not reached the lower limit 2 of the hierarchy (step S270: YES), the boundary determination unit 16 sets the layer n to be processed to layer 2, which is one level higher than the current level 1 (FIG. 6 step S280).

FIG. 9 shows the process when the hierarchy n is 2. The boundary determination unit 16 refers to the tree structure data of the update data and determines whether each of the blocks B2-ij of the second layer in the processing target divided region D1 includes a point of the update data. Note that the boundary determination unit 16 may limit the determination target to child blocks of blocks B1-1, B1-2, and B1-3 that include boundaries in layer 1, which is the layer one higher.

The boundary determining unit 16 assigns 1 to blocks B2-ij that include update data points, and assigns 0 to blocks B2-ij that do not include update data points. The boundary determining unit 16 detects the first block B2-ij to which 1 is assigned for each row of blocks B2-ij starting from the initial value of the merge boundary R. In other words, the boundary determining unit 16 detects the block closest to the current merge boundary R among the blocks B2-ij having a value of 1 in each column.

The boundary determining unit 16 selects a block B2-2-3 having a value of 1 among blocks B2-3-3, B2-3-2, B2-2-3, and B2-2-2 that constitute the vertical column L11. Detect. The boundary determining unit 16 moves the merge boundary R to the boundary between the block B2-2-3 and the block B2-3-2 adjacent to the merge boundary R side of the block B2-2-3 in the column L11 ( Step S260 in FIG. 6).

Similarly, the boundary determining unit 16 detects the block B2-3-0 closest to the current merge boundary R among the blocks having a value of 1 in the vertical column L12. The boundary determining unit 16 moves the merge boundary R to the boundary between the detected block B2-3-0 and the block B2-3-1 adjacent to the current merge boundary R side of the block B2-3-0 ( Step S260 in FIG. 6).

Similarly, the boundary determining unit 16 detects the block B2-1-3 closest to the current merge boundary R among the blocks having a value of 1 in the vertical column L13 where block B2-1-3 is the first block. In addition, the boundary determining unit 16 detects the block B2-1-1 closest to the current merge boundary R among the blocks having a value of 1 in the vertical column L14 where the block B2-1-1 is the first block. Since the current merge boundary R is included in the detected blocks B2-1-3 and B2-1-1, the boundary determination unit 16 does not move the merge boundary R for columns L13 and L14 (step S260 in FIG. 6). ).

The boundary determination unit 16 detects the block B2-1-3 closest to the current merge boundary R among the blocks having a value of 1 in the horizontal column L15 where block B2-3-3 is the first block. The boundary determining unit 16 moves the merge boundary R to the boundary between the detected block B2-1-3 and the block B2-3-1 adjacent to the current merge boundary R side of the block B2-1-3 ( Step S260 in FIG. 6). The boundary determining unit 16 also performs the same process as above for the horizontal columns L16 to L18.

Through the above processing, the merge boundary R of horizontal column L17 remains at the initial value, but the merge boundary R of horizontal column L18 becomes between block B2-2-2 and block B2-2-0. . Since these merge boundaries R are discontinuous, the boundary determining unit 16 connects the merge boundary R of column L17 and the merge boundary R of column L18.

Since the layer n to be processed has not reached the lower limit 3 of the hierarchy (step S270: YES), the boundary determination unit 16 sets the layer n to be processed to layer 3 one higher than the current level (step S280 in FIG. 6). ).

Figure 10 shows the processing when hierarchical level n is 3. The boundary determination unit 16 refers to the tree structure data of the update data and determines whether each block of hierarchical level 3 in the processing target division area D1 contains a point of the update data. The boundary determination unit 16 may limit the objects of the determination to child blocks of blocks B2-1-4, B2-2-1, B2-2-3, B2-2-4, B2-3-1, B2-3-2, B2-3-3 that contain a boundary in hierarchical level 2, which is the next higher hierarchical level.

The boundary determination unit 16 assigns 1 to blocks that include update data points among the blocks of the third layer, and assigns 0 to blocks that do not include update data points. The boundary determining unit 16 performs the same process as in FIG. 9 using the values assigned to the blocks in the third hierarchy, and moves the merge region R (step S260 in FIG. 6). The boundary determination unit 16 determines that the layer n to be processed has reached the lower limit 3 of the layers (step S270 in FIG. 6: NO).

The merging unit 17 replaces a block on the update data side with respect to the determined merge boundary among the blocks in the processing target divided area of the old data with that block of the update data (step S290 in FIG. 6).

Note that the boundary determining unit 16 may perform the process shown in FIG. 11 instead of the process shown in FIG. 6. FIG. 11 is a flow diagram showing the merge boundary determination process of the merge area detection device 1. In FIG. 11, the same processes as those in FIG. 6 are denoted by the same reference numerals, and their explanations will be omitted. The process shown in FIG. 11 differs from the process shown in FIG. 6 in that the process in step S310 is performed before the process in step S290. In step S310, the boundary determining unit 16 moves the merge boundary by one block toward the area where the updated data is located.

FIG. 12 is a diagram showing an example in which the boundary determining unit 16 performs the process of step S310 in FIG. 11 on the merge boundary R determined as shown in FIG. 10. As shown in FIG. 12, the boundary determination unit 16 moves the merge boundary R shown in FIG. 10 by one block in the direction of the update data E.

The difference between the process shown in FIG. 6 (described as process A) and the process shown in FIG. 11 (described as process B) is whether the merge boundary is placed outside or slightly inside the updated data. In the case of process A, merging can be performed with all updated data remaining. On the other hand, there is a possibility that the update data exists only in a part of the block adjacent to the inside of the boundary, and the point group regarding this block may become sparse. This is because, after merging in step S290, no points are included in the portion outside area E within the diagonally shaded block in FIG. In process B, the old data is used at the merge boundary, and only the area inside the merge boundary where the updated data is sure to exist in the entire block is filled with the updated data. This may prevent boundaries from becoming sparse.

Note that in the above, the merge area detection device 1 extracts a target area to be updated with update data from old data. Then, when merging the old data and the updated data, the merge area detection device 1 detects an area that does not include the updated data among the areas of the old data, leaves the old data in the detected area, and stores the updated data. Add together. However, the merge area detection device 1 may extract areas that will not be updated from the old data. In that case, in step S120, the replacement unit 15 identifies a divided area in which updated data does not exist among the divided areas of old data. The replacement unit 15 adds the specified divided area to the updated data, and replaces the added divided area with the old data of the divided area. Then, in step S220, the replacement unit 15 leaves the processing target divided region as the updated data. In step S290, the merging unit 17 replaces, among the blocks of the divided area to be processed of the update data, a block on the old data side with respect to the determined merging boundary with a block in the same position of the old data.

Second Embodiment
In the first embodiment, the area in which the old data and the updated data are merged is determined three-dimensionally. In the second embodiment, points are projected in the z-axis direction (axis perpendicular to the ground) and the area in which the data is merged is determined two-dimensionally. This makes it possible to reduce and simplify the processing of the merge area detection device. The second embodiment will be described focusing on the differences from the first embodiment.

FIG. 13 is a block diagram showing the configuration of a merge area detection device 2 according to the second embodiment. In FIG. 13, the same parts as those of the merge area detection device 1 according to the first embodiment shown in FIG. 1 are denoted by the same reference numerals, and the description thereof will be omitted. The merge region detection device 2 differs from the merge region detection device 1 shown in FIG.

The converter 24 performs the same processing as the converter 14. Further, the conversion unit 24 projects the divided regions and each point of the update data included in the divided regions onto a two-dimensional plane. For each two-dimensional divided area, the conversion unit 24 generates tree structure data representing the point cloud data projected onto the divided area using quadtree data. The boundary determining unit 26 determines a merging boundary for a divided region where old data and updated data overlap, using updated data converted into a two-dimensional plane.

An example of calculating tree structure data of points projected onto a two-dimensional plane will be described with reference to FIGS. 14 and 15. These figures show projections in the z-axis direction.

FIG. 14 is a diagram for explaining the conversion from 8-ary tree data to 4-ary tree data. Nodes N-0 to N-7 correspond to blocks B-0 to B-7, which are child blocks of block B shown in FIG. 2, respectively. In FIG. 14, points exist only in blocks B-2 and B-3. Therefore, node N-2 is connected to nodes B-2-0 to B-2-7 corresponding to blocks B-2-0 to B-2-7, which are child blocks of node N-2, respectively. . Similarly, node N-3 is connected to nodes B-3-0 to B-3-7 corresponding to blocks B-3-0 to B-3-7, which are child blocks of node N-3. Ru. Each node is assigned a "1" if it has a point, and a "0" if it does not have a point.

The conversion unit 24 calculates the logical sum of the values of the nodes corresponding to the blocks overlapping in the z-axis direction. As shown in FIG. 2, block B-0 and block B-1, block B-2 and block B-3, block B-4 and block B-5, block B-6 and block B-7 are respectively z They overlap in the axial direction. The conversion unit 24 logically ORs the block value of the plane obtained by projecting block B-0 and block B-1, which overlap in the z-axis direction, with the value of node N-1 and the value of node N-2. . Similarly, the conversion unit 24 converts the block value of the plane obtained by projecting block B-2 and block B-3, which overlap in the z-axis direction, into the logic between the value of node N-2 and the value of node N-3. Make it the sum. At this time, the conversion unit 24 calculates the logical sum of the value of the node N-2-j and the value of the node N-3-j corresponding to the child block at the same position. The conversion unit 24 performs a process of calculating a block value of a plane obtained by projecting overlapping blocks in the z-axis direction on the obtained logical sum.

FIG. 15 is a diagram for explaining an example of generating tree structure data using the coordinates of points projected onto a two-dimensional plane. As shown in FIG. 15(a), the conversion unit 24 removes the z-axis coordinate value from the three-dimensional coordinate value of each point included in the point cloud data, and converts it into the coordinate of the xy plane. FIG. 15(b) is a diagram showing divided regions obtained by projecting three-dimensional divided regions overlapping in the z-axis direction onto the xy plane. The conversion unit 24 generates four child blocks by dividing the divided region into two equal parts in each of two mutually orthogonal directions (x-axis, y-axis). The conversion unit 24 uses the generated child block as a parent block and repeats the process of generating four child blocks from the parent block. The conversion unit 24 uses the coordinates of the projected points to generate nodes in a tree structure corresponding to each block of the hierarchical plane. For nodes corresponding to blocks containing points, the conversion unit 24 creates quadtree data by assigning a block value indicating whether or not each child block whose parent block is the block contains points. .

The merge area detection device 2 performs the process shown in FIG. In step S140 of FIG. 5, the merge area detection device 2 performs the process shown in FIG. 16 instead of the process shown in FIG.

FIG. 16 is a flow diagram showing the merge boundary determination process of the merge area detection device 2. In FIG. 16, the same processes as those in FIG. 6 are denoted by the same reference numerals, and their explanations will be omitted. The process shown in FIG. 16 differs from the process shown in FIG. 6 in that the merge area detection device 2 performs the process in step S410 before the process in step S230. In step S410, the conversion unit 24 projects the point cloud data of the update data in the z-axis direction to form a point cloud on a two-dimensional plane. The conversion unit 24 generates quadtree data of point cloud data on a plane onto which the divided regions to be processed are projected. Then, the boundary determining unit 26 of the merge region detection device 2 performs the processes of step S250, step S260, and step S280 using the generated quadtree data.

In step S290, the merging unit 17 replaces, among the blocks of the target divided area of old data, a block closer to an adjacent divided area where updated data exists than the determined merge boundary with the updated data of that block. Note that the boundary determining unit 26 determines the merge boundary in the plane. Therefore, the merging unit 17 performs the replacement using the merging boundary determined by the boundary determining unit 26, regardless of the z-axis position of the divided region to be processed.

Note that the merge area detection device 2 only needs to perform the processes from step S210 to step S270 in FIG. 16 once for a plurality of processing target areas that have the same projection onto the xy plane. Furthermore, the merge area detection device 2 may perform the process of step S410 after the process of step S230. Furthermore, the merge area detection device 2 may perform the process of step S310 in FIG. 11 before the process of step S290.

By determining the area two-dimensionally, in addition to reducing the weight and simplifying the processing, there are the following advantages. In other words, when updating 3D data on a map, assume that a building has been built on a vacant lot, and that the data is acquired in a situation where there is a blocking object such as a car between the building and Lidar. . In this case, it is not possible to obtain information on the existence of buildings in the space where the vacant ground existed, and there is a possibility that the vacant ground is below and the building is only above. However, when points are projected in the z-axis direction, the ground below can be deleted just by the information that the upper side of the building exists, and the state can be updated with only new data.

If the old data is simply replaced with the updated data, this can be done by merging a part of the hierarchical tree structure of the old data into the tree structure of the updated data. However, when the range to be replaced with update data is not known, a technique is needed to determine the area to be replaced. According to the embodiment described above, it is possible to determine the area to be replaced.

Further, in the above-described embodiment, it is assumed that the inside of the area of old data and updated data is all continuous data, that is, data in a convex-shaped area. This is based on the assumption that since point cloud data is acquired for a continuous space, data for distant areas is generally not acquired. For example, a case where the point cloud data is acquired in a donut shape is also assumed. In that case, it can be handled by dividing into divided regions in step S120.

Note that step S130 in FIG. 5 is a process when there is no boundary between old data and updated data. Furthermore, so far, the explanation has been given for the case where there is overlap between the point clouds of old data and updated data. A configuration is further added to determine whether the area included in the updated data includes an area that does not overlap with the old data, and the merge area detection devices 1 and 2 do not closely examine areas of the updated data that do not overlap with the old data. may be processed. For example, if the boundary determination units 16 and 26 can confirm that all the old data in the area inside the determined merge boundary (on the updated data side) is 0, they will abort the determination process for the lower layers. Good too.

In the above, point cloud data is divided into divided regions of a common size, and each divided region is converted into 8-ary tree data and merged. On the other hand, in PCC (Point Cloud Compression), which is being developed in the MPEG (Moving Picture Experts Group) standardization, and in particular G-PCC for space and stationary objects, point cloud data is converted to an octree representation and then converted into arithmetic codes. be converted into Therefore, when one or both of old data and updated data is a G-PCC stream that is compressed data, octree processing is not necessary when merging processing is performed using a common block. The G-PCC stream may be arithmetic decoded and merged using octree data. In other words, merging processing using a once compressed G-PCC stream rather than the point cloud data itself can be performed without converting to an octree. In this way, the old data and updated data of the G-PCC stream can be merged without completely decoding the coordinate data. Furthermore, when using MPEG, it is possible to use information in the G-PCC stream as information equivalent to header information regarding each block (coding unit).

Up to this point, an embodiment has been described in which data in an octree structure is used and merged without decoding. From here, a method will be described that allows merging without performing inverse conversion even if stream data obtained by converting octree-structured data into binary values or the like is used. As described above, by using the header information, it is possible to specify the area of the old data that corresponds to the area of the real space expressed by the updated data. If the area can be specified, by replacing the old data with the specified area using the payload of the update data stream, it is possible to merge without performing reverse conversion.

Note that in the above, a cubic parent block is divided into eight cubic child blocks, but the parent block and child blocks do not have to be cubes. For example, when a parent block is divided into n child blocks, instead of using the tree structure data expressed as an 8-ary tree structure as described above, the spatial region containing the points is expressed as an n-fold tree structure. Tree-structured data is used.

The functions of the merge area detection devices 1 and 2 in the embodiments described above may be realized by a computer. In that case, a program for realizing this function may be recorded on a computer-readable recording medium, and the program recorded on the recording medium may be read into a computer system and executed. Note that the "computer system" herein includes hardware such as an OS and peripheral devices. Furthermore, the term "computer-readable recording medium" refers to portable media such as flexible disks, magneto-optical disks, ROMs, and CD-ROMs, and storage devices such as hard disks built into computer systems. Furthermore, a "computer-readable recording medium" refers to a storage medium that dynamically stores a program for a short period of time, such as a communication line when transmitting a program via a network such as the Internet or a communication line such as a telephone line. It may also include a device that retains a program for a certain period of time, such as a volatile memory inside a computer system that is a server or client in that case. Further, the above-mentioned program may be one for realizing a part of the above-mentioned functions, or may be one that can realize the above-mentioned functions in combination with a program already recorded in the computer system.

An example of the hardware configuration of the merge area detection devices 1 and 2 will be described. FIG. 11 is a device configuration diagram showing an example of the hardware configuration of the merge area detection devices 1 and 2. As shown in FIG. The merge area detection device 1 includes a processor 71, a storage unit 72, a communication interface 73, and a user interface 74.

The processor 71 is a central processing unit that performs calculations and control. Processor 71 is, for example, a CPU. The processor 71 reads a program from the storage unit 72 and executes it. Some of the functions of the merge region detection devices 1 and 2 may be realized using hardware such as an ASIC (Application Specific Integrated Circuit), a PLD (Programmable Logic Device), or an FPGA (Field Programmable Gate Array). The storage unit 72 further includes a work area when the processor 71 executes various programs. The communication interface 73 is communicably connected to other devices. The user interface 74 is an input device such as a keyboard, a pointing device (mouse, tablet, etc.), a button, a touch panel, or a display device such as a display. A human operation is input through the user interface 74 . For example, upper limit tier information and lower limit tier information are input through the user interface 74 .

Each of the merge area detection devices 1 and 2 may be realized by a plurality of computer devices connected to a network. In this case, each of the functional units of the merge area detection devices 1 and 2 can be implemented by any one of the plurality of computer devices. Furthermore, the same functional unit may be realized by a plurality of computer devices.

According to the embodiment described above, the merge region detection device includes an acquisition section and a boundary determination section. The acquisition unit is, for example, the conversion unit 14 in the embodiment. The acquisition unit acquires first point cloud data that includes information on the position of each point in a part of a predetermined space, and obtains points for each region in which the predetermined space is divided into tree-structured regions consisting of a plurality of layers. Obtain tree structure data expressed by presence/absence information. The predetermined space corresponds to a divided area in the embodiment, and the area corresponds to a block. The boundary determination unit generates first point cloud data in a predetermined space and information about each point in at least a part of the space in the predetermined space based on the highest layer in which points exist in the hierarchy of the tree structure data. A merging boundary, which is a boundary when merging the second point cloud data including

The boundary determining unit performs an initial value setting process in which the boundary between the predetermined space and the adjacent space, which is a space adjacent to the predetermined space, in which the point of the first point cloud data does not exist, is an initial value merging boundary. , the process of determining whether or not the points of the first point cloud data exist in the region of the hierarchy to be determined, and moving the merge boundary to the boundary that changes from the region where no points exist to the region where points exist. An iterative process may be performed in which the hierarchy is changed from an upper hierarchy to a lower hierarchy.

The merge area detection device may further include a merge section. The merging unit merges the points of the first point group data and the points of the second point group data based on the merging boundary determined by the boundary determining unit.

The merge area detection device may further include a dividing section. The dividing unit divides a space represented by the first point group data and a space represented by the second point group data into divided regions that are units of generation of tree structure data. The merging unit uses information about the points of the first point group data for the divided regions where the points of the first point group data exist and where the second point group data does not exist. Furthermore, the merging unit uses the point information of the first point cloud data for divided regions in which all adjacent divided regions include regions of the first point cloud data. Furthermore, the merging unit, for a divided area in which any of the adjacent divided areas does not include the area of the first point cloud data, performs the first point cloud data based on the merging boundary determined by the boundary determining unit with the divided area as a predetermined space. Merging the points of the point cloud data and the points of the second point cloud data. The merging unit is, for example, the replacing unit 15 and the merging unit 17 in the embodiment.

Although the embodiments of the present invention have been described above in detail with reference to the drawings, the specific configuration is not limited to these embodiments, and includes designs within the scope of the gist of the present invention.

DESCRIPTION OF SYMBOLS 1...Merge area detection device, 2...Merge area detection device, 11...Storage part, 12...Input part, 13...Dividing part, 14...Conversion part, 15...Replacement part, 16...Boundary determination part, 17...Merge part, 24... Conversion unit, 26... Boundary determination unit, 71... Processor, 72... Storage unit, 73... Communication interface, 74... User interface

Claims (6)

The first point cloud data containing information on the position of each point in a part of a predetermined space is divided into tree-structured regions consisting of multiple layers, and the presence or absence of points is determined in each region. an acquisition step of acquiring tree structure data represented by information;
The first point cloud data in the predetermined space and information on each point in at least a part of the space in the predetermined space are included based on the highest hierarchy in which points exist in the hierarchy of the tree structure data. a boundary determining step of determining a merge boundary, which is a boundary when merging with the second point cloud data, in units of the area;
A merge region detection method having the following. The boundary determination step includes:
an initial value setting step of setting a boundary between the predetermined space and an adjacent space, which is a space adjacent to the predetermined space, in which the point of the first point group data does not exist, as an initial value merging boundary;
A process of determining whether or not a point of the first point cloud data exists in the area of the layer to be determined, and moving the merge boundary to a boundary where the area changes from the area where the point does not exist to the area where the point exists. an iterative processing step of repeating the above while changing the judgment target hierarchy from an upper hierarchy to a lower hierarchy;
The merge region detection method according to claim 1. The method further comprises a merging step of merging the points of the first point cloud data and the points of the second point cloud data based on the merging boundary determined in the boundary determining step.
The merge area detection method according to claim 1 or claim 2. further comprising a dividing step of dividing a space represented by the first point group data and a space represented by the second point group data into divided regions of the generation unit of tree structure data,
In the merge step,
The divided area in which the points of the first point cloud data exist and the second point cloud data does not exist, and the divided area in which all adjacent divided areas include the area of the first point cloud data. uses point information of the first point cloud data,
For the divided area in which the area of the first point cloud data is not included in any of the adjacent divided areas, the merge boundary is determined in the boundary determining step by using the divided area as the predetermined space, and the merge boundary is determined by the boundary determining step. merging the points of the first point cloud data and the points of the second point cloud data based on a merge boundary;
The merge region detection method according to claim 3. The first point cloud data containing information on the position of each point in a part of a predetermined space is divided into tree-structured regions consisting of multiple layers, and the presence or absence of points is determined in each region. an acquisition unit that acquires tree structure data represented by information;
The first point cloud data in the predetermined space and information on each point in at least a part of the space in the predetermined space are included based on the highest hierarchy in which points exist in the hierarchy of the tree structure data. a boundary determining unit that determines a merge boundary, which is a boundary when merging the second point cloud data, in units of the area;
A merge area detection device comprising: to the computer,
A program for executing the merge area detection method according to any one of claims 1 to 4.

Images