搜索小图像中的大单 [英] search for a small image in a big one
问题描述
我正在寻找一个灰阶图像从一个大的。
I'm working on search a gray-scaled image from a big one.
下面是我做了什么,到目前为止,只需搜索逐像素从左至右,从上到下,它的灰阶所以我用布尔作为数据类型(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;
}
我在找一些更好的算法,它具有更好的性能。
I'm looking for some better algorithm that with better performance.
任何意见?
感谢。
推荐答案
您可能会跨preT的放大图像作为申请的字符串搜索算法,如博耶 - 穆尔字符串搜索算法字节的字符串( 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屋!