Patent Description:
Object recognition is a key-enabler in various technical application areas, such as autonomous driving in which object recognition may be used to detect and recognize objects in sensor data acquired by one or more sensors integrated into a vehicle. For example, other road users (cars, pedestrians, etc.) or traffic signs may be recognized in the image data acquired by a camera sensor. In some cases, the output of the object recognition may be used to control actuators, such as actuators involved in the steering and/or braking of the vehicle, e.g., to autonomously avoid collisions with other road users.

There are various other uses for object recognition, for example in robotics where it may enable a robot to recognize objects in its environment and act accordingly, but also for enabling character recognition, pose recognition, searching in images, etc..

It is known to use machine learning techniques for object recognition. This typically involves training a learnable model, e.g., a neural network or the like, with a large set of training data which resembles the type of sensor data to which the learnable model is to be applied. Disadvantageously, such training data typically needs to be manually annotated, which may be time consuming and costly. Moreover, if after deployment the characteristics of the sensor data change, for example, due to a different type of camera being used, the machine learnable model may have to be retrained.

The publication "<NPL>, empirically compares four local search algorithms for correlation clustering by applying these to a variety of instances of the correlation clustering problem for the tasks of image segmentation, hand-written digit classification and social network analysis. For example, it is described to train a Siamese CNN to predict, for any pair of images, whether they depict the same or distinct digits. The probabilities predicted by the Siamese CNN define an instance of the correlation clustering problem for the complete graph whose nodes are the test images. In the empirical comparison, the combination of the use of Greedy Additive Edge Contraction (GAEC) followed by Kernighan-Lin (KL) is described.

It would be desirable to enable object recognition which addresses one or more of the disadvantages of the above-described machine learning based approach.

The following measures address this disadvantage(s) by performing object recognition in a geometric domain based on a geometric template of the object which is to be recognized and based on input data which represents input points and which may in some embodiments be obtained by extracting points of interest from sensor data.

In accordance with a first aspect of the invention, a computer-implemented method and a system are provided for object recognition, as defined by claim <NUM> and <NUM>, respectively. In accordance with a further aspect of the invention, a computer-readable medium is provided comprising data representing instructions arranged to cause a processor system to perform the computer-implemented method, as defined by claim <NUM>.

Advantageous embodiments are disclosed by the dependent claims.

The above measures provide a computer-implemented method and system for object recognition in a geometric domain. Namely, input data is accessed which comprises input points defined as coordinates in a coordinate system, for example as 3D or 2D coordinates defined in a 3D Euclidean space. Such points may for example be obtained by processing sensor data to extract points of interest from the sensor data. The result may elsewhere be referred to as a 'input point cloud' by resembling a cloud in 3D space. In addition, template data is accessed which comprises a finite number of template points and which are defined as coordinates in the same type of coordinate system. Such template points represent a geometric template of an object, in that each point may represent a geometric point of interest of the object and their relative position may be indicative of an overall geometry of the object. For example, the template points may define points of interest of the exterior of a vehicle, such as its corners. The template points are labelled to distinguish respective parts of the object. Such labelling may, but does not need to represent a semantic labelling. In some embodiments, the labelling may be a contiguous indexing of the template points within the coordinate system, e.g., <NUM>, <NUM>, <NUM>, <NUM>, etc..

The object recognition can then be performed in the geometric domain on the following basis: an undirected weighted graph G = (V, E) is constructed having nodes V representing the input points and edges E in between the nodes. Occurrences or partial occurrences of the object in the input data can now be detected on the basis of the system and method assigning edge labels to the edges E to define cuts in the graph to obtain a decomposition into one or more clusters representing (partial) objects. Such edge labels may represent binary labels either defining a connection, e.g., <NUM>, or a cut, e.g., <NUM>, between a pair of nodes, and may thereby partition the graph into disjoint subsets representing clusters of nodes. Such type of node clustering is known per se from the field of graph theory. In addition, node labels are assigned to the nodes V to identify a respective node as representing a respective part of a respective object. The object recognition may therefore recognize a (partial) object in the input data by forming a cluster of nodes in the graph by edge cuts and labelling the cluster's nodes in accordance with the labels of all or a part of the template points. If the cluster contains all labels of the template points, the object may be detected in the input data in its entirety, and otherwise in part.

The object recognition is thus performed by edge and node labelling, which in turn involves the following. Firstly, a cost function is provided which expresses a scale-invariant similarity between a given triangle in the input points and a given triangle in the geometric template. In other words, the cost function may determine the similarity between a pair of three input points and three template points in a scale-invariant manner. Here, 'scale-invariant' may refer to the similarity measure being invariant to similarity transformations, such as translation, rotation, reflection and scaling. The similarity measure may be defined in various ways, but may in general define a negative contribution to the cost function, in that a maximal similarity may correspond to a local minimum in the cost function. The similarity measure, for a respective pair of triangles, only contribute to the cost function if the labelling of the nodes matches the labelling of the template points and the nodes are part of a same cluster, and otherwise does not contribute (i.e., provides a zero contribution). The similarity measure may thus represent a conditional component of the cost function and may reward an edge and node labelling by which a cluster of nodes is created of which the labels match those of the template points, or at least those of a subset of the template points.

On the basis of the cost function, a first local search algorithm is applied to an initial version of the undirected weighted graph which may be maximally partitioned, in that each edge label may define a cut causing all nodes to be clustered in separate clusters, and in which the nodes are not yet labelled. The first local search algorithm, which may be a so-called greedy algorithm, is used to obtain an initial edge and node labelling which according to the cost function may represent a local minimum, but which is not guaranteed or in fact likely not to represent a global minimum yet which may be considered as an 'initial solution' to the problem of object recognition. In determining the initial edge and node labelling, the first local search algorithm, in an iterative process, connects nodes by edge labelling to form clusters in the graph and label nodes, so as to arrive at the initial solution.

Having obtained the initial edge and node labelling, a second local search algorithm is applied, which seeks to obtain an improvement in the initial local minimum. Compared to the first local search algorithm, the second local search algorithm can iteratively move nodes between clusters by edge re-labelling, instead of only being able to connect nodes, and to relabel nodes. Thereby, the second local search algorithm may arrive at a minimum which typically represents an improvement over the initial solution, or at least arrives at the same solution if no improvement can be achieved. The result may be a partitioned and labelled graph. The assigned edge labels and node labels are then output as object recognition data and thereby represent a result of the object recognition. As will be elucidated elsewhere, the object recognition data may then be used for various purposes, including but not limited to the control of one or more actuators based on the object recognition data.

The above measures enable object recognition based on a geometric template of the object which is to be recognized and based on input data which represents input points and which may in some embodiments be obtained by extracting points of interest from sensor data. Accordingly, the object recognition operates in a geometric domain which may represent an abstraction from sensor data and which thereby may be less dependent on a particular type of sensor data or a particular type of sensor, which may otherwise be the case for machine-learning based object recognition which is directly learned on the sensor data. In particular, by using a scale-invariant similarity measure, the object recognition may be less sensitive to various geometric distortions between input data, including perspective projections. Furthermore, the use of a triangle-based similarity measure allows also partial objects to be detected as also partially detected objects may contribute to a local minimum in the cost function. Such partial detection is highly relevant in real-life applications in which an object is often partially occluded by another object. For example, a car may be partially occluded by a billboard, but it may nevertheless be valuable to detect the car as it may represent an obstacle for an autonomous driving system.

The above measures further specifically establish a two-step approach to object recognition in the geometric domain by applying two different local search algorithms sequentially. This aspect is based on the insight that the performance of local search algorithms which are capable of moving nodes between clusters and thereby have a large degree of exploratory freedom may greatly depend on the initialization, in that a poor initialization (e.g., fully unlabeled and unconnected graph, or randomly labelled edges and nodes) typically provides a (very) poor outcome. Therefore, beforehand, a local search algorithm is applied to the graph which aims at only providing an acceptable initial solution. This 'first' local search algorithm can iteratively connect and label nodes and thereby have a lower degree of exploratory freedom than the second local search algorithm, and thereby may provide an acceptable result even from a fully unlabeled and unconnected graph. Having obtained the initial solution in the form of the initial edge and node labelling, the second local search algorithm then seeks to obtain an improvement in the initial local minimum by exploiting its larger degree of exploratory freedom. Thereby, the two-step approach may overcome the problem of initialization in graph-based object recognition.

Optionally, the cost function (cλu) expresses the similarity between respective triangles as a function of angles defining the triangles. The angles defining a respective triangle have been found to be well-suited to be used in a scale-invariant similarity measure.

Optionally, the method further comprises determining the similarity as the function of the angles defining the triangles by projecting the angles of a respective triangle as a 3D coordinate onto a 2D simplex and by calculating a distance between projected coordinates of the triangles on the 2D simplex.

Given that the angles defining a triangle, they also define a 3D coordinate in a 3D coordinate system, e.g., (α, β, γ) representing the angles α, β and γ, the similarity between two triangles may be expressed as a distance between their coordinates in 3D. However, since the 3D coordinates lie on a 2D simplex in the 3D coordinate system and the angles always sum up to <NUM>° degrees a similarity measure may be obtained by determining the distance on the 2D simplex, for example by making use of the Mahalanobis-distance.

Optionally, the second local search algorithm is a Kernighan-Lin (KL) algorithm. The KL algorithm has been found to be well-suited to, on the basis of the given cost function, provide a node and edge labelling in the graph and thereby recognize (partial) objects in the input data. However, the KL algorithm has been found to perform inadequately when it is poorly initialized, and therefore in accordance with the above measures the KL algorithm is preceded by a first local search algorithm providing an initial node and edge labelling which surprisingly greatly improves the overall object recognition.

Optionally, the first local search algorithm is a Greedy Additive Edge Contraction (GAEC) algorithm. The GAEC algorithm has been found to be able to provide an acceptable initialization to the KL-algorithm on the basis of an unlabeled graph.

Optionally, the geometric template data comprises template points representing a compound geometric template of multiple objects, wherein the template points are labelled to distinguish respective parts of respective ones of the multiple objects.

Optionally, the method further comprises accessing sensor data acquired by a sensor and generating the input points by extracting points of interest from the sensor data. Such sensor data may be accessed via a sensor data interface from any type of sensor which provides sensor data from which geometrically-defined points of interest may be extracted. This may include sensors which capture image data, such as camera sensors, but also depth sensors (time of flight, range), lidar sensors, radar sensors and the like.

Optionally, the sensor data is image data acquired by a camera and the method comprises generating the input points by extracting the points of interest as keypoints from the image data. Such keypoints may for example represent corners.

Optionally, the image data is 2D image data and the method comprises generating the input points by extracting the keypoints from the 2D image data and back-projecting said extracted keypoints into a 3D coordinate system based on depth information for the 2D image data. Effectively, by combining the 2D image data with depth information, e.g., as obtained from a stereoscopic camera system or additional depth sensor, 3D keypoints may be reconstructed and used as input to the object recognition.

Optionally, the template points are labelled by contiguous indexing the template points within the coordinate system. For the cost function, it may not be needed to have a sematic labelling, but rather a simple contiguous indexing may suffice to be able to determine whether the labelling of the nodes matches the labelling of the template points.

Optionally, the system further comprises a sensor interface for accessing sensor data acquired by a sensor, wherein the processor subsystem is configured to generate to the input points by extracting points of interest from the sensor data.

Optionally, the system further comprises an actuator interface for providing control data to an actuator, wherein the processor subsystem is configured to generate to the control data to control the actuator based on the object recognition data.

Optionally, a vehicle or robot is provided comprising the system. For example, the vehicle or robot may use the object recognition to recognize objects in its environment.

It will be appreciated by those skilled in the art that two or more of the above-mentioned embodiments, implementations, and/or optional aspects of the invention may be combined in any way deemed useful as long as the resulting combination is within the scope of the invention defined by the appended claims.

Modifications and variations of any system, any computer-implemented method or any computer-readable medium, which correspond to the described modifications and variations of another one of said entities, can be carried out by a person skilled in the art on the basis of the present description within the scope of the invention as defined by the appended claims.

<FIG> shows a system <NUM> for object recognition. The system <NUM> comprises an input interface for accessing template data as described elsewhere and for accessing input data for the object recognition. For example, as also illustrated in <FIG>, the input interface may be constituted by a data storage interface <NUM> which may access the template data <NUM> and the input data <NUM> from a data storage <NUM>. For example, the data storage interface <NUM> may be a memory interface or a persistent storage interface, e.g., a hard disk or an SSD interface, but also a personal, local or wide area network interface such as a Bluetooth, Zigbee or Wi-Fi interface or an ethernet or fiberoptic interface. The data storage <NUM> may be an internal data storage of the system <NUM>, such as a hard drive or SSD, but also an external data storage, e.g., a network-accessible data storage. In some embodiments, the template data <NUM> and the input data <NUM> may each be accessed from a different data storage, e.g., via a different subsystem of data storage interface <NUM>. Each subsystem may be of a type as described above for the data storage interface <NUM>.

The template data <NUM> comprises template points defined as coordinates in a coordinate system and which represent a geometric template of an object. The template points are labelled in the template data to distinguish respective parts of the object. The input data <NUM> comprises input points defined as coordinates in the coordinate system.

The system <NUM> further comprises a processor subsystem <NUM> which is configured to, during operation of the system <NUM>, construct an undirected weighted graph having nodes representing the input points and edges in between the nodes and to perform object recognition by finding one or more occurrences or partial occurrences of the object in the input data on the basis of i) assigning edge labels to the edges to define cuts in the graph to obtain a decomposition into one or more clusters representing objects, and ii) assigning node labels from a set of labels to the nodes to identify a respective node as representing a respective part of a respective object. More specifically, said edge and node labelling which is performed by the processor subsystem <NUM> comprises j) providing a cost function expressing a scale-invariant similarity between a respective triangle in the nodes and a respective triangle in the template points, wherein the scale-invariant similarity only contributes to the cost function if the labelling of the nodes matches the labelling of the template points and the nodes are part of a same cluster, jj) applying a first local search algorithm to an initial graph having each node unlabeled and each edge labelled to define a cut, wherein the first local search algorithm is configured to search for an initial local minimum in the cost function by iteratively connecting nodes by edge labelling to form clusters in the graph and by iteratively labelling nodes, thereby obtaining obtain an initial edge and node labelling, and jjj) applying a second local search algorithm to the initial edge and node labelling, wherein the second local search algorithm is configured to search for an improvement in initial local minimum of the cost function by iteratively moving nodes between clusters by edge re-labelling and by re-labelling nodes. As a result, the processor subsystem <NUM> obtains a graph with labels assigned to the nodes and edges.

The system <NUM> may comprises an output interface for outputting object recognition data which represents said assigned edge labels and said assigned node labels. For example, as also illustrated in <FIG>, the output interface may be constituted by the data storage interface <NUM>, with said interface being in these embodiments an input/output ('IO') interface, via which the object recognition data <NUM> may be stored in the data storage <NUM>. Alternatively, the output interface may be separate from the data storage interface <NUM>, but may in general be of a type as described above for the data storage interface <NUM>.

<FIG> further shows various optional components of the system <NUM>. For example, in some embodiments, the system <NUM> may comprise a sensor interface <NUM> for accessing sensor data <NUM> acquired by a sensor <NUM> in an environment <NUM>. In such embodiments, the processor subsystem <NUM> may be configured to generate to the input points by extracting points of interest from the sensor data. Accordingly, in these embodiments, the sensor interface <NUM> may represent the input interface as described above. However, in some embodiments, the system <NUM> may also have a data storage interface <NUM> to store the acquired sensor data <NUM> and/or the input data <NUM> which is derived by the processor subsystem <NUM> from the sensor data in the data storage <NUM>. In general, the sensor data interface <NUM> may have any suitable form, including but not limited to a low-level communication interface, e.g., based on I2C or SPI data communication, or a data storage interface of a type as described above for the data storage interface <NUM>.

In some embodiments, the system <NUM> may comprise an actuator interface <NUM> for providing control data <NUM> to an actuator <NUM> in the environment <NUM>. Such control data <NUM> may be generated by the processor subsystem <NUM> to control the actuator <NUM> based on the object recognition data. For example, the actuator may be an electric, hydraulic, pneumatic, thermal, magnetic and/or mechanical actuator. Specific yet non-limiting examples include electrical motors, electroactive polymers, hydraulic cylinders, piezoelectric actuators, pneumatic actuators, servomechanisms, solenoids, stepper motors, etc. Such type of control is described with reference to <FIG> for an autonomous vehicle.

In other embodiments (not shown in <FIG>), the system <NUM> may comprise an output interface to a rendering device, such as a display, a light source, a loudspeaker, a vibration motor, etc., which may be used to generate a sensory perceptible output signal which may be generated based on the object recognition data, for example to identify a recognized object to a user, or in general to provide any other type of derived sensory perceptible output signal, e.g., for use in guidance, navigation or other type of control.

In general, the system <NUM> may be embodied as, or in, a single device or apparatus, such as a workstation or a server. The server may be an embedded server. The device or apparatus may comprise one or more microprocessors which execute appropriate software. For example, the processor subsystem may be embodied by a single Central Processing Unit (CPU), but also by a combination or system of such CPUs and/or other types of processing units. The software may have been downloaded and/or stored in a corresponding memory, e.g., a volatile memory such as RAM or a non-volatile memory such as Flash. Alternatively, the processor subsystem of the system may be implemented in the device or apparatus in the form of programmable logic, e.g., as a Field-Programmable Gate Array (FPGA). In general, each functional unit of the system <NUM> may be implemented in the form of a circuit. The system <NUM> may also be implemented in a distributed manner, e.g., involving different devices or apparatuses, such as distributed local or cloud-based servers. In some embodiments, the system <NUM> may be part of vehicle, robot or similar physical entity, and/or may be represent a control system configured to control the physical entity.

<FIG> shows an example of the above, in that the system <NUM> is shown to be a control system of an autonomous vehicle <NUM> operating in an environment <NUM>. The autonomous vehicle <NUM> may incorporate the system <NUM> to control the steering and the braking of the autonomous vehicle based on sensor data obtained from a video camera <NUM> integrated into the vehicle <NUM>. For example, the system <NUM> may control an electric motor <NUM> to perform (regenerative) braking in case the autonomous vehicle <NUM> is expected to collide with an obstacle. The obstacle may be recognized by the system <NUM> in the sensor data by extracting keypoints from the sensor data and by applying object recognition to the extracted keypoints, for example in a manner as described elsewhere in this specification.

The following example describes the geometric object detection in more detail. However, the actual implementation of the geometric object detection may be carried out in various other ways, e.g., on the basis of analogous mathematical concepts.

In general, object detection using a graph-based representation of input points may be considered as a weighted correlation clustering problem with respect to the graph, which is known per se in computer science. The following first considers the formulation of this problem, before considering measure to address this problem.

A higher-order weighted correlation clustering problem with node labels may be formulated rigorously in the form of a binary multi-linear program. Feasible solutions to this problem may define both a clustering and a node labeling of a given graph. An instance of the multi-linear problem may be defined with respect to the following data:.

A clustering may be identified in the graph with the set of those edges that straddle distinct clusters. These sets of edges are typically called the 'multicuts' of the graph, and have the property that no cycle in the graph intersects with a multicut in precisely one edge. Specifically, a set X of binary labelings x: E → {<NUM>,<NUM>} of edges with the set x-<NUM>(<NUM>) of edges labeled '<NUM>' may be considered to define a multicut and thus a clustering of the graph. For any edge {v, w} E E, xvw = <NUM> may then indicate that the incident nodes v and w are in distinct clusters, or xvw = <NUM> may indicate that v and w are in the same cluster. Formally: <MAT> <MAT>.

One may further consider functions y: V × L → {<NUM>,<NUM>} that indicate, for any node v ∈ V and any label l ∈ L, by yvl = <NUM> that the node v is assigned the label l, or by yvl = <NUM> that the node v is not assigned the label l. In order to ensure that each node is assigned precisely one label, these functions may be constrained to the set: <MAT>.

The instance of the higher order weighted correlation clustering problem with node labels with respect to G, L, V and c may be defined as the binary multi-linear program: <MAT>.

Note that the first product assumes the value '<NUM>' if all nodes in the set U are assigned to the same cluster, and assumes the value '<NUM>' otherwise. Note also that the second product assumes the value '<NUM>' if the nodes in the set U are labeled according to λU, and assumes the value '<NUM>' otherwise. Thus, the cost cλU may be payed if and only if the nodes in the set U are labeled according to λU and assigned to the same cluster.

Local search algorithms may be used to obtain feasible solutions of Eq. (<NUM>). In particular, a combination of Greedy Additive Edge Contraction and Kernighan-Lin algorithms may be used, which are generalized to higher-order cost functions and labels as follows.

The problem which is addressed is the problem of object recognition. As input, a geometric template is obtained, which may be represented by t: <MAT>, where L = {<NUM>,. , ℓ} is a finite index set. The label set <IMG> may be readily defined by the contiguous indexing of the template points. The goal is to find all occurrences of the template in the input point set together with a labeling of the points. It is assumed that the template can undergo a similarity transformation, e.g., translation, rotation, reflection and scaling.

The following defines a model that is robust for similarity transformations. For that purpose, ternary costs are defined over triplets of points, corresponding to triangles, such that for similar triangles the same cost will be assigned, i.e., the cost is scale-invariant. The costs also depend on labels, which identify a corresponding triangle from the template.

Let Π: <MAT> be a function which projects the coordinates of a triangle to the 2D simplex S: <MAT>.

The Mahalanobis-distance DM: <MAT> may be used on the simplex <IMG>, where µ ∈ <IMG> and <MAT> are the mean vector and the covariance matrix, respectively. For all <MAT> one may define <MAT> where µλU = Π(tλU(u), tλU(v), tλU(w)) and ΣλU is the covariance matrix of the corresponding triangle from the template. The ternary costs may then be defined as: <MAT>.

It is noted that the model can cope with multiple templates by setting all inter-template costs to ∞ such that different labels are assigned to points in different groups.

The following first introduces and then comments on the pseudo-code of respectively <NUM>) the Kernighan-Lin Algorithm, <NUM>) an update function used in the Kernighan-Lin Algorithm, and <NUM>) the Greedy Additive Edge Contraction (GAEC) algorithm.

The Kernighan-Lin algorithm was originally proposed for the set partitioning problem, while later being adapted for the multicut problem with node labels and to higher order cost function. The variant of the Kernighan-Lin algorithm described in this specification is specifically adapted to the higher-order node labelling multicut problem.

The KL algorithm receives an undirected graph G = (V, E), label set L, a family V of connected subsets of nodes, costs c and an initial (feasible) solution (x<NUM>, y<NUM>) and iterates over all possible pairs (A, B) of adjacent (connected) components (i.e., there exists e = {v, w} ∈ E such that v E A and w ∈ B) with respect to the current clustering xt-<NUM> (line <NUM>). The algorithm solves a sequence of <NUM>-cut problems between pairs of components (line <NUM>). For each component with respect to the current clustering xt (line <NUM>), new components can be introduced into the decomposition by solving a <NUM>-cut problem against the empty set (line <NUM>). The procedure may continue either up to a maximum number of iterations or until there is no more difference in the subsequent solutions (line <NUM>). Both lines <NUM> and <NUM> rely on the function update that operates on a pair of components only and which is described below.

The above function seeks a lower objective value by updating the <NUM>-way clustering only for two components A, B ⊆ V, A ∩ B = <NUM≯ (B can be the empty set). The algorithm computes the cumulative total gain Si for all steps <NUM> ≤ i ≤ |A ∪ B|. It also maintains a queue M of moves in order to keep the update steps. In each iteration (lines <NUM>-<NUM>), it picks a vertex whose move (with possible relabeling) to the other set will result in the largest decrease of objective value (line <NUM>). For efficiency these values may be precomputed (line <NUM>-<NUM>) with respect to the current solution (x,y) in line with the Kernighan-Lin algorithm. For any set U E V and any labeling λU, the notation dλU(u, l) may define the cost with respect to the current (feasible) solution (x,y), where the label of node u E U is fixed to l, namely, <MAT> where [·] is the Iverson-bracket, that is: <MAT>.

The sum of the costs for any A ⊆ V, any node v ∈ V and a label l ∈ L may be defined as <MAT> where Av = {A' ∪ {v}|A' ⊆ A}. For all v ∈ A ∪ B and l ∈ L the precomputed values may be calculated as: <MAT>.

In the main loop (lines <NUM>-<NUM>) the algorithm picks a vertex v* to move potentially and its new (possibly the same) label (line <NUM>), computes the actual cumulative gain (line <NUM>) and records this move (line <NUM>) and then updates precomputed values of Dvl of all other vertices that share a cost with v* (lines <NUM>-<NUM>). There are different cases captured by lines <NUM>-<NUM>; without loss of generality, it is assumed that v* is moved from A to B. Note that only a single node is considered to be moved in each iteration. Note that this way sub-optimal (i.e., non-decreasing) individual moves may be allowed in the hope to leave a local minimum and arrive at a better one later. We search for the step i* resulting in the maximum cumulative gain (line <NUM>). A special operation computes the decrease of the objective of joining two components A and B (line <NUM>) keeping their node labels y unchanged as follows: <MAT> where for any A ⊆ V <MAT>.

This is relevant as individual local moves may not result in joining A and B even if it is beneficial. The optimal operation is chosen (line <NUM>): either join the two components A and B (lines <NUM>-<NUM>) or keep some moves up to i* (lines <NUM>-<NUM>). Both the clustering (lines <NUM>-<NUM>) and the labeling (lines <NUM>-<NUM>) are then updated.

The GAEC algorithm starts with an initial decomposition of all vertices v ∈ V into individual components (line <NUM>). Initially all nodes are unlabeled (line <NUM>). The algorithm greedily contracts a pair or a triplet of vertices, while fixing their node labels. The remaining costs, which the contracted vertices were part of, are added up. A min-priority queue Q is used to keep track of the most prospective subset of vertices to contract. We initialize Q by finding the best cost (including node labels) for each pair and triplet of vertices (lines <NUM>-<NUM>). The main loop goes until the queue is empty or does not contain any negative-cost elements (line <NUM>). In each iteration the best subset U and its labeling λU (line <NUM>) may be picked. Without loss of generality, we assume that a node u of U remains in the graph (lines <NUM>-<NUM>), while other vertices in U\{u} are contracted with it (lines <NUM>-<NUM>). Lines <NUM>-<NUM> update all costs, while line <NUM> handles collapse of cost. The new prospective improvements in the objective value are pushed into the queue Q. In the end, the vertices that have not been assigned a node label assume the cheapest one (lines <NUM>-<NUM>), based on unary costs, which may be defined as cλu where u stands for a single node, and remain in individual clusters.

<FIG> shows an input point cloud <NUM> representing stars. In particular, the input points <NUM> represent four 'Big Dippers' and four Cassiopeia star constellations and <NUM> outliers. In general, such input points <NUM> may be defined as 2D coordinates in a Euclidian coordinate system, and may be obtained by the system and method directly as 2D coordinates or by detecting stars in an image of the night sky.

<FIG> illustrates object recognition being applied to the input points <NUM> to recognize constellation of stars based on geometric templates defining the constellations. In the example of <FIG>, various star constellations <NUM> are recognized as clusters of points with the points of each cluster being mutually connected by edges in the corresponding graph. Such edge connections are shown in <FIG> by the thin lines, while the outline of the constellations according to the obtained labelling are shown as thick lines.

In another embodiment, keypoints may be detected by one or more keypoint detectors in image data acquired by an onboard camera of a vehicle. For example, corners or corner-like points may be detected as keypoints. Such keypoints may be converted to input data for the geometric object recognition by back-projecting the extracted keypoints into a 3D coordinate system based on depth information for the image data, which may be obtained from for example a stereoscopic camera system or an additional depth sensor or which may be estimated. Geometric object detection may then be applied to the points based on a geometric template of a car, resulting in inferred keypoints. Such car recognition may involve obtaining CAD models of various car types. The input points in 3D Euclidian space may be obtained by back-projecting extracted keypoints from a 2D digital image into a 3D coordinate system by making use of the camera matrix and estimated or measured depth information. The object recognition may then effectively search for the CAD models in the input point cloud while using a scale-invariant similarity measure under the assumption that similarity transformations may have occurred. A possible application area is in driver assistance systems which operate when a vehicle is travelling on a highway. Here, the direction of cars has a relatively low variance, but the scaling of the cars varies substantially during operation due to the different distances of the cars to the camera.

The above-described object recognition in the geometric domain may also be applied to various other application areas, for example, to articulated object detection. Here, a graph G = (V, E) with an arbitrary structure E may be used to model compound objects composed of rigid parts that can move around junction points. This movement may be modeled as a piecewise rigid transformation. An example of an articulated object is a moving robot arm. The geometry of the robot arm is known, and therefore the geometric template is readily available. By making use of markers on the junctions, input points may be obtained in the form of the position of the markers. The exact pose of the robot arm may be determined through the geometric object recognition even for partially occluded parts. This application may be incorporated into safety systems, where dangerous situations need to be recognized. For marker extraction, one may use IR or UV cameras in order to increase the robustness of the system depending on the given conditions. A similar application area is the inspection of parts (e.g., piston, valves) which may use the geometric object recognition.

Another example of an application area is traffic sign recognition. Here, planar geometric data or image data may be obtained which defines various traffic signs. In order to model the traffic signs from such type of data, one or several types of points of interest, such as corners, may be extracted from the data. The input point cloud may be obtained from sensor data, such as the image data acquired by an onboard camera of a vehicle, by extracting the same type of points of interest from the sensor data.

Yet another example of an application area is character recognition. Here, planar geometric data or image data may be obtained which defines a finite set of characters and thereby a set of 2D objects. In order to model the characters from such type of data, one or several types of points of interest, such as corners, may be extracted from the data. The input point cloud may be obtained from sensor data, such as the image data of a document page acquired by a scanner or digital camera, by extracting the same type of points of interest from the sensor data. In case of a digital camera, if the camera's direction is not perpendicular to the plane of the document page, the transformation is a perspective projection, which may be accounted for by the scale-invariant similarity measure.

Yet another example of an application area is detecting and identifying small objects with a known geometry. This may for example be relevant for a robot which may be configured to find and grab the objects. Such a robot may also be configured to count objects. By being able to recognize the objects, the counting of the objects is trivial.

<FIG> shows a computer-implemented method <NUM> for object recognition, being a high-level representation of some embodiments described in this specification. The method <NUM> comprises in a step titled "ACCESSING TEMPLATE DATA", accessing <NUM> template data representing a geometric template, in a step titled "ACCESSING INPUT DATA", accessing <NUM> input data for the object recognition, in a step titled "PROVIDING COST FUNCTION", providing <NUM> a cost function, in a step titled "GREEDY ADDITIVE EDGE CONTRACTION (GAEC)", performing <NUM> a Greedy Additive Edge Contraction (GAEC), in a step titled "KERNIGHAN-LIN (KL) ALGORITHM", executing <NUM> a Kernighan-Lin (KL) algorithm, and in a step titled "OUTPUT CLUSTERING AND NODE LABELS", outputting <NUM> object recognition data representing a clustering and labelling of nodes.

This method <NUM> and any other method, algorithm or pseudo-code described in this specification may be implemented on a computer as a computer implemented method, as dedicated hardware, or as a combination of both. As also illustrated in <FIG>, instructions for the computer, e.g., executable code, may be stored on a computer readable medium <NUM>, e.g., in the form of a series <NUM> of machine-readable physical marks and/or as a series of elements having different electrical, e.g., magnetic, or optical properties or values. The executable code may be stored in a transitory or non-transitory manner. Examples of computer readable mediums include memory devices, optical storage devices, integrated circuits, servers, online software, etc. <FIG> shows an optical disc <NUM>.

Examples, embodiments or optional features, whether indicated as non-limiting or not, are not to be understood as limiting the invention as claimed.

Claim 1:
A computer-implemented method (<NUM>) for object recognition, comprising:
- accessing (<NUM>) template data comprising template points defined as coordinates in a coordinate system, wherein the template points represent a geometric template of an object, wherein the template points are labelled to distinguish respective parts of the object;
- accessing (<NUM>) input data for the object recognition, the input data comprising input points (<NUM>) defined as coordinates in the coordinate system;
- constructing an undirected weighted graph having nodes representing the input points and edges in between the nodes;
- performing object recognition by finding one or more occurrences or partial occurrences of the object (<NUM>) in the input data on the basis of:
- assigning edge labels to the edges to define cuts in the graph to obtain a decomposition into one or more clusters representing objects, and
- assigning node labels from a set of labels to the nodes to identify a respective node as representing a respective part of a respective object,
wherein said edge and node labelling comprises:
- providing (<NUM>) a cost function expressing a scale-invariant similarity between a respective triangle in the nodes and a respective triangle in the template points, wherein the scale-invariant similarity contributes to the cost function if the labelling of the nodes matches the labelling of the template points and the nodes are part of a same cluster;
- applying (<NUM>) a first local search algorithm to an initial graph having each node unlabeled and each edge labelled to define a cut, wherein the first local search algorithm is configured to search for an initial local minimum in the cost function by iteratively connecting nodes by edge labelling to form clusters in the graph and by iteratively labelling nodes, thereby obtaining obtain an initial edge and node labelling;
- applying (<NUM>) a second local search algorithm to the initial edge and node labelling, wherein the second local search algorithm is configured to search for an improvement in the initial local minimum of the cost function by iteratively moving nodes between clusters by edge re-labelling and by re-labelling nodes;
- generating (<NUM>) object recognition data as output, the object recognition data representing said assigned edge labels and said assigned node labels.