TECHNICAL FIELD

The present invention refers to apparatuses such as robots or automatic positioning devices, e.g. mechanical linear or rotational devices. More particularly, the present invention is related to the provision of an automatic segmentation and trajectory generation from a 3D geometry for surface inspection or processing (painting, polishing...) of a target by a robot or automatic positioning devices, that reduces the overall cost it takes the robot to completely inspect the target surface.

BACKGROUND

Automation of many processes has led to the deployment of robots and automatic positioning devices intended to conduct tasks that formerly required human intervention.

The main issue in process automation, especially in processes requiring to inspect/process an entire target, is the following: whilst a human being is able to adapt to different types of objects and clearly see whether she/he had inspected/processed the entire target or which parts had yet to be inspected/processed, a robot or automatism typically does not have such a cognitive capacity to adapt to non-previously programmed targets and decide if the process it automates has been performed on the entire target, or has gone around the target multiple times or still has parts left uninspected, all in a fully autonomous manner.

To have an effective robot or positioning device automation it is necessary to avoid both problematic behaviors, otherwise the process becomes ineffective owing to the noninspected or non-processed parts, and inefficient owing to the repeated inspection or processing of certain parts of the target.

There have been attempts to improve automated surface inspection or processing by robots. However, the proposals that have been done so far (scientific publications, patents and commercial products) have substantial limitations to accomplish it. Most of them, especially in patent proposals, present the automatic robot trajectories generation challenges but they do not provide a detailed technical solution to accomplish it. The proposals that provide a technical description or a demo are focused in flat or quasi-flat surfaces and/or with predefined trajectories like zigzag trajectories or parallel lines, and the methodology of flat surfaces cannot be extended to non-flat 3D surfaces because of their complexity. In addition, in the case of predefined trajectories, the full coverage of the workpiece is not guaranteed by design as the trajectories are defined and afterwards projected on the 3D surface were lacks and holes usually appear and therefore do not allow to provide a general solution.

The present disclosure presents a complete technical methodology to work directly with 3D curved surfaces (which includes flat surfaces) such that its processing covers all the surface by design and that generates an optimal path in terms of robot cost. The use of mesh segmentation methods based on point or curvature deviation allows generating a set of processing points such that more points are generated in more curved regions so as to guarantee a detailed processing of the object. With a simulation of the robot device the set of points are ordered such that the robot cost is optimized, being all the process to obtain the final trajectory completely automatic.

SUMMARY

A first aspect of the disclosure relates to a computer-implemented method for automated surface inspection or processing of a target by a robot (or an automatic positioning device), comprising: providing a 3D model of the target to be inspected or processed, the 3D model being a surface mesh; converting the 3D model into a polygon mesh with mesh segmentation; computing a set of bounding boxes for each polygon face in the polygon mesh, each set of bounding boxes comprising one or more bounding boxes, and each set of bounding boxes covering the entire surface of the respective polygon face, that is to say, the volume of the one or more bounding boxes encloses the respective polygon face; providing, for each polygon face, a first list indicative of all polygon faces that are adjacent to each respective polygon face; projecting a centroid onto the 3D model (i.e. surface mesh) for each bounding box of each set of bounding boxes resulting from the step of computing the sets of bounding boxes; providing, for each bounding box of each set of bounding boxes, a second list indicative of all projected centroids of bounding boxes of a polygon face where said bounding boxes are adjacent to the bounding box of the respective projected centroid of the same polygon face, the second list thereby being a list indicative of adjacent projected centroids in each polygon face; providing, for each pair of adjacent polygon faces of the polygon mesh according to the first list, a third list indicative of ? pairs of projected centroids, where N > 1, where a first projected centroid of each pair is of a first polygon face of the pair, and a second projected centroid of each pair is of a second polygon face of the pair, and where the first and second projected centroids are of bounding boxes that are not surrounded by other bounding boxes of the same respective polygon face; providing an undirected graph with both the second list and the third list; estimating robot cost for travelling along each edge in the undirected graph thereby providing a weighted undirected graph, the robot cost preferably being one or a combination of (e.g. weighted combination): time cost, energy cost, product usage cost, produced elements cost; connecting all pairs of unconnected vertices in the weighted undirected graph with an edge and assign a robot cost for each such edge such that the robot cost of each edge is equal to: a total robot cost for the shortest path between the unconnected vertices present in the weighted undirected graph, or a predetermined robot cost value not lower than the maximum robot cost in the weighted undirected graph; computing a path for surface inspection or processing of the target by processing the resulting weighted undirected complete graph so that: all vertices are visited only once and the robot cost for visiting all vertices is minimized; and providing the path for surface inspection or processing to the robot or automatic positioning device and commanding the robot or automatic positioning device to inspect or process the surface of the target according to the path so that the robot or automatic positioning device inspects or processes the surface at each vertex in the path.

The graph being considered (i.e. the graph provided with both the second list and the third list) is, in general, not necessarily complete, although in very particular scenarios the initial (in general, incomplete) graph could be complete from the beginning and so no additional edges should be added. One skilled in the art will understand that the procedure of constructing the complete graph (by connecting all pairs of unconnected vertices) is done only when the graph is incomplete.

Both the incomplete graph (in which not all the vertices are joined by an edge) and the complete graph (in which all the vertices are joined by an edge) are undirected.

For other applications different than inspection (e.g. cleaning), the robot or automatic positioning device may not only process the surface specifically only at the vertices, but also along a path over the surface.

In the following, the term ‘inspect’ and its derivations will be used to refer to ‘inspect or process’. Further, in the following, the term ‘robot’ refers to a robot as known in the art, or an automatic positioning device, e.g. a mechanical linear axis or a rotation device.

The path obtained enables the robot to inspect the target in an efficient and exhaustive manner because, in several inspection points, the robot will be inspecting the target’s complete surface. Further, the path enables the robot to inspect the target in such a way that no portion of the surface of the target lacks robot’s inspection. The inspection points order to be followed completing the trajectory has been defined to minimize the robot cost to complete the given trajectory.

The 3D model (e.g. CAD 3D model) is represented by a surface mesh. The surface mesh structure, although it has vertices, edges and faces, is a totally different structure than the graph constructed with a different set of points and edges.

The conversion of the digital 3D model, which can be generated as known in the art and with any format known in the art, into the polygon mesh is done by mesh segmentation algorithms known in the art, preferably based on point, curvature or normal variation, such as, but without limitation, Variational Shape Approximation, VSA. The mesh segmentation provides a plurality of polygonal faces that can be effectively processed to compute and, thus, provide bounding boxes. For instance, the mesh segmentation algorithm provides a polygon mesh formed by n-gons, i.e. polygons with different n edges, that represents an approximation to the mesh of the 3D model, which also follows a curvature of the 3D model; the n number of edges may be dependent upon the complexity and details of the surface mesh so that the n-gons provide a more or less accurate representation thereof. In the nonlimiting example in which the VSA is used as mesh segmentation, the surface mesh needs to be a triangular mesh that is a 2-manifold. For other mesh segmentation methods, the allowed input may be different.

The bounding boxes in the sets of bounding boxes computed are preferably 6-sided prisms, which preferably have rectangular or parallelogram shapes (including combinations thereof), but other boxes and shapes are possible as well within the scope of the present disclosure (in which case they are preferably regular prisms with sides as regular polygons). 6-sided bounding boxes enable the provision of centroids in a computationally cost-effective manner. The sets of bounding boxes enclose the respective polygon face preferably in the manner that minimize the volume of the set of bounding boxes while having at least some sides (i.e. faces) that at least contain one point (even if it is by being tangent) of the respective polygon face. Different ways of computing the bounding boxes known in the art are possible within the scope of the present disclosure, for example with the way described in C. T. Chang et. al. (2011). "Fast oriented bounding box optimization on the rotation group SO(3, R)", ACM Trans. Graph. 30, 122:1-122:16, which is incorporated in its entirety herein by reference, that combines the Nelder-Mead algorithm and a metaheuristic genetic algorithm and results in a computationally efficient technique. When the set of bounding boxes for a polygon face comprises a single bounding box, it is that bounding box that is preferably minimal in volume and has at least some sides that at least contain one point of the respective polygon face. When the set of bounding boxes for a polygon face comprises more than one bounding box, each bounding box of the set is adjacent to one or more other bounding boxes in the set (i.e. the bounding boxes are not apart and thus one touches the other), or at least partially superposes to one or more other bounding boxes in the set.

The computation of one or more bounding boxes is preferably made dependent upon both the dimensions of the surface that the robot can inspect each time, i.e. the coverage that the robot or a tool thereof has at a predetermined distance from the surface of the target, and the dimensions of the surface of the polygon face. Too large polygon face surfaces (relative to the robot inspection surface) or, in other words, too small robot inspection surfaces (relative to the polygon face surface) results in the computation of sets of bounding boxes with a plurality of bounding boxes.

Centroids of each bounding box are then projected onto the respective parts of the surface mesh of the 3D model by way of vectors normal thereto. The centroids are preferably those corresponding to the largest two-dimensional surface of the bounding box (in rectangular 6-sided prisms, these comprise the two largest perpendicular edges of the bounding box; there are two such surfaces and any one of the two can be used). A nonlimiting example of intersection algorithm that can be used, is an intersection algorithm based on the construction of a hierarchy of axis-aligned bounding boxes (AABBs), see e.g. G. van den Bergen. (1997). “Efficient collision detection of complex deformable models using AABB trees”, Journal of graphics tools, 2(4), 1-13.

The second and third lists provided indicate the connections of the different centroids intra- and inter-polygon face, respectively; for the third list, the first list indicating which polygon faces are adjacent to each polygon face is used. Afterwards, the undirected graph is provided with both the centroids as vertices and the connections as edges, and the cost for the robot to move along the different edges is estimated. The costs can be estimated by providing the projected centroids and the connections among them by means of either a simulation method where the kinematics of the robot is included or direct measurements of robot while executing the path between each and every pair of connected points of the undirected graph.

All pairs of vertices (that is to say, of centroids) that were not connected in the undirected graph or weighted undirected graph become connected with a certain robot cost. The imposition of the addition of edges makes the problem to be later solved for obtaining the path, namely a variant of the travelling salesman problem, to be computationally simpler and/or solvable with methods known in the art. The problem to be later solved for obtaining the path is a variant of the travelling salesman problem (TSP), instead of the travelling salesman problem. In applications, such as the inspection, in which the path is not needed to be closed (in such a case the problem should not be called a TSP, but a variant of the TSP). However, certain available routines to obtain a close-to-optimal solution use algorithms that solve the TSP (not the variant) and, therefore, look for a closed path.

Lastly, the path is computed by processing the weighted undirected graph modified such that the graph does not have any pair of unconnected vertices, in other words, any two vertices are joined with an edge, and therefore the complete weighted graph is processed. The criteria for computing the path are that all vertices are visited only once, and the total robot cost is minimized. The total robot cost is a sum of the robot costs for travelling along the edges providing the path for visiting all the vertices just once. The goal is to look for the optimal path that visits all the points (projected centroids) only once and that minimizes the total traveling cost, as defined by the variant of the TSP.

Some exemplary techniques suitable for the path computation are: J. K. Lenstra & A. H. G. Rinnooy Kan. (1975). “Some Simple Applications of the Travelling Salesman Problem”, Operational Research Quarterly (1970-1977), 26(4), 717-733; T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, “Introduction to algorithms", page 1111 and subsequent, third ed., MIT Press, Cambridge, MA, 2009; and N. Christofides, “Worst-case analysis of a new heuristic for the travelling salesman problem”, Tech, report, Graduate School of Industrial Administration (Carnegie-Mellon University), 1976. These exemplary techniques for the path computation are incorporated by reference in this description.

Because the condition that the graph does not have any pair of unconnected vertices has been imposed, it is guaranteed that the Travelling Salesman Problem (TSP) for this graph has a solution because it is well-known that any complete graph has a Hamiltonian cycle (this is because we can start at any vertex and go successively to any other vertex not yet visited). As a consequence, a statement as a variant of the TSP (not requiring the path to be closed), will be solvable as well. If, for the kind of application, a closed path is required, the TSP can be simply solved with the algorithms known in the literature, such as, but without limitation, the ones described in the references above. If a closed path is not required, and so a variant of the TSP must be solved, it can be proceed in two different ways (both are valid):

1. Solve a TSP with the algorithms known in the literature. A closed path is obtained. Then one edge of the closed path can simply be deleted, preferably the one with the highest cost, to get an open path.

2. Add a dummy point connected with all the other vertices of the graph with a zero cost edge. Solve a TSP (and a closed path is obtained). Remove the dummy point from the solution, so that an open path is obtained.

Preferably, the costs (weights of the graph) provided by the cost function satisfy the triangle inequality for all edges. This way, it is guaranteed that that the given solution by some algorithms known in the literature is optimal or close to optimal. In less preferable embodiments in which the triangle inequality is not satisfied for some edges, the given solution could be less close to the optimal one, although it will also be guaranteed that all vertices can be visited only once.

The path can be provided to the robot for automated surface inspection; or, alternatively, to the inspected target or platform where the inspected target is for moving the target around the robot according to the path, in which case the robot is kept static and inspects the target while the target moves around the robot. The path includes a plurality of ordered inspection points. The robot (or target in the alternative case) sequentially covers all inspection points by moving sequentially to from one inspection point to another in the specified order. At each inspection point, the robot will inspect a portion of the surface of the target according to an inspection area or work area, i.e. the surface inspected or processed by the robot. In this sense, for each application the orientation of the tool will be defined and for a general case, as in some embodiments, the robot is preferably commanded to inspect the target with an orientation such that: at the inspection points, a center point of the inspection area of the robot coincides with the inspection point, and the center point of the inspection area of the robot projects onto the surface of the target orthogonally.

With regards to the robot cost for moving along each edge of the graph, being this edge defined by a start node and an end node without any intermediate nodes:

The time cost is the time that the robot takes to move from the start node to the end node of the edge. This cost estimation is done setting a base speed, so every cost is calculated under the same conditions. The base speed can be any feasible speed that the robot can operate.

The energy cost is the amount of power that the robot needs to move from the start node to the end node. This cost estimation is done setting a base speed, so every cost is calculated under the same conditions. The base speed can be any feasible speed that the robot can operate.

The product usage cost is the amount of product used to perform the processing task while moving from the start node to the end node. This cost estimation is made setting a base speed and a base product usage per time unit (e.g. seconds) of use or area, so every cost is calculated under the same conditions. The base speed can be any feasible speed that the robot can operate. The base product usage can be any feasible amount that the processing can operate.

Produced elements cost is the amount of production done in a given period of time, where production can be number of unitary products for independent elements production process or the amount of material produced for continuous processes. This cost estimation is made setting a base speed and a base product usage per time unit (e.g. seconds) of use or area, so every cost is calculated under the same conditions. The base speed can be any feasible speed that the robot can operate. The base product usage can be any feasible amount that the processing can operate.

To estimate the cost of the robot to move from one (initial) position to another (target), that is to say, to move along an edge in the graph (although in practice, the robot may not follow the straight line, but some curve) different approaches can be considered. For example, the distance between two configurations of the space of the robot can be interpreted as a vector of differences of the parameter values of all actuators of the robot. In embodiments in which a primary objective is to minimize inspection time, the limiting velocities of each of the joints/actuator are chosen as the terms in the cost function, since they are a basis for the movement of the robot whatever the displacement mode. The existence of singular positions between the study points, where very high and damaging velocities can occur may also be used as a criterion.

In some embodiments, in the step of computing the path for surface inspection or processing of the target, the weighted graph is processed so that the computed path closes at the initial vertex.

In some embodiments, the processing in the step of computing the path comprises introducing a predetermined inspection point (also known in the art as dummy inspection point), the predetermined inspection point preferably being introduced such that distances to every other point in the weighted complete graph is zero. In some embodiments, the step of computing the path comprises removing the predetermined inspection point after computing the path.

In other words, the weighted complete graph with the dummy inspection point can be solved as a travelling salesman problem, and the path being closed. Then, in some cases, the solution to the problem, i.e. the path, can be processed to remove the dummy inspection point, if added, to obtain the actual path, which will then be open.

In some embodiments, in the step of connecting all pairs of unconnected vertices in the weighted undirected graph with an edge, the robot cost is assigned for each such edge such that the robot cost further fulfills the triangle inequality. The fulfillment of the triangle inequality might result in a simpler path generation computation-wise.

In some embodiments, the method further comprises providing a target frame for each projected centroid by: computing a normal vector, N _k , for each projected centroid (where k refers to a particular projected centroid) on a portion of the surface mesh (i.e. the 3D model) corresponding to the respective polygon face of the polygon mesh; computing, for each normal vector N _k resulting from the step of computing the normal vector, a normalized projection of a first edge onto a tangent plane defined by the respective normal vector /V _fe and containing the respective projected centroid thereby providing a first vector, t _{k l} , the first edge being an edge of the respective set of bounding boxes or an edge of a prism-shaped bounding box enclosing the respective set of bounding boxes; and computing, for each first vector t _{k l} resulting from the step of computing the normalized projection, a second vector, t _{k 2} , by computing a cross product of the respective normal vector N _k and the respective first vector, i.e. t _{k 2} = N _k x t _{k l} each target frame comprises a set formed by the normal vector N _k , the first vector t _{fe l} and the second vector t _{fc 2} ; and the step of computing the path further comprises including an orientation per each vertex such that inspection or processing of the surface is aligned with a direction of the normal vector N _K of the respective target frame, and first and second edge boundaries, which are perpendicular, are respectively aligned with the first and second vectors t _{fe l} , t _{k 2} .

The step of providing a target frame for each projected centroid can be done almost at the same time as in the step of computing the projected centroids.

Although the inspection or processing of the surface (namely, camera) is positioned according to the normal vector N _k , within the scope of the present disclosure it is both possible and allowed to define another target frame by means of spatial rotations of the given target frame {N _k , t _{k l} , t _{k 2} } such that, in some embodiments, a new transformed “normal” vector so to speak is a vector lying on a 3D half-space defined by the corresponding tangent plane at the projected centroid (generated by t _{k l} and t _{k 2} ) and that contains the normal vector. The new target frame will be indicative of how another device shall be positioned to perform some action according to the deviated “normal” vector, which is not normal anymore.

The edge boundaries are of one of the following: the inspection or processing field of view itself, a bounding rectangle containing an inspection or processing field of view, and a two-dimensional frame of the inspection or processing field of view.

The edge boundaries are determined by the particularities of the robot and/or the inspection process, for example, a resolution of the device of the robot for inspection, e.g. camera, spray, polishing tool, etc. By way of example, in the case of a camera, the edge boundaries can be the width and height of the photos it takes. By way of example, in the case of a spray or polishing tool, the edge boundaries can be the width and height of the spray or polishing tool area as applied from a predetermined distance on a surface of the target; the predetermined distance is one of the particularities of the robot and/or the inspection process.

The provision of target frames enables the addition of orientations in the path computed so that the robot inspects the target in a specific manner that does not leave any uninspected portion on the surface of the target. This is so because the robot has, with the added orientations in the path, all the data necessary not just to position itself but also to orient itself for maximizing the effectiveness of the inspection area. In this sense, the edge boundaries of the inspection area are to be aligned with the two vectors to provide full orientation to the robot.

In some embodiments, the step of providing the third list comprises: computing, for each pair of adjacent polygon faces of the polygon mesh according to the first list, a distance between all pairs of projected centroids of the first polygon face and of the second polygon face whose bounding boxes are not enclosed by other bounding boxes of the same polygon face; and selecting, for each pair of adjacent polygon faces of the polygon mesh according to the first list, the minimum distance computed and multiplying said minimum distance by a predetermined factor k, where k is a real number greater than 1 ,00; and the third list is provided for each pair of adjacent polygon faces such that it includes all the pairs of the projected centroids of the respective pair of adjacent polygon faces that have a computed distance less than or equal to the respective minimum distance multiplied by the predetermined factor k.

The third list provided results in the connection of multiple pairs of centroids of adjacent polygon faces that, according to such a list, will be close enough to expect a robot cost lower than other possible connections with greater robot cost, thereby simplifying the computation of the path. Notwithstanding, it is noted that more connections between adjacent polygon faces could enable the computation of a better path when the trajectory that the robot must follow is less costly (when fewer change of directions and/or less abrupt changes of direction are needed), but it also increases the computation complexity of the cost estimation. In fact, all unconnected pairs of vertices will eventually be connected, and the solution may become more accurate as more connections are set before.

The predetermined factor k, which forces projected centroids to have at least one connection, can be set depending on the features of the 3D model or the polygon mesh so that the path to be computed will have more or fewer leg options to form the path. The predetermined factor k might be e.g. set beforehand, set by the at least one processor running the method upon evaluating the 3D model or the polygon mesh, or manually set by a user.

In some embodiments, each third list provided fulfills the following relationship: 2 < N < n • n ₂ where n is a number of bounding boxes of the first polygon face and n ₂ is a number of bounding boxes of the second polygon face.

It is preferred to have an N value equal to or greater than 2 so that each pair of adjacent polygon faces is connected with a plurality of connections, thereby making possible more effective paths for automated surface inspection. Likewise, having an upper limit for IV is also convenient to avoid having an undirected graph with all possible centroid connections between adjacent polygon faces whose robot cost is to be estimated e.g. in the cases where the running time of the estimation routine is high. Notwithstanding, all unconnected pairs of vertices will eventually be connected, and the solution may become more accurate as more connections are set before.

In some embodiments, the method further comprises, before connecting all pairs of unconnected vertices in the weighted undirected graph with an edge, connecting, each first vertex vi that is only connected with a second vertex V2 in the undirected graph (points or vertices which have only one connection (edge) are also referred to as lonely points), with at least a third vertex V3, where: when the second vertex V2 is connected with at least two vertices other than the first vertex vi , the at least third vertex V3 is one or more vertices of the at least two vertices that are closest to the first vertex vi , and when the second vertex V2 is only connected with a single vertex other than the first vertex vi , finding a vertex V4 directly or indirectly connected with the second vertex V2 (with a minimum total number of connections to reach vertex V4 from the second vertex V2) that is connected with at least two vertices other than the vertex it is coming from, and the at least third vertex V3 is one or more vertices of said at least two vertices (the one or more vertices being that or those closest to the first vertex vi).

The connection of lonely vertices with other vertices improves the possible path that can be provided with the method since the vertices can be reached with at least two pathways. In other words, the connection of lonely vertices will give more flexibility later in the search of the optimal path when solving the Travelling salesman Problem, because these new edges will provide alternative paths with known estimated costs in the optimal tour, which will provide a more accurate solution than if the cost of these edges is not estimated.

Each vertex of the at least third vertex V3 is such that the connection with the first vertex vi preferably fulfills the following: d ₁ < f • d ₂ , where: d _± is the distance between the first vertex vi and the at least third vertex V3; d ₂ is the minimum distance between the first vertex vi and each vertex of the at least third vertex V3; and f is a predetermined factor greater than 1 ,00. When multiple vertices fulfill this relationship, all such vertices are preferably connected with the first vertex vi.

In some embodiments, the step of computing the sets of bounding boxes further comprises splitting up each computed bounding box in the set of bounding boxes whose largest surface has a size greater than a predetermined maximum size into a plurality of bounding boxes such that a largest surface thereof has a size not greater than the predetermined maximum size.

Splitting up the bounding boxes in multiple bounding boxes is preferable for enabling the robot to inspect the surface of the target at a closer distance, something that in turn increases the precision and accuracy of the inspection. This is so because providing multiple bounding boxes also results in the provision of more centroids, and thus inspection points in the computed path. The predetermined maximum size can be set based on the particularities of the robot and/or the inspection process, for example, a resolution of the device of the robot for inspection, e.g. camera, spray, polishing tool, etc., the largest surface of the bounding box that is preferably used for centroid projection will, thus, be coverable by the robot at the inspection point.

It will be noted that, in some embodiments, one or some bounding boxes resulting from the splitting up do not enclose any portion of the polygon face. Likewise, it will be noted that, in some embodiments, one or several bounding boxes resulting from the splitting up do not have sides that contain a point to the portion of the polygon face that they enclose, or only one or several sides (i.e. faces) contain these points.

In some embodiments, in the step of splitting up the computed bounding boxes in the set of bounding boxes, each bounding box is split up in the minimum number of bounding boxes that make the size of the largest surface thereof not to be greater than the predetermined maximum size.

This splitting up results in the provision of the minimum number of inspection points that are necessary for the inspection by the robot according to the particularities of the robot and/or the inspection process.

In some embodiments, the largest surfaces of the plurality of bounding boxes that each computed bounding box is split up into is a plurality of rectangles (rectangle splitting).

Preferably, the rectangles have their two perpendicular edges dimensioned in such a way that a length of each edge is equal to a respective perpendicular edge boundary of the inspection of the surface of the target (i.e. field of view of the camera), or is smaller than the respective perpendicular edge boundary.

In some embodiments, the largest surfaces of the plurality of bounding boxes that each computed bounding box is split up into is a plurality of circles (circular splitting). In some of these embodiments, a rectangle or square is provided inside each circle of the plurality of circles as a bounding box.

The splitting up of largest surfaces into circles contained in the field of view of the robot (or a processing device thereof) makes possible to inspect the surface of the target with the robot not having any particular angle when oriented towards the surface of the target; in other words, when the robot is facing the surface of the target according to the orthogonal arrangement thereto or according to the normal vector, any angle/rotation about said axis towards the surface is possible while ensuring the full inspection coverage of the target. The computation of centroids is preferably made from a rectangle within each circle.

The circles that the largest surfaces are split up into have a radius equal to half of a shortest edge of the field of view of the camera, which yields the circle that the robot inspects regardless of the rotation thereof. These circles, in turn, enable the provision of squares inscribed therein with edge equal to the radius of the circle times square root of two, hence each bounding box fits inside such square.

In some embodiments, the method further comprises flipping at least some target frames to be processed or inspected by the robot to minimize a global angle deviation between a frame and adjacent frames thereof, thereby providing a smoother set of frames to be processed or inspected; the flipping of said target frames is a 180° rotation of the frames. In some other embodiments, the method further comprises making a global smoothing of at least some target frames to be processed or inspected by the robot to minimize a global angle deviation between a frame and adjacent frames thereof, thereby providing a smoother set of frames to be processed or inspected.

Techniques for frame smoothing are known in the art, for example but without limitation, "Mixed-Integer Quadrangulation" of Bommes et al., which achieves a global smoothing of the frame network.

Frames to be processed or inspected are sets of three orthogonal vectors (like e.g. a set formed by normal vector /V _fe , first vector t _{k l} and second vector t _{k 2} as explained before) in which one of them indicates the direction in which the robot will process or inspect, and the other two vectors determine the orientation of a tool of the robot, thereby providing the processing or inspection area of the robot at inspection points, for example target frames. In some occasions the orientation of the robot with respect to the target does not affect the quality of the inspection, but flipping the frame so that it is upwards or downwards (e.g. when the frames are obtained from square or rectangular splitting) or arbitrarily rotated (e.g. when the frames are obtained from circular splitting) may result in a smoother inspection. Flipped frames and arbitrarily rotated frames, depending on the type of frames, thus maintain the same normal related properties of the non-flipped frames or non-rotated frames and globally covering the same surface that the non-flipped or non-rotated frames cover. Frame flipping or rotation might lead to a cost minimization in some applications.

Where any rotation of the processing frames around their normal vector is allowed while covering the full processing object, a global smoothing of the processing frames can be performed to get a frame network that will be better in terms of performance and cost minimization for some applications.

In some embodiments, the step of commanding the robot includes making the robot to inspect or process the surface according to the orientation given by each target frame. In some embodiments, the commanding includes making the robot to inspect or process the surface so that, at each vertex, it orients itself towards the surface with the vertex projecting onto the surface orthogonally.

In some embodiments, the robot processes the surface with a tool. The robot comprises the tool, and the tool comprises one of: a camera, a painting spray, and a mechanical sander.

In some embodiments, the 3D model is a triangular surface mesh that is both manifold and connected. A vertex on a surface mesh is defined as being regular if it does not have incident singular edges, i.e. those that are shared by three or more faces. A surface mesh is defined as being a manifold if every vertex is regular.

In some embodiments, the method further comprises receiving the 3D model from a computing device.

In some embodiments, the method further comprises producing the 3D model in a 3D modelling program.

In some embodiments, the method further comprises scanning the target, and producing the 3D model based on the scan. The scanning of the target can be with a technique known in the art, for instance processing of images capturing the target from different positions such that the entire surface is captured in a plurality of photos, with laser scanning, etc.

The method is fully automated (does not require human intervention in placing inspection points on the surface, nor their ordering). Additionally, once a proper mesh segmentation is done, the surface segmentation considers, also fully automatically, the curvature of the surface and proceeds in accordance with the inspection experience that highly curved regions require more tool positions (smaller segments) when compared to flat regions where fewer positions are sufficient. On the other hand, the algorithm offers a set of handful parameters that control, e.g., distance of the tool with respect to the to-be-inspected surface or the trade-off between the computational time to solve the Travel Salesman Problem (TSP) and the optimality of the solution.

A second aspect of the present disclosure relates to a data processing device comprising means adapted to carry out the steps of a method of the first aspect of the disclosure.

The data processing device may comprise at least one processor, and at least one memory storing instructions or computer program code that configure, that is to say, that program the data processing device to perform the steps of the method.

The data processing device is, in some embodiments, a controller or controlling device of the robot (or the automatic positioning device) that is embedded thereto or is at least communicatively coupled therewith, either in wired form or in wireless form.

A third aspect of the present disclosure relates to a system comprising the data processing device of the second aspect of the disclosure, and the robot (or the automatic positioning device).

In some embodiments, the system further comprises the target.

A fourth aspect of the present disclosure relates to a robot (or an automatic positioning device) comprising the data processing device of the second aspect of the disclosure.

A fifth aspect of the present disclosure relates to a computer program product comprising instructions which, when the program is executed by a computer, cause the computer to carry out the method of the first aspect of the disclosure.

Upon running the computer program product on one or more processors of the computer, the computer provides the path for the robot and, optionally, commands the robot to inspect the target following the path provided.

In some embodiments, the computer program product is embodied on a non- transitory computer-readable medium or a computer-readable data carrier has the computer program product stored thereon.

A sixth aspect of the disclosure relates to a data carrier signal carrying a computer program product according to the fifth aspect of the disclosure.

Similar advantages as those described for the first aspect of the disclosure are also applicable to the second, third, fourth, fifth, and sixth aspects of the disclosure.

BRIEF DESCRIPTION OF THE DRAWINGS

To complete the description and for a better understanding of the invention, a set of drawings is provided. Said drawings form an integral part of the description and illustrate embodiments of the invention, which should not be interpreted as restricting the scope of the invention, but just as examples of how the invention can be carried out. The drawings comprise the following figures:

Figure 1 diagrammatically shows a method in accordance with embodiments.

Figures 2A-2B show a surface mesh of a 3D model and a polygon mesh thereof provided by mesh segmentation.

Figure 3 shows the difference between a polygon centroid and a bounding box centroid.

Figure 4 shows a polygon face with a plurality of bounding boxes and centroids as provided in some embodiments.

Figures 5A-5D show connections between bounding boxes of polygon faces as provided in some embodiments.

Figures 6A-6B show two different cases of how lonely vertices are connected with other vertices in some embodiments.

Figures 7, 8 and 9 show paths for surface inspection or processing on different targets as provided in some embodiments.

Figures 10A-10D illustrate stages of a car door test case used to validate the proposed method.

Figures 11A-11 B show inspection trajectories used to validate the proposed method.

DESCRIPTION OF WAYS OF CARRYING OUT THE INVENTION

Figure 1 diagrammatically shows a method in accordance with embodiments. The method, which is implemented in a computer by means of e.g. a data stream or a computer program code, includes a step whereby it provides 105 a 3D model, as a surface mesh, of a target to be inspected or processed.

The method also includes a step whereby it converts 110 the 3D model provided 105 into a polygon mesh with mesh segmentation.

The method also includes a step whereby it computes 115 a set of bounding boxes for each polygon face in the polygon mesh converted 110 into. The sets of bounding boxes have one or more bounding boxes, e.g. two, three, five, ten, etc. The entire surface of the polygon face is at least enclosed by the entire volume of the set of bounding boxes. When the set has more than one bounding box, the set has a continuum of bounding boxes by having each bounding box be adjacent to (i.e. in contact with) or at least partially superposed (at least part of the volume of one bounding box is within at least part of the volume of another bounding box) to one or more other bounding boxes in the set.

The method also includes a step whereby, for each polygon face in the polygon mesh, it provides 120 a first list indicative of all polygon faces that are adjacent to each respective polygon face.

The method also includes a step whereby it projects 125 a centroid onto the surface mesh of the 3D model provided 105 for each bounding box of each set of bounding boxes resulting from the step of computing 115 the sets of bounding boxes.

The method also includes a step whereby, for each bounding box of each set of bounding boxes computed 115, it provides 130 a second list indicative of all projected 125 centroids of bounding boxes of a polygon face where said bounding boxes are adjacent to the bounding box of the respective projected centroid of the same polygon face. The second list is thus a list indicative of adjacent projected centroids in each polygon face.

The method also includes a step whereby, for each pair of adjacent polygon faces of the polygon mesh according to the first list, it provides 135 a third list indicative of N pairs of projected centroids, with N > 1. A first projected centroid of each pair is of a first polygon face of the pair, and a second projected centroid of each pair is of a second polygon face of the pair. The first and second projected centroids are of bounding boxes that are not surrounded by other bounding boxes of the same respective polygon face.

The method also includes a step whereby it provides 140 an undirected graph with both the second list and the third list.

The method also includes a step whereby it estimates 145 robot cost for travelling along each edge in the undirected graph thereby providing a weighted undirected graph.

The method also includes a step whereby it connects 150 all pairs of unconnected vertices in the weighted undirected graph with an edge, so that the undirected graph becomes complete. It also assigns a robot cost for each such edge such that the robot cost of each edge is equal to: a total robot cost for a shortest path between the unconnected vertices present in the weighted undirected graph, or a predetermined robot cost value not lower than the maximum robot cost in the weighted undirected graph.

The method also includes a step whereby it computes 155 a path for surface inspection or processing of the target by processing the weighted undirected complete graph so that: all vertices are visited only once, and the robot cost for visiting all vertices is minimized. The path computation 155 is conducted after the connection 150 step by processing the weighted undirected complete graph as resulting from the connection 150 step.

Figure 2A shows a surface mesh of a 3D model (e.g. like that provided in step 105 of Figure 1) and Figure 2B shows a polygon mesh of the same 3D model provided by mesh segmentation, like e.g. VSA. The surface and polygon meshes are of a handle of a car, thus if a method according to the present disclosure were to be applied to this exemplary case, the target would be the handle of the car. It will be noted that the method of the present disclosure can be applied to various targets like objects, assemblies, people, etc.

The 3D model is a surface mesh with a plurality of polygon faces that are typically triangles 20, but could be differently-shaped as well. The mesh segmentation may have polygon faces in the form of triangles or other n-gons. For example, the surface mesh like that shown in Figure 2A is approximated with a polygon mesh made up of n-gonal polygon faces 22, where n is equal to or greater than three. For instance, the polygon faces 22 resulting from the VSA may have and typically have a different number of sides. As known in the art, finer or coarser n-gons can be provided with the mesh segmentation based on parameters thereof. In any case, the polygon faces 22 follow the curvature of the original polygon mesh.

Figure 3 shows the difference between a polygon centroid 32 and a bounding box centroid 36.

A polygon face 22, which can be an n-gon, has multiple sides that form either a non- planar polygon face 22 or a planar polygon face 22. The overall polygon mesh, like that in Figure 2B, might occupy a volume in a three-dimensional volume where some polygon faces 22 go inside the page or protrude therefrom to follow the curvature of the door handle.

A bounding box 24, 26 is a three-dimensional volume enclosing the surface of the polygon face 22 or part of the surface thereof based on the entire polygon mesh, even though in the representation of Figure 3 it appears as if having two dimensions only because the third dimension corresponds to the axis perpendicular to the surface of the page. The representation of Figure 3 is, in fact, that of a largest surface 25 of a bounding box 24, 26. When a single bounding box, which relates to the robot inspection surface, cannot enclose the entirety of the polygon face 22, a set of bounding boxes connected by adjacency or superposition is provided so that the resulting three-dimensional volume encloses the entirety of the polygon face 22.

It can be seen that the centroid 36 of the largest surface 25 of the bounding box 24, 26 is at the center of the largest surface 25, whereas the polygon centroid 32 is typically offset from the center of the largest surface 25 of the bounding box 24, 26.

For example, when a camera is used as inspecting tool, the centroid of a bounding box is a better focal point for the camera than the actual centroid of the polygon, see Figure 3. It is also computationally cheaper to compute the centroid of the bounding box. Therefore, this focal point is preferably used.

Figure 4 shows a polygon face 22 with a plurality of bounding boxes 26a-26c and centroids 36a-36c as provided in some embodiments. Although nine bounding boxes and centroids are illustrated in Figure 4, only three of each have been referenced with reference signs for the sake of clarity.

A bounding box 24 for the entire polygon face 22 is shown. In some embodiments of the disclosure, a bounding box 24 is split up into a plurality of bounding boxes 26a-26c so as to make surface inspection of a target more accurate. Some or all bounding boxes 26a-26c enclose a portion of the polygon face 22 but one or some may not, and in any case, there can be bounding boxes that do not have any side (or at least some sides) thereof that contain at least one point of the respective portion 28a-28c of the polygon face 22 that they enclose.

Preferably, each bounding box 24, 26a-26c is a rectangular prism. In contrast with the representation of Figure 3, in Figure 4 it can be seen that the bounding boxes 24, 26a-26c are three-dimensional volumes; further, one of the three dimensions thereof usually has a length shorter than lengths of the other two dimensions, and although it depends on the polygon mesh and the mesh segmentation, typically the length of said third dimension is considerably smaller than the length of the other two dimensions, e.g. 10 times smaller, 50 times smaller, or even more.

A centroid 36a-36c can be retrieved for each respective bounding box 26a-26c, preferably on the largest surface of each bounding box 26a-26c.

Figures 5A-5D show connections, namely edges, between bounding boxes 24a, 24b of polygon faces 22a, 22b as provided in some embodiments. Although the bounding boxes 24a, 24b have been split up so that respective centroids 36a, 36b could have been retrieved for projection thereto onto a surface mesh of a 3D model, the pluralities of bounding boxes have not been illustrated for the sake of clarity only. Additionally, only a subset of the different elements presented in Figures 5A-5D have been referenced with reference signs for the sake of clarity only. Even if it is perhaps not apparent from these Figures, it is noted that the centroids 36a, 36b are projected onto the mesh (not illustrated for the sake of clarity only) as it has been previously disclosed.

The polygon faces 22a, 22b are adjacent, which can be indicated in a list to that end, e.g. a first list.

Regarding Figure 5A, adjacent centroids 36a of a first polygon face 22a are connectable with connections or edges 40a, which can be indicated in a list to that end, e.g. a second list. Similarly, adjacent centroids 36b of a second polygon face 22b are connectable with connections or edges 40b, which can be indicated in the same list to that end, e.g. the second list.

Regarding Figure 5B, having regard that the two polygon faces 22a, 22b are adjacent as indicated in e.g. the first list, at least one centroid 36a of the first polygon face 22a and at least one centroid 36b of the second polygon face 36b are connectable with a connection or edge 40c, which can be indicated in a list to that end, e.g. a third list.

Regarding Figures 5C and 5D, further centroids of both the first polygon face 22a and second polygon face 22b are connectable with connections or edges 40c, which can be indicated in the same list to that end, e.g. the third list.

The number of connections or edges 40c between centroids 36a, 36b of pairs of adjacent polygon face 22a, 22b is preferably within a predetermined range. The predetermined range can be configured so as to provide a balance between possible legs of a path to be provided, and the processing power needed for computing the path.

Figures 6A-6B show two different cases of how lonely vertices 38a are connected with other vertices in some embodiments. The addition of edges to lonely points is an optional step before estimating the robot costs (weights) (and then constructing the complete graph connecting all pairs of unconnected vertices), that can provide a better solution in the end (because these costs will be estimated as well).

In Figure 6A, a lonely first vertex 38a is only connected with a second vertex 38b by way of edge 40a. In order to connect the lonely first vertex 38a with other vertices, the number of connections of the second vertex 38b is evaluated. If it has at least three connections with vertices, from which at least one is the lonely first vertex 38a, then one or more vertices that it is connected with are to become connected with the lonely first vertex 38a. In this case, a third vertex 38c that is connected with the second vertex 38b through a connection or edge 40b, and that is the closest to the lonely first vertex 38a, is connected with the first vertex 38a by way of an added connection or edge 40c (shown with dashed line for illustrative purposes only).

A length of the added connections or edges, in this case just one added connection or edge 40c, is either: the minimum distance among all distances between pairs of vertices that have, as one vertex, the first vertex 38a and, as another vertex, each of the vertices connected to the second vertex 38b; or less than or equal to said minimum distance multiplied by a predetermined factor f greater than 1 ,00; by way of example, the predetermined factor f is 1 ,2 or 1 ,5 or 2,0, etc.

So when multiple vertices are at a distance from the first vertex 38a that fulfill the above relationship, i.e. the resulting length of the connection or edge is equal to or less than the minimum distance times the predetermined factor / , all such multiple vertices are connected with the first vertex 38a.

In Figure 6B, the second vertex 38b has just two connections 40a, 40b, one with the first vertex 38a itself and one with a third vertex 38c. Accordingly, the additional connection(s) of the first vertex 38a will rely on this third vertex 38c or in the first subsequent vertex that has at least three connections. In this case, the third vertex 38c has more than two connections, and one of the vertices 38d that both: (1) is connected with vertex 38c (and which is not the second vertex 38b that it is coming from with the first vertex 38a as origin) via edge 40c, and (2) is closest to the first vertex 38a; is to be connected with the first vertex 38a with the additional edge 40d (shown with dashed line for illustrative purposes only).

As described with reference to Figure 6A, vertices like the vertex 38d which are connected with 38c (and which is not 38b) that fulfill the relationship of their distance to the first vertex 38a being less than or equal to the length of the additional edge 40d multiplied by a predetermined factor / may be connected with the first vertex 38a as well.

Figures 7, 8 and 9 show paths 50 for surface inspection or processing on different targets 60, 61, 62 as provided in some embodiments. Particularly, in Figure 7 the target 60 is a teddy bear, in Figure 8 the target 61 is an ellipsoid and in Figure 9 the target 62 is a back bumper. Note that the target in Figure 9, for illustrative purposes only, has been drawn without showing the triangles of the surface mesh and using some transparency to capture the shape of the whole object.

As it can be seen, the paths 50 provided comprise a polyline that although appear as not following a smooth trajectory due to considerable direction changes so as to cover each vertex 38, a robot can smooth the overall path 50 by going from one inspection point to another with curved trajectories, for instance but without limitation, with inverse kinematics. All vertices 38 are visited, they are visited only once and, in some embodiments, the path closes at the starting point. The robot cost for following the entire paths has been minimized with the weighted undirected graph provided in the embodiments.

In summary, the proposed method for automated surface inspection or processing of a target by a robot takes a CAD geometry of a to-be-inspected workpiece as an input and designs a path for the robot as an output. The algorithm takes the object’s boundary (as a surface mesh) and segments it into smaller patches. These smaller patches are constructed in such a way that most of them are visible from a tool (such as a camera) within a given distance. If some patches (in fact the bounding boxes of the patches) still do not meet the single-visibility condition, the corresponding bounding boxes are further subdivided.

Once the points have been validated, an undirected graph is then constructed where vertices of the graph represent a position of the tool (such as a camera mounted on the endeffector of the robot) capturing (and fully containing) a single patch, and edges of the graph represent motions of the robot from one position to another. The edges are provided by cost values obtained in a virtual simulator and that correspond to the cost (such as time) of the motion.

Then, based on the associated costs, and after connecting with an edge each pair of points (so obtaining a complete graph with costs), an inspection trajectory optimization is formulated as a Travel Salesman Problem (TSP) or as a variant of the TSP and heuristic methods are used to find a close-to-optimal solution. The given list of ordered points is translated into a final robot routine.

Next, a case study is provided for demonstrating the efficiency of the proposed method applied to the inspection of a part using a 7-DoF KUKA robot. A 2D camera has been attached to the end-effector of the robot. The camera, which preferably includes an optical lens for focusing, records an image at the inspection point and sends it to a computer or processing unit. In particular, a scale model of a car door geometry has been 3D printed. The CAD file is the front panel of the car door. For accessibility reasons, the inspection workpiece was scaled down to approximately 27 x 27 cm, (see Fig. 10A). The inspection distance can be adjusted by selecting the focal length (several standard commercial options are available). In the current use case, an 8mm lens disposed at 10cm has been used. In other use cases with a 12mm lens disposed at 5cm has been used. The car door geometry was segmented and the corresponding bounding boxes split so as to guarantee that the region represented by each bounding box is seen from a single inspection viewpoint of the camera. Segmentation was performed using the VSA method (see Fig. 10B). The computed list of inspection points and their frame orientations are shown in Fig. 10C. The accessibility of the inspection points was pre-validated by the KUKA robot and the connectivity graph was constructed. An optimized inspection path was calculated and then validated in two ways: virtually and physically.

First, the inspection trajectory was monitored in a virtual environment created in the software CoppeliaSim, a state-of-the art robotics simulator where both the inspection robot with a virtual inspection head and the to-be-inspected object were loaded, see Fig. 10D. It can be observed that the inspection head is a provided by a virtual rod that is pointing to the inspection point, and should coincide with the surface normal at the inspection point. This fact corresponds to the objective that the axis of the camera is positioned orthogonally to the surface, i.e., the screen of the camera is parallel to the tangent plane of the surface at the inspection point (and therefore minimizes the image distortion). The position of the camera met this orthogonality requirement at all the inspection points.

Second, the algorithm on the 3D printed workpiece was validated in a real environment using the 7-DoF KUKA robot.

In both environments, the proposed algorithm was implemented and compared to another inspection method. The algorithm has been implemented in C++ and using some packages and routines from the Computational Geometry Algorithms Library (CGAL, 2021 , https://www.cgal.org) and the Boost Graph Library (BGL, 2020, http://www.boost.org). The Eigen library (2021, http://eigen.tuxfamily.org/) is used optionally for the “global smoothing” step. Two specific trajectories have been compared (Fig. 11): Fig. 11A shows a trajectory computed in an automated way using the proposed TSP algorithm according to this disclosure, that is to say, using costs between pairs of neighbouring points (and adding costs satisfying the triangle inequality for the unestimated connections of the corresponding complete graph in a way according to this disclosure). Fig. 11 B shows a Zig-Zag trajectory, which is a user-designed trajectory that arranges the inspection points in a zig-zag fashion in a descending order according to the z-coordinates of the inspection points.

It has been observed that the Zig-Zag path (Fig. 11 B) is slower. It is remarkable that the proposed algorithm generates a trajectory in a fully automated way while ensuring that the whole object is inspected. The generated trajectory is close-to-optimal (and better than automatic naive attempts like the zig-zag).

In this text, the term “comprises” and its derivations (such as “comprising”, etc.) should not be understood in an excluding sense, that is, these terms should not be interpreted as excluding the possibility that what is described and defined may include further elements, steps, etc.

On the other hand, the invention is obviously not limited to the specific embodiment(s) described herein, but also encompasses any variations that may be considered by any person skilled in the art (for example, as regards the choice of materials, dimensions, components, configuration, etc.), within the general scope of the invention as defined in the claims.