基于TBB的Hough变换并行检测直线

刘向娇　赵学武　贾超超

摘要：Hough变换存在着运算时间长的缺点，用了并行处理这种解决海量数据计算的有效方法来减少其运行时间。该文主要研究了：利用TBB（Threading Building Blocks）这种线程构建模块在多核机上对Hough变换中可并行的部分进行并行化；实验表明这种方法对Hough变换的并行化都有很好的加速效果。

关键词：Hough变换；TBB

中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2014）13-3162-03

Hough Transform Based on TBB Parallel Detection Straight Line

LIU Xiang-jiao1， ZHAO Xue-wu1， JIA Chao-chao2

（1.Department of Soft， Nanyang Normal College， Nanyang 473061， China； 2.ChuMuJu， Jiyuan 454450， China）

Abstract： Hough transform operation time long shortcomings， using the parallel processing that solution is a effective method to compute the huge amounts of data to reduce the running time. This paper mainly studied the： using the TBB （Threading Building Blocks） this thread Building Blocks on a multi-core machine was carried out on the part of the Hough transform can be parallel parallelization； Parallel experiments show that this method of Hough transform has a good speedup.

Key word： Hough transform；TBB

TBB的概念在2004年产生于Intel的内部，到了目前已经有了4.2的版本。TBB在编程的时候使用模板作为通常的并行迭代模型。它提供了丰富的C++模板类，这使得程序员不需要专业地去学习同步、缓存优化、负载平衡等问题，就能很容易地自动调度并行程序，并能使CPU的多个核心都高效的运转起来。TTB是一种能使程序的伸缩性得以提升，且对嵌套完全支持的并行编程模型，可以在 Windows、MacX和Linux的系统上运行，支持 Intel C++、VC7/和gcc编译器。并且为了构建大型的并行程序，允许程序员创建自己的并行组件[1]。

1 TBB的任务调度器

线程构建模块的核心组件就是TBB的任务调度器（Task Schedule），任务调度器使用之前，每个线程都会通过tbb：： task_scheduler_int来初始化线程构建模块库，并且在同时还会隐含地初始化一个全局线程池，通过调度与任务机制自动地来管理线程池。任务的管理由任务调度器通过线程池来进行，通过使用让每一个逻辑线程都对应一个物理线程的方法来解决负荷问题。使用TBB的任务调度机制task与task_schedule可以将线程与任务结合，任务就是计算的逻辑单元，用户可以不必关注线程，而只关心任务本身，通过使用把这些任务映射到物理线程的方法以减少系统的开销。任务调度器不需要用户考虑负载平衡问题，只需要把程序分成若干个小任务，调度器就会将任务自动分配给线程，做到在多核处理器上的负载均衡。

任务调度器将任务映射到物理线程，这个映射是非抢占式的。每个线程都有一个execute（）方法，当线程开始执行execute（）方法之后，这个任务将被绑定到线程上，直到execute（）方法返回。在这期间，线程只有在子任务上等待时，才会执行其他任务，这时它可以执行同一线程中的其他子任务或 （如果没有正在等待的子任务）执行在其他线程中创建的任务。

任务调度器主要是将计算高度密集的工作进行并行化。由于任务对象不会被抢先调度，故在执行时不可以有长时间的阻塞，因阻塞的线程（及其相应的处理器）将无法为其他任务服务了。

调度器是对任务图进行计算的。任务图就是一张有向图，图中的一个节点表示一个任务，每个节点都指向其各自的父节点，根节点的父节点是NULL，或是正在等待根节点完成的其他任务。通过task：：parent（）方法能访问父指针。

2 Hough变换检测直线的原理

Hough变换的基本思想是：利用点—线的对偶性，即图像空间中共线的点与参数空间中相交的线相对应；而反过来，相交于参数空间里同一个点上的所有直线（曲线）与在图像空间中共线的点相对应[2-3]。

在图像空间X-Y中，所有共线的点（x，y）均能用公式（1）所示的直线方程来描述：

y=mx+c （1）

其中截距是c，斜率是m，公式（1）又可以改写成公式（2）：

c=-xm+y （2）

该方程是参数空间M-C中的一条直线方程，其中y是截距，x是斜率。

比较公式（1）与公式（2）可以知道，在图像空间中的一点（x，y）至少要与参数空间中的一条直线相对应，而图像空间中的一条直线又是由参数空间中的一个点（m，c）来决定的。Hough变换的基本思想就是将公式（1）和公式（2）这两个式子看作是对图像空间里的点与参数空间里的线的约束条件，并定义了一个一对多的从图像空间到参数空间的映射关系。endprint

假若被检测直线的斜率为无限大（例直线x=a），公式（2）将无法完成该直线的检测工作，要想使任意方向或位置的直线都能够被正确的识别和检测[4]，我们可以利用Hart与Duda提出的直线极坐标方程公式来替代公式（1）：

[ρ]=ycos[θ]+xsin[θ] （3）

3 利用TBB并行检测直线

由检测直线的串行算法可以得到在整个检测过程中最耗时的是：对任意一个给定的[θ]值，对X-Y平面上的每一个边缘像素点应用Hough变换，利用公式[ρn=icosθm+jsinθm]，计算相应的[ρ]值，并在相应的累加器上加l，[A（ρ，θ）=A（ρ，θ）+1][5]。又因这一步是一个循环迭代过程（其中所有的迭代都可以同时运行，不互相影响），而循环迭代又是可扩展并行的简单形式，故对此算法的并行化改造应主要针对这个最耗时的循环进行[6]。

在这个循环迭代中，由于各个迭代是相互独立的，故可以通过TBB中的模板类parallel_for或模板类parallel_reduce将这个循环并行化。又因程序中的累加是不可重入的，即下一次循环依赖上一次循环的结果，故只能通过模板类parallel_reduce来并行。在应用模板类parallel_reduce时，线程私有的函数副本在最后要被合并起来，故operator（）不能被声明为const。OpSum拥有一个join方法和一个划分构造函数。

在划分构造函数中有一个split类型的哑参数和一个指向初始对象的引用参数。这个哑参数的作用是将划分构造函数与构造函数副本（在构造副本中没有这个参数）区分开来[7]。当任务完成了它的工作且开始将结果汇合到整体工作中去时，就需要调用join方法。传递给这个方法的参数是已经完成工作的结果，故这个方法只需要重复在每个元素上执行相同的运算（在这里是求和运算）即可。当任务调度器发现有一个工作线程可用时，parallel_reduce将首先调用划分构造函数来创建子任务，然后把子任务传递给这个线程来执行。当任务完成时，parallel_reduce将使用join方法来汇合各个子任务的结果[8]。注意，划分构造函数可能会并发地进行，故当在划分构造函数中需要增加其他共享对象的引用计数时，应该使用原子递增操作。

以下是用TBB检测直线程序的核心代码：

struct OpSum{

int r；

void operator（）（const tbb：：blocked_range &t）

{ for（int i=t.begin（）； i！=t.end（）； ++i）

for（ int j = 0； j < width； j++ ）

{if（ image[i * step + j] ！= 0 ）

for（int n = 0； n < numangle； n++ ）

{

r = cvRound（ j * tabCos[n] + i * tabSin[n] ）；

r += （numrho - 1） / 2；

accum[（n+1） * （numrho+2） + r+1]++；

}}}

void join（OpSum& x）{r += x.r；}

OpSum（ OpSum& x， tbb：：split）

： r（0） {；}

OpSum（）

：r（0） {；}

}；

4 实验结果分析

在Hough变换检测直线的串行程序和TBB并行程序执行时间的对比中，应用的硬件环境：CPU 为Intel Core2 Quad Q9400 2.66GHz，内存为 DDR3 4G；软件环境：Windows XP；编程环境：Microsoft Visual Studio 2008，tbb30_20100915oss。线检测串并行程序执行时间比较表：

表1 直线检测串并行程序执行时间比较表

[图片编号＼&图片大小＼&图片宽高（像素）＼&串行执行时间（秒）＼&并行执行时间（秒）＼&加速比＼&图片1＼&1.48M＼&868*600＼&0.578＼&0.257＼&2.249＼&图片2＼&34.3M＼&4000*3000＼&1.468＼&0.518＼&2.834＼&图片3＼&18.1M＼&2772*2286＼&8.156＼&2.477＼&3.292＼&图片4＼&35.8M＼&2795*4481＼&19.046＼&5.625＼&3.386＼&图片5＼&60.1M＼&5973*4481＼&42.781＼&12.438＼&3.440＼&图片6＼&152M＼&11922*4481＼&122.109＼&34.601＼&3.529＼&]

图1 TBB检测直线的加速比比较图

有上表1和图1可得出如下结论：

1）实验中所用的图片2的图片大小和像素数虽然比图片3要大，但由于其所选的图片比较简单，其中存在的直线条数比图片3要少的多，故其执行时间要比图片3短很多。

2）在启动了多个线程的时候，刚开始由于问题的规模较小，线程间的切换也比较频繁并且初始化多个线程也要占用较多的时间，故加速比不是很大。随着问题规模的扩大，CPU的使用率也越来越高，多核优势逐渐体现出来，而启动多个线程所用的时间在程序总的执行时间中所占的比例也越来越小，故加速比越来越大。

5 结束语

本文在实现串行Hough变换算法的基础上，使用TBB工具对其进行了并行化改造加速，都取得了较好的效果。但论文还有一些不足需要进一步改进和提高：

由于时间的关系，该文只做了Hough变换对直线检测的并行化研究工作，而对圆、椭圆及抛物线之类的其他曲线检测的并行化有待进一步研究。

参考文献：

[1] Bennett N，ButridgeR，Saito N.A Method to Detect and Characterize ElliPses Using the Hough Transform[J].IEEE Transactions on Patten Analysis and Machine Intelligence，1999，21（7）.

[2] Ballard D H.Generalizing the Hough Transform to detect arbitrary shapes[J].PatternReeoguition，1981，13（2）：111-122.

[3] 赵书安，冯少彤，聂守平.Hough变换在几何特征检测中的应用[J].南京师范大学学报：工程技术版，2006，16（4）.

[4] IbrahimHAH，Kender J R，Shaw D E.The analysis and performanceof two middle-level vision tasks on a fine-grained SIMD tree machine [A].Binford T O.Proceedings IEEE Computer Society Conference onComputer Vision and Pattern Recognition[C].Los Alamitos： IEEE Computer Society Press，1985：387-393.

[5] Fisher A L，Highnam P T.Computing the hough transform on a scan line array processor[J].IEEETransactions on PAMI，1989，11（3）：262-265.

[6] Jolion J，Rosenfeld A.AnO（logn） pyramid Hough transform[J].Pat-tern Recognition Letters，1989，9（5）：343-349.

[7] Pan Y，Chung H Y H.Faster line detection algorithms on enhanced mesh connected arrays[J].IEEE Proceeding-E，1993，2（140）：95-100.

[8] Chung KL，Lin H Y.Hough transform on reconfigurable meshes[J].Computer Vision and Image Understanding，1995，61（2）：278-284.endprint

由于时间的关系，该文只做了Hough变换对直线检测的并行化研究工作，而对圆、椭圆及抛物线之类的其他曲线检测的并行化有待进一步研究。

参考文献：

[1] Bennett N，ButridgeR，Saito N.A Method to Detect and Characterize ElliPses Using the Hough Transform[J].IEEE Transactions on Patten Analysis and Machine Intelligence，1999，21（7）.

[2] Ballard D H.Generalizing the Hough Transform to detect arbitrary shapes[J].PatternReeoguition，1981，13（2）：111-122.

[3] 赵书安，冯少彤，聂守平.Hough变换在几何特征检测中的应用[J].南京师范大学学报：工程技术版，2006，16（4）.

[4] IbrahimHAH，Kender J R，Shaw D E.The analysis and performanceof two middle-level vision tasks on a fine-grained SIMD tree machine [A].Binford T O.Proceedings IEEE Computer Society Conference onComputer Vision and Pattern Recognition[C].Los Alamitos： IEEE Computer Society Press，1985：387-393.

[5] Fisher A L，Highnam P T.Computing the hough transform on a scan line array processor[J].IEEETransactions on PAMI，1989，11（3）：262-265.

[6] Jolion J，Rosenfeld A.AnO（logn） pyramid Hough transform[J].Pat-tern Recognition Letters，1989，9（5）：343-349.

[7] Pan Y，Chung H Y H.Faster line detection algorithms on enhanced mesh connected arrays[J].IEEE Proceeding-E，1993，2（140）：95-100.

[8] Chung KL，Lin H Y.Hough transform on reconfigurable meshes[J].Computer Vision and Image Understanding，1995，61（2）：278-284.endprint

由于时间的关系，该文只做了Hough变换对直线检测的并行化研究工作，而对圆、椭圆及抛物线之类的其他曲线检测的并行化有待进一步研究。

参考文献：

[1] Bennett N，ButridgeR，Saito N.A Method to Detect and Characterize ElliPses Using the Hough Transform[J].IEEE Transactions on Patten Analysis and Machine Intelligence，1999，21（7）.

[2] Ballard D H.Generalizing the Hough Transform to detect arbitrary shapes[J].PatternReeoguition，1981，13（2）：111-122.

[3] 赵书安，冯少彤，聂守平.Hough变换在几何特征检测中的应用[J].南京师范大学学报：工程技术版，2006，16（4）.

[4] IbrahimHAH，Kender J R，Shaw D E.The analysis and performanceof two middle-level vision tasks on a fine-grained SIMD tree machine [A].Binford T O.Proceedings IEEE Computer Society Conference onComputer Vision and Pattern Recognition[C].Los Alamitos： IEEE Computer Society Press，1985：387-393.

[5] Fisher A L，Highnam P T.Computing the hough transform on a scan line array processor[J].IEEETransactions on PAMI，1989，11（3）：262-265.

[6] Jolion J，Rosenfeld A.AnO（logn） pyramid Hough transform[J].Pat-tern Recognition Letters，1989，9（5）：343-349.

[7] Pan Y，Chung H Y H.Faster line detection algorithms on enhanced mesh connected arrays[J].IEEE Proceeding-E，1993，2（140）：95-100.

[8] Chung KL，Lin H Y.Hough transform on reconfigurable meshes[J].Computer Vision and Image Understanding，1995，61（2）：278-284.endprint