A method to segment maps from different modalities using free space layout - MAORIS : MAp Of RIpples Segmentation

Malcolm Mielle, Martin Magnusson, Achim J. LilienthalICRA 2017 · DOI · OpenReview

TL;DR

This paper introduces MAORIS, a novel method for segmenting indoor maps into semantic regions like rooms and corridors, working effectively across different map types, including robot-generated maps and human-drawn sketches. It addresses a critical need for robots to understand spatial layouts and introduces a more robust evaluation metric, the Matthews Correlation Coefficient (MCC), to better assess segmentation quality.

What Problem Does This Paper Address?

Robots operating in indoor environments need to understand their surroundings in a semantically meaningful way, not just as raw sensor data. This means identifying distinct areas like rooms and corridors, which is crucial for tasks like navigation, human-robot interaction (e.g., "go to the kitchen"), and place recognition. While existing methods primarily focus on segmenting maps built by robots (which can be noisy and complex), they often struggle with other intuitive map representations like hand-drawn sketches. These sketches, while less metrically precise, can convey spatial relationships effectively for humans but are challenging for robots to interpret. The paper aims to bridge this gap by developing a unified segmentation method applicable to both modalities and by proposing a better way to evaluate segmentation performance.

Methods

MAORIS employs a multi-stage approach to segment maps:

  1. Free Space Image (FSI) Computation: The core idea is to represent the map not by obstacles, but by the free space around each point. This is achieved by calculating a distance image (distance to the nearest obstacle) and then creating a "Free Space Image" (FSI). In the FSI, each pixel's value represents the radius of the largest circle that can be centered at that pixel without hitting an obstacle. This effectively encodes information about the size of the navigable space.
  2. Ripple Merging: The FSI naturally leads to an over-segmented map with many small regions, termed "ripples." These are often thin variations in free space. The algorithm merges these ripples into larger, more meaningful regions based on the percentage of their contour shared with a neighbor.
  3. Neighboring Region Merging: Regions with similar free space values are then merged. This step uses a threshold-based approach, with a secondary condition that allows merging even if the direct difference is slightly above the threshold, provided there's a similarity to a neighbor of the other region. This helps consolidate areas that might be part of the same room but have slight variations in free space.
  4. Door Handling: For robot maps, the algorithm can optionally detect and use "door patterns" to prevent merging regions that are separated by doorways, even if their free space values are similar.
  5. Boundary Straightening (Robot Maps Only): For metrically accurate robot maps, boundaries between segmented regions are straightened to improve geometric consistency. This step is omitted for sketch maps where such precision is not expected.

A key innovation is the use of the FSI, which focuses on free space layout rather than just obstacle contours, making it more robust to different map types.

Datasets

The paper evaluates MAORIS on two datasets:

  1. Bormann et al. [2] Dataset: This is a standard benchmark dataset consisting of 20 uncluttered robot-built maps.
  2. MAORIS Sketch Dataset: A newly introduced dataset of 25 hand-drawn sketch maps. These sketches were generated from virtual environments and correspond to ground truth segmentations from the KTH dataset for SLAM. Crucially, this dataset includes two different ground truth segmentations for each sketch, provided by two non-expert users, reflecting the inherent subjectivity in map interpretation.

Key Insights and Ideas

  • Free Space as a Semantic Cue: The paper highlights that the layout of free space, rather than just the presence of walls, is a powerful indicator for semantic segmentation. The FSI effectively captures this by encoding navigable space size.
  • Ripples as a Segmentation Artifact: The concept of "ripples" as thin, artifactual regions in the FSI is a useful insight for understanding and refining initial segmentations.
  • MCC as a Superior Evaluation Metric: The authors convincingly argue that traditional precision/recall metrics can be biased, especially towards under- or over-segmentation. The Matthews Correlation Coefficient (MCC) is presented as a more balanced and robust metric for evaluating segmentation quality, particularly when dealing with imbalanced class sizes or varying region overlaps.
  • Unified Approach for Modalities: The ability of MAORIS to perform well on both precise robot maps and abstract sketch maps is a significant achievement, suggesting a more generalizable approach to map understanding.

Key Results

MAORIS consistently outperforms existing state-of-the-art methods on both datasets:

  • Bormann's Dataset (Robot Maps): MAORIS achieves a median MCC of 0.98, significantly outperforming Voronoi-based segmentation (0.65) and DuDe (0.70).
  • MAORIS Sketch Dataset: MAORIS achieves a median MCC of 0.56, again outperforming Voronoi (0.28) and DuDe (0.30).
  • The paper also demonstrates the stability of MAORIS's parameters, showing that it is largely insensitive to certain parameters (like m for margin) and that the chosen parameter values are well-justified.

Limitations and Future Work

  • Computational Speed: MAORIS is pixel-based, meaning its speed is dependent on image size. While this can be mitigated by downsampling, the authors suggest developing an incremental segmentation method for faster processing.
  • Clutter Handling: The current method is best suited for unfurnished environments. Future work will focus on automatically removing clutter from maps before segmentation.
  • Cross-Modal Matching: The authors plan to leverage the segmented regions from MAORIS to perform matching between maps from different modalities, a crucial step for robust robot localization and mapping.

Summary updated

Abstract

How to divide floor plans or navigation maps into semantic representations, such as rooms and corridors, is an important research question in fields such as human-robot interaction, place categorization, or semantic mapping. While most works focus on segmenting robot built maps, those are not the only types of map a robot, or its user, can use. We present a method for segmenting maps from different modalities, focusing on robot built maps and hand-drawn sketch maps, and show better results than state of the art for both types. Our method segments the map by doing a convolution between the distance image of the map and a circular kernel, and grouping pixels of the same value. Segmentation is done by detecting ripple-like patterns where pixel values varies quickly, and merging neighboring regions with similar values. We identify a flaw in the segmentation evaluation metric used in recent works and propose a metric based on Matthews correlation coefficient (MCC). We compare our results to ground-truth segmentations of maps from a publicly available dataset, on which we obtain a better MCC than the state of the art with 0.98 compared to 0.65 for a recent Voronoi-based segmentation method and 0.70 for the DuDe segmentation method. We also provide a dataset of sketches of an indoor environment, with two possible sets of ground truth segmentations, on which our method obtains an MCC of 0.56 against 0.28 for the Voronoi-based segmentation method and 0.30 for DuDe.
BibTeX
@inproceedings{mielle2017method,
  author = {Malcolm Mielle and Martin Magnusson and Achim J. Lilienthal},
  title = {{A method to segment maps from different modalities using free space layout - MAORIS : MAp Of RIpples Segmentation}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2017},
  doi = {10.1109/icra.2018.8461128},
}
Figure