Calcolo della lunghezza degli oggetti nell'immagine binaria - algoritmo

Question

Ho bisogno di calcolare la lunghezza dell'oggetto in un'immagine binaria (distanza massima tra i pixel all'interno dell'oggetto). Poiché si tratta di un'immagine binaria, potremmo considerarla come una matrice 2D con valori 0 (bianco) e 1 (nero). La cosa di cui ho bisogno è un algoritmo intelligente (e preferibilmente semplice) per eseguire questa operazione. Tieni presente che ci sono molti oggetti nell'immagine.

L'immagine da chiarire: immagine in ingresso

alt text http://cl.ly/489019a048c1bf20c6bb/content

Esempio:

alt text http://cl.ly/f5c379e59deef435f365/content

Answer 1

Credo che il problema è semplice se il contorno di un oggetto è convessa e non tre vertici sono su una linea (cioè nessun vertice può essere rimossa senza cambiando il poligono): Poi si può semplicemente prendere due punti a caso e utilizzare un semplice gradiente-discesa tipo di ricerca per trovare la linea più lunga:

Start with random vertices A, B 
See if the line A' - B is longer than A - B where A' is the point left of A; if so, replace A with A' 
See if the line A' - B is longer than A - B where A' is the point right of A; if so, replace A with A' 
Do the same for B 
repeat until convergence 

Quindi io suggerirei di trovare il convesso per ogni blob seme, rimuovendo tutti i vertici "superflui" (per garantire la convergenza) e runn l'algoritmo sopra.

La costruzione di uno scafo convesso è un'operazione O (n log n) IIRC, dove n è il numero di pixel limite. Dovrebbe essere abbastanza efficiente per piccoli oggetti come questi. EDIT: Ho appena ricordato che l'O (n log n) per l'algoritmo dello scafo convesso era necessario per sort punti. Se i punti di confine sono il risultato di un'analisi dei componenti connessi, sono già ordinati. Quindi l'intero algoritmo dovrebbe essere eseguito in tempo O (n), dove n è il numero di punti di confine. (E 'un sacco di lavoro, però, perché potrebbe essere necessario scrivere il proprio algoritmo di convesso scafo o modificare uno per saltare l'ordinamento.)

Add: risposta al commento

Se non lo fai bisogno di precisione al 100%, si può semplicemente montare un'ellisse su ogni blob e calcolare la lunghezza dell'asse maggiore: questo può essere calcolato da central moments (IIRC è semplicemente la radice quadrata se è il più grande autovalore della matrice di covarianza), quindi è un O (n) operazione e può essere calcolato in modo efficiente in un'unica scansione sull'immagine. Ha l'ulteriore vantaggio di prendere in considerazione tutti i pixel di un blob, non solo di due punti estremi, cioè è molto meno influenzato dal rumore.

Answer 2

Un approccio molto grezzo, forza bruta sarebbe innanzitutto identificare tutti i pixel del bordo (qualsiasi pixel nero nell'oggetto adiacente a un pixel non nero) e calcolare le distanze tra tutte le possibili coppie di pixel del bordo. La più lunga di queste distanze ti darà la lunghezza dell'oggetto.

Se gli oggetti hanno sempre la forma di quelli del campione, è possibile velocizzarli valutando solo i pixel con i valori x e y più alti e più bassi all'interno dell'oggetto.

Answer 3

Suggerirei di provare una trasformazione di distanza "inversa". Nel magico mondo della morfologia matematica (scusa non ho potuto resistere all'allitterazione) la trasformazione della distanza ti dà la distanza più vicina di ogni pixel al suo pixel di confine più vicino. Nel tuo caso, ti interessa la distanza più lontana da un pixel di confine, quindi ho abilmente applicato un prefisso "reverse".

È possibile trovare informazioni sulla distanza di trasformazione here e here. Credo che MATLAB implementa la trasformazione a distanza come da here. Ciò mi porterebbe a credere che sia possibile trovare un'implementazione open source della trasformazione della distanza in octave. Inoltre, non mi sorprenderebbe minimamente se fosse stato implementato lo opencv.

Non ci ho pensato molto, ma è intuitivo per me che dovresti essere in grado di invertire la trasformazione della distanza e calcolarla in circa lo stesso tempo della trasformazione della distanza originale.

Answer 4

Penso che potresti prendere in considerazione l'utilizzo di un algoritmo breadth first search.

L'idea di base è quella di eseguire il loop su ogni riga e colonna dell'immagine e, se non si è ancora visitato il nodo (un nodo è una riga e una colonna con un pixel colorato), si eseguirà l'ampiezza prima ricerca Visiterai ogni nodo che potresti, e tieni traccia dei punti max e min per l'oggetto.

Ecco alcuni C++ codice di esempio (non testato):

#include <vector> 
#include <queue> 
#include <cmath> 
using namespace std; 

// used to transition from given row, col to each of the 
// 8 different directions 
int dr[] = { -1, 0, 1, -1, 1, -1, 0, 1 }; 
int dc[] = { -1, -1, -1, 0, 0, 1, 1, 1 }; 

// WHITE or COLORED cells 
const int WHITE = 0; 
const int COLORED = 1; 

// number of rows and columns 
int nrows = 2000; 
int ncols = 2000; 

// assume G is the image 
int G[2000][2000]; 

// the "visited array" 
bool vis[2000][2000]; 

// get distance between 2 points 
inline double getdist(double x1, double y1, double x2, double y2) { 
    double d1 = x1 - x2; 
    double d2 = y1 - y2; 
    return sqrt(d1*d1+d2*d2); 
} 

// this function performs the breadth first search 
double bfs(int startRow, int startCol) { 
    queue<int> q; 

    q.push(startRow); 
    q.push(startCol); 

    vector< pair< int, int > > points; 

    while(!q.empty()) { 
    int r = q.front(); 
    q.pop(); 
    int c = q.front(); 
    q.pop(); 

    // already visited? 
    if (vis[r][c]) 
     continue; 


    points.push_back(make_pair(r,c));  

    vis[r][c] = true; 

    // try all eight directions 
    for(int i = 0; i < 8; ++i) { 
     int nr = r + dr[i]; 
     int nc = c + dc[i]; 

     if (nr < 0 || nr >= nrows || nc < 0 || nc >= ncols) 
     continue; // out of bounds 

     // push next node on queue 
     q.push(nr); 
     q.push(nc); 

    }  
    } 

    // the distance is maximum difference between any 2 points encountered in the BFS 
    double diff = 0; 
    for(int i = 0; i < (int)points.size(); ++i) { 
    for(int j = i+1; j < (int)points.size(); ++j) { 
     diff = max(diff,getdist(points[i].first,points[i].second,points[j].first,points[j].second)); 
    } 
    } 
    return diff; 
} 

int main() { 

    vector<double> lengths; 

    memset(vis,false,sizeof vis); 
    for(int r = 0; r < nrows; ++r) { 
    for(int c = 0; c < ncols; ++c) { 
     if (G[r][c] == WHITE) 
     continue; // we don't care about cells without objects 
     if (vis[r][c]) 
     continue; // we've already processed this object 

     // find the length of this object 
     double len = bfs(r,c); 
     lengths.push_back(len); 
    } 
    } 

    return 0; 
} 

Answer 5

Trova la lunghezza dell'asse maggiore dell'ellisse che ha gli stessi secondi secondi centrali normalizzati della regione. In MATLAB puoi usare regionprops.