SoftMatch: Comparing Scanpaths Using Combinatorial Spatio-Temporal Sequences with Fractal Curves

Robert Ahadizad Newport, Carlo Russo, Sidong Liu, Abdulla Al Suman, Antonio Di IevaSensors 2022 · DOI · OpenReview

TL;DR

This paper introduces SoftMatch, a novel method for comparing eye-tracking scanpaths that moves beyond traditional string-editing approaches. By leveraging fractal curves (Hilbert curves) for dimensionality reduction and a combinatorial approach with discrete Fréchet distance, SoftMatch offers a more robust way to analyze gaze patterns, particularly in free-viewing scenarios, leading to better insights into perceptual processes.

What Problem Does This Paper Address?

Comparing eye-tracking scanpaths, which represent sequences of where a person looks, is crucial for understanding human cognition, perception, and expertise. Existing methods, largely borrowed from bioinformatics, rely on string-editing algorithms like Needleman-Wunsch. While effective for some tasks, these methods struggle with the inherent variability and non-linearity of human gaze, especially in free-viewing situations where there's no specific task guiding the eyes. Traditional methods often quantize gaze data into grids, losing crucial spatial information and locality. This paper aims to overcome these limitations by proposing a new method that better preserves spatial relationships and handles the combinatorial nature of scanpaths.

Methods

The core of SoftMatch lies in two key innovations:

  • Dimensionality Reduction with Hilbert Curves: Instead of using traditional grid-based quantization, SoftMatch converts 2D (x,y) gaze coordinates into 1D Hilbert distances. Hilbert curves are fractal space-filling curves that preserve locality, meaning points close in 2D space remain close in their 1D representation. This reduces the complexity of the data while retaining more spatial information than simple gridding.
  • Combinatorial Scanpath Comparison with Discrete Fréchet Distance: SoftMatch segments scanpaths into shorter, time-binned sequences (called "SOFT sequences"). It then uses the discrete Fréchet distance to compare these segments. The Fréchet distance is a measure of similarity between two curves that considers their temporal order and shape. By using a combinatorial approach, SoftMatch compares all possible pairs of segments, making it less sensitive to the exact timing of fixations and more robust to variations in viewing strategies.

The method also incorporates an outlier detection mechanism based on fractal dimension to identify and potentially exclude unusual scanpaths.

Datasets

The study used two types of datasets:

  • Artificial Scanpaths: Synthetic scanpaths were generated and perturbed with varying levels of noise (spatial offset and duration variations) to test the sensitivity of SoftMatch against ScanMatch and MultiMatch.
  • Real Scanpath Data: Eye-tracking data from 53 healthy participants viewing six different artworks (paintings) was used. Participants were medical professionals with no specific art training and were instructed to view the artworks freely.

Key Insights and Ideas

  • Beyond Linearity: The paper strongly argues that traditional string-editing methods, which assume a linear or collinear structure, are ill-suited for analyzing the complex, non-linear nature of human scanpaths, especially in free-viewing tasks.
  • Locality Preservation is Key: Using fractal curves like Hilbert curves is crucial for maintaining spatial relationships when reducing dimensionality, a significant improvement over grid-based methods that can artificially separate nearby points.
  • Combinatorial Power: A combinatorial approach, rather than a purely sequential one, is better equipped to handle the inherent variability in how individuals explore visual stimuli.
  • Free-Viewing vs. Task-Based: The study highlights that methods performing well in task-based experiments (where gaze is more constrained) may falter in free-viewing scenarios, suggesting the need for methods like SoftMatch that are more adaptable to naturalistic viewing.

Key Results

  • Strong Performance in Real-World Scenarios: SoftMatch demonstrated high statistical and substantive significance in comparing real scanpaths from participants viewing artworks. It achieved the highest number of statistically significant p-values (<0.05) and substantively significant Cohen's effect sizes (>0.20) compared to ScanMatch and MultiMatch.
  • Artificial Scanpath Limitations: In the simulated scanpath experiment with artificial noise, SoftMatch initially showed poorer performance than ScanMatch and MultiMatch, particularly in direction and position. This is attributed to the artificial noise not fully simulating the perceptual differences between individuals.
  • Visual Separability: Heatmaps generated by SoftMatch showed a high degree of visual separability between concordant and discordant matches, indicating its effectiveness in distinguishing between similar and dissimilar viewing patterns.

Limitations and Future Work

  • Artificial Scanpath Performance: The paper acknowledges SoftMatch's weaker performance in the simulated scanpath experiment, suggesting that the artificial noise generation might not fully capture the complexities of real-world perceptual differences.
  • Parameter Optimization: While the paper suggests using brain's rhythmic attention physiology as a starting point for parameter selection (τ and δ), it notes that future work could involve optimization analysis using machine learning to find optimal values.
  • Exploring Other Metrics: The authors suggest exploring alternative methods for measuring curve similarity, such as using Support Vector Machines (SVMs) on SOFT segments as multidimensional feature spaces.
  • Task-Based Scenarios: Future work could explore how SoftMatch performs in task-based scenarios, where strategic top-down aspects of attention are more prominent.
  • Bottom-Up vs. Top-Down: The study acknowledges that similarities might be driven by bottom-up saliency mechanisms, which were not explicitly explored, and suggests future work to investigate the correlation between fixation patterns and these mechanisms.

Summary updated

Abstract

Recent studies matching eye gaze patterns with those of others contain research that is heavily reliant on string editing methods borrowed from early work in bioinformatics. Previous studies have shown string editing methods to be susceptible to false negative results when matching mutated genes or unordered regions of interest in scanpaths. Even as new methods have emerged for matching amino acids using novel combinatorial techniques, scanpath matching is still limited by a traditional collinear approach. This approach reduces the ability to discriminate between free viewing scanpaths of two people looking at the same stimulus due to the heavy weight placed on linearity. To overcome this limitation, we here introduce a new method called SoftMatch to compare pairs of scanpaths. SoftMatch diverges from traditional scanpath matching in two different ways: firstly, by preserving locality using fractal curves to reduce dimensionality from 2D Cartesian (x,y) coordinates into 1D (h) Hilbert distances, and secondly by taking a combinatorial approach to fixation matching using discrete Fréchet distance measurements between segments of scanpath fixation sequences. These matching “sequences of fixations over time” are a loose acronym for SoftMatch. Results indicate high degrees of statistical and substantive significance when scoring matches between scanpaths made during free-form viewing of unfamiliar stimuli. Applications of this method can be used to better understand bottom up perceptual processes extending to scanpath outlier detection, expertise analysis, pathological screening, and salience prediction.
BibTeX
@article{newport2022softmatch,
  author = {Robert Ahadizad Newport and Carlo Russo and Sidong Liu and Abdulla Al Suman and Antonio Di Ieva},
  title = {{SoftMatch: Comparing Scanpaths Using Combinatorial Spatio-Temporal Sequences with Fractal Curves}},
  journal = {Sensors},
  year = {2022},
  doi = {10.3390/s22197438},
}
Figure