SIMD-based Exact Parallel Fuzzy Dilation Operator for Fast Computing of Fuzzy Spatial Relations

Régis Pierrard, Laurent Cabaret, Jean-Philippe Poli, Céline HudelotWpmvp@ppopp 2020 · DOI

TL;DR

This paper introduces a novel, exact, and parallel algorithm called "Reverse" for computing fuzzy spatial relations, significantly speeding up a computationally intensive process. By leveraging modern CPU architectures with SIMD extensions and multi-core processing (OpenMP), their optimized versions (PR128, PR256, PR512) achieve substantial performance gains over existing methods, making fuzzy spatial reasoning more practical for real-world applications.

What Problem Does This Paper Address?

Interpreting and understanding visual scenes often relies on identifying spatial relationships between objects (e.g., "object A is to the left of object B"). Fuzzy logic provides a powerful framework for representing these relationships, especially when dealing with vague or imprecise information. A key operation in fuzzy spatial reasoning is the fuzzy dilation, which is used to compute various spatial relations like directional proximity or distances. However, the standard fuzzy dilation operator is computationally expensive, leading to long processing times. This has historically forced researchers to use approximate methods, which may sacrifice generality or accuracy. The paper addresses this by developing an exact and efficient method for fuzzy dilation that can keep pace with the demands of modern computer vision tasks.

Methods

The core innovation is the Reverse algorithm. Unlike traditional "Forward" algorithms that iterate through all pixels, Reverse optimizes by only considering pixels that are part of the "active" reference object (i.e., pixels with a non-zero value in the input fuzzy set). This is achieved by reordering computations and directly processing the input image rather than the output fuzzy landscape. This significantly reduces the number of operations, especially when the reference object is sparse.

To further accelerate this, the authors introduce Parallel Reverse (PR), which leverages OpenMP for multi-core processing. Building on PR, they developed three SIMD-optimized versions:

  • PR128: Uses AVX instructions (128-bit wide).
  • PR256: Uses AVX2 instructions (256-bit wide).
  • PR512: Uses AVX512 instructions (512-bit wide).

These SIMD versions exploit vector processing capabilities to perform operations on multiple data elements simultaneously, leading to substantial speedups. The authors also compare their methods against existing algorithms like Bloch's and Wang's.

Datasets

The paper uses two types of datasets for evaluation:

  • Structured Artificial Dataset: A newly introduced benchmark of 282 images designed to systematically evaluate algorithm performance based on parameters like object shape, fuzziness, size, position, and image size. This includes crisp and fuzzy images with various shapes (rectangles, disks, ellipses) and sizes (256x256, 512x512, 1024x1024), with reference objects ranging from 1 to 65536 pixels.
  • Natural Image Dataset: A dataset of medical images (10 images of size 312x384 and 8 images of size 407x1515) representing segmented organs. This dataset is used to assess performance on real-world applications.

Key Insights and Ideas

  • The "Active Pixel" Optimization is Key: The Reverse algorithm's efficiency stems from realizing that only pixels belonging to the reference object contribute to the dilation. This simple observation, when implemented correctly, drastically reduces computation.
  • SIMD and Multi-core Synergy: The paper demonstrates that combining multi-threading (OpenMP) with SIMD instructions (AVX, AVX2, AVX512) is crucial for achieving state-of-the-art performance. The performance gains are not just additive; they synergize.
  • Exactness Matters: Unlike many previous attempts to speed up fuzzy dilation, the proposed Reverse algorithm is exact. This means it produces the same results as the theoretical fuzzy dilation, avoiding the trade-off between speed and accuracy that often plagues approximate methods.
  • Scalability with SIMD: The performance gains from SIMD extensions become more pronounced with larger data widths (AVX512 > AVX2 > AVX), especially when sufficient data is available to saturate the vector units.

Key Results

  • Significant Speedups: The PR512 algorithm, leveraging AVX512, is shown to be significantly faster than existing methods. For example, on the natural image dataset, PR512 is on average 10.6 times faster than Bloch for smaller images and 33.5 times faster for larger images.
  • Competitive with Approximate Methods: Despite being an exact algorithm, PR512 is competitive with or faster than the approximate Bloch algorithm, especially for larger images and objects.
  • Reverse is Faster than Forward: Even without SIMD, the Reverse algorithm offers substantial speedups over the naive Forward algorithm, making it viable for certain applications.
  • Object Size Impact: The execution time of Reverse and its SIMD variants increases with the size of the reference object, as expected. However, the performance gains from SIMD are substantial enough to overcome this.
  • Core Count Optimization: For smaller datasets, using fewer CPU cores can sometimes be more efficient than using all available cores, due to factors like memory bandwidth limitations and overhead.

Limitations and Future Work

  • Memory Bandwidth Bottleneck: The paper notes that while SIMD extensions offer significant computational advantages, memory bandwidth can become a bottleneck, especially with many threads and large datasets. This limits the scalability of using all available cores in all scenarios.
  • Future Work: The authors plan to extend their work to other morphological operators like erosion, opening, and closing, and to explore GPU-based acceleration for fuzzy dilation algorithms.

Summary updated

BibTeX
@inproceedings{pierrard2020simd,
  author = {Régis Pierrard and Laurent Cabaret and Jean-Philippe Poli and Céline Hudelot},
  title = {{SIMD-based Exact Parallel Fuzzy Dilation Operator for Fast Computing of Fuzzy Spatial Relations}},
  booktitle = {Wpmvp@ppopp},
  year = {2020},
  doi = {10.1145/3380479.3380482},
}
Figure