快速内存块的匹配算法！

Bosee 2007-06-18 12:39:12

其实是在一块大图片中查找其中的一块小图片，我已经把其内容的内存块取出，写了一个最笨的匹配算法，4层嵌套循环逐个象素比较，能正确找到图片位置，但速度很慢（在1024*1280图片中查找16*16图片，极端情况下要比较(1024-16)*(1280-16)*16*16次，在800Mhz电脑上需要3秒，需求起码要快10倍）。哪位大哥能推荐一款最快速的算法吗？非常感谢！

...全文

370 8 打赏收藏转发到动态举报

写回复

用AI写文章

8 条回复

切换为时间正序

请发表友善的回复…

发表回复

boris_cui 2007-06-19

打赏
举报

mark

mLee79 2007-06-18

打赏
举报

这东西不应该用 vb 搞的吧, 用 c 很快的, 即使最简单的写法, 一次也不应该超过 100 毫秒的吧, 简单的试了试, 在PM1.4G 上大概10毫秒 .....

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

typedef unsigned long pixClr;

#define WIDTH (1024)
#define HEIGHT (1280)
#define SCANLINE_DLEN (1024)
#define SUBWIDTH (16)
#define SUBHEIGHT (16)

#define XALGO_preKMP( __patt__ , __p_len__ , __i__ , __j__ , __kmp_Next__ , __compare_eq_xi_xj__ , __N_TYPE__ ) \
do { \
(__i__) = 0; (__j__) = (__kmp_Next__)[0] = (__N_TYPE__)(-1); \
while( (__i__) < (__p_len__) ) { \
while( (__j__) > -1 && ! (__compare_eq_xi_xj__) ) \
(__j__) = (__kmp_Next__)[ (__j__) ]; \
++ (__i__); ++ (__j__); \
if( (__compare_eq_xi_xj__) ) \
(__kmp_Next__)[(__i__)] = (__kmp_Next__)[(__j__)]; \
else \
(__kmp_Next__)[(__i__)] = (__N_TYPE__) (__j__); \
} } while(0)

#define XALGO_KMP( __patt__ , __p_len__ , __src__ , __s_len__ , __i__ , __j__ , __kmp_Next__ , __compare_eq_xi_yj__ , __pattern_find_do__ ) \
do { \
while( (__j__) <= (__s_len__) - (__p_len__) ) { \
while( __i__ > -1 && !(__compare_eq_xi_yj__) ) \
(__i__) = (__kmp_Next__) [ __i__ ]; \
++ (__i__) ; ++ (__j__); \
if( (__i__) >= (__p_len__) ) { \
__pattern_find_do__ ; \
(__i__) = (__kmp_Next__) [ __i__ ]; } \
} } while(0)

pixClr picture[ HEIGHT ][ SCANLINE_DLEN ];
pixClr subpic [ SUBHEIGHT ][ SUBWIDTH ];

void check1( int i , int j )
{
int x ;
for( x = 1; x < SUBHEIGHT; ++x )
{
if( 0 != memcmp( picture[ i + x ] + j , subpic[ x ] , SUBWIDTH * sizeof( pixClr ) ) )
return ;
}
printf( "match @ %d %d\n" , i , j );
}

#define USE_KMP

void slove()
{
int i ;
#ifdef USE_KMP
int kmpNext[ SUBWIDTH + 1 ] , j;
#endif

pixClr *begin = picture[0] , *ptr = begin , *end = picture[ HEIGHT - SUBHEIGHT ];

#ifdef USE_KMP
XALGO_preKMP( subpic[0] , SUBWIDTH , i , j , kmpNext , subpic[0][i] == subpic[0][j] , int );

for( ; ptr != end; ptr += SCANLINE_DLEN )
{
i = j = 0;
XALGO_KMP( subpic[0] , SUBWIDTH , ptr , WIDTH , i , j , kmpNext , subpic[0][i] == ptr[j] ,
check1( (ptr-begin)/SCANLINE_DLEN , j - i ) );
}
#else
for( ; ptr != end; ptr += SCANLINE_DLEN )
{
for( i = 0; i < WIDTH - SUBWIDTH; ++i )
{
if( 0 == memcmp( ptr + i , subpic[0] , SUBWIDTH * sizeof( pixClr ) ) )
check1( (ptr-begin)/SCANLINE_DLEN , i );
}
}
#endif
}

int main()
{
int xx;
srand( time(0) );
for( xx = 0; xx < 100; ++xx )
{
int i , j , i0 , j0;
clock_t clk ;

printf( "------round %d -------\n" , xx );

for( i = 0; i < WIDTH ; ++i )
for( j = 0; j < HEIGHT; ++j )
picture[j][i] = rand();

i0 = rand() % (WIDTH - SUBWIDTH);
j0 = rand() % (HEIGHT - SUBHEIGHT - 500) + 500;

for( i = 0; i < SUBWIDTH; ++i )
for( j = 0; j < SUBHEIGHT; ++j )
subpic[j][i] = picture[j+j0][i+i0];

clk = clock();
slove();
printf( "%d %d : time used %lg(sec)\n" , j0 , i0 , 1. * ( clock() - clk ) / CLOCKS_PER_SEC );
}

return 0;
}

fire_woods 2007-06-18

打赏
举报

用c语言写会快很多.

Bosee 2007-06-18

打赏
举报

其中rgqSource是大图片数组，rgqMatch是小图片数组。

Bosee 2007-06-18

打赏
举报

相关代码如下(VB)：
blnMatch = False
For i = 0 To UBound(rgqSource, 2) 'height
For j = 0 To UBound(rgqSource, 1) 'width
For m = 0 To UBound(rgqMatch, 2) 'height
For n = 0 To UBound(rgqMatch, 1) 'width
v = i + m 'height
w = j + n 'width
If w <= UBound(rgqSource, 1) And v <= UBound(rgqSource, 2) Then
If rgqSource(w, v) <> rgqMatch(n, m) Then
GoTo NextCol
End If
Else
GoTo NextRow
End If
Next
Next
blnMatch = True
GoTo NextStep
NextCol:
Next
NextRow:
Next

NextStep:
If blnMatch = True Then
MsgBox "Match! X: " & j & ", Y: " & i
Else
MsgBox "Not Match!"
End If

halve 2007-06-18