Learning Propagation for Arbitrarily-Structured Data

Sifei Liu, Xueting Li, Varun Jampani, Shalini De Mello, Jan Kautz

Abstract

Standard Convolutional Neural Networks (CNNs) are optimized for grid-like data, such as images. However, many real-world datasets, including LiDAR point clouds and superpixels, are "arbitrarily structured." This paper introduces the Spatial Generalized Propagation Network (SGPN), a novel deep learning module designed to model global pairwise relationships in irregular data by representing it as a collection of Directed Acyclic Graphs (DAGs). By learning a linear diffusion process, SGPN significantly improves semantic segmentation performance across various data formats while remaining computationally efficient.

The Challenge of Irregular Data

While CNNs excel at processing pixels arranged in neat grids, they struggle with unstructured data like scattered points in a LiDAR scan. Researchers typically address this by either voxelizing the data—which wastes memory and loses detail—or using Non-Local blocks to model every point's relationship to every other point. The latter is computationally expensive and often ignores the underlying geometry of the object.

A key issue in modeling global affinities is "bleeding" information across unrelated boundaries. For instance, in a curved object, two points might be physically close in Euclidean space but belong to different parts of the structure. SGPN addresses this by ensuring propagation follows the actual "skeleton" of the data.

Figure 1: Comparison of direct affinity vs. path-aware propagation. (a) shows points on a curve. (c) shows direct affinity where $v_1$ might incorrectly influence $u$. (d) shows path-aware propagation where influence follows the structure.

Spatial Generalized Propagation Network (SGPN)

The SGPN module generalizes Spatial Propagation Networks (SPNs) to any arbitrary graph. The core innovation lies in how information is propagated:

  1. Graph Representation: Data is represented as a set of Directed Acyclic Graphs (DAGs). For point clouds, these graphs can follow principal axes in multiple directions.
  2. Learnable Affinities: SGPN learns the "affinity" (similarity) between connected nodes using a differentiable kernel. This allows the network to dynamically decide how much information should flow between points based on features like color or geometry.
  3. Linear Diffusion: Information is propagated across the graph using a process equivalent to linear diffusion, effectively "smoothing" features across the entire object through chains of connections.
  4. Parallel Execution: To ensure efficiency, graph nodes are re-ordered into groups that can be processed simultaneously, preventing the module from becoming a training bottleneck.
Figure 6: The overall pipeline for point cloud segmentation using SGPN. Features from multi-view images are processed by CNNs, aggregated into nodes, and then refined via the SGP module before final segmentation.

Key Insights: Path-Awareness and Geometry

The authors emphasize that path-awareness is crucial. By propagating along the graph's structure rather than relying on Euclidean distance, SGPN avoids mixing features from distinct structural components. Furthermore, incorporating geometric hints like surface normals and XYZ coordinates into the affinity learning process helps the network understand that points on the same smooth surface should likely share semantic labels.

Experimental Results

SGPN was evaluated on several benchmarks, demonstrating significant improvements:

  • Image Segmentation (Cityscapes): Integrating SGPN into a Dilated Residual Network (DRN) backbone increased the mean Intersection over Union (mIoU) from 69.5% to 75.0%, outperforming memory-intensive Non-Local modules.
  • Point Cloud Segmentation (RueMonge2014): SGPN achieved an mIoU of 73.66%, a substantial jump over the previous state-of-the-art, SplatNet (69.8%).
  • Versatility: The module also proved effective for tasks like color restoration and scribble-based colorization, where a single user stroke can propagate color accurately across an entire object by following learned structural paths.

Conclusion

SGPN provides a flexible and efficient way to model global relationships in non-grid data. By generalizing propagation to arbitrary graphs and emphasizing path-aware affinities, it bridges the gap between grid-based CNNs and the unstructured reality of 3D data. Future work may explore end-to-end learning of the graph topology itself, further automating the discovery of optimal information flow paths.

Summary updated

Abstract

Processing an input signal that contains arbitrary structures, e.g., superpixels and point clouds, remains a big challenge in computer vision. Linear diffusion, an effective model for image processing, has been recently integrated with deep learning algorithms. In this paper, we propose to learn pairwise relations among data points in a global fashion to improve semantic segmentation with arbitrarily-structured data, through spatial generalized propagation networks (SGPN). The network propagates information on a group of graphs, which represent the arbitrarily-structured data, through a learned, linear diffusion process. The module is flexible to be embedded and jointly trained with many types of networks, e.g., CNNs. We experiment with semantic segmentation networks, where we use our propagation module to jointly train on different data -- images, superpixels, and point clouds. We show that SGPN consistently improves the performance of both pixel and point cloud segmentation, compared to networks that do not contain this module. Our method suggests an effective way to model the global pairwise relations for arbitrarily-structured data.
BibTeX
@misc{liu2019learning,
  author = {Sifei Liu and Xueting Li and Varun Jampani and Shalini De Mello and Jan Kautz},
  title = {{Learning Propagation for Arbitrarily-Structured Data}},
  year = {2019},
  eprint = {1909.11237},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1909.11237},
}
Figure