# ComCLIP: Training-Free Compositional Image and Text Matching

Kenan Jiang∗†
UC Berkeley
<EMAIL_ADDRESS>Xuehai He∗
UC Santa Cruz
<EMAIL_ADDRESS>Ruize Xu†
Renmin University of China
<EMAIL_ADDRESS>Xin Eric Wang
UC Santa Cruz
<EMAIL_ADDRESS>
###### Abstract

Contrastive Language-Image Pretraining (CLIP) has demonstrated great zero-shot
performance for matching images and text. However, it is still challenging to
adapt vision-lanaguage pretrained models like CLIP to compositional image and
text matching — a more challenging image and text matching task requiring the
model understanding of compositional word concepts and visual components.
Towards better compositional generalization in zero-shot image and text
matching, in this paper, we study the problem from a causal perspective: the
erroneous semantics of individual entities are essentially confounders that
cause the matching failure. Therefore, we propose a novel training-free
compositional CLIP model (ComCLIP). ComCLIP disentangles input images into
subjects, objects, and action sub-images and composes CLIP’s vision encoder
and text encoder to perform evolving matching over compositional text
embedding and sub-image embeddings. In this way, ComCLIP can mitigate spurious
correlations introduced by the pretrained CLIP models and dynamically evaluate
the importance of each component. Experiments on four compositional image-text
matching datasets: SVO, ComVG, Winoground, and VL-checklist, and two general
image-text retrieval datasets: Flick30K, and MSCOCO demonstrate the
effectiveness of our plug-and-play method, which boosts the zero-shot
inference ability of CLIP, SLIP, and BLIP2 even without further training or
fine-tuning.

**footnotetext: Equally contributed.††footnotetext: Work done during
internship at UC Santa Cruz. Figure 1: Examples of the compositional image-
text matching problem, in which the positive and negative images have very
similar semantics except for the only difference in subject, predicate/verb,
or object. CLIP mistakenly connects the text prompts with the wrong images on
the right (high similarity scores with negative images), while our ComCLIP
model does compositional matching more effectively.

##  1 Introduction

Image and text matching [36, 24] is a fundamental task for vision-language
research that involves multimodal reasoning and multi-level visual and text
concept alignment. Recently, a growing number of pretrained vision-language
foundation models [37, 16, 20, 22] have shown encouraging results towards
open-domain visual and language concept matching. Among these models, CLIP
[37] can be easily transferred to image and text matching under zero-shot and
few-shot scenarios. However, CLIP treats the image and the text as a whole for
alignment and ignores the compositional matching of disentangled concepts.
Especially for tasks that require the model’s compositional understanding
ability. For instance, Figure 1 shows some examples that CLIP fails at, which
require a compositional generalization of the model to understand different
subject, predicate, or object concepts.

In fact, it is widely observed that current pretrained vision-language models
struggle to recognize actions from the input image, distinguishing objects
from subjects [11], or failing to identify objects in unseen surroundings
[38]. These may be ascribed to shortcut learning [7] and dataset biases during
pretraining, where the models learn the correspondence between entities and
images implicitly and are thus vulnerable to spurious correlations, incurring
biases toward particular objects/subjects/predicates and combinations.

Therefore, there are primarily two challenges to address when adopting CLIP
for compositional image and text matching. _Challenge 1_ : the pretrained
language model in CLIP is biased and tends to rely on spurious relationships
learned during pretraining. For example, in Figure 1 (A), CLIP associates
“frisbee” with “dog” because of their more frequent co-occurrence and makes
the wrong prediction. Meanwhile, the richness of entities in text descriptions
brings _Challenge 2_ : entity embeddings should contribute dynamically for
compositional matching. Taking Figure 1 for illustration, the
subject/predicate/object entities “man/hitting/sign”, as identifiers for
correct matching in each scenario, should be endowed with more importance.
Based on the semantics of input images, CLIP should adjust the weights for
these entity embeddings. Yet existing approaches often calculate the
similarities merely based on the global embedding of images and texts and
overlook fine-grained concept matching [21].

To address the aforementioned limitations, we propose a new training-free
framework based on CLIP-like models from the causal viewpoint, named ComCLIP.
Specifically, we disentangle the visual scene into individual visual concepts
and construct counterfactual subimages containing subject/object/predicate
entities only. Then we utilize backdoor adjustment [33] to implement
interventions over the disentangled subimages to mitigate the effect of
spurious correlations. With this design, ComCLIP can bind the disentangled
visual components with the correct word concept and avoid matching solely
based on spurious correlations learned during pretraining and fine-tuning,
achieving compositional generalization. To validate our approach, we formalize
the compositional image and text matching task and construct a new
Compositional Visual Genome (ComVG) dataset from the Visual Genome [17]
dataset for this task. We do evaluations on multiple datasets: SVO-Probes
[11], Flickr30K [36], MSCOCO [24], Winoground, VL-checklist, and the
Compositional Visual Genome (ComVG) dataset. Notably, ComCLIP gains an
absolute accuracy improvement of 2.3% and 1.1% over CLIP using ViT-B-32 and
ResNet-50 on ComVG and SVO-Probes respectively.

Our primary contributions are summarized as follows:

  * •

We formally define the compositional image and text matching problem and
propose a novel approach named ComCLIP to address it from the causal
perspective: it disentangles the input image into counterfactual subimages and
leverages the idea of backdoor adjustment [33] to compose entity features and
perform fine-grained compositional concept matching, mitigating the effect of
spurious correlations introduced during training and achieve compositional
generalization.

  * •

The ComCLIP framework is training-free and can be applied to CLIP-like models
for zero-shot inference without pretraining or fine-tuning.

  * •

We introduce a new dataset, the Compositional Visual Genome†††The dataset is
available at  https://drive.google.com/file/d/1rWHuq48pa
ToXZs7_OT2Wko4l5YrAfFmR/view , which contains 5400 image-text pairs with
subject, verb, and object annotations. This dataset was generated by creating
image–sentence pairs from the Visual Genome [17] in the same format as the
SVO-Probes [11] dataset, to benchmark compositional image and text matching.

  * •

We demonstrate the effectiveness of ComCLIP by outperforming CLIP on the SVO-
Probes, Compositional Visual Genome, Winoground, and VL-checklist dataset over
the compositional image-text matching task. We also shows its effectiveness
over the general image-text retrieval task by testing Flickr30K and MSCOCO.

Figure 2: Overview of our ComCLIP framework using CLIP as the backbone. We
disentangle the input image using three independent encoding mechanisms by
obeying the rules of encoding object, subject, and predicate respectively. The
entity information is introduced to the global embedding of the whole image.
Module components from CLIP (vision encoder $F(\cdot)$, text encoder
$G(\cdot)$) are always frozen. The whole framework is training-free.

##  2 Related Work

Image-Text Matching Most existing image-text matching datasets are evaluated
in a classification setting. For example, [4, 27] focus on the relationship or
interaction detection. [9, 6] explore how creating hard negatives (_e.g_., by
substituting words in train examples) leads to better test performance. FOIL
benchmark [40] tests if vision-language models can differentiate between
sentences that vary with respect to only one noun. SVO-Probes adds hard
evaluation examples to test the model’s understanding of verbs as well as
subjects and objects in a controlled way. To associate local regions in an
image with texts to do matching, [45] incorporates a soft form of attention
into their recurrent model. [30] learns multiple networks that capture words,
phrases, and sentence-level interactions with images and combines the scores
of these networks to obtain a whole image-sentence score. [13] leverages
spatial information and global context to predict where objects are likely to
occur. [42] formulates a linear program to localize all the phrases from a
caption jointly. In this paper, we focus on the task of matching error-prone
texts with images, requiring distinguishing words on a granular level —
compositional image and text matching.

Pretrained Vision-Language Models Vision-Language models pretrained on large-
scale image-text pairs have demonstrated great potential in multimodal
representation learning [16, 47, 48, 22, 37]. Among them, CLIP [37] benefits
from 400M curated data and defines various prompt templates to carry out zero-
shot image classification. GLIP [22] has incorporated region-level alignment
in its pretraining. However, these models can suffer from connecting
verbs/subjects/objects concepts with visual components correctly [11] and bias
towards spurious relations they have seen in the pretraining data, referred to
as “confounders” [50]. By modeling using a structural causal model (SCM)
network [34], [50] executes a hard intervention to eliminate dataset bias via
a backdoor intervention during pretraining. Different from them, in this work,
we focus on mitigating the effect of spurious relations and improving the
zero-shot inference and compositonal generalization abilities of off-the-shelf
pretrained vision-language models. We develop a new training-free paradigm
that gains superior performance on compositional image and text matching.

Disentangled Representation Learning It is often assumed that real-world
observations like images can be disentangled [1, 35]. [23] disentangles
background, texture, shape, etc., and uses object bounding boxes as
supervision to synthesize images. [2] leverages the idea of independent
mechanisms to identify modularity in pretrained generative models. [32]
performs hierarchical alignments in three different granularities, i.e.,
global-global, global-local, and local-local alignments for description-based
person re-id. [5] improves fine-grained video-text retrieval by decomposing
video-text matching into global-to-local levels. [49] proposes a multi-
granularity semantic collaborative reasoning network and employs different
granularity semantic representations of the question and dialog history to
collaboratively identify the relevant information from multiple inputs based
on attention mechanisms. [39] utilizes independent mechanisms to generate
images to improve image classification. [29] disentangles word entities from
the conventional meanings of special entities encoded in the pretrained
language model. None of these works consider the alignment of subjects,
objects, and predicate entities. Different from them [35], we employ
independent mechanisms to disentangle images and use generated subimages to
improve fine-grained visual and language concept matching, which can mitigate
spurious correlations introduced by the pretrained model.

##  3 Compositional Image and Text Matching

We first introduce the task of compositional image and text matching, where we
are interested in improving the compositional understanding, more
specifically, subject/object/predicate understanding of vision-language
models. Compositional image and text matching is a task focused on enhancing
the understanding of compositional elements such as subjects, objects, and
predicates within CLIP-like models. This task requires an appreciation of fine
distinctions between texts and their underlying compositional structure, as
illustrated in Figure 1 with phrases like “man/hitting/sign.” The model’s
ability to differentiate images that only vary by a single conceptual element
in their accompanying text highlights its comprehension of compositionality.

We formally define this task as follows: given text prompts $Y$ (e.g., ”A man
is hitting a baseball”) and a set of entities $T^{E}=\\{e^{k}\\}_{k=1}^{K}$
such as hitting, where $K$ denotes the total number of entities and $e^{k}$
represents the $k$-th entity, the model’s objective is to match the text
prompts with the corresponding images. The challenge lies in the inclusion of
negative images that contain mismatched entities $\\{e^{k}\\}_{k=1}^{n}$,
where $n<k$. These negative images are designed to confuse the model,
demanding a nuanced understanding of the entities within a sentence. Simply
relying on nouns or spurious relations would not suffice to succeed at this
task. To evaluate how well the model grasps this concept of compositionality
in texts and matches them with the right images, we introduce an additional
Compositional Visual Genome dataset as an extended testing platform.

##  4 ComCLIP

In this section, we propose ComCLIP, incorporating a causal view into the
CLIP-like models. We briefly introduce the background of ComCLIP in view of
structured causal models in Section 4.1. Then, we present the overview of
ComCLIP pipeline in Section 4.2. We introduce its critical components in depth
in Section 4.3 and 4.4. Our dual objectives are: (i) We aim at disentangling
visual input into subimages containing fine-grained compositional concepts.
(ii) We intend to utilize those disentangled concepts to perform entity-level
matching dynamically and mitigate the effect of spurious relations in the
pretrained vision-language models learned during training.

###  4.1 Background

Causal inference aims to understand how changing one variable can affect
another, often represented using concepts such as confounders, interventions,
counterfactuals, and do-operations. In the realm of computer vision and
natural language processing, the causal relationships can provide insights
into the underlying generative processes.

Consider a dataset comprised of (high-dimensional) observations $X$ (i.e.,
images) and corresponding text prompts $Y$. Assume that each $X$ can be
described by lower-dimensional, semantically meaningful factors of variation
$z$ (e.g., objects, subjects, or action relations between objects and subjects
(i.e., predicates in the image)). These factors, which we term confounders
$Z$, may affect either $X$ or $Y$. By disentangling these factors, we can
achieve more granular image and text matching. This idea of disentanglement
resonates with the principles of structural causal models (SCMs) [34] and
independent mechanisms (IMs). An SCM is a mathematical formulation
representing how variables influence one another, often composed of multiple
IMs, which are the individual causal processes. Inspired by SCMs, our approach
decomposes the subimage generation process into three independent mechanisms:
object mechanism $f_{\text{object }}$, subject mechanism $f_{\text{subject}}$,
and predicate mechanism $f_{\text{predicate}}$.

###  4.2 Method Overview

We first introduce the overview of our method from a conceptual view. The
pipeline is shown in Figure 2. The goal is to steer the pretrained vision-
language model to do fine-grained compositional image and text matching. Given
an input image-text pair, we first disentangle the input image and generate
subimages only containing the given entity. Then we compute the pairwise
similarity between the embedding of the subimage with the entity embedding and
adopt the similarity score to weigh the subimage embedding. The weighted
embedding will be added to the global image embedding for final image-text
matching, allowing the model to capture non-spurious semantic entity
information and conduct concept matching at the granular level.

###  4.3 Counterfactual Subimage Generation

At the heart of our method lies the concept of causality, particularly, the
Independent Mechanism (IM) assumption. In the realm of causality, the IM
assumption posits that a system’s variable generation process comprises
autonomous modules that operate without mutual interference [35]. We adopt
this principle and tailor it to our context by considering three independent
mechanisms for generating object, subject, and predicate subimages.

While our method is inspired by causal mechanisms, we do not make strong
causal claims. Instead, we utilize the intuition that in a complex system,
certain variables (or mechanisms) operate autonomously. Given the
aforementioned setup, our structural causal model (SCM) takes the form:
$\mathbf{O}:=f_{\text{object
}}\left(X\right),\mathbf{S}:=f_{\text{subject}}\left(X\right),\mathbf{P}:=f_{\text{predicate}}\left(X\right).$
Where $\mathbf{O}$ is the object image, $\mathbf{S}$ is the subject image, and
$\mathbf{P}$ is the predicate image.

Using the structural framework detailed above, we answer counterfactual
questions, a fundamental concept in causality. Specifically, we pose questions
like ”What if we retain only the subject/object/predicate in the original
image?”. The responses to such inquiries allow us to generate what we term as
_counterfactual subimages_. The essence of these images is that they
exclusively feature the entity in question (see Figure 2 for examples). This
procedure leads to the disentanglement of the input image into three distinct
and causally independent subimages.

With these foundational blocks in place, our method is geared to connect each
disentangled image entity with its corresponding textual counterpart. When
each entity is independently and aptly encoded, matching them becomes
streamlined and efficient. The remaining challenge then is to craft a
mechanism that effectively governs the composition process of distinct entity
regions within an image.

###  4.4 Entity Composition

As mentioned earlier, the pretrained CLIP-like model is prone to be biased
toward specific subjects, objects or predicates, or even rely solely on one of
them in the given sentence. From the causal perspective, to match image $X$
with text prompt $Y$ correctly, we want to infer $P(Y|X)$ while at the same
time mitigating the effect of detrimental confounders $z$. The confounders may
introduce spurious correlations in the model when directly inferring from
$P(Y\mid X)$. Leveraging Bayes Rule,

$P(Y\mid X)=\sum_{z}P(Y,z\mid X)=\sum_{z}P(Y\mid X,z){P(z\mid X)},$ (1)

where the confounder $z$ introduces the bias of word concept via $P(z\mid X)$.
To adjust the effect of confounder $z$, we can intervene $X$ by first
disentangling it and then intervening with it using $do$-operation †††$P(Y\mid
do(X)$ uses the do-operator [8]. Given random variables $X,Y$, we write
$P(Y=y\mid do(X=x))$ to indicate the probability that $Y=y$ when we intervene
and set $X$ to be $x$. :

$P(Y\mid do(X))=\sum P(Y\mid X,z){P(z)}.$ (2)

We now seek an implicit way to compute $P(Y\mid X,z)$ and ${P(z)}$.
Considering the SCMs mentioned above, we interpret $f_{\text{object
}}(X),f_{\text{subject}}(X),f_{\text{predicate}}(X)$ as incorporating the
entity semantics into attended regions of images.

To do concept matching over the text prompt $Y$ and the entity set
$T^{E}=\left\\{e^{k}\right\\}_{k=1}^{K}$, where $K$ is the total number of
entities, and $e^{k}$ is the $k$-th entity. This interpretation motivates us
to compute the similarity between $f_{\text{object
}}(X),f_{\text{subject}}(X),f_{\text{predicate}}(X)$ with different word
entity embeddings to achieve concept-wise semantic fusion and guidance. The
prediction $P(Y\mid X,z)$ can be regarded as a classifier: $P(Y\mid X,z)=$
Softmax $f_{i}(X,z)$. Similar to [43], using the approximation of NGSM
(Normalized Weighted Geometric Mean) [46], we have: $P(Y\mid
do(X))\approx\operatorname{Softmax}\left[\mathbb{E}_{z}\left(f_{i}(X,z)\right)\right].$
Specifically, to implement this on the ComVG dataset, given an input image $X$
and IMs $f_{\text{object
}}(\cdot),f_{\text{subject}}(\cdot),f_{\text{predicate}}(\cdot)$, we first
extract a collection of visual concepts from input images as $f_{\text{object
}}(X),f_{\text{subject}}(X),f_{\text{predicate}}(X)$. For the language side,
given a prompt $Y$ and its entity set $T^{E}$, we extract all (subject,
object, predicate) words ($Y_{s},Y_{o},Y_{p}$) from the input text prompts.
Using cosine similarity score $\mathcal{S}$ as an example, we compute the
concept-level similarity separately:

$\displaystyle S_{1}=\mathcal{S}(F(f_{\text{object }}(X)),G(Y_{s})),$ (3)
$\displaystyle S_{2}=\mathcal{S}(F(f_{\text{subject }}(X)),G(Y_{o})),$
$\displaystyle S_{3}=S(F(f_{\text{predicate}}(X)),G(Y_{p})),\;$
$\displaystyle\text{where}\
F(\cdot)=\text{CLIP}_{\text{vision}}(\cdot),\;G(\cdot)=\text{CLIP}_{\text{text}}(\cdot).$

The final visual feature is composed by:

$\displaystyle V=F(X)+$ $\displaystyle F(f_{\text{object
}}(X))S_{1}+F(f_{\text{subject }}(X))S_{2}$ (4)
$\displaystyle+F(f_{\text{predicate}}(X))S_{3}.\;$

We can compute the image-text matching score by: $O=S(G(Y),V).$ With this
design, the language part of CLIP is aware of connections between entities
from both the visual and language input when doing the concept matching.

Our algorithm is summarized in Algorithm 1 in the Supplementary Material,
which requires no training or additional data. Note that apart from CLIP, it
can be easily adapted to other vision-language pretrained model with the two-
stream encoder structure.

##  5 Experiments

###  5.1 Datasets

We use the following datasets for evaluation:

Flickr30K [36] Each test image has 5 annotations; one annotation is selected
randomly. CLIP is evaluated across the dataset; for ComCLIP, the top 10
similar images from CLIP are taken. We create subimages for the top 10 similar
images and apply ComCLIP to them.

MSCOCO [24] From 1000 images (each having 5-6 annotations), one annotation is
selected randomly. Like Flickr30K, the top 10 images from CLIP undergo ComCLIP
processing, and subimages are created based on parsed elements.

Winoground [41] Designed to evaluate vision-language models, this dataset
contains 400 instances with two image-text pairs per instance. The challenge
is the differing arrangement of identical words across the pairs. Our
evaluation spanned the entire dataset.

VL-checklist [51] Distinguishing itself by combining multiple sources, VL-
checklist classifies 410,000 images into three categories. We analyzed a
subset of 2000 images from each category to gauge our method’s effectiveness.

SVO-Probes [11] Built to assess language-image models on distinctions within
image elements. From its initial 30,000 data points, we utilized 13,000 due to
accessibility issues. We conducted tests using three random divisions and
presented the average accuracy in our results.

Compositional Visual Genome (ComVG)  Derived from Visual Genome’s [17] 2.3
million relationships, we developed ComVG. These relationships, encompassing
action and spatial aspects, are formatted in subject, predicate, and object
triplets. Leveraging these triplets, we crafted image descriptions using
articles. Capitalizing on Visual Genome’s abundant relationship-annotated
images, we curated a subset to challenge models’ differentiation abilities.
From this, we selected 542 images with distinct relationships. Inspired by
SVO-Probes, for each primary image, we identified mutated variants with
singular discrepancies in subject, object, or predicate. This process yielded
5400 manually-curated test samples, with subsequent grammatical corrections.
ComVG distinguishes itself with superior image quality and an emphasis on
text-to-image retrieval. For comprehensive dataset statistics, refer to Table
1. Our evaluation covered the entire ComVG.

Further dataset examples are available in the Supplementary Material.

| Sub-Neg | Pred-Neg | Obj-Neg | Subjects | Predicates | Objects
---|---|---|---|---|---|---
ComVG | 2,584 | 1,536 | 1,280 | 30 | 65 | 82
SVO | 5,679 | 23,525 | 7,637 | 100 | 421 | 275

Table 1:  The number of data samples in the dataset that have one of their
subjects, objects, or predicates changed between positive and negative images
and the number of unique types of subjects, verbs, and objects across
Compositional Visual Genome (ComVG) and SVO-Probes (SVO).  Figure 3:
Comparison of Recall@1 (%) and Recall@5 (%) using CLIP and ComCLIP over the
general image-text retrieval datasets.

Method | ComVG | SVO-Probes
---|---|---
Sub | Pred | Obj | Ave | Sub | Pred | Obj | Ave
GLIP | 65.95 | 57.50 | 65.75 | 63.85 | 68.91 | 65.14 | 74.94 | 67.81
SLIP | 86.20 | 61.33 | 85.84 | 80.13 | 79.62 | 79.92 | 78.43 | 79.57
ComSLIP $\spadesuit$ | 87.43 | 61.25 | 87.11 | 81.07 | 79.73 | 80.83 | 79.63 | 80.42
CLIP | 88.61 | 68.52 | 93.85 | 83.66 | 85.53 | 80.77 | 90.53 | 85.61
ComCLIP $\spadesuit$ | 90.04 | 69.06 | 94.78 | 84.63 | 86.70 | 81.87 | 90.67 | 86.41

Table 2: Comparison of accuracy (%) on ComVG, and average accuracy (%) across
the three splits on SVO-Probes using CLIP, GLIP, and ComCLIP. Results marked
with $\spadesuit$ are our methods. Ours could also beat GLIP, showing the
superiority of our method compared with region-based vision-language
pretrained models.

| Compositional Visual Genome | SVO-Probes
---|---|---
Vision Encoder | CLIP | OpenCLIP | ComCLIP | CLIP | OpenCLIP | ComCLIP
ResNet-50 | 82.25 | 82.21 | 83.73 | 83.07 | 83.06 | 84.17
ViT-B-32 | 82.45 | 82.41 | 84.75 | 84.28 | 84.27 | 85.18
ViT-L-14 | 86.38 | 86.38 | 87.40 | 85.61 | 85.60 | 86.41

Table 3: Comparison of accuracy (%) on Compositional Visual Genome and SVO-
Probes using CLIP, OpenCLIP, and ComCLIP.

| Compositional Visual Genome | SVO-Probes
---|---|---
Subimage Configuraion | ResNet-50 | ViT-B-32 | ViT-L-14 | ResNet-50 | ViT-B-32 | ViT-L-14
ComCLIP | 83.73 | 84.73 | 87.40 | 84.17 | 85.18 | 86.41
All black subimages | 82.75 | 83.33 | 86.35 | 83.09 | 83.83 | 84.47
All original images | 82.25 | 82.45 | 86.38 | 83.07 | 84.27 | 85.60
All subject subimages | 82.46 | 82.55 | 86.46 | 83.18 | 84.10 | 85.24
All object subimages | 83.28 | 83.73 | 86.48 | 83.85 | 84.53 | 85.72
All predicate subimages | 82.79 | 83.33 | 86.37 | 83.30 | 84.22 | 85.34

Table 4: Comparison of accuracy (%) on Compostional Visual Genome and SVO-
Probes using different subimage configuration.

###  5.2 Baselines

CLIP [37] We use standard CLIP, where image embeddings are generated by CLIP’s
vision encoder $F$; and text embeddings are generated by CLIP’s text encoder
$G$. The cosine similarity between them is computed to do matching.

SLIP [31] We use the SLIP ViT-L-16. Similar to CLIP, the cosine similarity
between the image embeddings and text embeddings is computed to do matching.

GLIP [22] As GLIP has no global sentence and image embedding, we perform the
following rule-based matching: 1) The image with more matched objects is
predicted to be matching; 2) For images with the same set of objects, we
compute the average confidence score of each object on both images. The one
with the larger score is predicted.

BLIP2 [19] We employed the official pretrained BLIP2. To calculate the cosine
similarity between image and text features, we adopted BLIP2’s image-text
contrastive learning match head as our BLIP2 baseline. Specifically, BLIP2
computes the cosine similarity score between each image embedding from each
query output and the text embedding of the [CLS] token, selecting the highest
similarity score as the ultimate outcome.

###  5.3 Implementation Details

The process begins by processing the original image with the dense caption
module of GRiT [44], producing dense image captions based on object. The input
text sentence is then parsed using the large language model (LLM),
gpt-3.5-turbo, extracting entity words and organizing them into a subject-
predicate-object format. The alignment between dense image captions and entity
words is realized using the same LLM, mapping entity words to their image
counterparts based on captions.

For creating a predicate subimage, related object and subject subimages are
combined. The original sentence and image, along with their respective parsed
words and subimages, are fed into the CLIP text and vision encoders. Cosine
similarity scores between each image and word embedding are computed and
processed through a softmax [15] layer, yielding three positive weights. The
weighted sum of the subimage embeddings is then added to the original image’s
global embedding to obtain the final image embedding. The methodology remains
similar for SLIP [31] and BLIP2 [19], termed as ComSLIP and ComBLIP
respectively. Notably, for BLIP2, we further project the final image embedding
to the sentence embedding dimension for the score computation.

Evaluation Metrics  We use Accuracy as the evaluation metric on the
Compositional Visual Genome, SVO-Probes and VL-checklist datasets. For the
Winoground dataset, we use three accuracy scores: text, image, and group
score. The text score quantifies the proportion of both images correctly
matched to their corresponding texts. The image score indicates the rate of
both texts correctly matched to their corresponding images. Lastly, the group
score signifies the accuracy of all texts and images matched correctly. We use
Recall [3] for Flickr30K and MSCOCO over the general image-text retrieval
task.

###  5.4 Main Results

Compositional Image and Text Matching In this subsection, we show the
evaluation results on Visual Genome and SVO-Probes datasets in Table 2. Our
ComCLIP can outperform zero-shot CLIP on both Compositional Visual Genome and
SVO-Probes datasets. Separately reviewing the results, we see improvements in
all negative types. This indicates that incorporating the information of
subimages at inference time is helping CLIP attend to the semantic details of
images and make fine-grained alignment. Apart from CLIP, we also validate the
effectiveness of our method on SLIP [31], denoted by ComSLIP, with the results
shown in Table 2. As can be seen, ours can beat SLIP on both the ComVG and
SVO-Probes datasets, validating the effectiveness of our method on other CLIP-
like models.

In addition, we realize that our methods have lower performance improvement on
the SVO-Probes dataset compared to Visual Genome Datasets both on CLIP and
SLIP. This is due to the reason that SVO-Probes has a number of sketchy data
samples that we can not remove completely. We present and analyze some bad
examples from SVO-Probes in the Supplementary Material.

_Comparison with GLIP_ We compare our methods with GLIP in Table 2. Ours
outperforms GLIP by a large margin on the compositional image-text matching
task, further suggesting the effectiveness of our method compared with other
region-based vision-language pretrained models.

_Results on Winoground and VL-checklist_ From Table 5, ComCLIP and ComSLIP
consistently outperforms CLIP and SLIP respectively across both datasets,
emphasizing their ability to grasp complex image-text relationships. While
ComBLIP shows improvements, its gains are more modest, likely because BLIP2,
with its pretraining on the Visual Genome dataset, already has a strong
performance. However, it shows that our method’s capability to be generalized
to other stronger vision-language pretrained models.

#### General Image-Text Retrieval Datasets

Results on two image-text retrieval datasets are shown in Figure 3. CLIP and
ComCLIP both do well on Recall@5. Because in the general image-text retrieval
task such as the Flickr30K dataset, most examples are easy and do not
necessitate the model’s ability to comprehend compositionality. ComCLIP beats
CLIP on Recall@1 on Flickr30K and MSCOCO. This happens because ComCLIP
leverages entities and their relations in its decision, steering CLIP and thus
avoiding making decisions based on a single noun or spurious relations.
Overall, these results suggest that our method is competitive not only for
compositional image-text matching but also for general image-text retrieval
tasks.

###  5.5 Ablations and Analysis

Ablation of Different Vision Encoders The results of using different vision
encoders are shown in Table 3. ComCLIP demonstrates its effectiveness on
various vision encoders and also yields notable improvements over OpenCLIP
[14], an open source implementation of CLIP.

Method | Winoground | VL-checklist
---|---|---
Text | Image | Group | Attribute | Object | Relation | Ave
SLIP | 23.25 | 10.00 | 6.75 | 65.95 | 76.81 | 65.30 | 69.35
ComSLIP $\spadesuit$ | 26.76 | 12.12 | 9.09 | 67.64 | 77.79 | 67.02 | 70.82
CLIP | 31.25 | 11.25 | 9.00 | 67.85 | 75.70 | 67.15 | 70.23
ComCLIP $\spadesuit$ | 34.00 | 15.75 | 10.50 | 69.90 | 79.00 | 69.30 | 72.73
BLIP | 29.25 | 12.00 | 8.75 | 79.00 | 84.05 | 73.55 | 78.87
ComBLIP $\spadesuit$ | 28.75 | 13.00 | 10.00 | 79.15 | 84.70 | 73.95 | 79.27

Table 5: Comparison of accuracy (%) on Winoground and VL-checklist using SLIP,
CLIP, and BLIP2. Results marked with $\spadesuit$ are our methods. Figure 4:
Examples showing the generated subject, object, and predicate subimages. The
first and third rows correspond to positive images and individual outputs of
each IM for different entities. The second and fourth rows correspond to
negative ones. Top two rows: examples from the Compositional Visual Genome
dataset. (Woman, carrying, skateboard) is used as input (subject, predicate,
object) to each IM. Bottom two rows: examples from the SVO-Probes dataset.
(Cat, sits, table) is used as input to each IM. Note that for negative images,
when IM could not accept the given (subject, predicate, object) and generate
output subimages, the subimage is replaced with the original image for entity
composition.

Ablation of Different Subimage Configurations To demonstrate the efficacy of
our pipeline, we conducted a series of experiments using different types of
subimages in ComCLIP, with the results presented in Table 4. We evaluated the
performance of feeding all subimages with black images, feeding only subject
subimages, only object subimages, and only predicate subimages. Our
experiments involved testing diverse methods of combining three subimages, and
we found that the amalgamation of subject, object, and predicate subimages
achieved the highest accuracy across all vision encoders on both datasets.
This implies that ComCLIP utilizes the specialized information conveyed by
subimages to make accurate decisions.

###  5.6 Qualitative Comparison

We illustrate the individual outputs of each IM for different entities in
Figure 4. In each row, we show from left to right: the original image $X$,
subject image $\mathbf{S}$, object image $\mathbf{O}$, and predicate image
$\mathbf{P}$.

##  6 Conclusion

In this work, we observe that CLIP-like model could struggle in situations
that require object, subject, and verb/predicate understanding when performing
compositional image and text matching. Based on this observation, we propose a
training-free method for compositional image and text matching from the causal
view, which could mitigate the effect of spurious relations and improve
compositional generalization. We also propose a new dataset to facilitate
future research in this direction. Our method is plug-and-play and could be
applied to other vision-language pretrained model. We hope that our simple yet
effective training-free approach could boost the development of more
interpretable and principled methods for the compositional image and text
matching task.

## References

  * [1] Yoshua Bengio, Aaron Courville, and Pascal Vincent.  Representation learning: A review and new perspectives.  IEEE transactions on pattern analysis and machine intelligence, 35(8):1798–1828, 2013.
  * [2] M Besserve, A Mehrjou, R Sun, and B Schölkopf.  Counterfactuals uncover the modular structure of deep generative models.  In Eighth International Conference on Learning Representations (ICLR 2020), 2020.
  * [3] Michael Buckland and Fredric Gey.  The relationship between recall and precision.  Journal of the American society for information science, 45(1):12–19, 1994.
  * [4] Yu-Wei Chao, Zhan Wang, Yugeng He, Jiaxuan Wang, and Jia Deng.  Hico: A benchmark for recognizing human-object interactions in images.  In Proceedings of the IEEE international conference on computer vision, pages 1017–1025, 2015.
  * [5] Shizhe Chen, Yida Zhao, Qin Jin, and Qi Wu.  Fine-grained video-text retrieval with hierarchical graph reasoning.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10638–10647, 2020.
  * [6] Fartash Faghri, David J Fleet, Jamie Ryan Kiros, and Sanja Fidler.  Vse++: Improving visual-semantic embeddings with hard negatives.  arXiv preprint arXiv:1707.05612, 2017.
  * [7] Robert Geirhos, Jörn-Henrik Jacobsen, Claudio Michaelis, Richard Zemel, Wieland Brendel, Matthias Bethge, and Felix A Wichmann.  Shortcut learning in deep neural networks.  Nature Machine Intelligence, 2(11):665–673, 2020.
  * [8] Madelyn Glymour, Judea Pearl, and Nicholas P Jewell.  Causal inference in statistics: A primer.  John Wiley & Sons, 2016.
  * [9] Tanmay Gupta, Arash Vahdat, Gal Chechik, Xiaodong Yang, Jan Kautz, and Derek Hoiem.  Contrastive learning for weakly supervised phrase grounding.  In European Conference on Computer Vision, pages 752–768. Springer, 2020.
  * [10] Xuehai He, Chunyuan Li, Pengchuan Zhang, Jianwei Yang, and Xin Eric Wang.  Parameter-efficient fine-tuning for vision transformers.  arXiv preprint arXiv:2203.16329, 2022.
  * [11] Lisa Anne Hendricks and Aida Nematzadeh.  Probing image-language transformers for verb understanding.  arXiv preprint arXiv:2106.09141, 2021.
  * [12] Matthew Honnibal and Ines Montani.  spaCy 2: Natural language understanding with Bloom embeddings, convolutional neural networks and incremental parsing.  2017\.
  * [13] Ronghang Hu, Huazhe Xu, Marcus Rohrbach, Jiashi Feng, Kate Saenko, and Trevor Darrell.  Natural language object retrieval.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4555–4564, 2016.
  * [14] Gabriel Ilharco, Mitchell Wortsman, Ross Wightman, Cade Gordon, Nicholas Carlini, Rohan Taori, Achal Dave, Vaishaal Shankar, Hongseok Namkoong, John Miller, Hannaneh Hajishirzi, Ali Farhadi, and Ludwig Schmidt.  Openclip, July 2021.  If you use this software, please cite it as below.
  * [15] Eric Jang, Shixiang Gu, and Ben Poole.  Categorical reparameterization with gumbel-softmax.  arXiv preprint arXiv:1611.01144, 2016.
  * [16] Chao Jia, Yinfei Yang, Ye Xia, Yi-Ting Chen, Zarana Parekh, Hieu Pham, Quoc Le, Yun-Hsuan Sung, Zhen Li, and Tom Duerig.  Scaling up visual and vision-language representation learning with noisy text supervision.  In International Conference on Machine Learning, pages 4904–4916. PMLR, 2021.
  * [17] Ranjay Krishna, Yuke Zhu, Oliver Groth, Justin Johnson, Kenji Hata, Joshua Kravitz, Stephanie Chen, Yannis Kalantidis, Li-Jia Li, David A Shamma, et al.  Visual genome: Connecting language and vision using crowdsourced dense image annotations.  International journal of computer vision, 123(1):32–73, 2017.
  * [18] Chunyuan Li, Haotian Liu, Liunian Harold Li, Pengchuan Zhang, Jyoti Aneja, Jianwei Yang, Ping Jin, Yong Jae Lee, Houdong Hu, Zicheng Liu, et al.  Elevater: A benchmark and toolkit for evaluating language-augmented visual models.  arXiv preprint arXiv:2204.08790, 2022.
  * [19] Junnan Li, Dongxu Li, Silvio Savarese, and Steven Hoi.  Blip-2: Bootstrapping language-image pre-training with frozen image encoders and large language models.  arXiv preprint arXiv:2301.12597, 2023.
  * [20] Junnan Li, Dongxu Li, Caiming Xiong, and Steven Hoi.  Blip: Bootstrapping language-image pre-training for unified vision-language understanding and generation.  arXiv preprint arXiv:2201.12086, 2022.
  * [21] Kunpeng Li, Yulun Zhang, Kai Li, Yuanyuan Li, and Yun Fu.  Visual semantic reasoning for image-text matching.  In Proceedings of the IEEE/CVF international conference on computer vision, pages 4654–4662, 2019.
  * [22] Liunian Harold Li, Pengchuan Zhang, Haotian Zhang, Jianwei Yang, Chunyuan Li, Yiwu Zhong, Lijuan Wang, Lu Yuan, Lei Zhang, Jenq-Neng Hwang, et al.  Grounded language-image pre-training.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10965–10975, 2022.
  * [23] Yuheng Li, Krishna Kumar Singh, Utkarsh Ojha, and Yong Jae Lee.  Mixnmatch: Multifactor disentanglement and encoding for conditional image generation.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 8039–8048, 2020.
  * [24] Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick.  Microsoft coco: Common objects in context.  In ECCV, 2014.
  * [25] Edward Loper and Steven Bird.  Nltk: The natural language toolkit.  arXiv preprint cs/0205028, 2002.
  * [26] Ilya Loshchilov and Frank Hutter.  Decoupled weight decay regularization.  arXiv preprint arXiv:1711.05101, 2017.
  * [27] Cewu Lu, Ranjay Krishna, Michael Bernstein, and Li Fei-Fei.  Visual relationship detection with language priors.  In European conference on computer vision, pages 852–869. Springer, 2016.
  * [28] Timo Lüddecke and Alexander Ecker.  Image segmentation using text and image prompts.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 7086–7096, June 2022.
  * [29] Haoyu Ma, Handong Zhao, Zhe Lin, Ajinkya Kale, Zhangyang Wang, Tong Yu, Jiuxiang Gu, Sunav Choudhary, and Xiaohui Xie.  Ei-clip: Entity-aware interventional contrastive learning for e-commerce cross-modal retrieval.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 18051–18061, 2022.
  * [30] Lin Ma, Zhengdong Lu, Lifeng Shang, and Hang Li.  Multimodal convolutional neural networks for matching image and sentence.  In Proceedings of the IEEE international conference on computer vision, pages 2623–2631, 2015.
  * [31] Norman Mu, Alexander Kirillov, David Wagner, and Saining Xie.  Slip: Self-supervision meets language-image pre-training.  arXiv preprint arXiv:2112.12750, 2021.
  * [32] Kai Niu, Yan Huang, Wanli Ouyang, and Liang Wang.  Improving description-based person re-identification by multi-granularity image-text alignments.  IEEE Transactions on Image Processing, 29:5542–5556, 2020.
  * [33] Judea Pearl et al.  Models, reasoning and inference.  Cambridge, UK: CambridgeUniversityPress, 19(2), 2000.
  * [34] Judea Pearl et al.  Models, reasoning and inference.  Cambridge, UK: CambridgeUniversityPress, 19(2), 2000.
  * [35] Jonas Peters, Dominik Janzing, and Bernhard Schölkopf.  Elements of causal inference: foundations and learning algorithms.  The MIT Press, 2017.
  * [36] Bryan A Plummer, Liwei Wang, Chris M Cervantes, Juan C Caicedo, Julia Hockenmaier, and Svetlana Lazebnik.  Flickr30k entities: Collecting region-to-phrase correspondences for richer image-to-sentence models.  In Proceedings of the IEEE international conference on computer vision, pages 2641–2649, 2015.
  * [37] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al.  Learning transferable visual models from natural language supervision.  In International Conference on Machine Learning, pages 8748–8763. PMLR, 2021.
  * [38] Amir Rosenfeld, Richard Zemel, and John K Tsotsos.  The elephant in the room.  arXiv preprint arXiv:1808.03305, 2018.
  * [39] Axel Sauer and Andreas Geiger.  Counterfactual generative networks.  arXiv preprint arXiv:2101.06046, 2021.
  * [40] Ravi Shekhar, Sandro Pezzelle, Yauhen Klimovich, Aurélie Herbelot, Moin Nabi, Enver Sangineto, and Raffaella Bernardi.  Foil it! find one mismatch between image and language caption.  arXiv preprint arXiv:1705.01359, 2017.
  * [41] Tristan Thrush, Ryan Jiang, Max Bartolo, Amanpreet Singh, Adina Williams, Douwe Kiela, and Candace Ross.  Winoground: Probing vision and language models for visio-linguistic compositionality.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 5238–5248, 2022.
  * [42] Mingzhe Wang, Mahmoud Azab, Noriyuki Kojima, Rada Mihalcea, and Jia Deng.  Structured matching for phrase localization.  In European Conference on Computer Vision, pages 696–711. Springer, 2016.
  * [43] Tan Wang, Jianqiang Huang, Hanwang Zhang, and Qianru Sun.  Visual Commonsense R-CNN.  arXiv:2002.12204 [cs], April 2020.
  * [44] Jialian Wu, Jianfeng Wang, Zhengyuan Yang, Zhe Gan, Zicheng Liu, Junsong Yuan, and Lijuan Wang.  Grit: A generative region-to-text transformer for object understanding.  arXiv preprint arXiv:2212.00280, 2022.
  * [45] Kelvin Xu, Jimmy Ba, Ryan Kiros, Kyunghyun Cho, Aaron Courville, Ruslan Salakhudinov, Rich Zemel, and Yoshua Bengio.  Show, attend and tell: Neural image caption generation with visual attention.  In International Conference on Machine Learning, pages 2048–2057, 2015.
  * [46] Kelvin Xu, Jimmy Ba, Ryan Kiros, Kyunghyun Cho, Aaron Courville, Ruslan Salakhudinov, Rich Zemel, and Yoshua Bengio.  Show, attend and tell: Neural image caption generation with visual attention.  In International conference on machine learning, 2015.
  * [47] Lewei Yao, Runhui Huang, Lu Hou, Guansong Lu, Minzhe Niu, Hang Xu, Xiaodan Liang, Zhenguo Li, Xin Jiang, and Chunjing Xu.  Filip: Fine-grained interactive language-image pre-training.  arXiv preprint arXiv:2111.07783, 2021.
  * [48] Lu Yuan, Dongdong Chen, Yi-Ling Chen, Noel Codella, Xiyang Dai, Jianfeng Gao, Houdong Hu, Xuedong Huang, Boxin Li, Chunyuan Li, et al.  Florence: A new foundation model for computer vision.  arXiv preprint arXiv:2111.11432, 2021.
  * [49] Hongwei Zhang, Xiaojie Wang, Si Jiang, and Xuefeng Li.  Multi-granularity semantic collaborative reasoning network for visual dialog.  Applied Sciences, 12(18):8947, 2022.
  * [50] Shengyu Zhang, Tan Jiang, Tan Wang, Kun Kuang, Zhou Zhao, Jianke Zhu, Jin Yu, Hongxia Yang, and Fei Wu.  Devlbert: Learning deconfounded visio-linguistic representations.  In Proceedings of the 28th ACM International Conference on Multimedia, pages 4373–4382, 2020.
  * [51] Tiancheng Zhao, Tianqi Zhang, Mingwei Zhu, Haozhan Shen, Kyusong Lee, Xiaopeng Lu, and Jianwei Yin.  Vl-checklist: Evaluating pre-trained vision-language models with objects, attributes and relations.  arXiv preprint arXiv:2207.00221, 2022.

##  Appendix A Algorithm Details

The comprehensive steps of the ComCLIP algorithm are shown in Algorithm 1.
References to equation numbers ({Eq. (3)}, {Eq. (4)}) correspond to those in
the main paper.

Algorithm 1 Training-Free Compositional Image and Text Matching with ComCLIP.

0: Input: image $X$, text prompt $Y$, vision encoder $F(\cdot)$, text encoder
$G(\cdot)$, independent mechanisms $f_{\text{object
}}(\cdot),f_{\text{subject}}(\cdot),f_{\text{predicate}}(\cdot)$.Output:
Matching score $O$.

1: Generate counterfactual subimages
$\mathbf{O},\mathbf{S},\mathbf{P}\\!\\!\leftarrow\\!\\!f_{\text{object
}}(X),f_{\text{subject}}(X),f_{\text{predicate}}(X)$;

2: Extract feature embeddings
$F(\mathbf{O}),F(\mathbf{S}),F(\mathbf{B})\leftarrow\mathbf{O},\mathbf{S},\mathbf{P}$;

3: Extract (subject, object, predicate) words $Y_{s},Y_{o},Y_{p}\leftarrow Y$;

4: Compute the concept-level similarity $S_{1},S_{2},S_{3}\leftarrow
G(Y_{s}),G(Y_{o}),G(Y_{p}),F(\mathbf{O}),F(\mathbf{S}),F(\mathbf{P})$; {Eq.
(3)}

5: Extract sentence embeddings $G(Y)\leftarrow Y$;

6: Compose visual features $V\leftarrow S_{1},S_{2},S_{3}$, $f_{\text{object
}}(\cdot),f_{\text{subject}}(\cdot),f_{\text{predicate}}(\cdot),F(\cdot),X;$
{Eq. (4)}

7: Compute the matching score $O\leftarrow Y,V$

Figure 5: Design of the counterfactual subimage generation process. LLM
matches the dense captions generated by GRiT from image to parsed subjects,
objects, predicates from text. Figure 6: The causal graphs in the context of
compositional image-text matching.

##  Appendix B Counterfactual Subimage Generation

Figure 5 presents a visual guide to our subimage creation process for image-
text pairs. For instance, GRiT analyzes the image, generating detailed
captions for objects such as pizza, person, fork, and knife, along with their
spatial references. Next, LLM extracts relation triplets from sentences, like
person cutting into pizza and person with a fork. Utilizing LLM again, we
identify all captions that could pertain to an object. To illustrate, for
creating the pizza subimage, LLM recognizes that the dense caption a pizza on
a table refers to pizza, so we use the corresponding image section of this
caption. For generating the predicate cutting into subimage, we merely overlap
the subimages of person and pizza, the subject and object of cutting into
respectively.

##  Appendix C Causal Graph in the Context of Image-text Matching

We show the causal graph in the context of our image-text matching task in
Figure 6. $X$ are high-dimensional observations (i.e., images), and $Y$ are
corresponding text prompts. $X$ can be described by lower-dimensional,
semantically meaningful factors of variation $Z$ (e.g., objects, subjects, or
action relations between objects and subjects (i.e., predicates in the
image)).

##  Appendix D Implementation Details

We introduce the implementation details of ComCLIP in this section. Our
pipeline is training-free, so there are no parameters involved in ComCLIP. In
the main results of Table 2 of the main paper, we use the CLIP backbone with
ViT-L-14 as its vision encoder. The masks for subjects/objects/predicates are
generated using GRiT [44] with the dense caption version, which is pre-trained
for 200 epochs.

##  Appendix E Experimental Results on SVO-Probes over Different Splits

| Seed 42 | Seed 11 | Seed 2
---|---|---|---
Vision Encoder | CLIP | ComCLIP | CLIP | ComCLIP | CLIP | ComCLIP
ResNet-50 | 82.77 | 83.87 | 82.06 | 83.10 | 82.87 | 83.97
ViT-B-32 | 84.13 | 85.47 | 84.47 | 84.83 | 84.17 | 84.67
ViT-L-14 | 85.53 | 86.63 | 84.76 | 86.10 | 85.27 | 86.33
Table 6: Comparison of ComCLIP with CLIP under three different splits on the SVO-Probes dataset.  | Seed 42 | Seed 11 | Seed 2
---|---|---|---
Vision Encoder | SLIP | ComSLIP | SLIP | ComSLIP | SLIP | ComSLIP
SLIP (ViT-B-32) | 77.70 | 77.90 | 79.10 | 79.75 | 81.00 | 80.15
SLIP (ViT-L-14) | 78.90 | 79.70 | 79.70 | 80.15 | 80.10 | 81.30
Table 7: Effectiveness of our method using SLIP under three different splits
on the SVO-Probes dataset.

In this section, we show additional results using three different data splits
on SVO-Probes. We use random seeds $42,11,2$ to re-split the dataset, with the
results of CLIP vs. ComCLIP shown in Table 6 and the results of other CLIP-
based models shown in Table 7.

##  Appendix F Case Study: Generalized Scenario with Multiple SVO

In this section, we present the case study where the text contains multiple
SVO on Flickr30K and MSCOCO.

###  F.1 Cases Study on Flickr30K

In Figure 8, we first show the case where single SVOs are involved.

In Figure 9 and Figure 10, we show the case where multiple SVOs are involved.
Specifically, in this provided case, multiple objects (Food cart, City street)
and subjects (Several People, Food cart) are involved. Figure 9 is a positive
example, and Figure 10 is a negative example. As can be seen, ComCLIP can
utilize multiple subjects/objects/predicates in the input texts to do the
matching. The food cart object dominates the decision process and helps
ComCLIP make the correct match.

###  F.2 Case Study on MSCOCO

In Figure 11 and 12, we provide a breakdown of how ComCLIP makes the correct
decision when multiple SVOs are involved on MSCOCO. Both the negative image
from Figure 11 and the positive image from Figure 12 are closely aligned with
the text, featuring prominent visual entities such as a person and a pizza.
ComCLIP integrates various subjects, objects, and predicates, effectively
distinguishing the correct image match from a pair of visually analogous
images.

Figure 7: Comparison of accuracy (%) on SVO-Probes using parsed and ground-truth SVO triplets.  | ResNet-50 | ViT-B-32 | ViT-L-14
---|---|---|---
CLIP | 79.38 | 79,94 | 83.70
ComCLIP (Lang-Seg mask) | 82.41 | 83.15 | 86.05
ComCLIP (Lang-Seg mask with blur) | 83.27 | 83.09 | 85.31
ComCLIP (CLIPSeg mask) | 83.27 | 82.22 | 85.18
ComCLIP (CLIPSeg mask with blur) | 82.78 | 82.90 | 85.31
Table 8: Compositional Visual Genome subset accuracy (%) with masks generated
by Lang-Seg and CLIPSeg. Figure 8: The comparison of CLIP (left) and ComCLIP
(right) over the case where single subjects/objects/predicates are involved.
Image and text examples are from Flickr30K.  Figure 9: The comparison of CLIP
(left) and ComCLIP (right) over the case where multiple
subjects/objects/predicates are involved (this is a positive example from
Flickr30K).  Figure 10: The comparison of CLIP (left) and ComCLIP (right) over
the case where multiple subjects/objects/predicates are involved (this is a
negative example from Flickr30K).  Figure 11: The comparison of CLIP (left)
and ComCLIP (right) over the case where multiple subjects/objects/predicates
are involved (this is a negative example from MSCOCO).  Figure 12: The
comparison of CLIP (left) and ComCLIP (right) over the case where multiple
subjects/objects/predicates are involved (this is a positive example from
MSCOCO).

##  Appendix G Error Analysis

As shown in the main paper, we get higher improvements using ComCLIP on
Compositional Visual Genome compared with SVO-Probes. This is mainly because
our collected Compositional Visual Genome is cleaner and the SVO-Probes
dataset tends to be noisy. Herein, we give a case study covering three major
error-inducing issues found in SVO-Probes, as depicted in Figure 13: instances
where the negative image aligns with the input sentence, object mismatches,
and the presence of watermarks in images.

Figure 13: Selected bad quality examples along with reasons from the SVO-
Probes dataset. Figure 14: Example from MSCOCO dataset. Figure 15: Examples
from the SVO-Probes dataset (left two) and Compositional Visual Genome dataset
(right two). There are three negative types for a given triplet: a subject-
negative, predicate-negative, or object-negative where respectively, the
subject, predicate, or object in the triplet is replaced by a different word.
Within each image pair, the positive image on the left represents the positive
triplet, while the negative image on the right corresponds to the negative
triplet.

##  Appendix H Extracted Entities

#### Use Language Parser to Extract SVO

The performance of ComCLIP is also dependent on the quality of the subject,
object, and predicate entity provided. To study the effect of extracted
entities, we analyze our methods on SVO-Probes since it has more complex
sentence structures. Apart from the LLM approach shown in the main paper, we
remove stop words from the sentence using NLTK [25] and then use a Subject
Verb Object extractor developed based on [12] to extract the subject,
predicate, and object from the original sentence. Figure 7 shows that our
parsed entities have almost the same performance as that using the ground
truth subjects, predicates, and objects.

##  Appendix I Robustness of Counterfactual Subimage Generator

To show the robustness of using GRiT [44] to generate counterfactual
subimages, we quote the results and conclusions from [44]. According to [44],
GRiT is comparable to the closed-set object detector with a 0.8 AP gap. This
result demonstrates GRiT’s open-set framework can serve as a new promising
formulation for object detection. GRiT also performs comparably with the
state-of-the-art closed-set object detectors. This once again demonstrates
GRiT can serve as the subimage generator in our pipeline.

##  Appendix J Additional Ablations on Counterfactual Subimage Generation

In this section, we show that ComCLIP is robust to the choice of
counterfactual subimage generator. We use segmentation models, Lang-Seg and
CLIPSeg [28] with the clipseg-rd64-refined version, to create segmentation
masks and generate subimages. Specifically, given the input (subject, object,
predicate) triplet, we model the object mechanism $f_{\text{object }}$ using a
binary mask generated by Lang-Seg and CLIPSeg, which are both CLIP-based
language-guided segmentation models. Given the segmentation results, the
object part will be set to $1$ while the remainder of the image is $0$. In a
manner similar to the object mechanism, the subject mechanism
$f_{\text{subject}}$ is achieved by setting the background to $0$ while the
subject region is set to $1$. The predicate mechanism $f_{\text{predicate}}$
is implemented by combining the binary mask generated by $f_{\text{object }}$
and $f_{\text{subject}}$ together: the object and subject regions will be $1$
while the remaining regions will be $0$.

We test the masks on a randomly selected 30% subset of Compositional Visual
Genome. The results in Table 8 indicate that ComCLIP continues to outperform
CLIP across all vision encoders when the masks are generated by CLIPSeg. To
further test its robustness, we add noise by applying Gaussian image blur to
the backgrounds of generated subimages rather than using pure black
backgrounds. Despite the blurring, ComCLIP using either Lang-Seg or CLIPSeg
masks still performs better than CLIP and achieves similar performance to
ComCLIP without blur as shown in Table 8. Thus, ComCLIP is shown to be
resilient to the precision of generated subimages.

##  Appendix K Data Examples from MSCOCO

In this section, we provide an example from the MSCOCO dataset that we
constructed, as shown in Figure 14. The MSCOCO dataset typically incorporates
adjectives to enhance query sentences, which CLIP tends to overlook. For
instance, in the provided example, the orange road sign helps ComCLIP
successfully identify the accurate image as the best match, while CLIP does
not rank it among the top 5 matches.

##  Appendix L Data Examples from Compositional Visual Genome and SVO-Probes

In this section, we show examples from the Compositional Visual Genome dataset
constructed by us and the SVO-Probes in Figure 15. As can be seen, they are
formatted similarly: Negative Types — Sentence — SVO Triplet — Positive Image
— Negative Image.

##  Appendix M Compared with Finetuned CLIP on Visual Genome

To further evaluate the effectiveness of our method, we compare ComCLIP with
finetuned CLIP utilizing the abundant relations from the entire Visual Genome
dataset. Excluding the images that occurred in our Compositional Visual
Genome, there are 1,129,818 image-text pairs left, and we randomly took 56,490
such pairs to finetune the CLIP. We follow the settings in [18] and [10],
where we use AdamW [26] optimizer with a learning rate of $0.003$ and weight
decay of $0.05$. The detailed experimental settings for finetuning CLIP are
shown in Table 9. We then evaluate the result on Compositional Visual Genome
and compare it with ComCLIP, with results shown in Table 10. Unexpectedly,
finetuned CLIP performs worse than zero-shot CLIP by a large margin,
suggesting that CLIP may further learn spurious relations during finetuning as
the training set can be biased. This further demonstrates the superiority of
our method, which is training-free, effective, and can mitigate the effect of
spurious correlations. Moreover, there is no need to perform hyper-parameter
tuning.

Name | Value
---|---
Optimizer | AdamW
Learning rate | 0.003
Weight decay | 0.05
Max epoch | 10
Batch size | 10
Table 9: Hyperparameter settings for finetuning CLIP.

Vision Encoder | CLIP | Finetuned CLIP | ComCLIP
---|---|---|---
ResNet-50 | 82.25 | 76.43 | 83.73

Table 10: Comparative analysis using ComCLIP and finetuning CLIP. ComCLIP
outperforms finetuned CLIP, proving its capacity to mitigate the effect of
spurious correlations from finetuning, apart from pretraining.


11institutetext: Department of Informatics, Bioengineering, Robotics, and
Systems Engineering, University of Genoa, Via All’Opera Pia 13, 16145, Genoa,
Italy.
11email<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
# Revisiting the Minimum Constraint Removal Problem in Mobile Robotics

Antony Thomas  Fulvio Mastrogiovanni  Marco Baglietto

###### Abstract

The minimum constraint removal problem seeks to find the minimum number of
constraints, i.e., obstacles, that need to be removed to connect a start to a
goal location with a collision-free path. This problem is NP-hard and has been
studied in robotics, wireless sensing, and computational geometry. This work
contributes to the existing literature by presenting and discussing two
results. The first result shows that the minimum constraint removal is NP-hard
for simply connected obstacles where each obstacle intersects a constant
number of other obstacles. The second result demonstrates that for $n$ simply
connected obstacles in the plane, instances of the minimum constraint removal
problem with minimum removable obstacles lower than $(n+1)/3$ can be solved in
polynomial time. This result is also empirically validated using several
instances of randomly sampled axis-parallel rectangles.

##  1 Introduction

The classical robot motion planning problem seeks to find a collision-free
path from a start location to a goal location in the presence of fixed
obstacles. However, in many situations, a collision-free path may not exist,
but obstacles could be moved. For example, in a typical in-home setting,
obstacles could correspond to chairs that could be re-positioned to allow for
a feasible path, or they could be objects located inside a kitchen shelf that
could be rearranged to reach a desired object. If no collision-free path
exists, and if we allow for paths to intersect (collide with) obstacles, then
one may naturally ask what is the minimum number of obstacles that are to be
removed so that there exists a collision-free path from start to goal. This
problem, introduced by Hauser [14] is called the Minimum Constraint Removal
(MCR) problem, and it is related to finding the fewest constraints (obstacles)
that must be removed from the environment to connect a start and a goal
location with a free path.

Hauser showed that MCR is NP-hard by reduction from the SET-COVER problem.
Erickson and Lavalle [10] performed a reduction from the maximum
satisfiability problem for binary Horn clauses, proving that MCR is NP-hard
for convex polygonal obstacles. The problem is also NP-hard when the obstacles
are line-segments [1, 31]. As a result, approximate solutions are often sought
after [19]. Bandyapadhyay et al. [2] showed that there exists an $O(\sqrt{n})$
approximation for rectilinear polygons and disks (with $n$ denoting the number
of polygons or disks). MCR as translatd to computing the minimum color in an
edge-colored graph is shown to have an $O(n^{2/3})$ polynomial time
approximate algorithmic solution [20], where $n$ denotes the vertices on the
translated graph.

Minimum constraint removal has also been studied under the name barrier
resilience by those who work in sensor networks [21, 4, 5]. This problem
considers an arrangement of different regions in a 2D plane, where each region
represents the detection region of a sensor. Given a start and a goal point,
the resilience of the network is then measured by the minimum number of
distinct sensor detection regions intersected, that is the minimum number of
sensors that need to fail to create a sensor-avoiding path. Chan and
Kirkpatrick [5] reduce the barrier resilience problem to the minimum-color
path problem [32], and compute a $1.5$-approximation for unit disks (sensor
regions) which is an improvement over the $2$-approximation developed in [4].
The problem is also shown to be NP-hard even for axis-aligned rectangles with
an aspect ratio close to one [17].

In this paper, we demonstrate the following:

  1. 1.

MCR is NP-hard for simply connected obstacles, where each obstacle intersects
a constant number of other obstacles. Such a claim addresses an open question
presented in [14] — Is MCR in P on problems in which each obstacle is
connected and intersects no more than $k$ obstacles, with $k$ held constant?

  2. 2.

For $n$ simply connected obstacles in the plane, instances of MCR with minimum
removable obstacles lower than $(n+1)/3$ can be solved in polynomial time.

The result in (1) also augments the findings presented in [8], wherein MCR
with each obstacle intersecting a constant number of other obstacles is shown
to run in $2^{O(\sqrt{N})}$, where $N$ is the number of regions formed by the
intersections of the $n$ obstacles ($N=O(n^{2})$). The existence of a sub-
exponential time (in $N$) algorithm is proved by considering line segments as
obstacles and performing a reduction from the MAXIMUM NEGATIVE
2-SATISFIABILITY problem which is NP-hard. In contrast, we provide general
proof for simply connected obstacles by considering different paths induced by
the intersecting obstacles.

If it is known beforehand that the optimal solution to MCR, which we refer to
as $S^{\star}$, is lower than $(n+1)/3$, that is, $|S^{\star}|<(n+1)/3$, the
result in (2) implies that an exact algorithm could be accorded more priority
than an approximate one. Proof and further discussions on this result are
provided in Section 4.

##  2 Related Work

Minimum constraint removal is closely related to different areas of research
within the robotics literature. MCR finds the minimal set of obstacles that
render motion planning infeasible. Disconnection proving or infeasibility
proofs in motion planning [3, 33, 22] that guarantee that no path can be found
is thus a related class of problem. Another closely related line of work is
the Minimum Constraint Displacement (MCD) motion planning [13, 28, 27]. While
MCR identifies the minimum number of obstacles that must be removed to yield a
feasible path, MCD computes the minimum amount by which obstacles must be
displaced to enable a feasible motion plan.

In Navigation Among Movable Obstacles (NAMO) [25, 23, 30] class of problems, a
robot manipulates different objects in the plane to create space for its
motion. However, such approaches could move many objects (not necessarily the
minimal set) and the corresponding displacements may be arbitrary. Another
related area is the field of task and motion planning [15, 24, 6, 11, 29]. In
such domains, additional symbolic actions are generated to ensure motion
planning feasibility of the required task. Manipulation among clutter or
rearrangement planning in clutter [26, 7, 18, 16] also pose related challenges
since this requires moving aside a set of obstacle (obstacles that hinder the
task) or placing them at selected locations.

##  3 Hardness Result for Fixed Obstacle Intersections

In this Section, we prove that instances of MCR where each obstacle intersects
up to a fixed number of other obstacles are NP-hard.

It is well known that MCR problems can be converted to a graph search problem
[10, 14, 12, 9]. To attain this transformation, the configuration space is
partitioned along the obstacle boundaries, and a graph is constructed such
that the vertices are the faces of the obstacle arrangements and the edges
connect neighboring faces. The start $s$ and goal $g$ locations are augmented
by adding the appropriate edges to obtain a graph $G=(V,E)$, where $V$ is the
set of vertices, and $E$ is a collection of pairs of vertices
$(v,v^{\prime})$, where $v\neq v^{\prime}$, or edges. An example is given in
Fig. 1. It is noteworthy that when the obstacles do not intersect each other,
then each vertex $v\in V$ corresponds to a single obstacle, and any path
passing through $k$ such vertices implies that the $k$ corresponding obstacles
must be removed to obtain a feasible path111MCR with disjoint and simply
connected obstacles is in P [14].. When obstacles are allowed to intersect,
each vertex could correspond to more than one obstacle. For each vertex $v$,
we thus define the intersection function $I(v)$ as the set of intersecting
obstacles that are represented by the vertex, that is, a path $P_{G}$ induced
on $G$ that passes through vertex $v$ intersects all the obstacles in $I(v)$.
Consequently, for a path $P$ in the configuration space from $s$ to $g$ to be
feasible, the union of intersection functions for all vertices $v$ lying on
$P_{G}$ need to be computed. This gives the set of obstacles that should be
moved to make the path $P$ feasible, and it will be called the removable set
$R_{P}$ for the path $P$. Similarly, the removable set of a path $P$ from $s$
to a generic vertex $v$ can be denoted as $R_{P}(v)$222In the following, we
will omit the subscript $P$ because the reference to a specific path $P$ will
be implicit..

(a)

$s$$1$$2$$2,4$$4$$1,2$$2$$1$$3$$3,4$$3$$1,3$$1$$g$

(b)

Figure 1:  (a) An instance of MCR with 4 obstacles. Start and goal locations
are shown in green and red, respectively. (b) The MCR problem transformed into
a graph. Vertices represent obstacle sets (obstacle numbers inside the nodes)
that form 2D connected regions based on the partition along obstacle
boundaries.

Given a vertex $v$, a path $P$, and the corresponding path on a graph $P_{G}$,
MCR on a graph can be solved exactly by expanding the graph in the increasing
order of the cardinality $|R(v)|$ of the removable set. To this end, each
state is encoded as a pair $(v,R(v))$, representing the vertex and the
corresponding removable set. This approach is complete and optimal [14]. When
the obstacles are disjoint and simply connected, the exact search corresponds
to finding the shortest path on a graph with a unit cost associated with each
vertex. In this case, we can compute the minimum $|R(v)|$ path by employing
the Dijkstra’s algorithm. However, when the obstacles are overlapping, paths
could enter as well as exit an obstacle more than once. This makes the
removable set $R(v)$ path-dependent since an obstacle could potentially belong
to the intersection function $I(v)$ of all the vertices, causing NP-hardness.

Let us now consider the case in which each obstacle is allowed to intersect up
to $k$ other obstacles so that we have $k+1$ intersecting obstacles. Let the
graph search be at a vertex $v^{\prime}$ with a corresponding removable set
$R(v^{\prime})$. For any $v$ adjacent to $v^{\prime}$ with $c=|I(v)|$, $1\leq
c\leq k+1$, the removable set $R(v)=R(v^{\prime})\cup I(v)$. Clearly, it holds
that $|R(v^{\prime})|\leq|R(v)|\leq|R(v^{\prime})|+c$. This is due to the fact
that $R(v)$ depends on the path history, that is the vertices encountered
while reaching $v$. In order to make this more explicit, let us assume
$I(v)=\\{o_{1},\ldots,o_{k}\\}$. If $R(v^{\prime})\cap I(v)=\\{\emptyset\\}$,
the path from start to $v^{\prime}$ has not encountered any of the obstacles
contributing to $v$, and therefore $|R(v)|=|R(v^{\prime})|+k+1$. However, if
$R(v^{\prime})\cap I(v)\neq\\{\emptyset\\}$, then the path from start to
$v^{\prime}$ did encounter some (or all) of the obstacles in $I(v)$, and it
holds that $|R(v)|<|R(v^{\prime})|+k+1$. This can be easily visualized in Fig.
1b. If we let $I(v)=\\{o_{1},o_{3}\\}$, and if $I(v)\subseteq R(v^{\prime})$,
then $R(v)=R(v^{\prime})$. If either $o_{1}\in R(v^{\prime})$ or $o_{3}\in
R(v^{\prime})$, we then have $|R(v)|=|R(v^{\prime})|+1$. Finally, if neither
$o_{1}\not\in R(v^{\prime})$ nor $o_{3}\not\in R(v^{\prime})$, we have that
$|R(v)|=|R(v^{\prime})|+2$.

As pointed out before, MCR can be solved exactly by expanding the
corresponding graph in the increasing order of the cardinalities $|R(v)|$.
However, as argued above, $R(v)$ is path-dependent. This means that at each
node $v$, $|R(v)\backslash R(v^{\prime})|$ could take different values
depending on whether obstacles in $I(v)$ previously appeared on the path till
reaching $v$. In other words, the state $(v,R(v))$ could be reached by many
paths.

###### Lemma 1

If each obstacle is simply connected and intersects no more than $k$
obstacles, a vertex $v$ with $|I(v)|=k+1$ and a removable set $R(v)$ could
possibly be reached by $2^{k+1}$ different paths.

###### Proof

Let us assume that the graph search is currently at a vertex $v^{\prime}$ with
a removable set $R(v^{\prime})$. For any $v$ adjacent to $v^{\prime}$ with
$I(v)=k+1$, it can be inferred that

  * •

if any one element of $I(v)$ belongs to $R(v^{\prime})$, then
$|R(v)|=|R(v^{\prime})|+k$, which is possible in $\binom{k+1}{1}$ ways;

  * •

if any two elements of $I(v)$ belong to $R(v^{\prime})$, then
$|R(v)|=|R(v^{\prime})|+k-1$, which is possible in $\binom{k+1}{2}$ ways;
$\vdots$

  * •

if any $k$ elements of $I(v)$ belong to $R(v^{\prime})$, then
$|R(v)|=|R(v^{\prime})|+1$, which is possible in $\binom{k+1}{k}$ ways.

Finally, it holds that $|R(v)|=|R(v^{\prime})|+k+1$ if $I(v)\nsubseteq
R(v^{\prime})$, and $R(v)=R(v^{\prime})$ if $I(v)\subseteq R(v^{\prime})$,
which could be mapped to $\binom{k+1}{0}$ and $\binom{k+1}{k+1}$,
respectively.

If we add all the quantities above, we obtain the different possible paths to
arrive at $(v,R(v))$. An exact expression can be obtained using the binomial
sum $\sum_{i=0}^{k+1}\binom{k+1}{i}=2^{k+1}$. Therefore, the state $(v,R(v))$
could potentially be reached via $2^{k+1}$ different paths.

We will now prove that MCR with simply connected obstacles with no more than
$k+1$ obstacle intersections cannot be solved in polynomial time.

###### Theorem 3.1

MCR with simply connected obstacles such that each obstacle intersects no more
than $k$ obstacles, with $k$ held constant, cannot be solved in polynomial
time.

###### Proof

Let there be $n$ movable obstacles such that each obstacle is simply connected
and intersects no more than $k$ obstacles. Since there are $2^{n}$ possible
subsets of obstacles, each vertex could appear in $2^{n}$ search states. From
Lemma 1, we know that a vertex $v$ with a given subset of obstacles (removable
set $R(v)$) could be reached via $2^{k+1}$ possible paths. Therefore, each
vertex could potentially appear in $2^{n+k+1}$ search states. Consequently, in
the worst case, the exact search generates $O(|E|2^{n+k+1})$ search states.
Therefore, MCR with simply connected obstacles such that each obstacle
intersects no more than $k$ obstacles cannot be solved in polynomial time.

##  4 A Sub-class in P

###  4.1 Considered Sub-classes

Though exact MCR via graph search is worst-case exponential time, one may ask
if there exist sub-classes of MCR problems that are solvable in polynomial
time. In this Section, we study one such sub-class.

For an instance of MCR, let us consider the minimum set of obstacles
$S^{\star}$ that must be removed to obtain a feasible path, that is the
optimal solution. As seen before, the NP-hardness of MCR is caused by
overlapping obstacles since they make $R(v)$ path-dependent333Exact MCR using
best-first search for non-overlapping and simply connected obstacles could
still generate $O(|E|2^{n})$ states. However, for such sub-classes, a greedy
search (running in $O(|E|n)$) generates an optimal solution [14].. We have
also seen that the worst-case exponential complexity is attributed to the
different possible combinations of obstacle sets. Since the exact search
proceeds in the order of increasing cardinality $|R(v)|$, a natural question
arises: does there exist a fixed $\alpha\leq n$ such that for all instances of
MCR with $|S^{\star}|<\alpha$, an optimal solution can be found in polynomial
time?

###### Lemma 2

The binomial sum of the first $k$ terms has an upper bound given by

$\sum_{i=0}^{k}\binom{n}{i}\leq 2\binom{n}{k}.$ (1)

whenever $k<\frac{n+1}{3}$.

###### Proof

For $k<\frac{n+1}{3}$, we have

$\binom{n}{i}=\frac{n-i+1}{i}\binom{n}{i-1}\geq 2\binom{n}{i-1}.$ (2)

Furthermore, we have

$\sum_{i=1}^{k}\binom{n}{i}\geq
2\sum_{i=1}^{k}\binom{n}{i-1}\implies\binom{n}{k}\geq\binom{n}{0}+\sum_{i=0}^{k-1}\binom{n}{i}.$
(3)

Adding $\binom{n}{k}$ to both the sides of the inequality, we get

$2\binom{n}{k}\geq\binom{n}{0}+\sum_{i=0}^{k}\binom{n}{i}\implies\sum_{i=0}^{k}\binom{n}{i}\leq
2\binom{n}{k}.$ (4)

In general, given an upper bound $\alpha$ on the number of obstacles that may
need to be removed, we can safely prune the vertices $|I(v)|>\alpha$, since
$|S^{\star}|\leq\alpha$. We thus get a reduced graph $G^{\prime}$. Similarly,
for the MCR search on $G^{\prime}$, states $(v,R(v))$ with $|R(v)|>\alpha$ can
also be pruned since such states do not affect the solution as
$|S^{\star}|\leq\alpha$. Furthermore, a vertex could be reached via many paths
and hence could produce different states. Therefore, a state $(v,R(v))$ can be
pruned if during the search the vertex was previously reached by a state
$(v,R^{\prime}(v))$ such that $R(v)\supseteq R^{\prime}(v)$. Thus, given an
$\alpha$ and states pruned as argued above, the search generates
$O\left(\sum_{i=0}^{\alpha}\binom{n}{i}\right)$ states.

###### Theorem 4.1

Instances of MCR for simply connected obstacles in the plane with
$|S^{\star}|<\alpha$, where $\alpha=(n+1)/3$, can be solved in polynomial
time.

###### Proof

For any $\alpha<(n+1)/3$, the exact search generates $O(n^{\alpha})$ states.
This directly follows from our arguments above on pruning sub-optimal states
and using Lemma 2. Thus, MCR with $|S^{\star}|<(n+1)/3$ is in $P$.

Figure 2: Running times plotted against the MCR solution (cardinality of
$S^{\star}$) for different instances of 100 randomly sampled axis-parallel
rectangles.

###  4.2 Empirical Validation

In order to validate our claim, we employ the exact search on different
instances of MCR, in which the obstacles are axis-parallel rectangles. To
simulate different MCR instances, we consider a $30\times 30$ grid, and
randomly sample $n$ points with each sampled point corresponding to an
obstacle. For each sampled point we then randomly sample its length and
breadth. Finally, for each instance, the start and goal locations are randomly
chosen from the grid points. The tests are performed on an Intel® Core
i7-10510U<EMAIL_ADDRESS>with 16GB RAM under Ubuntu 18.04 LTS. Fig. 2
shows running times for the exact search on the $30\times 30$ grid with $100$
obstacles. The red vertical line corresponds to $\alpha=(n+1)/3$. For
$|S^{\star}|>(n+1)/3$, as the distance between the points and the $\alpha$
line increases, the exact search quickly becomes infeasible, requiring several
hours to compute the optimal solution. It should be noted that the
computational performance is greatly affected by the number of obstacle
overlaps (obstacle distribution), as we have shown in the previous section.
This justifies the non-monotonic relationship between MCR solution instances
and their corresponding computational times.

###  4.3 Computing an Upper Bound for $|S^{\star}|$

Figure 3:  A 6-obstacle solution
($S=\\{o_{1},o_{2},o_{3},o_{4},o_{5},o_{7}\\}$) is returned when a minimum
weight path is computed with each vertex assigned a weight equal to its
intersection function. The optimal solution
$S^{\star}=\\{o_{1},o_{3},o_{7}\\}$ is obtained by removing $3$ obstacles.

An implication of the result in Theorem 4.1 is that if we know that the
inequality $|S^{\star}|<(n+1)/3$ holds, then the exact graph search approach
can be employed. Such knowledge could be obtained by determining a tight upper
bound (or one must hope for the existence of an oracle). One straightforward
approach is to solve a weighted graph with each vertex $v$ assigned a weight
of $|I(v)|$. It is noteworthy that if the colors repeat no more than $p$
times, the minimum weight path (say, using Dijkstra’s algorithm) gives a
$p-$approximate solution, where $p=\Theta(n)$. Fig. 3 shows an example in
which the minimum weight path is
$S=\\{o_{1},o_{2},o_{3},o_{4},o_{5},o_{7}\\}$. However the optimal MCR
solution is $S^{\star}=\\{o_{1},o_{3},o_{7}\\}$. An upper bound is also easily
obtained by assigning unit weight to all the vertices. This approach could
achieve an $O(n)$ error and one such instance is displayed in Fig. 4a.

Another natural approach is to employ the greedy search, whereby at each $v$
the minimum $|R(v)|$ subset would be expanded, and the remaining states with
$|R^{\prime}(v)|\geq|R(v)|$ would be pruned, which runs in $O(n)$ time.
However, the greedy search has worst-case $O(n)$ error. An example is shown in
Fig. 4b.

(a)

(b)

Figure 4:  (a) The optimal solution is $S^{\star}=\\{o_{1},o_{2}\\}$.
Assigning equal weights to each vertex, we have a sub-optimal path with
$S=\\{o_{3},\ldots,o_{7}\\}$. (b) An example with five rectangular obstacles
$o_{1},\ldots,o_{5}$, and an L-shaped obstacle $o_{6}$ in the plane. The exact
search gives $S^{\star}=\\{o_{1},o_{6}\\}$ but the greedy search returns
$S=\\{o_{2},o_{3},o_{4},o_{5},o_{6}\\}$.

Though instances achieving a tight upper bound can be easily synthesized, in
general, the approaches discussed above compute conservative upper bounds. As
seen in Fig. 4, even when the obstacles are axis-parallel rectangles, an
$O(n)$ error is achieved. A $1.5$-approximation for unit disks is known due to
Chan and Kirkpatrick [5]. Do tighter bounds exist for different sub-classes?
Do polynomial-time algorithms exist for MCR that give an
$\epsilon$-approximation ($\epsilon>0$ and $\epsilon\to 0$)? We leave them as
open theoretical questions.

##  5 Conclusion

We have shown that MCR is NP-hard for instances in which no obstacle
intersects more than a constant number of other obstacles. This answers an
open question posed in [14] on whether MCR is in $P$ on problems in which each
obstacle is connected and intersects no more than $k$ obstacles. The
tractability of such instances is also questioned in [10] wherein the authors
state without proof that the problem is trivial when the obstacles are allowed
to intersect only pairwise. Eiben et al. [8] showed that instances in which no
more than two obstacles overlap at the same point cannot be solved in time
$2^{o(\sqrt{N})}$, where $N=O(n^{2})$ and $n$ denotes the number of obstacles
in the plane. Instances restricted to the pairwise intersection are a sub-
class of the 2-obstacle overlap MCR. This suggests a future line of study: is
MCR in $P$ for instances with only $k-$wise allowed intersections, that is
only groups of $k$ obstacles allowed to intersect, and $k$ held fixed?

We have also shown that for $n$ simply connected obstacles in the plane,
instances of MCR with $|S^{\star}|<(n+1)/3$ can be solved in polynomial time.
A consequence of these results is that the exact graph search could be
employed if it is known beforehand that $|S^{\star}|<(n+1)/3$ holds. However,
algorithms that compute tight bounds are currently unknown. The existence of
polynomial time algorithms for MCR computing tight upper bounds is left as an
open theoretical question.

## References

  * [1] Alt, H., Cabello, S., Giannopoulos, P., Knauer, C.: On some connection problems in straight-line segment arrangements. 27th EuroCG pp. 27–30 (2011)
  * [2] Bandyapadhyay, S., Kumar, N., Suri, S., Varadarajan, K.: Improved approximation bounds for the minimum constraint removal problem. Computational Geometry 90, 101650 (2020)
  * [3] Basch, J., Guibas, L.J., Hsu, D., Nguyen, A.T.: Disconnection proofs for motion planning. In: Proceedings 2001 ICRA. IEEE International Conference on Robotics and Automation (Cat. No. 01CH37164). vol. 2, pp. 1765–1772. IEEE (2001)
  * [4] Bereg, S., Kirkpatrick, D.: Approximating barrier resilience in wireless sensor networks. In: Algorithmic Aspects of Wireless Sensor Networks: 5th International Workshop, ALGOSENSORS 2009, Rhodes, Greece, July 10-11, 2009. Revised Selected Papers 5. pp. 29–40. Springer (2009)
  * [5] Chan, D.Y.C., Kirkpatrick, D.: Multi-path algorithms for minimum-colour path problems with applications to approximating barrier resilience. Theoretical Computer Science 553, 74–90 (2014)
  * [6] Dantam, N.T., Kingston, Z.K., Chaudhuri, S., Kavraki, L.E.: Incremental Task and Motion Planning: A Constraint-Based Approach. In: Proceedings of Robotics: Science and Systems XII. AnnArbor, Michigan (June 2016)
  * [7] Dogar, M., Srinivasa, S.: A framework for push-grasping in clutter. In: Hugh Durrant-Whyte, N.R., Abbeel, P. (eds.) Proceedings of Robotics: Science and Systems VII. MIT Press, Los Angeles, CA, USA (June 2011)
  * [8] Eiben, E., Gemmell, J., Kanj, I., Youngdahl, A.: Improved results for minimum constraint removal. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 32 (2018)
  * [9] Eiben, E., Kanj, I.: How to Navigate Through Obstacles? In: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), vol. 107, pp. 48:1–48:13. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2018), http://drops.dagstuhl.de/opus/volltexte/2018/9052
  * [10] Erickson, L.H., LaValle, S.M.: A simple, but np-hard, motion planning problem. In: Twenty-Seventh AAAI Conference on Artificial Intelligence (2013)
  * [11] Garrett, C.R., Lozano-Perez, T., Kaelbling, L.P.: FFRob: Leveraging symbolic planning for efficient task and motion planning. The International Journal of Robotics Research 37(1), 104–136 (2018)
  * [12] Gorbenko, A., Popov, V.: The discrete minimum constraint removal motion planning problem. In: Proceedings of the American Institute of Physics. vol. 1648, p. 850043. AIP Publishing LLC (2015)
  * [13] Hauser, K.: Minimum constraint displacement motion planning. In: Proceedings of Robotics: Science and Systems IX. Berlin, Germany (June 2013)
  * [14] Hauser, K.: The minimum constraint removal problem with three robotics applications. The International Journal of Robotics Research 33(1), 5–17 (2014)
  * [15] Kaelbling, L.P., Lozano-Pérez, T.: Integrated task and motion planning in belief space. The International Journal of Robotics Research 32(9-10), 1194–1227 (2013)
  * [16] Karami, H., Thomas, A., Mastrogiovanni, F.: Task Allocation for Multi-robot Task and Motion Planning: A Case for Object Picking in Cluttered Workspaces. In: AIxIA 2021 – Advances in Artificial Intelligence. pp. 3–17. Springer International Publishing, Cham (2022)
  * [17] Korman, M., Löffler, M., Silveira, R.I., Strash, D.: On the complexity of barrier resilience for fat regions and bounded ply. Computational Geometry 72, 34–51 (2018)
  * [18] Krontiris, A., Bekris, K.E.: Dealing with Difficult Instances of Object Rearrangement. In: Proceedings of Robotics: Science and Systems XI. Rome, Italy (July 2015)
  * [19] Krontiris, A., Bekris, K.E.: Trade-off in the computation of minimum constraint removal paths for manipulation planning. Advanced robotics 31(23-24), 1313–1324 (2017)
  * [20] Kumar, N.: Computing a minimum color path in edge-colored graphs. In: Analysis of Experimental Algorithms: Special Event, SEA2 2019, Kalamata, Greece, June 24-29, 2019, Revised Selected Papers, pp. 35–50. Springer (2019)
  * [21] Kumar, S., Lai, T.H., Arora, A.: Barrier coverage with wireless sensors. In: Proceedings of the 11th annual international conference on Mobile computing and networking. pp. 284–298 (2005)
  * [22] Li, S., Dantam, N.T.: Learning proofs of motion planning infeasibility. In: Robotics: Science and Systems (2021)
  * [23] Nieuwenhuisen, D., van der Stappen, A.F., Overmars, M.H.: An effective framework for path planning amidst movable obstacles. In: Algorithmic Foundation of Robotics VII, pp. 87–102. Springer (2008)
  * [24] Srivastava, S., Fang, E., Riano, L., Chitnis, R., Russell, S., Abbeel, P.: Combined task and motion planning through an extensible planner-independent interface layer. In: Robotics and Automation (ICRA), IEEE International Conference on. pp. 639–646. IEEE (2014)
  * [25] Stilman, M., Kuffner, J.J.: Navigation among movable obstacles: Real-time reasoning in complex environments. International Journal of Humanoid Robotics 2(04), 479–503 (2005)
  * [26] Stilman, M., Schamburek, J.U., Kuffner, J., Asfour, T.: Manipulation planning among movable obstacles. In: Proceedings 2007 IEEE international conference on robotics and automation. pp. 3327–3332. IEEE (2007)
  * [27] Thomas, A., Ferro, G., Mastrogiovanni, F., Robba, M.: Computational Tradeoff in Minimum Obstacle Displacement Planning for Robot Navigation. In: IEEE International Conference on Robotics and Automation (ICRA) (2023)
  * [28] Thomas, A., Mastrogiovanni, F.: Minimum Displacement Motion Planning for Movable Obstacles. In: Intelligent Autonomous Systems 17. pp. 155–166. Springer Nature Switzerland, Cham (2023)
  * [29] Thomas, A., Mastrogiovanni, F., Baglietto, M.: MPTP: Motion-planning-aware task planning for navigation in belief space. Robotics and Autonomous Systems 141, 103786 (2021), https://www.sciencedirect.com/science/article/pii/S0921889021000713
  * [30] Van Den Berg, J., Stilman, M., Kuffner, J., Lin, M., Manocha, D.: Path planning among movable obstacles: a probabilistically complete approach. In: Workshop on the Algorithmic Foundations of Robotics VIII, WAFR, Guanajuato, Mexico. pp. 599–614. Springer (2009)
  * [31] Yang, S.: Some Path Planning Algorithms in Computational Geometry and Air Traffic Management. Ph.D. thesis, State University of New York at Stony Brook (2012)
  * [32] Yuan, S., Varma, S., Jue, J.P.: Minimum-color path problems for reliability in mesh networks. In: Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies. vol. 4, pp. 2658–2669. IEEE (2005)
  * [33] Zhang, L., Kim, Y.J., Manocha, D.: A simple path non-existence algorithm using c-obstacle query. In: Algorithmic Foundation of Robotics VII, pp. 269–284. Springer (2008)