Abstract
Generating domino portraits—images reconstructed using a fixed number of double-nine domino sets—is a complex combinatorial optimization problem. Traditional approaches using Integer Linear Programming (ILP) provide mathematically optimal results but suffer from poor scalability. This paper introduces a hybrid approach that combines minimum cost flow algorithms with computer vision-guided local search. The resulting algorithm produces portraits that are visually indistinguishable from optimal versions while achieving a speedup of several orders of magnitude.
Introduction
Domino portraits are a form of constrained mosaic art. Using "double nine" sets, which contain 55 unique dominoes ranging from 0-0 to 9-9, an artist must reconstruct a grayscale image. This task is governed by two primary constraints: a fixed palette (only one of each domino type per set) and integrity (dominoes must remain 1x2 units).
As the resolution of the target image or the number of domino sets increases, the search space for an optimal arrangement grows exponentially. While ILP can find the "perfect" fit, its computational cost makes it impractical for high-resolution artistic applications. This research aims to bridge the gap between fast but low-quality heuristics and slow optimal solvers.
Methodology
The core insight of the hybrid approach is that the optimization problem can be decomposed. The most difficult aspect is not the assignment of specific dominoes, but the determination of the "pattern"—the orientation (horizontal or vertical) of the 1x2 slots.
Minimum Cost Flow and Symmetry Breaking
Once a pattern of 1x2 slots is fixed, assigning dominoes to those slots to minimize grayscale error becomes a Minimum Cost Flow problem, which is solvable in polynomial time. To further enhance speed, the authors utilize symmetry breaking: since each domino type is repeated $k$ times across $k$ sets, they group identical costs into "areas," allowing the assignment to be solved in nearly constant time regardless of the number of sets.
Computer Vision-Guided Local Search
To optimize the initial pattern, the algorithm employs Large Neighborhood Search. However, rather than searching the entire image uniformly, it uses the FAST (Features from Accelerated Segment Test) corner detection algorithm. This identifies high-detail regions such as eyes and hair where human perception is most sensitive to errors. The local search prioritizes these "interesting" regions, ensuring high fidelity where it matters most.
Results and Discussion
The approach was evaluated using the portrait of George Boole, a standard benchmark for domino tiling. Portraits were generated using 1, 4, and 16 sets of dominoes (55, 220, and 880 dominoes, respectively).
The hybrid method achieved a runtime improvement of several orders of magnitude over traditional ILP methods. Crucially, the visual quality of the portraits remains high; the perceptual difference between these heuristic results and mathematically optimal solutions is negligible to the human eye. The algorithm proved robust, maintaining high performance even as the problem size scaled with additional domino sets.
Conclusion
By combining operations research techniques with computer vision, this work provides a highly scalable framework for domino portrait generation. This hybrid approach prioritizes perceptual optimality over absolute mathematical minimums, allowing for the rapid creation of high-quality computational art. Future work may extend this framework to other tiling problems or different domino set configurations.
Summary updated