큰 이미지에서 작은 이미지 검색

Question

큰 이미지에서 회색조 이미지를 검색하고 있습니다.

여기까지는 픽셀 단위로 픽셀을 왼쪽에서 오른쪽으로 그리고 위에서 아래로 검색 했으므로 회색으로 표시되므로 bool을 데이터 형식 (1 == 검정 0 == 흰색)으로 사용했습니다.

#include <iostream> 
using namespace std; 

template <int WIDTH, int HEIGHT> 
struct array { 
    bool data[WIDTH][HEIGHT]; 
    int width() { return WIDTH; } 
    int height() { return HEIGHT; } 

    void random_fill() { 
     for(int row=0; row<HEIGHT; row++) { 
      for(int col=0; col<WIDTH; col++) { 
       data[row][col] = (row*col+col*col) % 3 == 0 ? 1 : 0; 
      } 
     } 
    } 
    void display() { 
     cout << "array content:" << endl; 
     for(int row=0; row<HEIGHT; row++) { 
      for(int col=0; col<WIDTH; col++) { 
       cout << data[row][col] << " "; 
      } 
      cout << endl; 
     } 
    } 
    void operator=(bool _data[WIDTH][HEIGHT]) { 
     memcpy(data, _data, WIDTH*HEIGHT); 
    } 
}; 

struct point { 
    int x; 
    int y; 
}; 

// test if a sub-rect of a big_rect matches a small rect 
template <typename big_t, typename small_t> 
bool rect_match(big_t& big_arr, int x_offset, int y_offset, small_t& small_arr) { 
    int w = small_arr.width(), 
     h = small_arr.height(); 
    for(int row=0; row<h; row++) { 
     for(int col=0; col<w; col++) { 
      if(big_arr.data[row+y_offset][col+x_offset] != small_arr.data[row][col]) 
       return false; 
     } 
    } 
    return true; 
} 

// search for a small_rect in a big_rect 
template <typename big_t, typename small_t> 
point search(big_t& big_arr, small_t& small_arr) { 
    point pt; 
    for(int row=0; row<big_arr.height()-small_arr.height(); row++) { 
     for(int col=0; col<big_arr.width()-small_arr.width(); col++) { 
      if(rect_match(big_arr, col, row, small_arr)) { 
       pt.x = col; 
       pt.y = row; 
       return pt; 
      } 
     } 
    } 

    pt.x = pt.y = -1; 
    return pt; 
} 

int main() { 
    array<10, 10> big_arr; 
    big_arr.random_fill(); // fill the sample image with some "random" color 
    big_arr.display(); 

    array<3, 3> small_arr; 
    bool data[3][3] = {{1,0,1},{0,0,1},{0,1,1}}; 
    small_arr = data; 
    small_arr.display(); 

    point pt = search(big_arr, small_arr); 
    cout << "pt: (" << pt.x << ", " << pt.y << ")" << endl; 

} 

더 나은 성능을 갖춘 알고리즘을 찾고 있습니다.

어떤 조언이 필요합니까?

감사합니다.

Answer 1

더 큰 이미지는 'Boyer-Moore 문자열 검색 알고리즘'(http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm)과 같은 문자열 검색 알고리즘을 적용하여 작은 이미지의 첫 번째 줄을 찾는 데 사용할 수 있습니다. 그 라인을 찾으면 다음과 일치합니다.

그러나 더 작은 이미지가 발견되지 않으면 (큰 이미지에서 바이트 경계에 정렬되지 않은 경우), 찾을 때까지 이동 한 더 작은 이미지 (첫 번째 및 마지막 바이트를 일시적으로 무시)를 사용하여 검색을 반복해야합니다 일치 또는 더 이상의 이동은 그럴듯합니다.