Domino portrait generation: a fast and scalable approach

Hadrien Cambazard (), John Horan (), Eoin O’Mahony () and Barry O’Sullivan ()

Annals of Operations Research, 2011, vol. 184, issue 1, 79-95

Abstract: A domino portrait is an approximation of an image using a given number of sets of dominoes. This problem was first formulated in 1981 by Ken Knowlton in a patent application, which was finally granted in 1983. Domino portraits have been generated most often using integer linear programming techniques that provide optimal solutions, but these can be slow and do not scale well to larger portraits. In this paper we propose a new approach that overcomes these limitations and provides high quality portraits. Our approach combines techniques from operations research, artificial intelligence, and computer vision. Starting from a randomly generated template of blank domino shapes, a subsequent optimal 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 attractive as optimal ones. Combining techniques from computer vision and large neighborhood search we can quickly improve the portraits. Empirically, we show that we obtain many orders of magnitude reduction in search time. Copyright Springer Science+Business Media, LLC 2011

Date: 2011
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1007/s10479-010-0738-6 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:184:y:2011:i:1:p:79-95:10.1007/s10479-010-0738-6

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-010-0738-6

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().