多线程加速图像模板匹配

多线程加速图像模板匹配
2010年09月05日
　　多线程加速图像模板匹配
　　首先这是个没有什么很好的结局的故事。所以下面这点文字不是为了表现一个怎么怎么好的结果，而是整个让人头疼的过程。
　　多线程加速算法的实现，不是对于算法本身的优化。而只是针对算法理论的编程实现过程中采用的技巧这里采用的算法是基于灰度的相关函数法。而一般实现图像处理算法的代码示例，都是单线程（即主线程）操作，这样的弊端至少有两点：一是速度很慢，尤其对于这里所用的计算量巨大的模板匹配算法，时间复杂度为  。二是主线程进行图像处理的运算，将导致主程序无法进行其他操作和响应，如窗口重绘、鼠标操作等等，相当于卡死状态。把多线程编程应用在此，是一次尝试。到今天为止，也只完成了程序的基本功能，一直都在测试，一直都存在小问题，鲁棒性只能与菲律宾警察一个级别。现在把基本的过程写一写，留做多年后自嘲的凭据吧:-)。
　　【DIB位图】
　　程序只兼容dib图像，所以用大家都见过的一个CDib类完成一般性操作。这个类的具体实现，网上应该有很多代码可以找，择而用之。不过在这里只需要用到三四个基本的功能就够了。
　　【算法计时】
　　单线程处理的函数也不必详述，这里只是为了与多线程做个对照，看加速的效果如何。当然，为了衡量计算速度，我这里是计算了耗时长短。例如： clock_t start; clock_t finish; float duration; start = clock();//开始计时 //do something finish = clock();//结束计时 duration = (double)(finish - start) / CLOCKS_PER_SEC; //可以精确到微秒，具体请参考MSDN         
　　
　　【规范返回值】
　　模板匹配的最终目的是在源图像中确定模板图像的位置，事实上只要知道一个点就可以定位，比如模板左上角点在源图像中的相对坐标。于是我定义了这样一个结构体来作为处理函数的返回值： struct CalcReport { CPoint lefttop; CPoint rightbottom; double duration; BOOL isValid; };       这样的好处在于处理结果可作为一个整体返还给调用函数，结构清晰，同时调用函数只需声明一个结构体，用处理函数进行填充，本程序中为view类成员调用doc类成员。在一定程度上是对doc类成员实现细节的隐蔽。
　　单线程处理返回值获取后，使用设备上下文对象在活动视图区绘制模板位置。这里遇到过一个纠缠了很久的问题。原因在于只顾使用别人封装好的类，而忽略了位图数据结构的特点。在此感谢方毅，多谢他的提示。
　　【关于多线程】
　　多线程就像那种你曾在传闻中听到的有多么神秘而又吸引人的异性，直到你亲眼去看了、亲身去相处了，才会发现其实也不过如此。一句题外话，对于一般人而言，Windows编程永远没有真正的懂与不懂。知道就是TRUE，不知道就是FALSE。Don't ask me why, just use it. 如果你连use都不会，要么是因为你不自信，要么是你过于理想化--不自信的人觉得自己不可能掌握它的用法，过于理想化的人总想自己使用自己的操作系统。
　　多线程属于你只管去用的东西之一。
　　另外想说一说的想法是，MFC并提供自己相应的线程类CWinThread，在网上你还可能会看到一些老手封装好的CThread类，但作为初学者，我还是倾向于自己使用平台SDK的函数： HANDLE CreateThread( LPSECURITY_ATTRIBUTES lpThreadAttributes, // pointer to security attributes DWORD dwStackSize, // initial thread stack size LPTHREAD_START_ROUTINE lpStartAddress, // pointer to thread function LPVOID lpParameter, // argument for new thread DWORD dwCreationFlags, // creation flags LPDWORD lpThreadId // pointer to receive thread ID );       一般会用到的参数主要是lpStartAddress、lpParameter这两个。前者为线程函数的地址，后者为线程的启动参数。简单地说，就是你决定开辟一个新的线程去做某件事，并且给这个新线程一个预备好的参数，如此而已。其他几个参数个人感觉用到的机会不多，详细说明MSDN上面很详细。
　　返回值是一个线程句柄，如果你想在启动这个线程后还能找到它，就去接收它保存好。比如你要在什么时候调用TerminateThread()，它的参数就是线程句柄。
　　另外两个问题，一个是多线程对于同一资源或者变量的访问权控制，二是线程同步。前者应当属于线程的并发控制，但我非专业，没有系统学过，只能明白其大意。后者是对于多个线程的执行顺序等问题的控制，也属于比较头疼的问题。幸而在这个程序中我可以回避这两个问题。
　　接下来是线程函数，这是多线程的核心代码之一。 DWORD WINAPI ThreadProc( LPVOID lpParameter // thread data );      参数只有一个，可以指向任意数据类型的长指针。于是就遇到了另一个麻烦，线程函数的参数传递。
　　【线程函数传参】
　　这是整个编写过程中最抓狂的一部分。
　　在说传参之前，要说一说线程函数在Visual C++/Visual Studio环境下几个特点。首先线程函数不能以某个类的普通成员函数出现，会有编译错。具体如何的提示我必然回忆不起来，有兴趣的朋友可以去试一试。基于这样一个缘故，线程函数可以写成某个类的静态成员函数或者全局函数，但一旦你写成了全局函数，csdn上的一些朋友又要说你违背OO了:-D。记得孙鑫在他的教程中说过这么一句话，大意是，如果你的老板要求这个工程中不出现全局函数，即维持代码的OO特性，你就将线程函数放到一个类中加一个static关键字。其次，线程函数还有一些我不知道怎么说的奇怪之处，于我而言其中一些是不可知的错误。可以参考一下这个帖子，同时感谢论坛上这些不认识的朋友给我的指点：http://topic.csdn.net/u/20100901/23/6b2ac224-81c6- 42b3-91e5-aae1c6759373.html 。
　　再回到传参的问题。显而易见的是，线程启动参数只允许一个，这类回调函数都是Windows默认约定的，应该是不能手动修改，与资环的喻世江讨论了一下，也在此谢过，这个高手以前给过我很多帮助。
　　模板匹配需要哪些已知参数？源图像数据块，模板图像数据块--这是至少有的两个。
　　对于这个程序中独立的线程函数需要什么参数？可能设计就不尽相同了。
　　最开始的构想，是doc类保存源图像的数据，然后设法在线程函数内部获取这个数据段的指针。大概思路是首先获取theApp对象的指针，继而是MainFrame、View、Doc，从而获得文档类数据成员的指针。但是在写代码的时候发现总会有运行错。当时调试的时候是什么状况已经不记得了，总之是百调不通，在某一行出溢出。这个问题也可以参考上面的链接。
　　在论坛上得到另外两种思路，一是设置一个全局变量，保存位图数据的指针，从而在线程函数中就可以使用；另一个是将这一指针作为参数结构体的一个变量，一同传给线程函数。两种思路都尝试了很多次，但无奈大一的时候C语言学得并不是那么扎实，以至于连extern关键字都不知道用了。等意识到的时候，已经用别的笨方法做完了。调试中的各种纠缠不做描述，总之依旧没有结果。
　　用到的笨方法，是放弃最初的由指针访问同一份数据的思路，而改为每个线程内部拥有各自一份位图数据的设计。为什么之前不愿意这样，尽管这样设计起来很明晰，而且可以避免可能存在的并发控制的问题，主要是因为考虑到内存的消耗。毕竟处理的位图格式是没有压缩的。
　　最后采取的办法就是这样了，每个线程内部独立获取位图数据，同时在读取源图像文件时要保证可共享读，以防止访问冲突。
　　自定义线程函数的参数结构体： struct ThreadParam { int ThreadID; BOOL CalcTpye; //TRUE表示大部分区域的处理，FAUSE表示剩余区域的处理 TCHAR templateFilePath[MAX_PATH]; TCHAR sourceFilePath[MAX_PATH]; int ThreadNum; //线程数n，总线程数应为n+1+1(主线程) };       顺便提一下，在写这个结构体的时候发现了一个奇怪的问题，如果结构体内存在"&"引用，那么在声明该类型的结构体时，编译器会将其识别为类，报错称不存在默认构造函数，我不知道怎么解释。坐待高手指点。
　　【图像拆解】
　　使用多线程加速模板匹配无非就是在逻辑上将位图拆分为几个分割的块，让不同的线程处理不同的块，以实现加速。
　　最直接的想法是，比如，可以将位图分层"田"字形的四块，让四个线程分别处理四块区域。这样的设计未尝不可，一开始我也这么构思。但是细想，这种拆分方法并没有很好的拓展性，分成四块还好说，但如果要分成七块呢？于是想了另外一种拆分法。主要是受一种"先粗后精"的匹配方法启发而来。
　　假设预计用N个线程处理，则分为N = n + 1，n个线程的处理方式如下：
　　将n个线程视为一个组，一组视为同时可处理一个块，块宽为：
　　blockNum = ( nWidth   nTemplateWidth +1 ) /n
　　这样，n个线程负责处理图像"左"边的大部分区域。剩下"右"边的区域宽为：
　　restNum = ( nWidth   nTemplateWidth + 1 ) % n
　　该部分由余下的一个线程处理。
　　第1号线程计算i行j列的位置后，接下来处理i行j + n列的位置，每次跳跃n列。
　　余下的n   1 个线程依此类推。
　　那么，实际上各个线程处理的不是一块连续的图像区域，而是图像中的一部分"列"。
　　【几段代码】 BOOL CMTMDoc::MultiThreadMatch(TCHAR templateFilePath[MAX_PATH], TCHAR sourceFilePath[MAX_PATH]) { ThreadParam tp[6]; //实际参与匹配计算的总线程数为ThreadNum+1 int i; for (i=0 ; iThreadID; BOOL bType = tp->CalcTpye; CString templateFilePath;// = tp->templateFilePath; CString sourceFilePath;// = tp->sourceFilePath; int ThreadNum = tp->ThreadNum; templateFilePath = "2.bmp"; sourceFilePath = "1.bmp";  /************************************************* ***********************/ //截取自线程函数，用于计算模板位置 clock_t start; clock_t finish; start = clock();//开始计时 CFile sourceFile(sourceFilePath,CFile::modeRead | CFile::shareDenyWrite); CDib sourceDib; sourceDib.Read(&sourceFile); if (sourceDib.IsEmpty()) { sourceFile.Close(); return NULL; } CFile templateFile(templateFilePath,CFile::modeRead | CFile::shareDenyWrite); CDib templateDib; templateDib.Read(&templateFile); if (templateDib.IsEmpty()) { templateFile.Close(); return NULL; } //初始化源图像参数，变量名均不带template CSize size = sourceDib.GetDimensions(); DWORD nWidth = (DWORD)size.cx; DWORD nHeight = (DWORD)size.cy; LPBYTE lpData= sourceDib.m_lpImage; //初始化模板图像参数 CSize templateSize = templateDib.GetDimensions(); DWORD nTemplateWidth = (DWORD)templateSize.cx; DWORD nTemplateHeight = (DWORD)templateSize.cy; LPBYTE lpTemplateData = templateDib.m_lpImage; LPSTR lpSrc;//指向源图像的指针 LPSTR lpTemplateSrc; DWORD i; //循环变量 DWORD j; DWORD m; DWORD n; long lMaxWidth = 0;//最大相似性出现位置 long lMaxHeight = 0; unsigned char pixel; unsigned char templatepixel;//像素值 DWORD lRowBytes,lRowTemplataBytes;//原始图像和模板图像每行字节数 lRowBytes=WIDTHBYTES(nWidth*8); lRowTemplataBytes=WIDTHBYTES(nTemplateWidth*8); double dSigmaST;//中间变量 double dSigmaS; double dSigmaT; double R;//相似性测度 double MaxR;//最大相似性测度 dSigmaT=0; //模板所有像素值灰度平方和 for (n=0;n0.9999) //相关系数大于99.99%则视为匹配成功 { MaxR=R; lMaxWidth=i; lMaxHeight=j; finish = clock();//结束计时 goto end; //没办法，要跳出两层循环用goto还是简单点 } } } return 0; } else { blockNum = (nWidth - nTemplateWidth + 1) / ThreadNum; //FUCK U ALL DWORD restNum = (nWidth - nTemplateWidth + 1) % ThreadNum; //FUCK U ALL if (!restNum) { return 0; } MaxR=0.0; for(j=0;j0.9999) //相关系数大于99.99%则视为匹配成功 { MaxR=R; lMaxWidth=i; lMaxHeight=j; finish = clock();//结束计时 goto end; //没办法，要跳出两层循环用goto还是简单点 } } } return 0; 【加速效果】
　　由于多个线程属于均匀的作用，我想理论上是加速到N倍。一直在测试，效果还是有的，只是时好时坏。由于只是测试，用Photoshop截图制成8位灰度图像，只取了2组图像试验：
　　这一组速度变为大约5.1倍
　　这一组速度变为大约6.6倍。
　　两组结果与预期的相似，但是我记得在途中似乎出现过接近于10倍的速度，莫非是那时代码还不完整的缘故？那样的情况，理论上是应当是不可能的。
　　【最后的废话】
　　基于灰度的模板匹配，我个人的感觉是精确度不太可靠，对于模板的灰度分布状况要求较高，如果颜色深度不突出，很容易发生错判，如果形状不规则，那么具体编程实现更为复杂。更严重的是它巨大的计算量。所以，这种方法只适合初学者练手。另外，就如开始所说，多线程加速的尝试只能算是技术实现的一种手段，真正能有较大程度改善的，是算法本身。但那些算法什么的，暂且让专家教授们去做吧！作为小小的本科僧，我能做的就只是这种技术性的体力活了。
　　这个想法在脑海中存在了很久，抓住暑假的尾巴，终于在开学之前完成了。最后一段废话把字数凑到了4K+，怎么突然间，就大三了。
　　卢昊
　　QQ 137571735
　　2010-9-5 1:42