이진 이미지에서 객체의 길이 계산 - 알고리즘

Question

이진 이미지에서 객체의 길이를 계산해야합니다 (객체 내부의 픽셀 사이의 최대 거리). 이진 이미지이기 때문에 값이 0 (흰색)과 1 (검정) 인 2D 배열로 간주 할 수 있습니다. 필요한 것은이 작업을 수행하는 영리한 알고리즘입니다. 이미지에는 많은 오브젝트가 있음을 명심하십시오.

이미지 명확히 :

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

샘플 입력 화상 :

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

Answer 1

나는 물체의 경계가 볼록 인 경우 문제가 간단하다 생각에는 3 개 개의 꼭지점은 라인에 없다 (즉, 어떤 정점이없이 제거 할 수 없습니다 :

여기 (안된) 일부 C++ 샘플 코드입니다) 다각형을 변경 : 그럼 당신은 그냥 무작위로 두 점을 선택하고 긴 라인을 찾기 위해 간단한 그라데이션 하강 형 검색을 사용할 수 있습니다

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 

그래서 나는 각각의 종자에서 얼룩 볼록 선체를 찾는 게 좋을 것를, 모든 "superfluos"정점 제거 (수렴을 위해) 및 runn 위의 알고리즘.

convex hull은 O (n log n) 연산 IIRC입니다. 여기서 n은 경계 픽셀 수입니다. 이런 작은 객체에 대해서는 꽤 효율적이어야합니다. EDIT : 나는 단지 convex Oull 알고리즘을위한 O (n log n)가 점이 필요하다는 것을 기억했다. 경계 지점이 연결된 구성 요소 분석의 결과 인 경우 경계 지점은 이미 정렬되어 있습니다. 따라서 전체 알고리즘은 O (n) 시간에 실행되어야합니다. 여기서 n은 경계 지점의 수입니다. (당신이 당신의 자신의 볼록 선체 알고리즘을 작성하거나 정렬을 건너 뛸 하나를 수정 할 수 있기 때문에 많은 일을하지만,입니다.)

추가 : 그렇게하지 않으면 응답

을 언급 100 % 정확도가 필요하다면 각 얼룩에 타원을 맞추고 주축의 길이를 계산할 수 있습니다. 이것은 central moments (IIRC는 공분산 행렬의 최대 고유치 인 경우 IIRC)에서 계산할 수 있으므로 O (n) 연산을 수행하며 이미지에 대해 한 번의 스위프로 효율적으로 계산할 수 있습니다. 블로 브의 모든 픽셀을 고려해야한다는 추가 이점이 있습니다. 단지 두 개의 극점이 아니라 노이즈에 의한 영향이 훨씬 적습니다.

Answer 2

매우 조, 무차별 접근은 우선 에지 픽셀들을 식별하는 것 (존재 블랙 픽셀 이외의 픽셀에 인접한 오브젝트의 블랙 픽셀)을 계산하고 모든 가능한 에지 픽셀 쌍 사이의 거리를 계산합니다. 이 거리 중 가장 긴 거리는 물체의 길이를 알려줍니다.

개체가 항상 샘플에있는 것과 같은 모양이라면 개체 내의 가장 높은 값과 가장 낮은 x 값과 y 값을 가진 픽셀을 평가하면됩니다.

Answer 3

"역방향"거리 변환을 시도하는 것이 좋습니다. 수학적 형태학의 마법 세계 (미안하지만 이성에 저항 할 수 없음)에서 거리 변환은 각 픽셀과 가장 가까운 경계 픽셀 간의 가장 가까운 거리를 제공합니다. 귀하의 경우, 당신은 경계 픽셀까지 가장 먼 거리에 관심이 있습니다. 따라서 나는 "역"접두사를 똑똑하게 적용했습니다.

거리 변환 here 및 here에 대한 정보를 찾을 수 있습니다. Matlab은 here에 따라 거리 변환을 구현한다고 생각합니다. 그러면 octave에서 거리 변환의 오픈 소스 구현을 찾을 수 있다고 생각하게 될 것입니다. 또한, 적어도 opencv을 구현하면 놀라지 않을 것입니다.

나는 그다지 생각하지 못했지만, 직관적 인 것은 거리 변환을 되돌리고 원래의 거리 변환과 대략 같은 시간으로 계산할 수 있어야한다는 것입니다.

Answer 4

breadth first search 알고리즘을 사용해보십시오.

기본적인 아이디어는 이미지의 각 행과 열을 반복하는 것이며 노드를 방문하지 않은 경우 (노드는 유색 픽셀이있는 행과 열입니다) 아직 너비가 첫 번째 검색. 가능한 각 노드를 방문하고 객체의 최대 및 최소 점을 추적합니다.

#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

정규화 된 두 번째 중심 모멘트가 지역과 동일한 타원의 장축 길이를 찾습니다. MATLAB에서는 regionprops을 사용할 수 있습니다.