均值漂移跟踪算法
在无人驾驶车辆测试平台上利用均值漂移跟踪算法实现移
动图像的实时跟踪
Benjamin Gorry, Zezhi Chen, Kevin Hammond, Andy Wallace, and Greg Michaelson
摘要：本文描述了一种用来跟踪移动目标的新型计算机视觉算法，该算法是作为
无人驾驶车辆长期研究的一部分而被发展的。我们将介绍在视频序列中利用变量核
进行跟踪的研究结果。其中，均值漂移目标跟踪算法是我们工作的基础；对于一个
移动目标，该算法通常用来在初始帧中确定一个矩形目标窗口，然后利用均值漂移
分离算法处理该窗口中的数据，将跟踪目标从背景环境中分离出来。我们并没有使
用标准的Epanechnikov内核，而是利用一个倒角距离变换加权内核来提升目标表
示和定位的精度，利用Bhattacharyya系数使RGB色彩空间中两个分布之间的距离
最小化。实验结果表明，相对于标准算法，本算法在跟踪能力和通用性上有一定的
提升。这些算法已经运用在机器人试验平台的组成部分中，并证明了这些算法的有
效性。
关键词：Hume，函数程序设计，无人驾驶车辆，先驱者机器人，视觉
I.引言
本文比较和对比了在视觉序列中跟踪移动目标的三种计算机视觉算法。对于很多无人驾驶车辆（A V）来说，在复杂背景中检测和跟随移动目标的应用是至关重要的。例如，这可以让一个全尺寸无人驾驶车辆跟踪行人或者移动车辆并避免与之相撞。同时对于机器人而言，这项技术也可以提升导航性能和增强安全性。对单个移动目标的良好隔离，将便于我们针对感兴趣的目标进行应用开发。而所有的这些应用都要求我们能够实时的处理全彩色的视频序列。
我们的工作是在基于先驱者P3-AT全地形机器人的无人驾驶车辆测试平台上进行的，它是一个英国项目的一部分。这个庞大的项目是由国防科学技术中心（DTC）下辖的无人系统工程（SEAS）为了开发新型无人驾驶车辆传感器技术而建立的。国防科学技术中心的无人系统工程是由英国工业联盟操作管理，旨在通过采取系统工程的方法在整个系统和子系统
层次上，研究有关无人系统的创新性技术，以此达到利用科学技术进步促进军事能力发展的目的。
本文有许多独到之处。第一，基于之前探讨的均值漂移算法，我们介绍了在复杂、混乱的背景下追踪移动图像的新算法。第二，我们展示了我们的算法能够在全尺寸视频图像中实时地追踪移动目标。第三，我们以先驱者P3-AT全地形机器人为基础，介绍了如何在一个简易无人车辆测试平台上配置新算法。最后，我们的实现方式是与众不同的，因为我们采用新颖的Hume[1,2]编程语言来编写程序。这一语言的新奇之处在于将函数式编程概念与编写实时反应系统的有限状态自动机有机结合起来。
B. Gorry, Z. Chen, G. Michaelson来自苏格兰瑞卡顿的赫瑞瓦特大学计算机科学系。
K. Hammond来自苏格兰圣安德鲁斯的圣安德鲁斯大学计算机科学学院。
A. Wallace来自苏格兰瑞卡顿的赫瑞瓦特大学电子与计算机工程系
II.均值漂移视觉算法
A.均值漂移分离算法
我们将介绍利用不同内核对视频序列中移动目标实时跟踪的研究结果。这些内核是由Comaniciu和Meer[4,5,6]第一次应用于图像分离处理，其具有如下特征，底层的、简单的、鲁棒性的以及不同的均值漂移、聚类算法[3]。对于在无人驾驶车辆上的应用，我们首先通过分割及交互式的选择确定一个感兴趣的目标，然后当该目标在摄像机视野范围内移动时对其实施跟踪。设计均值漂移算法是用来寻找数据的众数（或者说数据高度集中区域的中心），而这些数据是由任意维向量表示的。该算法处理过程如下所示[7]。
●选择搜索窗口的半径
●选择窗口的初始位置（中心点）
●重复如下步骤
计算整个窗口数据点的均值，然后将窗口中心点平移到该均值点
●直到中心点的平移距离小于预设的阀值
特征空间中的高密度区域对应于在图像域中色彩/饱和度有限范围内拥有的足够大数量的像素。因此，这些像素就形成了连通区域（这种情况在相对平滑图像中是很常见的）；该算法本质上就是为了找到在对比度/色彩上基本无变化的相对较大的连通区域（被人们理解
并定义的区域）。事实上，本算法是这样进行处理的，每一次随机地放置一个搜索窗口，找到相应的众数，然后将所有特征向量从特征空间移动到最终窗口中。因此，人们总是希望能够快速找到较大区域。
(a)一个320×240的彩色图像
(b)对应的RGB图像
(c)对应的Luv色彩空间
图1 图像，RGB和Luv之间的关系
在实现过程中，我们将通常在RGB色彩空间中呈现的像素映射到Luv色彩空间，Luv色彩空间有一个通过L表示的亮度分量和两个通过u和v表示的色度分量。通常认为后一个色彩空间等方性更好，因而更适合用在众数寻找算法中。最后，当我们定义了一个可变核，该可变核就会在显示跟踪结果时被约束在我们之前提到的矩形窗口中。
图1举例说明了图像和特征空间之间的关系。图2展示了分别在RGB与Luv空间中的分离结果。至少主观上，我们可以看到在这个实例中利用Luv参数化所带来的提升。通过Hume 编程语言将RGB映射到Luv的实现流程图如图3所示。图4是均值漂移分离算法的流程图。
(a)在RGB色彩空间中分离结果
(b)在Luv色彩空间中分离结果
图2 分离结果
图3 RGB到Luv的流程图（Hume）
图4 均值漂移分离算法流程图（Hume）
B. 均值漂移目标跟踪算法
在初始帧中，首先针对目标区域定义一个矩形窗口。然后在Luv 色彩空间中运用均值漂移算法，将跟踪目标从背景中分离出来。当目标移动时，利用独特的倒角距离变换加权内核来提升目标表示和定位的精度，同时利用Bhattacharyya 系数使两个颜色分布之间的距离最小化。在通过彩色图像序列跟踪目标的过程中，假设我们能够利用色彩空间中某一区域的样本离散分布将目标表示出来，并利用一个能够确定当前位置的内核进行定位。因此，我们就要找到函数ρ分布中的最大值。该函数是相对于之前的模版图像，在候选图像中目标位置（漂移）的函数，用来计算加权色彩分布之间的相似度。而Bhattacharyya 系数[8]
是重叠数量的估算值。如果能够得到相对密度p (x )和q ( x )的两组参数，则Bhattacharyya 系数定义如下： ()()p x q x d x ρ=? （1） 因此，我们在处理从彩色图像中得到的离散采样数据时，我们就使用在模版和候选图像中应用以m 进制直方图存放的离散密度。模版图像的离散密度定义如下：
{}1,1,2,,1m
u u u q q u m q ===???=∑ （2）
同样地，在随后帧中的给定位置y 处，候选图像的预估直方图是：
()(){}1,1,2,,1m
u u u p y p y u m p ===???=∑ （3）
根据方程（1）的定义，Bhattacharyya 系数的样本估计定义如下：
()()()1,m
u u u y p y q p y q ρρ===????∑ （4）
由色彩密度函数()f x 得到一组独立的随机样本{}12,,,n x x x ???。如果K 是标准的内核函数，那么内核密度估计由下式给出：
()()1n
n i i i q K X b X u δ==-????∑ （5）
用这种方式估算色彩密度时，那么均值漂移算法就用来在目标帧中不断移动位置y ，以此来寻找Bhattacharyya 系数分布的众数（方程4）。围绕u p (0y )展开泰勒级数，则Bhattacharyya 近似为[8]
：
()()()011
,1
122m n u u i i u i p y q p y q w K X ρ==≈
????+∑∑ （6） 其中 ()()
10m
u i i u u q w b X u p y δ==-????∑ （7）
当方程（6）的第一项独立于y 时，方程（6）的第二项取得最大值，则方程（4）取最大值。在均值漂移算法中，内核不断地从当前位置0y 移动到新位置1y ，0y 到1y 的关系如下： ()()10011n n i i
i i i i i y X wG y x wG y x ===--∑∑ （8）
其中，
G 是K 的梯度函数。这等价于基于色彩直方图的内核过滤相似度函数梯度的阶跃上升。图5是均值漂移目标跟踪算法的流程图。
图5 均值漂移目标跟踪算法流程图（Hume ）
III.在无人驾驶车辆测试平台上应用跟踪算法
我们的硬件测试平台由先驱者P3-AT全地形机器人组成，即SEBO（SEAS机器人，图6）。我们为SEBO配置了前阵声纳光盘，无线以太网，前后安全保险杠以及一个安装在表面用来收集均值漂移视觉算法数据的摄像头。我们通过如下的标准软件连接到先驱者机器人从而实现Hume程序应用：ARIA（先进机器人应用程序接口）。该软件是一个连接机器人微控制器的开源开发环境，并且提供了基本的马达和摄像功能接口；VisLib是一个基于C语言的开源视觉处理程序库，它提供了基本的图像处理能力。
图6 SEBO - the Heriot-Watt/St Andrews先锋机器人P3-AT
A.软件体系结构
图7展示了在测试平台上实现的软件结构。在机器人上实线箭头代表本地套接字通信而虚拟箭头表示无线套接字通信。除了在笔记本电脑上运行的Java GUI以外，所有的代码都是存储于机器人上的。位于机器人上的图像处理程序将机器人摄像机捕获的实时图像以Hume语言方式记录，然后通过无线方式发送到笔记本电脑，并在其中实时的显示出来。每
个图像的红色，蓝色和绿色分量都能被捕获到。由于其中被捕获的图像大小是240×320，因此要求有一个尺寸为3×240×320的存储结构。
图7 机器人测试平台结构
图8 接口界面的截图
我们已经在笔记本电脑上实现了一个简单命令的接口。当用户决定移动机器人时，电脑会发送一个无线信号到位于机器人上的Hume程序中。然后Hume程序与一个C++ ARIA程序通信，该程序把基本的电机命令发送到机器人。以类似控制机器人的方式控制摄像头。图7展示了当用户选择控制相机时，控制信号就通过无线从笔记本电脑发送到机器人上的Hume程序中。然后，Hume程序就会与C++ ARIA程序通信，并让其发送相机的控制命令。图8左上部分显示的是相机面板，用于控制相机的摇摄，倾斜和变焦功能。这里提供了两套
相机控制。第一组允许设定相机的最小运动或对焦距值，而第二组允许设定相机的最大运动或对焦值。
B.结合视觉算法
图7中有星号标记的Hume方框图可以先后被替换为：
1.LUV转换算法；
2.均值漂移分离算法；
3.均值漂移目标跟踪算法。
这些算法产生不同的图像效果。从最初的实验中，每一个算法都可以作为测试平台结构的一部分，并通过简单地更换Hume盒，将图像从相机传到Java界面上。这项工作的开始就要明确各算法间的依赖关系并在需要处建立有效的链接点。
对于LUV的转换算法，图像被呈现在LUV色彩空间中。对于均值漂移分离算法，实验中使用多种类型和尺寸的图像。通常情况下该算法是处理尺寸为240×320的图像。均值漂移目标跟踪算法的最初工作出现了令人欣喜的结果。对于一个放置在相机焦点上的目标，当机器人或相机以稳定的速度移动时，可以在屏幕上实时的跟踪目标。
当前的工作是引入这样一个选项，它允许用户在界面屏幕上圈出感兴趣的目标，将其突出出来。该对象的坐标，即在屏幕上的位置，就被传送到均值漂移跟踪算法。这样一来，如果目标移动，机器人也跟着移动；或者机器人上的相机跟着移动，然后使用在2.2节中讨论的算法对该目标进行跟踪。这些是可以在界面上观察到的。
C.实现与实验评价
图9展示了跟踪对象的第一帧图和前景图像。在这种情况下，当目标具有相对统一的亮度时，一个简单的区域同质标准就会被采用。图10展示了使用NCDT内核跟踪一名男路人的部分结果。
图9 分离出的矩形窗口
图10 使用NCDT内核跟踪一名男路人的部分结果
D.机器人平台
目前，图7中展示的机器人平台已被用来作为在Hume语言中开发的视觉算法的部署体系结构。这些算法的使用是Hume的实现工作以及Hume可以和其他行业标准语言，例如C,C++,Java相结合的概念上的证明。在第二节中探讨的这三种算法，可以对安装在机器人表面上的相机捕获的图像进行实时处理。
机器人平台可能的扩展将涉及到的Hume代码的各个部分，这些代码与机器人的API 相连接。我们通过做这些内容，以个别方案为基础来获得一系列的性能分析。或者，我们将图7中展示的三种Hume程序结合起来。通过程序的执行我们可以对其进行性能分析，当Java接口发出机器人或相机的移动请求时，我们也可以评估程序的反应速率。均值漂移跟踪算法的一系列实验将继续进行下去。这些实验涉及到不同大小，颜色，不同的背景颜色和形状的跟踪对象。
IV.相关工作
在很多应用领域都有关于实时跟踪算法的应用。通过实时获取图像，并进行图像分割，我们可以将图像分为几个不同的区域。然后，我们可以利用这个信息来跟踪突出显示的对象。在这个处理过程中，这些算法是采用FPGAs(现场可编程门阵列)而不是微处理器来实现。这是利用现场可编程门阵列的计算性和并行处理的优势。然而，在[10]中讨论到的算法需要用到
清晰可见的荧光标记，在本文中讨论到的均值漂移算法则不需要这种标记。我们最初的实验已经证明两个仅在一些小地方有颜色差异的相似物体也可以被识别出来。
在嵌入式实时应用程序中，获得精确的时间和空间使用率边界是非常有价值的[11,12]。如果我们能够预测系统如何运行，我们就可以为一个程序周期的期望执行时间设定上界。使用Hume编程语言，就可以做到这些。Hume编程语言设计的关键是它的可计算的功能。为了提供这些计算结构，Hume编程语言开发了一系列的重叠语言子集[13]。在每个重叠子集中都增加了语言的可表达性。通过选择合适的语言等级，程序员可以在语言的表现性和需要的计算等级中得到平衡。因此，我们可以确定所需要的时间和空间上界——这就使我们可以确定所需要的硬件数量。在本文中提到的关于FPGAs的休姆算法的部署正是我们所感兴趣的。然后我们可以利用Hume编程语言的计算结果与微处理器中获得的计算结果相比较。
V.结论及展望
本文中我们探索了使用变量核来提高均值漂移分割算法。实验结果表明，和利用标准内核程序计算结果相比较，已经完成的均值漂移物体跟踪算法在跟踪能力和通用性上有所提高。这些算法包含在用于证明他们效率的机器人测试架构中。每一种算法都是用Hume算法研发的。通过实时图像的处理和机器人的无线通信，可以在复杂混乱的背景下追踪移动物体。
目前进行中的工作是通过以下几项来扩展试验平台：
1、为无人驾驶车辆研发新图像的处理算法；
2、通过增加一条线性后续算法来补充动态跟踪算法。
这些将包括用于控制机器人和相机移动的扩展接口，这些扩展功能还需要进一步的论证：
1、Hume编程语言如何用于研发执行实时处理的算法；
2、测试平台的灵活性；
3、跟踪算法的准确性。
致谢
本论文中研究的工作是由英国国防部国防科学技术中心成立的系统工程自治系统（SEAS）资助的。这里要特别感谢我们在欧盟FP6 EmBounded工程中的合作伙伴：Christian Ferdinand、Reinhold Heckmann、Hans-Wolfgang Loidl、Robert Pointon和Steffen Jost。
参考文献
[1]K. Hammond and G. Michaelson, “The Hume Report, Version 0.3”, 2006
[2]K. Hammond and G. Michaelson, “Hume: a Domain-Specific Language for Real-Time
Embedded Systems”, Proc. of Int. Conf. on Generative Programming and Component Engineering, Erfurt, Germany, Sept. 2003, Springer-Verlag Lecture Notes in Comp. Sci., pp.
37-56.
[3]Y. Z. Cheng, “Mean shift, model seeking, and clustering,” IEEE Transactions on Pattern
Analysis and Machine Intelligence, 17(8): 790 -799, 1995.
[4]Comaniciu, P. Meer, “Robust analysis of feature space: Color image segmentation,” In IEEE
Conf. Computer vision and Pattern Recognition, 750 – 755, 1997.
[5]Comaniciu and P. Meer, “M ean shift: A robust approach toward feature space analysis,” IEEE
Transactions on Pattern Analysis and Machine Intelligence, 24(5), 603-619, 2002.
[6]Comaniciu, V. Ramesh, P. Meer, “Kernel-based object tracking,”IEEE Transactions on
Pattern Analysis and Machine Intelligence, 25(5), pp564-575, 2003.
[7]Y. Keselman and E. Micheli-Tzanakou, “Extraction and characterization of regions of interest
in biomedical images,” In Proceeding of IEEE International conference on Information Technology Application in Biomedicine (ITAB 98), 87-90, 1998.
[8]Bhattacharyya, “On a measure of divergence between two statistical populations defined by
their probability distributions,” Bulletin of the Calcutta Mathematics Society, 35, pp99-110, 1943.
[9]MobileRobots Inc., “Pioneer 3 Operations Manual with MobileRobots Exclusive Advanced
Control & Operations Software”, MobileRobots Inc., January 2006.
[10]T. Johnston, K. T. Gribbon and D. G. Bailey. “FPGA based Remote Object Tracking for
Real-time Control”, 1st International Conference on Sensing Technology, Palmerston North, New Zealand, 2005.
[11]G. Hager and J. Peterson, “FROB: A Transformational Approach to the Design of Robot
Software”, Proc. of the ninth International Symposium of Robotics Research, Utah, USA, 1999.
[12]Fijma and R. Udink, “A Case Sudy in Functional Real-Time Programming”, Technical
Report, Dept. of Computer Science, Univ. of Twente, The Netherlands, 1991
[13]K. Hammond, “Exploiting Purely Functional Programming to Obtain Bounded Resource
Behaviour: the Hume Approach,” First Central European Summer School, CEFP 2005, Budapest, Hungary, July 4-15,2005, Lecture Notes in Computer Science 4164, Springer-Verlag, 2006,pp. 100-134.
光线跟踪讲解及源代码
计算机图形学期末作业 作业题目：Ray Tracing算法的实现 姓名：李海广 学号：S130201036 任课教师：秦红星
摘要 Ray Tracing算法又叫光线跟踪算法，它能通过递归方法逐个计算每个像素点的光强，然后就可以绘制出高度真实感的图像，因此该方法在图形学领域得到了广泛的应用。Ray Tracing算法的思想还能应用到移动通信终端定位领域，该领域里的射线跟踪法与此算法思想类似。MFC是微软公司提供的一个类库，以C++类的形式封装了Windows的API，并且包含一个应用程序框架，以减少应用程序开发人员的工作量。其中包含的类包含大量Windows句柄封装类和很多Windows的内建控件和组件的封装类。MFC在处理Windows窗口应用程序方面具有很大的优势，因此，本文使用MFC在VC6.0里实现Ray Tracing算法，并给出了该算法的详细讲解。 【关键词】Ray tracing 光线跟踪递归像素光强 MFC C++
目录 1.Ray Tracing算法概述 (1) 1.1Ray Tracing算法简介 (1) 1.2Ray Tracing算法的实现原理 (1) 2.Ray Tracing算法的具体实现 (2) 2.1算法的实现环境 (2) 2.2实现算法的C++程序简介 (2) 2.3算法的具体实现过程 (3) 2.4 程序运行结果 (11) 3.总结 (11) 3.1 通过该算法学到的东西 (11) 3.2本程序未完成的任务 (12) 4.参考文献 (12)
1.Ray Tracing算法概述 1.1Ray Tracing算法简介 光线跟踪（Ray tracing），又称为光迹追踪或光线追迹，它是来自于几何光学的一项通用技术，它通过跟踪与光学表面发生交互作用的光线从而得到光线经过路径的模型。它用于光学系统设计，如照相机镜头、显微镜、望远镜以及双目镜等。这个术语也用于表示三维计算机图形学中的特殊渲染算法，跟踪从眼睛发出的光线而不是光源发出的光线，通过这样一项技术将具有一定数学模型的场景显现出来。这样得到的结果类似于光线投射与扫描线渲染方法的结果，但是这种方法有更好的光学效果，例如对于反射与折射有更准确的模拟效果，并且效率非常高，所以在追求高质量结果时我们经常使用这种方法。 在光线跟踪的过程中，我们要考虑许多因素。要跟踪的光线包括反射光线、散射光线和镜面反射光线，利用递归方法并且设定一定的阀值来跟踪；在计算光强度时，我们要考虑场景中物体的反射系数、漫反射系数和镜面反射系数，还有交点处的法向量，出射光线的方向向量；在求视线以及反射光线和场景中物体的交点时，要计算出离眼睛以及出射点最近的交点作为击中点，得到击中点之后，我们就可以计算出击中点的坐标。最终，通过三个公式计算出每一个像素点处三种光线的光强值，再将三个光强值相加，就得到了该像素点出的总光强值，最后将颜色缓冲器中的三种颜色值输出到屏幕上，就得到了我们需要的光线跟踪图像。 1.2Ray Tracing算法的实现原理 （1）对图像中的每一个像素，创建从视点射向该像素的光线； （2）初始化最近时间T为一个很大的值，离视点最近的物体指针设为空值； （3）对场景中的每一个物体，如果从视点出发的光线和物体相交，且交点处的时间t比最近时间T小，则将t的值赋给最近时间T，并设置该物体为最近物体，将物体指针指向该物体； （4）经过第三步的计算后，如果最近物体指针指向空值NULL，则用背景色填充该像素。如果该指针指向光源，则用光源的颜色填充该像素；
均值漂移跟踪算法
在无人驾驶车辆测试平台上利用均值漂移跟踪算法实现移 动图像的实时跟踪 Benjamin Gorry, Zezhi Chen, Kevin Hammond, Andy Wallace, and Greg Michaelson 摘要：本文描述了一种用来跟踪移动目标的新型计算机视觉算法，该算法是作为 无人驾驶车辆长期研究的一部分而被发展的。我们将介绍在视频序列中利用变量核 进行跟踪的研究结果。其中，均值漂移目标跟踪算法是我们工作的基础；对于一个 移动目标，该算法通常用来在初始帧中确定一个矩形目标窗口，然后利用均值漂移 分离算法处理该窗口中的数据，将跟踪目标从背景环境中分离出来。我们并没有使 用标准的Epanechnikov内核，而是利用一个倒角距离变换加权内核来提升目标表 示和定位的精度，利用Bhattacharyya系数使RGB色彩空间中两个分布之间的距离 最小化。实验结果表明，相对于标准算法，本算法在跟踪能力和通用性上有一定的 提升。这些算法已经运用在机器人试验平台的组成部分中，并证明了这些算法的有 效性。 关键词：Hume，函数程序设计，无人驾驶车辆，先驱者机器人，视觉 I.引言 本文比较和对比了在视觉序列中跟踪移动目标的三种计算机视觉算法。对于很多无人驾驶车辆（A V）来说，在复杂背景中检测和跟随移动目标的应用是至关重要的。例如，这可以让一个全尺寸无人驾驶车辆跟踪行人或者移动车辆并避免与之相撞。同时对于机器人而言，这项技术也可以提升导航性能和增强安全性。对单个移动目标的良好隔离，将便于我们针对感兴趣的目标进行应用开发。而所有的这些应用都要求我们能够实时的处理全彩色的视频序列。 我们的工作是在基于先驱者P3-AT全地形机器人的无人驾驶车辆测试平台上进行的，它是一个英国项目的一部分。这个庞大的项目是由国防科学技术中心（DTC）下辖的无人系统工程（SEAS）为了开发新型无人驾驶车辆传感器技术而建立的。国防科学技术中心的无人系统工程是由英国工业联盟操作管理，旨在通过采取系统工程的方法在整个系统和子系统
opencv实现分水岭,金字塔,均值漂移算法进行分割
using System; using System.Collections.Generic; using https://www.wendangku.net/doc/ba1611662.html,ponentModel; using System.Data; using System.Drawing; using System.Linq; using System.Text; using System.Windows.Forms; using System.Diagnostics; using System.Runtime.InteropServices; using Emgu.CV; using Emgu.CV.CvEnum; using Emgu.CV.Structure; using Emgu.CV.UI; namespace ImageProcessLearn { public partial class FormImageSegment : Form { //成员变量 private string sourceImageFileName = "wky_tms_2272x1704.jpg";//源图像文件名 private Image
光线投射,光线追踪与路径追踪的概念与区别
光线投射,光线追踪与路径追踪的概念与区别 光线投射Ray Casting [1968] 光线投射（Ray Casting），作为光线追踪算法中的第一步，其理念起源于1968年，由Arthur Appel在一篇名为《Some techniques for shading machine rendering of solids》的文章中提出。其具体思路是从每一个像素射出一条射线，然后找到最接近的物体挡住射线的路径，而视平面上每个像素的颜色取决于从可见光表面产生的亮度。 光线投射：每像素从眼睛投射射线到场景 光线追踪Ray Tracing [1979] 1979年，Turner Whitted在光线投射的基础上，加入光与物体表面的交互，让光线在物体表面沿着反射，折射以及散射方式上继续传播，直到与光源相交。这一方法后来也被称为经典光线跟踪方法、递归式光线追踪（Recursive Ray Tracing）方法，或Whitted-style 光线跟踪方法。 光线追踪方法主要思想是从视点向成像平面上的像素发射光线，找到与该光线相交的最近物体的交点，如果该点处的表面是散射面，则计算光源直接照射该点产生的颜色；如果该点处表面是镜面或折射面，则继续向反射或折射方向跟踪另一条光线，如此递归下去，直到光线逃逸出场景或达到设定的最大递归深度。 经典的光线追踪：每像素从眼睛投射射线到场景，并追踪次级光线（(shadow, reflection, refraction），并结合递归 光线追踪（Ray tracing）是三维计算机图形学中的特殊渲染算法，跟踪从眼睛发出的光线而不是光源发出的光线，通过这样一项技术生成编排好的场景的数学模型显现出来。这样得到的结果类似于光线投射与扫描线渲染方法的结果，但是这种方法有更好的光学效果，例如对于反射与折射有更准确的模拟效果，并且效率非常高，所以当追求高质量的效果时经常使用这种方法。
基于均值漂移的视觉目标跟踪方法综述
基于均值漂移的视觉目标跟踪方法综述 齐 飞，罗予频，胡东成 (清华大学自动化系，北京 100084) 摘 要：基于均值漂移的视觉目标跟踪方法具有模型简洁实用、能够处理目标形变及部分遮挡等复杂情形的优点，算法高效且易于模块化实现。各种改进的模型及方法针对目标的尺度变化、特征分布等核心问题进行了系统研究，跟踪性能得到了进一步提高。该文从基本的均值漂移跟踪方法出发，系统介绍了此类方法的发展过程与最新成果。 关键词：均值漂移；视觉目标跟踪；核函数；相似性度量 Overview on Visual Target Tracking Based on Mean Shift QI Fei, LUO Yu-pin, HU Dong-cheng (Department of Automation, Tsinghua University, Beijing 100084) 【Abstract 】Mean-shift-based visual target tracking is one of the hotspots in the field of computer vision. The model of the algorithm is simple,efficient and easy-to-implement, and it can handle the complex cases such as deformations and partial occlusions. Recent researches on scale adaptation of the tracking window and distributions of features improve the performance of such trackers. This paper introduces the development and the state of such kind of the algorithms. 【Key words 】mean shift; visual target tracking; kernel functions; similarity measurement 计 算 机 工 程Computer Engineering 第33卷 第21期 Vol.33 No.21 2007年11月 November 2007 ·博士论文· 文章编号：1000—3428(2007)21—0024—04 文献标识码：A 中图分类号：TP311 视觉目标跟踪在安全监控、汽车辅助驾驶、人体运动分析以及视频压缩等领域有着广泛应用。由于视觉目标本身及周边环境复杂多变，因此获得鲁棒而高效的跟踪算法目前仍旧是计算机视觉中一个极具挑战性的研究课题。 典型的视觉跟踪算法通常包括2个核心模块：数据关联和目标定位。前者根据先验知识如目标的动力学特征，将检测结果与目标状态关联起来，并对跟踪轨迹进行滤波。这方面的研究已经比较成熟，常用方法有卡尔曼滤波器、粒子滤波器及概率数据关联。后者是对被跟踪目标建模并据此在图像序列各帧中定位目标。在视觉目标跟踪中，目标建模及定位更为重要，常用的方法有色块模型和活动轮廓模型。均值漂移方法[1~2]提供了一种新的目标描述与定位的框架，将目标特征与空间信息有效地结合起来，避免了使用复杂模型描述目标的形状、外观及其运动。 1 均值漂移方法介绍 均值漂移(mean shift)是Fukunaga 等人提出的一种非参 数概率密度梯度估计算法[1]，在统计相似性计算与连续优化方法之间建立了一座桥梁。该方法直到Cheng 的研究成果[2]发表之后，才受到较多的关注。此后均值漂移被广泛应用到诸多相关领域，如模式分类、图像分割以及目标跟踪等方面。 核函数在均值漂移方法中起了非常重要的作用，核函数的概念、构造方法及常用形态如下文所述。 1.1 核函数 考虑d 维实欧氏空间d R ，向量,d R ∈x y 的内积定义为 T ,=i i i x y ??=∑x y x y ，向量的模可由内积导出1/2=,??x x x 。 对给定的函数:d K R R →，若存在一元函数:[0,)k R ∞→使得 2 ()=()K k x x 成立，其中，()k r 在区间[0,)∞上非负、有界、 单调减、分段连续并且积分0 ()d k r r ∞ ∫有界，则称函数() K x 为核函数，)(r k 为相应的剖面函数。因为函数)(r k 分段连续，不可导点集的Lebesgue 测度为0，所以在不可导点集上补充定义后，函数)(r k 在其定义域内处处可导，即)(r k ′存在。常见的剖面函数见表1。 表1 常见的剖面函数 给定核函数()K ?和()H ?，对应的剖面函数为)(r k 和 ()h r ，若存在常数c ，使得()=()k r ch r ′?，则称()H ?为()K ?的 影子核。 给定核函数()K x 和()K x 及正实数σ，由下列各式定义的函数也是核函数： 1()(/)()()()()() ()()()K K P K K K K S K K σσ?====+?x x x x x x ?x x x x 其中，矩阵?是d d ×维实正定对称矩阵。若记单位矩阵为 I ，当取=σ?I 时，()=()K K σ?x x 。通常称σ为核函数 ()K σx 的窗宽，称?为核函数()K ?x 的窗宽矩阵。 作者简介：齐 飞(1977－)，男，博士研究生，主研方向：模式识别，计算机视觉；罗予频、胡东成，教授、博士生导师 收稿日期：2006-11-20 E-mail ：qfei00@https://www.wendangku.net/doc/ba1611662.html,
光线跟踪算法思想
光线跟踪算法思想 一、概述 本试验完成了基本光线跟踪、高级光线跟踪（反射、折射、透明、阴影）、光线跟踪加速算法等三个与光线跟踪有关的内容。 二、算法简述 1．面片求交 面片求交采用了先求交后判断的方法。现将光线的方程代入平面方程中求出交点。然后将该面片与交点都投影到同一个平面中如XOY平面。投影时需要判断投影结果是否会退化为一条直线，如果发生这种情况则要投影到另一平面内。 投影后，将交点坐标代入到面的边线方程中（要保证线的方向一致），并判断符号，如果符号始终相同，则表示点在面内。 2．球体求交 球体求交也采用了将光线方程代入球体方程的方式。如果方程无解表示没有交点。如果有两个大于0的解，则取较小的一个；如果一个大于0，一个小于0的解，则取大于零的解。 如果没有大于零的解则仍判定为不相交。 3．光线跟踪算法 设定视点和画布 for 画布上的每一行 { for 每一行上的每个像素 { 生成一条从视点到像素点的光线ray LT[i,j] = ray.RayTrace(物体数组，光源数组，1) } } //计算光线与物体的交点，并计算光强 V oid RayTrace(物体数组，光源数组，递归深度) { for 每个物体 { 计算光线与该物体的交点 if 光线起点到交点的距离小于已记录的最短距离且大于0 { 将最短距离设置为该距离
在这条光线对象中记录交点坐标，平面法向量，透明度，物体序号等 } } 对于距光线起点最近的那个点，执行 ComputeIntensity（物体数组，交点数组序号，光源数组，递归深度） } V oid ComputeIntensity(物体数组，交点数组序号，光源数组，递归深度) { 给物体加上环境光强 for (每个光源) { 生成一条从光源指向交点的光线 判断该光线是否与其他不透明的物体相交 if （不相交） 将该光线光强乘以满反射系数和镜面反射系数加到被跟踪光线的光强中 } if （递归深度< 设定深度） { if （需要反射） { 生成一条以交点为起点的反射光线reflectRay reflectRay.RayTrace(物体数组，光源数组，递归深度+1) 将reflectRay的光强与镜面反射系数相乘，加到原被跟踪光线光强中} if （需要折射） { 生成一条以交点为起点的折射光线refractRay refractRay.RayTrace(物体数组，光源数组，递归深度+1) 将refractRay的光强与透明系数相乘，加到原被跟踪光线光强中} } } 4．光线跟踪加速算法（层次包围球） 本作业选择了包围球而不是包围和来实现加速。这是基于光线与包围球求交比与包围盒求交速度快的考虑。虽然包围盒比包围球能更紧密地包围住物体，但与包围盒求交时需要处理所有可见面片并且对求出的交点还要判断是否在面片内，这样，当物体数量较少时反而起不到加速的作用。因此我觉得包围盒更适合于规模很大的光线跟踪计算。
光线跟踪算法
光线跟踪算法的研究与进展 刘进 摘要：光线跟踪算法是图形绘制技术中的经典算法，但是该算法光线与物体的求交量庞大，严重制约着应用。本文从经典的光线跟踪算法出发，研究了目前光线跟踪算法的国内外研究状况，具体从改进的光线跟踪算法和光线跟踪算法的加速技术，并进行了对比和分析。最后对近几年的光线跟踪方法发展进行了总结，对未来研究热点及应用前景进行了展望。 关键词：可视化；光线跟踪算法；并行绘制；GPU Research Status and Prospect for ray tracing algorithms Abstract: As an classic algorithms of volume rendering in computer graphics, ray tracing algorithms is hindered by the huge computation cost in ray and volume. This paper summarizes the research status in ray tracing technology from the two main solutions: different extended ray tracing algorithms and the acceleration techniques in ray tracing algorithms. Comparison and analysis the different performance. Both current research focus and the future research prospect are also discussed in recent years. Key words: visualization; ray tracing algorithms; parallel rendering; GPU 引言 随着科学技术和计算机高速发展，人类已经进入到一个科技支撑的时代，在我们的生活中到处充满了高科技产品和技术，给我们的生活带来了改变和方便，其中计算机图形学的应用已经渗透到了各个工程技术领域，其已经成为计算机科学的重要学科之一，具有相当的重要性和无可替代的作用。计算机图形学自诞生以来得到了飞速发展，其通过计算机的输入设备、显示设备及绘制设备等对图形的表示、绘制、存储、显示等相关理论知识、算法技术进行研究的一门学科。真实感图形绘制是计算机图形学的主要研究内容之一，在虚拟现实、文物保护、影视游戏、三维动画、医学研究、建筑设计和系统仿真等领域中得到广泛应用，它追求对场景的逼真渲染[1]。其中逼真的图形绘制技术是最为活跃的研究领域之一。 光线跟踪算法是真实感图形绘制技术的主要算法之一，其原理简单，能够有效生成具有比较真实视观效果的各种各样的场景。该算法可通过一些光照明模型模拟在光源或环境光照射下物体表面发生的多种光照效果，例如漫反射、高光、镜面映像、场景消隐及阴影等。在计算机中对现实场景或是虚拟场景进行显示，除了要构建场景图形外，还要将场景中的各种光照效果模拟出来，这样生成的场景才能更逼真，光线跟踪算法就是既在几何上相似，也能模拟出大部分的光照效果的生成真实感图形的方法。光线跟踪算法是逆着真实光线的投射方向进行反向跟踪的，从视点向场景发射光线，光线与场景中的物体相交，计算光分量，因为视点向场景的光线较多，因而该算法光线与物体的求交量较大，但是因为其对场景的模拟的逼真，及其可以模拟漫反射、镜面反射、反射折射以及阴影等光照效果[1-2]。 进入90年代，随着计算机技术的发展，光线跟踪技术广泛应用于三维特技电影、电视广告、电子游戏的制作中，其应用领域也正在向如物理、化学、生物等其他学科领域渗透，其应用的范围正不断扩大，很多基于光线跟踪算法的新理论也应运而生，物理学中的相对论、地理中地层的绘图等与光线跟踪算法相结合的研究已经实现，极大的推动其学科的发展。可
光线追踪的应用及发展趋势
课程论文 课程论文题目：光线追踪的应用及未来发展 学院：人民武装学院 专业：计算机科学与技术 班级：物联人151 学号： 1500860346 学生姓名：谭朝艳 指导教师：宁阳 2016 年6 月3 日
目录 摘要 ............................................................... II 第一章绪论 . (1) 1.1 光线追踪的定义 (1) 1.2 光线追踪的原理 (1) 1.2.1 自然现象 (1) 1.2.2 光线追踪的原理 (1) 1.3 光线追踪的特点 (3) 1.3.1 光线追踪的优点 (3) 1.3.2 光线追踪的缺点 (3) 第二章光线追踪的应用 (4) 2.1 光线追踪在图形渲染中的应用 (4) 2.2 光线追踪在物理学中的应用 (4) 2.3 光线追踪在实际应用 (4) 2.4 实时跟踪 (4) 第三章光线追踪的未来发展趋势 (6) 3.1 光线追踪VS光栅化 (6) 3.2 显卡何时才能实时光线追踪 (7) 3.3 光线追踪的未来发展 (8)
光线追踪的应用及未来发展 摘要 光线跟踪是一种真实地显示物体的方法，该方法由Appe在1968年提出。光线跟踪方法沿着到达视点的光线的反方向跟踪，经过屏幕上每一个象素，找出与视线相交的物体表面点P0，并继续跟踪，找出影响P0点光强的所有光源，从而算出P0点上精确的光线强度，在材质编辑中经常用来表现镜面效果。光线跟踪或称光迹追踪是计算机图形学的核心算法之一。在算法中，光线从光源被抛射出来，当他们经过物体表面的时候，对他们应用种种符合物理光学定律的变换。最终，光线进入虚拟的摄像机底片中，图片被生成出来。 关键字：光线跟踪（Ray tracing），真实感
光线追踪实验报告
Ray Tracer---光线跟踪实验报告 711064XX XXX 一、实验目的 在计算机图形学课程作业中，题目要求是做Ray Tracing 或碰撞检测，其中对Ray Tracing 的要求是： (1)多种形状物体，Ball, box等 (2)包含多种材质物体：纯镜面反射、透明物体、纯漫反射、半透明物体等 (3)Moving in a 3D world (4)environment texture 二、实验原理 在这次实验中，使用了真正的光线跟踪算法，而不是采用环境纹理来反映周围环境。 1、光线跟踪简介 光线跟踪是一种真实地显示物体的方法，该方法由Appel在1968年提出为了 生成在三维计算机图形环境中的可见图像，光线跟踪是一个比光线投射或者 扫描线渲染更加逼真的实现方法。这种方法通过逆向跟踪与假象的照相机镜 头相交的光路进行工作，由于大量的类似光线横穿场景，所以从照相机角度 看到的场景可见信息以及软件特定的光照条件，就可以构建起来。当光线与 场景中的物体或者媒介相交的时候计算光线的反射、折射以及吸收。由于一 个光源发射出的光线的绝大部分不会在观察者看到的光线中占很大比例，这 些光线大部分经过多次反射逐渐消失或者至无限小，所以对于构建可见信息 来说，逆向跟踪光线要比真实地模拟光线相互作用的效率要高很多倍。计算 机模拟程序从光源发出的光线开始查询与观察点相交的光线从执行与获得正 确的图像来说是不现实的。 2
由以上经典的光线追踪算法可以发现，在此算法中，环境中的物体等模型，并不是 一次性的画好的，而是对整个场景一个像素一个像素的画上去的，光线跟踪算法中 的每一根光线要与场景中的每一个物体所含的每一个面求交。 三、光线跟踪算法实现 1、计算观察光线 首先需要确定光线的数学表达式。一条光线实际上只是一个起点和一个传播方向， 假设起点为O（x1，y1，z1），屏幕上一点为D（x2，y2，z2），则光线的方向dir（x3，y3，z3）为： dir=O–D； 即 在程序中，光线的起点定义为： 方向为： 由此可以确定一条光线
基于均值漂移与卡尔曼滤波的目标跟踪算法
２００７，４３（１２）ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用 １引言 视频图像序列中运动目标跟踪是智能监控系统中的重要一部分，是计算机视觉、目标识别与跟踪、安全监控等视频分析和处理应用的关键技术。均值漂移算法作为一种高效的模式匹配算法，已经被成功的应用在目标跟踪领域［１－４］。该算法利用梯度优化方法实现快速目标定位，能够对非刚性目标实时跟踪，对目标的变形、旋转等运动有较好的适用性，但是均值漂移算法在目标跟踪过程中没有利用目标在空间中的运动方向和运动速度信息，当周围环境存在干扰时，仅使用均值漂移算法容易丢失目标。Ｋａｌｍａｎ滤波器是一个对动态系统的状态序列进行线性最小方差估计的算法，具有计算量小，可实时计算的特点，可以准确的预测目标的位置和速度［５］。 考虑到目标运动过程中可能会受到场景中诸如遮挡、光照变化等因素的影响，本文在采用基于颜色直方图的均值漂移跟踪算法的同时，合理结合了Ｋａｌｍａｎ滤波对目标空间运动位置的预测，保证了目标运动的一致性和连贯性。每一帧图像分别采用这两种方法进行跟踪，根据干扰的不同情况，采用不同的比例因子将两个跟踪结果线性加权，从而得到目标的最终位置。在干扰较小情况下，均值漂移算法可以得到良好的跟踪效果，其跟踪结果占较大的比重，强干扰情况下，加大Ｋａｌｍａｎ预测结果的比重，克服干扰。 ２均值漂移跟踪算法 目标的直方图不受目标形状变化的影响，因此采用直方图作为目标的模式，依据颜色分布进行匹配具有较好的稳定性。假设被跟踪的目标是中心为ｙ０，窗宽为ｈ的矩形。目标外围的像素可能被遮挡或者受到背景的影响是相对不可靠的，为此对目标内不同位置的像素赋予不同的权重，位置与目标中心的距离越近其权重越大。 目标的加权颜色直方图［２］为 ｑｕ（ｙ）＝Ｃｈ ｎ ｉ＝１ !ｋ（‖ｙ０－ｘｉ ｈ ‖２）δ［ｂ（ｘｉ）－ｕ］（１）其中Ｃｈ为归一化系数，Ｃｈ＝ １ ｎ ｉ＝１ !ｋ（‖ｙ０－ｘｉ ｈ ‖２） 。 当前图像帧中以图像空间点ｙ为中心的候选图像区域内，象素点的加权直方图表示为： 基于均值漂移与卡尔曼滤波的目标跟踪算法 常发亮，刘雪，王华杰 ＣＨＡＮＧＦａ－ｌｉａｎｇ，ＬＩＵＸｕｅ，ＷＡＮＧＨｕａ－ｊｉｅ 山东大学控制科学与工程学院，济南２５００６１ ＳｃｈｏｏｌｏｆＣｏｎｔｒｏｌＳｃｉｅｎｃｅａｎｄＥｎｇｉｎｅｅｒｉｎｇ，ＳｈａｎｄｏｎｇＵｎｉｖｅｒｓｉｔｙ，Ｊｉ’ｎａｎ２５００６１，Ｃｈｉｎａ Ｅ－ｍａｉｌ：ｌｉｕｘｕｅ９３＠１６３．ｃｏｍ ＣＨＡＮＧＦａ－ｌｉａｎｇ，ＬＩＵＸｕｅ，ＷＡＮＧＨｕａ－ｊｉｅ．ＴａｒｇｅｔｔｒａｃｋｉｎｇａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｍｅａｎｓｈｉｆｔａｎｄＫａｌｍａｎｆｉｌｔｅｒ．ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ，２００７，４３（１２）：５０－５２． Ａｂｓｔｒａｃｔ：Ｍｅａｎｓｈｉｆｔａｌｇｏｒｉｔｈｍｄｏｅｓｎ’ｔｕｓｅｔｈｅｔａｒｇｅｔ’ｓｍｏｔｉｏｎｄｉｒｅｃｔｉｏｎａｎｄｓｐｅｅｄｉｎｆｏｒｍａｔｉｏｎｉｎｐｒｏｃｅｓｓｏｆｔａｒｇｅｔｔｒａｃｋｉｎｇ．Ｗｈｅｎａｆｆｅｃｔｅｄｂｙｄｉｓｔｕｒｂａｎｃｅｉｔｅａｓｉｌｙｆａｉｌｓｔｏｔｒａｃｋｔｈｅｔａｒｇｅｔ．Ｋａｌｍａｎｆｉｌｔｅｒｉｎｇｃａｎｐｒｅｄｉｃｔｔｈｅｐｏｓｉｔｉｏｎａｎｄｖｅｌｏｃｉｔｙｏｆｔｈｅｔａｒｇｅｔｅｘａｃｔｌｙ．ＡｎａｌｇｏｒｉｔｈｍｃｏｍｂｉｎｅｄＫａｌｍａｎｆｉｌｔｅｒｉｎｇｗｉｔｈｍｅａｎｓｈｉｆｔａｌｇｏｒｉｔｈｍｉｓｐｒｏｐｏｓｅｄｉｎｔｈｉｓｐａｐｅｒ．Ｋａｌｍａｎｆｉｌｔｅｒｉｎｇｉｓｕｓｅｄｔｏｐｒｅｄｉｃｔｔｈｅｐｏｓｉｔｉｏｎａｎｄｖｅｌｏｃｉｔｙｏｆｔｈｅｔａｒｇｅｔ．Ａｃｃｏｒｄｉｎｇｔｏｄｉｆｆｅｒｅｎｔｄｉｓｔｕｒｂａｎｃｅｃｉｒｃｕｍｓｔａｎｃｅｓ，ｔｈｅｔｗｏａｌｇｏｒｉｔｈｍｓｔｒａｃｋｉｎｇｒｅｓｕｌｔｓａｒｅｄｏｎｅｗｉｔｈｌｉｎｅｒｗｅｉｇｈｔｍｅｔｈｏｄｂｙｕｓｉｎｇｄｉｆｆｅｒｅｎｔｓｃａｌｅｆａｃｔｏｒｓｔｏｇｅｔｔｈｅｆｉｎａｌｐｏｓｉｔｉｏｎｏｆｔｈｅｔａｒｇｅｔ．Ｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｓｈｏｗｔｈｅｇｏｏｄｐｅｒｆｏｒｍａｎｃｅｓｏｆｔｈｅｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍ． Ｋｅｙｗｏｒｄｓ：ｔａｒｇｅｔｔｒａｃｋｉｎｇ；ｏｃｃｌｕｓｉｏｎ；ｍｅａｎｓｈｉｆｔ；Ｋａｌｍａｎｆｉｌｔｅｒ 摘要：均值漂移算法在目标跟踪过程中没有利用目标的运动方向和速度信息，在目标受到干扰时容易跟踪失败，而Ｋａｌｍａｎ滤波能够较为准确地预测目标的速度和位置。因此，提出了一种结合均值漂移与Ｋａｌｍａｎ滤波的跟踪算法，使用Ｋａｌｍａｎ滤波对目标运动速度和空间位置进行预测。根据干扰的不同情况，使用不同的比例因子将两算法的跟踪结果线性加权得到目标的最终位置。实验结果表明该算法是可行有效的。 关键词：目标跟踪；遮挡；均值漂移；Ｋａｌｍａｎ滤波 文章编号：１００２－８３３１（２００７）１２－００５０－０３文献标识码：Ａ中图分类号：ＴＰ３９１．４ 基金项目：山东省自然科学基金（ｔｈｅＮａｔｕｒａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎｏｆＳｈａｎｄｏｎｇＰｒｏｖｉｎｃｅｏｆＣｈｉｎａｕｎｄｅｒＧｒａｎｔＮｏ．Ｚ２００５Ｇ０３）。 作者简介：常发亮（１９６５－），男，教授，主要从事模式识别、机器视觉与智能控制的理论及应用研究；刘雪（１９８２－），女，硕士研究生，主要从事计算机视觉、图像处理与分析研究；王华杰（１９８０－），男，硕士研究生，主要从事机器视觉方面的研究。 ５０
在光线跟踪算法的递归过程中
在光线跟踪算法的递归过程中，加速算法有哪几种？说明他们分别使用与哪些场合光线跟踪的基本原理 由光源发出的光到达物体表面后，产生反射和折射，简单光照明模型和光透射模型模拟了这两种现象。在简单光照明模型中，反射被分为理想漫反射和镜面反射光，在简单光透射模型把透射光分为理想漫透射光和规则透射光。由光源发出的光称为直接光，物体对直接光的反射或折射称为直接反射和直接折射，相对的，把物体表面间对光的反射和折射称为间接光，间接反射，间接折射。这些是光线在物体之间的传播方式，是光线跟踪算法的基础。 最基本的光线跟踪算法是跟踪镜面反射和折射。从光源发出的光遇到物体的表面，发生反射和折射，光就改变方向，沿着反射方向和折射方向继续前进，直到遇到新的物体。但是光源发出光线，经反射与折射，只有很少部分可以进入人的眼睛。因此实际光线跟踪算法的跟踪方向与光传播的方向是相反的，而是视线跟踪。由视点与象素(x,y) 发出一根射线，与第一个物体相交后，在其反射与折射方向上进行跟踪，如图4. 6.1所示。 图4.6.1 基本光线跟踪光路示意
为了详细介绍光线跟踪算法，我们先给出四种射线的定义与光强的计算方法。在光线跟踪算法中，我们有如下的四种光线：视线是由视点与象素 (x，y)发出的射线；阴影测试线是物体表面上点与光源的连线；以及反射光线与折射光线。当光线V与物体表面交于点P时，点P分为三部分，把这三部分光强相加，就是该条光线V在P点处的总的光强： a) 由光源产生的直接的光线照射光强，是交点处的局部光强，可以由下式计算： b) 反射方向上由其它物体引起的间接光照光强，由 I s K s'计算，I s通过对反射光线的递归跟踪得到 c) 折射方向上由其它物体引起的间接光照光强，由I t K t'计算，I t通过对折射光线的递归跟踪得到。 在有了上面介绍的这些基础之后，我们来讨论光线跟踪算法本身。我们将对一个由两个透明球和一个非透明物体组成的场景进行光线跟踪（图4.6.2）通过这个例子，可以把光线跟踪的基本过程解释清楚。
光线追踪算法的GPU加速算法(学习版)
加速构建KD树的方法 （声明：本文仅为笔者的相关整理和理解） 摘要：光线追踪算法是用来生成照片逼真的渲染效果最有前途的算法之一。然而，算法的计算开销使算法远达不到实时显示效果。许多学者提出了不同的改进，不断加速光线追踪算法。在本文中，我们将介绍一些的改进方法的关键步骤，例如GPU构建kd树，和专用硬件加速引擎。 关键词：KD树光线追踪 GPU 硬件 A Method Of Accelerating The Construction Of KD-Tree Abstract: The ray tracing algorithm is one of the most promising algorithms, which is used to generate photo realistic rendering effects. However, the expense cost of computing puts the real time ray tracing far from reaching. Many scientists come up with different improvements to stand closer to, real time ray tracing, the terminal goal. In this paper, we will introduce some key points of certain outstanding improvements, such as, constructing the KD tree on GPU, and dedicated hardware acceleration engine. Key words: KD Tree ray tracing GPU hardware 一、简介 光线追踪算法在真实感填充方面的效果非常出色，考虑了不同方向反射光线与折射光线对空间特定点亮度的影响，通过多次的迭代达到真实的效果。然而多次迭代跟踪反射光线与折射光线带来的结果就是三维空间中要进行大量的求交点运算，特别现在提倡的高清的时代，在2560*1440的区域上进行光线追踪算法，每秒几乎要发射出20亿条光线。有学者提出区域分割、八叉树、KD树等方法来快速计算光线与物体表面交点。区域分割是将整个空间划分成为相等大小的子区域，如果某个子区域内有实体，就标记该区域为有实体。八叉树是在空间划分上进行的一个改进，空间不是被等分，而是将实体使用大小不同的正方体来表示实体，算法中大小相邻的正方形空间之间大小比例是8:1。KD树可以看作是八叉树的一种改进，KD在划分子空间的时候总是选取散度最大的坐标轴方向，使得空间划分更有效。所以KD树是使用最广泛，并被认为是最有前景的方法。在加速构建KD树的领域，研究人员也做出了许多探索，部分小组成功的把构建KD树的算法移植到4核的CPU上运行。所以在并行计算能力非常强大的GPU上实现KD树构建算法成了很热的一个方向，与此同时，部分研究人员把目光转向专用硬件芯片FPGA，并取得了很好的成绩。 本文的结构是这样安排的：我们在第二本分介绍传统的序列SAH KD树的构建方法；在随后的第三部分介绍并行化计算SAH代价和排序的算法；在第四部分介绍现已有的硬件专用芯片；第五部分是实验结果的展示；最后是对本文的总结。