JP2016514310A - Image processing - Google Patents

Abstract

A method and apparatus for automatically generating a three-dimensional representation of a set of objects from point cloud data of the set of objects is described. The method and apparatus divides the space occupied by the object into a plurality of volumes. If a point in the volume approximately coexists on the surface, such a volume is designated as a surface volume. Surface volumes having approximately coplanar surfaces are combined to form a larger surface volume. If the points in the volume coexist roughly on the line, such a volume is designated as a line volume. Line volumes having approximately collinear lines are combined to form a larger line volume. [Selection] Figure 1

Description

  The present invention relates to a method and apparatus for automatically generating a set of three-dimensional representations of an object from a set of three-dimensional point cloud data.

The production of accurate three-dimensional (3D) computer models of real objects is very useful in the fields of archeology, architecture, civil engineering and mechanical engineering, and geographical mapping, as well as many other areas. I know that. In many of these applications, the scanner measures a large number of points on the surface of the object in order to generate a three-dimensional “point cloud” of the points on the surface. This group of points may contain a very large amount of data, and for other reasons as well as this, it is difficult to efficiently manipulate and process the final model. Therefore, it is beneficial to convert point cloud data into a format that can be more easily handled, for example, in a three-dimensional computer aided design (CAD) model format.

  The essence of point cloud data means that they have an analysis view that does not exist in other imaging technologies. For example, medical imaging techniques such as magnetic resonance imaging (MRI) and computed tomography (CAT) scans scan a specific volume and have a continuous density defined at all points within the scanned volume. Generate a 3D image from the values. For point clouds, however, the density of points is a function of distance and angle to the scanner position, and to scanner settings, rather than an indication of object density or other characteristics. In addition, the scanned high volume area may be completely devoid of any features.

  Currently, point cloud data is given by an expert (or team of experts) that explains the data by recognizing the structure and manually generates a 3D model of what is being identified (3D model). It has been. The process has several drawbacks. First, it requires a great deal of man-hours to complete and causes an increase in cost. Second, different people interpreting the same point cloud may generate different three-dimensional models. Users of such models can therefore not rely too much on their accuracy. This second difficulty is manifested in the case of noisy point cloud data resulting from the use of a movable scanner. Although they (point cloud data) are noisy, movable scanners are preferred over stationary scanners to scan the range of scanning techniques in question in a larger area.

Another device has been disclosed that claims to automatically generate a three-dimensional model, but it has other drawbacks. For example, U.S. Pat. No. 8,244,026 describes an apparatus (LIDAR) that performs light detection and ranging processing on a ground scan point cloud. The ground filter removes the ground so that features extending above the ground can be identified. Thereafter, an automatic feature search and recognition unit recognizes points associated with a feature and replaces them with virtual objects representing that feature. Such devices use the ground as a reference point and cannot be used for other applications. In addition, only the object for which there is a virtual object for that object can be replaced, and the expert will have to monitor the result or model manually and with more specific functions.

European Patent Publication No. 1,691,335 describes an apparatus for fitting a surface to a point cloud along a two-dimensional profile. The disadvantage here is that the profile must first be defined and does not form part of this invention either manually or by an automatic mechanism. In contrast, the present invention does not require a two dimensional or separate profile to be provided.

  ClearEdge 3D manufactures software that automatically extracts features from point clouds. This software uses the technique described in WO 2010/042466, where one or more surface sections are extracted from the point cloud and one or more principal axes of the object are Used to be determined. However, this method cannot be used when the scanned object does not have a common aligned principal axis, particularly when analyzing data generated by a movable scanner. In fact, the clear edge 3D requires the user to manually define the first version of the feature, and those copies are then automatically identified.

  The claimed aspects of the invention provide, but are not limited to, computational efficiency and useful labor-saving solutions, where superior features are identified as real objects and virtually equivalent Provide scenarios that are exchanged for things. In addition, exemplary embodiments of the present invention are sufficiently stable to convert point cloud data from a movable scanner system.

The present invention requires frequent calculation of the eigenvalues of the 3 × 3 symmetric matrix and the corresponding eigenvectors. This is for example described in G.I. H. Golub and C.I. F. It can be easily solved using Jacobian diagonalization, as described by van Loan in “Matrix Computations”, 1983, John Hopkins University News. However, any other valid eigenvalue and eigenvector calculation method can be used instead if it can accurately handle two or all eigenvalues not different from others.

  The invention is defined by the appended claims. Other features and advantages of exemplary embodiments of the present invention will become apparent from the following description taken in conjunction with the accompanying drawings.

It is explanatory drawing which shows the typical system by which point cloud data are produced | generated and converted into a three-dimensional model. It is a flowchart of the main steps from M1 to M12 of the method. FIG. 6 is a flowchart of steps A1 to A8 of an exemplary method for classifying cubes that contain points that are coplanar or collinear. FIG. 4 is a flowchart of steps B1 to B24 of an exemplary method for identifying surfaces by combining coplanar cubes along a common plane to form a planar cube set. FIG. 10 is a flowchart of steps Y1 to Y8 of an exemplary method for flattening cubes belonging to a planar cube set such that they all intersect by a common plane. FIG. 6 is a flow chart of steps X1 through X10 of an exemplary method for identifying cubes that form the boundaries of a planar cube set. FIG. 10 is a flowchart of steps Z1 to Z21 of an exemplary method for tracking boundary polygons around an outer or inner hole of a planar cube set. FIG. 6 is a flowchart of steps U1 to U11 of an exemplary method for identifying the position of a group boundary point along a boundary polygon. FIG. 7 is a flowchart of steps V1 to V14 of an exemplary method for moving a group boundary point on an intersection having adjacent planes. FIG. 6 is a flow chart of steps W1-W24 of an exemplary method for identifying straight lines by joining collinear cubes along a common line to form a line cube set. FIG. 9 is a flowchart of steps T1 to T8 of an exemplary method for flattening cubes belonging to a line cube set such that all intersect by a common line. 12 is a flowchart of steps S1 to S16 of an exemplary method for finding the position of an end of a finite line segment from within a line cube set. FIG. 6 is a plan view illustrating an exemplary method for calculating the distance between planes. FIG. 3 is a plan view showing a typical polygon fan. FIG. 6 is a plan view illustrating an exemplary method for tracking boundary polygons of a planar cube set. It is a top view which shows the position of two choices of the next edge part of a polygon. It is a top view which shows the typical method for calculating a group boundary point in case a point group boundary is linear within an intersection polygon. It is a top view which shows the typical method for calculating a group boundary point in case a point group boundary is nonlinear within an intersection polygon. It is a top view which shows the typical method for calculating a group boundary point in case there exist two or more candidate group boundary points. FIG. 6 is a perspective view showing an exemplary method for moving group boundary points on a plane intersection. FIG. 6 is a diagram using a structural scenario obtained by performing the method described herein on a specific set of point cloud data.

FIG. 1 is a block diagram illustrating the general preparation of an apparatus according to an exemplary embodiment of the present invention. The scanner 120 includes a LIDAR scanning module 102 that emits a series of laser pulses. These laser pulses are scanned across the surface of the object of interest 104 and the pulses are reflected off the surface and received by the scanning module sensor. The processing module 106 of the scanner 120 may calculate the distance from the time of flight of the laser pulse to a point on the surface and may generate a point cloud based on this distance data. The point cloud data 108 is then stored in the point cloud database 110 before further processing. If further processing is required, the point cloud data is sent to the computer 112 and the computer's point cloud processing module performs a method of converting the data into a 3D representation 118. One embodiment of such a method is described in detail below. Once the method is complete, the three-dimensional display 118 may be stored as a data file in the memory 114 and / or output in a visible manner.

  There are various applications in which such a three-dimensional display can be used. For example, in a car assembly line scenario, various parts designed to fit together may be scanned by a LIDAR scanner. The resulting point cloud can be converted to a three-dimensional vector model to determine whether the parts can fit each other within individual tolerances. Achieving accurate results using conventional techniques such as those described above without the automated techniques described herein required a significant amount of man-hours and was not feasible within the required time axis.

Another application relates to guardrails along the road. Many public bodies require a minimum height for guardrails on high-speed traffic roads. In order to ensure compliance with this requirement, the onboard scanner can be scanned in many areas of the road to generate point cloud data for the guardrail. This data can be converted into a three-dimensional model to determine the rail height. Again, the manual method for converting data to a vector graphic model takes a long time. However, the problem is exacerbated because different manual workers often determine different heights for rails in the same area. Groups with different vested benefits may provide the resulting model to fit data that is a more favorable fact for the modeller, whether intentionally or not. If the model determiner determines a sufficiently high individual guardrail, but the result is incorrect, the results can be disastrous. Therefore, an objective method as described below is preferable.

点群の点が１または２以上の三次元物体の表面に分布していると仮定する。この明細書に記載されている技術は、点群を物体のＣＡＤモデル表示に変換することである。これらは、閉じた平面ポリゴンの端部（物体の平面を表す）を有する線区画、および電力線、電話線のような平坦な平面を有しない物体を表している別の線区画、に接続されたセットから構成されている。（例えばパイプやトンネルのように）円筒のような非平面の表面を構成する物体は、物体の表面の接線方向である十分な数の小さな平面によって表される。本方法によって、どのような三次元物体でも表すことができる。

Assume that the points of the point group are distributed on the surface of one or more three-dimensional objects. The technique described in this specification is to convert a point cloud into a CAD model representation of an object. They were connected to a line segment with the end of a closed planar polygon (representing the plane of the object), and another line segment representing an object that does not have a flat plane such as a power line, telephone line It consists of a set. An object comprising a non-planar surface such as a cylinder (such as a pipe or tunnel) is represented by a sufficient number of small planes that are tangential to the surface of the object. Any three-dimensional object can be represented by this method.

  FIG. 2 is a flowchart showing the main steps M1 to M12 of the method.

<M1>
Superimposing a three-dimensional lattice on the position of the space occupied by the object. The grid partitions the space into a list of large but finite cubes. To avoid wasting computer storage space, the list excludes any empty cubes. In the current embodiment, the cubes are all the same size. The length of the side of each cube is called its resolution. If necessary (for example, a partially scanned surface has a very large curvature), some of these cubes can be subdivided into smaller cubes, which can be further subdivided You can also do it. In this way, different local resolutions can be used on different planes. Another segmentation of the three-dimensional space can also use, for example, a tetrahedron. In the following, the term cube can be taken to mean tetrahedron or another space-filled mosaic process.

<M2>
Steps to classify each non-empty cube as follows: a matching cube (all points in the cube are located at approximately the same position), a coplanar cube (all points in the cube are approximately Existing in one plane), or a collinear cube (all points in the cube are approximately along one line), or a space-filled cube (locally a point) Groups are neither lines nor surfaces). Details of step M2 will be described in more detail in the following steps A1 to A8 shown in FIG.

<M3>
Growing a planar cube set by joining adjacent coplanar cubes whose planes (the planes of the points of the point cloud) are approximately coplanar. Each planar cube set is associated with a single mathematical plane called the common plane of the cube set. At the end of step M3, all coplanar cubes completely belong to one planar cube set. Each planar cube set includes one or more coplanar cubes. Details of step M3 will be described in more detail in the following steps B1 to B24 shown in FIG.

<M4>
Flatten each planar cube set as follows: If no coplanar cube is intersected by the common plane of the planar cube set, the cube is removed from the planar cube set and all its points are projected onto the common plane. If any projected point exists in a cube that does not already belong to the planar cube set, add that cube to the planar cube set. This means that at the end of step M4, the planar cube set may also include cubes that were not classified as coplanar cubes in step M2. A cube may currently belong to more than one planar cube set. However, any cube that belongs to more than one planar cube set is intersected by a common plane of all planar cube sets to which it belongs. Details of step M4 will be described in more detail in the following steps Y1 to Y8 shown in FIG.

<M5>
Each planar cube set generates a planar boundary cube set. This consists of all the cubes on the boundary of the planar cube set. Details of step M5 will be described in more detail in the following steps X1 to X10 shown in FIG.

<M6>
The boundary polygons of each planar cube set are in turn around the outside of the planar cube set and around any hole inside the planar cube set, using the end of the cube belonging to the planar cube boundary set. The tracked step. Details of step M6 will be explained in more detail in the following steps Z1 to Z21 shown in FIG.

<M7>
A group boundary point is estimated for each end of each boundary polygon. Group boundary points are different from boundary polygons, and their ends exist along the surface of the cube, and each group boundary point is a convexity of a point cloud point projected on the common plane of each plane cube set. It exists in close proximity to the convex hull. The group boundary points are stored in the order in which each separate boundary polygon calculated in step M6 is encountered. Details of step M7 will be explained in more detail in the following steps U1 to U11 shown in FIG.

<M8>
If any group boundary point exists sufficiently close to the intersection of a common plane with another planar cube set, the position of that group boundary point is moved to the closest point on the line of intersection. If the group boundary point exists sufficiently close to an intersection having two or more planes, the group boundary point is moved to the closest point of the intersection. Details of step M8 will be described in more detail in the following steps V1 to V14 shown in FIG.

<M9>
Converting the edges of the boundary polygons into polylines composed of different group boundary points in the order in which they are stored at the end of step M8. Separate polylines are created for each boundary polygon.

<M10>
Adjoining collinear cubes whose lines are approximately collinear are combined to form a line cube set. Each line cube set is associated with a single mathematical line called the common line of that cube set. At the end of step M10, all collinear cubes completely belong to one line cube set. Each line cube set includes one or more collinear cubes. Details of step M10 will be described in more detail in the following steps W1 to W24 shown in FIG.

<M11>
Flatten each line cube set as follows: If no collinear cube is intersected by the common line of the line cube set, the cube is removed from the line cube set and all its points are projected onto the common line. If any projected point is in a cube that does not already belong to the line cube set, add that cube to the line cube set. This means that at the end of step M11, the line cube set may also contain cubes that were not classified as collinear cubes in step M2. A cube may belong to more than one line cube set. (In fact, a cube may belong to a line cube set and a planar cube set simultaneously.) However, any cube that belongs to two or more line cube sets intersects with a common line of all the line cube sets to which it belongs. Is done. Details of step M11 will be described in more detail in the following steps T1 to T8 shown in FIG.

<M12>
Identifying the end points of one or more line segments along a common line of each line cube set. Details of step M12 will be described in more detail in the following steps S1 to S16 shown in FIG.

As already mentioned, the end result of this process is therefore the production of polygons with fully defined boundaries as well as other line areas. Further processing may be performed, identified as defined as part of the edge of the object, adjacent to the polygon boundary that satisfies the individual requirements. A full three-dimensional object can be reconstructed by combining more and more polygons with sufficient data in this way. When this is achieved, the object can be identified as its important features and data regarding the number and location of important features, and additionally provide other relevant information to the user of the 3D model. it can. It is very inefficient to identify or compare objects directly from point cloud data. For example, if an object's point cloud contains 10 ⁶ points, comparing two such objects would require 10 ¹² computations (each computation of an object's point cloud Compare one of the points with another object that has a similar number of points). On the other hand, if the same object is represented by a model consisting of a small number of polygons (eg 100 polygons), much less computation is required (eg 10,000). The process is computationally much more efficient. In a street scene model, common street furniture may be identified by their shape (polygon combination). They can be exchanged with accurate virtual models or data regarding the location of street furniture that can be extracted by the parties. If parallel photographic images are available to create a three-dimensional image, the resulting image portion may be associated with each polygon that fills the surface.

  FIG. 3 is a flowchart of step M2 showing steps A1 to A8 for classifying each cube (created in step M1) as follows. An empty cube (the cube does not contain any points), a matching cube (all the points of the cube are located at approximately the same position), a coplanar cube (all the points of the cube are approximately 1) Lies in one plane.), Collinear cube (all the points of the cube are approximately along one straight line), or space-filled cube. In all cases, if a point in a point cloud is exactly on a face or vertex between two or more cubes, only one of those cubes is considered to contain that point. Please note.

Mathematical surfaces and lines are zero in thickness. Since point clouds suffer from measurement errors and other fluctuations, collectively referred to as noise, the points of the point cloud themselves may exist a little away from the true mathematical surface or line that represents them. To allow this, the calculations described in steps A1 to A8 make use of thickness tolerances. Its optimal value depends on the accuracy of the point cloud.

  The classification process is as follows.

<A1>
The step of selecting the first cube in the list of non-empty cubes.

<A2>
Calculating the three eigenvalues of the covariance matrix of the points of the points contained in the cube using the Jacobi method, or any other valid method. Set any negative eigenvalues to zero. If there is exactly one point in the cube, all three eigenvalues are set to zero.

<A3>
If all eigenvalues are less than the thickness threshold, classify the cube as consistent and proceed to step A7. This happens when all the points in the cube roughly match.

<A4>
If only two of the eigenvalues are smaller than the thickness tolerance, classify as a collinear cube and proceed to step A7. This happens when all points in the cube are approximately along the same mathematical line.

<A5>
If only one of the eigenvalues is smaller than the thickness tolerance, it is classified as a coplanar cube and the process proceeds to step A7. This occurs when all the points of the cube are approximately in the same mathematical plane.

<A6>
Classify the cube so that it fills the space. This occurs when non-empty cubes are not coincident cubes, collinear cubes, and coplanar cubes.

<A7>
If the cube is at the end of the list, stop.

<A8>
Select the next cube in the list and proceed to step A2.

FIG. 4 is a flowchart of step M3 for growing a set of adjacent coplanar cubes along a common plane, as shown in the following detailed steps B1 to B24. Each set of coplanar cubes grown in this way is called a planar cube set.

ここでｕは、共通平面に垂直である単位長のベクトルであり、累積された共分散行列Ｖのユニークな最小の固有値に対応する累積された共分散行列Ｖの固有ベクトルに等しい。

Where u is a vector of unit length perpendicular to the common plane and is equal to the eigenvector of the accumulated covariance matrix V corresponding to the unique minimum eigenvalue of the accumulated covariance matrix V.

  In steps B14 and B21 of the method, a plane adapted to pass the current accumulated common plane through the current coplanar cube l to determine whether the two planes are coplanar; Compare. Different criteria are used in the two steps.

Criterion B is used in step B21 and requires:

  The actual steps of the planar growth process are as follows.

<B1>
Creating an unused list of cubes containing all of the coplanar cubes identified in step M2. Any cube in this list is called an unused cube.

<B2>
Step to stop if the unused list is empty.

<B3>
The step of creating an empty list of cubes called a planar cube set. This planar cube set is grown to include all coplanar cubes along the common plane of the cubes in the planar cube set. Eventually, even if the planar cube set contains only one cube, all cubes currently in the unused list of cubes are moved to the planar cube set.

<B4>
Setting the current cube to the first cube in the list of unused cubes.

<B5>
Creating an empty list of cubes called a candidate list. This list will include unused coplanar cubes that are considered candidates for inclusion in the planar cube set.

<B6>
The step of creating an empty list of cubes called a special list. This list will contain unused coplanar cubes that have recently been rejected as candidates for inclusion in the planar cube set.

<B7>
The step of moving the current cube from the unused list into the planar cube set. Thus, every planar cube set includes at least one cube.

<B8>
Setting the sum of points in a planar cube set to be equal to the sum of points in the current cube.

<B9>
Setting the total cross product of points in a planar cube set to be equal to the sum of cross products of points in the current cube.

<B10>
Adding all adjacent cubes of the current cube that are in the unused list to the candidate list. Here, a cube is adjacent to the current cube if it shares a face or vertex with the current cube.

<B11>
If the candidate list is empty, the process proceeds to step B18.

<B12>
Setting the current cube to the first cube in the candidate list.

<B13>
The step of removing the current cube from the candidate list.

<B14>
If the current cube does not meet criterion A, add the current cube to the special list and proceed to step B11.

<B15>
Move the current cube from the unused list to the planar cube set.

<B16>
Adding the sum s _l of the points in the current cube l to the accumulated total s of the points in the planar cube set.

<B17>
Adding the sum of the outer products W ₁ of the points in the current cube 1 to the accumulated total W of the outer products of the points in the planar cube set and proceeding to step B 10.

<B18>
If the special list is empty, output the plane cube set data and proceed to step B2.

<B19>
Setting the current cube to the first cube in the special list.

<B20>
A step that removes the current cube from a special list.

<B21>
If the current cube does not satisfy criterion B, proceed to step B18.

<B22>
The step of moving the current cube from the unused list to a planar cube set.

<B23>
Adding the sum s _l of the points in the current cube l to the accumulated total s of the points in the planar cube set.

<B24>
Adding the sum W ₁ of the outer products of the points in the current cube l to the accumulated total W of the outer products of the points in the planar cube set and proceeding to step B18.

  FIG. 5 is a flowchart of step M4, shown in detail in steps Y1 to Y8, applied to each cube in the planar cube set to ensure that all cubes in the planar cube set are intersected by their common plane. It is. The effect of step M4 is to flatten the planar cube set. Step M4 is necessary because the common plane changes each time a new cube is added to the plane cube set in step M3. In the growth process of a planar cube set, there is no guarantee that the initially added cube will continue to be intersected by the common plane after the common plane has changed. Step M4 compensates for this. Steps Y1 to Y8 are applied separately to all cubes in the planar cube set, so they can be applied in parallel if necessary.

  The process steps in which the planar cube set is planarized are as follows.

<Y1>
Stop if the cubes are intersected by a common plane.

<Y2>
The step of removing a cube from a planar cube set.

<Y3>
Setting the current point to a point in the first point cloud in the cube;

<Y4>

<Y5>
Finding a cube that contains projected points. This cube is called a projected cube. The exact details of this calculation depend on how the cube is arranged in space. In one example, cubes are arranged in rows, columns, and layers.

<Y6>

<Y7>
Stop if the current point is the last point cloud point in the cube.

<Y8>
Setting the current point to the next point group point in the cube and proceeding to step Y4.

  FIG. 6 is a flowchart of step M5, details in steps X1 to X10, to identify members of a planar cube set that have adjacent cubes that do not belong to the planar cube set but are intersected by a common plane. Applied. The identified cubes are stored in a planar boundary cube set. At the stage where step M5 is applied, each planar cube set is flattened because all of those cubes are intersected by a common plane.

<X1>
Steps to create an empty plane boundary cube set.

<X2>
Stop if the planar cube set is empty.

<X3>
Setting the current cube to the first cube in a planar cube set.

<X4>
Generating a list containing 18 cubes orthogonal to and adjacent to the current cube; Here, an orthogonally adjacent cube means a cube that shares a plane or end with the current cube. Note that cubes that share only one vertex with the current cube are not orthogonally adjacent cubes.

<X5>
Setting the test cube to the first cube in the list of cubes that are orthogonally adjacent.

<X6>
If the test cube is a member of a planar cube set, proceed to step X8.

<X7>
If the common plane intersects the test cube, add the current cube to the plane boundary cube set and proceed to step X9.

<X8>
If the test cube is not the last cube in the list of adjacent orthogonal cubes, set the test cube to the next member of the list and proceed to step X6.

<X9>
Step to stop if the current cube is the last cube in a planar cube set.

<X10>
Set the current cube to the next cube in the planar cube set and proceed to step X4.

FIG. 7 is a flowchart of step M6 showing details in sub-steps Z1 to Z21 applied to track the boundary polygon of each planar cube set. At the stage where step M6 is applied, each planar cube set is flattened so that all of those cubes intersect their common plane. A common plane intersection having any cube that intersects the common plane (including cubes that do not belong to a plane cube set) is a convex polygon called a cube intersection polygon. Any two cubes that are intersected by a common plane must be said to be adjacent cubes on the same plane if their intersecting polygons share at least one common end. Note that cubes with intersecting polygons are not adjacent on the same plane if they share only one vertex. For example, in FIG. 14, the polygons D ₀ C ₀ P ₀ and C ₀ B ₀ Q ₀ are adjacent on the same plane as the polygons A ₀ B ₀ C ₀ D ₀ E ₀ , but the polygon C ₀ Q ₀ P ₀ Are not adjacent.

A polygonal fan is a series of two or more polygons, each of which is placed consecutively around a central vertex that shares a common end with the next polygon in the list, except perhaps at the end. It is a list of convex polygons. For example, in FIG. 14, the polygons C ₀ D ₀ E ₀ A ₀ B ₀ , C ₀ B ₀ Q ₀ , C ₀ Q ₀ P ₀ , and C ₀ P ₀ D ₀ are four with respect to the central vertex C ₀ . Has a polygon fan consisting of members. The common ends are C ₀ B ₀ , C ₀ Q ₀ , and C ₀ D ₀ . Similarly, in FIG. 15, polygons GHO and GOB
, And GBF have a polygon fan consisting of three members with respect to the central vertex G. The common ends are GO and GB.

  Briefly described below, the intersecting polygons of a cube belonging to a planar cube set are called internal polygons, and the rest are called external polygons. The intersecting polygons of all the cubes in the plane boundary cube set are inner polygons, and are polygons adjacent on the same plane of at least one outer polygon. The end shared between the inner polygon and the outer polygon is called the outer end. They form one or more adjacent (but not necessarily convex) polygons called boundary polygons in a planar cube set. The continuous edge of the boundary polygon is the continuous edge of a polygon fan whose members are all internal polygons. It is these boundary polygons that are tracked by step M6.

  A planar cube set has one or more holes in the planar cube set and / or a cube of the planar cube set is cut from another part of the same cube set 1 or 2 If the above portions are formed or connected to each other only by a common vertex, it has two or more boundary polygons. An example is shown in FIG. Here, all the polygons are triangles to simplify the drawing. All shaded polygons are internal polygons. The unshaded polygon is an external polygon that is a polygon adjacent on the same plane of at least one internal polygon. All shaded polygons except OIK, OKC, and OBG are also members of the planar boundary cube set. In FIG. 15, there are three boundary polygons, ABC, DEFGHIJKLMN, and PQF. The end portions EF and FP are not continuous ends of the same boundary polygon. This is because the intersecting polygons EFB and PQF are not members of a single polygon fan, all of which are internal. On the contrary, the end portions HG and GF are continuous end portions of a polygon fan composed of three members formed by the polygons GHO, GOB, and GBF. Similarly, end portions AB and BC are continuous end portions of a polygon fan composed of five members formed by polygons BAE, BEF, BFG, BGO, and BOC.

  The edge of the boundary polygon is tracked as follows. This is also referred to FIG.

<Z1>
Creating an empty list of boundary polygons.

<Z2>
Stop if the planar bounding cube set is empty.

<Z3>
Selecting the first cube in the planar cube set as the current cube.

<Z4>
Mark all external edges in the intersecting polygon of the current cube as unused.

<Z5>
If the current cube is not the last in the planar bounded cube set, set the next cube in the set as the current cube and proceed to step Z4. Steps Z4 and Z5 loop through all the cubes in the planar bounding cube set, ensuring that all external ends of their intersecting polygons are marked as unused.

<Z6>
Creating a new empty boundary polygon. A boundary polygon is a list of external edges that are now increased in the order they are tracked around one boundary of a common plane.

<Z7>
Selecting the first cube in the planar bounded cube set as the current cube.

<Z8>
Selecting any unused external edge in the intersecting polygon of the current cube as the current edge.

<Z9>
Naming the two nodes at the current end as A and B. The end is processed as starting at node A and ending at node B. The selection of the end direction is arbitrary here.

<Z10>
Adding the current edge to the boundary polygon. Also, storing the cube containing the current end for use in steps U2 and U7.

<Z11>
Marking the current edge as used.

<Z12>
Finding the end of the next polygon in the intersecting polygon of the current cube. This is the unique end (not AB) of the current polygon, with B as one of its nodes. Name another node at the end of the next polygon as C. As shown in FIG. 16, the position of the next end depends on the position of the B node that is the node at the current end.

<Z13>
If the next end is an external end, go to step Z18.

<Z14>
Remove the current cube from the planar bounded cube set if the polygon intersection of the current cube does not leave any unused outer edges.

<Z15>
Setting the current cube to a unique coplanar adjacent cube whose intersecting polygon includes the next end BC.

<Z16>
Setting the next end to another end in the current cube with node B as one of its nodes. Name another node C.

<Z17>
If the next end is not an external end, go to step 15; otherwise go to step Z18. Steps Z15 to Z17 loop over the polygon fan until it finds a fan member having an external end connected to the central vertex of the fan. For example, assume that at the start of step Z15, the end HG in FIG. 15 is the current end and therefore GO is the next end. Note that step Z13 has already been tested and GO is not the external end. In step Z15, the current intersecting polygon is set in GOB. In step Z16, the next end is set to GB. In step Z17, GB is also not an external end, so that the operation returns to step Z15. In step 15, the current intersecting polygon is set in GBF, and the next end is set in GF in step Z16. At that time, since the next end GF is finally the external end, in step Z17, an action to escape from the loop is caused. On the other hand, if the current end is GF and the next end is FB at the start of step Z15, the current intersecting polygon is set to FBE in step Z15, and the next end is set to FE in step Z16. Since this FE is an external end, it immediately exits the loop at step Z17. As a final example, assume that at the start of step Z15, the current end is AB and the next end is BE. At that time, in step Z15, the current intersecting polygon is set in BEF, and in step Z16, the next end is set in BF. Since BF is not an external end, step Z17 causes an action of returning to step Z15. Steps Z15 to Z17 are repeated, considering the ends BG and BO in turn, but since none of them are external ends, it is the external end BC when exiting the loop thereafter.

<Z18>
If the next end is not the same as the first end in the boundary polygon, the current end is set as the next end and the process proceeds to step 10.

<Z19>
If the polygon intersection of the current cube has any unused ends left, removing the current cube from the planar boundary cube set.

<Z20>
Adding a boundary polygon to the list of boundary polygons.

<Z21>
If the plane bounding cube set is not empty, go to Z6, otherwise stop.

  FIG. 8 is a flowchart of step M7 showing details in steps U1 to U11 applied to calculate the position of the group boundary point. Steps U1 to U11 are applied to each separate boundary polygon calculated in step M6. The A and B nodes required in steps U4 and U8 can be stored in step M6, or else the previous and next vertex vertices in the boundary polygon Note that they can be estimated by comparing.

<U1>
Setting the current edge to the first edge in the boundary polygon.

<U2>
Setting the current cube to the cube where the current end exists. The identity of the cube located at any end is stored in step Z10 when the boundary polygon is tracked. The cube is a member of a planar cube set.

<U3>
Setting the current edge to the leading edge.

<U4>
Setting P to the A node at the current end;

<U5>
If the current end is the last end in the boundary polygon, go to step U8.

<U6>
Obtaining the next edge from the boundary polygon.

<U7>
If the next end is located in the current cube, setting the current end to the next end and proceeding to step U6. The identity of the cube located at any end is stored in step Z10 when the boundary polygon is tracked. Steps U6 and U7 are repeated until the current end is the last end in the current cube.

<U8>
Set Q to the B-node at the current end.

ここで、ｑは線ＰＱのいかなる点でもよく（最も簡単にはＰまたはＱ）、ｖはＰＱに対する垂線であって共通平面に置かれてあり、単位長を有している。−ｖもまた、これらの条件を満足することを注記する。ｖおよび−ｖの正しい選択は、ｄ_kがまた、境界ポリゴ
ンの頂点である現在の交差ポリゴンのいかなる頂点に対しても負ではないこと、と、ｄ_k
がいかなる他の頂点に対しても正ではないこと、を検査することによってなされる。そのしるし（sign）が識別できるように、ｄ_kがゼロではない交差ポリゴンの少なくとも１つ
の頂点が常に存在している。ステップＵ９の幾何学的形状を図１７から図１９に示す。これら３つの図の全てにおいて交差ポリゴンは、ＰＣＱＢＡであり、境界ポリゴンの端部はＱＢ、ＢＡ、およびＡＰである。頂点Ｃのみが境界ポリゴンに置かれていない。法線ベクトルｖは、ｄ_kが増加する方向に示される。点群は、陰影を付した領域によって表されて
いる。投影された点群の点は、Ｘでマーク付けされた有向距離を最大化し、ＫＬは、ＰＱに平行であるＸを通る線である。 <U9>
Setting a group boundary point at a point of the point group projected with the maximum directional distance to the line PQ. The points of the point group are projected on the plane using the formula of step Y4.

Where q can be any point on the line PQ (most simply P or Q), and v is a normal to PQ, placed in a common plane and having a unit length. Note that -v also satisfies these conditions. The correct choice of v and -v is that d _k is also negative for any vertex of the current intersecting polygon that is also the vertex of the boundary polygon, and d _k
Is done by checking that is not positive for any other vertex. There is always at least one vertex of the intersecting polygon where d _k is not zero, so that the sign can be identified. The geometric shape of step U9 is shown in FIGS. In all three figures, the intersecting polygon is PCQBA, and the end of the boundary polygon is QB, BA, and AP. Only vertex C is not placed on the boundary polygon. The normal vector v is shown in the direction in which d _k increases. A point cloud is represented by a shaded area. The points of the projected point cloud maximize the directed distance marked with X, and KL is a line through X that is parallel to PQ.

<U10>
If there is another projected point group point in the intersecting polygon that is close to the straight line passing through the group boundary point and parallel to the PQ, the parallel line passing through the position of the group boundary point calculated in step U9 Set the group boundary point to the average of all projected point cloud points that are close enough. Here, “close enough” means any point in the projected point cloud whose distance to the parallel line is less than the specified tolerance, which must be small fluctuations. It can be said that the resolution is 1/4 or 1/10. The geometric shape of step U10 is shown in FIG. 19, where KL is the end of the projected point cloud. Assuming that the points in the point group are evenly distributed, the average of the points in PCQBA that are sufficiently close to KL is approximately X.

<U11>
If the current end is not the last end in the boundary polygon, the current end is set as the next end in the boundary polygon, the process proceeds to step U2, and the rest stops.

  FIG. 9 is a flowchart of step M8 showing details in steps V1 to V14 applied to move the group boundary point to the line intersection between the pair of common planes.

<V1>
Creating a list of common planes for all planar cube sets. This list contains normal vectors and includes means for a common plane.

<V2>
Stop if the common plane list is empty.

<V3>
Setting the current plane to the first common plane in the common plane list.

<V4>
Setting the current group boundary point to the first group boundary point in the current plane; Group boundary points can be listed in any order for the purpose of step M8. In particular, it is not necessary to distinguish between group boundary points associated with different boundary polygons.

<V5>
Setting the minimum distance to infinity. Here, infinity means any positive number that is guaranteed to be greater than the distance between the group boundary point and any common plane. A suitable value for infinity is 10 to the 30th power.

<V6>
Setting an adjacent plane to the first common plane in the list of common planes.

<V7>
If the adjacent common plane is the same as the current plane, proceed to step V11.

<V8>
If the angle between the normal vectors of the current adjacent planes is sufficiently small (less than 1 degree), go to step 11. The purpose of this test is to prevent meaningless calculations for the intersection of nearly parallel planes.

<V9>

<V10>
If the distance D between the current group boundary point and its projection is less than the minimum distance, the minimum distance is set to D
And set the best projected point to the current projected point.

<V11>
If the adjacent plane is not the last plane in the common plane list, set a plane adjacent to the next plane in the common plane list and proceed to step V7.

<V12>
If the minimum distance is sufficiently small, move the current group boundary point position to the best projected point position and proceed to step V13. Here, “sufficiently small” means a small fluctuation, that is, a fluctuation that can be said to be about 1/4 or 1/10 of the resolution. In FIG. 20 showing the geometric plane, ABCD is the common plane of the individual plane cube sets, and DCFE and ADEG are the two neighboring plane cube sets that intersect the common plane ABCD along DC and AD. Common plane. Dashed lines MN and KL indicate the distance that is parallel to DC and AD and that the point is considered sufficiently close to the intersection line. Points P ₁ , P ₂ , P ₃ , and P ₄ are exemplary positions of group boundary points. The distances from P ₂ and P ₄ to DC are small enough that they (P ₂ and P ₄ ) are moved their projections onto Q ₂ and Q ₄ . The group boundary point P ₁ is sufficiently small for both DC and AD. However, it is moved to Q ₁ because it (P ₁ ) is closer to AD. On the other hand, P ₃ is not moved because it is not close enough to both intersections.

<V13>
If the current group boundary point is not the last group boundary point in the list of group boundary points for the current plane, the current group boundary point is set to the next group boundary point in the list, and the process proceeds to step V5 .

<V14>
If the current plane is not the last in the list of common planes, set the current plane to the next plane in the list of common planes and go to V3, otherwise stop.

FIG. 10 is a flowchart illustrating steps W1 to W24 for growing a set of adjacent collinear cubes that are intersected by a common line (referred to as a common line). Each set of collinear cubes grown in this way is called a line cube set.

  In steps W14 and W21 of the method, to determine whether two straight lines exist on the same straight line, a mathematical straight line along the current accumulated line cube set is converted to the current straight line cube. Compare with a straight line fitted through l. Different criteria are used in the two steps.

基準Ａは、ここではｕが共通平面の基準ベクトルではなく、共通線に沿ったベクトルであることを除いては、ステップＢ１４で用いた基準Ａと同一である。図１３は、この観点から再解釈されてもよい。

The reference A is the same as the reference A used in step B14 except that u is not a common plane reference vector but a vector along a common line. FIG. 13 may be reinterpreted from this point of view.

<W1>
Creating an unused list of cubes including all collinear cubes identified in step M2. Any cube in this list is called an unused cube.

<W2>
Step to stop if the unused list is empty.

<W3>
The step of creating an empty list of cubes called a line cube set. The line cube set is grown to include all collinear cubes that are intersected by a common line. Eventually, all cubes currently in the unused list of cubes are moved to the line cube set even if the line cube set contains only one cube.

<W4>
Setting the current cube to the first cube in the unused list.

<W5>
Creating an empty list of cubes called a candidate list. This list includes unused collinear cubes that are considered candidates for inclusion in the line cube set.

<W6>
The step of creating an empty list of cubes called a special list. This list includes unused collinear cubes that have been recently rejected as candidates for inclusion in the line cube set.

<W7>
The step of moving the current cube from the unused list to the line cube set. Thus, every line cube set includes at least one cube.

<W8>
Setting the total of points in a line cube set to be equal to the sum of points in the current cube.

<W9>
Setting the total cross product of points in a line cube set to be equal to the sum of cross products of points in the current cube.

<W10>
Adding all adjacent cubes of the current cube in the unused list to the candidate list. Here, if a cube shares a face or vertex with the current cube, the cube is a cube adjacent to the current cube.

<W11>
If the candidate list is empty, the process proceeds to step W18.

<W12>
Setting the current cube to the first cube in the candidate list.

<W13>
Removing the current cube from the candidate list.

<W14>
If the current cube does not meet criterion A, add the current cube to the special list and proceed to step W11.

<W15>
The step of moving the current cube from the unused list to the line cube set.

<W16>
Adding the sum s _l of the points in the current cube l to the accumulated total s of the points in the line cube set.

<W17>
Adding the sum W ₁ of the outer products of the points in the current cube l to the accumulated total W of the outer products of the points in the line cube set and proceeding to step W10.

<W18>
If the special list is empty, output line cube set data and proceed to step W2.

<W19>
Setting the current cube to the first cube in the special list.

<W20>
The step of removing the current cube from the special list.

<W21>
If the current cube does not satisfy criterion C, the process proceeds to step W18.

<W22>
The step of moving the current cube from the unused list to the line cube set.

<W23>
Adding the sum s _l of the points in the current cube l to the accumulated total s of the points in the line cube set.

<W24>
Current cross product sum W _l step proceeds to step W18 by adding to the accumulated sum W of the cross product of the points in the line cube set of points in the cube l.

  FIG. 11 is a flowchart of step M11 showing details in steps T1 to T8 applied to each cube in the line cube set to ensure that all cubes in the line cube set are intersected by their common line. is there. The effect of step M11 is to flatten the line cube set. Step M11 is necessary because the common plane changes each time a new cube is added to the plane cube set in step M10. In the growing process of a line cube set, there is no guarantee that the initially added cube will continue to intersect the common line after it (common plane) changes. Step M11 compensates for this. Steps T1 to T8 are applied separately to all cubes in the planar cube set, so they can be applied in parallel if necessary.

  The steps of the process by which the line cube set is flattened are as follows.

<T1>
Stop if the cubes are crossed by a common line. (This cube requires no further action.)

<T2>
The step of removing a cube from a line cube set.

<T3>
Setting the current point to a point cloud point in the cube.

<T4>

<T5>
Finding a cube that contains the projected points. This cube is called a projected cube. See step Y5 for details on how the projected cube is calculated.

<T6>
If the projected cube does not belong to a line cube set, adding the projected cube to the line cube set.

<T7>
Stop if the current point is the last point cloud point in the cube.

<T8>
Setting the current point to the next point group point in the cube and proceeding to step T4.

  FIG. 12 is a flowchart of step M12, shown in detail in steps S1 to S16, applied to identify the end point of the common line in the line cube set. At the stage where step M12 is applied, each line cube set has the property that all those cubes are intersected by their common line. Any cube that is intersected by a common line (including cubes that are not members of a line cube set) matches the common line at two points (which may be coincident) called the intersection of the cubes.

  Any two cubes that are intersected by a common line and share an intersection are called collinear adjacent cubes. Any intersection shared by two collinear adjacent cubes that have only one member of the line cube set is called the end point of the line cube set. In step M12, the possibility that the line cube set has three or more end points is also allowed.

  Step M12 is applied separately to each line cube set. It progressively removes cubes from the line cube set until the set is empty. Step M12 can be applied in parallel.

<S1>
Creating an empty list of A and B node pairs. Upon completion of step M12, each node pair in the list will indicate two endpoints of a line segment along the common line of the line cube set.

<S2>
Step to stop if the line cube set is empty.

<S3>
Setting the current cube to the first cube in the line cube set.

<S4>
If the current cube does not include the end point of the line cube set, removing the current cube from the line cube set and proceeding to step S6.

<S5>
Setting the current cube as the next cube in the line cube set and proceeding to step S4. In step S5, the next cube may be any cube left in the line cube set.

<S6>
Setting the current node pair at the intersection of the current cube.

<S7>
If both nodes of the current node pair are the end points of the line cube set, name one node A and name another node B and proceed to step S16.

<S8>
Storing the unique endpoint of the current node pair as A.

<S9>
Setting the next cube to be a unique adjacent cube of the current cube that is a member of a line cube set.

<S10>
The step of storing the current cube as the previous cube.

<S11>
The step of setting the current cube to the next cube.

<S12>
Remove the current cube from the line cube set.

<S13>
Setting the current node pair to the current cube intersection.

<S14>
If both nodes of the current node pair are not endpoints, set the next cube to a unique adjacent cube that is not the previous node and proceed to step S10.

<S15>
Storing the unique end point as a B-node.

<S16>
If A and B nodes are not consistent (within tolerance), add A and B nodes to the list of node pairs.

<S17>
Step proceeding to step S2.

  Although the above individual embodiments of the present invention have been described using cubes (which may be construed as meaning tetrahedral or other mosaic-filled space-filling shapes) It will be appreciated that overlapping volumes, particularly overlapping spheres, can also be used. In such an embodiment, a close volume may be defined as a volume whose center point is located within a predetermined distance from the center point of the volume in question.

  FIG. 21 shows the result of conversion from point cloud data to a vector image to draw an architectural scene. Individual size measurements in the image can be easily determined and the architect can manipulate the drawing of the vector image to produce a modified blueprint. This avoids the problem of architects taking measurements in the laboratory of 3D models made from physical buildings / environments and handwriting.

Those skilled in the art will appreciate that a variety of different techniques may be used for the generation of point cloud data including LIDAR and photogrammetry. Various variations of these techniques may generate various point clouds, including not only the correct position data. This additional data may also be incorporated into the described method. For example, each point in the point cloud may include color or intensity information. Once the surface is identified, the surface coloration or lightness mapping may be performed using the color or lightness of the point that first identified the surface on the model.

  The described method may also be used in combination with other image techniques to improve the accuracy of the 3D model and / or cover the model with additional image data. For example, the scanner may be used in conjunction with a three-dimensional camera. Scanning and 3D photography may be performed simultaneously so that a realistic 3D environment like a photograph is generated.

  It will be appreciated that the present invention is not limited to specific embodiments of the invention, since many distinct embodiments of the present invention can be made without departing from the scope of the invention.

<M1>
Superimposing a three-dimensional lattice on the position of the space occupied by the object. The grid partitions the space into a list of large but finite cubes. To avoid wasting computer storage space, the list excludes any empty cubes. In the current embodiment, the cubes are all the same size. The length of the side of each cube is called its resolution. If necessary (for example, a partially scanned surface has a very large curvature), some of these cubes can be subdivided into smaller cubes, which can be further subdivided You can also do it. In this way, different local resolutions can be used on different planes. Another segmentation of the three-dimensional space can also use, for example, a tetrahedron. In the following, although the term cube is used, it is recommended that the method apply equally to tetrahedron or other space-filled mosaic processing.

The above individual embodiments of the present invention cubes said that described with reference to (or other space-filling shapes are mosaic type containing tetrahedral), those skilled in the art, overlapping volumes, In particular, it will be understood that overlapping spheres can also be used. In such an embodiment, a close volume may be defined as a volume whose center point is located within a predetermined distance from the center point of the volume in question.

Claims (26)

An apparatus for converting a set of point cloud data of one or more objects into a set of three-dimensional displays of the objects,
Means for dividing the space occupied by the set of objects into a plurality of volumes;
A means of determining whether the points in each volume roughly coexist on the surface;
Here, such a volume is designated as a surface volume, and the surface on which the points coexist is designated as the surface of the surface volume,
Means for combining the first plurality of adjacent surface volumes that are approximately coexisting along a similar surface identified as a larger surface within the surface volume set;
Means for identifying a surface edge volume set of the surface volume set;
Wherein the surface edge volume set has a volume in the surface volume set adjacent to an empty volume intersected by a larger surface,
A device comprising:   The apparatus of claim 1, comprising means for generating a set of point cloud data for the object.   The apparatus according to claim 2, wherein the means for generating the point cloud data is a LIDAR scanner that detects and measures light. The means for generating the point cloud data includes:
A camera configured to capture a set of one or more images of the object;
The apparatus of claim 2, wherein the apparatus comprises a processor configured to perform image techniques on the image.   The apparatus according to claim 3 or 4, wherein the scanner is configured to move along a path, and generates point cloud data from a plurality of scanning points along the path. Means for estimating a group boundary point for each end of each volume in the surface end volume set;
Where an edge is defined by the intersection of the larger surface of the surface volume set having a boundary between a volume in the surface edge volume set and an empty volume;
The apparatus according to claim 1, comprising: Means for identifying where a group boundary point is close to the curve formed by the intersection of the larger surfaces;
Means for moving the position of the group boundary point to an intersection curve. Means for determining whether the points in each volume roughly coexist on the curved surface;
Here, such a volume is identified as a curved volume, and the curved surface in which points coexist is identified as the curved surface of the curved volume.
Means for combining the first plurality of adjacent curvilinear volumes intersected in a curved volume set by similar curved surfaces;
Where intersecting curved surfaces are identified as larger curved surfaces,
Means for identifying an end point defining a curve segment;
The apparatus according to claim 1, comprising: A method of converting a set of point cloud data of one or more objects into a set of three-dimensional displays of the objects,
Dividing the space occupied by the set of objects into a plurality of volumes;
Determine if the points in each volume roughly coexist on the surface, where such volumes are designated as surface volumes, and the surface where the points coexist is designated as the surface of the surface volume And
Combining a plurality of first adjacent surface volumes approximately coexisting along similar surfaces identified as larger surfaces in the surface volume set;
Identify a surface edge volume set of the surface volume set, wherein the surface edge volume set has a volume in the surface volume set adjacent to an empty volume intersected by a larger surface. The way you are.   A group boundary point is estimated for each end of each volume in the surface boundary volume set, where the end of the surface volume set has a boundary between the volume in the surface boundary volume set and the empty volume. 10. The method of claim 9, defined by a larger surface intersection. Identify where the group boundary points are close to the curve formed by the intersection of the larger surfaces,
The method of claim 10, wherein the position of the group boundary point is moved to an intersection curve. Decide if the points in each volume roughly coexist on the curved surface,
Here, such a volume is identified as a curved volume, and coexisting points are identified as curves of the curved volume,
Combining the first plurality of adjacent curved volumes intersected in a curved volume set by a similar curved surface into the curved volume set;
Here, the intersecting curved surfaces are identified as larger curved surfaces,
12. A method according to claim 10 or 11, wherein the end points defining the curved section are identified.   13. A method according to any one of claims 9 to 12, wherein the surface on which dots coexist is a plane.   13. The method according to any one of claims 9 to 12, wherein the volume is a non-overlapping cube and adjacent cubes have one or more common faces, common ends, or common vertices.   The volumes are non-overlapping, space-filled tetrahedrons or other space-filled mosaic shapes, do not include non-overlapping cubes, and have one or more adjacent surfaces, common ends, or common adjacent volumes 13. A method according to any one of claims 9 to 12, having a vertex.   13. A method according to any one of claims 9 to 12, wherein the volume is an overlapping sphere or other overlapping shape.   The method according to claim 9, wherein the point cloud data is derived from a plurality of scanning points.   The method of claim 17, wherein the plurality of scanning points are on a path of a movable scanner. The method according to any one of claims 9 to 18, wherein the three-dimensional representation is stored as a data file.   The method of claim 19, wherein the data file is stored as a vector image model.   21. The method of claim 20, wherein the vector image model is a three-dimensional computer aided design CAD model format.   The method of claim 21, wherein the three-dimensional model is overlaid with image data.   The method of claim 21, wherein important features are identified in the three-dimensional model.   The method of claim 21, wherein the key feature information is provided to a user.   A computer program having computer-executable instructions for causing a computer to execute the method according to any one of claims 9 to 24.   A data carrier storing the computer program according to claim 25.

Images