💻 computer science

Recovering Construction Logic from Chinese Key Fret Patterns through Joint Primitive and Grammar Inference

This paper presents a primitive-grammar co-inference method that recovers executable construction logic and reusable design parameters from Chinese key fret patterns without requiring task-specific training, enabling more compact and editable representations for heritage documentation and reuse.

Original authors: Shunan Zhang, Yi Xiao, Guangpeng Wei, Xuguang Yuan, Chi-Sing Leung

Published 2026-10-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Shunan Zhang, Yi Xiao, Guangpeng Wei, Xuguang Yuan, Chi-Sing Leung

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

For centuries, artisans have filled the world with intricate geometric designs, from the meandering borders on ancient Chinese pottery to the repeating patterns on furniture and textiles. These designs, known as key-fret patterns, are built from simple right-angled turns and straight lines that repeat in complex, symmetrical ways. For a human observer, these patterns are beautiful and meaningful, but for a computer, they are often just a flat image of black lines on a white background. Traditional methods of digitizing these designs can trace the lines accurately, turning a photograph into a digital drawing. However, these methods treat every line as a separate, independent object. They fail to understand that the design is actually built from a few reusable building blocks that are copied, rotated, and reflected to create the whole. Without this understanding, a digital archive is merely a picture; it cannot be edited, reconstructed, or truly understood as a set of construction rules.

A team of researchers at Hunan University and the City University of Hong Kong has developed a new way to look at these patterns. Instead of just tracing the lines, their method attempts to reverse-engineer the logic the original designer used. They call this process "primitive–grammar co-inference." In simple terms, the computer looks at a scanned image and asks two questions at the same time: "What are the basic shapes here?" and "How were these shapes put together?" It does not just draw the lines; it figures out that a specific corner shape was used four times, or that a whole section was created by flipping another section over. The system then writes a set of instructions, or a program, that can rebuild the pattern from scratch. This program is compact, editable, and reveals the hidden rules behind the visual form.

The researchers tested their method on 230 different patterns, ranging from perfectly clean computer-generated images to real-world photographs of aged artifacts with scratches and uneven lines. They compared their approach against existing tools that simply trace the image or tools that try to find patterns after the tracing is already done. The results showed that their joint method was far superior at finding the underlying structure. While the older tools could draw the lines with similar accuracy, they missed the connections between them. The new method successfully identified that repeated shapes were actually copies of the same prototype and that symmetrical sections were created through specific operations like reflection or rotation. In tests, the new system correctly identified the construction rules in about 76 percent of cases, whereas the best alternative method managed only about 34 percent.

Perhaps the most significant finding is that this method produces a much more efficient digital representation. Because the system recognizes that a shape is repeated, it does not need to store the coordinates for every single copy. Instead, it stores the shape once and a rule that says "copy this four times." This reduced the number of independent data points needed to describe a pattern by more than half compared to standard tracing methods. This efficiency matters because it makes the digital file smaller and, more importantly, easier to work with. If a designer wants to change the width of the lines in the pattern, they can adjust the single "prototype" shape, and the computer will automatically update every instance of that shape in the design. If they want to change the spacing, they can adjust the rule that controls the repetition.

The study also highlighted the importance of not making early decisions. Traditional methods often pick one way to draw the lines and then try to find patterns within that fixed drawing. If the initial drawing splits a repeated unit into two separate pieces, the computer can never realize they were meant to be one. The new method avoids this trap by keeping multiple possibilities open at the start. It considers different ways the lines could be grouped and only settles on the best explanation after it has checked how well each explanation fits the image and how simple the resulting rules are. This flexibility allowed the system to recover complex structures, such as patterns where a design is repeated and then rotated, which other methods consistently failed to identify.

The researchers found that this approach works even when the input image is imperfect. Whether the pattern came from a high-quality vector file or a photograph of a worn ceramic tile with missing pieces, the system could still infer the likely construction logic. It does this by weighing the visual evidence against the simplicity of the rules. If a pattern looks like it was made by repeating a shape, the system will favor that explanation even if the image has a small gap or a slight distortion. The study confirms that accurate tracing alone is not enough to recover the logic of a design. To truly preserve and reuse these historical ornaments, we need to recover the executable instructions that created them, turning a static image back into a dynamic, editable set of rules. This work offers a new way to document cultural heritage, ensuring that the construction logic of these ancient patterns is not lost, but preserved in a form that can be studied, modified, and understood for generations to come.

Technical Summary: Recovering Construction Logic from Chinese Key Fret Patterns through Joint Primitive and Grammar Inference

1. Problem Definition

The paper addresses the challenge of recovering executable construction logic from raster images of Chinese key-fret patterns (huiwen). While existing computational methods can trace contours or generate variations, they typically fail to recover the underlying reusable units (prototypes), shared parameters, and construction relations (operators) that define the pattern's generative structure.

Current approaches face a specific limitation:

Flat Vectorization: Converts images to paths but treats repeated elements as independent geometric copies, losing shared parameters and relational semantics.
Fixed-Decomposition Grammar Recovery: Assumes primitives and decomposition boundaries are predefined or fixed early, preventing the system from considering alternative interpretations where a path might be a single module or a sequence of turns.
Sequential Pipelines: Methods that first vectorize, then cluster prototypes, and finally detect relations often commit prematurely to a structural explanation, missing more compact or editable programs that require a different initial decomposition.

The core problem is an inverse procedural modeling task where primitive boundaries, prototype sharing, and operator structures (e.g., repetition, reflection) must be inferred jointly from ambiguous raster evidence, rather than resolved in a fixed sequential order.

2. Methodology: Primitive–Grammar Co-Inference

The authors propose a training-free framework that performs primitive–grammar co-inference. The method maintains multiple primitive hypotheses and jointly searches over reusable prototypes and executable operator structures.

Key Components:

Overcomplete Primitive Initialization:
Instead of committing to a single vectorization, the method constructs an overcomplete attributed graph of orthogonal atomic segments and path candidates. It retains several compatible "covers" (sets of paths that explain the image) as alternative structural hypotheses. This includes periodic partitions proposed along skeleton chains.
Joint Structural Inference:
The system performs a beam search over a state space defined by $(C, Z, G, \theta)$ $(C, Z, G, θ)$ , where $C$ $C$ is the primitive cover, $Z$ $Z$ is the prototype assignment, $G$ $G$ is the operator tree, and $\theta$ $θ$ are continuous parameters.
- Rewrite Operations: The search explores structural transitions including:
  - Decomposition: Split and Merge to refine primitive boundaries.
  - Prototype Sharing: Tie (assign compatible occurrences to a shared prototype), Untie (release incorrect sharing), and Reassignment.
  - Relation Discovery: Proposes operators (Connect, Repeat, Reflect, RotateRepeat) based on geometric compatibility (direction sequences, segment lengths, stroke widths) without requiring the occurrences to share a prototype beforehand.
- Coupling: Primitive hypotheses, prototype assignments, and operator structures are evaluated within a single search objective, allowing a change in one to enable a better configuration in another.
Raster-Aware Rewrite Evaluation:
Candidate programs are scored using an energy function $E(S; I)$ $E (S; I)$ that balances:
1. Reconstruction Fidelity ( $L_{rec}$ ): Pixel difference, edge difference, and bidirectional distance between the rendered program and the input raster.
2. Program Compactness ( $C_{prog}$ ): Penalizes the count of independent prototypes, operators, and free scalar parameters.
3. Geometric Regularity ( $R_{geom}$ ): Enforces orthogonality and penalizes disconnected placements.
  The search uses beam search to retain competing derivations and applies final reranking based on compactness and supported relations.

3. Key Contributions

Formulation: A novel formulation of key-fret digitization as the recovery of executable construction logic from raster observations, explicitly representing reusable units, shared parameters, and compositional relations.
Framework: A training-free primitive–grammar co-inference framework that retains alternative decompositions and jointly infers prototype sharing and operator structures (Connect, Repeat, Reflect, RotateRepeat) from geometric compatibility, avoiding the pitfalls of sequential pipelines.
Evaluation: A comprehensive evaluation on 230 patterns (100 synthetic, 80 vector, 50 real scanned/photographed) demonstrating that the method achieves stronger structural recovery and more compact representations than baselines while maintaining competitive geometric fidelity.

4. Results

The method was compared against Flat Vectorization and PolyVector Flow + Fixed-Decomposition Grammar Recovery.

Structural Recovery: The proposed method achieved significantly higher Operator F1 (0.763 vs. 0.000 for Flat; 0.339 for PolyVector) and Prototype F1 (0.841 vs. 0.000 for Flat; 0.473 for PolyVector).
Compactness: The recovered programs were substantially more compact, using an average of 30.1 free parameters compared to 87.2 for Flat Vectorization and 86.5 for PolyVector. This reduction reflects genuine reuse rather than over-aggressive merging.
Geometric Fidelity: The method maintained competitive geometric accuracy, with a mean center-path distance of $3.32 \times 10^{-3}$ , only slightly higher than the topology-aware PolyVector baseline ( $2.56 \times 10^{-3}$ ) but significantly better than Flat Vectorization ( $3.46 \times 10^{-3}$ ).
Editability: In a controlled study on synthetic programs, the recovered programs exposed 90.6% of reference-eligible edit controls (shared prototypes, repeat counts, symmetry axes), enabling coordinated edits that are cumbersome in flat vector representations.
Ablation: Removing joint inference (e.g., using a single initial cover or sequential recovery) caused significant drops in Operator F1 (e.g., from 0.763 to 0.392), confirming that maintaining alternative hypotheses is critical for discovering complex relations.

5. Significance and Claims

The paper claims that accurate tracing alone is insufficient to recover reusable construction logic. By retaining alternative primitive hypotheses and jointly evaluating prototype sharing and executable operators, the framework produces compact, editable representations that preserve interpretable construction relations.

Heritage Documentation: The approach shifts heritage-pattern digitization from merely recording contours toward preserving inspectable construction models and explicit computational assumptions.
Editability: The recovered programs expose explicit controls for coordinated editing (e.g., changing a prototype updates all instances; modifying a repeat count adjusts the entire band), supporting the reconstruction and controlled reuse of heritage ornaments.
Transparency: The training-free design improves transparency by removing dependence on task-specific learned representations, relying instead on expert-designed primitives, operator vocabularies, and geometric tolerances.

The authors acknowledge limitations, noting that the method assumes cropped, high-contrast, rectilinear patterns and does not handle perspective distortion, curved strokes, or complex interlacing. However, the core inference strategy of maintaining alternative decompositions and jointly evaluating structure is presented as a general principle for structured ornament analysis.