PaperlayerView exact revision on arXiv

Source-linked AI summary

ShapeCoder: Discovering Abstractions for Visual Programs from Unstructured Primitives

R. Kenny Jones, Paul Guerrero, Niloy J. Mitra, Daniel Ritchie

arXiv:2305.05661v1cs.GRcs.AIcs.CVcs.LGcs.PL

TL;DR

Obtaining useful visual-program abstractions is difficult without expert design, and prior discovery methods have limitations in modeling parametric relationships or input requirements. ShapeCoder learns abstractions and programs from unstructured primitives; it outperforms previous methods on its abstraction objective and produces compact explanations, including for unseen shapes.

  • Problem

    Useful abstraction functions can improve visual-program quality, but they are difficult to obtain without expert design, while prior methods may miss parametric relationships or require demanding inputs.

    Source: §1 · pp. 1–2

  • Method

    ShapeCoder learns an abstraction library from unannotated primitive collections and uses partial-solution recognition and conditional e-graph rewrites to infer programs for the shapes.

    Source: §1 · p. 2

  • Results

    ShapeCoder significantly outperforms ShapeMOD, even with its wake phase, and DreamCoder on the abstraction objective while finding meaningful parametric and structural relationships.

    Source: §1 · p. 2

  • Takeaways & Limitations

    ShapeCoder produces compact programs for shapes not observed during optimization and discovers useful abstractions even over noisy, inconsistent primitive decompositions.

    Source: §1 · p. 2, §8 · p. 13

    The method can produce redundant abstractions because it does not execute programs to compare their geometric outputs.

    Source: §8.1 · p. 13

Abstract

from arXiv · show

Programs are an increasingly popular representation for visual data, exposing compact, interpretable structure that supports manipulation. Visual programs are usually written in domain-specific languages (DSLs). Finding "good" programs, that only expose meaningful degrees of freedom, requires access to a DSL with a "good" library of functions, both of which are typically authored by domain experts. We present ShapeCoder, the first system capable of taking a dataset of shapes, represented with unstructured primitives, and jointly discovering (i) useful abstraction functions and (ii) programs that use these abstractions to explain the input shapes. The discovered abstractions capture common patterns (both structural and parametric) across the dataset, so that programs rewritten with these abstractions are more compact, and expose fewer degrees of freedom. ShapeCoder improves upon previous abstraction discovery methods, finding better abstractions, for more complex inputs, under less stringent input assumptions. This is principally made possible by two methodological advancements: (a) a shape to program recognition network that learns to solve sub-problems and (b) the use of e-graphs, augmented with a conditional rewrite scheme, to determine when abstractions with complex parametric expressions can be applied, in a tractable manner. We evaluate ShapeCoder on multiple datasets of 3D shapes, where primitive decompositions are either parsed from manual annotations or produced by an unsupervised cuboid abstraction method. In all domains, ShapeCoder discovers a library of abstractions that capture high-level relationships, remove extraneous degrees of freedom, and achieve better dataset compression compared with alternative approaches. Finally, we investigate how programs rewritten to use discovered abstractions prove useful for downstream tasks.

1 INTRODUCTION

ShapeCoder discovers abstraction libraries and programs for shapes represented as unstructured primitives, addressing the difficulty of obtaining useful visual-program abstractions without expert design. Its recognition network and conditional e-graph rewrites support this process, and it significantly outperforms prior methods on the abstraction objective.

1 INTRODUCTION

  • Useful abstraction functions can improve visual-program quality, but expert-designed libraries are hard to obtain and prior discovery methods either miss parametric relationships or require demanding inputs.A DSL that merely unions instantiated primitives may reconstruct a scene perfectly while losing structure and downstream benefits such as editing, generation, and analysis.Source: §1 · pp. 1–2
  • ShapeCoder takes a base DSL and unannotated collections of primitives, then discovers abstraction functions and programs that explain the input shapes.The library is tailored to the input distribution.Source: §1 · p. 2
  • Its recognition network learns partial solutions, allowing program inference on datasets without a curriculum of examples that are easy to solve using the base DSL.The paper identifies lack of a task curriculum as a limitation of some prior work.Source: §1 · p. 2
  • E-graphs let the integration stage search a large space of refactored programs, while conditional rewrites lazily evaluate parametric relationships to avoid e-graph size blowup.This supports integrating more complex abstractions that better match the input distribution.Source: §1 · p. 2
  • ShapeCoder significantly outperforms ShapeMOD, even with its wake phase, and DreamCoder on the abstraction objective while finding meaningful parametric and structural relationships.The discovered relationships dramatically simplify the input datasets.Source: §1 · p. 2

2 RELATED WORK

Prior work spans abstraction discovery, visual program induction, and visual program generation, but DreamCoder and ShapeMOD have limitations for discovering abstractions in complex visual programs.

2 RELATED WORK

  • Program-abstraction methods range from context-free grammars to iterative program-induction and abstraction systems; Babble uses e-graphs but lacks special handling for complex parametric expressions [Cao et al. 2023].The paper notes that extending Babble's anti-unification scheme to ShapeCoder's e-graph formulation could be interesting.Source: §2 · pp. 2–3
  • Visual program induction has expanded from domains such as vegetation, façades, and urban landscapes to neural methods for jointly inferring program parameters and structure.Recent domains include CSG sequences, CAD modeling sequences, SVG shapes, and L-Systems; ShapeAssembly and ShapeMOD arrange cuboid primitives [Jones et al. 2020; Jones et al. 2021].Source: §2 · p. 3
  • Visual program generation includes deep generative models for materials, SVGs, CAD sketches, and 3D CAD sequences [Guerrero et al. 2022; Carlier et al. 2020; Reddy et al. 2021a; Para et al. 2021; Seff et al. 2022; Wu et al. 2021; Xu et al. 2022].ShapeAssembly and ShapeMOD can also serve as generative models [Jones et al. 2020; Jones et al. 2021].Source: §2 · p. 3
  • DreamCoder alternates program induction and abstraction discovery, with an objective trading off program likelihood against library complexity.Its dream phase samples library programs, its wake phase infers programs, and its abstraction phase proposes and integrates library improvements.Source: §2 · p. 3
  • DreamCoder uses structural abstractions that discretize real-valued components, and can fail to discover programs or abstractions when its task-curriculum assumption is broken.The authors report that it did not find the kinds of abstractions ShapeCoder finds in their simple grammar with parametric relationships.Source: §2 · p. 3
  • ShapeMOD discovers structural and parametric abstractions but requires imperative programs, known valid line reorderings, and hierarchical part annotations [Jones et al. 2021].Its integration and proposal stages use the limited reorderings to propose macros and determine their applicability.Source: §2 · p. 3

3 OVERVIEW

ShapeCoder iteratively expands a library to explain a dataset of primitive-based shapes while optimizing an objective that balances program fit and library complexity.

3 OVERVIEW

  • Each input shape is an unstructured primitive collection assumed to have an equivalent program expansion in the supplied library.Each round dreams training scenes, infers dataset programs, proposes abstractions, and integrates candidates for later rounds.Source: §3 · p. 4

3.1 Optimization Objective F

  • The objective F balances program complexity and reconstruction error against library complexity, rejecting programs whose geometric error exceeds a user-defined threshold.Program length is a weighted sum of token counts; function costs can be weighted by input arity, which can indicate an overly general pattern.Source: §3.1 · p. 4

4 INFERRING VISUAL PROGRAMS

ShapeCoder infers programs by training a recognition network on sampled library expressions, then iteratively selecting expressions that explain input primitives and combining them into complete programs.

4 INFERRING VISUAL PROGRAMS

  • The recognition network finds partial expressions for subsets of primitives, which are combined into complete programs; the search assumes a combinator and an analytical way to represent each primitive.The analytical procedure ensures a solution can be found for any individual primitive under the library.Source: §4 · p. 4

4.1 Recognition Network

  • A Transformer decoder attends to tokenized primitive parameters and autoregressively predicts library-function tokens and parameterizations.Real-valued scene parameters are rounded to two decimal places and mapped to tokens for conditioning and prediction.Source: §4.1 · p. 4, Figure 3 · p. 5

4.2 Dream Phase

  • Dream training combines independently sampled function-specific dreams into composite scenes, creating separate target expressions for each component.The paired examples train the network with supervised maximum-likelihood updates, with each library function appearing in at least the specified number of targets.Source: §4.2 · p. 5

4.3 Wake Phase

  • Wake repeatedly samples expressions, selects the lowest-cost expression per explained primitive, removes covered primitives, and combines selected expressions until the canvas is empty.Naive single-primitive expressions are also included to guarantee a valid solution.Source: §4.3 · p. 5
  • Later wake rounds preserve earlier programs by greedily replacing entries with combinations of old and newly inferred programs to optimize F.This avoids clearing the program set and forgetting previously discovered solutions.Source: §4.3 · p. 5

5 PROPOSING AND INTEGRATING ABSTRACTIONS

ShapeCoder proposes abstractions from programs inferred for the input shapes, then integrates candidates into a library when refactoring improves the objective. Its proposal and integration phases use local searches to manage the abstraction-discovery problem.

5.1 Proposal Phase

  • The proposal phase records observed abstraction structures and parameterizations, then samples structure–parameterization clusters for greedy candidate search.It considers singleton and paired sub-expression structures and filters out those observed in less than 5% of programs.Source: §5.1 · p. 6
  • Candidate abstractions are scored by cluster frequency and parameter-reduction gain, with parameter slots filled by high-scoring expressions or new free parameters.Float slots consider possible parametric relationships; discrete slots can reuse an instantiated parameter or take a static value.Source: §5.1 · p. 6

5.2 Integration Phase

  • Integration adds a top-scoring candidate, refactors the programs under the modified library, and keeps the change only if the objective improves.It also tests variants that replace overlapping functions or remove library functions, retaining the best-scoring library.Source: §5.2 · pp. 6–7

6 REFACTORING PROGRAMS WITH E-GRAPHS

ShapeCoder uses e-graphs and conditional rewrites to refactor programs into lower-cost equivalent expressions while checking structural and parametric matches. The conditional scheme avoids unnecessary parametric e-nodes and can apply approximate matches within a user-specified error threshold.

Refactor operation

  • The refactor operation converts a program into an e-graph, expands it with semantic and abstraction rewrites, then extracts a minimum-cost equivalent program.Expansion continues until saturation or timeout.Source: §6 · pp. 7–8

E-graphs

  • E-graphs compactly represent equivalent programs through e-nodes and e-classes, enabling rewrite rules and extraction of a low-cost expression.Rewrite rules preserve semantic equivalence, and extraction finds a minimal-cost expression from the root e-class.Source: §6 · p. 7

Conditional rewrite scheme

  • Conditional rewrites first find structural matches, then lazily check parametric relationships to avoid expanding the e-graph with unnecessary parametric operators.The checks can allow approximately equivalent rewrites under a user-specified maximum error threshold.Source: §6 · p. 8

Refactoring with conditional rewrites

  • Conditional rewriting quickly saturates e-graphs for complex inputs with many parameters, while the naive approach times out at high complexity.The paper reports time in seconds and describes the conditional scheme as a dramatic speedup for its refactoring problems.Source: Table 1 · p. 8, §6 · p. 8

7 RESULTS AND EVALUATION

Across the evaluated shape domains, ShapeCoder discovers abstractions that improve compression, capture reusable structure, and support downstream perturbation and synthesis tasks. The results also show that useful abstractions can be learned from noisy, unsupervised primitive decompositions.

7.1 Experimental Domains

  • Experiments use 400 PartNet shapes per category, represented as simplified cuboids with hierarchy and canonical ordering removed.The main domains are Chairs, Tables, and Storage; the starting primitives match ShapeMOD's except for the removed ordering and hierarchy information.Source: §7.1 · p. 8

7.2 Discovering Abstractions

  • ShapeCoder improves the objective over ShapeMOD, while reducing starting objective values by 56% for Chairs, 67% for Tables, and 53% for Storage.For Chairs, ShapeCoder reaches 63 versus Szalinski's 131, from a starting value of 146; ShapeMOD also struggles when canonical orderings and hierarchy annotations are absent.Source: Table 2 · p. 9, §7.2 · p. 9

7.3 Analysis of Discovered Abstractions

  • Discovered abstractions capture diverse geometry and constrain degrees of freedom; post hoc inference on held-out Chair shapes shows a relatively small training–validation difference in compression.The abstractions can nest, and some explain an entire chair from five parameters; the table caption identifies Table 3 as comparing post hoc inference on held-out shapes with normal operation.Source: §7.3 · pp. 9, 11, Table 3 · p. 11

7.4 ShapeCoder Ablations

  • Every tested ablation worsens optimization; removing conditional rewrites leaves the naive-rewrite version unfinished after the three-day budget.The authors link other ablations to underused or undiscovered abstractions, while preference weighting helps avoid local minima.Source: §7.4 · p. 11, Table 4 · p. 11

7.5 Discovering Abstractions from Unstructured Shapes

  • On noisy, unsupervised ShapeNet chair decompositions, ShapeCoder discovers meaningful reusable abstractions and improves the objective score by 61%, from 140 to 53.9.The discovered chair structure resembles an abstraction found with PartNet annotations; Figure 7 shows two top-level abstractions sharing a four-leg-base sub-function.Source: Figure 7 · p. 12, §7.5 · p. 12

7.6 Downstream Benefits of Abstractions

  • Rewriting programs with discovered abstractions helps keep perturbed outputs in distribution, a property the authors identify as important for goal-directed editing.The evaluation measures similarity to a validation set using Frechet Distance in a pretrained model's feature space.Source: §7.6 · p. 12
  • Training a generative model on abstraction-based programs improves validation Frechet Distance from 17.1 to 13.8, a 19% improvement.The model also produces novel shapes that qualitatively stay within the training distribution; its sampled programs and nearest neighbors are shown in Figure 8.Source: §7.6 · pp. 12–13, Figure 8 · p. 13

8 CONCLUSION

ShapeCoder discovers abstractions from unstructured primitive collections without requiring ground-truth programs, operation ordering, or a program curriculum, and finds abstractions for noisy decompositions. The conclusion also identifies limitations in abstraction redundancy, e-graph saturation, and wake-phase inference, while the appendix specifies the 3D and simplified 2D grammars.

8 CONCLUSION

  • ShapeCoder discovers high-level abstractions from unstructured primitives without ground-truth programs, operation ordering, or a program curriculum, and can explain unseen shapes compactly.It also finds useful abstractions from noisy primitive decompositions produced by an unsupervised method.Source: §8 · p. 13

8.1 Limitations and Future Work

  • Redundant abstractions can encode the same concept, and without executing programs to compare geometry, their outputs may feel redundant for downstream tasks.The authors propose exploring conditional or probabilistic abstractions, such as a chair-base abstraction varying between pedestal and four-leg forms.Source: §8.1 · p. 13
  • E-graphs cannot always be fully saturated within the computational budget, leaving potentially useful rewrites unexplored and out of the abstraction library.Conditional rewrites avoid extraneous parametric operation nodes and alleviate exponential blowup, but do not directly solve saturation limits.Source: §8.1 · p. 13
  • The bottom-up wake network must be retrained when the library changes, can make inference expensive, and yields less consistent inferred programs across a dataset.A top-down replacement could remove the need for primitive collections, but would be more challenging.Source: §8.1 · p. 13
  • ShapeCoder requires a functional language; its combinator operation and primitive-decomposed inputs are needed for the wake phase.The authors suggest raw-visual-input inference networks could relax the latter requirements.Source: §8.1 · p. 13
  • The authors identify sketches, CSG, SVG, and shader programs as possible domains for future exploration.They note that the language requirements may be relaxed by using inference networks that consume raw visual data.Source: §8.1 · p. 13

A SHAPE GRAMMAR

  • The 3D grammar includes symmetry reflection and translation, rotation, movement, cuboid construction, and arithmetic parameter operations.Symmetry translation makes a specified number of copies up to a specified distance; axes are X, Y, or Z, and integer copy counts range from 1 to 6.Source: A SHAPE GRAMMAR · p. 15
  • The 2D grammar is a simplified 3D version without rotation, using 2D parameterizations and rectangle construction.Its symmetry operations use X or Y axes, and integer copy counts range from 1 to 4.Source: A SHAPE GRAMMAR · p. 15

B IMPLEMENTATION DETAILS

The implementation details set N_A=20 and N_D=10000 for all Section 7 experiments.

B IMPLEMENTATION DETAILS

B.1 Objective Function Weights

The implementation assigns different objective weights to token types and geometric error, and modulates abstraction cost according to expression and usage properties.

B.1 Objective Function Weights

  • Float tokens receive weight 2.0, shape-returning function tokens 1.0, float-returning function tokens 0.1, and categorical tokens 0.5.Float-returning function tokens include parametric operations; categorical tokens include integers.Source: §B.1 · p. 15
  • The geometric error weight λ_e is set to 10.Source: §B.1 · p. 15
  • A new abstraction has base cost 0.25, modulated from 0.125 to 0.5; parametric expressions and doubleton abstractions decrease cost, while singleton abstractions increase it.More than 6 input parameters incur penalties, and abstractions with more than 10 parameters are rejected.Source: §B.1 · p. 15
  • Abstractions used in less than 1% of observations are rejected outright.Source: §B.1 · p. 15

B.2 Geometric Error Function

The geometric error function matches generated primitives to target primitives, with domain-specific distances, thresholds, and a stricter equal-count validity check during integration.

B.2 Geometric Error Function

  • The error function builds a pairwise primitive-distance matrix, rejects pairs above a threshold by assigning distance 10000, then uses Hungarian matching to find an optimal mapping.The error is the sum of distances for matched pairs; a match is valid only if none exceeds 10000.Source: §B.2 · pp. 15–16
  • During integration, a program is invalid if its generated and target primitive counts differ, enforced by requiring a square distance matrix.Source: §B.2 · p. 16
  • For 2D rectangles, distance is the average absolute difference across width, height, x position, and y position, with a maximum error threshold of 0.05.Source: §B.2 · p. 16
  • For 3D cuboids, distance is the Hausdorff distance between corner-point sets, with a maximum error threshold of 0.1.Cuboids are represented by dimensions, position, and Euler-angle rotations.Source: §B.2 · p. 16

B.3 Recognition Network

The appendix details how ShapeCoder trains its recognition network, constructs dreams, and combines inferred programs. It also describes its search over parametric relationships and its conditional e-graph rewrites.

B.3 Recognition Network

  • The recognition network is a causally masked Transformer trained during dream phases, with up to 16 input primitives and a maximum prediction length of 32.It uses two attention blocks, eight heads per block, and a hidden dimension of 128; training uses batch size 64, dropout 0.5, and learning rate 0.0001, with early stopping on held-out dreams.Source: §B.3 · p. 16

B.4 Dream Creation

  • Dreams sample type-matched tokens and float values, reject invalid or redundant scenes, and combine function-specific samples with optional distractors and translations.Dreams must satisfy primitive size, visibility, and scene-bound constraints and contain no more than 16 primitives; composite scenes combine one to four functions, sometimes adding distractors or a translation not included in the target expression.Source: §B.4 · p. 16

B.5 Combining Wake Programs

  • Wake inference compares the current program and recognition proposal with greedy merged and rebuilt variants, retaining the variant with the lowest score under F.Programs are split into expressions covering subsets of primitives; greedy merging checks matching instances and replaces them when the proposal improves F, while rebuilding selects low-cost, non-overlapping expressions until all primitives are covered.Source: §B.5 · p. 16

B.6 Preference Ordering of Parametric Relationships

  • Candidate parametric expressions are considered in increasing complexity, from constants through expressions using up to three previously instantiated variables, stopping once the cluster is covered.Only zero is considered as a constant, and a score function selects among the resulting candidates.Source: §B.6 · p. 17

B.7 E-graphs

  • ShapeCoder augments Egg e-graphs with a shared mapping from e-classes to real values, maintained by dummy rewrites to support conditional rewrites.The method also supplies domain-specific semantic-preserving rewrites: 25 for 3D and 16 for 2D.Source: §B.7 · p. 17

B.8 Unsupervised Primitive Decomposition

The appendix describes preprocessing unsupervised cuboid predictions for ShapeCoder and a Transformer model for generating programs from shapes. It also specifies how that model is trained and sampled.

B.8 Unsupervised Primitive Decomposition

  • 400 chair cuboid predictions from Yang and Chen [Yang and Chen 2021] are parsed into primitives, filtering scenes with more than 12 cuboids and snapping near-axis-aligned cuboids to axis alignment.The cuboid predictions come from pretrained models applied to the test set; snapping uses a 0.05 threshold around 0 or 2π Euler angles.Source: §B.8 · p. 17

B.9 Generative Model for Programs

  • The program generator is a Transformer conditioned on a CNN encoding of voxelized shapes that autoregressively adds predicted expressions until it predicts STOP.It is trained on programs inferred from 3,600 chairs, using shuffled expression sequences, teacher forcing, and maximum-likelihood updates; the comparison model uses the same setup with the starting library.Source: §B.9 · p. 17

Related papers

Loading 2305.05661v1…