快速内存块的匹配算法!
其实是在一块大图片中查找其中的一块小图片,我已经把其内容的内存块取出,写了一个最笨的匹配算法,4层嵌套循环逐个象素比较,能正确找到图片位置,但速度很慢(在1024*1280图片中查找16*16图片,极端情况下要比较(1024-16)*(1280-16)*16*16次,在800Mhz电脑上需要3秒,需求起码要快10倍)。哪位大哥能推荐一款最快速的算法吗?非常感谢!
[解决办法]
代码贴出来也许可以优化
[解决办法]
找一下KMP算法的资料,应该会有帮助
[解决办法]
这东西不应该用 vb 搞的吧, 用 c 很快的, 即使最简单的写法, 一次也不应该超过 100 毫秒的吧, 简单的试了试, 在PM1.4G 上大概10毫秒 .....
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
typedef unsigned long pixClr;
#defineWIDTH(1024)
#defineHEIGHT(1280)
#defineSCANLINE_DLEN(1024)
#defineSUBWIDTH(16)
#defineSUBHEIGHT(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)
pixClrpicture[ HEIGHT ][ SCANLINE_DLEN ];
pixClrsubpic [ 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
voidslove()
{
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;
}