CN106292673A

CN106292673A - A kind of method for optimizing route and system

Info

Publication number: CN106292673A
Application number: CN201610863868.3A
Authority: CN
Inventors: 李坚强; 邓根强; 李赛玲; 明仲
Original assignee: Shenzhen University
Current assignee: Shenzhen University
Priority date: 2016-09-29
Filing date: 2016-09-29
Publication date: 2017-01-04
Anticipated expiration: 2036-09-29
Also published as: CN106292673B

Abstract

The present invention is applicable to the field of computer technology, and provides a path optimization method and system. The method includes: after correcting the image by polynomial transformation, detecting the edge of the obstacle in the image; marking the vertex of the obstacle, and forming a first path by selecting vertices of the obstacle; sequentially performing crossover and mutation operations on the first path to form a second path; selecting a sub-path in the second path according to the preset number of vertices, and Judging whether the start point and the end point in the sub-path are directly accessible, so as to determine the optimal path. The present invention makes the outline of obstacles in the image clearer by processing the image, so as to improve the accuracy of path planning, and sequentially processes the sub-paths on the basis of global path planning, further improving the accuracy of path planning , improve the work efficiency of the robot.

Description

A route optimization method and system

技术领域technical field

本发明属于计算机技术领域，尤其涉及一种路径优化方法及系统。The invention belongs to the technical field of computers, and in particular relates to a path optimization method and system.

背景技术Background technique

路径规划是智能机器人导航技术中不可缺少的重要组成部分，也是现阶段智能机器人研究的主要研究方向，良好的路径规划可以节省机器人大量的作业时间以及减少机器人的损耗，尤其是在灾后救援领域发挥更为重要的作用。影响路径规划有两个方面：一个是从空中拍摄图像，由于受限于环境和技术，拍摄的角度不能完全垂直于地面，因此拍摄角度对地面的障碍物的轮廓有着很大的影响，容易引起误判，从而影响规划效果；另一个是采用全局路径规划方法是在环境信息全部已知的情况下，通过全局路径规划找到优选地的路径，计算量太大，实时性欠佳。Path planning is an indispensable and important part of intelligent robot navigation technology, and it is also the main research direction of intelligent robot research at this stage. Good path planning can save a lot of working time and reduce the loss of robots, especially in the field of post-disaster rescue. more important role. There are two aspects that affect path planning: one is to shoot images from the air. Due to the limited environment and technology, the shooting angle cannot be completely perpendicular to the ground, so the shooting angle has a great influence on the outline of obstacles on the ground, which is easy to cause Misjudgment, thus affecting the planning effect; the other is to use the global path planning method to find the optimal path through the global path planning when all the environmental information is known, the calculation amount is too large, and the real-time performance is not good.

发明内容Contents of the invention

本发明的目的在于提供一种路径优化方法及系统，旨在解决现有技术中路径规划受限于图像质量与数据计算量，导致无法在短时间找到更加优化的路径。The purpose of the present invention is to provide a path optimization method and system, aiming at solving the limitation of image quality and data calculation amount in path planning in the prior art, which makes it impossible to find a more optimized path in a short time.

一方面，本发明提供了一种路径优化方法，所述方法包括下述步骤：On the one hand, the present invention provides a kind of path optimization method, described method comprises the following steps:

利用多项式变换对图像进行校正后，对图像中障碍物的边缘进行检测；After the image is corrected by polynomial transformation, the edge of the obstacle in the image is detected;

对所述障碍物的顶点进行标记，并通过选取所述障碍物的顶点形成第一路径；marking the vertices of the obstacle, and forming a first path by selecting the vertices of the obstacle;

对所述第一路径依次通过交叉以及变异操作，形成第二路径；sequentially performing crossover and mutation operations on the first path to form a second path;

按照预设顶点数量，在所述第二路径中选取子路径，并判断所述子路径中的起点与终点之间能否直达，以确定优化路径。Selecting a sub-path in the second path according to the preset number of vertices, and judging whether the start point and the end point in the sub-path are directly accessible, so as to determine an optimized path.

另一方面，本发明提供了一种路径优化系统，所述系统包括：In another aspect, the present invention provides a path optimization system, the system comprising:

图像处理单元，用于利用多项式变换对图像进行校正后，对图像中障碍物的边缘进行检测；The image processing unit is used to detect the edge of the obstacle in the image after correcting the image by polynomial transformation;

第一路径形成单元，用于对所述障碍物的顶点进行标记，并通过选取所述障碍物的顶点形成第一路径；a first path forming unit, configured to mark vertices of the obstacles, and form a first path by selecting vertices of the obstacles;

第二路径形成单元，用于对所述第一路径依次通过交叉以及变异操作，形成第二路径；以及The second path forming unit is configured to sequentially perform crossover and mutation operations on the first path to form a second path; and

路径优化单元，用于按照预设顶点数量，在所述第二路径中选取子路径，并判断所述子路径中的起点与终点之间能否直达，以确定优化路径。The path optimization unit is configured to select a sub-path in the second path according to the preset number of vertices, and determine whether the start point and the end point in the sub-path are directly accessible, so as to determine an optimized path.

本发明实施例通过对图像进行处理，使得图像中障碍物的轮廓更加清晰，以便于提高路径规划的精确度，在全局路径规划的基础上，依次对子路径进行处理，进一步地提高路径规划的精确度，提高机器人的工作效率。In the embodiment of the present invention, by processing the image, the outline of obstacles in the image is clearer, so as to improve the accuracy of path planning. Accuracy, improve the work efficiency of the robot.

附图说明Description of drawings

图1是本发明实施例一提供的路径优化方法的实现流程图；以及FIG. 1 is an implementation flowchart of a path optimization method provided in Embodiment 1 of the present invention; and

图2是本发明实施例二提供的路径优化系统的结构示意图；FIG. 2 is a schematic structural diagram of a path optimization system provided by Embodiment 2 of the present invention;

具体实施方式detailed description

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。In order to make the object, technical solution and advantages of the present invention clearer, the present invention will be further described in detail below in conjunction with the accompanying drawings and embodiments. It should be understood that the specific embodiments described here are only used to explain the present invention, not to limit the present invention.

以下结合具体实施例对本发明的具体实现进行详细描述：The specific realization of the present invention is described in detail below in conjunction with specific embodiment:

实施例一：Embodiment one:

图1示出了本发明实施例一提供的路径优化方法的实现流程图，为了便于说明，仅示出了与本发明实施例相关的部分，详述如下：Fig. 1 shows the implementation flow chart of the path optimization method provided by Embodiment 1 of the present invention. For the convenience of description, only the parts related to the embodiment of the present invention are shown, and the details are as follows:

在步骤S101中，利用多项式变换对图像进行校正后，对图像中障碍物的边缘进行检测。In step S101, after the image is corrected by polynomial transformation, the edge of the obstacle in the image is detected.

在本发明实施例中，图像在生成、传输、处理、发送和接收等过程时，不可避免的会受到各种噪声的干扰和影响，比如在大气环境中，由于光线在空气中会产生散射和吸收，使得图像的有些地方可能产生灰白效应，导致图像的对比度下降严重，有时甚至会影响图像的视觉效果而无法进行下一步处理。因此，首先对空中机器人采集的图像进行预处理，优选地，可以采用的去噪方法是中值滤波法和形态学去噪。对去噪后的图像进行校正，利用坐标间的多项式变换来近似表示这种非线性的畸变，并选取一些控制点来消除畸变。In the embodiment of the present invention, images will inevitably be disturbed and affected by various noises during the process of generation, transmission, processing, sending and receiving. For example, in an atmospheric environment, due to light scattering and Absorption may cause some parts of the image to have a gray effect, resulting in a serious decrease in the contrast of the image, and sometimes even affect the visual effect of the image and cannot be processed in the next step. Therefore, firstly, the image collected by the aerial robot is preprocessed. Preferably, the denoising methods that can be used are median filtering and morphological denoising. Correct the image after denoising, use the polynomial transformation between coordinates to approximate the nonlinear distortion, and select some control points to eliminate the distortion.

具体地，对于图像上的点(x,y)，利用多项式变换得到校正后的点(f,g)，式1如下：Specifically, for a point (x, y) on the image, use polynomial transformation to obtain the corrected point (f, g), Equation 1 is as follows:

$\{\begin{matrix} x x = = {Σ Σ}_{i i = = 00}^{n no} {Σ Σ}_{j j = = 00}^{n no - - i i} {a a}_{i i j j} {f f}^{i i} {g g}^{j j} \\ y the y = = {Σ Σ}_{i i = = 00}^{n no} {Σ Σ}_{j j = = 00}^{n no - - i i} {b b}_{i i j j} {f f}^{i i} {g g}^{j j} \end{matrix}$

其中，a_ij，b_ij为多项式的系数，n为次数，利用已知的控制点进行求解。Among them, a _ij and b _ij are the coefficients of the polynomial, n is the degree, and the known control points are used to solve the problem.

如果控制点数目与方程组中未知数的数目相同，则可以直接求解方程组；而在一般的图像畸变校正处理中，为了获得较高的校正准确度，控制点数目会多于方程组中未知数的数目，通过求误差平方和最小准则下的最优近似解，具体做法如下：If the number of control points is the same as the number of unknowns in the equations, the equations can be solved directly; while in general image distortion correction processing, in order to obtain higher correction accuracy, the number of control points will be more than the number of unknowns in the equations Number, by seeking the optimal approximate solution under the minimum criterion of the sum of squared errors, the specific method is as follows:

对L个控制点，用多项式拟合后的误差平方和最小，即：For L control points, the sum of squared errors after polynomial fitting is the smallest, namely:

$ϵ ϵ = = {Σ Σ}_{l l = = 11}^{L L} {[[x x - - {Σ Σ}_{i i = = 00}^{n no} {Σ Σ}_{j j = = 00}^{n no - - i i} {a a}_{i i j j} {f f}_{l l}^{i i} {g g}_{l l}^{j j}]]}^{22} = = min min$

则有：Then there are:

$\frac{\partial \partial ϵ ϵ}{\partial \partial {a a}_{s the s t t}} = = 22 {Σ Σ}_{l l = = 11}^{L L} (({Σ Σ}_{i i = = 00}^{n no} {Σ Σ}_{j j = = 00}^{n no - - i i} {a a}_{i i j j} {f f}_{l l}^{i i} {g g}_{l l}^{j j} - - {x x}_{l l})) {f f}_{l l}^{s the s} {g g}_{l l}^{t t} = = 00$

可以得到，式2：It can be obtained, formula 2:

${Σ Σ}_{l l = = 11}^{L L} (({Σ Σ}_{i i = = 00}^{n no} {Σ Σ}_{j j = = 00}^{n no - - i i} {a a}_{i i j j} {f f}_{l l}^{i i} {g g}_{l l}^{j j})) {f f}_{l l}^{i i} {g g}_{l l}^{j j} = = {Σ Σ}_{i i = = 00}^{n no} {Σ Σ}_{j j = = 00}^{n no - - i i} {a a}_{i i j j} (({Σ Σ}_{l l = = 11}^{L L} {f f}_{l l}^{i i + + s the s} {g g}_{l l}^{j j + + t t})) = = {Σ Σ}_{l l = = 11}^{L L} {x x}_{l l} {f f}_{l l}^{s the s} {g g}_{l l}^{t t}$

同理有，式3：Similarly, formula 3:

${Σ Σ}_{l l = = 11}^{L L} (({Σ Σ}_{i i = = 00}^{n no} {Σ Σ}_{j j = = 00}^{n no - - i i} {b b}_{i i j j} {f f}_{l l}^{i i} {g g}_{l l}^{j j})) {f f}_{l l}^{i i} {g g}_{l l}^{j j} = = {Σ Σ}_{i i = = 00}^{n no} {Σ Σ}_{j j = = 00}^{n no - - i i} {b b}_{i i j j} (({Σ Σ}_{l l = = 11}^{L L} {f f}_{l l}^{i i + + s the s} {g g}_{l l}^{j j + + t t})) = = {Σ Σ}_{l l = = 11}^{L L} {y the y}_{l l} {f f}_{l l}^{s the s} {g g}_{l l}^{t t}$

上述式子中L为控制点的个数，s＝0,1,2,…,n；t＝0,1,2,…,n-s；s+t≤n。In the above formula, L is the number of control points, s=0,1,2,...,n; t=0,1,2,...,n-s; s+t≤n.

在式2和式3中都包含(n+1)(n+2)/2，则可组成线性方程组，解出a_ij以及b_ij，带入式1便可求出校正后的点(f,g)。Both formula 2 and formula 3 contain (n+1)(n+2)/2, then a system of linear equations can be formed, and a _ij and b _ij can be solved, and put into formula 1 to obtain the corrected point ( f, g).

校正准确度与所用校正多项式次数n有关，多项式次数越高，拟合误差越小，但是随着n增加，系数数目增加，导致计算量急剧增加，对一般的非线性失真，通常采用三次多项式进行拟合，方法比较简单有效，且准确度较高，此时式1可写为：The correction accuracy is related to the degree n of the correction polynomial used. The higher the polynomial degree, the smaller the fitting error, but as n increases, the number of coefficients increases, resulting in a sharp increase in the amount of calculation. For general nonlinear distortion, cubic polynomials are usually used. Fitting, the method is relatively simple and effective, and the accuracy is high. At this time, formula 1 can be written as:

$\{\begin{matrix} x x = = {a a}_{0000} + + {a a}_{0101} f f + + {a a}_{0202} {f f}^{22} + + {a a}_{0303} {f f}^{33} + + {a a}_{1010} g g + + {a a}_{1111} f f g g + + \\ {a a}_{1212} {f f}^{22} g g + + {a a}_{2020} {g g}^{22} + + {a a}_{21 twenty one} {fg fg}^{22} + + {a a}_{3030} {g g}^{33} \\ y the y = = {b b}_{0000} + + {b b}_{0101} f f + + {b b}_{0202} {f f}^{22} + + {b b}_{0303} {f f}^{33} + + {b b}_{1010} g g + + {b b}_{1111} f f g g + + \\ {b b}_{1212} {f f}^{22} g g + + {b b}_{2020} {g g}^{22} + + {b b}_{21 twenty one} {fg fg}^{22} + + {b b}_{3030} {g g}^{33} \end{matrix}$

进一步地，对图像中障碍物的边缘进行检测包括：Further, detecting the edge of the obstacle in the image includes:

利用中值滤波法对所述图形进行去噪处理，除去所述图像中的噪声以及保留边缘信息；performing denoising processing on the graphics by using a median filtering method, removing noise in the image and retaining edge information;

对所述图像中每个像素点计算梯度值，分别对x方向和y方向做卷积运算，公式如下：The gradient value is calculated for each pixel in the image, and the convolution operation is performed on the x direction and the y direction respectively, and the formula is as follows:

${F f}_{x x} = = (\begin{matrix} - - 11 & 11 \\ - - 11 & 11 \end{matrix}) {F f}_{y the y} = = (\begin{matrix} - - 11 & 11 \\ - - 11 & 11 \end{matrix})$

可以计算得到： Can be calculated to get:

对所述梯度值进行非极大抑制；performing non-maximum suppression on the gradient value;

根据高阈值以及低阈值进行边缘检测，并对边缘进行连接，所述高阈值设定为所述低阈值的三倍。Edge detection is performed according to a high threshold and a low threshold, and edges are connected, and the high threshold is set to be three times the low threshold.

在步骤S102中，对障碍物的顶点进行标记，并通过选取障碍物的顶点形成第一路径。In step S102, the vertices of the obstacles are marked, and the first path is formed by selecting the vertices of the obstacles.

在本发明实施例中，将图像中的障碍物标记为G_n以及障碍物的顶点标记为M_mun，其中，G_n表示障碍物的编号，依次标记为：G₀,G₁,G₂…G_n，M_mun表示障碍物中顶点的编号；根据所确定的起点以及终点，获取从起点到终点的所有路径，路径由障碍物的顶点组成；从路径中选取第一路径，路径被选中的概率为：In the embodiment of the present invention, the obstacles in the image are marked as G _n and the vertices of the obstacles are marked as M _mun , where G _n represents the number of the obstacle, which are marked as: G ₀ , G ₁ , G ₂ ... G _n , M _mun represent the number of vertices in the obstacle; according to the determined starting point and end point, obtain all paths from the starting point to the end point, the path is composed of the vertices of the obstacle; select the first path from the path, the path is selected The probability is:

${p p}_{i i} = = \frac{{f f}_{i i}}{{Σ Σ}_{j j = = 11}^{N N} {f f}_{j j}}$

其中，p_i表示路径i被选中的概率，f_i表示路径i的自适应度，N表示所有路径的总数。Among them, p _i represents the probability that path _i is selected, fi represents the adaptability of path i, and N represents the total number of all paths.

将路径作为种群，路径作为个体，路径中从起点到终点经过的每个顶点作为基因，从种群中选择出优良的个体，并淘汰掉不良的基因，从路径中选取第一路径的目的是把性能好的个体直接遗传给下一代。种群中个体被选中的概率与其适应度的大小成正比，若种群的大小为N，其中一个个体i的适应度为f_i，适应度函数是取一个较大的值S_max减去路径长度S，路径长度S越大，适应度f越小；路径长度S越小，适应度f越大，根据适应度函数，适应度越小(路径越长)的个体被淘汰的概率越大，适应度越大(路径越短)的个体被淘汰的概率越小。用公式表示如下：Take the path as a population, the path as an individual, and each vertex in the path from the starting point to the end point as a gene, select good individuals from the population, and eliminate bad genes. The purpose of selecting the first path from the path is to Individuals with good performance are directly passed on to the next generation. The probability of an individual being selected in the population is proportional to its fitness. If the size of the population is N, the fitness of an individual i is f _i , and the fitness function is to take a larger value S _max minus the path length S , the greater the path length S, the smaller the fitness f; the smaller the path length S, the greater the fitness f, according to the fitness function, the smaller the fitness (the longer the path), the greater the probability of being eliminated, and the fitness The larger (shorter the path) individuals are less likely to be eliminated. The formula is as follows:

f＝S_max-Sf=S _max -S

其中的S表示的从起始点到当前个体之间经过的路径总长，而S_max则远大于S。从上述公式可见，当前点的到起始点之间的路径越短，适应度越大，选中进入下一代的概率与适应度成正比。Among them, S represents the total length of the path from the starting point to the current individual, and S _max is much larger than S. It can be seen from the above formula that the shorter the path from the current point to the starting point, the greater the fitness, and the probability of being selected to enter the next generation is proportional to the fitness.

在步骤S103中，对第一路径依次通过交叉以及变异操作，形成第二路径。In step S103, a second path is formed by performing crossover and mutation operations on the first path in sequence.

在本发明实施例中，交叉操作是将种群中的两个父代个体的部分基因进行重组，生成新两个新的个体，在进行个体选择时是选取一个较小的概率p_a，再随机选取一个概率数p_b，当p_b>p_a时，则被选中进入交叉池中，等待进行交叉操作，例如：可以选择p_a＝0.2，而p_b在(0,1)中随机选择一个数，这样选择的数大于0.2的概率就会比较大，可以保证大多数的个体都进行了交叉操作，进行交叉的个体越多，种群中基因的多样性就越大，越能够产生优良的基因。In the embodiment of the present invention, the crossover operation is to recombine part of the genes of the two parent individuals in the population to generate two new individuals. When selecting individuals, a small probability p _a is selected, and then randomly Select a probability number p _b , when p _b >p _a , it will be selected to enter the crossover pool, waiting for the crossover operation, for example: you can choose p _a =0.2, and p _b randomly selects one in (0,1) In this way, the probability that the selected number is greater than 0.2 will be relatively high, which can ensure that most individuals have carried out the crossover operation. The more individuals who perform crossover, the greater the diversity of genes in the population, and the better the genes can be produced. .

变异操作是指通过随机改变个体中的某些基因来改变个体的特性，从而形成新的个体，虽然变异的个体并一定是优良基因，但这对增加种群的多样性有非常重要的作用，因为产生优良的个体的概率较小，所以这里选取的一个较小的概率对其进行变异。例如选取一个固定的概率p_c＝0.8，再随机选取(0,1)中的数p_d，当p_d>p_c时，则当前选取的个体进行变异，这样种群中发生变异的个体相对较少，这样能够既保证不产生很多不良个体，又能够保证种群的多样性。The mutation operation refers to changing the characteristics of the individual by randomly changing some genes in the individual to form a new individual. Although the mutated individual is not necessarily a good gene, it plays a very important role in increasing the diversity of the population, because The probability of producing an excellent individual is small, so a small probability is selected here to mutate it. For example, select a fixed probability p _c = 0.8, and then randomly select the number p _d in (0,1). When p _d > p _c , the currently selected individual will mutate, so that the mutated individuals in the population are relatively small This can not only ensure that many bad individuals will not be produced, but also ensure the diversity of the population.

在步骤S104中，按照预设顶点数量，在第二路径中选取子路径，并判断子路径中的起点与终点之间能否直达，以确定优化路径。In step S104, according to the preset number of vertices, a sub-path is selected in the second path, and it is judged whether the start point and the end point in the sub-path are directly accessible, so as to determine an optimal path.

在本发明实施例中，计算所述图像中每个障碍物顶点的地势值；将所述第二路径从起点开始，按照预设顶点数量，依次选取子路径；计算所述子路径的长度，以及选出地势值介于子路径的起点的地势值以及终点的地势值之间的顶点的集合。In the embodiment of the present invention, the terrain value of each obstacle vertex in the image is calculated; the second path starts from the starting point, and the sub-paths are sequentially selected according to the preset number of vertices; the length of the sub-path is calculated, And select a set of vertices whose terrain value is between the terrain value of the starting point and the terrain value of the end point of the sub-path.

若所述子路径中的起点与终点之间能直达，则将起点和终点连接的直线路径确定为优化路径；若所述子路径中的起点与终点之间不能直达，则在所述顶点的集合中查找是否存在1个或2个顶点，使得经过所述1个或2个顶点的路径长度小于所述子路径的长度，若存在所述1个或2个顶点，则将经过所述1个或2个顶点的路径。If there is direct access between the starting point and the end point in the sub-path, then the straight line path connecting the starting point and the end point is determined as an optimized path; Find whether there are 1 or 2 vertices in the set, so that the length of the path passing through the 1 or 2 vertices is less than the length of the sub-path, if there are 1 or 2 vertices, it will pass through the 1 A path with 1 or 2 vertices.

实施例二：Embodiment two:

图2示出了本发明实施例二提供的路径优化系统的结构示意图，为了便于说明，仅示出了与本发明实施例相关的部分。该路径优化系统包括：图像处理单元21、第一路径形成单元22、第二路径形成单元23以及路径优化单元24，其中：FIG. 2 shows a schematic structural diagram of a path optimization system provided by Embodiment 2 of the present invention. For ease of description, only parts related to the embodiment of the present invention are shown. The route optimization system includes: an image processing unit 21, a first route forming unit 22, a second route forming unit 23 and a route optimizing unit 24, wherein:

图像处理单元21，用于利用多项式变换对图像进行校正后，对图像中障碍物的边缘进行检测。The image processing unit 21 is configured to use polynomial transformation to correct the image, and then detect the edge of the obstacle in the image.

具体地，图像处理单元21包括：图像校正单元以及边缘检测单元，其中：Specifically, the image processing unit 21 includes: an image correction unit and an edge detection unit, wherein:

图像校正单元，用于对于所述图像上的点(x,y)，利用多项式变换得到校正后的点(f,g)。The image correction unit is configured to use polynomial transformation to obtain corrected points (f, g) for the points (x, y) on the image.

边缘检测单元，具体用于：An edge detection unit, specifically for:

对所述图像中每个像素点计算梯度值，分别对x方向和y方向做卷积运算；Calculate the gradient value for each pixel in the image, and perform convolution operations on the x direction and the y direction respectively;

第一路径形成单元22，用于对障碍物的顶点进行标记，并通过选取障碍物的顶点形成第一路径。The first path forming unit 22 is configured to mark the vertices of the obstacles, and form the first path by selecting the vertices of the obstacles.

第一路径形成单元包括：The first path forming unit includes:

标记单元，用于将所述图像中的障碍物标记为G_n以及所述障碍物的顶点标记为M_mun，其中，G_n表示所述障碍物的编号，依次标记为：G₀,G₁,G₂…G_n，M_mun表示所述障碍物中顶点的编号；A marking unit, configured to mark the obstacle in the image as G _n and the vertex of the obstacle as M _mun , where G _n represents the number of the obstacle, which are marked as: G ₀ , G ₁ in turn ,G ₂ ...G _n , M _mun represents the number of vertices in the obstacle;

路径形成单元，用于根据所确定的起点以及终点，获取从起点到终点的所有路径，所述路径由所述障碍物的顶点组成；a path forming unit, configured to obtain all paths from the starting point to the ending point according to the determined starting point and the ending point, the paths are composed of vertices of the obstacles;

第一路径形成子单元，用于从所述路径中选取第一路径。The first path forms a subunit for selecting the first path from the paths.

${p p}_{i i} = = \frac{{f f}_{i i}}{{Σ Σ}_{j j = = 11}^{N N} {f f}_{j j}}$

f＝S_max-Sf=S _max -S

第二路径形成单元23，用于对第一路径依次通过交叉以及变异操作，形成第二路径。The second path forming unit 23 is configured to sequentially perform crossover and mutation operations on the first path to form a second path.

路径优化单元24，用于按照预设顶点数量，在第二路径中选取子路径，并判断子路径中的起点与终点之间能否直达，以确定优化路径。The path optimization unit 24 is configured to select a sub-path in the second path according to the preset number of vertices, and determine whether the start point and the end point in the sub-path are directly accessible, so as to determine the optimized path.

在本发明实施例中，各单元可由相应的硬件或软件单元实现，各单元可以为独立的软、硬件单元，也可以集成为一个软、硬件单元，在此不用以限制本发明。In the embodiment of the present invention, each unit can be realized by corresponding hardware or software unit, and each unit can be an independent software and hardware unit, or can be integrated into one software and hardware unit, which is not used to limit the present invention.

以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。The above descriptions are only preferred embodiments of the present invention, and are not intended to limit the present invention. Any modifications, equivalent replacements and improvements made within the spirit and principles of the present invention should be included in the protection of the present invention. within range.

Claims

1. a paths planning method, it is characterised in that described method comprises the steps:

After utilizing polynomial transformation to correct image, the edge of barrier in image is detected；

The summit of described barrier is marked, and forms first path by choosing the summit of described barrier；

Described first path is passed sequentially through intersection and mutation operation, forms the second path；

According to default summit quantity, described second path is chosen subpath, and judges the starting point in described subpath and end Can go directly between point, to determine path optimizing.

2. the method for claim 1, it is characterised in that described utilize the polynomial transformation step to correct image Suddenly, including:

For on described image point (x, y), point after utilizing polynomial transformation to be corrected (f, g), calculating formula is as follows:

\{\begin{matrix} x = Σ_{i = 0}^{n} Σ_{j = 0}^{n - i} α_{i j} f^{i} g^{j} \\ y = Σ_{i = 0}^{n} Σ_{j = 0}^{n - i} b_{i j} f^{i} g^{j} \end{matrix}

Wherein, a_ij, b_ijFor polynomial coefficient, n is number of times, utilizes known control point to solve.

3. the method for claim 1, it is characterised in that the described step that the edge of barrier in image is detected Suddenly, including:

Utilize median filtering method that described figure is carried out denoising, remove the noise in described image and retain edge letter Breath；

Each pixel in described image being calculated Grad, respectively x direction and y direction is done convolution algorithm, formula is as follows:

F_{x} = (\begin{matrix} - 1 & 1 \\ - 1 & 1 \end{matrix}) F_{y} = (\begin{matrix} - 1 & 1 \\ - 1 & 1 \end{matrix})

Can be calculated:

Described Grad is carried out non-maximum restraining；

Carrying out rim detection according to high threshold and Low threshold, and be attached edge, described high threshold is set as described low Three times of threshold value.

4. the method for claim 1, it is characterised in that the described summit to described barrier is marked, and passes through The summit choosing described barrier forms the step of first path, including:

It is G by the obstacle tag in described image_nAnd the apex marker of described barrier is M_mun, wherein, G_nRepresent described The numbering of barrier, is labeled as successively: G₀,G₁,G₂…G_n, M_munRepresent the numbering on summit in described barrier；

Starting point determined by according to and terminal, obtain from all paths of origin-to-destination, and described path is by described barrier Summit composition；

Choosing first path from described path, the selected probability in described path is:

p_{i} = \frac{f_{i}}{Σ_{j = 1}^{N} f_{j}}

Wherein, p_iRepresent the selected probability of path i, f_iRepresenting the adaptive response of path i, N represents the sum in all paths.

5. the method for claim 1, it is characterised in that described according to default summit quantity, in described second path Choose subpath, by judging that can described subpath go directly, to determine the step of path optimizing, including:

Calculate the physical features value on each barrier summit in described image；

By described second path from the off, according to default summit quantity, subpath is chosen successively；

Calculate the length of described subpath, and select physical features value between the physical features value of the starting point of subpath and the physical features of terminal The set on the summit between value.

6. method as claimed in claim 5, it is characterised in that described according to default summit quantity, in described second path Choose subpath, and judge can go directly between the Origin And Destination in described subpath, to determine the step of path optimizing, also Including:

If can go directly between the Origin And Destination in described subpath, then the straight line path that beginning and end connects is defined as excellent Change path；

If can not go directly between the Origin And Destination in described subpath, then search whether to have 1 in the set on described summit Individual or 2 summits so that the path through described 1 or 2 summit is less than the length of described subpath, if existing described 1 or 2 summits, then by the path through described 1 or 2 summit.

7. a path optimizing system, it is characterised in that described system includes:

Graphics processing unit, after being used for utilizing polynomial transformation to correct image, is carried out the edge of barrier in image Detection；

First path forms unit, for being marked the summit of described barrier, and by choosing the top of described barrier Point forms first path；

Second path forms unit, for described first path passes sequentially through intersection and mutation operation, forms the second path； And

Path optimization's unit, for according to default summit quantity, chooses subpath in described second path, and judges described son Can go directly between Origin And Destination in path, to determine path optimizing.

8. system as claimed in claim 7, it is characterised in that described graphics processing unit includes:

Image correction unit, for on described image point (x, y), point after utilizing polynomial transformation to be corrected (f, g)。

9. system as claimed in claim 7, it is characterised in that described graphics processing unit also includes edge detection unit, tool Body is used for:

Each pixel in described image is calculated Grad, respectively convolution algorithm is done in x direction and y direction；

Described Grad is carried out non-maximum restraining；

10. system as claimed in claim 7, it is characterised in that described first path forms unit and includes:

Indexing unit, being used for the obstacle tag in described image is G_nAnd the apex marker of described barrier is M_mun, its In, G_nRepresent the numbering of described barrier, be labeled as successively: G₀,G₁,G₂…G_n, M_munRepresent the volume on summit in described barrier Number；

Path forms unit, for starting point and terminal determined by basis, obtains from all paths of origin-to-destination, described Path is made up of the summit of described barrier；

First path forms subelement, for choosing first path from described path.