在一个大的搜索一个小图像 [英] search for a small image in a big one

问题描述

我正在从一个大图像中搜索灰度图像。

I'm working on search a gray-scaled image from a big one.

这是我到目前为止做的，只需从左到右逐个像素搜索从右到上和从上到下，它是灰度的，所以我使用bool作为数据类型（1 ==黑色0 ==白色）。

Here's what I've done so far, simply search pixel by pixel from left to right and top to bottom, it's gray-scaled so I use bool as the data type (1==black 0==white).

#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;

}

我在寻找更好的算法

任何建议？

谢谢。

推荐答案

您可以将较大的图像解释为字符串，以应用字符串搜索算法，如'Boyer-Moore字符串搜索算法'（ http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm ）找到第一行的较小图像。找到该行后，您匹配以下行。

You might interpret the larger image as a string of bytes for applying a string-search algorithm like the 'Boyer–Moore string search algorithm' (http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm) to find the first line of the smaller image. After finding that line, you match the following lines.

但是，如果找不到较小的图像（未与较大图像中的字节边界对齐），则必须使用移动的较小图像重复搜索忽略第一个和最后一个字节），直到找到匹配或没有进一步的移位是可信的。

However, if the smaller image is not found (not aligned to a byte boundary in the larger image), you have to repeat the search using a shifted smaller image (temporary ignoring the first and last byte), until you find a match or no further shift is plausible.

这篇关于在一个大的搜索一个小图像的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！