Algoritmo sequenziale / parallelo per l'estrazione del perimetro esterno del blob / lunghezza del contorno

Suppongo che tu non stia perseguendo il calcolo della GPU solo per il gusto di farlo. In altre parole, sei disposto a prendere in considerazione la CPU o le "tecniche tradizionali", confrontando più tecniche e, infine, scegliendo qualunque cosa offra le massime prestazioni, invece di dover continuare a utilizzare la GPU per fare una tesi.

Trovo che l'algoritmo Chain Code (Contour Tracing) sia sufficiente per l'attività, se successivamente le coordinate del contorno vengono lisce.

In termini di concorrenza e parallelismo

Se viene fornita una raccolta di punti di partenza per la tracciatura del contorno, la tracciatura del contorno può essere eseguita indipendentemente da ciascun agente che lavora su un punto iniziale. Ciò è possibile perché la tracciatura del contorno non è distruttiva sull'immagine o sulla matrice dell'etichetta - legge solo i valori vicini attorno alla posizione corrente.

Tuttavia, la tracciatura del contorno non è parallela ai dati. In altre parole, non può essere vettorizzato in una macchina SIMD o SPMD.

• I contorni possono avere lunghezze drasticamente differenti. Quindi, alcuni agenti finiranno presto, altri finiranno tardi. Non avranno schemi di controllo del flusso coerenti.
• Inoltre, i motivi di accesso alla memoria saranno sparsi su tutta l'immagine. Sarà anche molto dispendioso nelle cache della CPU - da ogni linea della cache, forse solo fino a tre valori di pixel saranno effettivamente significativi per l'algoritmo di tracciamento del contorno.

Esiste un algoritmo divide et impera per il tracciamento del contorno di un singolo blob?

Non lo so. Si prega di lasciare un commento se ne trovi uno, perché mi piacerebbe conoscere anche questo. Non ho fatto una ricerca seria nella letteratura, quindi potrei essere ignorante. (Ovviamente dovresti nasconderlo se costituirà la spina dorsale della tua tesi.)

D'altra parte, ho implementato un algoritmo basato su tessere per l'etichettatura dei componenti connessi, basato sull'etichettatura di ciascuna piastrella in modo indipendente e sul follow-up con un processo di "cucitura cuciture", e terminato con un'assegnazione dell'etichetta finale. Non è parallelo ai dati (non SIMD / SPMD) ma è altamente parallelizzabile - l'immagine può essere divisa in centinaia o migliaia di tessere.

Per quanto riguarda le prestazioni.

In un progetto precedente in cui ho utilizzato il tracciamento del contorno, sono rimasto piacevolmente sorpreso dal fatto che gli algoritmi di tracciamento del contorno sono in generale molto più veloci del tempo di esecuzione per gli algoritmi di etichettatura dei componenti connessi, per il tipo di immagini che ho elaborato, perché la tracciatura del contorno non eseguire tutte le operazioni di memoria richieste dall'etichettatura dei componenti collegati.

Si noti che, in generale, la tracciatura del contorno e l'etichettatura dei componenti collegati non sono sostituzioni dirette l'una dell'altra: forniscono output in rappresentazioni diverse, nonostante le uscite corrispondenti allo stesso blob. Potrebbe essere necessario eseguire entrambi gli algoritmi: etichettare prima l'intera immagine, campionare i "punti di partenza del contorno" e tracciare i contorni di ciascuno di essi.

Ricerca di componenti connessi nidificati.

Esiste un algoritmo di tracciamento del contorno migliorato che risolve la relazione dei componenti connessi nidificati.

• Dato il contorno del componente connesso esterno,
• Converti la sequenza del codice catena in una sequenza di marker.
  • Esistono due tipi di indicatori:
    1. Segna il bordo più a sinistra (inizia la posizione X) di una corsa orizzontale di pixel
    2. Segna il bordo più a destra (fine posizione X) di una corsa orizzontale di pixel
       • Quale indicatore viene generato per il codice catena attuale dipende dall'orientamento del codice catena corrente.
• Ordina la sequenza dei marcatori in base alla posizione verticale Y (maggiore), quindi in base alla posizione X (minore).
• La sequenza di marker ordinati diventa quindi un descrittore raster run-length del blob circondato dal contorno.

Livella le coordinate del contorno in virgola mobile.

Il livellamento delle coordinate del contorno farà sì che cambi da discreto (interi) a virgola mobile. Dopodiché, scoprirai che la somma della distanza Euclidea a coppie è abbastanza buona per la maggior parte degli scopi.

Il dettaglio esatto della levigatura non è importante - per esempio, puoi usare il livellamento gaussiano, applicandolo alla sequenza delle coordinate X e Y del contorno proprio come una convoluzione 1D. Tieni presente la natura circolare (periodica / avvolgente) della sequenza.

Per trovare i confini circolari, ho trovato che la Hough Transform è molto utile, specialmente se conosci il intervallo approssimativo di raggi che potresti avere nell'immagine.