A Hybrid Approach to Domino Portrait Generation

Abstract

A domino portrait is an approximation of an image using a given number of sets of dominoes. This problem was first stated in 1981. Domino portraits have been generated most often using integer linear programming techniques that pro-vide optimal solutions, but these can be slow and do not scale well. We demonstrate a new approach that overcomes these limitations and provides high quality portraits. Our software combines techniques from operations research, artificial in-telligence, and computer vision. Starting from a randomly generated template of blank domino shapes, a subsequent op-timal placement of dominoes can be achieved in constant time when the problem is viewed as a minimum cost flow. The domino portraits one obtains are good, but not as visually at-tractive as optimal ones. Combining techniques from com-puter vision and local search we can improve our portraits to be visually indistinguishable from those generated optimally.