💻 computer science

Spatial Model Checking of Images via Minimised Models and Branching Bisimilarity

This paper proposes and validates an efficient minimization method for spatial model checking of quasi-discrete closure models by encoding them as labeled transition systems to compute CoPa equivalence classes via branching bisimilarity, demonstrating significant performance improvements through the prototype toolchain VoxMinX.

Original authors: Vincenzo Ciancia, Jan Friso Groote, Diego Latella, Mieke Massink, Erik P. de Vink

Published 2026-07-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Vincenzo Ciancia, Jan Friso Groote, Diego Latella, Mieke Massink, Erik P. de Vink

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a massive, high-definition digital photo of a brain scan or a video game scene. This photo isn't just a picture; it's a giant grid made of millions of tiny dots called pixels. In the world of computer science, checking if a specific rule applies to every single one of those millions of dots is like trying to find a needle in a haystack, but the haystack is the size of a city and the needle is a tiny logical rule.

This paper introduces a clever shortcut to solve that problem. It's like taking a giant, messy map and folding it down into a tiny, simplified version that keeps all the important connections but gets rid of the clutter.

Here is the breakdown of their method, using everyday analogies:

1. The Problem: Too Many Dots to Count

Think of a digital image as a giant neighborhood. Every house (pixel) has a color (like red, green, or white) and is connected to its neighbors. The researchers want to ask questions like, "Can I walk from this blue house to a green house without stepping on a black wall?"

If the neighborhood has 16 million houses, checking this for every single house takes a long time. The computer has to visit every house, check its neighbors, and repeat. It's slow and inefficient.

2. The Solution: Grouping "Look-Alikes"

The authors realized that many houses in this neighborhood are essentially the same. For example, if you have a huge white field where every white house has the exact same neighbors (other white houses), the computer doesn't need to check them one by one. It can treat the whole group as a single "super-house."

They call this CoPa-bisimilarity. It's a fancy way of saying: "If two points can reach the same types of destinations through the same types of paths, they are twins."

3. The Magic Trick: Translating the Neighborhood into a Train System

To make this grouping happen automatically, the researchers invented a translation tool. They turned the image (the neighborhood) into a Labelled Transition System (LTS).

The Analogy: Imagine turning the neighborhood map into a train network.
- Each pixel becomes a train station.
- The colors of the pixels become the "tickets" or labels on the stations.
- The connections between pixels become train tracks.
- They added special "silent" tracks (called $\tau$ ) that represent moving between identical houses without changing the view.

Once the image is a train network, they used a very powerful, existing tool (from a software suite called mCRL2) that is an expert at simplifying train maps. This tool finds all the stations that are functionally identical and merges them into one.

4. The Result: A Tiny Map with Big Power

After the train network is simplified, it becomes a Minimal Model.

Before: A map with 16 million stations.
After: A map with maybe 7 stations (for a maze) or 35 stations (for a Pac-Man scene).

The researchers proved mathematically that this tiny map is a perfect "shrink-ray" version of the original. If a rule is true on the tiny map, it is true on the big map. If it's false on the tiny map, it's false on the big map.

5. The Toolchain: "VoxMinX"

They built a prototype tool called VoxMinX to do this automatically. Here is the workflow:

Input: You feed it a digital image (like a 4096x4096 pixel maze).
Translate: It turns the image into the train network (LTS).
Simplify: It uses the mCRL2 tool to crush the network down to its smallest possible size.
Check: It runs the logical check on this tiny, fast model.
Project: It takes the results and paints them back onto the original, giant image.

6. The Proof: Speeding Up the Process

They tested this on three types of images:

Mazes: Finding paths from a start point to an exit.
Monoscope: A test pattern with complex color gradients.
Pac-Man: Identifying ghosts, cherries, and pellets.

The Results:

For the largest images (64 million pixels), checking the full image took a few seconds.
Checking the minimized version took a fraction of a second.
The Speed-Up: They found that using the minimized model made the process 3 to 25 times faster, depending on the image size and complexity.

Why This Matters

The paper claims that this method allows computers to verify complex spatial rules on huge images much faster. It's like realizing you don't need to count every grain of sand on a beach to know if the beach is wet; you just need to check a few representative handfuls that represent the whole.

They specifically mention that this is useful for medical imaging (like analyzing brain scans to find tumors) and video game analysis, where images are huge and rules are complex. The tool doesn't just save time; it keeps the connection to the original image, so you can still see exactly which pixels in the original photo satisfied the rule.

Technical Summary: Spatial Model Checking of Images via Minimised Models and Branching Bisimilarity

Problem Statement
Spatial model checking involves the automatic verification of properties expressed in spatial logics (specifically the Spatial Logic for Closure Spaces, SLCS) on every point of a spatial model. While tools like VoxLogicA have successfully applied these methods to digital images (represented as quasi-discrete closure models, QdCMs), the sheer size of modern medical and digital images—often containing millions of pixels or voxels—poses significant challenges for time and space efficiency. Direct model checking on such large models can be computationally expensive. The paper addresses the need for effective model minimisation procedures that reduce the size of the model without losing the ability to verify spatial properties, thereby accelerating the verification process.

Methodology
The proposed methodology relies on a theoretical encoding of finite Closure Models (CMs) into Labelled Transition Systems (LTSs) to leverage existing, highly efficient minimisation algorithms for branching bisimilarity.

Theoretical Foundation (CoPa-Bisimilarity): The work builds upon "Compatible Paths" (CoPa) bisimilarity, a spatial bisimilarity relation for QdCMs. Unlike previous bisimilarities that rely strictly on one-step reachability (closure membership), CoPa-bisimilarity is based on path compatibility. Two paths are compatible if they can be decomposed into the same number of "zones" (sequences of points) such that points in corresponding zones are related by the bisimulation. This relation is logically characterised by Infinitary Compatible Reachability Logic (ICRL), which features forward ( $\vec{\zeta}$ ) and backward ( $\vec{\zeta}$ ) conditional reachability modalities.
Encoding to LTS: The core technical contribution is an encoding of a finite QdCM $M = (X, C, V)$ $M = (X, C, V)$ into an LTS.
- For general (non-symmetric) QdCMs, each point $x$ is mapped to two states in the LTS: a forward state $\vec{x}$ and a backward state $\vec{x}$ . Transitions include self-loops for atomic propositions, $\tau$ -transitions for points with identical valuations reachable within the closure, $ch$-transitions for points with different valuations, and specific $cv$ (converse) and $dr$ (direct) transitions linking forward and backward states.
- For symmetric QdCMs (typical of digital images with 8-adjacency), a more compact encoding is used where each point maps to a single state, with $\tau$ and $ch$ transitions representing the closure relations.
Correctness: The paper proves that CoPa-bisimilarity in the original QdCM coincides exactly with branching bisimilarity in the encoded LTS. Consequently, the minimal model with respect to CoPa-bisimilarity can be computed by minimising the encoded LTS using branching bisimilarity algorithms.
Toolchain (VoxMinX): A prototype toolchain, VoxMinX, was developed to validate this approach. It performs the following steps:
- Converts a digital image into a QdCM and then into an LTS.
- Minimises the LTS using the $mCRL2$ toolset's branching bisimilarity minimiser.
- Transforms the minimal LTS back into a minimal QdCM.
- Executes spatial model checking on the minimal model using GraphLogicA.
- Projects the results back onto the original image, preserving the relationship between equivalence classes and the original sets of pixels.

Key Contributions

Theoretical Encoding: The paper introduces a formal encoding of finite closure models into LTSs that preserves CoPa-bisimilarity via branching bisimilarity. This allows the application of efficient state-space reduction techniques from process algebra to spatial model checking.
Correctness Proofs: Detailed proofs are provided, including a novel induction based on the "depth" of states in an LTS, demonstrating that the encoding correctly reflects CoPa-bisimilarity.
Practical Implementation: The development of VoxMinX, a toolchain that integrates image processing, LTS encoding, minimisation, and result projection.
Experimental Validation: The approach is evaluated on three families of benchmark images (mazes, monoscope patterns, and Pac-Man scenes) at various resolutions, comparing performance against the state-of-the-art, non-minimised checker VoxLogicA.

Results
Experimental results indicate a significant speed-up in model checking times when using the minimised models, particularly for larger images:

Maze Images: Speed-ups ranged from approximately 3.3x for smaller images (128x128) to over 17x for large images (8192x8192). The minimal model size remained constant (7 states) regardless of the input resolution, as the spatial structure was identical.
Monoscope Images: For images with complex nested reachability properties, speed-ups reached over 25x for the largest resolution (4320p). The minimal model size varied with resolution due to the loss of fine details during downscaling.
Pac-Man Images: A speed-up of roughly 3x to 7x was observed. The minimal model consistently contained 35 states across all resolutions.
Overhead: The paper notes that while the minimisation and encoding steps introduce overhead (I/O and conversion times), the reduction in model checking time on the minimal model (using GraphLogicA) outweighs this cost for larger images. The authors acknowledge that VoxLogicA is highly optimised for images, whereas GraphLogicA is a general graph checker; thus, the reported speed-ups are conservative estimates.

Significance and Claims
The paper claims that the proposed method offers a "promising speed-up" for spatial model checking of realistic-sized images. The significance lies in demonstrating that spatial bisimilarity minimisation is a viable strategy for handling large-scale spatial data, such as medical images (e.g., MRI scans with millions of voxels).

The authors emphasize that the approach preserves the logical truth of the original model, allowing results to be visualized directly on the original image (e.g., highlighting pixels satisfying a property). While the current prototype serves as a feasibility study, the results suggest that further integration of the toolchain components could yield even greater efficiency. The paper positions this work as a step toward making spatial model checking more practical for real-world applications, particularly in medical imaging where large datasets are common. The authors modestly frame the work as a foundation for future research, noting that the minimisation technique could also serve as a form of lossless compression for spatial properties.