Regularized Graph Matching for Correspondence Identification under Uncertainty in Collaborative Perception

In this article, we aim to explain correspondence identification in collaborative perception for multi-robot system. We will try to skip all the complex mathematical equations (maybe a little part), and focus on the motivation, challenges and intuitions of the approach published in Robotics: Science and System 2020.

What is the problem?

Multi-robot systems have been attracting a significant attention over the past decades due to their reliability, parallelism, and scalability to address large-scale problems. As one of the essential abilities of multi-robot systems, collaborative perception enables shared awareness and understanding of the surrounding environment among the robots, as shown in Figure 1.

Figure 1: Collaborative perception in the connected autonomous driving scenario.

In order to perform collaborative perception, correspondence identification is a core task that must be addressed, with the goal of identifying the same objects (thus deciding the correspondences) observed by two robots in their own fields of view. For example, as shown in Figure 2, if two connected vehicles want to share information of other vehicles and road conditions, they first need to identify street objects’ correspondence in order to correctly refer to the same objects.

Figure 2: Correspondence identification in collaborative perception.

What are the challenges and solutions?

Chllenge-1: Multiple objects observed by these robots may look similar or identical, thus, the visual ambiguousness may lead to incorrect correspondences, as shown in Figure 3.

Figure-3 Visual ambiguousness in correspondence identification (challenge-1).

Solution: In order to address the ambiguousness in the visual apperance of objects during correspondence identification, we formulate correspondence identification as a graph matching problem, as shown in Figure 4. We aim to obtain the corresponding matrix X, which encodes the correspondence of objects. In addition, both graphs obtained from two observations encodes the visual and spatial information of objects, which can be used to facilite correspondence identification with visual ambiguousness.

Figure 4: Formulate correspondence identification as a graph matching problem.

• The attribute similarity between a pair of objects is denoted as matrix A
• The distance similarity between two pairs of objects is denoted as matrix D
• The angular similarity between two triangles constructed by three nodes in each graph is denoted as tensor T
• The correspondences of objects in two observations are encoded in the matrix X

Figure 4: Address visual ambiguousness by using visual and spatial information of objects encoded in graph representations.

As shown in Figure 4, by integrating the visual and spatial similarity of object in graph matching, we can obtain the correspondences of objects with visual ambiguousness. Formally, we try to search all the potential correspondences X, to find the optimal solution with the largest overall score on attribute, distance and angular similarities. And also the correspondences follow the one-to-one constraint, which means that one object in one observation can at most has one corresponding object in the other observation.

Up to now, it seems that correspondence identification has done. However, we cannot ensure the visual and spatial information we used are accurate.

Challenge-2: Mainly due to sensor resolution limit and noise, measurement scenario variations, and perception model bias, uncertainty always exists in robot perception, which cause the uncertain visual (attribute) and spatial (position) information of objects. As shown in Figure 5, the larger the value, the larger the uncertainty exsiting in the visual or spatial information of objects.

Figure 5: The attribute uncertainty (visual uncertainty) and position uncertainty (spatial uncertainty) exist in the robot perception. The larger the value, the larger the uncertainty (challenge-2).

Solution: In order to address uncertainty in the attributes and positions of the objects, we propose a regularization term to penalize the correspondence of objects with high attribute and position uncertainties and promote the correspondence of objects with low uncertainties.

Figure 6: Address perception uncertainty in correspondence identification

The quantified attribute and position uncertainties of objects are shown in Figure 6. We represent the attribute and position uncertainties between two observations as matrix V and U separately. And then, we introduce a new regularization term over the correspondence matrix X to control the sum of attribute and position uncertainties. Intuitively, if two objects have larger uncertainties, it may still be inappropriate to match them, even though they have a large similarity score. Moreover, given matrix V and U, we further generate three weight matrix Wa, Wd, Wt to indicate the importance of the elements in three similarity matrices.

Have we finished yet? The anwser is NO. In real-world applications, not all the objects have correspondences.

Challenge-3: We refer the objects observed by one robot may not be observed by other robots (e.g., due to limited field of view or occlusion) as non-covisible objects, as shown in Figure 7. Non-covisible objects usually significantly increase the number of incorrect correspondences, because the correspondences of non-covisible objects may not exist.

Figure 7: Illustration of non-covisible objects (challenge-3)

Solution: In order to address non-covisible objects, we design another new regularization term over the number of identified correspondence to penalizet the correspondence constructed by the non-covisible objects.

Figure 8: Address non-covisible objects

One correspondence is added to X, only if the increase of the overall similarity caused by the newly added correspondence is larger than the penalty resulted from the regularization ||X||².

What is the results?

We evaluate our approach in the scenarios of connected autonomous driving (CAD) and multi-robot coordination in simulations (S-MRC) and using real robots (R-MRC).

Figure 9: Qualitative experimental results of our approach over CAD (first row), S-MRC (second row) and RMRC (third row), and comparisons with the ReId and MOS methods. The green/red dash lines denote correct/incorrect correspondences and yellow dashed lines denote missing correspondences.

Conclusion

Correspondence identification is a critical ability for a group of robots to consistently refer to the same objects within their own fields of view. Visual ambiguousness, perception uncertainties and non-covisible objects are three of the biggest challenges to enable this ability. We propose a novel regularized graph matching approach to explicitly address ambiguousness, uncertainty and non-covisibility. The experimental results have shown that our approach obtains the state of-the-art performance for correspondence identification with non-covisible objects under uncertainty.

If you want to know the details, please check out our paper “Regularized Graph Matching for Correspondence Identification under Uncertainty in Collaborative Perception” published in RSS 2020.

Reference

[1].: Chang, Hyung Jin, et al. “Learning kinematic structure correspondences using multi-order similarities.” PAMI, 2017.

[2]. Zhao, Yiru, et al. “Attribute-driven feature disentangling and temporal aggregation for video person re-identification.” CVPR, 2019.