基于路段空间划分的车载摄像机视野优化融合方法

1.本发明涉及基于路段空间划分的车载摄像机视野优化融合方法，属于智能交通领域。


背景技术：

2.车联网技术正在迅速发展，全球范围内都得到了大量的关注和投资。这项技术可以为我们的现代交通提供前所未有的便利性、效率和安全性。全局视野是车联网的一个关键问题，主要是指通过车辆之间的交互作用，每一台车都可以获得其周围环境信息的全貌。这使得每辆车辆可以以最完整、准确的方式感知和应对所有情况，从而大大提高了行车的安全和效率。实现全局视野的构建是车联网研究中的一个核心问题，意义重大。然而，在当今的车联网技术条件下，数据传输和运行效率是实现全局视野构建的制约因素之一。由于每个车辆通过传感器或者摄像机获得的信息量巨大，因此在传输和分析数据时需要大量的网络带宽和处理能力。这可能会导致通信延迟过高、数据丢失和复杂性增加，使得实现完整的全局视野受到困难。汽车采集到的传感器或者摄像机数据可以直接发送至边缘服务器进行实时处理，分析车辆状态、行驶路线等信息，并根据分析结果实现智能驾驶、车联网、车辆安全等应用，而边缘服务器可以通过与汽车的交互，实现智能控制功能。
3.基于上述问题和功能，本专利提出一种以减少数据传输和运行效率为目标的全局视野构建算法。这种算法采用了基于路段空间划分的车载摄像机视野优化融合方法，它可以在计算上减少冗余操作，从而进一步优化算法以提高通信和编译速度和准确性。这种算法可以帮助减少一个数据包传输所需的时间和能源，同时减少运行算法所需要的复杂度和减少边缘服务器复杂度。这些优点使得该算法在实现全局视野构建方面具有巨大的潜力和预期效果。本发明的技术方案不仅可以将这些问题的影响降到很小，并为更好地实现全局视野的构建提供了一种有效的方法，有望在车联网技术研究和应用中得到广泛应用。


技术实现要素：

4.本发明要解决的问题是：针对边缘服务器信号覆盖区域内的若干车辆，如附图1所示，每辆配备四个摄像机以记录可见视野，需确定一种车载摄像机优化组合方案，以基于该组合内所有摄像机上传的局部视野图片对整个路段的全局视野进行有效构建。其中，每一辆车的前置摄像机和后置摄像机的可见视野距离一致，左右两个摄像机可见视野距离一致，每一个摄像机的视野定义为一个梯形视野，将整个路段空间划分为若干大小相同的栅格。
5.本发明提出了一种基于路段空间划分的车载摄像机视野优化融合方法，方法包括(1)数据预处理阶段：基于广度优先和并查集优化的栅格连通组件构建算法(bgbc)；(2)初始分配阶段：基于连通分量的贪心分配算法(ccfa)；(3)优化阶段：贪心策略引导的分段式遗传算法优化；(4)对比实验验证算法的性能指标四个核心步骤。具体如下：
6.1.基于广度优先和并查集优化的栅格连通组件构建算法
7.基于空间划分的全局视野，本发明已经获取到了每一个车辆的每一个摄像机的候选栅格集合g
l
(l＝0，1，2...m，m为预分配栅格数目)。此时所有预分配栅格在整个道路上是不连续的，零散的。分配栅格给摄像机是为了实现全局视野的高效上传并且降低上传的重复数据以及数据量。若某些栅格的候选摄像机列表一致，那么这些栅格连续的概率很高。而若一些连续栅格分别被分配到不同的摄像机中，那么这些摄像机因为全部能看到这些连续栅格，故会导致这些摄像机都需要上传这些重叠的栅格所表示的视野，从而会极大的浪费上传带宽和存储空间。通过尽可能的将一些连续栅格分配给同一个摄像机，可以最大可能避免这种大量重叠的情况，提高数据的利用率。本发明在于提出了这些全局视野的融合优化方案。利用广度优先算法和并查集构建出栅格连通组件，分为两个步骤：(1)构建并查集；(2)广度优先搜索构建连通组件。
8.步骤11：并查集(disjoint-set)本身是一种数据结构，同时也是一种基于该数据结构的算法。在该数据结构中，每一个元素都有一个parent表示其祖先，相当于每个元素都属于某个集合，我们可以用该数据结构实现集合操作，包括建立集合，合并集合，查找元素，集合大小等，达到对集合元素的快速查找和合并的目的。在本发明中，使用并查集来实现数据点的连通性分组。我的并查集支持合并(union)，查找(find)和连接(connect)。查找是用来查询某个节点是否属于某个已知的连通分量组，合并操作是用来将两个连通分量组合成一个，连接阶段是用来获取每一个连通分量具体包含的节点。
9.不同的连通分量之间相互独立，同一连通分量内的所有节点都可以相互到达。设计时用parent数组表示每个节点的父节点，size数组表示每个连通分量的大小。在进行节点合并的时候，先找到节点所在连通分量的根节点，然后如果两个节点属于同一个连通分量，就不用做任何事情，否则将其中规模较小的连通分量合并到规模较大的连通分量上，并且更新根节点对应连通分量的大小信息。
[0010][0011]
在并查集中，每个元素都有一个父节点，当一个元素的父节点为其本身时，它表示自己是一个独立的集合，我这里采用基于路径压缩的查找，这种方式是在查找的过程中，不仅仅找到了集合的代表元素，还将路径上的所有元素的父节点都直接指向代表元素。这种方式的时间复杂度通常比基于树结构的查找更优。
[0012][0013]
接下来需要获取某个节点所在的连通分量中的所有节点坐标。我们创建了一个connected列表，用于存储连通分量中节点坐标。随后，遍历所有节点，将节点的坐标加入到列表中，如果该节点所在的连通分量的根节点是rootp。最后返回所有节点坐标组成的列表connected，即可得到某个节点所在连通分量中的所有节点坐标。
[0014]
步骤12：广度优先搜索构建连通组件。采用图论中的广度优先搜索算法，将每一个栅格构建为一个节点，选择的起始节点为整个道路的最左下角开始。对起始节点开始广度优先搜索，在遍历过程中，只处理预分配栅格所表示的节点，将候选摄像机列表一致的节点构建到一个连通分量中。在搜索过程中，遍历与该节点相邻的节点，若该节点不属于预分配节点，则跳过；否则从下到上、从左到右，每次遍历到一个格子时，都会先判断它周围的格子是否符合合并条件。如果符合，就将它们合并起来，然后加入队列继续遍历下去。即判断该节点的候选摄像机列表是否和上一个节点的候选摄像机列表一致，若一致则将该节点与上一个节点合并到一个连通分量中。当遍历到最后一个节点的时候，所有预分配上已经按照合并条件，形成了不同的连通分量集合，每一个连通分量集合中的栅格的候选摄像机列表都是一致的。算法设计如下：
[0015]
[0016]
2.基于连通分量的贪心分配算法
[0017]
以连通分量为基本单位进行贪心算法分配，该算法用于进行视野分配方案的计算。因为我们对数据预处理，所以此时，我们不需要对所有预分配栅格进行判断分配，在数据量比较大的时候，搜索效率是非常低的。采用并查集可以将搜索时间效率降低到o(1)。在这个应用场景中，每个摄像机都有自己的视野范围，那么选取能看到最多栅格的摄像机其实就是选取能够覆盖最多栅格的摄像机。这样做的优势在于能够充分利用摄像机的视野范围，将尽可能多的栅格分配给能看到它们的摄像机。从而减少最终需要上传图片的摄像机数量。操作步骤：我们只需要处理每个连通分量的根节点，将该根节点所属的连通分量的所有栅格都分配给候选摄像机列表中能看到最多栅格的那个摄像机。并且在在分配连通分量的时候，比如一个连通分量g1的候选摄像机列表是“abcde”，另一个连通分量g2的候选摄像机列表是“abh”，如果g1分配的时候分配给了a，那么g2分配的时候，若h摄像机之前没有被分配过，那么基于贪心策略，认为该摄像机后面也不会被分配。所以依然是优先也是分配给摄像机a，这样就能进一步提升摄像机a的利用率。算法思路如下所示：
[0018][0019]
3.贪心策略引导的分段式遗传算法
[0020]
步骤31，贪心策略引导的分段式遗传算法。利用贪心策略虽然得出一个近似解。贪心算法是一种局部最优策略的组合，不能保证得到最优解，一般情况下之只能得到一个接近最优解的解决方案。所以我们需要利用遗传算法来优化。分段式遗传算法需要以下几个步骤：(1)设置编码方式；(2)基于贪心策略地初始种群；(3)设置适应度函数；(4)并发式单点交叉操作；(5)并发式变异操作；(6)轮盘赌选择策略
[0021]
(1)编码方式。采用的是分段式实数编码。模型的预分配是栅格集合，将他分配到对应的车辆以及摄像机中。此外这是带约束的遗传算法分配。将染色体分段，均等分。我们提出以下的基因表示，如图2所示。集合g中第i个元素，那么按照栅格在集合中的顺序可以得到该元素的后续按摄像机和车辆列表集合di，从该集合中选择一个元素，这样就保证了一个元素必须并只能分配到一个子集，从而不会导致产生任何违反约束条件的基因，很好
的适用于本发明。
[0022]
(2)初始种群。以2得出来的一个最优解作为遗传算法的初始种群的一个染色体(chromosome)输入。预分配栅格集合长度为m，采用的是分段式实数编码，在本发明中染色体长度为m*3，将基因链分为m段，每一段对应着一个预分配栅格，每一段中前两位对应着该栅格的分配车辆编号，第三位对应的该栅格的分配摄像机编号。如附图2。通过随机变异贪心算法得到的最优解，生成最终的初始种群。增加了随机性，能使遗传算法更快的搜索到最优解。每一个染色体的长度即基因数量由所有计算任务的数量确定。由于种群由多个染色体组成，在本发明中，种群由数组pop表示；种群大小定义为popsize。
[0023]
(3)适应度函数。为了在选择过程中衡量每一个个体的优异程度，需要设计一个能直接反应个体性能的适应度函数(fitness function)，在本发明中，因为我们目标是以尽可能少的摄像机分配到所有预分配视野。所以适应度函数设置为最终被分配到的摄像机个数最少。适应度函数为该染色体基因链上的被分配到的不同摄像机个数，适应度函数的值成为适应度值(fitness value)，计算方式如下：
[0024][0025]
(4)并发式交叉操作。我设置的单调交叉，单点杂交：设定杂交概率与杂交个体，按照断裂点进行染色体杂交。示例：杂交前：a＝《123234|081162》，b＝《062031|182113》；杂交后：a＝《123234|182113》，b＝《062031|081162》。交叉操作交叉率为80％，平均为80％的染色体进行交叉。因为我们的个体之间是分段式，每一段都对应着一个预分配栅格，交叉之后，我们会需要验证交叉操作，是可以满足约束条件的情况下进行的。单调交叉是基于随机产生交叉点，是在遗传算法的交叉操作中，一种相对简单而有效的交叉方式。它的基本思想是尽可能地保留父代染色体中的基因序列信息，同时确保每个基因在交叉后仍只出现一次。算法思路如下：
[0026][0027]
(5)变异操作。基本思想是：根据变异概率选择变异位点，将实数位改变。变异的时候，因为个体的每一段和该栅格对应的候选车辆/摄像机之间存在约束依赖关系，所以只能在该栅格的候选摄像机集合中进行变异。变异概率设置为1％。
[0028]
(6)选择操作。其基本思想是优秀个体被选中的概率与其适应度值成正比，即按由个体适应度值所决定的某个规则选择将进入下一代的个体。首先：计算每个个体的适应度值：对于每个个体，根据适应度函数计算出相应的适应度值。接着：随机产生每个个体的选择概率：对于每个个体，根据其适应度值计算其在本轮选择中被选中的概率。常用的方法是根据适应度函数的值来计算每个个体的选择概率，根据适应度函数的值来计算每个个体的选择概率。具体来说，将所有个体的适应度函数的值相加作为分母，每个个体的适应度函数的值除以总和作为该个体的选择概率。
[0029][0030]
然后：创建轮盘，按照计算出的每个个体的选择概率比例，创建轮盘。具体来说，将0到1的随机数分成多个区间，每个个体的区间长度比例与其选择概率相同。最后：选择个体：随机生成一个0到1之间的随机数，根据落到哪个个体的区间上，选择该个体进入下一代。重复这个过程，直到选择的个体数量与父代相同。在整个算法中，通常会将当前代种群中的染色体按照其适应值的大小进行排序，并根据一定的概率选择一些个体作为下一代种群的父代。因此，在选择操作中，我们需要计算每个个体的适应值，并使用适当的方法选择一些个体。具体来说，我们首先定义了三个数组evals、p和q，分别用于存储所有染色体的适应值、选择概率和累计概率。然后，我们使用一个循环遍历整个种群，计算每个个体的适应值，并将其存储在evals数组中。在计算适应值的同时，我们还要记录下来种群中的最优解，以及相应的个体信息。接下来，我们计算各染色体的选择概率和累计概率，用于构造选择所用的轮盘。具体地，我们使用两个循环遍历整个数组p和q。具体设计算法如下：
[0031][0032]
(7)迭代次数。设置的为200次。实验证明，该迭代次数已经能很好的得到很好的解，并且若迭代20次，还没有出现更优解，那么则结束迭代，认为已经找到了最优解。
[0033]
4.对比算法效果验证
[0034]
从该结果可以见出，基于连通分量的分段式贪心遗传分配算法得出的最优解明显优于遗传算法和贪心算法，在运行时间性能上，远远低于遗传算法的运行时间。在通过最朴素的分配方案，运行时间达到了秒级别，遗传算法也能达到几包毫秒，但是贪心算法和基于连通分量地分段式贪心遗传算法却能在很少的时间上得到一个比较好的解。尽管基于连通分量的分段式贪心遗传算法在时间效率上略低于贪心算法和基于连通分量的贪心算法，时间效率都控制在几十毫秒之内。但是，在得到的最优解上却能明显优于贪心算法，例如在道路长度设置为1000，宽度为20，栅格边长为1，前后摄像机视野距离为16，左右摄像机视野距离为12的时候，本发明的方法在得到的解上，需要上传图片的摄像机数量上明显少于贪心算法，例如在车辆个数为20的时候，本发明的方法得出的被分配到的摄像机个数比贪心算法减少了了35％左右，在车辆个数逐渐增多的情况下，例如车辆个数为28时，减少了45％左右。故通过实验验证了该算法的实时性和有效性。大幅度减少了需要上传数据的车路车辆个数以及图像数量。
附图说明
[0035]
图1为单车梯形视野示意图
[0036]
图2为分段式遗传算法编码方式示意图
具体实施方式
[0037]
为了更好的解释本发明的内容，现给出一个实例进行具体说明。
[0038]
对于预分配栅格的集合获取方式及见附图1，可以很直观的获取，为了能很好的说明实例，在这里进行小规模数据量的参数设置。这里设置道路长度为40m，宽6m，栅格长度甚至为2m，宽度设置为2m，障碍物个数为1个，前置摄像机和后置摄像机视野距离是6m，左向和右向摄像机的可见视野距离是3m。通过随机将车辆放置到该道路上，车辆的位置分别是：
[0039]
表1车辆位置
[0040][0041]
下面按照上面解释的计算公式，分别计算出每个摄像机梯形视野对应的栅格索引集合为：
[0042]
表2预分配栅格
[0043][0044][0045]
首先将这些预分配栅格按照候选摄像机一致的原则构建连通分量，并且将保存在并查集中。比如栅格(1，1)和(2，2)的候选摄像机列表都是(7，1)和(9，1).表示这两个栅格都能被7号车的1号摄像机和9号车的1号摄像机看见。那么将这两个栅格构建为一个连通分量。并且放入到并查集中。然后根据上面设计的贪心算法，将每个连通分量中的每个节点(栅格)分配给候选摄像机中能看到最多栅格的摄像机，那么这个情况下，(1，1)和(2，2)是分配给7号车的1号摄像机，因为该摄像机能看到五个栅格。由此依次分配完所有预分配栅格。
[0046]
再将该近似解随机变异，生成遗传算法的初始种群。进入分段式遗传算法进行优化。得到最终的解。
[0047]
表3最终分配方案
[0048]

技术特征：
1.一种基于路段空间划分的车载摄像机视野优化融合方法，其特征在于提出了一种基于路段空间划分的车载摄像机视野融合优化方法，通过数据预处理、初始分配和优化三个阶段的组合，能够有效地减少减少冗余操作，从而进一步优化算法以提高通信和编译速度和准确性，实现了计算资源的优化分配。在优化阶段采用贪心策略引导的分段式遗传算法，进一步优化了视野分配方案，提高了车载摄像机实时监控能力和交通信息处理精度。。方法可行高效。该方法包括下列步骤：(1)数据预处理阶段：基于广度优先和并查集优化的栅格连通组件构建算法(bgbc)；(2)初始分配阶段：基于连通分量的贪心分配算法(ccfa)；(3)优化阶段：贪心策略引导的分段式遗传算法优化。2.根据权利要求1所述的一种基于路段空间划分的车载摄像机视野优化融合方法，其特征在于，在步骤1)中，本发明在于提出了基于bfs和并查集地数据构建全局视野连通分量。利用广度优先算法和并查集构建出栅格连通组件，分为两个步骤：(1)构建并查集；(2)广度优先搜索构建连通组件。采用图论中的广度优先搜索算法，将每一个栅格构建为一个节点，选择的起始节点为整个道路的最左下角开始。对起始节点开始广度优先搜索，在遍历过程中，只处理预分配栅格所表示的节点，将候选摄像机列表一致的节点构建到一个连通分量中。为之后的视野栅格分配提供了数据基础。3.根据权利要求1所述的一种基于路段空间划分的车载摄像机视野优化融合方法，其特征在于，在步骤2)中，我们只需要处理每个连通分量的根节点，将该根节点所属的连通分量的所有栅格都分配给候选摄像机列表中能看到最多栅格的那个摄像机。并且通过基于贪心策略，在候选摄像机列表存在交集的情况下，优先分配给已经被分配的摄像机。每一步选择都采取当前状态下最优的策略，以期望达到全局最优解。为了实现最大化视野覆盖度和图像质量的目标，此方法还计算了每个可选摄像机方案中已被分配的相机数量，实现了计算视野融合度的操作进一步最大化利用每一个摄像机的可见视野。4.根据权利要求1所述的一种基于路段空间划分的车载摄像机视野优化融合方法，其特征在于，在步骤3)中，本发明设计了一种贪心策略引导的分段式遗传算法。以贪心策略得到的分配方案为基础，进入分段式遗传算法。将遗传算法得出的解随即变异作为遗传算法的初始种群，并且采用分段式实数编码，满足问题中的约束条件。将得出来的解作为最终的结果。经过验证，具有很好的实验效果。

技术总结
车联网构建全局视野这一关键问题，主要是指通过车辆和边缘服务器之间的交互作用，每一台车都可以获得其周围环境信息的全貌。然而，在当今的车联网技术条件下，数据传输和运行效率是实现全局视野构建的制约因素之一。为此，本文设计了一种基于路段空间划分的车载摄像机视野优化融合方法，方法包括1)数据预处理：基于广度优先和并查集优化的栅格连通组件构建算法(BGBC)；(2)初始分配：基于连通分量的贪心分配算法(CCFA)；(3)优化：贪心策略引导的分段式遗传算法优化；(4)对比实验验证性能指标四个步骤。这种算法可以帮助减少一个数据包传输所需的时间和能源，同时减少运行算法所需要的复杂度和减少边缘服务器消耗。的复杂度和减少边缘服务器消耗。的复杂度和减少边缘服务器消耗。


技术研发人员：吴孝宇 刘茜萍
受保护的技术使用者：南京邮电大学
技术研发日：2023.04.12
技术公布日：2023/7/12