Kinect体感游戏控制器的手势检测方法研究(4)
2.1 dijkstra算法的研究
2.1.1 dijkstra定义
Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表的方式，本文中均采用永久和临时标号的方式。[5]
2.1.2 问题描述
在无向图 G=(V,E) 中，假设每条边 E[i] 的长度为 w[i]，找到由顶点 V0 到其余各点的最短路径。（单源最短路径）
2.1.3 迪杰斯特拉(Dijkstra)算法思想
按路径长度递增次序产生最短路径算法：
把V分成两组： （1）S：已求出最短路径的顶点的集合；（2）V-S=T：尚未确定最短路径的顶点集合 ；
将T中顶点按最短路径递增的次序加入到S中，保证：（1）从源点V0到S中各顶点的最短路径长度都不大于从V0到T中任何顶点的最短路径长度；（2）每个顶点对应一个距离值。 S中顶点：从V0到此顶点的最短路径长度。T中顶点：从V0到此顶点的只包括S中顶点作中间 。顶点的最短路径长度 。依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和（反证法可证）
求最短路径步骤：
算法步骤如下：
（1） 初使时令 S={V0},T={其余顶点}，T中顶点对应的距离值。
若存在<V0,Vi>，d(V0,Vi)为<V0,Vi>弧上的权值；
若不存在<V0,Vi>，d(V0,Vi)为∝ 。
（2）从T中选取一个其距离值为最小的顶点W且不在S中，加入S。
（3） 对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值。
重复上述步骤2、3，直到S中包含所有顶点，即S=T为止 [5]
2.1.4 迪杰斯特拉算法的原理
首先，引进一个辅助向量D，它的每个分量D表示当前所找到的从始点v到每个终点vi的最短路径的长度。如D[3]=2表示从始点v到终点3的路径相对最小长度为2。这里强调相对就是说在算法过程中D的值是在不断逼近最终结果但在过程中不一定就等于最短路径长度。它的初始状态为：若从v到vi有弧，则D为弧上的权值；否则置D为∞。显然，长度为 D[j]=Min{D | vi∈V} 的路径就是从v出发的长度最短的一条最短路径。此路径为(v,vj)。 那么，下一条长度次短的最短路径是哪一条呢？假设该次短路径的终点是vk，则可想而知，这条路径或者是(v,vk)，或者是(v,vj,vk)。它的长度或者是从v到vk的弧上的权值，或者是D[j]和从vj到vk的弧上的权值之和。 一般情况下，假设S为已求得最短路径的终点的集合，则可证明：下一条最短路径（设其终点为X）或者是弧(v,x)，或者是中间只经过S中的顶点而最后到达顶点X的路径。因此，下一条长度次短的最短路径的长度必是D[j]=Min{D | vi∈V-S} 其中，D或者是弧(v,vi)上的权值，或者是D[k](vk∈S)和弧(vk,vi)上的权值之和。 迪杰斯特拉算法描述如下： 1）arcs表示弧上的权值。若不存在，则置arcs为∞（在本程序中为MAXCOST）。S为已找到从v出发的最短路径的终点的集合，初始状态为空集。那么，从v出发到图上其余各顶点vi可能达到的最短路径长度的初值为D=arcs[Locate Vex(G,v),i] vi∈V 2）选择vj，使得D[j]=Min{D | vi∈V-S} 3）修改从v出发到集合V-S上任一顶点vk可达的最短路径长度。[5]
2.2 将dijkstra算法应用到深度图像中
2.2.1 深度图像
上一篇：智能手机电影订票系统网站设计