Abstract

In this work, we study the natural monotone analogues of various equivalent definitions of : a well studied class (Poizat 2008, Koiran & Perifel 2009, Malod 2011, Mahajan & Rao 2013) that is believed to be larger than . We observe that these monotone analogues are not equivalent unlike their non-monotone counterparts, and propose monotone ( ) to be defined as the monotone analogue of Poizat's definition. With this definition, turns out to be exponentially stronger than and also satisfies several desirable closure properties that the other analogues may not. Our initial goal was to understand the monotone complexity of transparent polynomials, a concept that was recently introduced by Hrubeš & Yehudayoff (2021). In that context, we show that transparent polynomials with large support are hard for the monotone analogues of all the known definitions of , except for the one due to Poizat.

Abstract

No Results Found

Abstract

Reconfiguring two shortest paths in a graph means modifying one shortest path to the other by changing one vertex at a time so that all the intermediate paths are also shortest paths. This problem has several natural applications, namely: (a) repaving road networks, (b) rerouting data packets in a synchronous multiprocessing setting, (c) the shipping container stowage problem, and (d) the train marshalling problem. When modelled as graph problems, (a) is the most general case while (b), (c), (d) are restrictions to different graph classes. We show that (a) does not admit polynomial-time algorithms (assuming ), even for relaxed variants of the problem (assuming ). For (b), (c), (d), we present polynomial-time algorithms to solve the respective problems. We also generalize the problem to when at most k (for a fixed integer ) contiguous vertices on a shortest path can be changed at a time.

Abstract

Image Attribution seeks to reveal the importance of image regions in the classifier’s final decision. Of the various ways to tackle this problem, the optimization based perspective is particularly intuitive: It applies the attribution as a mask on the image and reduces the attribution task to a loss, that can be optimized using gradient descent. Previous work has considered the goal as searching for the single best mask. Under this setup, however, there is a tendency towards trivial solutions of large masks with reduced discernment of the relative importances of regions. This has typically required auxiliary loss terms to control the area of the mask, however, their strength relative to the primary loss needs to be tuned. We challenge this necessity, by re-imagining attribution as an ordering of pixels according to importance. This ordering may be interpreted as a schedule which determines which locations get seen earlier and which later, allowing us to create a trajectory of masks from completely OFF to completely ON. We optimize through this sequence of masks of “all” areas and not just a single mask as in previous methods. We explore this setting, which we dub Saliency-as-Schedule (SaS), and demonstrate its effectiveness through experiments in a variety of settings, involving multiple datasets and CNN architectures. Further, we also propose a novel attribution task, feature saliency, where we use SaS to rate the influence of image regions on the intermediate feature maps of a CNN, and not just the class logit. Our findings suggest that SaS is a promising direction for the attribution problem. Our code will be available at https://github.com/tumbleweed/SaliencyasSchedule

Abstract

Image Attribution is the task of ascribing importance to regions of the input, for the final decision of a classifier. Many methods for attribution exist, and a recent development has been to use the image at multiple scales to improve the performance of some lightweight attribution methods. These gains have been demonstrated for methods that require a single or multiple but independent forward passes through the network; however, they haven’t been explored in the context of optimization-based attribution (OA) methods. As compared to other techniques, like CAMs or axiomatic methods, OA is attractive as it lends a natural formulation of the task without the need for any heuristic rules. However, the iterative way of solving the optimization problem presents challenges to straightforward utilization of multiple scales. We investigate this scenario and develop a novel 2-step approach that first discovers promising areas across scales and locations from the input and then runs Optimization based Attribution on them. We find that while a naive incorporation of image crops is unsuccessful, this 2-stage pipeline leads to improvements in performance. We provide qualitative and quantitative evidence for this and investigate the reasons for the improvement via multiple ablation experiments.

Abstract

The recent surge in the vehicle market has led to an alarming increase in road accidents. This underscores the critical importance of enhancing road safety measures, particularly for vulnerable road users like motorcyclists. Hence, we introduce the rider intention prediction (RIP) competition that aims to address challenges in rider safety by proactively predicting maneuvers before they occur, thereby strengthening rider safety. This capability enables the riders to react to the potential incorrect maneuvers flagged by advanced driver assistance systems (ADAS). We collect a new dataset, namely, rider action anticipation dataset (RAAD) for the competition consisting of two tasks: single-view RIP and multi-view RIP. The dataset incorporates a spectrum of traffic conditions and challenging navigational maneuvers on roads with varying lighting conditions. For the competition, we received seventy-five registrations and five team submissions for inference of which we compared the methods of the top three performing teams on both the RIP tasks: one state-space model (Mamba2) and two learning-based approaches (SVM and CNN-LSTM). The results indicate that the state-space model outperformed the other methods across the entire dataset, providing a balanced performance across maneuver classes. The SVM-based RIP method showed the second-best performance when using random sampling and SMOTE. However, the CNN-LSTM method underperformed, primarily due to class imbalance issues, particularly struggling with minority classes. This paper details the proposed RAAD dataset and provides a summary of the submissions for the RIP 2024 competition.

Abstract

The problem of determining geolocation through visual inputs, known as Visual Place Recognition (VPR), has attracted significant attention in recent years owing to its potential applications in autonomous self-driving systems. The rising interest in these applications poses unique challenges, particularly the necessity for datasets encompassing unstructured environmental conditions to facilitate the development of robust VPR methods. In this paper, we address the VPR challenges by proposing an Indian driving VPR dataset that caters to the semantic diversity of unstructured driving environments like occlusions due to dynamic environments, variations in traffic density, viewpoint variability, and variability in lighting conditions. In unstructured driving environments, GPS signals are unreliable often affecting the vehicle to accurately determine location. To address this challenge, we develop an interactive image-to-image tagging annotation tool to annotate large datasets with ground truth annotations for VPR training. Evaluation of the state-of-the-art methods on our dataset shows a significant performance drop of up to 15%, defeating a large number of standard VPR datasets. We also provide an exhaustive quantitative and qualitative experimental analysis of frontal-view, multi-view, and sequence-matching methods. We believe that our dataset will open new challenges for the VPR research community to build robust models.

Abstract

With the increased importance of autonomous navigation systems has come an increasing need to protect the safety of Vulnerable Road Users (VRUs) such as pedestrians. Predicting pedestrian intent is one such challenging task, where prior work predicts the binary cross/no-cross intention with a fusion of visual and motion features. However, there has been no effort so far to hedge such predictions with humanunderstandable reasons. We address this issue by introducing a novel problem setting of exploring the intuitive reasoning behind a pedestrian’s intent. In particular, we show that predicting the ‘WHY’ can be very useful in understanding the ‘WHAT’. To this end, we propose a novel, reasonenriched PIE++ dataset consisting of multi-label textual explanations/reasons for pedestrian intent. We also introduce a novel multi-task learning framework called MINDREAD, which leverages a cross-modal representation learning framework for predicting pedestrian intent as well as the reason behind the intent. Our comprehensive experiments show significant improvement of 5.6% and 7% in accuracy and F1-score for the task of intent prediction on the PIE++ dataset using MINDREAD. We also achieved a 4.4% improvement in accuracy on a commonly used JAAD dataset. Extensive evaluation using quantitative/qualitative metrics and user studies shows the effectiveness of our approach.

Abstract

Prior works have addressed the problem of driver intention prediction (DIP) by identifying maneuvers after their onset. On the other hand, early anticipation is equally important in scenarios that demand a preemptive response before a maneuver begins. However, there is no prior work aimed at addressing the problem of driver action anticipation before the onset of the maneuver, limiting the ability of the advanced driver assistance system (ADAS) for early maneuver anticipation. In this work, we introduce Anticipating Driving Maneuvers (ADM), a new task that enables driver action anticipation before the onset of the maneuver. To initiate research in ADM task, we curate Driving Action Anticipation Dataset, DAAD, that is multi-view: in- and out-cabin views in dense and heterogeneous scenarios, and multimodal: egocentric view and gaze information. The dataset captures sequences both before the initiation and during the execution of a maneuver. During dataset collection, we also ensure to capture wide diversity in traffic scenarios, weather and illumination, and driveway conditions. Next, we propose a strong baseline based on a transformer architecture to effectively model multiple views and modalities over longer video lengths. We benchmark the existing DIP methods on DAAD and related datasets. Finally, we perform an ablation study showing the effectiveness of multiple views and modalities in maneuver anticipation

Abstract

This paper presents the competition report on Reading Documents through Aria Glasses (ICDAR 2024 RDTAG) held at the 18th International Conference on Document Analysis and Recognition (ICDAR 2024). From a mixed reality perspective, understanding the text in the world is of paramount importance. However, all day long, always on, machine perception devices like Aria Glasses pose a unique primary challenge of lower resolution due to their power and sensor constraints. Moreover, diverse everyday scenes like variations in the lighting conditions and reading positions further complicate the reading tasks. To address this, we propose a new dataset and a challenge. Specifically, we propose three novel tasks: Isolated Word Recognition in Low Resolution (Task A), Prediction of Reading Order (Task B), and Page Level Recognition (Task C). We provide new training and test sets consisting of document images captured by Aria Glasses while reading diverse documents in English under various everyday scenarios. Our aim is to engage researchers with prior experience in English language OCR, and to establish benchmarks contributing to the academic literature in this field. A total of thirty-three different teams from around the world registered for this competition, and twelve teams submitted their results along with algorithm details. The winning team, SRCB, achieved a 97.23% Character Recognition Rate (CRR) and a 90.45% Word Recognition Rate (WRR) for Task A: Isolated Word Recognition in Low Resolution. Team Gang-of-N won Task B: Prediction of Reading Order with a BLEU score of 0.0939. Team SRCB also won Task C: Page Level Recognition and Reading with a 77.44% average Page Level Character Recognition Rate (PCRR) and a 50.55% average Page Level Word Recognition Rate (PWRR).