A SAT-Based Parser and Completer for Pictures Specified by Tiling (Articolo in rivista)

Type
Label
  • A SAT-Based Parser and Completer for Pictures Specified by Tiling (Articolo in rivista) (literal)
Anno
  • 2008-01-01T00:00:00+01:00 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#doi
  • 10.1016/j.patcog.2007.06.018 (literal)
Alternative label
  • M. Pradella, S. Crespi Reghizzi (2008)
    A SAT-Based Parser and Completer for Pictures Specified by Tiling
    in Pattern recognition; Academic Press Elsevier, Amsterdam (Paesi Bassi)
    (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
  • M. Pradella, S. Crespi Reghizzi (literal)
Pagina inizio
  • 555 (literal)
Pagina fine
  • 566 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume
  • 41 (literal)
Rivista
Note
  • Scopus (literal)
  • ISI Web of Science (WOS) (literal)
  • Google Scholar (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni
  • Politecnico di Milano (literal)
Titolo
  • A SAT-Based Parser and Completer for Pictures Specified by Tiling (literal)
Abstract
  • Pictures or patterns have been formally specified by different methods such as grammars. An alternative approach is based on tiling systems (TS) (Wang tiles are an analogous and equivalent formalism), whereby the picture is obtained by first covering it with a specified set of 2 × 2 tiles, then by performing a pixel by pixel mapping. TS are a powerful technique: the corresponding pictures can be recognized by non-deterministic cellular automata, which are more powerful than the four-ways automata. The difficulty to write such specifications for non- elementary pictures, and the NP-complete computational complexity of TS picture recognition have so far blocked any attempt to application. We have implemented a recognizer and generator for TS pictures in a very attractive, unconventional way, by transforming the tiling problem into a SAT (Boolean satisfiability) one, then using an efficient off-the-shelf SAT-solver. The prototype is fast enough to experiment on reasonably sized samples, and has the bonus of being able to complete or extrapolate a partial or noisy picture. The tool is invaluable to assist in writing picture specification. A series of examples shows how to specify patterns using TS. (literal)
Editore
Prodotto di
Autore CNR
Insieme di parole chiave

Incoming links:


Prodotto
Autore CNR di
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi
Editore di
Insieme di parole chiave di
data.CNR.it