Abstract
Program synthesis has emerged as a successful approach to the image parsing task. Most prior works rely on a two-step scheme involving supervised pretraining of a Seq2Seq model with synthetic programs. This paper introduces the first fully unsupervised algorithm for parsing images into executable programs (like Constructive Solid Geometry) without requiring any supervised pretraining. By combining a grammar-constrained tree LSTM with an efficient "sampling without replacement" strategy, the authors overcome the "sparse reward" problem, allowing a model to learn how to describe an image through code just by looking at the final picture.
Introduction
In computer vision, representing images as human-readable programs—such as a CAD model where a chair is defined as a "union of four cylinders and a cube"—offers a more interpretable alternative to black-box neural representations. This task, known as Program Synthesis, has traditionally relied on a two-step process: supervised pretraining on synthetic datasets followed by Reinforcement Learning (RL) fine-tuning.
However, this approach faces significant hurdles. Program aliasing occurs when multiple distinct code strings produce the same image; supervised learning penalizes models for generating any version that doesn't match a specific training label. Furthermore, supervised models often fail to generalize to real-world images that deviate from synthetic training distributions. Unsupervised learning avoids these issues but is notoriously difficult due to sparse rewards: random programs almost never produce meaningful outputs, leaving the model with no feedback to learn from.
Methods
The authors propose a purely RL-driven approach centered on three architectural and algorithmic innovations:
1. Grammar-Encoded Tree LSTM
To ensure the model only explores valid programs, the rules of the language (Context-Free Grammar) are baked directly into the architecture. Using a stack-based approach, the model is physically constrained from generating syntactically invalid code.
2. Decomposed Entropy Estimator
To prevent the model from collapsing into a single guess, entropy regularization is used to encourage exploration. The authors developed a "stepwise" estimator that decomposes the entropy of a full program into individual decisions, significantly reducing mathematical noise (variance) during training.
3. Sampling Without Replacement (SWOR)
Standard Monte Carlo sampling often results in the model evaluating the same incorrect program multiple times. By utilizing a Gumbel-top-k trick, the model samples a diverse set of distinct programs in every batch. This forces the model to explore the search space more efficiently and prevents redundant computations.
Key Insights: The Power of Diversity
The "Sampling Without Replacement" strategy proved to be a critical component for unsupervised success. By ensuring the model never evaluates the same program twice in a single update, the entropy—and thus the breadth of exploration—increases much faster than with standard sampling methods.
Furthermore, by rewarding the model based on the rendered output rather than a specific text string, the system bypasses the aliasing trap. The model is free to discover any valid way to construct a shape, leading to better generalization.
Results
The model was evaluated on two benchmarks: a Synthetic 2D CSG Dataset and a 2D CAD Furniture Dataset.
- Synthetic Performance: On the CSG dataset, the model achieved near-perfect scores (0.98 Chamfer Reward and 0.99 IoU) for simpler programs. It maintained high performance even as the search space expanded to approximately $3.8 \times 10^{28}$ possible programs.
- CAD Furniture: On the furniture dataset, the unsupervised model significantly outperformed supervised models that lacked fine-tuning. When compared to "refined" models (supervised + RL), the unsupervised approach was highly competitive, achieving a Chamfer Distance of 1.47 (lower is better) compared to the refined model's 1.49.
Ablation studies confirmed that the tree structure, entropy regularization, and SWOR are all essential; removing any one of these pillars caused the model to fail or converge to local optima.
Conclusion
This work demonstrates that fully unsupervised program synthesis is viable for image parsing. While currently limited to 2D binary images and relatively short programs, it provides a foundation for scaling to 3D geometry and more complex scenes. Future research will focus on increasing the efficiency of search strategies to handle the exponential growth of the search space as program length increases.
Summary updated