Quante combinazioni di pixel di K vicino sono lì in un'immagine?

Question

Succhio in matematica, quindi non riesco a capirlo: quante combinazioni di k pixel di K sono lì in un'immagine?Combinazioni di K Pixels da n * n Totale pixel nell'immagine, ma con la restrizione che devono essere vicini, per ogni K da 2 a n * n.Ho bisogno della somma per tutti i valori di K per un programma che deve tenere conto di molti elementi in un set di cui è un ragionamento.

I vicini sono a 4 collegati e non si avvolgono.

Answer 1

Una volta ottenuto il numero di forme distinte per un blob di pixel di taglia k ( qui è un riferimento ) Quindi si tratta di due cose:

.
• Quanti modi sulla tua immagine puoi posizionare questo BLOB?
• Quanti di questi sono gli stessi, in modo da non contare a doppio conto (a causa delle simmetrie)?

Ottenere una risposta esatta è un enorme lavoro computazionale (stai guardando più di 10 ^ 30 forme distinte per K= 56 - Immagina se k= 10.000) ma potresti essere in grado di ottenere abbastanza bene per quello di cui hai bisognoadatto per i primi 50 valori di K.

(Nota: il riferimento nell'articolo Wikipedia si occupa dei duplicati con la loro definizione di A_K.)

Answer 2

Sembra che tu stia lavorando su un problema che può essere mappato a Markovian Walks.

Se capisco la tua domanda, stai cercando di contare i percorsi di lunghezza K come questo:

Start          (end)-> any pixel after visiting k neighbours
*     - - - - -*
|     |
|     |
- - - -

.

in una struttura simile a una scacchiera e si desidera collegare solo i vicini verticali e orizzontali.

Penso che tu voglia che i percorsi siano autosufficienti, il che significa che un pixel non dovrebbe essere attraversato due volte in una passeggiata (che significa non loop). Questa condizione porta a un problema classico chiamato SAWS (Autospirando le passeggiate).

Bene, ora le cattive notizie: il problema è aperto! Nessuno lo ha risolto ancora.

Puoi trovare una bella introduzione al problema qui , A partire da pagina 54 (o pagina 16, il conteggio è confuso perché i numeri di pagina stanno ripetendo nel DOC). Ma l'intera carta è molto interessante e facile da leggere. Gestisce di spiegare lo sfondo matematico, gli aneddoti storici e l'importanza scientifica delle catene Markovian in poche scivoli.

Spero che questo aiuti ... per evitare il problema.

Answer 3

Se hai intenzione di integrare su tutto il possibile poliminos , temo te 'Aspettando molto tempo.Dal sito di Wikipedia su Polyominos, sarà almeno o (4.0626 ^ n) e probabilmente più vicino a O (8 ^ N).Quando n= 14, il conte sarà superiore a 5 miliardi e troppo grande per adattarsi a un int.Nel tempo n= 30, il conte sarà più di 17 quintillion e non sarai in grado di adattarlo a lungo.Se tutti i governi mondiali hanno raccolto insieme le loro risorse per iterano attraverso tutti i Polyominos in un'icona 32 x 32, non sarebbero in grado di farlo prima che il sole vada Supernova.

Ora che non significa quello che vuoi fare è intrandibile.È probabile che quasi tutto il lavoro che fai su un polyminal sia stato fatto in parte sugli altri.Potrebbe essere un compito divertente effettuare una velocità esponenziale utilizzando la programmazione dinamica.Cosa stai cercando di realizzare?