Come implementare l'algoritmo di riempimento di piene su più macchine?

Parlando in modo molto astratto, l'etichettatura dei componenti connessi è un esempio di chiusura delle relazioni di equivalenza.

• All'inizio conosciamo solo le relazioni di equivalenza per alcune coppie di pixel. Nello specifico, conosciamo solo la relazione di equivalenza per i pixel vicini l'uno all'altro (adiacenti).
• Ogni pixel ha un colore, che è un valore binario (0 o 1). La relazione di equivalenza per pixel adiacenti (A, B) è definita come Color(A) == 1 AND Color(B) == 1
• Inoltre, i pixel sono già partizionati e memorizzati su macchine diverse. Se pixel (A, B) sono adiacenti ma sono partizionati in macchine diverse M(A) e M(B) , allora queste due macchine devono scambiarsi informazioni per scoprire se i due pixel si trovano nella relazione di equivalenza.
• Poiché l'attività è un esempio di chiusura delle relazioni di equivalenza, puoi sempre utilizzare un approccio divide et impera:
  • Esegui la chiusura delle relazioni di equivalenza all'interno di ciascuna partizione di pixel (a seconda di come sono archiviate tra le macchine). Fondamentalmente, gestisci il caso per tutte le coppie di pixel A e B adiacenti e dove M(A) e M(B) sono uguali, per ogni M .
  • Esegue la chiusura delle relazioni di equivalenza tra coppie di pixel situate su macchine diverse. In pratica, gestisci il caso in cui M(A) e M(B) sono diversi.
  • Esegui un ultimo round di aggiornamento delle etichette su ciascun pixel, per dare il risultato.

Esistono diverse possibili strategie di implementazione. La scelta influirà notevolmente sulle prestazioni e le prestazioni potrebbero essere influenzate dai dati di input. (In altre parole, la performance tra input best-case e input worst-case può essere significativa.)

Contributi utente concessi in licenza con cc by-sa 3.0 con attribuzione richiesta (politica dei contenuti)

• link
• link
• link
• link
• link

Vorrei usare un approccio di ampiezza. Dividi l'immagine grande in tessere e chiedi a ogni lavoratore di possedere una tessera, e anche sapere quali sono i suoi vicini. Riempi la prima tessera come di consueto. Se alcune località toccano il bordo della tessera e c'è un vicino in quella direzione, invia un messaggio al vicino con la posizione e le informazioni sul colore in modo che possa decidere se riempire o meno. A questo punto, ogni vicino di casa ripeterà questo processo fino a quando non verranno raggiunti i bordi della piastrella con i vicini.

Dichiarazione di non responsabilità: non ho mai implementato nulla di simile prima, e non so quale tipo di difetti potrebbe avere. Ci sono circa 5 minuti di riflessione sul problema e potrebbe essere necessario un cambiamento.