# ObjectCarver: Semi-automatic segmentation, reconstruction and
separation of 3D objects

Gemmechu Hassena, Jonathan Moon, Ryan Fujii, Andrew Yuen,
Noah Snavely, Steve Marschner, Bharath Hariharan
Cornell University

###### Abstract

Implicit neural fields have made remarkable progress in reconstructing 3D
surfaces from multiple images; however, they encounter challenges when it
comes to separating individual objects within a scene. Previous work has
attempted to tackle this problem by introducing a framework to train separate
signed distance fields (SDFs) simultaneously for each of N objects and using a
regularization term to prevent objects from overlapping. However, all of these
methods require segmentation masks to be provided, which are not always
readily available. We introduce our method, ObjectCarver, to tackle the
problem of object separation from just click input in a single view. Given
posed multi-view images and a set of user-input clicks to prompt segmentation
of the individual objects, our method decomposes the scene into separate
objects and reconstructs a high-quality 3D surface for each one. We introduce
a loss function that prevents floaters and avoids inappropriate carving-out
due to occlusion. In addition, we introduce a novel scene initialization
method that significantly speeds up the process while preserving geometric
details compared to previous approaches. Despite requiring neither ground
truth masks nor monocular cues, our method outperforms baselines both
qualitatively and quantitatively. In addition, we introduce a new benchmark
dataset for evaluation.

##  1 Introduction

With recent advances in neural implicit scene representations, we can now
reconstruct 3D scenes with complete, high-quality surfaces (represented as
signed distance functions or SDFs) from a set of images taken by cameras with
known poses [29, 35]. Although these techniques compute high-quality surfaces,
they are limited to representing the entire scene as a single surface. This
representation is fine for applications such as walkthroughs where the scene
remains fixed, but for many applications it is desirable to extract and
manipulate individual objects, including applications in robotics and virtual
reality where simulating such scene manipulations is crucial. In this paper,
we tackle this problem of 3D scene decomposition: given multiple views of a 3D
scene, can we produce a reconstruction where the individual objects are
separated out?

Some previous works [33, 30, 31, 13] have addressed the problem of
reconstructing many separate objects. However, two key challenges remain.
First, these techniques require segmentation masks of each object in each view
as part of the input. Unfortunately, the cost of the manual work involved in
producing such segmentations scales with the number of input views and the
number of objects, making the process cumbersome. Automated solutions like the
Segment Anything Model (SAM) [10] often over-segment and result in
inconsistent segmentation across multiview images (Fig. 1, left). Recent
works, such as SA3D [7], that attempt this problem use volume density, but our
method uses SDF, where we know exactly where the surface lies.

Figure 1: Failure cases of SOTA. Using SAM independently on each image
precludes corresponding objects between views (Left). Even if one were to
solve this correspondence problem, slight errors in SAM output mean that the
same object may be segmented differently in the different views (e.g., the top
of the vase is included in the vase segment in the left image but not the
right). Even with good segmentations, prior work such as ObjectSDF++ [31]
introduces floating artifacts, especially those hidden behind other objects
(Right).

Second, prior work fails in the presence of occlusion (Fig. 1, right). Parts
of the scene that are occluded from all views provide no supervision for
existing techniques, giving the model free rein to introduce floating
components in the occluded regions. These floating artifacts can be large and
numerous and as such result in extremely inaccurate object reconstructions.

We introduce ObjectCarver to address these limitations. ObjectCarver takes as
input a collection of posed images and point clicks of each object for
segmentation in just _one_ of the views. This first segmentation can be
performed with tools like SAM [9]. ObjectCarver then outputs object
segmentations for all input views and a high-fidelity 3D surface for each
object (Figure LABEL:fig:intro). This 3D surface includes not just the parts
of the object that are visible but also makes reasonable completions in
completely occluded regions where no image evidence is available. Crucially,
ObjectCarver removes almost all floating artifacts that plague prior work.
Finally, ObjectCarver achieves this reconstruction with a fairly small
computational overhead beyond the computational cost of full scene
reconstruction.

ObjectCarver works in three phases. First, we reconstruct the entire 3D scene
as a single SDF using existing methods [29]. Then, from one segmentation mask
(computed from the user’s input click using SAM [10]), we use the
reconstructed 3D surface together with SAM [9] to propagate segmentation
labels to the other input images, resulting in accurate and multi-view
consistent masks for each object. Finally, we jointly train per-object SDF
surfaces, starting from the full-scene SDF. We introduce a novel loss function
to produce a set of consistent and compact 3D surfaces.

Finally, we find that existing benchmarks for this task are limited, with
incomplete ground-truth object meshes and metrics that do not correctly
penalize floaters. Therefore, we introduce a new dataset of both synthetic and
real-world scenes consisting of multiple objects and equipped with a ground-
truth mesh for each object. We also introduce updated metrics that correctly
penalize all error modes. We compare our method with prior methods both
qualitatively and quantitatively in this benchmark and demonstrate that our
method outperforms the previous methods for this problem. In sum, our
contributions are:

  1. 1.

A new automatic segmentation approach that leverages the 3D scene structure to
generate object segmentations for all the input images from just a few points
the user clicks in one view.

  2. 2.

A new object compactness loss that removes floaters in occluded regions and
produces substantially more accurate reconstruction; and

  3. 3.

A change of initialization for the object models that improves surface quality
and considerably speeds up convergence.

  4. 4.

Synthetic and real-world datasets of multi-object compositional scenes and
their individual geometries.

##  2 Related Work

Neural field representations for geometry. Neural representations for surface
geometry began with methods that trained using 3D supervision [15, 21], but
soon began to focus on using more readily available multi-viewpoint images as
supervision [34, 20]. Neural Radiance Fields [16] introduced a framework to
use volumetric rendering to train radiance fields, leading to follow-on work
improving training and rendering speed [24, 36, 28, 18], handling complex,
unbounded, and dynamic scenes [39, 4, 22, 23, 12, 14], and improving
representation quality [3, 5].

To obtain more explicit geometric representations than NeRFs provide, some
recent advances have optimized neural signed distance functions (SDFs) by
using them to define smooth volume densities that are rendered in the NeRF
framework, which helps guide the training process stably to accurate and
detailed surfaces. VolSDF [35] and NeuS [29] both achieve good surface
reconstructions in this way; building on these methods, MonoSDF [38]
incorporates monocular cues and PermutoSDF [26] achieves detailed
reconstructions of small-scale features.

Decomposing 3D scenes into objects. The methods above focus on reconstructing
geometry or radiance fields, but do not attempt to further understand scenes
as compositions of objects. A number of methods for disentangling separate
objects have been proposed. Some of these methods learn from observing scenes
without further supervision. Niemeyer and Geiger proposed GIRAFFE [19], which
utilizes latent codes to generate object-centric Neural Radiance Fields
(NeRFs) and conceptualize scenes as compositional generative neural feature
fields. uORF learns unsupervised object composition models that can be used to
factor new scenes at inference time [37]. DiscoScene [32] uses weak
supervision in the form of _layout prior_ for object-compositional generation
but fails to generalize to unknown objects. In contrast to the high-level
object decompositions of the above work, Differentiable Blocks World [17]
trains a mid-level scene representation from multiple images. Rather than
achieving the highest geometric quality, that method aims to decompose the
scene into mid-level 3D textured primitives.

Other work uses joint language-visual embeddings like CLIP to identify objects
in 3D scenes. Sosuke _et al_. use CLIP and DINO to learn neural feature
fields, supporting editing and selection mechnisms [11]. LERF [8] learns a
language field by volumetrically rendering proto-CLIP features along the ray
which is supervised with multi-scale CLIP features on the training images,
allowing radiance fields to be decomposed into semantically distinct areas.

In contrast to CLIP, our method relies on a pre-trained 2D image segmentation
network. Other work in this vein includes ObjectNeRF, which separates scenes
into disjoint radiance fields for each object based on rough 2D instance masks
[33]. More recently, the emergence of the Segment Anything Model (SAM) marked
a significant step towards segmenting 2D images [9]. Extending this model to
3D object segmentation, Segment Anything 3D (SA3D) [7] uses mask inverse
rendering and cross-view self-prompting to construct 3D masks, demonstrating
adaptability to various scenes and efficiency in achieving 3D segmentation.
However, unlike our method, SA3D segments a fixed 3D representation and does
not attempt to _separate_ objects from one another, i.e., to modify their
geometry to, e.g., fill in holes at interfaces where they are in contact.

Another key difference with the above work is that we seek not to produce
segmented NeRFs, but instead segmented, separated, and high-quality _surfaces_
in the form of SDFs that can be converted into convenient graphics
representations like meshes. In that sense, our work is similar to ObjectSDF
[30], which uses per-image input instance masks to product an SDF for each
object. However, this method can encounter issues with object and scene
reconstruction accuracy, slow convergence, and training speed. Its successor
ObjectSDF++ [31] introduces an occlusion-aware object opacity rendering
strategy and an overlap regularization term to better separate the surfaces
between neighboring objects. However, it still requires per-image, per-object
input masks, in contrast to our method. RICO [13] leverages geometrically
motivated regularizations to smooth unobserved regions in indoor compositional
scenes, whereas our method goes farther to separate and reconstruct complete
objects. Our method is in the spirit of other semi-supervised methods like
that of Ren _et al_. [25], but scales well to complex scenes with many
objects.

##  3 Methodology

Figure 2: Mask Propagation pipeline: in the first iteration, a user clicks a
point on each object to generate a per-object anchor mask, which are then
unprojected into 3D (here, we only show unprojected 3D points for the bottom
can). These 3D points are subsequently projected back into each image view,
while checking for occlusions. The projected points serve as seeds for SAM
[10] to generate masks for each object (bottom and top cans, door stop). To
combine these individual segmentation masks into a single image, we use a
depth ordering technique. In the next iterations, all views are used as anchor
masks, allowing the pipeline to cover previously unseen regions.

We assume that we are given a set of $N$ posed images
$\mathcal{I}=\\{I_{1},\ldots,I_{N}\\}$ of a scene. We are interested in not
just reconstructing the scene, but segmenting, reconstructing and _separating_
each of $K$ different objects in the scene. By separation, we mean to produce
an SDF representation of each of the $K$ objects so that they can be
manipulated at will. We aim to do so as accurately, as efficiently, and with
as little manual annotation as possible.

Our proposed approach operates in three stages:

  1. 1.

Reconstruct the full scene as a single SDF.

  2. 2.

Generate segmentation masks for each of the $K$ objects in all images by
propagating segmentation mask from one of the views.

  3. 3.

Optimize $K$ separate SDFs using a novel loss to handle occlusion and contacts
between objects for accurate reconstruction.

We next describe each step below.

###  3.1 Scene Reconstruction

We first train a full scene reconstruction. Any SDF-based technique can be
used; however, here we use NeuS [29] which converts the SDF into a density
term to allow for optimization through volumetric rendering. Concretely, for
every pixel $\mathbf{p}$, discrete samples are taken along the corresponding
ray $\\{\mathbf{p}_{i}=\mathbf{o}+t_{i}\mathbf{v}|i=1,\ldots
n,t_{i}<t_{i+1}\\}$ where $\mathbf{o}$ is the camera center and $\mathbf{v}$
is the viewing direction corresponding to the pixel. Then NeuS calculates
densities $\alpha_{i}$ and an accumulated transmittance
$T_{i}=\prod_{j=1}^{i-1}(1-\alpha_{i})$. The density is shown to be related to
the SDF as:

$\displaystyle\alpha_{i}=\max\left(\frac{\Phi_{s}\left(f(\mathbf{p}_{i})\right)-\Phi_{s}\left(f(\mathbf{p}_{i+1})\right)}{\Phi_{s}\left(f(\mathbf{p}_{i})\right)},0\right)$
(1)

where $\Phi_{s}$ is the sigmoid function and $f$ is the SDF. (Please refer to
Wang et. al [29] for details.) Given these densities $\alpha_{i}$ and the
corresponding accumulated transmittance
$T_{i}=\prod_{j=1}^{i-1}(1-\alpha_{j})$, the rendered color at this pixel is
computed as:

$\displaystyle
C(\mathbf{o},\mathbf{p})=\sum_{i}T_{i}\alpha_{i}c(\mathbf{p}_{i},\mathbf{v})$
(2)

where $c(\mathbf{p}_{i},\mathbf{v})$ is the color at the point
$\mathbf{p}_{i}$ seen from the viewing direction $\mathbf{v}$.

The SDF is optimized to minimize rendering and eikonal losses:

$L=L_{\text{color}}+\lambda L_{\text{eik}}$ (3)
$L_{\text{color}}=\frac{1}{m}\sum_{j}\|\hat{C}_{j}-C_{j}\|$ (4)
$L_{\text{eik}}=\frac{1}{nm}\sum_{j,i}(\|\nabla
f(\textbf{p}_{j,i})\|_{2}-1)^{2}$ (5)

Here $j$ indexes over pixels and $i$ indexes over points sampled along a ray.
$\hat{C}_{j}$ is the predicted color, $C_{j}$ is the observed color, $m$ is
the number of pixels, and $n$ is the number of samples per ray, and
$\textbf{p}_{j,i}$ is the sampled point along pixel $j$ at index $i$.

###  3.2 Generating Segmentations

Our next step is to segment each of the $K$ objects in each of the $N$ images.
Given a few clicked points for one of the images, we use SAM [9] to generate
the segmentation; we call this our anchor mask. Then we use the reconstructed
3D scene to backproject the mask into 3D, resulting in labeled 3D points for
each object. Using these labeled 3D points we propagate the segmentation to
all views. Finally, we iterate through this process again, using the newly
obtained segmentation as the anchor mask (for two iterations, in our
implementation). Below we describe each step in detail.

Figure 3: Projection to 3D. Left: Example image. Middle: points projected
without mask edge erosion and outlier removal, resulting in noisy segmentation
outputs. Right: by using mask erosion and outlier removal we obtain clean 3D
points and subsequently obtain a correct segmentation output.

3D point labeling:  After generating the anchor mask, we project it into 3D by
tracing rays from each pixel through the object mask to determine surface
intersections (Figure 2). However, segmentations can often be imprecise near
object boundaries, causing the mask to leak onto other surfaces (Figure 3). To
address this, we first erode the mask to remove any segmentation errors where
the mask overshoots the true boundary. Second, after back-projecting the
points to 3D we remove all points from an object mask whose depths are
outliers, i.e., more than $\theta$ standard deviations from the mean depth of
the object. We found 2.5 to be a good threshold in our experiment.

Finally, we ensure that each 3D point has a unique label by discarding points
with more than one label.

Propagating to a new view:  To segment an object in a new view, we project the
labeled 3D points into that view (as long as they are unoccluded) to obtain
labeled 2D image points (“seeds”). In principle, these 2D points can be used
to prompt SAM. However, in practice, SAM tends to oversegment when prompted
with numerous seeds. To avoid this, we employ a coreset selection algorithm
(algorithm in the supplementary) to reduce the seed points while preserving
the object’s shape.

Finally, to reconcile multiple overlapping segmentations, we perform a partial
ordering of the different objects based on depth. We compare the depths of the
seed points of each mask in the overlapping areas, and assign the overlapping
area to the object that is closer. For example, in Figure 2, this depth
ordering allows us to correctly place the green can pixels in front of the
blue can when viewed from the top. Note that this approach assumes that a
depth ordering exists for every pair of objects, which can be false if objects
are intertwined, but it works in the vast majority of cases. Please refer to
the supplementary for detail.

###  3.3 Object Separation

Given the images and their segmentation masks, our goal is to now produce $K$
separated SDFs, one per object. We can train the $K$ SDFs by updating the
color loss so that each SDF is only responsible for producing the colors of
the corresponding object:

$L_{\text{color}}=\frac{1}{m}\sum_{k}\sum_{j}M_{k}(j)\|\hat{C}_{j}-C_{j}\|$
(6)

However, this is not enough to separate out the object because the
segmentation mask only covers the visible part of the object. When a pixel is
not part of the mask, it is ambiguous whether this is because the pixel is
outside the extent of the object or because it is occluded. Furthermore, there
are still parts of the scene that are not visible from any of the images.
These ambiguous regions include both interfaces between objects and occluded
parts of the scene (e.g., below the table in table-top scenes). It is unclear
how these occluded regions of the SDF must be optimized.

In what follows, we first discuss the simpler case of unoccluded objects and
then discuss the precise ambiguities and our proposed solution.

##### Special case: Unoccluded objects without contacts.

Consider first the special case where each object is completely visible in
each image, and does not make contact with any other part of the scene. In
this case, given a candidate object SDF, we can _render_ an object mask for
each input viewpoint by aggregating the density along each ray. We can then
add a loss term that encourages this predicted mask to match the provided
segmentation mask using a simple binary cross entropy loss. Concretely,
similar to Equation 2, for every object and for every pixel we calculate a
_mask loss_ :

$\displaystyle
L_{\textrm{mask}}=\sum_{k}\sum_{\mathbf{j}}\text{BCE}(\hat{O}_{k}(\mathbf{j}),M_{k}(\mathbf{j}))\text{,
}\hat{O}_{k}=\sum_{i}T_{i}\alpha_{i}^{k}$ (7)

Here, $k$ ranges over objects, $\mathbf{j}$ is a pixel, $i$ ranges over
samples along the ray, $\hat{O}_{k}$ is a score representing the opacity of
this pixel in the $k$-th SDF, and $M_{k}$ is the ground-truth segmentation
indicating if this pixel is part of the $k$-th object.

This loss, as proposed in NeuS [29], causes problems in scenes with
occlusions. To see this, consider Figure 4, where a blue object is occluded by
a gray box. The segmentation only shows the visible parts of the blue object.
Clearly, point A must lie outside the blue object and thus the accumulated
density along the corresponding ray will tend toward 0, as specified by the
mask loss in Equation 7. The mask loss also has the correct behavior for pixel
B, which shows a point on the object surface and so the corresponding ray must
have a high density point along it. However, pixels C and D land on the gray
box that occludes the object of interest, and so are not part of the mask. The
mask loss would suggest that the rays from these pixels should lie completely
outside the object. Clearly, this is not the right behavior at pixel C, and
thus we need a different strategy to handle occlusion.

##### Resolving occlusion:

One option is to not impose any loss on points C and D at all. In other words,
we could exclude all pixels where the object of interest is occluded by
another object. Past work proposes an occlusion-aware loss which has a similar
effect [31]. However, the effect of this is that the trained SDF may now
include artifacts that are occluded from view in all images without incurring
any penalty. While this kind of an object is _possible_ given the input views,
our intuition tells us that it is highly unlikely.

Instead, we propose a prior that, to the extent possible, the object should
only include surfaces that are visible from at least some input view. In other
words, we would like a _compact completion_ of the visible surfaces that we
see in the input views. Thus, in Figure 4, we would be okay with the object
including point C (because it is near projections of other surface points that
are observed in other views), but not okay with any artifacts that include the
point D.

We formalize this intuition as follows. We backproject all annotated pixels
for object $k$ from all input views into the reconstructed 3D scene to create
a cloud of 3D points that are known to belong to this object,
$\mathbf{p}_{k}$. We then project all these points into every view without
regard to occlusion (producing e.g., the crosses in Figure 4). In each view,
we then take the _bounding box_ of these projected points; this is the
_amodal_ bounding box of the object, $\mathcal{B}_{k}$ (the term _amodal_
completion refers to the phenomenon where humans perceive the complete shape
of a background object in spite of occlusion[6]). We then intersect this
amodal bounding box with the provided segmentation masks of the _other
objects_ to get a “present-but-occluded” mask $M^{\textrm{occ}}$. We then only
apply the mask loss above to pixels outside this present-but-occluded region.

$\displaystyle\mathcal{B}_{k}$ $\displaystyle=\text{Bounding
Box}\left(\pi(\mathbf{p}_{k})\right)$ (8) $\displaystyle M^{\textrm{occ}}_{k}$
$\displaystyle=\mathcal{B}_{k}\cap\left(\cup_{i\neq k}M_{i}\right)$ (9)
$\displaystyle L_{\text{compactness}}$
$\displaystyle=\sum_{k}\sum_{\mathbf{j}\notin
M^{\textrm{occ}}_{k}}\text{BCE}\left(M_{k}(\mathbf{j}),\hat{O}_{k}(\mathbf{j})\right)$
(10)

Here $k$ indexes the objects. Effectively, this compactness loss creates a
compact region in 3D space (formed by the intersection of all the frusta
corresponding to the amodal bounding boxes) in which the object is allowed to
lie. Any part of the object outside of this compact region is penalized
irrespective of occlusion.

Figure 4: An occlusion event. The object of interest is the blue cylinder. On
the left is the segmentation mask. On the right, the crosses (not included in
the segmentation mask) represent points on the blue object that are visible in
other views but occluded in this view. The red dotted box is the amodal mask,
and its intersection with the occluding cuboid is the set of pixels that are
“present” in the blue object, but occluded in this view.

##### Resolving object interfaces.

A final step is to resolve object interfaces, to ensure that each object
occupies a distinct region of 3D space and does not intersect others. For
this, we use a loss term, that we call the _overlap_ loss. It adds a penalty
whenever the interiors of two objects overlap. Concretely, suppose we have $K$
SDFs $f_{1},\ldots,f_{K}$. For every 3D point $\mathbf{p}$ sampled randomly in
space, we identify the SDF that yields the most negative value (i.e., the
object for which $\mathbf{p}$ is farthest into the interior), and penalize
negative values from all other SDFs using a hinge loss:

$\displaystyle k^{*}$
$\displaystyle=\arg\min_{k}\left(f_{k}(\mathbf{p})\right)$ (11) $\displaystyle
L_{\text{overlap}}(\mathbf{p})$ $\displaystyle=\sum_{k\neq
k^{*}}\max\left(f_{k}(\mathbf{p}),0\right)$ (12)

Our final loss function is:

$L=L_{\text{color}}+\lambda L_{\text{eik}}+\beta L_{\text{compactness}}+\gamma
L_{\text{overlap}}.$ (13)

We train all $K$ SDFs in parallel using this loss. Where we set the hyper-
parameters to be ($\lambda=0.1$, $\beta=0.9,$ $\gamma=0.001$). We tested on 1
RTX 3090 GPU. We used a batch size of 512 and 64 for the full scene
reconstruction and per-object reconstruction respectively.

##### Initialization.

One challenge with the proposed approach is that it trains $K$ different SDFs,
and so can be up to $K$ times as expensive as training the single scene SDF.
Prior work uses various strategies to reduce this training cost, such as
sharing layers between the SDFs [31] or distilling from the scene SDF [33]. We
propose a simpler strategy that significantly reduces running time (to a few
hours instead of days) and yet preserves details: we initialize each SDF with
a copy of the full scene SDF (unlike ObjectSDF++, which uses a sphere
initialization). Because each SDF starts with geometry that matches the scene,
it has all the details and matches the input images by default. All the
network has to do is to “cut off” the scene SDF in the appropriate regions.

##  4 Benchmark

Figure 5: Left: Previous datasets, like Replica, feature objects that only
includes visible surfaces, not complete surfaces (including hidden surfaces).
As a result, using the cropped sub-meshes as ground-truth for object
separation is not an adequate evaluation. Middle and right: Our proposed
dataset with complete individual objects.

Previous scene decomposition techniques evaluate their methods on benchmark
datasets like Replica and ScanNet. A critical limitation of these is that they
do not offer complete ground truth geometries for the reconstructed objects.
More specifically, per-object meshes are extracted from the full ground truth
mesh of the indoor scene by cropping the ground truth mesh with the semantic
masks and therefore lack completeness in regions occluded by other objects
(Figure 5). We introduce a new benchmark for 3D scene decomposition
techniques, consisting of 30 real-world scenes and 5 synthetically generated
ones. The scenes contains different combinations of objects in close contact,
and we provide a high-quality complete mesh of each object.

###  4.1 Dataset

Real-World Scenes. We provide 22 individual 3D scanned objects and 32 scenes,
each created using a combination of the individual objects. To scan the
individual objects, we use Polycam [2] (for analysis of Polycam, please refer
to the supplementary materials). The scenes are captured as raw images using a
phone camera at a resolution of 3008 × 3008. We provide camera pose estimates
from COLMAP [27], ground-truth meshes from Polycam [2], and masks generated
using our mask propagation strategy. Last, we provide rotations and
translations that align the ground-truth object meshes to the objects in the
scenes.

Synthetic Scenes. We provide 5 synthetic scenes composed by combining objects
with varying geometric complexities. We used Blender [1] to create the
dataset, with each scene centered at the origin. We used white indoor scene
environment lighting. We rendered the scenes with 500 samples at a resolution
of 512×512 using the Cycles renderer, capturing 100 images from cameras
positioned on the upper hemisphere around the subject. In addition to the
multi-view images, we provide ground-truth poses, geometries, masks and
transformations that align object meshes to the corresponding scene. Please
refer to our supplementary material for more details on the creation of real
and synthetic dataset.

###  4.2 Evaluation

To evaluate our method and the baselines we show quantitative and qualitative
results on our synthetic and real world benchmark datasets. For quantitative
evaluation we report the precision and completion ratio. Precision is the
ratio of reconstructed points that are within a distance of $\theta$ from the
ground truth, and penalizes floaters. Completion ratio is the ratio of ground
truth points that are within a distance of $\theta$ of the reconstruction, and
penalizes incomplete reconstructions.

The two-way Chamfer distance is also measured between evenly-sampled vertex
points on the ground truth mesh and sampled vertex points on the predicted
mesh obtained by running marching cubes on the trained SDF.

To calculate these metrics between predicted and ground-truth meshes, it’s
crucial to maintain similar point densities to prevent imbalances. This can be
difficult if the two meshes are widely different in size. ObjectSDF++[31]
addresses this by clipping predicted meshes using ground-truth bounds to
improve density similarity and remove outliers. However, this approach may
artificially inflate precision by not penalizing for floaters outside the
bounding box. Instead, we keep the meshes as is but propose a refinement
technique that uses rejection sampling to maintain consistent point densities,
adjusting for mesh saturation until the surface can’t hold more points and
ensuring a fair comparison. Please see the supplement for more details.

##  5 Experiments

We first evaluate how our mask propagation strategy performs with increasing
number of anchors and iterations. Then, we compare our full pipeline
qualitatively (Fig. 7) and quantitatively (Table. 2) against two baselines,
ObjectSDF++ [31] and RICO [13]. We benchmark these methods on the five
synthetic datasets. Because ObjectSDF++ and RICO fail to produce meshes for
some of the real-world scans, we evaluate on a subset of 11 real scans for
which all methods can produce valid meshes. Finally, we ablate components of
our proposed method to see their impact on the quality of our solution.

###  5.1 Mask Propagation Evaluation

We first evaluate the performance of our segmentation propagation approach. To
do so, we use our synthetic dataset where all scenes have corresponding
ground-truth segmentation.

The first column of each scan in Table 1 shows the mIOU (Mean Intersection
over union) for each iteration, starting with one anchor image. We observe
that the first iteration generally performs poorly but the mIOU improves with
more iterations; however, after the second iteration, the improvement becomes
minimal. Our method can also take multiple anchor images if provided, this can
be useful for example if all the objects are not visible in one image alone or
the user wanted to provide more information. We evaluate the effect of
providing multiple anchor masks in the second and third columns of each scan.
However, after the third iteration, whether we start from a single image or
multiple anchor masks, all converge to similar results, as shown in the third
row.

A failure case of the mask propagation is presented in scan 2 in Table 1,
where the mIOU is low. This is because some parts of one object end up being
labeled as another object; for example, the duck in Figure 8 (top left) is
classified as the horse. Note that the same surface may be correctly labeled
in a different image, since SAM is performed independently for each image.

One may ask how this failure impacts our final reconstruction and separation
result. Figure 8 shows, despite the low mIOU mask of scan 2, our object
separation module still reconstructs plausible results. This is due to the
majority of the masks are still correctly labeled.

Table 1: We report the mIOU values of the predicted masks using our mask
propagation strategy, varying the number of propagation iterations and anchor
images per each scan. Mask quality does not improve much after the second
round of mask propagation and adding additional anchors does not offer much
improvement after a few propagation iterations.

Scan | 1 |  | 2 |  | 3 |  | 4 |  | 5
---|---|---|---|---|---|---|---|---|---
No of anchors | 1 | 2 | 3 |  | 1 | 2 | 3 |  | 1 | 2 | 3 |  | 1 | 2 | 3 |  | 1 | 2 | 3
iter | 1 | 0.73 | 0.77 | 0.86 |  | 0.60 | 0.63 | 0.65 |  | 0.71 | 0.71 | 0.77 |  | 0.86 | 0.91 | 0.91 |  | 0.80 | 0.77 | 0.90
2 | 0.90 | 0.90 | 0.91 |  | 0.64 | 0.64 | 0.64 |  | 0.78 | 0.78 | 0.78 |  | 0.91 | 0.92 | 0.91 |  | 0.94 | 0.94 | 0.94
3 | 0.91 | 0.91 | 0.91 |  | 0.63 | 0.63 | 0.63 |  | 0.78 | 0.78 | 0.78 |  | 0.90 | 0.91 | 0.91 |  | 0.94 | 0.94 | 0.94

###  5.2 Reconstruction Evaluation

Table 2: Quantitative evaluation:  RICO performs the lowest among all methods. ObjectSDF++ performs well on synthetic data, but its performance drops on real data, especially in terms of precision ratio. This drop is due to the imperfect masks in the real scans. On both synthetic and real datasets, our method outperforms the baseline in all metrics. We used GT masks for the synthetic evaluation and masks generated by our mask propagation for the real dataset. Dataset | Metrics | RICO | ObjectSDF++ | Ours
---|---|---|---|---
Synthetic | Chamfer ↓ | 0.374 | 0.018 | 0.010
Prec. Ratio ↑ | 0.449 | 0.937 | 0.960
Comp. Ratio ↑ | 0.868 | 0.946 | 0.991
Real | Chamfer ↓ | 0.138 | 0.096 | 0.015
Prec. Ratio ↑ | 0.537 | 0.763 | 0.921
Comp. Ratio ↑ | 0.595 | 0.835 | 0.927

Table 2 results reveal the failures of the baselines. First, RICO performs
poorly in the quantitative results, despite having decent qualitative results.
The reason is that RICO, while often complete, produces huge floaters like the
one visualized in ‘Real scan7’ in Figure 7 which significantly hurts the
quantitative performance. While RICO achieves good completion metrics, it
struggles to precisely generate meshes of the object of interest.

Second, ObjectSDF++, while competitive on the synthetic datasets, loses out in
the real dataset benchmarks. Unlike the synthetic ground-truth masks, the
masks used in the real-world benchmark of ObjectSDF++ were obtained using our
proposed mask propagation strategy, which is still imperfect. This not only
results in floaters, which are not handled due to the absence of a compactness
loss, but also a loss of detail of objects at sharp edges as shown in ‘Real
scan3’ and ‘Real scan16’. In contrast, we initialize the object SDF from the
reconstructed scene, resulting in more robust results.

From Figures 7 and Table 2, we can conclude our method produces results with
higher quality and fewer floating artifacts. Most of our quantitative
improvement comes from the lack of undesired artifacts like floaters and
carved holes. The remaining improvement, more evident qualitatively, comes
from the scene initialization.

Figure 6: Importance of the compactness loss and initialization. Left: our
compactness loss and initialization together avoids floating artifact and
achieves high-quality results. Middle: a naive mask loss as in NeuS carves out
objects whenever there is an occlusion and with occlusion aware mask, and we
see floating artifacts in unobserved parts of the scene. Right: without scene
initialization details are lost and the runtime grows significantly.

###  5.3 Ablation

To understand the importance of our contributions, we ablate the proposed
compactness loss and the scene initialization as shown in Figure 6.

To evaluate the compactness loss, we compare to two alternatives:

  1. 1.

The first baseline is the naive mask loss used in NeuS, which does not take
object occlusion into account. This loss is defined in Equation (7).

  2. 2.

The second alternative without compactness is an _occlusion-aware mask loss_ :
we simply apply the mask loss only to the unoccluded pixels, i.e., to discount
pixels that are marked as belonging to other objects.

$\displaystyle\tilde{M}^{\textrm{occ}}_{k}$ $\displaystyle=\left(\cup_{i\neq
k}M_{i}\right)$ (14) $\displaystyle L_{\text{occ-aware}}$
$\displaystyle=\sum_{k}\sum_{\mathbf{j}\notin\tilde{M}^{\textrm{occ}}_{k}}\text{BCE}\left(M_{k}(\mathbf{j}),\hat{O}_{k}(\mathbf{j})\right)$
(15)

While this strategy correctly avoids penalizing pixels that are part of the
object but occluded, it does not encourage the object to be compact. As such,
the model is free to hallucinate other floaters as long as they are completely
occluded in the view.

Figure 7: Qualitative Comparison: RICO and ObjectSDF++ produce floating
artifacts, as shown in Real scans 7 and 12. RICO also sometimes carves out the
object, leaving a hollow area, as shown in Real scan 16, 3 and 12. In
contrast, our method produces fewer artifacts while also providing more
detail.  Figure 8: Impact of Low mIOU (scan2 Table 1) on reconstruction. Top:
An example of a low mIOU (0.633) mask, where the handle of the kettle and
parts of the duck are sometimes misclassified as part of the horse. Despite
this, our object separation pipeline remains robust. For instance, the duck
has an accurate 3D mesh due to our scene initialization technique, and the
mask labels are correct in other images. However, the 3D reconstruction of the
horse includes part of the kettle handle, as most of the mask incorrectly
classifies the handle as part of the horse. Bottom: Ground truth mask and its
respective reconstruction.

The three loss variants are shown in the first three columns of Figure 6. When
using naive mask loss, object geometries are carved out, resulting in
incomplete reconstructions. This is because the model is penalized whenever it
produces a surface that is occluded, evident in the hand’s fingers becoming
detached as a result of the object sitting on it. The occlusion-aware mask
loss prevents the objects from being carved out, but introduces floaters,
sometimes _inside_ the other objects, which are reconstructed as hollow
shells. This occurs because any floater that is completely inside the shell of
another object will never be visible and therefore never be penalized. The
compactness loss both removes floaters and prevents the objects from being
carved out.

The last column of Figure 6 shows the reconstruction without the scene
initialization. In this case, the reconstruction quality is significantly
reduced and reconstruction requires a prohibitively long time. Scene
initialization is critical to reducing computational time and obtaining high-
quality results.

##  6 Conclusion

We proposed ObjectCarver, a method that separates objects in a scene into
individual high-resolution meshes by automatically generating segmentation
masks for all multi-view training images from a few clicks on just one image.
We introduced compactness loss, a novel loss function that removes many of the
floaters that have plagued prior methods. Finally, we show that initializing
the per-object models with the scene model not only improves convergence and
reduces training time but also maintains the details of the objects.

Supplementary Material

##  A Runtime analysis

We provide a runtime analysis for all stages of our method, considering an
image size of 512×512 with a single RTX 3090 GPU.

  * •

Stage 1: Scene reconstruction for 200k iterations takes 5.8 hours.

  * •

Stage 2: Segmentation takes 2 minute per image.

  * •

Stage 3: The amount of time Object Separation takes depends on the number of
objects in the scene. For two, four, and six objects, Object Separation takes
2.7, 3.5, and 7.5 hours respectively.

##  B Dataset

The problem of object separation in 3D reconstruction is a fairly new topic
and, as such, lacks the proper benchmark dataset. Previous methods evaluated
their approach on a cropped sub-meshes from a full scene, which has in holes
in occluded regions. Thus, during the evaluation, the area that needs to be
properly evaluated will be ignored. Figure 5 illustrates the issue with
previous datasets. To address the gap in the literature, we introduce a new
benchmarking dataset composed of real-world and synthetic scenes. Below, are
the details on how we created the dataset.

Figure 9: [first row] illustrates our method’s failure due to segmentation
errors. Here, SAM itself struggles to obtain the correct mask as the two
gingerbread houses are colorful, making it difficult to segment them. In the
[second row], the segmentation is correct, but there is a flat surface
floating in the pink box. This is due to the limitation of our amodal bounding
box, which is contain this space from all views. In addition the overlap loss
may not be computed at area as we are using fixed random points (of 10,000) in
3D space to compute the overlap loss and the pink floating surface is thin,
and the points may not lie within this area. In the [third row], both the
torus and the pipe occupy the space. Once again, this highlights the
shortcomings of the amodal bounding box and overlap loss.

###  B.1 Real-world dataset creation

Figure 10 shows the steps we took in creating the dataset. First, we scanned
the individual object to obtain the ground truth mesh using Polycam. Second,
we captured the scene using a handheld camera and then obtained the camera
pose using COLMAP. The fourth step involved obtaining the full scene
reconstruction so that we could use it to align the individual meshes. We
trained vanilla NeuS to obtain the full mesh. The fifth step involved aligning
the meshes, We used Blender software to transform the individual meshes to
their respective positions within the scene. To further refine the alignment
and avoid human error, we applied ICP to align the meshes together.
Ultimately, we obtained each scene images, camera pose, and the transformation
matrix for each individual object. Below, we describe in more detail how we
scanned the individual meshes and the scene.

####  B.1.1 Individual mesh scanning.

We provide 22 object scans. We collected 80-150 images per object and used
Polycam to generate the full mesh. We set the option Isolate object from
environment to true and exported the final mesh in raw format. Since Polycam
is not open-source software, we conducted an analysis of its reconstruction
quality. We performed an experiment where we used the same object in different
environments. We captured the object and obtained a mesh with Polycam and
analyzed the robustness of Polycam. Figure 11 illustrates our analysis. We
used a boot and took pictures in three different environments and used these
three sets of images to obtain the meshes. Then we compared them to each other
to see if there is a significant quality drop. However, we found that they are
very similar, and we concluded that Polycam is consistent in its output.

####  B.1.2 Scene capture.

We provide 32 real-world scene. We used a Samsung Note9 with a 12-megapixel
camera to capture the scenes, utilizing the raw option in the pro-mode to
capture raw images. The original images are $3008\times 3008$ pixels with
16-bit depth. We converted the raw format to .png for lossless compression and
downscaled it to $1002\times 1002$ pixels. We show the steps we took to
collect the dataset on Figure 10. Both the individual scene and individual
objects can be found in Figure 14.

Figure 10: Real-world dataset creation steps: (1) Scanning individual objects
with Polycam for ground truth meshes, (2) Capturing the scene with a handheld
camera, (3) Estimating camera pose with COLMAP, (4) Full scene reconstruction
for mesh alignment, (5) Aligning individual meshes with Blender to the full
scene, and (6) Further aligning the meshes with ICP for precision. From this
process, we obtain scene images, camera poses, and transformation matrices for
each object.  Figure 11:  Analysis of the robustness of Polycam: [Left] images
captured in different environments and their respective Polycam meshes.
[Right] Quantitative evaluation where we compare each mesh against each other
(unit in millimeters). We can observe that both qualitatively and
quantitatively, Polycam is consistent.  Figure 12: Full list of captured real-
world scenes.  Figure 13: Full list of scanned individual meshes using
Polycam.  Figure 14: Full list of synthetic scenes.

###  B.2 Synthetic data creation

We generated five realistic scenes, each with its own level of difficulty.
Each scene has $N$ objects, $N$ ranging from 3 to 10. We used Blender to
create the dataset, with each scene centered at the origin. We used white
indoor scene environment lighting. We rendered the scenes with 500 samples at
a resolution of $512\times 512$ using the Cycles renderer, capturing 100
images from cameras positioned on the upper hemisphere around the subject.

##  C Rejection sampling

When calculating the point-to-point Chamfer distance between predicted and
ground-truth meshes, it is important to ensure locally similar point densities
to avoid one of the directional Chamfer distances from being larger than the
other. While the ideal metric here is the point-to-surface Chamfer distances
(i.e. the average unsigned distances), this is often prohibitively slow;
hence, it is common practice to resample the two point clouds to have the same
number of points for an accurate point-to-point Chamfer distance. However,
when the predicted mesh contains floaters and extraneous artifacts, this
results in a diluted sampled point cloud and causes the densities to differ in
the region of interest. The reverse holds true when the predicted mesh
experiences carved out regions that lower its surface area for point sampling.
ObjectSDF++ and Rico are evaluated on Replica and ScanNet, and they clip the
predicted meshes using the 3D bounds calculated from the ground-truth meshes.
While this was likely done to try to ensure similar point densities, it
removes any floater artifacts that exist outside the clipping bounds, yielding
in a artificially lower smaller precision metric. We revise this evaluation by
using a rejection sampling based approach that samples points only if it is
some radius away from the growing list of samples. If the desired number of
points is large enough to saturate the mesh (i.e. desired number of points is
impossible due to the radius constraint), we ensure that the point density is
similar between the two meshes.

##  D Ablation

###  D.1 Effect of mask propagation on object reconstruction:

Figure 15 shows the effect of mask propagation using the mask obtained from
each iteration. We see that the first iteration is not enough to capture the
full object, as some parts of the segmentation are missing, resulting in
carving out. However, after the second iteration, we observe that we can
obtain the full geometry.

###  D.2 Effect of increasing number of SDF parameters of baselines

One possible reason why ObjectCarver achieves more details in the
reconstruction is that increase in model capacity with a whole SDF network
being dedicated to each model. On the other hand, ObjectSDF++ and RICO use a
single SDF network backbone with separate heads for each object’s SDF. In
order to determine if the expressivity of the SDF networks in RICO and
ObjectSDF++ is the limiting factor, we increase the learnable parameters of
the SDF networks in RICO and ObjectSDF++ by the number of objects $k$. For
ObjectSDF++, we increase the dimensionality of the feature vector learned at
each level of the hash-grid by $k$. For RICO, we increase the width of the
network by $\lceil\sqrt{k}\rceil$. These modified models are called RICO* and
ObjSDF++*.

Figure 17 shows the evaluation results of this comparison. RICO* tends to
over-smooth the geometry and create more floater artifacts than RICO.
ObjectSDF++ achieves better reconstruction quality and even reduces the number
of floaters. However, ObjectCarver still achieves the best qualitative and
quantitative results among the baselines, demonstrating the effectiveness of
scene initialization for learning the geometries with more parameters.

Figure 15: Effect of mask propagation on the reconstruction, [Top]
reconstruction of using the mask, [bottom] mask used for.  Figure 16:
Qualitative comparison on large indoor scenes: Due to our compactness loss,
our method results in fewer artifacts compared to the baseline, which is
plagued by floating artifacts, most apparent in row 3, and carving of the
objects shown in row 2 of the RICO output.  Figure 17: Comparison of
increasing the expressivity of the model backbone of RICO and ObjectSDF++

##  E Additional Results

We provide more qualitative results on our dataset in Figure 18. We can
observe that our method produces much higher quality and fewer floating
artifacts compared to previous methods.

Figure 18: Comparison between RICO, ObjectSDF++ and our approach. ObjectSDF++
produces fewer details and more floating artifacts

##  F Implementation details

###  F.1 Coreset Algorithm

This algorithm takes as input a set of projected 2D points and selects $n$
points that will later be used as seed points for SAM to segment a specific
object (seed points being the set of $(x,y)$ coordinates used to prompt SAM to
segment the object). The intuition behind using this algorithm is to simulate
how a human would select the seed point to segment an object using SAM. It
starts by clicking the centroid of the object; the next point will be far away
from the centroid, and the following point will be far away from both of the
previous points. As a result, these points capture the overall shape of the
object. We chose $n=15$ as it works for most cases.

Algorithm 1 Modified Coreset Algorithm

1:Input: projected points $S\subset\mathbb{R}^{2}$, coreset size $n$

2:Output: $C$

3:$C\leftarrow\\{\\}$

4:$x_{0}\leftarrow\arg\min_{s\in S}\|s-\text{mean}(S)\|_{2}$

5:$C.\text{add}(x_{0})$

6:$S.\text{remove}(x_{0})$

7:while $|C|<n$ do

8: $y\leftarrow\arg\max_{s\in S}\min\\{\|s-c\|_{2}:c\in C\\}$

9: $C.\text{add}(y)$

10: $S.\text{remove}(y)$

###  F.2 Partial depth ordering

When there is an overlap between two segmentation outputs from SAM, the
partial depth ordering is used to break the tie. Below we describe the steps:

#### Step 0: Initialization

  * •

Initialize the depth as zero for each of the $K$ objects.

#### Step 1: Overlap Checking

  * •

For each pair of objects $(k_{h},k_{i})$ where $h\neq i$: Check if the
segmentation masks of object $k_{h}$ and object $k_{i}$ overlap.

#### Step 2: Overlap Resolution

  * •

If there is an overlap between the segmentation masks of objects $k_{h}$ and
$k_{i}$:

    1. 1.

Count the number of seed points in the overlapping region for both
segmentation masks.

    2. 2.

Identify the object with more seed points in the overlapping region as the
”top” object and the one with fewer seed points as the ”bottom” object.

    3. 3.

Increase the depth of the top object by one relative to the depth of the
bottom object.

## References

  * [1] Blender.
  * [2] Polycam.
  * Barron et al. [2021a] Jonathan T. Barron, Ben Mildenhall, Matthew Tancik, Peter Hedman, Ricardo Martin-Brualla, and Pratul P. Srinivasan.  Mip-nerf: A multiscale representation for anti-aliasing neural radiance fields.  _CoRR_ , abs/2103.13415, 2021a.
  * Barron et al. [2021b] Jonathan T. Barron, Ben Mildenhall, Dor Verbin, Pratul P. Srinivasan, and Peter Hedman.  Mip-nerf 360: Unbounded anti-aliased neural radiance fields.  _CoRR_ , abs/2111.12077, 2021b.
  * Barron et al. [2023] Jonathan T Barron, Ben Mildenhall, Dor Verbin, Pratul P Srinivasan, and Peter Hedman.  Zip-nerf: Anti-aliased grid-based neural radiance fields.  _arXiv preprint arXiv:2304.06706_ , 2023.
  * Breckon and Fisher [2005] Toby P. Breckon and Robert B. Fisher.  Amodal volume completion: 3d visual completion.  _Computer Vision and Image Understanding_ , 99(3):499–526, 2005.
  * Cen et al. [2023] Jiazhong Cen, Zanwei Zhou, Jiemin Fang, Wei Shen, Lingxi Xie, Xiaopeng Zhang, and Qi Tian.  Segment anything in 3d with nerfs.  _arXiv preprint arXiv:2304.12308_ , 2023.
  * Kerr et al. [2023] Justin Kerr, Chung Min Kim, Ken Goldberg, Angjoo Kanazawa, and Matthew Tancik.  Lerf: Language embedded radiance fields, 2023.
  * Kirillov et al. [2023a] Alexander Kirillov, Eric Mintun, Nikhila Ravi, Hanzi Mao, Chloe Rolland, Laura Gustafson, Tete Xiao, Spencer Whitehead, Alexander C. Berg, Wan-Yen Lo, Piotr Dollar, and Ross Girshick.  Segment anything.  In _ICCV_ , 2023a.
  * Kirillov et al. [2023b] Alexander Kirillov, Eric Mintun, Nikhila Ravi, Hanzi Mao, Chloe Rolland, Laura Gustafson, Tete Xiao, Spencer Whitehead, Alexander C. Berg, Wan-Yen Lo, Piotr Dollár, and Ross Girshick.  Segment anything, 2023b.
  * Kobayashi et al. [2022] Sosuke Kobayashi, Eiichi Matsumoto, and Vincent Sitzmann.  Decomposing nerf for editing via feature field distillation, 2022.
  * Li et al. [2020] Zhengqi Li, Simon Niklaus, Noah Snavely, and Oliver Wang.  Neural scene flow fields for space-time view synthesis of dynamic scenes.  _CoRR_ , abs/2011.13084, 2020.
  * Li et al. [2023a] Zizhang Li, Xiaoyang Lyu, Yuanyuan Ding, Mengmeng Wang, Yiyi Liao, and Yong Liu.  Rico: Regularizing the unobservable for indoor compositional reconstruction, 2023a.
  * Li et al. [2023b] Zhengqi Li, Qianqian Wang, Forrester Cole, Richard Tucker, and Noah Snavely.  Dynibar: Neural dynamic image-based rendering.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 4273–4284, 2023b.
  * Mescheder et al. [2018] Lars M. Mescheder, Michael Oechsle, Michael Niemeyer, Sebastian Nowozin, and Andreas Geiger.  Occupancy networks: Learning 3d reconstruction in function space.  _CoRR_ , abs/1812.03828, 2018.
  * Mildenhall et al. [2020] Ben Mildenhall, Pratul P. Srinivasan, Matthew Tancik, Jonathan T. Barron, Ravi Ramamoorthi, and Ren Ng.  Nerf: Representing scenes as neural radiance fields for view synthesis.  _CoRR_ , abs/2003.08934, 2020.
  * Monnier et al. [2023] Tom Monnier, Jake Austin, Angjoo Kanazawa, Alexei A. Efros, and Mathieu Aubry.  Differentiable blocks world: Qualitative 3d decomposition by rendering primitives, 2023.
  * Müller et al. [2022] Thomas Müller, Alex Evans, Christoph Schied, and Alexander Keller.  Instant neural graphics primitives with a multiresolution hash encoding.  _CoRR_ , abs/2201.05989, 2022.
  * Niemeyer and Geiger [2021] Michael Niemeyer and Andreas Geiger.  Giraffe: Representing scenes as compositional generative neural feature fields.  In _CVPR_ , 2021.
  * Niemeyer et al. [2019] Michael Niemeyer, Lars M. Mescheder, Michael Oechsle, and Andreas Geiger.  Differentiable volumetric rendering: Learning implicit 3d representations without 3d supervision.  _CoRR_ , abs/1912.07372, 2019.
  * Park et al. [2019] Jeong Joon Park, Peter R. Florence, Julian Straub, Richard A. Newcombe, and Steven Lovegrove.  Deepsdf: Learning continuous signed distance functions for shape representation.  _CoRR_ , abs/1901.05103, 2019.
  * Park et al. [2020] Keunhong Park, Utkarsh Sinha, Jonathan T. Barron, Sofien Bouaziz, Dan B. Goldman, Steven M. Seitz, and Ricardo Martin-Brualla.  Deformable neural radiance fields.  _CoRR_ , abs/2011.12948, 2020.
  * Park et al. [2021] Keunhong Park, Utkarsh Sinha, Peter Hedman, Jonathan T. Barron, Sofien Bouaziz, Dan B. Goldman, Ricardo Martin-Brualla, and Steven M. Seitz.  Hypernerf: A higher-dimensional representation for topologically varying neural radiance fields.  _CoRR_ , abs/2106.13228, 2021.
  * Reiser et al. [2021] Christian Reiser, Songyou Peng, Yiyi Liao, and Andreas Geiger.  Kilonerf: Speeding up neural radiance fields with thousands of tiny mlps.  _CoRR_ , abs/2103.13744, 2021.
  * Ren et al. [2022] Zhongzheng Ren, Aseem Agarwala†, Bryan Russell†, Alexander G. Schwing†, and Oliver Wang†.  Neural volumetric object selection.  In _IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2022.  († alphabetic ordering).
  * Rosu and Behnke [2023] Radu Alexandru Rosu and Sven Behnke.  Permutosdf: Fast multi-view reconstruction with implicit surfaces using permutohedral lattices, 2023.
  * Schonberger and Frahm [2016] Johannes L. Schonberger and Jan-Michael Frahm.  Structure-from-motion revisited.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2016.
  * Takikawa et al. [2021] Towaki Takikawa, Joey Litalien, Kangxue Yin, Karsten Kreis, Charles T. Loop, Derek Nowrouzezahrai, Alec Jacobson, Morgan McGuire, and Sanja Fidler.  Neural geometric level of detail: Real-time rendering with implicit 3d shapes.  _CoRR_ , abs/2101.10994, 2021.
  * Wang et al. [2021] Peng Wang, Lingjie Liu, Yuan Liu, Christian Theobalt, Taku Komura, and Wenping Wang.  Neus: Learning neural implicit surfaces by volume rendering for multi-view reconstruction.  _CoRR_ , abs/2106.10689, 2021.
  * Wu et al. [2022] Qianyi Wu, Xian Liu, Yuedong Chen, Kejie Li, Chuanxia Zheng, Jianfei Cai, and Jianmin Zheng.  Object-compositional neural implicit surfaces, 2022.
  * Wu et al. [2023] Qianyi Wu, Kaisiyuan Wang, Kejie Li, Jianmin Zheng, and Jianfei Cai.  Objectsdf++: Improved object-compositional neural implicit surfaces, 2023.
  * Xu et al. [2022] Yinghao Xu, Menglei Chai, Zifan Shi, Sida Peng, Ivan Skorokhodov, Aliaksandr Siarohin, Ceyuan Yang, Yujun Shen, Hsin-Ying Lee, Bolei Zhou, and Sergey Tulyakov.  Discoscene: Spatially disentangled generative radiance fields for controllable 3d-aware scene synthesis, 2022.
  * Yang et al. [2021] Bangbang Yang, Yinda Zhang, Yinghao Xu, Yijin Li, Han Zhou, Hujun Bao, Guofeng Zhang, and Zhaopeng Cui.  Learning object-compositional neural radiance field for editable scene rendering.  _CoRR_ , abs/2109.01847, 2021.
  * Yariv et al. [2020] Lior Yariv, Matan Atzmon, and Yaron Lipman.  Universal differentiable renderer for implicit neural representations.  _CoRR_ , abs/2003.09852, 2020.
  * Yariv et al. [2021] Lior Yariv, Jiatao Gu, Yoni Kasten, and Yaron Lipman.  Volume rendering of neural implicit surfaces.  _CoRR_ , abs/2106.12052, 2021.
  * Yu et al. [2021] Alex Yu, Ruilong Li, Matthew Tancik, Hao Li, Ren Ng, and Angjoo Kanazawa.  Plenoctrees for real-time rendering of neural radiance fields.  _CoRR_ , abs/2103.14024, 2021.
  * Yu et al. [2022a] Hong-Xing Yu, Leonidas J. Guibas, and Jiajun Wu.  Unsupervised discovery of object radiance fields.  In _ICLR_ , 2022a.
  * Yu et al. [2022b] Zehao Yu, Songyou Peng, Michael Niemeyer, Torsten Sattler, and Andreas Geiger.  Monosdf: Exploring monocular geometric cues for neural implicit surface reconstruction, 2022b.
  * Zhang et al. [2020] Kai Zhang, Gernot Riegler, Noah Snavely, and Vladlen Koltun.  Nerf++: Analyzing and improving neural radiance fields.  _arXiv preprint arXiv:2010.07492_ , 2020.


11institutetext: The University of Texas at Dallas, Richardson TX 75080, USA
11email: {fang.li, elmer.salazar<EMAIL_ADDRESS>
# Graph-based Interpretation of Normal Logic Programs

Fang Li  Elmer Salazar  Gopal Gupta

###### Abstract

In this paper we present a dependency graph-based method for computing the
various semantics of normal logic programs. Our method employs conjunction
nodes to unambiguously represent the dependency graph of normal logic
programs. The dependency graph can be transformed suitably in a semantics
preserving manner and re-translated into a equivalent normal logic program.
This transformed normal logic program can be augmented with a few rules
written in answer set programming (ASP), and the CLINGO system used to compute
its answer sets. Depending on how these additional rules are coded in ASP, one
can compute models of the original normal logic program under the stable model
semantics, the well-founded semantics, or the co-stable model semantics. In
each case, justification for each atom in the model is also generated. We
report on the implementation of our method as well as its performance
evaluation.

###### Keywords:

Normal Logic Programs, Well-founded Semantics, Stable Model Semantics, Co-
stable Model Semantics, Interpretation

##  1 Introduction

Logic programming [1] has been applied to many areas such as fault diagnosis,
databases, planning, natural language processing, knowledge representation and
reasoning. During decades of exploration, researchers have developed various
semantics for solving different reasoning tasks. Among those semantics, the
stable model semantics based answer set programming (ASP) [13] paradigm is
popular for knowledge representation and reasoning as well as for solving
combinatorial problems. Though computing ASP programs is considered to be NP-
hard, there are a lot of ASP solvers (e.g., CLINGO [7], DLV [2], s(CASP) [3])
that can compute stable models of an ASP program efficiently. Meanwhile, there
are also many approaches to solve programs under the well-founded semantics,
such as XSB [15] and XOLDTNF [6]. For the co-stable model semantics [16, 9],
there is no specific solving systems designed yet.

In this paper we are interested in computing models of normal logic programs
under various semantics: stable model, co-stable model and well-founded
semantics, in particular. At the same time, we want to provide justification
for inclusion of a given atom in the model. We show that our graph-based
approach is able to accomplish both these goals.

At present, to compute the semantics of a normal logic program under different
semantics, we have to encode the program in different formats and use
different systems to compute the model(s) under various semantics. For finding
justification, one may have to use yet another system. Lack of a single system
that can achieve all the aforementioned tasks is the main motivation of our
research. Graph-based approaches have other additional benefits, such as
partial models can be computed which is needed in some applications [11].
Elsewhere [10] the authors introduced a dependency graph-based approach to
represent ASP programs and compute their models. The basic idea is to use
dependency graph to represent rules and goals of an answer set program, and
finding models by reasoning over the graph. This graph-based representation is
the basis for our work in this paper in interpreting a normal logic program
under different semantics.

Our novel graph-based method for computing the various semantics of a normal
logic program uses conjunction nodes to represent the dependency graph of the
program. The dependency graph can be transformed in a semantics preserving
manner and re-translated into an equivalent normal logic program. This
transformed normal logic program can be augmented with a small number of rules
written in ASP, and then a traditional SAT solver-based system used to compute
its answer sets. Depending on how these additional rules are coded in ASP, one
can compute models of the original normal logic program under the stable model
semantics, the co-stable model semantics as well as the well-founded
semantics. In this paper, we use CLINGO [7] as the ASP solver to compute
models of the augmented normal logic program.

The rest of this paper is structured as follows: Section 2 introduces the
background knowledge related to the research. Section 3 presents the
interpretation methods for three different semantics. Section 4 uses a simple
example to illustrate the work flow of the algorithm. Section 8 concludes the
paper and introduces the future work with regard to this research.

##  2 Background

###  2.1 Answer Set Programming

Answer Set Programming (ASP) is a declarative paradigm that extends logic
programming with negation-as-failure. ASP is a highly expressive paradigm that
can elegantly express complex reasoning methods, including those used by
humans, such as default reasoning, deductive and abductive reasoning,
counterfactual reasoning, constraint satisfaction [4, 8]. ASP supports better
semantics for negation (negation as failure) than does standard logic
programming and Prolog. An ASP program consists of rules that look like Prolog
rules. The semantics of an ASP program $\Pi$ is given in terms of the answer
sets of the program ground($\Pi$), where ground($\Pi$) is the program obtained
from the substitution of elements of the Herbrand universe for variables in
$\Pi$ [4]. Rules in an ASP program are of the form shown as below (Rule 1):

$p\;:-\;q_{1},\;...,\;q_{m},\;\textbf{not}\;r_{1},\;...,\;\textbf{not}\;r_{n}.$
(1)

where $m\geq 0$ and $n\geq 0$. Each of p and qi ($\forall i\leq m$) is a
literal, and each not rj ($\forall j\leq n$) is a naf-literal (not is a
logical connective called negation-as-failure or default negation). The
literal not rj is true if proof of rj fails. Negation as failure allows us to
take actions that are predicated on failure of a proof. Thus, the rule r :-
not s. states that r can be inferred if we fail to prove s. Note that in Rule
1, p is optional. Such a headless rule is called a constraint, which states
that conjunction of qi’s and not rj’s should yield false. Thus, the constraint
:- u, v. states that u and v cannot be both true simultaneously in any model
of the program (called an answer set).

The declarative semantics of an Answer Set Program P is given via the Gelfond-
Lifschitz transform [4, 8] in terms of the answer sets of the program
ground($\Pi$). More details on ASP can be found elsewhere [4, 8].

###  2.2 Dependency Graph

A dependency graph [12] uses nodes and directed edges to represent dependency
relationships of an ASP rule.

###### Definition 1

The dependency graph of a program is defined on its literals s.t. there is a
positive (resp. negative) edge from $p$ to $q$ if $p$ appears positively
(resp. negatively) in the body of a rule with head $q$.

Conventional dependency graphs are not able to represent ASP programs
uniquely. This is due to the inability of dependency graphs to distinguish
between non-determinism (multiple rules defining a proposition) and
conjunctions (multiple conjunctive sub-goals in the body of a rule) in logic
programs. For example, the following two programs have identical dependency
graphs (Figure 2).

⬇

%% program 1 %% program 2

p :- q, not r, not p. p :- q, not p. p :- not r.

To make conjunctive relationships representable by dependency graphs, we first
transform it slightly to come up with a novel representation method. This new
representation method, called conjunction node representation (CNR) graph,
uses an artificial node to represent conjunction of sub-goals in the body of a
rule. This conjunctive node has a directed edge that points to the rule head
(Fig. 2).

Figure 1: Dep. Graph for Programs 1 & 2

(a) CNR for Program 1

(b) CNR for Program 2

Figure 2: CNRs for Program 1 & 2

The conjunction node, which is colored black, refers to the conjunctive
relation between the in-coming edges from nodes representing subogals in the
body of a rule. Note that a CNR graph is not a conventional dependency graph.

###  2.3 Converting CNR Graph to Dependency Graph

Since CNR graph does not follow the dependency graph convention, we need to
convert it to a proper dependency graph in order to perform dependency graph-
based reasoning. We use a simple technique to convert a CNR graph to an
equivalent conventional dependency graph. We negate all in-edges and out-edges
of the conjunction node. This process essentially converts a conjunction into
a disjunction. Once we do that we can treat the conjunction node as a normal
node in a dependency graph. As an example, Figure 4 shows the CNR graph to
dependency graph transformation for program p :- q, not r. This transformation
is a simple application of De Morgan’s law. The rule in this program
represents p :- C. and C :- q, not r. The transformation produces the
equivalent rules p :- not C., C :- not q. and C :- r.

Since conjunction nodes are just helper nodes which allow us to perform
dependency graph reasoning, we don’t report them in the final answer set.

###  2.4 Constraint Representation

ASP also allows for special types of rules called constraints. There are two
ways to encode constraints: (i) headed constraint where negated head is called
directly or indirectly in the body (e.g., Program 3), and (ii) headless
constraints (e.g., Program 4).

⬇

%% program 3 %% program 4

p :- not q, not r, not p. :- not q, not r.

Our algorithm models these constraint types separately. For the former one, we
just need to apply the CNR-DG transformation directly. Note that the head node
connects to the conjunction node both with an in-coming edge and an out-going
edge (Figure 3(a)). For the headless constraint, we create a head node with
truth value as False. The reason why we don’t treat a headless constraint the
same way as a headed constraint is because in the latter case, if head node (p
in Program 3) is provable through another rule, then the headed constraint is
inapplicable. Therefore, we cannot simply assign a False value to its head.

Figure 3: CNR-DG Transformation

(a) Program 3

(b) Program 4

Figure 4: Constraint DG

###  2.5 Graph-based Transformation of an ASP Program

Based on the representation method defined above, we are able to convert an
ASP program into the graph format, which uses nodes for goals and edges for
rules. This process can be broken down into three steps: (1) converting the
original ASP program to CNR representation. (2) converting the CNR graph to
dependency graph. (3) wrapping each goal (or rule) with a ”node” (or ”edge”)
predicate. Algorithm 1 is the pseudo-code for implementing this procedure. In
our actual implementation, this procedure is written in the RUST language.

Algorithm 1 CNR-ASP Parsing Algorithm

1:g $\leftarrow$ new Graph()

2:conj_cnt $\leftarrow$ 0

3:rules $\leftarrow$ parse(file)

4:for r in rules do $\triangleright$ parse input program into graph

5: head, tail $\leftarrow$ parseRule(r)

6: if head.len() == 0 then head $\leftarrow$ ”constraint”

7: end if

8: if tail.len() $\leq$ 1 then

9: g.nodes.add(head, true)

10: else if tail.len() == 1 then

11: g.edges.add(tail, head, tail[0].sign)

12: else

13: conj $\leftarrow$ append(”conj”, ++conj_cnt.toString())

14: for t in tail do

15: g.edges.add(t, conj, t.sign.negate())

16: end for

17: g.edges.add(conj, head, negative)

18: end if

19:end for

20:res $\leftarrow$ new List()

21:for n in g.nodes do $\triangleright$ wrap goals with nodes

22: res.append(”node(” + n + ”)”)

23:end for

24:for e in g.edges do $\triangleright$ wrap rules with edges

25: res.append(”edge(” + e.from + ”,” + e.to + ”,” + e.sign + ”)”)

26:end for

27:return res

Let’s take Program 5 as an example.

⬇

%% program 5

p :- not q, r. q :- not p.

Step 1, we need to use CNR representation to solve the conjunctive goals in
the body of the first rule:

⬇

negative_edge(q, conjunct_1).

positive_edge(r, conjunct_1).

positive_edge(conjunct_1, p).

The second rule will be directly represented as

⬇

negative_edge(p, q).

Step 2, negating the signs of each edge (with conjunct_1) to get a dependency
graph:

⬇

positive_edge(q, conjunct_1).

negative_edge(r, conjunct_1).

negative_edge(conjunct_1, p).

negative_edge(p, q).

Step 3, wrapping goals and rules: Here we should parameterize the edge signs
for the reasoning purpose. Therefore, the final dependency graph
representation will be:

⬇

node(p). node(q). node(r). node(conjunct_1).

edge(q, conjunct_1, positive).

edge(r, conjunct_1, negative).

edge(conjunct_1, p, negative).

edge(p, q, positive).

###  2.6 Effective Edge

An effective edge in a dependency graph refers to any edge that propagates
True value to the node it is incident on. There are two types of effective
edges: (i) positive edge emanating from a True node; (ii) negative edge
emanating from a False node. An effective edge only points to a True node.

###  2.7 Loops in Programs

In an ASP program, loops among literals may exist. There are three kinds of
loops that can be found in the program: even loops, odd loops, and positive
loops. Even loops and odd loops refer to loops that have an even or odd number
of negative edges in the corresponding dependency graph. Positive loops are
loops with no negative edge.

##  3 Graph-based Normal Logic Program Interpretations

To compute different semantics of a normal logic program, we transform it into
a graph-based representation (discussed in Section 2.5), then augment the
program with the corresponding interpreter (consisting of ASP rules). The
resulting augmented ASP program can be solved by any ASP solver system (e.g.,
CLINGO). In this section, we introduce three interpreters which turn CLINGO
into solvers for different semantics.

Note that information regarding dependence between various literals in the
program is made explicit in the graph representation. This information is
maintained in the ASP program that results from the transformation and can be
made explicit in the answer sets of this transformed program. This explicit
information on dependence can then be used to provide justification
automatically.

It should be noted that this graph-based transformation approach can be quite
useful for the analysis of normal logic programs. In general, some interesting
property of the program can be computed and the dependency graph annotated.
The annotated graph can then be transformed into an answer set program with
the annotation intact. Models of the transformed program can then be computed
using traditional solvers. The annotations in the model can then be used for
computing the program property of interest. Finding causal justification of
literals in the model is but one example of this general technique.

###  3.1 CNR Graph Transformation

It is worth mentioning that our CNR based dependency graph transformation of
normal logic programs has an inherent “flaw”. However, this flaw actually
works to our advantage. As introduced in previous sections, the CNR approach
makes use of De Morgan’ Law by inserting an extra node with negated in/out
edges to convert conjunctive relationships into disjunctions. From the
perspective of logical meaning, double-negation is equivalent to a positive
claim, but under the stable model semantics, it may lead to differences.

For example, program p :- q, r. q :- p. r. has a positive loop between $p$ and
$q$. According to the stable model semantics, this program will only have an
empty model, in which both $p$ and $q$ are false. But after adding the double-
negation based conjunctive node $conj\\_1$ to represent p :- q, r., the new
graph will form an even loop between $p$, $conj\\_1$ and $q$. Since we have
$r$ as a fact, under this case, we will get two models {p/True, q/True} and
{p/False, q/False}, which violate the stable model semantics! But at the same
time, this follows the co-stable model semantics (introduced later).

This “flaw” in our graph transformation actually allows us to compute models
under the the co-stable model semantics. Therefore, all of our interpreters
that are introduced in this paper will be based on the co-stable model
semantics interpretation. For interpreting the stable model semantics, we just
need to bypass the double-negation related to conjunctive nodes in order to
falsify positive loops. For the well-founded semantics, we will have to change
the values of each node from binary to ternary (True, False, and Unknown).

###  3.2 The Co-stable Model Semantics Interpretation

Let us next introduce the co-stable model semantics interpretation, because it
is the basis of the other two interpreters.

Co-stable model semantics [16, 9] is similar to the stable model semantics,
except in the last step of the Gelfond-Lifschitz transform, where, instead of
finding the least fixpoint of the residual program, we compute its greatest
fixpoint. Thus, the co-stable model semantics is similar to stable model
semantics, the only difference is the way it handles positive loops. In the
co-stable model semantics, a positive loop generates two models, consisting of
an empty model and an all-true model. For example, in program p :- q. q :- p.,
co-stable model semantics will return {p/True, q/True} and {p/False, q/False}.

Co-stable model semantics is useful in many situations where we have cyclical
dependency between positive goals. For instance, consider the following two
rules: (i) Jack will drink wine if Jill drinks wine, and (ii) Jill will drink
wine if Jack drinks wine. In this case, co-stable model semantics will produce
the two expected answer sets: one in which both Jack and Jill drink wine, and
another in which none of the two drink wine (stable model semantics will
produce only a single model, namely, none of the two will drink wine).

The following ASP rules interpret the co-stable model semantics:

⬇

1effective_edge(X,Y) :- edge(X,Y,positive), not false(X).

2effective_edge(X,Y) :- edge(X,Y,negative), false(X).

3

4true(X) :- fact(X).

5true(X) :- node(X), can_pos(X), not false(X).

6

7false(X) :- node(X), not can_pos(X), not true(X).

8

9can_pos(X) :- edge(Y,X,_), effective_edge(Y,X).

10

11:- true(constraint).

12

13#show true/1.

14#show false/1.

This interpreter only has 6 rules, which directly reflects the CNR-dependency
graph representation of a normal logic program. As mentioned in section 3.1,
the CNR-dependency graph representation changes a positive loop to an even
loop. Therefore, in the interpreter, we only need to define the rules for
realizing effective edges (i.e., assign True value to the tail of each
effective edge). Lines 1-2 define the rules for effective edges: (i) when the
head of an edge is not False and the edge sign is positive, then the edge is
effective; (ii) when the head of an edge is False and the edge sign is
negative, then the edge is effective. Line 4-5 defines the situations that
make a node to be labeled True: (i) the node is a fact in the original
program; (ii) the node can be positive, and cannot be proved as False. Line 7
defines when a node is to be labeled False, which is in a manner opposite of
the previous rule. Finally, line 9 defines the situation in which a node can
be assigned True, that is the node being the tail of an effective edge. Line
11 ensures that the constraint node is always labeled False. Line 13-14 set
parameters for CLINGO to only print the True or False nodes.

###  3.3 The Stable Model Semantics Interpretation

The stable model semantics is the basis of answer set programming. In this
semantics, even loops generate multiple worlds, while odd loops kill worlds.
For example, in program p :- not q. q :- not p., $p$ and $q$ form an even
loop, which generates two mutually exclusive worlds: {p/True, q/False} and
{q/True, p/False}. For program p :- not q. q :- not r. r :- not p., nodes $p$,
$q$ and $r$ form an odd loop, which makes the program unsatisfiable. A
positive loop only generates an empty model.

The following ASP rules interpret the stable model semantics:

⬇

1effective_edge(X,Y,positive) :- edge(X,Y,positive), not false(X).

2effective_edge(X,Y,negative) :- edge(X,Y,negative), false(X).

3

4true(X) :- fact(X).

5true(X) :- node(X), can_pos(X), not false(X).

6

7false(X) :- node(X), not can_pos(X), not true(X).

8

9can_pos(X) :- edge(Y,X,_), effective_edge(Y,X, Sign).

10

11negate(positive, negative).

12negate(negative, positive).

13

14update(positive, negative, negative).

15update(negative, positive, negative).

16update(positive, positive, positive).

17update(negative, negative, negative).

18

19depends(X,Y,Sign) :- effective_edge(Y,X,Sign).

20depends(X,Y,Sign) :- not conjunct(Z), effective_edge(Z,X,positive),

21 depends(Z,Y,Sign).

22depends(X,Y,Sign) :- conjunct(Z), effective_edge(Z,X,negative),
edge(Z2,Z,S2),

23 negate(S2,S3),depends(Z2,Y,S4), update(S3,S4,Sign).

24

25:- true(N), depends(N,N,positive).

26:- true(constraint).

27

28#show true/1.

29#show false/1.

Based on the co-stable model interpreter, we added some rules to determine
whether an even loop is native or caused by the CNR transformation. In the
later case, there should be a conjunction node involved. Line 19-25 define
rules to extinguish real positive loops from even loops that are caused by the
CNR transformation. By proving depends/3, we will know whether a node depends
on itself and the sign of the dependency. If a node depends on itself and the
sign of the dependency is positive, it means that the node is in a positive
loop.

Basically, this stable model semantics interpreter extended the co-stable
model semantics interpreter, adding the positive loop detection mechanism to
prevent the extra model they generate.

###  3.4 The Well-founded Semantics Interpretation

The well-founded semantics can be viewed as a three-valued version of the
stable model semantics. Instead of only assigning propositions True or False,
it also allows for a value representing ignorance (Unknown). Any atom in an
even loop or an odd loop will be considered as Unknown. The following ASP
rules interpret the well-founded semantics:

⬇

1effective_edge(X,Y,positive) :- edge(X,Y,positive), not not_true(X).

2effective_edge(X,Y,negative) :- edge(X,Y,negative), false(X).

3

4not_true(X) :- node(X), not true(X).

5

6true(X) :- fact(X).

7true(X) :- node(X), can_pos(X), not false(X), not unknown(X).

8

9false(X) :- node(X), not can_pos(X), not true(X), not unknown(X).

10

11unknown(X) :- node(X), not true(X), not false(X).

12

13can_pos(X) :- edge(Y,X,_), effective_edge(Y,X, Sign).

14can_unknown(X) :- node(X), not can_pos(X), edge_type(S),

15 edge(Y,X,S), unknown(Y).

16

17negate(positive, negative).

18negate(negative, positive).

19

20edge_type(positive).

21edge_type(negative).

22

23update(negative, S, negative) :- edge_type(S).

24update(positive, S, S) :- edge_type(S).

25

26dependent_edge(X,Y,Sign) :- true(Y), effective_edge(X,Y,Sign).

27dependent_edge(X,Y,Sign) :- unknown(X), unknown(Y), can_unknown(Y),

28 edge(X,Y,Sign).

29dependent_edge(X,Y,Sign) :- false(Y), not can_unknown(Y), edge(X,Y,Sign).

30

31depends(X,Y,Sign) :- not conjunct(Y), dependent_edge(Y,X,Sign).

32depends(X,Y,Sign) :- not conjunct(Z), dependent_edge(Z,X,S1),

33 depends(Z,Y,S2), update(S1,S2,Sign).

34depends(X,Y,Sign) :- conjunct(Z), dependent_edge(Z,X,negative),

35 dependent_edge(Z2,Z,S1), negate(S1,S2), depends(Z2,Y,S3),
update(S3,S2,Sign).

36

37:- edge(N1,N2,S), edge_type(S), false(N2), unknown(N1).

38:- edge(N1,N2,S), edge_type(S), unknown(N2), effective_edge(N1,N2,S).

39:- node(N), not unknown(N), not conjunct(N), depends(N,N,negative).

40:- node(N), not false(N), depends(N,N,positive), not depends(N,N,negative).

41:- unknown(N), not can_unknown(N).

42:- not unknown(constraint).

43

44#show true/1.

45#show false/1.

46#show unknown/1.

Besides assigning False to positive loop nodes, the well-founded semantics
also gives Unknown value to nodes involved in even loops and odd loops. So the
interpreter will be built on the stable model semantics interpretation rules.

The first thing we need to handle is the representation of the Unknown value.
In line 1, we use not not_true(X) to define effective edges instead of not
false(X)  in the other two interpreters. Then in line 11, Unknown is defined
by neither True nor False. By doing this, we can avoid the even loop between
true(X) and false(X), so that the domain of the value of a node will have
three values. Line 26-35 redefine the depends/3 from the stable model
interpreter by adding aspects related to the Unknown value.

##  4 Examples and Results

In this section we will use an example to illustrate the process of computing
models for a simple program under the three different semantics. First, we
transform the program into the dependency graph representation, and then
regenerate it into an answer set program in the node/edge format. The
transformed program is then augmented with each of the rule-sets corresponding
to three different semantics. Finally, the augmented programs is evaluated
with CLINGO to obtain the answer sets. Here is a simple example answer set
program:

⬇

p :- not q, r.

q :- not p.

r :- p.

After transformation, the program will appear as follows:

⬇

node(p).

node(conjunct(0)).

node(q).

node(r).

conjunct(conjunct(0)).

edge(p,q,negative).

edge(p,r,positive).

edge(conjunct(0),p,negative).

edge(q,conjunct(0),positive).

edge(r,conjunct(0),negative).

When augmented with the stable model interpretation rules, CLINGO will produce
a single model: {false(p), true(conjunct(0)), true(q), false(r)}. This is
because in the stable model semantics, the positive loop between node $p$ and
$r$ cannot make any of them to be True. Only $q$ being True can make all rules
consistent.

When the transformed program is appended with the co-stable model
interpretation rules, CLINGO will produce two models for it: {false(p),
true(conjunct(0)), true(q), false(r)} and {false(q), true(p),
false(conjunct(0)), true(r)}. That is because the positive loop allows both
$p$ and $r$ becoming True simultaneously in the second answer set.

When combining with the well-founded semantics interpretation rules, CLINGO
returns one model: {unknown(p), unknown(conjunct(0)), unknown(q), unknown(r)}.
That is because $p$, $q$, and $r$ are all entangled in loops with negation and
therefore are unknown.

##  5 Performance

The interpreters for various semantics introduced in this paper are built on
top of CLINGO, so the overhead incurred needs to be understood. To quantify
this overhead, we compare the running time of the interpreted program with
running time when the program is directly run on CLINGO without
transformation. Of course, we can do this exercise only for the stable model
semantics, as CLINGO does not have the option for computing the co-stable
model semantics or the well-founded semantics.

Problem | Original (seconds) | Interpreted (seconds)
---|---|---
Coloring (4 nodes) | 0.001 | 0.007
Coloring (10 nodes) | 0.004 | 0.022
Ham Cycle (4 nodes, not fully connected) | 0.002 | 0.006
Ham Cycle (4 nodes, fully connected) | 0.003 | 0.011
N Queens (N = 4) | 0.004 | 0.009
N Queens (N = 8) | 0.037 | 0.082
K Clique (5 nodes) | 0.001 | 0.002
K Clique (10 nodes) | 0.001 | 0.005
Table 1: Performance Comparison on Classic Problems

From table 1 we can see that the interpreted approach is slower than directly
computing the model using CLINGO. The overhead is anywhere from two to five
times. The upside is that we gain the ability to compute the models for normal
logic programs under different semantics, as well as provide justification
(discussed next) for a given answer set under any of the three semantics.

##  6 Model Justification

One important feature of the graph-based interpretation method is the
convenience of being able to justify why an atom appears or does not appear in
a model. Since all the goals and their connecting edges are shown in the
graph, their causal relationships are explicitly captured in the dependence
graph representation. Therefore, when justifying a model, we just need to
validate all of the effective edges (discussed in section 2.6). These
effective edges capture the justification for each of the atoms in a model.
Let us take the example from section 4. We know that the graph contains 5
edges:

⬇

1 edge(p,q,negative).

2 edge(p,r,positive).

3 edge(conjunct(0),p,negative).

4 edge(q,conjunct(0),positive).

5 edge(r,conjunct(0),negative).

Justifying the Stable Models: For the stable model semantics case, we only
have one model: {false(p), true(conjunct(0)), true(q), false(r)}. Plugging
these nodes into each edge, we will get three effective edges: {edge 1, edge
4, edge 5}. Accordingly, the end points of those effective edges $q$ and
$conjunct(0)$ should also be True. Since $q$ and $conjunct(0)$ are both in the
model, the model is justified. This causal justification can be output in a
user-friendly format.

Justifying the Co-stable Models: For the co-stable model semantics case, we
have two models. The first model is identical to the stable model, therefore,
the justification is omitted here. The other model is {false(q), true(p),
false(conjunct(0)), true(r)}. After plugging in to the edges relation, we get
two effective edges {edge 2, edge 3}. Then from the ending points of effective
edges, we get {true(r), true(p)} which are in the model. Thus, this model is
also valid.

Justifying the Well-founded Model Under the well-founded semantics, there will
always be only one model for a program. In this example, we have {unknown(p),
unknown(conjunct(0)), unknown(q), unknown(r)}, which means no effective edges
could be formed. Therefore, there is no True node in this model. Thus, the
model is valid.

##  7 Related Work

To the best of our knowledge, the method that is introduced in this
paper—which interprets a normal logic program under different semantics using
a traditional ASP solver—is novel. Since our method also provides
justification for ASP models, we give a brief overview of relevant approaches
to justification for ASP.

Off-line and on-line justifications [14] provide a graph-based explanation of
the truth value (i.e., true, false, or assume) of a literal. The explanation
assume is used for literals whose truth value is not being requested. Causal
Graph Justification [5] explains why a literal is contained in an answer set,
but not why a negated literal is not contained. LABAS [17] explains the truth
value of an extended goal with respect to a given answer set. A goal is in the
answer set if a derivation of this goal is supported and is not in the answer
set if all derivations of this goal are “attacked”. XSB [15] based ErgoAI
(https://coherentknowledge.com) generates justification trees for programs
with variables, but it only works with the well-founded semantics. s(CASP) [3]
can generate justifications for Constraint Answer Set programs, preventing
generating excessively many justifications thanks to its ground-free, top-down
evaluation strategy and the use of constraints. It can also justify negated
literals and global constraints.

Comparing to the above approaches, the justification method we present in this
paper has two major advantages: (i) the graph preserves the causal
relationships that are defined by the program rules, but doesn’t need to
maintain a causal chain (as in the Causal Graph Justification approach) to
justify a literal in the model. (ii) it is capable of justifying models under
different semantics, instead of only being bound to justification for ASP
under stable model semantics.

##  8 Conclusion and Future Work

In this paper, we presented a novel method to represent normal logic programs
as dependency graphs. After augmenting with ASP interpretation rules, these
programs can be executed under different semantics by an ASP solver. This
research provides a new perspective, that a normal logic program can be
transformed into an intermediate format, which, when combined with specific
interpreters can be used for computing semantics other than stable model
semantics using the extremely efficient solver developed for answer set
programming such as CLINGO. Thus, the efficiency of ASP solvers is exploited
to develop interpreters for normal logic programs wrt other semantics with
very little effort. The graph-based method also allows us to find the
justification for the model(s) computed.

In the future, we plan to work on optimizing our dependence graph-based
implementation. Since interpretation rules actually define a symbolic graph
structure of a semantics, it means that all programs under one semantics will
have the same abstract graph structure. Therefore, we can optimize a solver
exclusively for each such graph structure. This is akin to specializing
(partially evaluating) an interpreter w.r.t. a given program.

Acknowledgement: Authors gratefully acknowledge support from NSF grants IIS
1718945, IIS 1910131, IIP 1916206, and from Amazon Corp and US DoD.

## References

  * [1] Abiteboul, S., Hull, R., Vianu, V.: Foundations of databases, vol. 8. Addison-Wesley Reading (1995)
  * [2] Adrian, W., Alviano, M., Calimeri, F., Others: The asp system dlv: Advancements and applications. Künstl Intell 32, 177–179 (2018)
  * [3] Arias, J., Carro, M., Salazar, E., Marple, K., Gupta, G.: Constraint answer set programming without grounding. Theory and Practice of Logic Programming 18(3-4), 337–354 (2018)
  * [4] Baral, C.: Knowledge representation, reasoning and declarative problem solving. Cambridge University Press (2003)
  * [5] Cabalar, P., Fandinno, J., Fink, M.: Causal graph justifications of logic programs. TPLP 14(4-5), 603–618 (2014)
  * [6] Chen, W., Warren, D.S.: A goal-oriented approach to computing the well-founded semantics. The Journal of Logic Programming 17(2-4), 279–300 (1993)
  * [7] Gebser, M., Kaminski, R., Kaufmann, B., Schaub, T.: Clingo= asp+ control. arXiv preprint arXiv:1405.3694 (2014)
  * [8] Gelfond, M., Kahl, Y.: Knowledge representation, reasoning, and the design of intelligent agents: The answer-set programming approach. Cambridge University Press (2014)
  * [9] Gupta, G., Saeedloei, N., DeVries, B., Min, R., Marple, K., Kluźniak, F.: Infinite computation, co-induction and computational logic. In: International Conference on Algebra and Coalgebra in Computer Science. pp. 40–54. Springer (2011)
  * [10] Li, F.: Graph based answer set programming solver systems. arXiv preprint arXiv:2109.08681 (2021)
  * [11] Li, F., Wang, H., Basu, K., Salazar, E., Gupta, G.: Discasp: A graph-based asp system for finding relevant consistent concepts with applications to conversational socialbots. arXiv preprint arXiv:2109.08297 (2021)
  * [12] Linke, T., Sarsakov, V.: Suitable graphs for answer set programming. In: International Conference on Logic for Programming Artificial Intelligence and Reasoning. pp. 154–168. Springer (2005). https://doi.org/10.1007/978-3-540-24609-1_26
  * [13] Marek, V.W., Truszczyński, M.: Stable models and an alternative logic programming paradigm. In: The Logic Prog. Paradigm, pp. 375–398. Springer (1999)
  * [14] Pontelli, E., Tran, S., Elkhatib, O.: Justifications for logic programs under answer set semantics. TPLP 9(1), 1–56 (2009)
  * [15] Rao, P., Sagonas, K., Swift, T., Warren, D.S., Freire, J.: XSB: A system for efficiently computing well-founded semantics. In: Proc. LPNMR. pp. 430–440 (1997)
  * [16] Salazar, E.: Proof-theoretic Foundations of Normal Logic Programs. Ph.D. thesis (2019), Department of Computer Science, The University of Texas at Dallas.
  * [17] Schulz, C., Toni, F.: Justifying answer sets using argumentation. TPLP 16(1), 59–110 (2016)