5
第五章 三维测量算法实时化研究
5.3三维测量算法GPU实现
本研究尝试使用CPU+GPU异构并行计算方法实现基于运动补偿的高速视觉三维测量算法，实现原理框图如图5.3所示。由基于GPU的CUDA编程模型可知，复杂的计算任务被分成并行执行的轻量级线程thread，多个thread组成线程块block，多个block组成执行网格grid；并且各个block是并行执行的，各个thread之间也是并行执行的，当各个执行任务相互独立时，并行效率达到最高。在系统实现中，由计算机产生的8对“正反”8-bit格雷码编码图像经高速投影仪DLP以1000帧每秒速度投向被测物体，与之同步的高速视觉系统IDPExpress 实时获取投影图像，同时将投影图像数据通过PCI-E接口传映射到计算机内存中；在基于格雷码编码的连续三维测量中，完成一次三维重建过程需要16幅投影图像，每获得一对“正反”投影图像，结合之前获取到的7对投影图像序列，即可生成一幅三维测量深度图像。因此，计算机将获取到的一对投影图像数据传输到GPU内存中进行加速并行处理运算。其中，按照算法执行的顺序，将三维测量算法步骤进一步细化为图像差分二值化、格雷码二进制转换、空间编码图像生成、三角变换、运动区域提取以及运动速度估计六个步骤。下面将对算法具体实现进行阐述。
图5.3异构运算原理图
如图5.4所示为图像差分二值化线程组织结构，算法步骤并行实现具体原理图如5.5所示。在时刻t=2k和t=2(k+1)，计算机获取到一对8-bit灰度投影图像I(x，y，2k)和I(x，y，2(k+1))，图像分辨率为512×512像素。由第三章差分二值化公式可知，每个像素点的二值化操作是相互独立的，可以将512×512个像素分为512×512个独立运行的线程thread并行执行。
为了便于与图像像素位置对应，其中block和thread均采用一维组织形式，分为512个block，其中每个block分为512个线程。如此一来，每一个线程可以处理一个像素点处的差分二值化计算，恰好与图像分辨率一致。由于每次三维深度信息计算需要16帧图像，因此需要将此运算过程重复8次。获得8帧512×512像素分辨率的1-bit的二值化图像后，根据估计出的物体运动信息，针对帧间像素偏移进行补偿(初始化阶段，默认速度值为0)，求得准确的编码字序列后，利用格雷码与二进制直接转换关系将其转成二进制边码字序列；此时，算法获得了每个像素点处的二进制编码字序列。将8-bit 二进制编码字序列进行按位加权求和即可求出对应像素点处的编码值。然后基于预先标定的投影仪和摄像机内外部参数即可进行三角变换，获得深度信息。获得的深度信息经过PCI-Ex16接口即可传输到计算机内存。通过将获取到的深度图像与背景深度图像差分、二值化操作即可获取到一帧标示运动区域的二值化图像，其中0值对应静止区域，1值对应运动区域。
图5.4并行实现线程组织结构
5.3.1
算法时间复杂度分析
理论上，假设GPU上同时有N个线程在执行，每个线程执行时间为to，因此完成一次512×512像素分辨率图像差分总共需要to×512×512/N。其中N与GPU核心数密切相关。多核并行运算是GPU相对于CPU运算的优势所在，并且当线程处理的数据之间相互独立时可以达到最大效率。在算法步骤图像差分二值化、格雷码二进制转换、空间编码图像生成、三角变换和运动区域提取中，每一个像素点处的数值计算均与其他像素无关，因此可以发挥出GPU并行运算的优势。但是在步骤运动速度估计中，有大量的累加求和操作；在CUDA编程构架中，block之间是并行执行的，并且block之间不能相互通信；虽然block内部线程thread之间可以并行运行，并且线程thread之间可以通过共享内存的方式进行数据共享和相互通信，但是一个block内部最多只能分配512个thread，如果在核函数内部进行大量的串行求和运算，则会大大降低算法并行执行效率。
5.3.2
算法优化方法
为提高程序并行执行效率，本章针对规约算法进行了研究，用于优化串行累加以及乘除法操作。规约算法[145](reduction algorithm)是并行运算中广泛应用于连加、连乘和最值操作的一种算法。其核心思想是将大运算量的任务分为小任务，每个任务负责一部分计算，最后经过迭代进行归并得出结果。
如图5.6所示为数组加法规约算法运算原理图，对于一个长度为N的数组的相加求和运算，CPU串行运算需要连续执行N次。运用规约算法处理这类问题时，第一次规约运算时，可分配N/2个thread分别用于N个数的两两之间求和；第一次规约完成之后，数据量减少一半，只需要分配N/4个thread用于第
二次规约计算；每次运算，数据量减少一半，需要运算线程数减少一半，最后一次规约运算只需要一个线程，这时可以得到计算结果。因此GPU规约计算需要log(N)次。如果假定CPU和GPU时钟周期相同，并且GPU可以同时执行N/2个线程thread，那么运算时间复杂度由N降为log(N)。因此，大大提高了程序执行效率。
因此，对于本章中的二维图像矩阵的求和运算，采用如图5.4所示的线程组织结构。规约步骤如下：
(a)将图像中一行数据对应于一个block中的512个执行线程thread，采用共享内存操作方式；与全局内存访问相比可以将数据访问速度提高100-150倍；
(b)每一行数据经过log(512)=9次规约运算后，对于512个block，得到了512个行叠加和值；
(c)再一次利用规约算法，分为一个block，block中分配512个thread，再经过9次规约运算，可以得到整个图像矩阵的叠加和。
图5.5算法并行实现流程图
5.3.3
规约算法优化
理论上，基于如图5.6结构的规约算法可以大大提高程序执行效率；实际上，这里存在一个共享内存块(Bank)访问冲突问题。CUDA共享内存分为大小相等的存储器模块(memory bank)，对于Tesla构架的GPU，它的每个SM(stream multipleprocessors)拥有16KB共享存储器，用于同一个线程块内的线程间通信。为了使一个half-warp(半个线程束，一个线程束包含16个thread)能够在一个内核周期中并行访问，将共享存储器组织成16个memory bank，每个存储器组都保存一个连续的32位值，可以存储例如整型和浮点型数据；因此，连续的线程进行的连续数组可以在一个内核周期中完成，访问速度非常快。当half-warp中的部分线程访问同一个bank内的数据时，会发生访问冲突(bank conflict)；此时，硬件将顺序化化存储器运算，强迫其它所有线程等待，直到当前线程完成了运算，因此会大大降低并行运算的效率。但是，当一个half-warp中所有的线程都访问同一个bank内的数据时会产生一次广播，不会产生访问冲突[145]。
图5.6规约算法原理图
如图5.7所示为采用图5.6所示规约算法实现过程中线程ID和共享内存bank ID对应情况。可以看出在一个half-warp中存在着2路访问冲突。例如，线程ID为0和为8时，都访问了bankID为0的内存中的数据。这种情况下会产生共享内存访问冲突，造成并行运算效率的下降。
图5.7共享内存访问冲突
因此，为了提高并行计算效率，避免共享内存访问冲突情况的产生，采取了如图5.8所示规约算法结构[145]。在优化算法中，每一个线程将同时处理数组ID为thread ID和threadID+N/2中的数据，其中N为thread ID总个数(本章中，默认为16的倍数)，与规约数组大小对应。因此，threadID为0和为16时，由于memory bank的ID范围为0到16变化，因此均对应同一个bank，内存访问不会冲突。
图5.9无共享内存访问冲突
图5.9所示为对应图5.8中规约算法的线程访问共享内存情况。可以看出，在一个half-warp(16个thread)中，每个线程均能连续访问共享内存中数据，并且不会造成共享内存访问冲突，大大提高了并行运算效率。
文章大纲
更多问题，可以扫码加微信咨询。
添加时务必备注”称呼+单位信息+DLP公众号“，否则不予通过。
本人微信
机器视觉交流群
历史推送
【连载预告】基于结构光投影的运动物体局速实时三维测量方法研究
【连载1.1】三维形态测量方法概述
【连载1.2】运动物体三维形态测量应用
【连载1.3.1】时间编码结构光
【连载1.3.2】空间编码结构光
【连载1.3.3-1.3.4】时间空间混合编码&直接编码
【连载1.4-1.5】课题来源及研究意义&主要内容
【连载2.1-2.2】三维测量原理
【连载2.3.1】结构光系统标定
【连载2.3.2】三角变换
【连载2.4-2.5】实验验证及小结
【连载3.1-3.2】运动物体三维测量存在的关键问题
【连载3.3】高速结构光3D测量
【连载3.4-3.5】实验验证与分析& 本章小结
【连载4.4-4.6】运动补偿算法&实验验证与分析&本章小结
【连载5.1-5.2】引言&基于CPU+GPU并行编程模型
科普
【科普】中国达芬奇手术机器人临床应用
【科普】达芬奇手术机器人系统介绍及应用进展
【科普】3D视觉技术在机器人抓取作业中的应用
【科普】采用菱形排列DMD的格雷码三维重建
【科普】6种3D光学传感技术概述
【科普】散斑结构光三维传感技术的典型应用
【科普】3D光学传感器的前世今生
【深度科普】贵得有底气！一文搞懂投影机镜头
3D 打印口腔领域应用盘点
基于机器视觉的水果品质检测综述
一个视频看懂DLP技术[DMD]
作者姓名：刘永久
学科专业：信息获取与控制
导师姓名：双丰研究员 石井抱教授
本文为转载内容，如有侵权，请通知删除。转一转赞一赞看一看

1  Halcon三维测量思路
 (1)   Halcon三维测量是通过将世界坐标的深度信息转化为二维图像上对应的深度信息，进而通过灰度图像的相应的分割，提取算法进行处理。该算法在大量的点云融合后，空间信息比较复杂的情况无法处理。
(2) 将三维坐标的X,Y，z三个点分别生成三幅图像，通过    xyz_to_object_model_3d 生成3D模型，通过visualize_object_model_3d 可视化显示，xyz_to_object_model_3d函数以及包含空间点的所有三维信息，visualize_object_model_3d实际上只是调用了Opengl进行显示而已，xyz_to_object_model_3d输入参数为三维渲染的视角，但是进行3D渲染以后的图像如何处理？
3d点云可视化化demo

 
3d处理demo
Gocator处理

结构光三维测量（数字光栅投影）
结构光三维测量系统
单目测量系统
双目测量系统
单目系统测量实例
光栅生成
三维点云重建

结构光三维测量系统
目前对于三维视觉来说，有很多种技术，例如双目/多目视觉法、TOF法、散斑法、结构光等等，不同的方法有着各自不同的应用场景和范围。对于工业的产品测量、识别，检测来说，结构光方法是目前比较主流的方法。结构光方法拥有高精度、高密集点云、高速的优点，适用于三维重建、缺陷检测、智能抓取、人脸识别、视觉导航等一系列工作。
结构光主要分为点、线、面三类测量结构，本博客主要从面结构光（数字光栅投影测量）阐述其测量原理和重建效果，面结构光主要投影光栅图像到测量物体表面，然后光栅经过物体面型调制之后被相机采集，通过一系列解相位，然后经过系统标定好的参数，将相位转换为三维点云。
单目测量系统
单目测量系统，就是一个相机+一个投影仪的测量结构，该方法需要对投影仪进行标定，首先对光栅进行投影，然后求解相位信息，再把相位转换到三维点云。对于求解相位信息有很多种成熟的方法：例如（1）格雷码方法（2）多频外差方法（3）倍频法（4）phase-coding法等等。将相位转化为三维点云也有很多经典的方法，例如（1）相位差法（2）东南大学达飞鹏老师的8参数方法（3）反向相机方法。后两种方法最为灵活，应用相对也更为广泛，下面会具体进行描述。下图改自南理工左老师的论文图。


双目测量系统
双目测量系统，就是双目相机+一个投影仪的测量系统，该方法主要利用相位信息进行双目匹配，然后实现三维重建。该方法的好处就是对投影仪无需进行标定，且现有双目测量有很多优秀的库函数可以调用，例如Opencv中包含很多标定、匹配、畸变校正、立体校正的代码。
单目系统测量实例
下面结合具体的测量实例进行详细介绍，包含光栅生成，相位解包，和三维点云转换。
光栅生成
本次我们采用四步相移+格雷码的方法进行物体测量，四步相移为了求解包裹相位，但是包裹相位是一个一对多的映射函数，因此需要利用格雷码将包裹相位展开，求取一个一对一映射函数的绝对相位。四步相移的光栅的形式如下：

$I_1(x,y)$ = $a(x,y)$ + $b(x,y)$cos[$\phi(x,y)$]

$I_2(x,y)$ = $a(x,y)$ + $b(x,y)$cos[$\phi(x,y)$-$\pi/2$]

$I_3(x,y)$ = $a(x,y)$ + $b(x,y)$cos[$\phi(x,y$)-$\pi$]

$I_4(x,y)$ = $a(x,y)$ + $b(x,y)$cos[$\phi(x,y)$-3$\pi/2$]

利用四步相位我们可以求解包裹相位，

$\phi(x,y)$ =  atan2[$I_1(x,y)$-$I_3(x,y)$, $I_2(x,y)$-$I_4(x,y)$]

其中atan2[]是一个四象限反正切函数，于是我们就得到了包裹相位，其具体形式如下图所示，



可以看出x与y是一个一对多的函数，我们需要进行展开，此时我们需要一个条纹阶次$k(x,y)$，然后通过下面的公式，完成相位展开

$\Phi(x,y)$ = $\phi(x,y)$ + 2$\pi\times k(x,y)$

其展开的过程如下图所示，格雷码的作用就是为了求解这个条纹阶次$k(x,y)$。



格雷码是由0或1的码字构成的，因此每张格雷码可以区分出两个周期的阶次$k(x,y)$，因此为了获取求解更多的阶次信息，更多的格雷码就需要，格雷码的数量n与阶次的关系为$2^n$。例如如下图的方式是三张格雷码光栅，第一个阶次的格雷码字为000，第二个为100，以此类推各个周期的格雷码都不相同，因此可以确定出8个阶次，结合包裹相位于是这样我们就可以得到绝对相位信息。


三维点云重建
本博客采用反向相机法将相位信息转化为三维点云，首先对圆形标定板进行了重建，其效果如下图所示，



利用50w分辨率相机对瓶盖进行三维重建，其纹理信息清晰可见



然后采用500w高分辨率相机对雕像进行三维重建，



如需了解更多，交流合作可以联系QQ：1091454117。

浅谈光学三维测量技术
前言
光学三位测量是指运用光学方法获取物体表面的三维坐标的技术。以下将从分类、应用等方面浅谈该技术，作为本系列的入门。
1.光学三维测量的分类
（1）摄影测量法

（2）结构光法

（3）光学干涉法
2.光学三维测量的应用
（1）虚拟现实

（2）逆向工程

（3）生物医学工程
参考文献
http://kns.cnki.net/KCMS/detail/detail.aspx?dbcode=CJFD&dbname=CJFDLAST2015&filename=CXYY201530036&uid=WEEvREcwSlJHSldRa1FhdkJkVG1BSEljZ2RrajVRblNncDliTFp4d3pFVT0=$9A4hF_YAuvQ5obgVAqNKPCYcEjKensW4IQMovwHtwkF4VYPoHbKxJw!!&v=MjQwMjFYMUx1eFlTN0RoMVQzcVRyV00xRnJDVVJMT2ZZdVJzRnlIZ1U3dkxKalhTZDdHNEg5VFByNDlHWW9SOGU=)