1. _ Technical field The present invention relates to a method of automatically placing a first object onto a second object.

2. Prior art

Nowadays, a lot of products are manufactured in a fully or at least partly automated fashion. Often, this requires placing one object onto another object by a machine without human intervention, for example to permanently affix the first object to the second object. In mass production, it is highly desirable that the first object is always placed at exactly the same location onto the second object to keep the manufacturing tolerances as low as possible for the sake of a high product quality and to achieve a low scrap rate.

The second object may not always be positioned at the same location when the first object is placed onto it. This may be due to tolerances in the conveyor mechanism used to move the second object. In fact, when automatically placing the same object a certain number of times, the positions of the object will be distributed with a certain variance around the desired position. In addition, the orientation of the object might deviate from a desired orientation as well.

It is known to account for deviations in position and orientation of an object by using an optical recognition system to determine the translation and rotation of the object relative to a desired position and orientation and to correct for deviations in translation and rotation of the object when placing another object onto it. In this way, unwanted deviations may be compensated to a certain degree and manufacturing tolerances can be improved. However, known techniques fail when it comes to deformable or non-rigid objects, such as textiles. In contrast to rigid objects, deformable or non-rigid objects exhibit further degrees of freedom in addition to translation and rotation. For example, they may scale, bend, warp and/or shear, etc. Compensating for translation and rotation only is not sufficient to determine the correct position of the first object on the second object. In some situations, known techniques do not show any improvement with deformable or non-rigid objects and the first object is placed onto the second object in the wrong place most of the time. This results in higher manufacturing tolerances and scrap rate.

In view of these disadvantages, the problem underlying the present invention is to provide a method of automatically placing a first object onto a second object which reduces manufacturing tolerances and scrap rate even in the case of deformable or non- rigid objects.

2. Summary of the invention

This problem is solved by a method of automatically placing a first object onto a second object by a machine, comprising the steps of capturing a digital representation of the second object; determining a deformation of the second object based on the digital representation and a digital model of the second object; determining a second position of the first object on the second object based on a first position of the first object on the digital model and the deformation; and placing the first object at the second position onto the second object.

The method may be performed by any machine which is capable of automatically placing a first object onto a second object, such as a robot in its broadest sense. The method according to the invention advantageously considers the deformation experienced by the second object. Such a deformation may occur with deformable or non-rigid objects as explained. The deformation is relative to an“ideal”, un-deformed shape of the object which is given by a digital model of the object. The deformation is determined based on a digital representation of the actual object, as it is for example placed on a conveyor mechanism, and its digital (“ideal”) model. Due to the

deformations, the digital representation of the object will deviate from the digital model. Unlike the prior art, these deviations do not just rely on translation and rotation, but will also consider deviations due to deformations which occur with deformable, non-rigid objects.

According to the method of the invention, the“ideal” (first) position of the first object on the second object is known. However, if the first object was simply placed at this first position, not taking into account of the deformations, the actual position would be wrong, in the worst case leading to a nonconforming product. Therefore, the deformations are considered in that a second (updated) position is computed based on the desired (first) position and the determined deformations of the second object. Then the first object is placed on the second object.

In this way, the variance in the position of the first object on the second object is considerably reduced. As a result, manufacturing tolerances are reduced leading to higher product quality. Furthermore, as less products fail subsequent quality checks, the scrap rate is reduced as well.

In addition to the position of the first object, its orientation may be determined based on its orientation in the digital model and the determined deformation as well.

Capturing the digital representation of the second object may involve optical means. More particularly, capturing the digital representation of the second object may comprise taking a photo of the second object. Taking a photo to obtain the digital representation is very convenient as digital cameras for industry applications are readily available. Also, such cameras may have a high resolution, such that the digital representation may have a high accuracy.

The photo may be taken with a calibrated camera to obtain a rectified image of the second object. This allows to rectify the image, to correct any distortion of the camera and to reconstruct the actual position and shape of the second object.

The method may further comprise the step of transforming the image into a metric space using calibration information of the camera. In such a metric space, each pixel corresponds to a well-defined distance, e.g. l mm. In addition, the angles may be corrected, such that right angles show up with 90° in the rectified photo. Therefore, the digital representation of the object in the metric space is very close to the actual position and shape of the object in physical space.

The step of determining the deformation of the second object may comprise taking the difference between a reference photo and the photo of the second object. Taking the difference is rather simple to implement, but very reliable in detecting any deformation of the second object. The reference photo may show the location where the second object is to be placed, e.g. a conveyor belt, but without the second object.

The step of determining the second position of the first object on the second object may comprise applying a function which maps the first position to the second position. The function may be based on the determined deformation. Thus, the function may define a mapping M ² ® M ² which accounts for the deformation of the second object and the corrected position of the first object may be obtained by simply applying the function to the original position in the digital model of the second object.

The step of determining the deformation of the second object may comprise extracting an outline of the second object. The outline of an object can be detected against a differently colored background. Moreover, the outline provides all information which is necessary to determine the deformation of the object.

The step of determining the deformation of the second object may comprise finding a first plurality of features in the digital representation. Features are understood as distinct“landmarks” which can easily be detected, such as sharp comers, indentations, spikes, etc. Thus, the features may be characteristic features of the outline. In another example, the features may be intentionally applied to the second object. For example, characteristic symbols may be printed on the second object. The symbols may be part of the general design of the object. Thus, while the features or symbols may easily detected by an algorithm, a human may not perceive the features or symbols as “landmarks”.

The step of determining the deformation of the second object may comprise identifying a second plurality of features in the digital model corresponding to the first plurality of features. In this way, a mapping between the features of the digital model of the“ideal” object and the features in the digital representation of the actual object may be obtained to aid in determining the function.

The step of determining the deformation of the second object may comprise

determining a first plurality of points in the digital representation based on the first plurality of features and determining a second plurality of points in the digital model based on the second plurality of features. In this way, a“sparse” representation of features may be augmented by a“dense” representation of points. For example, the points may be densely located on the outline of the object.

The step of determining the deformation of the second object may comprise sampling a first path between at least two neighboring features of the first plurality of features uniformly with a predetermined number of points to obtain the first plurality of points and sampling a second path between at least two neighboring features of the second plurality of features uniformly with the predetermined number of points to obtain the second plurality of points. This allows to obtain a dense representation of points in both the digital model as well as the digital representation of the actual object which correspond to each other.

The method may further comprise determining the function, such that it maps the first plurality of points to the second plurality of points. In this way a mapping M ² M ² is obtained by means of the plurality of points. The plurality of points in both the digital model and the digital representation serve to determine the function - possibly with a few additional assumptions.

Determining the function may comprise enclosing the second plurality of points inside a uniform grid; expressing the coordinates of each point of the second plurality of points as a linear combination of first grid points; and solving for second grid points, such that each point of the first plurality of points when recomputed using the respective linear combination of second grid points coincides with a corresponding point of the second plurality of points. Coincidence in this context needs not to be exact. Rather, it is sufficient if the points coincide up to a small distance. Enclosing the object in a grid allows to determine the function eveiywhere on the object. For example, if the outline of the object is used to determine the deformation, it is possible by means of the grid to compute the function also at points which are spaced apart from the outline.

Note that the method described herein is not limited to fit a function that is defined on/by a structured/unstructured grid. Instead, any other suitable type of function (e.g. a polynomial, defined for example as radial basis functions) that can be used to describe deformations might be fitted.

The step of solving may comprise solving a least-squares problem involving an energy function. As explained, the coincidence between the points in the digital model and the digital representation needs not be exact, but may be in a least-squares sense. Using an energy function allows to account for deformations which are due to the rigid nature of the object and helps to model the object as rigid as possible. The residual deformations, which cannot be explained by rigid transformations (rotation and translation) are due to non-rigid deformations which cause the object to scale, bend, warp, shear, etc.

The energy function may measure the plausibility of the deformation of the second object under the assumption that the second object is as rigid as possible. Thus, the energy which cannot be explained by this assumption is due to non-rigid deformations.

The first object may be a patch, reinforcement or logo. The present invention can be advantageously applied to such kind of objects because any misplacement of such objects is immediately apparent even to the naked eye.

The second object may be a shoe upper. Shoe uppers tend to be rather flexible and can easily be deformed because they are transformed from a flat configuration into a three- dimensional configuration which is not possible without deformation. Thus, shoe uppers are particularly susceptible to the problems outlined above. Therefore, applying the invention to shoe uppers is particularly beneficial.

The digital model of the second object may be a computer-aided design, CAD, model. Using suitable CAD software, the second object, such as a shoe upper, can be developed by a designer. A CAD model is very accurate and can be exchanged with other designers or those being in charge of manufacturing by electronic means. Also, CAD allows to incorporate updates or amendments of the model rather quickly.

The method may further comprise the step of applying heat and/or pressure to fix the first object to the second object. In this way, the first object may be firmly attached to the second object. Thanks to the invention, a visual control of the position of the first object before permanently fixing it can be dispensed with because the invention assures that the position is correct even in the presence of deformations. A further aspect of the present invention is directed to a computer program comprising instructions which cause a computer to perform a method according to the invention and as described herein. Such a computer program can be supplied to a corresponding manufacturing machine to control the machine as described herein. A further aspect of the present invention is directed to a sports article manufactured according to a method of one of the preceding claims. Thanks to the invention, the manufacturing tolerances of such a sports article are veiy low. In addition, the scrap rate is low, such that the sports article can be manufactured at decreased costs. The sports article may be a sports shoe.

4. Short description of the figures

In the following, exemplary embodiments of the invention are described with reference to the figures. The figures show: Figs. lA-C an illustration of the problem underlying the present invention;

Fig. 2 a flowchart of an exemplary embodiment of the method

according to the invention;

Fig. 3A a photo of an actual deformed upper taken with a calibrated camera;

Fig. 3B distinct features on the outline of the upper of Fig. 3A; and

Figs. 4A and 4B an illustration of an aspect of the present invention. Detailed description of preferred embodiments

The problem underlying the present invention is illustrated by means of figures lA, lB and lC. In Fig. lA the outline na of an upper to for a shoe is shown. Such an upper is usually made from a textile material, such as a woven, knitted, mesh, etc. In figures lA, lB and lC the upper to is shown in a flat (2D) configuration. Of course, when the shoe upper 10 is finally integrated into a shoe, such as a sports shoe, the upper 10 is brought into a three-dimensional shape, for example by sewing, gluing and/or lasting the upper 10. Also, the upper 10 may be treated with heat and/or pressure, so that the upper 10 maintains its three-dimensional shape.

In the example of figures lA, lB and lC, a tongue 12 is connected to the upper. The tongue 12 is separated later in the process from the rest of the upper and sewn or glued into the midfoot area of the upper 10. Also, a patch 13 is shown which is placed on the upper during manufacturing. In this example, the patch 13 is placed in a heel region of the upper 10. The patch can be made for example from polyurethane (PU), such as thermoplastic polyurethane (TPU). The patch 13 is placed on the upper 10 in a fully automated fashion as will be described in more detail below.

Fig. lA shows a CAD (computer-aided design) model of the upper 10 as it is obtained for example by a CAD software running on a computer. The CAD model serves as a digital model of the upper 10 and represents the upper 10 as it should ideally result from the manufacturing process.

In Fig. lB, the CAD outline 11a of the upper 10 from Fig. lA is shown. Also, the patch 13 is shown in Fig. lB at its intended position on the upper 10, i.e. according to the CAD model of Fig. lA. In addition, the outline 11b of the upper 10 is shown in Fig. lB after a patch 13 was placed in a real manufacturing process. As shown in Fig. lB, the outline 11b is deformed with respect to the ideal outline 11a of the digital model of the upper 10. Such a deformation is due to the non-rigid nature of the textile material of the upper 10. The material may scale, bend, warp, shear, etc. when it is placed for example on a conveyor belt. Now, when the patch 13 is placed on the deformed upper 10, but at the position prescribed by the digital model, i.e. the CAD model, it will end up at the wrong position on the upper 10 as shown in Fig. lC. This figure shows the actual outline 11b of the distorted upper 10 with the placed patch 13. As can be seen by comparing figures lA and 1C, the patch is not at the position according to the CAD model. The distances of the patch 13 to the outline 11b are very different than in the model of Fig. lA.

While the problem has been described with respect to placing a patch 13 on a shoe upper 10, the problem generally exists when automatically placing a first object on a non-rigid second object. Thus, the solution provided by the present invention is not limited to shoe uppers, but can be applied to arbitraiy sports articles, fashion articles, products for the automotive industry, furniture industry, etc. Also, the first object may be a patch, reinforcement, logo, printing, etc.

Fig. 2 illustrates the method 20 according to the present invention by means of a flow- chart. Again, placing a patch 13 on a shoe upper 10 has been taken as the underlying example. However, as outlined above, the present invention is not limited to this example. Therefore, the invention is generally directed at a method of automatically placing a first object onto a second object by a machine. Such a machine may for example be a robot in its broadest sense.

According to the exemplary method 20, a photo of a current upper (such as upper 10) is taken in step 21. The current upper is the upper that has just been placed for example on a conveyor belt. This upper is to be provided with a patch in the example of Fig. 2. The photo may be taken by a camera which is suitable for industry applications. For example, the camera may be calibrated, so as to provide calibrated and rectified images in which image distortion is removed or significantly reduced.

In a step 22 the deformation of the current upper is analyzed based on the photo taken in the previous step and the CAD data. Generally, such analysis may be performed by a suitable computer, such as for example an embedded computer. The computer may be equipped with a GPU (graphics processing unit) and/or an ASIC (application-specific integrated circuit) which may accelerate the computations performed according to the method of the invention. The method described herein may be embodied in a computer program comprising instructions which cause the computer to perform the method. Such a computer program may be stored on a storage medium such as a USB stick, CD ROM, etc. or may be transmitted wirelessly or by wire. In the computer, the program may be stored in a RAM or ROM memoiy.

The mentioned CAD data is a digital model of the upper and defines, how an ideal upper should look like when it is placed for example on a conveyor belt. As outlined with respect to figures lA, lB and lC, due to deformations of the non-rigid material of the upper, the current upper can deviate from the CAD model.

Thus, the result of step 22 is a determination of the deformation of the upper based on the digital representation, i.e. the rectified photo, and the CAD model of the upper. A detailed description of this determination will be given with respect to figures 3A, 3B, 4A and 4B.

In step 23, the patch position is updated according to the computed deformation. Thus, instead of simply placing the patch at the position defined by the CAD model, the deformation of the upper is considered and the position of the patch on the current upper is updated. To this end, the position of the patch in the CAD model (first position) and the deformation is taken into account.

Finally, in method step 24, the patch is placed on the current upper at the updated position. The patch may be placed by a robot arm which is controlled by the computer which had previously computed the updated position. Alternatively, the updated position is provided to a separate control unit of the robot arm which uses the updated position in its preprogrammed routines and controls the robot arm accordingly.

Fig. 3A shows an exemplary photo of an actual upper 10 taken with a calibrated camera to obtain a rectified image of the upper 10. The shape or outline of the upper 10 contrasts with the lighter background 31, such that the shape or outline of the upper 10 can be extracted, for example by a subsequent edge-detection process. To obtain the rectified image in a metric space, calibration information of the camera is used. In such a metric space, each pixel corresponds to a well-defined distance, e.g. l mm. In addition, the angles are usually corrected, such that right angles show up with 90° in the rectified photo. Therefore, the digital representation of the object in the metric space is very close to the actual position and shape of the object in physical space.

In a preferred embodiment of the invention, the outline of the upper to is used to determine its deformation. To this end, the difference between a reference photo and the actual photo of the upper, such as the photo in Fig. 3A is taken. The reference photo may for example just show the location, e.g. a conveyor belt, where the upper 10 is to be placed. Taking the difference is then performed pixel-by-pixel resulting in pixels with a value near zero where just the background shows up in the photo and non-zero pixels in the area of the upper 10. This difference image can then be supplied to an edge detection process as known in the art to extract the outline of the upper 10.

An example of an outline 11b of an upper 10 extracted in this way is shown in Fig. 3B. This figure also shows a plurality of features of the outline 11b. Three of those features have been denoted by the reference numeral 32. Features 32 are distinct“landmarks” which can easily be detected, such as sharp comers, indentations, spikes, turning points of curvature, etc. Thus, the features 32 are characteristic features of the outline 11b. However, the features may also be intentionally applied to the upper 10. For example, characteristic symbols may be printed on the upper 10 by means of e.g. a screen printing process. The symbols may be part of the general design of the upper 10 as defined in the CAD model.

Features are not only identified in the digital representation of the current upper 10, i.e. the rectified photo of Fig. 3A, but also in the CAD model. The features in the CAD model correspond to the features extracted in the photo, i.e. there is a one-to-one mapping between both pluralities of features. Generally, however, it is sufficient if a few corresponding features are identified in the photo and the CAD model, i.e. there may be some features in the photo and/or the CAD model for which no corresponding feature exist. The features represent a sparse correspondence between the features in the photo and the CAD model. To obtain a dense correspondence, a path between two neighboring features is uniformly sampled with a given number of points for both the CAD data and the outline of the upper to in the photo. This results in a dense set of correspondences (c _j e M ² , pi e M ² ), where c _L denote the 2D positions in the CAD model and p _L the corresponding 2D positions on the distorted upper to. In this sense, the dense set is defined by the sparse features and the uniformly sampled points in between.

The points thus obtained can be used to define a function /: M ² M ² that maps the features onto each other, i.e. such that /( ) = p _t V i = 0 ... n. To fit the function / to the actual distribution an assumption is made. The function / should favor physically plausible deformations as the upper is made of a real material and is subject to a real deformation underlying the laws of physics. In the exemplary embodiment, an as-rigid- as-possible (ARAP) deformation is assumed which shows a plausible physical behavior.

To actually fit the function /, the source geometry, i.e. the points in the CAD model, are enclosed inside a uniform grid. The coordinate of each point of the dense

representation of the outline is then expressed a linear combination of grid points. This is done for the points on the outline in the CAD model.

Fig. 4A shows the outline na of the upper to according to the CAD model and a uniform grid enclosing the upper to. Also shown is the deformed outline lib of the upper to which defines the“target” of the function / to be found by the fit.

Then, grid points in the rectified photo are solved for, such that each point on the outline in the CAD model when recomputed using the respective linear combination of grid points coincides with a corresponding point on the outline in the photo.

Coincidence in this context needs not to be exact. Rather, it is sufficient if the points coincide up to a small distance. Enclosing the upper in a grid allows to determine the function everywhere on the object, not just on the outline.

In the exemplary embodiment, the step of solving for the grid points in the photo comprises solving a least-squares problem involving an energy function. As explained, the coincidence between the points in the digital model and the digital representation needs not be exact, but may be in a least-squares sense. Using an energy function allows to account for deformations which are due to the rigid nature of the object and helps to model the object as rigid as possible. The residual deformations, which cannot be explained by rigid transformations (rotation and translation) are due to non-rigid deformations which cause the object to scale, bend, warp, shear, etc.

Note that the method described herein is not limited to fit a function that is defined on/by a structured/unstructured grid. Instead, any other suitable type of function (e.g. a polynomial, defined for example as radial basis functions) that can be used to describe deformations might be fitted.

The energy function measures the plausibility of the deformation of the upper under the assumption that the upper is as rigid as possible. Thus, the energy which cannot be explained by this assumption is due to non-rigid deformations.

Fig. 4B shows the computed space deformation. The uniform grid of Fig. 4A is transformed into a warped grid defined by the deformation of the upper 10. Also shown is the CAD outline 11a of Fig. 4A after application of the space deformation and the outline 11b according to the rectified photo, i.e. the current deformed upper 10. Both outlines coincide veiy well.

By applying the procedure described above, the function / can finally be determined from the fit. The function / is defined by the distorted grid and maps arbitrary points of the two-dimensional CAD model onto the rectified photo of the distorted upper 10.

Thus, in method step 24 instead of simply placing a patch 13 using the position and orientation defined in the CAD model, both are updated by applying the deformation to it. Instead of placing the patch 13 at position v, the patch 13 is placed at position f( ).

Instead of just updating the position and/or orientation of the patch, the entire shape could be updated in other embodiments. In case of printing onto the upper 10 (or any other object), a distorted shape could be printed that will move into the desired shape once the upper 10 is relaxed. This could be obtained by warping the entire tool path and not only the one distinct position. The procedure described above to determine the function / is partly described in Zollhofer et al.,“GPU based ARAP Deformation using Volumetric Lattices”. In this paper, a lattice based as-rigid-as-possible transformation is applied to a toy model.

In the exemplary embodiment of the invention applied to a shoe upper 10, heat and/or pressure is applied to fix the patch 13 to the upper 10. In this way, the patch 13 is firmly attached to the upper 10.