JP7606374B2 - Scan data creation method and scan data creation system - Google Patents

Description

This disclosure relates to a scan data creation method and a scan data creation system.

In recent years, the construction industry has increasingly adopted modeling methods that use 3D scan data, as typified by BIM (Building Information Modeling). With BIM, 3D digital models of buildings and other structures are created on a computer, and management and facility information is added to create comprehensive construction-related data, making it more convenient for a variety of uses. For example, it can be used to manage the progress of construction of buildings.

A known measuring device for obtaining 3D scan data is a 3D scanner, which radially irradiates a laser beam onto a measurement object to obtain the 3D coordinates of the object's surface shape. If any measurements are missed, the 3D digital data will be incomplete.

Patent document 1 describes a method for evaluating the placement of multiple surveillance cameras in a monitored area where obstacles exist, in order to minimize the blind spots of the obstacles.

JP 2011-86995 A

Acquiring 3D scan data takes a lot of time. In particular, when the object to be modeled is large or wide, the object must be divided into multiple areas, 3D scan data must be acquired for each area, and the data must then be combined, which takes a lot of time and effort.

Furthermore, when combining the 3D scan data acquired for each area, common objects contained in the 3D scan data for each area are used as indicators to link the data. In other words, data must be acquired so that the multiple 3D scan data to be combined contain common objects. At construction sites, the light reflection from the object and the ambient light can change depending on the time of day and weather. There is also the issue that the appearance of the object changes when the scanning angle changes as the process progresses. The influence of such conditions can make it difficult to determine that the target objects are the same. Therefore, in order to reduce the influence of such conditions, it is desirable to efficiently acquire 3D scan data for multiple areas.

When using multiple 3D scanners to efficiently generate a 3D digital model, it is necessary to set in advance the measurement positions that each scanner will be responsible for, the order of measurements, and the movement route of the moving object to the measurement positions. In particular, to create a 3D digital model in a short time, it is necessary to minimize the time variance from the start to the end of measurement work using multiple 3D scanners. There is an issue that complicated consideration work is required for humans to perform such settings and management.

The present disclosure has been made to solve the above problems, and aims to provide a scan data creation method and a scan data creation system that can efficiently perform measurements at multiple measurement positions.

One aspect of the present disclosure is a scan data creation method for acquiring 3D scan data for creating a 3D digital model of an object, the method including a measurement instrument for measuring the object, and comprising: a measurement position calculation step for calculating a plurality of measurement positions at which the object can be measured; and a measurement route calculation step for calculating a measurement route for moving the measurement instrument to the plurality of measurement positions with a minimum travel cost , wherein the measurement route calculation step sets all edges that can logically reach each of the plurality of measurement positions in the shortest distance, and in a minimum spanning tree calculated from all edges, a route that minimizes the sum of costs of edges that require a return to a branch is determined as the measurement route .

One aspect of the present disclosure is a scan data creation system that acquires 3D scan data for creating a 3D digital model of an object, the system comprising: a measuring instrument that measures the object; a calculation means that calculates a plurality of measurement positions at which the object can be measured and calculates a measurement route that brings the measuring instrument to the plurality of measurement positions with minimal movement cost; and a mobile body that is equipped with the measuring instrument and is capable of autonomous movement, and that moves along the measurement route in response to commands from the calculation means to perform measurements using the measuring instrument at the measurement positions, the calculation means setting all edges that can logically reach each of the plurality of measurement positions in the shortest distance, and determining as the measurement route a route in a minimum spanning tree calculated from all the edges that has the smallest sum of costs of edges that require backtracking to a branch .

The scan data creation method and scan data creation system disclosed herein allow measurements to be performed efficiently at multiple measurement positions.

FIG. 2 is a diagram illustrating a hardware configuration and functional blocks of the scan data creation system. 10 is a flowchart showing the flow of a scan data creating method. FIG. 13 is a diagram for explaining determination of a plurality of measurement positions. FIG. 13 is a diagram showing a connection relationship that allows a plurality of measurement positions to be moved in the shortest distance. FIG. 13 is a diagram showing a state in which a plurality of measurement positions are grouped. FIG. 13 is a diagram showing the measurement route with the minimum travel cost for each group. FIG. 13 is a diagram showing the order of movement of the measurement route of each group. FIG. 13 is a diagram showing a state in which the grouping is changed and the measurement route is corrected. FIG. 13 is a diagram for explaining the determination of the movement order on a measurement route.

The scan data creation method and scan data creation system according to the embodiments will be described in detail below with reference to the attached drawings. The following embodiment is applied to the case where 3D scan data of the internal structure of a building at a construction site is obtained.

Figure 1 is a block diagram showing the hardware configuration and functional blocks of the scan data creation system 1. The scan data creation system 1 includes a command creation unit 10 and a moving body 20. The command creation unit 10 is an example of a calculation means that calculates the measurement position and measurement route where the moving body 20 performs measurements.

The command creation unit 10 is configured with a local server or cloud server that is networked with the mobile object 20 and other external devices, and has a data receiving unit 11, a data processing unit 12, and an autonomous movement operation command unit 13. The mobile object 20 has a computer 21, and sensors and devices that are comprehensively controlled by the computer 21. The scan data creation system 1 can use one or more mobile objects 20, and each mobile object 20 has the configuration shown in FIG. 1.

The hardware configuration of the command creation unit 10 includes a CPU (Central Processing Unit) which is a calculation means, a ROM (Read Only Memory) which is a semiconductor memory that is read only, a RAM (Random Access Memory) which is a semiconductor memory that is randomly accessible, an input device, a display device, a communication interface, and the like. The command creation unit 10 can communicate with external devices including the mobile object 20 via the communication interface. The form of communication may be either a wired connection or a wireless connection, and the communication standard is not limited.

The ROM of the command creation unit 10 stores various programs. The CPU of the command creation unit 10 reads out the programs from the ROM and executes them in response to operation signals from the input device. The RAM of the command creation unit 10 is used as a work area for the programs and data when the CPU executes the programs. The display device of the command creation unit 10 is a monitor with a display screen, and displays information such as the contents of the processing and the results of the processing. The functions of the data processing unit 12 in the command creation unit 10 are realized by at least the CPU, ROM, and RAM. In addition, each process described below performed by the command creation unit 10 is executed based on a scan data creation program stored in the ROM.

Various data are input to the data receiving unit 11 of the command creation unit 10 by operating an input device or communicating via a communication interface. The data input to the data receiving unit 11 includes drawing data of the building, which is the measurement target (object) for which 3D scan data is to be obtained, and the number of mobile objects 20 planned to be used. The data input to the data receiving unit 11 is sent to the data processing unit 12.

Based on the input data, the data processing unit 12 calculates and determines multiple measurement positions where measurements are performed by the moving body 20, the allocation (group) of measurement positions to be assigned to each moving body 20 when multiple moving bodies 20 are used, and the measurement route which is the path that the moving body 20 moves between the measurement positions. The calculation process will be described later. The contents determined by the data processing unit 12 are sent to the moving body 20 from the autonomous movement operation command unit 13 as an operation command.

The computer 21 of the moving body 20 is composed of a CPU, ROM, RAM, etc. The computer 21 receives the operation command issued by the command creation unit 10 through the data receiving unit 22, and executes the contents of the operation command through the autonomous movement command control unit 23 and the 3D scanner operation unit 24.

The moving body 20 is equipped with an object sensor 25, an inertial measurement unit 26, and a traveling drive unit 27. The object sensor 25 is a detector capable of measuring the distance and positional relationship with an external object. For example, a ToF (Time of Flight) type sensor using LiDAR (Light Detection and Ranging) technology, a stereo camera capable of capturing stereo images, etc. can be applied as the object sensor 25. The inertial measurement unit 26 is also called an IMU (Internal Measurement Unit) and has a sensor that detects various motion information such as acceleration and rotational angular velocity. Note that a 360-degree camera can be used instead of the object sensor 25. By using a 360-degree camera, surrounding objects can be detected with a single shot. The travel drive unit 27 is a drive mechanism that is composed of wheels and caterpillars that contact the ground, a motor and power transmission system for operating the wheels and caterpillars, etc. The objective sensor 25 obtains information about surrounding objects and obstacles, the inertial measurement device 26 recognizes the attitude and moving state of the vehicle, and the travel drive unit 27 provides a driving force, allowing the mobile unit 20 to move autonomously to the measurement position without being operated by a driver.

The mobile body 20 is further equipped with a three-dimensional scanner 30, which is a measuring device. The three-dimensional scanner 30 is a non-contact optical scanner, and the measuring unit 31 irradiates a beam of light such as laser light onto the object and analyzes the time difference of reflection and the angle of irradiation to obtain the three-dimensional shape of the object. The three-dimensional scanner 30 of this embodiment is a type that can measure in all directions by irradiating laser light from the measuring unit 31 radially. The three-dimensional scan data obtained by the measuring unit 31 is stored in the data storage unit 32.

The three-dimensional scan data stored in the data storage unit 32 of the moving body 20 is sent to a server or other data processing device constituting the command creation unit 10. The three-dimensional scan data acquired by the moving body 20 at multiple measurement positions becomes three-dimensional scan data representing the entire building, which is the object of measurement. Alternatively, three-dimensional scan data representing the entire building, which is the object of measurement, can be created by synthesizing (linking) three-dimensional scan data acquired by multiple moving bodies 20 at multiple measurement positions. By acquiring three-dimensional scan data so that multiple moving bodies 20 include a common object, data synthesis can be performed using the common object as an index. In the case of a divided measurement method in which the moving body 20 does not continuously acquire three-dimensional scan data but acquires three-dimensional scan data at fixed points divided into multiple measurement positions, a process of synthesizing the three-dimensional scan data acquired at multiple measurement positions is performed regardless of the number of moving bodies 20. This embodiment is applied to the divided measurement method.

The 3D scan data created using the scan data creation system 1 in the manner described above is used to create 3D digital models of buildings, etc.

Next, the details of how the command creation unit 10 determines the measurement position and measurement route will be explained with reference to the flowchart in FIG. 2 and the explanatory diagrams in FIG. 3 and subsequent figures.

The explanatory diagrams from Figure 3 onwards show the case where the internal structure of a building 40 is scanned as the target object. The building 40 has a box-shaped outer wall 41 and multiple partition walls 42 located within the space surrounded by the outer wall 41. Note that for ease of understanding, Figures 3 to 8 show the building 40 in a plan view, but the acquired 3D scan data also includes information on the height direction (the direction perpendicular to the paper surface of Figures 3 to 8).

[Step S1: Data input step]
In step S1, data on drawings (design drawings) of the building 40 to be measured is input to the data receiving unit 11 of the command creating unit 10, and the input drawing data is expanded in the working area of the data processing unit 12 with coordinate information and the like added. In addition, the number of mobile objects 20 to be used for measurement is input to the data receiving unit 11, and is held as number data in the working area of the data processing unit 12. This embodiment illustrates the case where two mobile objects 20 are used, and number data indicating two is input.

[Step S2: Measurement position calculation step]
Step S2 is processed by the measurement position calculation unit 12a (FIG. 1), which is a functional block of the data processing unit 12. In step S2, the data processing unit 12 of the command creation unit 10 calculates the measurement positions at which the moving body 20 will acquire 3D scan data. When calculating the measurement positions, the following conditions are imposed: the entire measurement target is scanned so as to reduce blind spots; the number of measurement positions is minimized; and the ranges scanned by adjacent measurement positions include overlapping areas (objects that serve as indicators for later data synthesis), and multiple measurement positions that satisfy these conditions are determined. Each measurement position determined in step S2 is stored in the RAM of the command creation unit 10 as coordinate data.

The method of evaluating placement positions described in JP 2011-86995 A (Patent Document 1) can be used to calculate the measurement positions in step S2. In brief, a non-diffraction Voronoi diagram is created for the measurement target area, with the blind spots of obstacles seen from each generating point treated as non-diffraction, and the measurement positions to be placed in the measurement target area are evaluated using the non-diffraction Voronoi diagram.

The results of processing step S2 for the building 40 are shown in Figure 3. As a result of the calculation, 12 measurement positions are determined, from measurement position P1 to measurement position P12. Measurements are performed by the 3D scanner 30 at each of these measurement positions P1 to P12. If a partition wall 42 or the like is present, the laser light from the measurement unit 31 can be made to reach the partition wall 42 from both sides, and the entire internal structure of the building 40 can be scanned to obtain 3D scan data.

[Step S3: Movable information calculation step]
Step S3 is processed by the movable information calculation unit 12b (FIG. 1), which is a functional block of the data processing unit 12. In step S3, movable information between a plurality of measurement positions is calculated. In this calculation process, among the plurality of measurement positions obtained in step S2, those that can be moved in the shortest distance (straight movement) without being blocked by obstacles such as the partition wall 42 are set as provisional connection relationships (links). For example, a straight line connecting each of the plurality of measurement positions is set, and it is determined whether or not an obstacle that blocks each straight line exists on the drawing data. Then, a straight line without an obstacle is established as a link. In this way, a graph is created in which the measurement positions are vertices or nodes and the links are edges. Information on the links created in step S3 is stored in the RAM of the command creation unit 10.

The results of processing step S3 for building 40 are shown in Figure 4. All measurement positions P1 to P12 are connected to other measurement positions by at least one link L. In Figure 4, only one link L connecting measurement positions P2 and P5 is marked with a symbol, but all solid straight lines connecting each measurement position are links L. On the other hand, dashed straight lines indicate that they are blocked by a partition wall 42 or the like, meaning that they are not in a relationship where movement is possible over the shortest distance, and no link is established.

Figure 4 shows examples of locations where a link is not established due to obstruction by the partition wall 42, such as between measurement positions P1 and P2, between measurement positions P3 and P6, between measurement positions P9 and P10, and between measurement positions P11 and P12. Locations where a link is not established are not limited to these, and there are multiple other locations. For example, a link is not established between measurement positions P1 and P3 because there is a bent portion of the outer wall 41 on the straight line connecting them.

[Step S4: Measurement position classification step]
Step S4 is processed by the measurement position allocation calculation unit 12c (FIG. 1), which is a functional block of the data processing unit 12. In step S4, a calculation is performed to group (classify) a plurality of measurement positions. Based on the data on the number of moving bodies 20 input to the data receiving unit 11, groups are created for the number of bodies, and the measurement positions to be included in each group are determined. As a specific method, starting from an arbitrary measurement position on the graph based on the number of bodies, adjacent measurement positions connected by links are included in the same group one by one. It is efficient to start with the initial measurement position from a different end. This operation is performed for each group, and the process is stopped when all measurement positions are included in a group. Since all measurement positions belong to one of the groups, grouping is completed.

It is preferable that the number of measurement positions included in each group is nearly equal, but in the process of step S4, the number of measurement positions included in each group may not be equal. Furthermore, if the total number of measurement positions is not divisible by the number of groups (the number of mobile bodies 20), the number of measurement positions included in each group will necessarily be unequal. In either case, the number of measurement positions is optimized by the correction process described below, taking into account the movement costs in each group.

The results of processing in step S4 for building 40 are shown in Figure 5. Based on the number of vehicles input as data of two, measurement positions P1 to P12 are divided into two groups, a first group and a second group. In the initial grouping shown in Figure 5, the five measurement positions P1 to P5 are included in the first group, and the seven measurement positions P6 to P12 are included in the second group.

[Step S5: Measurement route calculation step]
Step S5 is processed by the measurement route calculation unit 12d (FIG. 1), which is a functional block of the data processing unit 12. In step S5, the measurement route for each group, i.e., the movement route of each moving object 20, is determined. The measurement route is determined based on the criterion of which of the previously set links is the most efficient route (the route with the smallest movement cost), and includes the following two sub-steps. The movement cost is the movement distance or the movement time. In this embodiment, the movement speed of the moving object 20 is assumed to be constant.

[First sub-step of step S5]
In the first sub-step of step S5, a minimum spanning tree in graph theory is obtained based on a graph in which the measurement positions of each group are vertices or nodes and the links are edges. A spanning tree is a tree obtained by eliminating edges while maintaining the condition that the graph is connected, and a minimum spanning tree is a spanning tree in which the sum of the costs of each edge is minimized. For example, the Kruskal algorithm can be used as an algorithm for obtaining a minimum spanning tree.

The results of processing the first substep in step S5 for building 40 are shown in Figure 6. Link L1, shown in solid line in Figure 6, is a part that constitutes the minimum spanning tree, and this part becomes the measurement route. Link L2, shown in dashed line in Figure 6, is a part that does not correspond to the minimum spanning tree. In Figure 6, the symbols for link L1 and link L2 are attached to only one link each, but all of the solid straight lines connecting each measurement position are link L1, and all of the dashed straight lines are link L2.

In the first group, the sum of the costs of each edge of the spanning tree is minimized when measurement position P4 is the hub (center) and measurement positions P1, P2, P3, and P5 are radially connected.

In the second group, the sum of the costs of each edge of the spanning tree is minimized when measurement position P7 is used as the hub (center) and connected to measurement positions P6, P8, and P10, measurement position P6 is connected to measurement positions P9 and P11, and measurement position P10 is connected to measurement position P12.

[Second sub-step of step S5]
In the second sub-step of step S5, a moving order is determined, which is the order in which to move the edges of the minimum spanning tree that has been set previously, and the moving order that has the smallest moving cost is selected. The moving order is determined based on a depth-first search algorithm, starting from a measurement position that is located at one of the ends (vertices) of the group.

Figure 9 shows route examples A to F for the movement order of the measurement positions in the second group. These route examples A to F compare the movement costs when the measurement positions P8, P11, and P12, which are the ends of the second group (there is only one other measurement position connected by a link), are used as the starting point of the movement. In each case, there is one branch along the way, so there are a total of six route examples, including the cases where each branch is followed.

The basic idea is that travel costs are minimized when all edges included in a route can be traveled in one stroke (without making round trips). Assuming that the length (distance) of each edge is the same, the travel cost increases as the number of edges that involve round trips or the number of round trips on a particular edge increases. For example, when traveling an outward route from a certain branch to the terminal node (measurement position), and a return route that returns to the original branch along the same route as the outward route, round trips are generated on the edges included in the round trip route. In each of the route examples A to F in Figure 9, a change in the numbers following the letters A to F indicates a choice at a branch or a change in direction due to a return move.

In route example A in FIG. 9, the route starts at measurement position P11 and proceeds to measurement position P7 (A1), branches off and proceeds to measurement position P8 (A2), and returns from measurement position P8 to measurement position P7 (A3). This A2 and A3 form a round trip movement. Next, the route proceeds to measurement position P10, an unsearched node, and ends when it reaches measurement position P12 at the end (A4). In this case, the number of return edges is "1".

Route example B in Figure 9 is the same as route example A up to the point where it starts at measurement position P11 and proceeds to measurement position P7 (B1). At a branch, it proceeds to measurement position P10 and reaches measurement position P12 at the end (B2), then returns to measurement position P7 (B3). This B2 and B3 form a round trip. It then proceeds to measurement position P8, an unexplored node, and reaches the end point (B4). In this case, the number of return edges is "2".

In route example C in Figure 9, the route starts at measurement position P8 and proceeds to measurement position P7 (C1). At a branch, the route proceeds to measurement position P6 and reaches measurement position P11 at the end (C2), then returns to measurement position P7 (C3). These C2 and C3 routes are round trips. The route then proceeds to measurement position P10, an unsearched node, and ends at measurement position P12 (C4). In this case, the number of return edges is "3".

Route example D in Figure 9 is the same as route example C up to the point where it starts at measurement position P8 and proceeds to measurement position P7 (D1). At a branch, it proceeds to measurement position P10 and reaches measurement position P12 at the end (D2), then returns to measurement position P7 (D3). This D2 and D3 form a round trip. It then proceeds to measurement position P6, an unexplored node, and ends at measurement position P11 (D4). In this case, the number of return edges is "2".

In route example E in Figure 9, the route starts at measurement position P12 and proceeds to measurement position P7 (E1). At a branch, the route proceeds to measurement position P6 and reaches measurement position P11 at the end (E2), then returns to measurement position P7 (E3). This round trip between E2 and E3 is followed by a return movement. The route then proceeds to measurement position P8, an unexplored node, and reaches the end point (E4). In this case, the number of return edges is "3".

Route example F in Figure 9 is the same as route example E up to the point where it starts from measurement position P12 and proceeds to measurement position P7 (F1). At a branch, it proceeds to measurement position P8 (F2) and returns from measurement position P8 to measurement position P7 (F3). These F2 and F3 are round trip movements. It then proceeds to measurement position P6, an unexplored node, and ends at measurement position P11 (F4). In this case, the number of return edges is "1".

As can be seen from the above route examples A to F, the number of return edges in the measurement route for each group determined in the first substep of step S5 may differ depending on the order in which multiple measurement positions are moved. Route examples A and F, which have the fewest number of return edges, have the shortest total travel distance and can complete the movement in a short time, resulting in a travel order with the lowest travel cost.

Route example G shown in Figure 9 is a comparative example when a route is set using the breadth-first search method. Starting from measurement position P7, proceed to measurement positions P6, P9, and P11 (G1). Turn back at measurement position P11 and return to measurement position P7 (G2). Next, proceed to the unsearched node toward measurement position P10 and reach measurement position P12 at the end (G3). Turn back at measurement position P12 and return to measurement position P7 (G4). Then proceed to the unsearched node toward measurement position P8, which becomes the end point (G5). In this case, the number of return edges is "5".

Route example G shows the case where the number of return edges is the greatest, but when a route is set using a breadth-first search starting from measurement position P7, the number of return edges is at least three. Therefore, it can be seen that a depth-first search method is more suitable for calculating the minimum movement cost than a breadth-first search method.

Note that in Figure 9, we focus on the number of return edges, but if the cost (distance) of each edge is not uniform, it is necessary to calculate the movement cost including the difference in cost of each edge that causes a return. For example, if the number of return edges is the same but the costs (lengths) of the return edges are different, the edge with the smaller cost of the return edge is selected as the movement order with the smallest movement cost.

Even if the number of edges to return to is "1", if the cost of that edge is high and the distance (amount) of return movement is greater than if returning along two other edges, the overall movement cost for the group is smaller if the edge is returned along the other two edges. Therefore, the cost of each edge of the minimum spanning tree determined in the first sub-step should be stored, and in the second sub-step of step S5, the route with the smallest sum of the costs of the edges that cause return movements should be determined as the route with the smallest movement cost.

Figure 9 shows an example of the second group, but the second substep in step S5 is executed in a similar manner for the first group to determine the measurement route with the minimum travel cost.

When the amount of return movement is taken into consideration, a route other than the minimum spanning tree may have a shorter total movement distance. For example, with reference to Figs. 7 and 8, consider the case where measurement position P5 included in the first group is linked to measurement position P4 (Fig. 7) and the case where it is linked to measurement position P2 (Fig. 8). Since the distance from measurement position P4 to measurement position P5 is shorter than the distance from measurement position P2 to measurement position P5, the cost of the edge linking to measurement position P5 is smaller in the form of Fig. 7. On the other hand, when tracing the three points of measurement positions P2, P4, and P5, in the form of Fig. 7, return movements (reciprocating movements) occur both between measurement position P4 and measurement position P5 and between measurement position P2 and measurement position P4, but in the form of Fig. 8, the movement path passes through two sides of a triangle and does not include return movements. And when the total movement distance is shorter by not including return movements, the movement in the form of Fig. 8 may be more advantageous in terms of time.

In the second substep of step S5, the link structure within such a group may be modified (reviewed from the minimum spanning tree) to take back movements into account.

In this way, a measurement route is determined for each group to allow the mobile body 20 to reach multiple measurement positions with the minimum travel cost. The results of the processing of the second sub-step in step S5 for the building 40 are shown in Figure 7. The arrows next to the edges (links) connecting each measurement position in Figure 7 indicate whether or not a return occurs on the determined measurement route. Where there are two arrows in the forward and reverse directions on both sides of an edge, this means that a return occurs from the measurement position located at the end to the branch. Where there is an arrow in one direction on only one side of an edge, this means that the route is a single stroke with no return.

In the example shown in FIG. 7, the movement order of the measurement route for the first group is set with measurement position P1 as the starting point. In the first group, the edges to each of the measurement positions P1 to P3 and P5 are connected in a spoke shape with measurement position P4 at the center, so the measurement route has a return movement on all edges except for the edge from measurement position P1, which is the starting point, to measurement position P4.

In the example shown in FIG. 7, the second group adopts route example A described with reference to FIG. 9 as the movement order of the measurement route. The measurement route is one in which a return movement occurs between measurement position P7 and measurement position P8, and no return movement is performed on any other sides.

[Step S6, Step S7: Measurement route evaluation step]
Step S6 is processed by the calculation result evaluation unit 12e (FIG. 1), which is a functional block of the data processing unit 12. In step S6, the measurement route calculated in step S5 is evaluated. In this evaluation, the movement costs of the measurement route for each group are compared. The lower the movement cost of each group, the shorter the time required for scanning in that group. In addition, when scanning is performed in parallel by multiple groups, the smaller the variation in movement costs between the multiple groups, the shorter the time required to complete the entire scanning work. From this perspective, the measurement route in which the movement costs of each group are most evenly distributed is the best in terms of work efficiency and work time, and whether or not this best measurement route is the evaluation criterion. If it is not the best measurement route, it is determined that there is room for improvement, and the result is YES in step S7, and the process proceeds to step S8. If it is the best measurement route, it is determined that there is no need for improvement, and the result is NO in step S7, and the process proceeds to step S9.

[Step S8: Measured route correction step]
Step S8 is processed by the calculation result correction unit 12f (FIG. 1), which is a functional block of the data processing unit 12. In step S8, the grouping of the measurement positions is changed. Specifically, from the grouping previously performed in step S4, the grouping of one measurement position is provisionally changed to another group. From step S8, the process returns to step S4, and for each updated group, calculation of the measurement route that minimizes the travel cost is performed in step S5. Then, evaluation in step S6 is performed again.

That is, after changing the group to which one measurement location belongs (steps S8 and S4), the minimum movement cost is calculated again for each group (step S5), and it is evaluated whether the movement cost is expected to be improved from the previous calculation result (step S6). As an evaluation method, for example, a method that aims to minimize the movement cost of the group with the highest movement cost among all groups (making the maximum movement cost as small as possible) or a method that aims to minimize the difference in movement cost between the group with the highest movement cost and the group with the lowest movement cost (making the difference in movement cost as small as possible) can be selected.

The flow of returning from step S8 to step S4 and looping until the judgment result of step S7 is obtained is a correction process for the calculation results related to the measured route. Therefore, strictly speaking, the measurement route correction step includes not only step S8 but also steps S4 to S7 from the second time onwards. The grouping change history and the calculation results of the movement cost performed in the correction process are stored in the RAM of the command creation unit 10. Then, the correction process for the calculation results is repeated until the judgment in step S7 becomes NO (no further improvement is possible).

An example of the calculation result correction process is shown in Figure 8. In Figure 8, the measurement position P8 is changed from the second group to the first group (step S8), and the contents of the first and second groups are updated (step S4). For the updated first and second groups, the measurement route is calculated (step S5), and the calculation result is evaluated (step S6). At this time, the route that most evenly distributes the movement costs between the first and second groups is extracted as the measurement route, and the movement cost is determined.

Before correction as shown in Figure 7, the number of sides in the first group is 4 and the number of sides in the second group is 6, whereas after correction as shown in Figure 8, the number of sides in both the first and second groups is 5. As a result, the movement cost of the second group, which had a large movement cost in Figure 7, has become smaller, and the difference in movement cost between the two groups has become smaller. Therefore, it can be said that the measured route in Figure 8 is an improvement over the measured route in Figure 7.

Furthermore, before correction as shown in FIG. 7, the first group includes five measurement positions (P1 to P5) and the second group includes seven measurement positions (P6 to P12), whereas after correction as shown in FIG. 8, both the first and second groups include six measurement positions, so the time required for scanning is averaged for each group. This averaging of the number of measurement positions between groups may be included in the improvement judgment criteria.

If we further consider return movements, we get the following: After the correction shown in Figure 8, measurement position P8 is no longer in the second group, so the second group becomes a route with no branches along the way, and regardless of whether measurement position P11 or measurement position P12 at either end is used as the starting point, the movement cost is the minimum without a return movement. Therefore, for the second group, the effect of reducing movement costs by updating the grouping can be reliably obtained.

For the first group, the movement cost increases due to the addition of measurement position P8. However, as shown in FIG. 8, in the setting of the updated minimum spanning tree for the first group, measurement position P8 is linked to measurement position P5 (first substep of step S5), so if a route is set starting from measurement position P8, which is the terminal position (second substep of step S5), there will be no increase in return movements due to the inclusion of measurement position P8 in the first group. Since the one-way distance from measurement position P8 to measurement position P5 after the correction shown in FIG. 8 is shorter than the round-trip distance between measurement position P7 and measurement position P8 before the correction shown in FIG. 7, a reduction in the total movement distance for the first and second groups combined can be expected.

In the correction example shown in FIG. 8, the first group is further modified so that measurement position P5 is linked to measurement position P2 instead of measurement position P4, and the route is corrected so that measurement position P8 starts and measurement positions P5, P2, and P4 are moved in that order. As a result, the return movement between measurement position P4 and measurement position P5 and the return movement between measurement position P2 and measurement position P4 before the correction shown in FIG. 7 are eliminated. Since the distance traveled one way along the two sides from measurement position P5 to measurement position P4 via measurement position P2 in FIG. 8 is shorter than the sum of the distance traveled back and forth between measurement position P2 and measurement position P4 in FIG. 7 and the distance traveled back and forth between measurement position P4 and measurement position P5 in FIG. 7, the effect of reducing the total movement distance of the first and second groups combined can be expected.

In addition to measurement position P8, whose group has been changed in FIG. 8, the measurement route is calculated and evaluated for all measurement positions that can be changed to a different group in the same way. A measurement position that can be changed to a different group is a measurement position that satisfies the conditions that "it is connected to two or more other measurement positions by links" and "the number of groups does not increase due to the change in the group to which it belongs (the link structure of each existing group is not broken)."

For example, in the initial grouping shown in FIG. 5, measurement positions P1, P2, P4, P5, P7, and P8 are measurement positions that can be moved to another group. If measurement positions P6, P9, and P10 were to change their affiliation from the second group to the first group, the terminal measurement positions P11 and P12 would become new groups separated from the second group, and so they would be unable to be moved to another group. Measurement positions P3, P11, and P12 have only one link destination, and it is not possible to skip this link destination and connect to a measurement position in another group, so they would be unable to be moved to another group.

As shown in FIG. 8, once calculation of the minimum movement cost for each group when measurement position P8 is changed to the first group is completed, measurement position P8 is returned to the second group. Next, the minimum movement cost for each group when measurement position P7 is changed from the second group to the first group is calculated, and measurement position P7 is returned to the second group. Similarly, the minimum movement cost for each group is calculated when measurement positions P1, P2, P4, and P5 are each changed from the first group to the second group. In this way, the measurement positions that can be changed to another group are changed into different groups one by one, and the minimum movement cost for each group is calculated in each case.

If the movement cost calculated by changing the group of measurement positions is better than the best existing movement cost stored (if the movement cost of the group with the highest movement cost has decreased, or if the difference between the movement costs of the group with the highest movement cost and the group with the lowest movement cost has narrowed), the improved movement cost is updated and stored. If the movement cost calculated by changing the group of measurement positions is better than the best existing movement cost stored, the contents of the existing movement cost are retained.

In this way, the grouping of measurement positions and the calculation of movement costs are repeated to correct the calculation results, and the grouping of measurement positions and the measurement route of each group when the movement cost is finally optimized (the judgement in step S7 is NO) become the finalized contents. This finalized content becomes the finalized measurement route that allows each moving body 20 to reach the multiple measurement positions P1 to P12 with the minimum movement cost, and the information on the finalized measurement route is stored in the RAM of the command creation unit 10.

[Step S9: Step of issuing a command to a moving object]
In step S9, the autonomous movement operation command unit 13 transmits an operation command to each moving body 20 based on the confirmed measurement route (grouping of measurement positions and the measurement route of each group) calculated by the data processing unit 12. When the processing of the second sub-step of step S5 is being performed, the confirmed measurement route is the one calculated in the first sub-step, with the addition of movement order information for tracing the measurement route most efficiently.

For example, when the grouping is confirmed according to the contents of FIG. 8, a command is sent to one mobile body 20 to "move to the measurement positions of the first group (P1 to P5, P8) along a predetermined measurement route (determined to be the best in steps S6 and S7) and perform a scan with the 3D scanner 30 at each measurement position." A command is sent to another mobile body 20 to "move to the measurement positions of the second group (P6, P7, P9 to P12) along a predetermined measurement route (determined to be the best in steps S6 and S7) and perform a scan with the 3D scanner 30 at each measurement position." When the command is sent, the series of processes in the command creation unit 10 is completed, and the flow chart of FIG. 2 is exited.

Each moving body 20 receives commands from the command creation unit 10 at the data receiving unit 22. The autonomous movement command control unit 23 operates the travel drive unit 27 while referring to signals from the object sensor 25 and the inertial measurement device 26, and causes the moving body 20 to move along the measurement route specified by the command. When the moving body 20 reaches each measurement position on the measurement route, it stops moving, and the 3D scanner operation unit 24 controls the 3D scanner 30 to scan the object. When the scan is completed, it moves to the next measurement position based on the measurement route specification.

The above-mentioned processing in the data processing unit 12 of the command creation unit 10 determines the measurement route so as to reduce the difference in movement cost between groups and to suppress the movement cost of the group with the highest movement cost. Therefore, when multiple moving bodies 20 simultaneously acquire 3D scan data, the time required for the moving body 20 in charge of the group with the highest movement cost to complete all measurement work can be shortened. As a result, it is possible to improve the utilization efficiency of multiple moving bodies 20 and efficiently create 3D scan data. In addition, if the difference in movement cost between groups is set small, the influence over time such as time difference and weather difference is reduced when measuring with the 3D scanner 30 of each moving body 20, so there is an advantage that it is easy to digitize a common object under common conditions for each measurement position. As a result, the 3D scan data acquired by each moving body 20 can be synthesized with high accuracy.

As an example, a case where there are two mobile bodies 20 has been described, but the present invention can also be applied to a case where three or more mobile bodies 20 are used. Processing can be performed by changing the number of groups set in step S4 according to the number of mobile bodies 20.

As described above, the scan data creation method and scan data creation system disclosed herein make it possible to efficiently perform measurements at multiple measurement positions and obtain 3D scan data with excellent measurement accuracy and data synthesis operability.

The present invention is not limited to the above-described embodiment, and can be modified as appropriate without departing from the spirit of the invention.

For example, while the above embodiment shows a case where multiple mobile bodies 20 are operated, it may also be applied to a case where there is only one mobile body. In this case, the grouping of measurement positions in step S4 is skipped. Furthermore, the movement of measurement positions between groups in step S8 and the associated correction process of the calculation results are not performed. Then, it is possible to obtain the effect of improving work efficiency and data acquisition accuracy by moving a single mobile body along a measurement route with the minimum movement cost.

In addition, in the above embodiment, a case has been shown in which the number of moving bodies 20 to be used is predetermined, but it is also possible to use this as a means for determining the appropriate number of moving bodies 20 to be introduced when the number of moving bodies 20 to be used is undecided. By changing the number of moving bodies input in step S1, the subsequent processing can determine the travel cost of the best measurement route when the number of groups is different. Then, the number of moving bodies 20 to be used can be determined based on the criterion that provides the best average travel cost per number of bodies.

The above embodiment is applied to a scan data creation system 1 in which a 3D scanner 30 is mounted on an autonomously mobile body 20, and commands including a measurement route are sent from the command creation unit 10 to the mobile body 20. The present invention is particularly useful in such a system configuration, but can also be applied to cases where movement between measurement positions is performed by a means other than an autonomously mobile body. For example, the present invention can also be used in a mode in which an operator (human) holding a measuring device moves between measurement positions by walking or driving a vehicle. In this mode, the measurement route calculated by the command creation unit 10 is displayed on a mobile information terminal or paper medium, and the operator moves along the measurement route while referring to it.

In the above embodiment, a three-dimensional scanner 30 capable of measuring in all directions is used as the measuring device, which provides excellent work efficiency for measurements at each measurement position, but the measuring device is not limited to this. For example, a device such as a handheld scanner with a limited measurable angle of view may also be used as the measuring device. The number and positions of the measurement positions set in step S2 will differ depending on the angle of view of the measuring device.

In addition to scanners that irradiate a target with laser light or the like, it is also possible to use cameras that capture images of a subject without emitting light from the device itself as measuring equipment. The camera can be a spherical camera that can capture a 360-degree image, or a normal camera with a narrower angle of view.

In the above embodiment, in step S5, the shape (edges) of the measurement route is calculated in the first sub-step, and the movement order when tracing the measurement route is calculated in the second sub-step. Then, the measurement route is transmitted as an instruction to the moving body 20 with the contents including the movement order information determined in the second sub-step. Alternatively, it is possible to omit the second sub-step and transmit only the shape of the measurement route determined in the first sub-step to the moving body 20, without specifying the movement order when tracing the measurement route. The moving body 20 autonomously moves so as to memorize the parts of the measurement route that have already been traveled and automatically proceed to unexplored parts. Since the measurement route is determined as a minimum spanning tree in the first sub-step, even in this modified example, the minimum movement cost as the shape of the measurement route (when the return movement of the edges is not considered) can be realized.

Alternatively, in step S5, it is possible to carry out the second sub-step without changing the shape of the measurement route determined in the first sub-step. In other words, the measurement route determined in the first sub-step is maintained, and only the movement order along the measurement route is additionally determined. Specifically, in the above embodiment, the link destination of the measurement position P5 is changed from the state where the link destination of the measurement position P5 is the measurement position P4 (FIG. 7) to the state where the link destination of the measurement position P5 is the measurement position P2 (FIG. 8). However, such a route change within the group is not carried out, and the link destination of the measurement position P5 is maintained as the measurement position P4, and only the movement order of the links within the group is determined in the second sub-step. In this modified example, the shape of the measurement route is determined in the first sub-step, and the route is not changed within the group later, so that the processing load during calculation can be reduced.

The present invention can be used to create scan data that requires measurements at multiple measurement positions, and is particularly useful when scanning large measurement objects such as buildings and construction sites.

1 Scan data creation system 10 Command creation unit (calculation means)
11 Data receiving unit 12 Data processing unit 12a Measurement position calculation unit 12b Movable information calculation unit 12c Measurement position allocation calculation unit 12d Measurement route calculation unit 12e Calculation result evaluation unit 12f Calculation result correction unit 13 Autonomous movement operation command unit 20 Moving body 21 Computer 22 Data receiving unit 23 Autonomous movement command control unit 24 Three-dimensional scanner operation unit 25 Object sensor 26 Inertial measurement unit 27 Travel drive unit 30 Three-dimensional scanner (measurement device)
31 Measurement unit 32 Data storage unit 40 Building (target object)
41: outer wall 42: partition wall P1 to P12: measurement position

Claims (7)

1. A method for generating scan data for acquiring three-dimensional scan data for generating a three-dimensional digital model of an object, comprising:
A measuring device is provided for measuring an object.
a measurement position calculation step of calculating a plurality of measurement positions at which the object can be measured;
a measurement route calculation step of calculating a measurement route for causing the measuring device to reach the plurality of measurement positions with a minimum travel cost;
Do the following:
The scan data creation method is characterized in that in the measurement route calculation step, all edges that can logically reach each of the multiple measurement positions in the shortest distance are set, and the route in the minimum spanning tree calculated from all the edges that has the smallest total cost of edges that require a return to a branch is determined as the measurement route . 2. The scan data creation method according to claim 1 , wherein in said measurement route calculation step, a movement order for tracing said measurement route most efficiently is calculated and determined as a measurement route including movement order information. a measurement position classification step of classifying the plurality of measurement positions into a plurality of groups when the object is measured by a plurality of the measurement instruments;
a measurement route correction step of calculating the measurement route for each group in the measurement route calculation step, changing the measurement positions included in each group to calculate the measurement route, and calculating a grouping that minimizes the travel cost;
3. The scan data creating method according to claim 1 , further comprising: 4. The scan data creating method according to claim 3 , wherein in said step of correcting said measured route, correction is performed until a difference between the movement costs of the group with the highest movement cost and the group with the lowest movement cost is minimized. The measuring device is mounted on a moving body capable of autonomous movement,
A scan data creation method as described in any one of claims 1 to 4, characterized in that an instruction is sent to the moving body to move along the measurement route calculated in the measurement route calculation step, and measurement is performed by the measuring instrument at the measurement position included in the measurement route. A scan data creation system for acquiring three-dimensional scan data for creating a three-dimensional digital model of an object, comprising:
A measuring device for measuring an object;
a calculation means for calculating a plurality of measurement positions where the object can be measured, and calculating a measurement route for causing the measuring device to reach the plurality of measurement positions with a minimum travel cost;
a moving body that is equipped with the measuring device and is capable of moving autonomously, and that moves along the measurement route and performs measurement by the measuring device at the measurement position in response to a command from the calculation means;
having
The scan data creation system is characterized in that the calculation means sets all edges that can logically reach each of the multiple measurement positions in the shortest distance, and determines as the measurement route the route in the minimum spanning tree calculated from all the edges that has the smallest total cost of edges that require a return to a branch . A plurality of the moving bodies are provided,
7. The scan data creation system according to claim 6 , wherein said calculation means, when calculating said measurement route, divides said plurality of moving bodies into groups so that said plurality of moving bodies move between said plurality of measurement positions with a minimum movement cost.

Images