[go: up one dir, main page]

WO2008000055A1 - Procédés pour une correspondance simultanée multiples ensembles de points - Google Patents

Procédés pour une correspondance simultanée multiples ensembles de points Download PDF

Info

Publication number
WO2008000055A1
WO2008000055A1 PCT/CA2006/001083 CA2006001083W WO2008000055A1 WO 2008000055 A1 WO2008000055 A1 WO 2008000055A1 CA 2006001083 W CA2006001083 W CA 2006001083W WO 2008000055 A1 WO2008000055 A1 WO 2008000055A1
Authority
WO
WIPO (PCT)
Prior art keywords
points
sets
triangle
cluster
pair
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/CA2006/001083
Other languages
English (en)
Inventor
Chun Hing Cheng
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
VX TECHNOLOGIES Inc
Original Assignee
VX TECHNOLOGIES Inc
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by VX TECHNOLOGIES Inc filed Critical VX TECHNOLOGIES Inc
Priority to PCT/CA2006/001083 priority Critical patent/WO2008000055A1/fr
Publication of WO2008000055A1 publication Critical patent/WO2008000055A1/fr
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T7/00—Image analysis
    • G06T7/30—Determination of transform parameters for the alignment of images, i.e. image registration
    • G06T7/35—Determination of transform parameters for the alignment of images, i.e. image registration using statistical methods
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06V—IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
    • G06V10/00—Arrangements for image or video recognition or understanding
    • G06V10/70—Arrangements for image or video recognition or understanding using pattern recognition or machine learning
    • G06V10/74—Image or video pattern matching; Proximity measures in feature spaces
    • G06V10/75—Organisation of the matching processes, e.g. simultaneous or sequential comparisons of image or video features; Coarse-fine approaches, e.g. multi-scale approaches; using context analysis; Selection of dictionaries
    • G06V10/757—Matching configurations of points or features
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T2200/00—Indexing scheme for image data processing or generation, in general
    • G06T2200/04—Indexing scheme for image data processing or generation, in general involving 3D image data
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T2207/00—Indexing scheme for image analysis or image enhancement
    • G06T2207/10—Image acquisition modality
    • G06T2207/10028—Range image; Depth image; 3D point clouds

Definitions

  • the invention relates to aligning two or more three dimensional images each having a respective three dimensional coordinate system in such a manner that the two or more three dimensional images share a common three dimensional coordinate system.
  • One manner to generate a 360 degree digital model of an object is to combine multiple images obtained from different angles using a three dimensional (3D) imaging device.
  • a difficulty in such digital model generation is properly aligning the multiple images.
  • a conventional method of aligning multiple images is using photogrammetry to accurately register the different positions from which the object is scanned so that the relative transformation between the images is known.
  • Another method is by matching shapes that are part of the images in the overlapping areas, assuming that the object has distinctive features that can be matched.
  • the first method introduces additional complexity to the alignment problem due to additional scanner position information required to solve the problem.
  • the second method is susceptible to errors if distinct features cannot be easily matched.
  • a method for aligning a plurality of three dimensional images of an object each image having a respective three dimensional coordinate system and comprising a set of points related to a surface of the object, such that when aligned within an acceptable error threshold the plurality of three dimensional images share a common three dimensional coordinate system
  • the method comprising the steps of: i) for each set of points, forming at least one triangle using vertices in the respective set of points; ii) for each respective pair of the plurality of sets of points; a) for each triangle in each set of points of the respective pair,- matching the triangle of a first set of points of the respective pair with a triangle of a second set of points of the respective pair to form at least one matching triangle pair; determining a transformation function to transform an orientation of a first triangle of the matching triangle pair to an orientation of a second triangle of the matching triangle pair; b) grouping together determined transformation functions that are substantially similar to form a respective cluster transformation function, each cluster transformation
  • a computer usable medium having computer readable program code means embodied therein for aligning a plurality of three dimensional images of an object, each image having a respective three dimensional coordinate system and comprising a set of points related to a surface of the object, such that when aligned within an acceptable error threshold the plurality of three dimensional images share a common three dimensional coordinate system
  • the computer readable code means comprising: i) for each set of points, computer readable code means for forming at least one triangle in which three of the points in the set of points form vertices of the at least one triangle; ii) for each respective pair of the plurality of sets of points; a) for each triangle in each set of points of the respective pair; computer readable code means for matching the triangle from a first set of points of the respective pair with a triangle of a second set of points of the respective pair to form at least one matching triangle pair; computer readable code means for determining a transformation function to transform an orientation of a first triangle of
  • Figure 1 is a flow chart for a method of multi-set point matching according to an embodiment of the invention
  • Figure 2 is a schematic diagram of three sets of points that are to be aligned
  • Figure 3 is a schematic diagram of three sets of points, each set containing multiple triangles formed from the points;
  • Figure 4A and 4B are schematic diagrams of a two dimensional transform space demonstrating clustering of transformations ;
  • Figures 5A, 5B, 5C, 5D, 5E and 5F are schematic diagrams of a sequence of steps involved in setting orientations for matching set pairs according to an embodiment of the invention
  • Figure 6A, 6B and 6C are schematic diagrams of different possibilities for alignment of three sets of example points
  • Figure 7 is a schematic diagram of a two-dimensional transform space showing how outliers are eliminated from cluster groups in accordance with an embodiment of the invention
  • Figures 8A, 8B, 8C and 8D are schematic diagrams of an example of how global identifiers are assigned for points in accordance with an embodiment of the invention
  • Figures 9A and 9B are schematic diagrams of three sets of points and how the sets are aligned, merged and given a common global identifier in accordance with an embodiment of the invention
  • Figure 10 is a schematic diagram of the three sets of points shown in Figure 2 in which points have been matched in the three sets;
  • Figure 11 is a flow chart for a method of multi-set point matching according to another embodiment of the invention.
  • Figures 12A and 12B are schematic diagrams of two examples of three overlapping sets that can be operated on according to embodiments of the invention.
  • the invention includes a method for aligning two or more 3D images of an object taken by a 3D imaging device that can capture both geometry of a surface of the object and positions of markers on the object's surface. After aligning the images and locating them in a common coordinate system, the images are combined together to generate the 3D model of the object.
  • a large number of small markers are placed over the entire surface of the object, and 3D images are taken of the object so that every part of the object is recorded by at least one image and there are at least three non-collinear matching points for each pair of overlapping images.
  • These markers are referred to as tie points as they help tie the images together.
  • Tie points in all images are matched simultaneously and matching points are assigned with the same global identifier (ID) .
  • ID global identifier
  • GCP ground control point
  • a ground control point (GCP) object which is an object (usually in a standard shape, for example a cube or plate) with many markers, called GCP points, located on the object's surface.
  • the positions of the GCP points are known, either by precise machining of the points or by measuring them using Coordinate Measuring Machine (CMM) or imaging equipment.
  • CMS Coordinate Measuring Machine
  • the object to be modelled, which has no markers located on it's surface is placed close to the GCP object, and the two objects are imaged together at different angles so as to fully image the object.
  • Each image is to have at least three non-collinear GCP points.
  • a first set, S includes the known positions of the markers of the GCP object and a second set, T, includes the GCP points visible in the image.
  • the positions of GCP points in S are exactly known as the spacing of the points is known apriori .
  • the GCP points in T are matched with the GCP points in S, so that the rigid transformation that transforms the image towards the coordinate system of the GCP object can be found. After repeating this process for other images, the images are aligned in a common coordinate system.
  • the global ID described above is a unique identification integer (normally starting from 0) assigned to all matching points in different sets. Therefore, two points in the same set cannot have the same global ID. Unmatched points may be given a global ID of -1, or more generally some other distinct value. Two points in different sets are said to be matching if they have the same global ID, that is they coincide within a margin of error after appropriate rigid 3D transformations on the sets. The margin of error is an acceptable misalignment distance between points with the same global ID.
  • the expression "rigid 3D transformation” is used to describe the transformation of a set of points.
  • the transformation includes one or both of a rotation of the points and a translation of the points in each of three axes.
  • Two sets of points are considered to be overlapping or connected if they have three or more matching points that are not collinear.
  • a family of three or more sets of points are said to be all connected if for any two sets, for example A and B in the family, we can find a sequence ("path") of sets in the family, say C, D and E, such that A and C are overlapping, C and D are overlapping, D and E are overlapping and E and B are overlapping.
  • the invention is capable of handling one or more of the following cases: a) positions of the points may not be accurate; b) some points in a set may be singular, that is they cannot be matched with a point in other sets; c) symmetry is allowed, that is three matching points in two sets may form an isosceles (two sides equal) or equilateral (all sides equal) triangle; d) the same pattern of points may repeat within a set and may repeat in another set; e) there can be a large number of sets, in which each set has a large number of points; and f) the same global ID can be shared by points from a large number of overlapping sets.
  • the invention is not as effective when a given family of sets are not all connected, that is there exists two sets A and B in the family such that a path of overlapping sets joining A and B cannot be found.
  • at least three non-collinear matching points between sets are used, so that no sets are left unpaired. Situations in which there are only one or two common points between every pair of sets, can be overcome in some embodiments of the invention as described below in the section entitled "Further embodiments of the Invention" .
  • the methods described herein are considered to be robust since the situation of many symmetries or pattern repetitions are unlikely or can be easily avoided, for example by simply randomly positioning the markers on the surface of the object or having more than three matching points per each pair of overlapping sets.
  • a method according to an embodiment of the invention will now be described with respect to the flow chart of Figure 1.
  • a first step 100 is inputting multiple sets of tie points on which the method will operate.
  • a second step 105 includes forming candidate edges, where an edge is a line between two points in a set.
  • a third step 110 is to form matching triangle pairs making use of the candidate edges of step 105.
  • a decision step 115 is to be determined if all the sets are connected by matching triangle pairs. If any of the sets are not connected (no path) then the method is complete (END) . If the sets are connected (yes path) then a further step 120 is to determine transformation functions for each matching triangle pair and from these determined transformation functions form transformation function cluster combinations.
  • a next step 125 is to sort the transformation function cluster combinations in a desirable manner. Once the transformation function cluster combinations are sorted at step 125, one of the transformation function cluster combinations is selected 130 to be operated on.
  • a next step, step 140 involves finding set orientations of the sets for the selected transformation function cluster combinations. Once the set orientations are determined, a next step, step 145 involves removing outlying transformations for each set pair. After outlying transformations are removed, a further step, step 150 is assigning common global IDs to points in each set. Following step 150, points that are in close proximity, for example within a particular distance threshold range, are merged and given a common global ID. Another decision point occurs at 160.
  • steps 140-155 It must be determined if a result output from steps 140-155 is acceptable. If the result is not acceptable (no path) , a subsequent transformation function c Luster combinations of the sorted cluster combinations from step 130 is selected at step 165 and steps 140, 145, 150, 155 and 160 are repeated. If the result is acceptable (yes path of step 160) , the global IDs are output at step 170 allowing the aLignment of the multiple images to form the 3D model.
  • the individual steps of Figure 1 will now be described in further detail .
  • the number of sets is provided and for each set, the number of points. Then for each point in each set, the local identifier (IDs) and the 3D position in the coordinate system of each respective set are also provided. The local IDs are used to identify the points within each respective set.
  • Figure 2 shows three sets of points, Set 0, Set 1 and Set 2.
  • Set 0 includes points having local IDs A, B, C, D, E and F.
  • Set 1 includes points having local IDs G, H, I, J and K.
  • Set 2 includes points having local IDs L, M, N and O.
  • the sets have differently shaped contours such that there is no simple manner to determine which points in the three sets may be matching points.
  • the sets are considered to represent 3D images and therefore the contours and points in Figure 2 are understood to have a 3D representation as well.
  • a maximum positional error ⁇ is determined for the points.
  • the error is at least in part due to the quality of the imaging equipment and therefore the error is estimated from the accuracy and/or resolution of the 3D imaging system.
  • the maximum error in the distance between any two points in a set is equal to 2* ⁇ . Consequently, a maximum error in the difference between distances between two points in a first set and two points in a second set is 4* ⁇ .
  • An edge is an ordered pair of points in the same set.
  • edges can be formed: AB and BA.
  • the length of an edge is the distance between the two points .
  • a candidate edge is an edge that has a corresponding or matching edge in another set whose length differs from that of the candidate edge by less than or equal to a magnitude of 4* ⁇ .
  • edges in each set are first defined.
  • a set with n points should have n* (n-1) edges.
  • the edges in each set are sorted in a particular order. In some embodiments this includes ascending order according to the edge lengths, that is shortest length at the top of the list and longest length at the bottom of the list. Edges that are longer than the potential candidate edge in a different set, but whose length do not exceed the length of the potential candidate edge by more than 4* ⁇ are recorded in a list of corresponding edges. For each potential candidate edge, when searching other sets for matching edges of a corresponding length it is possible to take advantage of the fact that each set has a list of all edges in that set that is sorted in order of length.
  • each candidate edge in each set has an associated list of edges in other sets that may correspond to the candidate edge in those respective sets.
  • Arranging the edges in ascending order is one example of how the edges can be arranged. Those skilled in the art would realize that the edges can be arranged in other ways, for example descending order of edge length. Edges of other sets that are shorter than the candidate edge by 4* ⁇ are also included in the associated list of edges in other sets that may be the same edge in those respective sets.
  • Figure 3 shows the sets from Figure 2 in which solid lines between points in each set indicate candidate edges and dashed lines indicate non-candidate edges.
  • An example of a scale representation of the maximum error in distance difference (4* ⁇ ) is also indicated in the figure.
  • rms root -mean-square residual p.
  • a rigid transformation T can be applied to the first set so that T(P x ) is close to Qi, T(P 2 ) is close to Q 2 , etc.
  • the rms residual between the first and second sets of points is the minimum value of the rms residuals between the respective matched points over different transformations.
  • minimization techniques that can be used for finding the transformation that gives the rms residual between two sets of points.
  • One example of a minimization technique is the use of eigenvalues.
  • a triangle is an ordered triple of points in the same set that are not substantially collinear.
  • the triangle is denoted by the three points or vertices of the triangle in a particular order, for example ⁇ XYZ .
  • Six labelled triangles can be formed by the same three points.
  • a triangle pair is made up of a triangle, for example ⁇ XYZ in a first set and a triangle ⁇ PQR in a second set .
  • the triangle pair of the example triangles is denoted by ( ⁇ XYZ, ⁇ PQR) .
  • triangle pairs are ordered by definition, triangle pairs are invariant under transposition, that is triangle pairs ( ⁇ XYZ, ⁇ PQR) , ( ⁇ YZX, ⁇ QRP) , ( ⁇ ZXY, ⁇ RPQ) , ( ⁇ XZY, ⁇ PRQ) , ( ⁇ YXZ, ⁇ QPR) , ( ⁇ ZYX, ⁇ RQP) are all regarded as equivalent.
  • a triangle pair for example ( ⁇ XYZ, ⁇ PQR) is considered to be a matching triangle pair if one or both of the following conditions are true:
  • the rms residual between ⁇ XYZ and ⁇ PQR (i.e. the minimum rms residual of all rigid transformations from ⁇ XYZ towards ⁇ PQR) does not exceed p.
  • one more condition is imposed on the triangle pair ( ⁇ XYZ, ⁇ PQR) for it to be considered a matching triangle pair.
  • the additional condition is that the two triangles have normal vectors for two edges of each respective triangle that point in a same direction with respect to a surface of the object.
  • ⁇ XYZ and ⁇ PQR are only considered to be matching triangle pairs if the normal vector for ⁇ XYZ satisfying the right-hand rule (parallel to cross product XY X XZ) and the normal vector of ⁇ PQR satisfying the right-hand rule (parallel to cross product PQ X PR) are either both pointing away from the object or both pointing toward the object.
  • a candidate triangle is a triangle in a set that has a chance of forming a matching triangle pair with a triangle in another set.
  • all candidate triangles are determined for each set. For each set, all combinations of three candidate edges are determined in the set such that the edges join together tail -to-head to form a triangle in which the edges are not substantially collinear. The edges can be confirmed as not being substantially collinear by checking that the difference between a longest edge and a sum of the other two edges is not less than 4* ⁇ .
  • a search is performed for triangles in other sets such that the potential candidate triangle and any triangles in other sets satisfy at least one of the first two conditions of matching triangle pairs described above.
  • the first condition is satisfied by determining that the lengths of each corresponding edge in the triangles do not differ by more than 4* ⁇ .
  • the second condition is satisfied by finding the rigid transformation to transform an orientation of a first triangle of the matching triangle pair to an orientation of a second triangle of the matching triangle pair that minimizes the rms residual.
  • the rigid transformation that minimizes the rms residual can be found, for instance, based on determining eigenvalues.
  • the third condition may also be used to establish whether the potential candidate triangle and other triangle are matching triangle pairs.
  • the list of corresponding edges in other sets for each candidate edge maintained in previous step 105 can be used when forming triangle pairs.
  • a data structure can be used to associate each edge to the list of triangles containing that edge as the shortest edge.
  • a scalene triangle is considered to be a triangle with all sides having different length, such that the difference between each pair of sides is greater than 4* ⁇ .
  • An isosceles triangle is considered to be a triangle with two of three sides equal in length such that the difference in length between the two equal sides is less than 4* ⁇ .
  • An equilateral triangle is considered to be a triangle with three equal sides such that the difference in length between the three equal sides is less than 4* ⁇ . Therefore, due to the ordered triple nature of labelling triangles, a pair of potentially matching scalene triangles in different sets can only form one possible match based on the different edge lengths.
  • a pair of potentially matching isosceles triangles in different sets can form two matching pairs having different ordered vertices when the two conditions described above are applied.
  • a pair of potentially matching equilateral triangles in different sets can form six matching pairs having different ordered vertices when the two conditions described above are applied.
  • each pair of sets is examined. Two sets are identified as overlapping if they have at least one matching triangle pair between them.
  • Every combination of pairs of sets is examined.
  • the examination process is started by selecting a first set and labelling it with an identifier.
  • the selected set is compared to a second set. If the two sets are overlapping, and the second set is unlabelled, the second set is labelled with a new identifier. If the second set already has an identifier, then another set is selected for comparison with the first set.
  • a set that is connected to the first set is selected and the labelling process repeated. This is continued until no more new sets can be labelled.
  • the method can be reinitiated using the same number of sets in which the points in the sets are changed, or the preceding steps can be repeated for only the sets that were identified with labels and are connected. If the method is to be reinitiated with the same number of sets one manner of changing the sets is to add more points to some or all sets so as to improve the potential for sets to be connected.
  • Step 120 is performed for each pair of overlapping sets in turn, however the description below applies to an example of a single pair only. Such a process is to be repeated for all overlapping pairs.
  • a convention is adopted that in a pair of sets, the index of the first set i is less than that of the second set j .
  • Each set is given an incremental index as they are input at step 100 e.g. 0, 1, 2,..JsT. Also, in some embodiments a particular convention is used such that transformations between pairs of sets transform a first set towards a second set.
  • each rigid transformation between two overlapping sets can be expressed uniquely by six transformation parameters including three rotations about x, y and z axes and three translations along x, y and z axes.
  • the uniqueness of angles is guaranteed by restricting values to principal values of inverse trigonometric functions.
  • the transformation between triangles of the matching tiriangle pair can be represented by a single point in a six- dimensional "transformation space" formed by the six transformation parameters.
  • Figure 4A represents a two- dimensional transform space for illustration purposes.
  • Figure 4A represents a transform space where the coordinate grid of the transform space represents movement for a particular type of transform, such as a rotation about an axis or a translation along an axis.
  • Locations indicating transformation functions to transform an orientation of a first triangle of the matching triangle pair to an orientation of a second triangle of the matching triangle pair in Figure 4A are indicated by lowercase letters a-k.
  • each square in the two- dimensional transform space of Figure 4A would represent a six dimensional "hyper-cube" in the six-dimensional transformation space .
  • a transformation function transforms most points in the first set towards corresponding points in the second set, then that same transformation function should transform each triangle formed by the points in the first set towards the corresponding triangle in the second set .
  • Points representing each matching triangle pair transformation for different matching triangle pairs across a pair of sets form a grouping or a cluster around a common location in the transformation space if the transformation function is consistent within an error threshold for all matching triangle pairs in the set pair.
  • each cluster of transformation functions represents triangle matching pairs having transformation functions that are substantially similar. It should be noted that the transformation functions determined to represent the two different potential matching triangle pairs for matching isosceles triangles described above may correspond to different groupings or clusters in the transformation space. The same can be said for the six potential matching triangle pairs for matching equilateral triangles .
  • cluster location determining techniques There are many cluster location determining techniques. However, the techniques usually assume that the total number of clusters is known before hand. In some embodiments of the invention a special clustering method is used which does not need the apriori knowledge of the number of clusters. Furthermore, a single transformation location can be treated as a cluster. This technique is hereinafter referred to as accumulation and is based on weighting of the transformations in the transform space. In some embodiments the cluster with the largest total weighting value of the multiple clusters is selected as the most probable transform function for the pair of sets of points .
  • the entire six-dimensional transformation space is divided into equally sized cells.
  • the resolution of each cell for the three rotational -axes and three translational-axes are defined so that the cells are not so small that they can only contain one transform point and not so large that adjacent clusters of multiple transformations merge in single cell.
  • the resolution that is selected is a function of maximum positional error ⁇ and maximum rms residual p.
  • a coordinate system is used in which each cell is identified by six integers, in which each one of the six integers represents one cell in a row of consecutively numbered cells in that respective dimension.
  • Each point in the transform space corresponds to a particular transformation and is represented by six real numbers .
  • tie points on the physical edges of the two sides are utilized as this is where the two sides overlap.
  • the images must be taken at an angle so as to include the edges .
  • the edges are narrow and have high curvature, so the common tie points there are less accurate and the triangles are thin.
  • the accumulation of the weights for each transformation point in each cell also takes into account transformation points in the neighbourhood of that respective cell.
  • Two cells are considered to be adjacent if any of the integers in the two cells' six integer labels differ by a value equal to one. Therefore, an order of adjacency is herein defined as the number of integers in the labels that differ by one. For example, a six integer label (5,2,2,3,4,1) is adjacent to (5,2,2,4,4,1) with an order of one because the fourth integers in the two labels differ by one, "3" in the first label and "4" in the second label.
  • a six integer label (5,2,2,3,4,1) is adjacent to (4,1,1,2,5,0) with order six as all six integers differ by one.
  • (5,2,0,3,4,1) is not considered to be adjacent to the six integer label (5,2,2,3,4,1) because the third integer value in the two labels differs by a value of two, "0" in the first label and "2" in the second label. Care has to be taken in identifying adjacent cells along the rotation-axes so as to properly handle wrapping of angles. For example, an angle of -L79 degrees is substantially equal to an angle of 178 degrees even though their numerical values are vastly different.
  • a new total weight is calculated for each cell that is equal to the sum of the cell's original total weight, plus the original total weight of each of its adjacent cells multiplied by 0.5 k , where k is the order of adjacency. Hence, adjacent cells that are closer to the cell contribute more to the new total weight.
  • a cluster of transform locations may be spread over more than one cell.
  • the boundaries of the cells in the transformation space are shifted by an amount equal to half a cell width in all six directions and the above weighting procedure is repeated for the shifted boundaries. Either one of the original six dimensional space or the shifted boundary six dimensional space is selected depending on which one has cells having clusters with a largest number of transform locations.
  • Figure 4B shows the same two dimensional transformation space with the same transformation points as Figure 4A, where the grid of cells as been shifted by half a cell with in both dimensions.
  • the cluster of transformation locations a, c, i and j is spread over four cells in Figure 4A
  • the same four transformation locations are substantially in a single cell in Figure 4B.
  • Figure 4B also indicates the accumulated weight of the cells by different cross hatching patterns in the cells.
  • the cell substantially encompassing transformation locations a, c, i and j is shown to a particular weighting value which is the largest weighting value.
  • Cells that contain a single transformation location or are in close proximity to a single transformation location have different cross hatching patterns, indicating their weighting value is less.
  • Cells that contain no transformation location are a white, indicating there is no weighting value for those cells .
  • cells are identified whose new total weights are at local maximum, i.e. greater than or equal to the new total weights of all its neighbours. There can be one or more local - maximum cells, and the local -maximum cell with the greatest weight value is called the global -maximum cell. These local- or global-maximum cells will be referred to herein as "clusters" or “cluster cells” .
  • Sort cluster combinations (step 125)
  • a list of clusters of transformation functions is determined, that is sorted in descending order of the new total accumulated cell weights from greatest weighted value to least weighted value.
  • the cluster at the top (which is in fact a global -maximum cell) is given an identifier 0, the one below it is given an identifier 1 and so on.
  • a cluster combination, or transform function combination is an ordered m-tuple of identifiers, where the ith component in the m-tuple is the identifier of the cluster used for the ith pair of overlapping sets.
  • the m-tuple of aLl zeros (0, 0,....,0) is a cluster combination formed by c Lusters that each have an identifier equal to 0, that is the global -maximum cluster for each pair of overlapping sets.
  • each cluster combination can be a solution to the alignment of the sets, though the combinations formed by clusters with the largest number of zeros is a more reasonable choice of selection to be the solution.
  • Ni*N 2 *...*N m can be a large number, in some embodiments a number of cluster combinations to be chosen as possible solutions to try is limited to a maximum number L.
  • the cluster combinations are sorted in a list in descending order of preference, so that the more preferred ones are tried first.
  • preference is measured by a "ratio-product" , which is obtained by multiplying the ratio of the total weight of each cluster by the total weight of the global -maximum cluster of all the M clusters for the m pairs of overlapping triangles. For example, for the cluster combination (0,0,...,0), the ratio-product is equal to one. For a cluster combination (3, 1, 0,...,0), the ratio-product is equal to (a3/A) * (bl/B) .
  • the value "a3" is the new total weight of the first cluster, the cluster having the ordered identifier equal to "3" in the cluster combination and "A” is that of the global -maximum cluster for the first pair of overlapping sets.
  • the value "bl” is the new total weight of the second cluster, the cluster having the ordered identifier equal to "1" in the cluster combination and "B” is that of the global -maximum cluster for the second pair.
  • the remainder of the clusters with a "0" identifier have a ratio equal to one. Hence the ratio-product for each cluster combination is less than or equal to one .
  • the cluster combination with the largest ratio-product is selected.
  • the top cluster combination is (0, 0,...,0) .
  • the cluster combination is the global -maximum cluster of each o E the m pairs of overlapping sets.
  • orientation is used to describe the rigid transformation that brings the set of points from an original coordinate frame to another coordinate frame .
  • the inverse of the rigid transformation is used to bring the object back to the original frame.
  • a set with an orientation of I is considered to be in a reference coordinate frame .
  • a first step is to determine the transformations between all pairs of overlapping sets, using the cluster combination selected in step 130. For each pair of overlapping sets, say Set i and Set j (i ⁇ j) , a "centre" location of the selected cluster is determined in the six-dimensional transformation space, as the weighted average of the positions of the points in the cluster cell and its adjacent cells.
  • the weights for the points in the cluster cell are the reciprocal of the minimum rms residual for the matching triangle pair represented by that point.
  • the weights of the points in its adjacent cells are obtained by multiplying the reciprocal of the minimum rms residual by a power of 0.5 as described above.
  • the six- dimensional coordinates of this centre location which are the three rotation and three translation parameters, are then synthesized into a transformation function Ti j , which represents the transformation for points from Set i to Set j in matrix form.
  • the inverse transformation function T j i for points from Set j to Set i is also determined.
  • the set-to-set transformations are applied to the sets to determine the set orientations.
  • the transformations may not all be consistent.
  • the list of pairs of overlapping sets is sorted in descending order of the new total weight of the cluster cells of the transformation between the pair, and the transformations are applied in that order. In this way, the more reliable transformations will take preference .
  • Each pair of overlapping sets in the sorted list is processed in this manner. Since it has previously been determined that the sets are all connected, at step 115 of Figure 1, eventually all sets belong to one group only, and only one set has the orientation of reference coordinate frame I. That set becomes the reference set, placed in its own coordinate system, with all other sets placed relative to it.
  • Figure 5A shows a group of eight cluster generally indicated by 1-8, in which the order of the numbering indicates the descending order of the weight of the clusters. Transformations between set-pairs of clusters are indicated by symbols ⁇ , ⁇ , ⁇ , ⁇ , ⁇ , ⁇ , ⁇ , ⁇ , i with an arrow indicating the direction of the transformation.
  • transformation ⁇ is the transformation used to orient cluster 1 in the same coordinate frame as cluster 5.
  • the goal is to obtain transformations for each cluster with respect to the reference coordinate frame I .
  • each one of clusters 1, 3 and 4 uses its own coordinate frame as the reference coordinate frame I . Transformations ⁇ , ⁇ and ⁇ are applied to clusters 1, 3 and 4, respectively to orient clusters 1, 3 and 4 with respect to clusters 5, 6 and 7.
  • Figure 5C transforms ⁇ and ⁇ are applied to cluster 2 and cluster 7, respectively to orient clusters 2 and cluster 7 to cluster 6 and cluster 8.
  • the transformation from cluster 4 to cluster 2, via cluster 6 is represented by ⁇ * ⁇ ⁇ ⁇ where ⁇ "1 is the inverse transformation function of ⁇ .
  • the inverse transformation is used because ⁇ represents the transformation in the direction from 2 to 6, which is opposite to the desired orientation.
  • the transformation from cluster 3 to cluster 8, via cluster 7 is represented by ⁇ * ⁇ .
  • transformation ⁇ is applied from cluster 2 to cluster 6. Since cluster 3 and cluster 4 are now coupled via transformation ⁇ and newly applied transformation ⁇ , a single reference coordinate frame I must be selected as either c Luster 3 or cluster 4. In this example the reference coordinate frame I of cluster 3 is maintained. The transformation from cluster 3 to cluster 4 via cluster 6 now becomes ⁇ * ⁇ "1 .
  • transformation ⁇ from cluster 2 to cluster 5 is applied. Since cluster 3 and cluster 1 are coupled via transformations ⁇ , ⁇ and ⁇ and newly applied transformation ⁇ , a single reference coordinate frame I must be selected as either cluster 3 and cluster 1. In this example the reference coordinate frame I of cluster 3 is maintained. The transformation from cluster 3 to cluster 1 via clusters 6, 2 and 5 now becomes ⁇ * ⁇ "1 * ⁇ * ⁇ "1 . The transformation from cluster 3 to cluster 5, via clusters 6 and 2 is represented by ⁇ * ⁇ "1 * ⁇ .
  • transformations ⁇ and i are applied from cluster 6 and cluster 4, respectively to orient clusters 6 and 4 with respect to clusters 8 and 5.
  • two assumptions are made.
  • a first assumption is that ⁇ * ⁇ * ⁇ and a second assumption is that ⁇ * ⁇ "1 ⁇ ⁇ * ⁇ "1 * ⁇ . Therefore, transformation ⁇ between cluster 6 and 8 is maintained and transformation i between cluster 4 and 5 is considered to be inconsistent with the other transformations and is eliminated.
  • Figure 6A shows an example of three individual sets of points, Set 0, Set 1 and Set 2 to be aligned.
  • Set 1 includes a group of three points that form a single triangle.
  • Set 2 includes a group of four points forming multiple triangles.
  • Set 3 includes a group of three points that form a single triangle and a group of four points forming multiple triangles.
  • Figure 613 shows respective alignments for pairs of the three sets, in the form of Set Pair (1,2), Set Pair (1,3) and Set Pair (2,3).
  • Figure 6C shows three different alignment solutions for the combination of all three sets based on weighting factors for the three set pairs.
  • the weighting of Set Pair (1,2) is larger than the weighting of Set Pair (1,3) and the weighting of set pair (1,3) is larger than the weighting of Set Pair (2,3) . Therefore, the first alignment solution uses Set Pair (1,2) and (1,3) and ignores the Set Pair (2,3) .
  • the weighting of Set Pair (1,2) is larger than the weighting of Set Pair (2,3) and the weighting of Set Pair (2,3) is larger than the weighting of Set Pair (1,3). Therefore, the second alignment solution uses Set Pair (1,2) and (2,3) and ignores the Set Pair (1,3).
  • the weighting of Set Pair (1,3) is larger than the weighting of Set Pair (2,3) and the weighting of Set Pair (2,3) is larger than the weighting of Set Pair (1,2) . Therefore, the third alignment solution uses Set Pair (1,3) and (2,3) and ignores the Set Pair (1,2).
  • each pair of overlapping sets is processed in turn. Note that some pairs of originally overlapping sets may become non-overlapping during the step 140 to ensure consistency of orientations, and these pairs are not dealt with here.
  • each transformation location represents the transformation between matching triangle pairs.
  • C be a centre of a selected duster in the cluster combination being processed.
  • a six- dimensional "bounding hyper-ellipsoid" is formed around C.
  • a hyper-ellipsoid is an ellipsoid of three or more dimensions.
  • the standard deviation of the points inside the bounding hyper-ellipsoid about C are determined, and a multiple of this standard deviation is used as the semi-axis-length of an "inlying hyper-ellipsoid" .
  • a constant multiple of the standard deviation for each dimension is used. Since the standard deviation for the 6 dimensions are all different, the 6 semi-axis-lengths are all different. All points outside the inlying hyper-ellipsoid are treated as outliers and ignored in the next step.
  • Figure 7 shows an example of the two-dimensional transform space of Figure 4B with the centre of the cluster C indicated with an "X" .
  • the bounding hyper-ellipsoid is indicated by a dashed line and the inlying hyper-ellipsoid is indicated by a solid line.
  • a more rigorous approach to eliminating outliers is to use a method that finds eigenvalues of a covariance matrix.
  • this method only works when there are six or more points in the cluster, and is generally found not to be significantly better than the method described above .
  • This step aims to assign all points in all sets global IDs so that matching points in different sets share the same global ID.
  • non-negative integers for example 0, 1, 2, ... are assigned for global IDs of matching points, and a negative integer for example -1 as assigned as a rogue global ID for all points with no match.
  • Step 145 finds inlying points in the six-dimensional transform space in the selected cluster for each pair of overlapping sets. Each inlying point corresponds to a matching triangle pair for that pair of sets . The triangle pairs are used to generate the global IDs.
  • a list of all matching triangle pairs for all pairs of overlapping sets is collected, and the list is sorted in ascending order of rms residual values.
  • the rms residual of a pair of triangles is the minimum rms residual of the three respective pairs of vertices as one triangle is transformed towards the other.
  • matching triangle pairs higher in the list have greater merit and dominate over the lower pairs in determining the global IDs.
  • triangle pairs in the sorted list are processed in the listed order.
  • a particular triangle pair be ( ⁇ P1P2P 3 , AQiQ 2 Q 3 ) where the first triangle ⁇ P1P2P3 is in Set i and the second triangle ⁇ Q 1 Q 2 Q 3 is in Set j .
  • a first step is to test whether the triangle pair (- ⁇ P 1 P 2 P 3 , ⁇ Q 1 Q 2 Q 3 ) should be rejected. It will be rejected if one of the following cases is true:
  • All the merge-pending global ID pairs are gathered together, each having the three statistical values, and are sorted in ascending order of the value B.
  • the merge-pending global ID pairs that belong to a greater number of well -aligned triangle pairs are given higher priority.
  • Each global ID pair is processed in turn, and if its values of N, A and B are within a specified threshold region, and if merging does not cause any set to have different points with the same global ID (as in cases 1 and 2) , then these two global IDs are merged together by assigning global ID n to all points with global ID m. Otherwise the pairs are not merged and the points with global IDs m or n are left unchanged.
  • Figures 8A-8D shows a group of points labelled as A, B, C, D, E, F, G, H, I, J, K, L, M and N. For these points it is considered that pairs of the points have been arranged in descending order of rank according to the rms residual of corresponding triangle pairs associated with the pairs of points.
  • the arrangement of pairs of points in descending order is as follows: AB, CD, EF, LM, KL BG, AH, DI, FJ, DE, BI, FI, JL and JM.
  • pair AB is given a global ID equal to non-negative integer 0 (case i above) .
  • pair CD is given a global ID equal to non- negative integer 1 (case i above) .
  • pair EF is given a global ID equal to non-negative integer 2 (case i above) .
  • pair LM is given a global ID equal to non-negative integer 3 (case i above) .
  • the next ranked pair KL includes point L, which was previously- given a global ID equal to 3 as part of pair LM.
  • K is assigned a global ID of 3 along with L and M (case ii above) .
  • G is assigned a global ID of 0.
  • H cannot truly be a match with A, because A forms a matching pair with B, and B and H are in the same set. Therefore, the AH match is ignored and point H is given a global ID equal to -1.
  • Point N has no match and it is also given a global ID of -1.
  • Point I is given a global ID of 1 based on the matching pair of DI and Point J is given a global ID of 2 based on the matching pair of FJ.
  • Pair DE includes point D that has a global ID of 1 and point E that has a global ID of 2. Therefore, global ID 2 and global ID 1 become a merge-pending global ID pair.
  • points C, D and I which have a global ID equal to 1 and none of points E, F and J, which have a global ID equal to 2 are in the same set, and their values of N, A, and B as defined above are determined to be within the specified threshold region, the points are merged and points E, F and J are assigned a new global ID equal to 1.
  • Pair BI includes point B that has a global ID of 0 and point I that has a global ID of 1.
  • global ID 0 and global ID 1 become a merge-pending global ID pair (0, 1) .
  • Points A, B and G, which have a global ID equal to 0 and points C, D, I, E, F and J, which have a global ID equal to 1 do not have any points in the same set .
  • the values of N, A, and B are determined not to be within the specified threshold region and therefore the global IDs of 0 and 1 are not merged.
  • matching pair FI is irrelevant.
  • the points in each set are relabelled so that the global IDs increases in an orderly manner, e.g. the first point in the first set has global ID 0, the second point in the first set has global ID 1, and so on.
  • each point in each set that matches with points in other sets are assigned global IDs.
  • pairs of matching points are assigned the same global ID. All the sets are simultaneously aligned using these matching point pairs in such a way that the overall rms residual of the point pairs is minimized.
  • the transformations of the sets are stored for future use . Simultaneous point alignment is performed for all the sets even though their orientations have already been found in a previous step. This is because the orientations found previously were only approximate due to the fact that the respective alignment transform functions were determined based on an average location that is a center of the respective clusters, and because the alignment transforms for each set pair were found sequentially, not simultaneously. When performed simultaneously over multiple iterations, all the sets are adjusted at the same time until the alignment solution converges .
  • Figure 9A shows an example of three individual sets of points, Set 0, Set 1 and Set 2 to be aligned.
  • Set 0 includes a triangle consisting of three points and a single point labelled as A.
  • Set 1 includes a triangle consisting of three points and a single point labelled as B.
  • Set 2 includes two groups, each including three points.
  • Figure 9B shows an alignment solution for Set 0, Set 1 and Set 2.
  • Each of the triangles of Set 0 and Set 1 are found to align with one of the respective triangles of Set 2.
  • Points A and B are not exactly aligned. However, if they are within an acceptable distance threshold, they are merged and assigned the same global ID.
  • step 155 can be repeated to re- align the sets, making use of new matches.
  • Step 160 is a decision point used to determine whether the assignment of global IDs is acceptable. If so, the transformations for the sets found in step 155 are output. If not, steps 140,145,150,155 are repeated for a next cluster combination in the list.
  • the method is used to match and align the same tie points on multiple images. After this is done, the surface are checked to determine whether of the surfaces of the object in the images are also aligned. In some embodiments this is done qualitatively by a user visually inspecting the surface after alignment is completed. In some embodiments the surface alignment with the object is determined by computing the "surface rms residual". If the surfaces align well, the result of global ID assignment is accepted.
  • tie points align well but the surfaces do not, for example when there are three tie points on an image forming an equilateral triangle. In such situations a user performing a visual inspection may be more appropriate for determining whether the assignment of global IDs is acceptable.
  • the user can transform all the images by the transformations found in step 155 and display all the transformed images together (with or without stitching) in a same computer window on the display, seeing visually how well they align.
  • the user arranges for the computer processor to determine the overall surface rms residual found by the simultaneous alignment of all the images and check whether it is below some threshold value.
  • step 160 if the result is not acceptable, a next cluster combination is selected from the sorted list generated in step 125 and steps 140-160 are repeated. This process continues until a suitable result is determined.
  • the global IDs of all matching points in all sets are output. From the output, it can be seen which point in a set matches which point in another set, based on the shared global IDs. All non-matching points may be given a rogue global ID of -1.
  • the algorithm may also output the rigid transformations on each set that align the sets towards the same reference coordinate system. These transformations have already been found by the simultaneous point alignment algorithm during the step "Align and merge close global IDs" 155. The inverses of these transformations are orientations of the sets with respect to the reference coordinate frame.
  • Figure 10 is a solution of the example of Figure 2, in which the global IDs for each point are in brackets by the local IDs.
  • Figure 1 is an example of a method for implementing the invention. More generally, in some embodiments of the invention some steps in Figure 1 can be omitted and the resulting method is still within the scope of the invention.
  • Figure 11 shows another embodiment of the invention that has some steps in common with Figure 1.
  • step 100 multiple sets of points on which the method will operate are input.
  • matching triangle pairs are formed directly from the points in the multiple sets, as opposed to using candidate edges as in Figure 1.
  • Steps 115 and 120 are similar to Figure 1.
  • a particular cluster combination is selected 130 to be operated on, but where the clusters are not sorted according to any particular criterion, the selection may be made randomly or based on some other factor.
  • global IDs are assigned to points in each set.
  • step 152 encompasses steps 140, 145, 150 and 155 as described above relating to Figure 1.
  • steps other than those specifically described with regard to Figure 1 are used to assign global IDs to points in the multiple sets.
  • steps 160 and 170 are the same as Figure 1.
  • another cluster is selected either randomly or based on some other factor. For example, the next best cluster may be based on sorted clusters as described above with regard to Figure 1.
  • the method may only be lacking some of the missing steps from Figure 1, but not as many as detailed in Figure 11.
  • additional steps to that of Figure 1 may be included in the method to provide additional improvement to the multiple image alignment method that would be known to one skilled in the art, that are not specifically detailed here, and still be considered within the scope of the invention.
  • Two of the ways in which the method can be extended are to allow user intervention to reduce the search size and to make the method capable of handling cases with very few points.
  • the user informs the algorithm which pairs of sets are disjoint (i.e. with no matching points) so that the algorithm does not have to look for matching triangle pairs for such pairs of sets.
  • a more convenient manner of providing the information is that a subfamily A of m sets is separate from another subfamily B of n sets, which implies m times n pairs of disjoint sets.
  • the user may provide the algorithm with the information that a particular point in one set matches with a particular point in another set so that it can enforce such a fact, or at least discard any matching that is inconsistent with such a fact .
  • Another approach is that the algorithm can be provided with information that particular sets of points should be matched first. If the result is acceptable, the result is saved and the algorithm is called again to match points for all the sets, giving the saved matches greater weight so that they have a higher chance of appearing in a final match. In some embodiments the saved matches are not given ultimate priority over all matches as newly added sets may add, change or even iivalidate the saved matches.
  • Figure 12A includes three overlapping sets Set 0, Set 1 and Set 2.
  • Sets 0 and 1 have one matching point in common.
  • Sets 0 and 2 have two matching points in common.
  • Sets 1 and 2 have three matching points in common.
  • these two sets can be aligned.
  • the points in Set 0 cannot be matched and Set 0 cannot be aLigned. This is because no matching triangle pairs can be formed.
  • One manner in which to solve this problem is to align Set 1 and Set 2 first and combine their points together to form a new set, Set 3. Then Set 0 and Set 3 will have three matching points between them and Set 0 can be aligned with respect to Set 3.
  • Figure 12B is more difficult to solve, since no pair o E sets have three matching points.
  • Sets 0 and 1 have two matching points in common.
  • Sets 0 and 2 have two matching points in common.
  • Sets 1 and 2 have two matching points in common.
  • the transformation of aligning a pair of triangles corresponds to a point.
  • the transformation to align a pair of edges corresponds to a curve with one degree of freedom as two sets can be rotated about the edge .
  • a curved surface with two degrees of freedom in a new six-dimensional space is formed. This surface intersects with the curve for Set Pair (0,2) at a unique point, which gives the transformations between the three sets.
  • implementation of the invention takes the form of a computer algorithm.
  • the algorithm provides simultaneous solution capability, as opposed to dealing with the sets in a pair-wise fashion or a sequential manner.
  • the computer algorithm is expressed as computer implemented program code that is stored on a computer readable medium.
  • the computer implemented program code can be run from the computer readable medium by a processing engine adapted to run such computer implemented program code.
  • Examples of types of computer readable media are portable computer readable media such as 3.5" floppy disks, compact disc ROM media, or a more fixed location computer readable media such as a hard disk media storage unit in a desktop computer, laptop computer or central server providing memory storage or a workstation.
  • the multiple 3D images for which embodiments of the invention will operate on are stored in a digital format on a computer readable memory.

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Vision & Pattern Recognition (AREA)
  • Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Health & Medical Sciences (AREA)
  • Computing Systems (AREA)
  • Evolutionary Biology (AREA)
  • Bioinformatics & Computational Biology (AREA)
  • Bioinformatics & Cheminformatics (AREA)
  • Life Sciences & Earth Sciences (AREA)
  • Artificial Intelligence (AREA)
  • Probability & Statistics with Applications (AREA)
  • Databases & Information Systems (AREA)
  • Evolutionary Computation (AREA)
  • General Health & Medical Sciences (AREA)
  • Medical Informatics (AREA)
  • Software Systems (AREA)
  • Multimedia (AREA)
  • Image Processing (AREA)

Abstract

L'invention concerne des procédés pour aligner des images multiples d'un objet tridimensionnel qui sont obtenues à partir de perspectives différentes. L'objet tridimensionnel est étiqueté avec des marqueurs situés sur la surface avant l'obtention des images ou un objet de référence avec des marqueurs sur celui-ci est placé au voisinage immédiat de l'objet. Des triangles de correspondance sont formés à partir des marqueurs sur des paires respectives d'images. Pour chacune des paires respectives d'images, une fonction de transformation est déterminée pour transformer une orientation d'un triangle d'une des images de la paire de triangles de correspondance en une orientation d'un triangle de l'autre image de la paire de triangles de correspondance. Sur la base du groupage de ces transformations, une fonction de transformation particulière est sélectionnée pour transformer une orientation de la première image en une orientation de la seconde image. Sur la base des orientations de chacune des images multiples les unes par rapport aux autres, les marqueurs sur chacune des images multiples sont affectés simultanément d'un identifiant qui indique le même marqueur sur toutes les images. À l'aide des identifiants affectés sur chaque image, les images multiples peuvent être alignées pour former le modèle tridimensionnel de l'objet.
PCT/CA2006/001083 2006-06-30 2006-06-30 Procédés pour une correspondance simultanée multiples ensembles de points Ceased WO2008000055A1 (fr)

Priority Applications (1)

Application Number Priority Date Filing Date Title
PCT/CA2006/001083 WO2008000055A1 (fr) 2006-06-30 2006-06-30 Procédés pour une correspondance simultanée multiples ensembles de points

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
PCT/CA2006/001083 WO2008000055A1 (fr) 2006-06-30 2006-06-30 Procédés pour une correspondance simultanée multiples ensembles de points

Publications (1)

Publication Number Publication Date
WO2008000055A1 true WO2008000055A1 (fr) 2008-01-03

Family

ID=38845057

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/CA2006/001083 Ceased WO2008000055A1 (fr) 2006-06-30 2006-06-30 Procédés pour une correspondance simultanée multiples ensembles de points

Country Status (1)

Country Link
WO (1) WO2008000055A1 (fr)

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
GB2458927A (en) * 2008-04-02 2009-10-07 Eykona Technologies Ltd 3D imaging system
US20130217996A1 (en) * 2010-09-16 2013-08-22 Ramot At Tel-Aviv University Ltd. Method and system for analyzing images
EP2988311A1 (fr) 2014-08-22 2016-02-24 ABB Technology Ltd Système électrique sous-marin compensé en pression

Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CA2244559A1 (fr) * 1997-08-05 1999-02-05 Canon Kabushiki Kaisha Appareil de traitement d'images
US6694064B1 (en) * 1999-11-19 2004-02-17 Positive Systems, Inc. Digital aerial image mosaic method and apparatus

Patent Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CA2244559A1 (fr) * 1997-08-05 1999-02-05 Canon Kabushiki Kaisha Appareil de traitement d'images
US6694064B1 (en) * 1999-11-19 2004-02-17 Positive Systems, Inc. Digital aerial image mosaic method and apparatus

Non-Patent Citations (4)

* Cited by examiner, † Cited by third party
Title
BEINAT A.: "A direct method for the simultaneous and optimal multidimensional models registration", IEEE/ISPRS JOINT WORKSHOP ON REMOTE SENSING AND DATA FUSION OVER URBAN AREAS, 8 November 2001 (2001-11-08) - 9 November 2001 (2001-11-09), pages 283 - 287 *
GUIDI G. ET AL.: "Fusion of range camera and photogrammetry: a systematic procedure for improving 3-D models metric accuracy", IEEE TRANSACTIONS ON SYSTEMS, MAN AND CYBERNETICS, PART B, vol. 33, no. 4, August 2003 (2003-08-01), pages 667 - 676 *
JOHNSON A. ET AL.: "Surface registration by matching oriented points", PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON RECENT ADVANCES IN 3-D DIGITAL IMAGING AND MODELING, 12 May 1997 (1997-05-12) - 15 May 1997 (1997-05-15), pages 121 - 128 *
WANG W. ET AL.: "3D shape measurement based on computer vision", PROCEEDINGS OF THE 2002 INTERNATIONAL CONFERENCE ON MACHINE LEARNING AND CYBERNETICS, vol. 2, 4 November 2002 (2002-11-04) - 5 November 2002 (2002-11-05), pages 910 - 914 *

Cited By (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
GB2458927A (en) * 2008-04-02 2009-10-07 Eykona Technologies Ltd 3D imaging system
GB2458927B (en) * 2008-04-02 2012-11-14 Eykona Technologies Ltd 3D Imaging system
US8773508B2 (en) 2008-04-02 2014-07-08 Fuel 3D Technologies Limited 3D imaging system
US20130217996A1 (en) * 2010-09-16 2013-08-22 Ramot At Tel-Aviv University Ltd. Method and system for analyzing images
US9153022B2 (en) * 2010-09-16 2015-10-06 Mor Research Applications Ltd. Method and system for analyzing craniofacial complex images
US9402565B2 (en) 2010-09-16 2016-08-02 Mor Research Applications Ltd. Method and system for analyzing craniofacial complex images
EP2988311A1 (fr) 2014-08-22 2016-02-24 ABB Technology Ltd Système électrique sous-marin compensé en pression

Similar Documents

Publication Publication Date Title
Chen et al. A robot vision system for recognizing 3D objects in low-order polynomial time
Chua et al. 3D free-form surface registration and object recognition
Keselman et al. Many-to-many graph matching via metric embedding
Willis et al. Computational reconstruction of ancient artifacts
US6591011B1 (en) Picture processing method and apparatus
US7027651B2 (en) Geometric hashing method for model-based recognition of an object
US20030067461A1 (en) Methods, apparatus and computer program products that reconstruct surfaces from data point sets
CN113111741B (zh) 一种基于三维特征点的装配状态识别方法
Bronstein et al. SHREC 2010: robust correspondence benchmark
CN105046684A (zh) 一种基于多边形广义霍夫变换的图像匹配方法
CN118674759B (zh) 一种异源点云数据的融合方法
CN101246595A (zh) 光学三维扫描系统中多视点云数据拼合方法
Cass Polynomial-time geometric matching for object recognition
Jin et al. Computing tëichmuller shape space
CN118334094A (zh) 一种基于三维点云的模型配准方法
CN119090797A (zh) 一种基于点云技术的齿轮参数测量方法
CN110838146A (zh) 一种共面交比约束的同名点匹配方法、系统、装置及介质
CN118196200A (zh) 基于三维激光点云的隧道爆破残孔检测方法、介质及设备
CN105740859B (zh) 一种基于几何测度和稀疏优化的三维兴趣点检测方法
WO2008000055A1 (fr) Procédés pour une correspondance simultanée multiples ensembles de points
CN114219857A (zh) 一种危化品仓储堆垛安全距离测量方法
TW201913421A (zh) 晶圓失效圖案分析方法
CN119359774A (zh) 一种用于点云数据配准的方法
CN112419464A (zh) 一种基于点云局部凹凸性的三维碎块拼接方法
CN119379761A (zh) 一种基于双视角点云配准的猪只体尺测量方法

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 06752855

Country of ref document: EP

Kind code of ref document: A1

NENP Non-entry into the national phase

Ref country code: DE

NENP Non-entry into the national phase

Ref country code: RU

32PN Ep: public notification in the ep bulletin as address of the adressee cannot be established

Free format text: NOTING OF LOSS OF RIGHTS PURSUANT TO RULE 112(1), EPC, EPO FORM 1205A SENT ON 17/04/09.

122 Ep: pct application non-entry in european phase

Ref document number: 06752855

Country of ref document: EP

Kind code of ref document: A1