DeepRail: Automatic Visual Detection System for Railway Surface Defect Using Bayesian CNN and Attention Network
-
摘要: 面向复杂多样的钢轨场景, 本文扩展了最先进的深度学习语义分割框架DeepLab v3+ 到一个新的轻量级、可伸缩性的贝叶斯版本DeeperLab, 实现表面缺陷的概率分割. 具体地, Dropout被融入改进的Xception网络, 使得从后验分布中生成蒙特卡罗样本; 其次, 提出多尺度多速率的空洞空间金字塔池化(Atrous spatial pyramid pooling, ASPP)模块, 提取任意分辨率下的密集特征图谱; 更简单有效的解码器细化目标的边界, 计算Softmax概率的均值和方差作为分割预测和不确定性. 为解决类别不平衡问题, 基于在线前景 − 背景挖掘思想, 提出损失注意力网络(Loss attention network, LAN)定位缺陷以计算惩罚系数, 从而补偿和抑制DeeperLab的前景与背景损失, 实现辅助监督训练. 实验结果表明本文算法具有91.46 %分割精度和0.18 s/帧的运行速度, 相比其他方法更加快速鲁棒.Abstract: This paper extends the state-of-the-art deep learning framework DeepLab v3+ to a light-weighted and scalable Bayesian version DeeperLab for the defect detection on complex and diverse rail surface. Specifically, Dropout is incorporated into the improved Xception network for Monte Carlo sampling from posterior distribution. Atrous spatial pyramid pooling (ASPP) module is utilized to extract the dense features at multiple scales and rates. Furthermore, a simpler and efficient decoder is proposed to improve the defect edges, and outputs the mean and variance of Softmax probability as segmentation and uncertainty. To solve class imbalance problem, we present the loss attention network (LAN) to perform auxiliary supervision for DeeperLab training. Experimental results show that the proposed algorithm is more accurate and robust than other methods with 91.46 % precision and 0.18 s/frame speed.
-
自多智能体系统理论提出以来, 其协调控制方面[1]的研究受到了国际学术界的广泛关注, 相关研究内容仅涉及多智能体系统一致性控制[2-3]或编队控制协议[4-5]、智能体动力学模型[6-7]和控制律设计[8-10], 而多智能体通信网络拓扑结构的连通性[11-12]研究未见有文献报道.通信网络拓扑结构的连通性是多智能体系统一致性控制与编队控制等的理论前提.网络连通性高效判定算法不仅是大规模多智能体系统一致性控制或编队控制的保证, 而且在图论[13-15]、现代移动通信[16-17]、计算机与交通[18]等各种网络中有着重要和广泛的应用.
在多智能体系统一致性控制或编队控制中, 如果两个智能体在规定的时间(通常为一个采样周期)内至少有一次数据交换, 则认为这两个智能体在通信方面是连通的.如此, 进行数据交换的多个智能体构成了一个移动通信网络.若所有智能体构成的这个移动通信网络在规定的时间内是连通的, 则称该网络的拓扑结构是连通的.这种多智能体通信网络常被建模为复杂无向网络(含自环和多重边), 而其拓扑结构的连通性检测和判定问题就可转化为复杂无向网络的连通性检测和判定问题.
迄今为止, 判定网络连通性的算法主要有两类:基于深度优先搜索技术的算法, 如Tarjan算法[19]和Gabow算法[20]等; 基于可达矩阵的算法和基于关系传递闭包的Warshall算法[21]等. Tarjan算法和Gabow算法是一类面向网络的直接搜索算法, 其优点是算法复杂度低(均为O$(n+m)$, 其中$n$为节点数, $m$为边数), 缺点是仅适合简单网络(无自环或多重边)且不易编程(需使用堆栈和标号技术). Warshall算法的优点是结构异常简洁且可采用效率更高的位运算方法, 缺点是算法复杂度高(O$(2n^3)$)且同样仅适用于简单网络.基于可达矩阵的连通性判定算法虽可用于复杂无向网络, 但由于其算法复杂度太高(O$(n^4)$)而很难适用于大规模移动通信网络或计算机互联网络的连通性判定.
针对具有$n$个节点的复杂无向网络, 本文给出了一种新的连通性判定算法, 该算法的时间复杂度和空间复杂度分别为O$(3n^2)$和O$(n^2+n)$.与基于可达矩阵的连通性判定算法和基于关系传递闭包的Warshall算法相比, 本文所给算法在时间复杂度上具有显著优势, 因而更适合大规模移动通信网络或计算机互联网络的连通性检测与判定.
1. 问题描述
给定一个无向网络$G$, 我们用$v_i\; (i = 1, 2, \cdots)$与$e_j\; (j=1, 2, \cdots)$分别表示$G$中的节点和边, 用$V(G) = \{v_1, v_2, \cdots\}$与$E(G) = \{e_1, e_2, \cdots\}$分别表示$G$中所有节点和所有边的集合, 则网络$G$可用一个偶对$(V, E)$表示, 记作$G = (V, E)$.
若用$n = |V(G)|$表示$V(G)$中节点的个数, $m = |E(G)|$表示$E(G)$中边的个数, 则网络$G$可另记为$G = (n, m)$. $n$称为网络$G$的阶数, 一个具有$n$个节点的网络称为$n$阶网络. $n$和$m$均为有限值的无向网络$G$称为有限无向网络.
除特别声明外, 本文所讨论的网络均指有限复杂无向网络, 原因在于大规模移动通信网络和计算机互联网络常被建模为复杂无向网络, 且复杂无向网络较简单无向网络具有更大的普适性.
定义1. 给定$n$阶无向网络$G$和网络的节点集$V(G) = \{v_1, v_2, \cdots, v_n\}$, 称$\overline{A} = \overline{A}(\overline{a_{ij}}) \in {\bf R}^{n \times n}$为$G$的邻接矩阵, 其中
$$ \begin{equation} { \overline{a_{ij}}} = \left\{ \begin{array}{ll} m_{ij}, & v_i~\text{与}~v_j~\text{之间有}~m_{ij}~\text{条边邻接} \\ 0, & v_i~\text{与}~v_j~\text{不邻接} \\ \end{array} \right. \end{equation} $$ 定义1中, $m_{ij} \geq 1$为整数.当$G$为简单无向网络时, $m_{ij} = 1$; 当$G$为复杂无向网络时, 则至少存在一个$m_{ij} > 1$.因本文仅考虑$G$的连通性, 所以将$m_{ij}$视为1并不影响$G$的连通性.
定义2. 给定$n$阶无向网络$G$和网络的节点集$V(G) = \{v_1, v_2, \cdots, v_n\}$, 设
$$ \begin{equation} { a_{ij}} = \left\{ \begin{array}{ll} 1, & \text{若}~v_i~\text{与}~v_j~\text{邻接}, \text{或}~i = j \\ 0, & \text{若~}v_i~\text{与}~v_j~\text{不邻接} \\ \end{array} \right. \end{equation} $$ (2) 则称: 1)由元素$a_{ij}\; (i, j = 1, 2, \cdots, n)$构成的$n$阶矩阵为网络$G$的邻居矩阵, 记作$A(G)$, 或简记为$A$; 2) $A$的第$i$行为网络$G$的第$i$个邻居集, 记作$A_i(G)$, 或简记为$A_i$.
我们以图 1和图 2所示无向网络为例来具体说明定义2中所涉及的概念.
图 1和图 2所示的无向网络各有8个节点, 它们的邻居矩阵分别是
$$ A(G1)=\begin{bmatrix} 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \end{bmatrix} $$ $$ A(G2)=\begin{bmatrix} 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \end{bmatrix} $$ 邻居集$A_i(Gj)\; (i = 1, 2, \cdots, n; j = 1, 2) $表示节点$v_i$与其邻接节点的关系, 其中取值为1的元素所对应的节点就是包含$v_i$在内的一个邻居组, 如$A_1(G1)$中包含$v_1$在内的邻居组是$\{v_1, v_2, v_3\}$.我们用$|A_i|$表示$A_i$中取值为1的元素个数、即邻居集$A_i$中邻居的个数, 如$|A_1(G1)| = 3$.显然, 每个邻居组中的节点及与它们相邻接的边一起构成网络$G$的一个连通子网络.此外, 我们称元素全为0的邻居集为零邻居集(对应空网络), 元素全为1的邻居集为全邻居集(对应连通网络).
给定一个无向网络, 由定义2和图论中邻接矩阵的定义可知, 复杂无向网络邻居矩阵与简单无向网络邻接矩阵的差别仅是对角线元素的取值有所不同, 邻居矩阵的对角线元素全为1, 而邻接矩阵的对角线元素全为0.
2. 算法理论基础与算法设计
2.1 算法理论基础
由定义2可知, $n\; (n \geq 2)$阶无向网络$G$的邻居集$A_i(G)$具有如下特点: 1)邻居集中只有2种元素1和0, 且至少有一个1; 2)各邻居集中元素的个数彼此相等; 3)每个邻居集对应一个邻居组, 每个邻居组彼此邻接且对应网络$G$的一个连通子网络.
定义2是一个新定义, 也是本文所给算法的基础.在具体给出基于邻居矩阵的网络连通性判定算法(下面简称本文所给算法)之前, 我们需先给出邻居集的相关运算规则.
定义3. 给定$n\; (n \geq 2)$阶无向网络$G$及相应的邻居集$A_i\; (i = 1, 2, \cdots, n)$, 邻居集的交与并的运算规则如下:
1) $A_i \cap A_j = \{z_k = x_k \cap y_k|x_k \in A_i, y_k \in A_j, k = 1, 2, \cdots, n\}$;
2) $A_i \cup A_j = \{z_k = x_k \cup y_k|x_k \in A_i, y_k \in A_j, k = 1, 2, \cdots, n\}$.
上式中各元素之间的运算($\cap$和$\cup$)均为布尔运算, 可采用效率更高的位运算方法实现.上述运算规则用于邻居集时具有明确意义:
1) 若两邻居集$A_i$、$A_j\; (i \neq j)$的交集$A_i \cap A_j$为零邻居集, 则由$A_i$、$A_j$决定的两个邻居组没有公共邻居, 反之则有公共邻居;
2) 没有公共邻居的两个邻居集的并集不构成新的邻居组, 即不构成$G$的新的连通子网络;
3) 有公共邻居的两个邻居集的并集$A_i \cup A_j$是一个新的邻居集, 该邻居集对应$G$的一个新的连通子网络; 新连通子网络是$A_i$、$A_j$所对应的连通子网络的并, 且显然有$|A_i \cup A_j| \geq \max(|A_i, A_j|)$.
本文所给算法主要涉及2种运算: 1)求两个邻居集$A_i$、$A_j\; (i \neq j)$的交集, 以验证它们是否有公共邻居, 若无则不求$A_i \cup A_j$; 2)若有公共邻居, 则求$A_i \cup A_j$.
两个邻居集$A_i$、$A_j\; (i \neq j)$的交并运算可按如下简便方法一次完成:
1) 求$A_i \cap A_j$, 对于$k= 1, 2, \cdots, n$, 依次检查$x_k \cap y_k$的取值, 当首次出现$x_k \cap y_k = 1$时, 停止本次求交运算;
2) 求$A_i \cup A_j = \{z_k = x_k \cup y_k|x_k \in A_i, y_k \in A_j, k = 1, 2, \cdots, n\}$.
本文所给算法的主要思路是: 1)给定$n\; (n \geq 2)$阶无向网络, 生成邻居矩阵$A(a_{ij}) \in {\bf R}^{n \times n}$和相应的邻居集$A_i\; (i = 1, 2, \cdots, n)$; 2)求$A_1 \cap A_i\; (i = 2, 3, \cdots, n)$以确定两个邻居集之间是否具有公共邻居; 若无, 令$i = i + 1$, 继续进行求交运算; 若有, 求$A_1 \cup A_i$并将运算结果赋予$A_1$; 上述求并与赋值运算结束后, 令$i = i + 1$, 继续进行这种求交和求并运算; 3)若上述运算进行到最后一步后, $|A_1| < $ $n$或$A_1$与所有剩余的邻居集之间没有相同的邻居, 则可判定所给网络不连通, 否则, 可判定所给网络连通.
2.2 算法设计
给定$n\; (n \geq 2)$阶无向网络$G$, 设: $G$的邻居矩阵$A(a_{ij})\in$ ${\bf R}^{n \times n}$和相应的邻居集$A_i\; (i = 1, 2, \cdots, n)$已经生成; $i$为$A(a_{ij})$的行循环变量, $j$与$k$为$A(a_{ij})$的列循环变量($i, j, k = 1, 2, \cdots, n$); $H=\{h_1$, $h_2$, $\cdots$, $h_n\}$为标号集, $h_i = 1$表示$A_1$与$A_i$进行过求并运算, $h_i = 0$表示$A_1$与$A_i$未进行过求并运算.下面我们具体给出复杂无向网络$G$的连通性判定算法.
基于邻居矩阵的复杂无向网络连通性判定算法
1) 赋初值: $i=j=k=0$, $H=\{h_i=0|i=1$, 2, $\cdots$, $n$};
2) $j=j+1$;
3) 如果$a_{1j}=0$且$j < n$, 转到2);如果$a_{1j}=$ $0$且$j=n$, 转到13);如果$a_{1j}=1$, $i=1$, 转到4);
4) $i=i+1$;
5) 如果$h_i=1$且$i < n$, 转到4);如果$h_i=1$且$i = n$, 转到11);如果$h_i=0$, 转到6);
6) 如果$a_{ij}=0$且$i < n$, 转到4);如果$a_{ij} = 0$且$i=n$, 转到11);如果$a_{ij}=1$, $k=1$, 转到7);
7) $k=k + 1$;
8) 如果$a_{ik}=0$且$k < n$, 转到7);如果$a_{ik} = 0$且$k=n$, 转到10);如果$a_{ik}=1$, $a_{1k} =:$ $a_{ik}$, 转到9);
9) 如果$k < n$, 转到7);如果$k=n$, 转到10);
10) $h_i =: 1$; 如果$i < n$, 转到4);如果$i=n$, 转到11);
11) 如果$j < n$, 转到2);如果$j=n$, $| A_1 | =$ $\sum_{j = 1}^{n}{ a_{1j}}$, 转到12);
12) 如果$|A_1|=n$, 输出结果:图$G$连通, 算法结束; 如果$|A_1| < n$, 转到13);
13) 输出结果:图$G$不连通; 算法结束.
步骤8)和10)中的符号$"=:"$表示赋值运算.
定理1. 任给$n\; (n \geq 2)$阶复杂无向网络$G$, 使用基于邻居矩阵的判定算法时, 网络$G$连通的充分必要条件是算法结束后$|A_1| = n$.
证明. 由本文所给算法可知, 当有公共邻居时, 每进行一次求并运算, $A_1$中所包含的邻居数(取值为1的元素数)或者保持不变或者增加.当保持不变且$A_1$包含网络$G$的全部节点, 即$|A_1| = n$时, 网络$G$连通; 当邻居数增加并最终导致$|A_1| = n$时, 网络$G$也连通.
反之, 设$|A_1| < n$时, 网络$G$连通. $|A_1| < n$有两种情况: 1) $|A_1| = 1$, 这表明节点$v_1$是悬挂点, 没有邻接边, 所以网络$G$不连通; 2)至少存在一个$A_i\; (i \in \{2, 3, \cdots, n\})$, 它在算法结束后与$A_1$没有相同的邻居, 即$A_i$对应的子网络与$A_1$对应的子网络没有公共节点, 这便导致$|A_1| < n$, 网络$G$不连通.上述两种情况都与假设矛盾, 则若要网络$G$连通, 必须要$|A_1| = n$.
图 3是本文所给算法的框图.
图 3 基于邻居矩阵的复杂无向网络连通性判定算法框图Fig. 3 Block diagram of the connectivity determination algorithm for complex undirected networks based on the neighbor matrix2.3 算法应用举例
我们以图$G1$和图$G2$所示无向网络为例来说明本文所给算法的具体应用.
例1. 图$G1$所示无向网络有8个节点, 其邻居矩阵$A(G1) \in$ ${\bf R}^{8 \times 8}$.算法运行前, $|A_1(G1)| = 3$, 算法运行后: $j = 1$, $|A_1(G1)| = 4$; $j = 2$, $|A_1(G1)| = 4$; $j = 3$, $|A_1(G1)| = 6$; $j = 4$, $|A_1(G1)| = 8$; $j = 5, 6, 7, 8$时, $|A_1(G1)| = 8$.因此, 可判定图$G1$所示无向网络连通.
例2. 图$G2$所示无向网络有8个节点, 其邻居矩阵$A(G2) \in {\bf R}^{8 \times 8}$.算法运行前, $|A_1(G2)| = 3$, 算法运行后: $j = 1$, $|A_1(G2)| = 3$; $j = 2$, $|A_1(G2)| = 3$; $j = 3$, $|A_1(G2)| = 3$; $j = 4, 5, 6, 7, 8$时, $|A_1(G2)| = 3 < 8$.因此, 可判定图$G2$所示无向网络不连通.
3. 算法复杂性分析
3.1 算法的时间复杂度
给定$n\; (n \geq 2)$阶无向网络$G$, 设其相应的邻居矩阵、邻居集分别为$A(a_{ij}) \in {\bf R}^{n \times n}$和$A_i\; (i = 1, 2, \cdots, n)$.本文所给算法涉及$a_{ij}$是否为1的比较运算, 将$a_{ik}\; (i \geq 2)$的值赋予$a_{1k}$的赋值运算, 以及两个元素$a_{1j}$、$a_{1k}\; (j \neq k)$的布尔或运算.按算法复杂性分析的常规做法, 我们将不考虑赋值运算并将一次比较运算视为一次加法运算.下面, 我们分3部分具体分析本文所给算法的时间复杂度.
1) 对于每一个$j \in \{1, 2, \cdots, n\}$, 本文所给算法需要比较$a_{ij}\; (1 \leq i \leq n)$是否等于1, 用于确定是否存在某个$i\; (2 \leq i \leq n)$使得$a_{1j} = a_{ij} = 1$, 即确定$A_1 \cap A_i$为非零邻居集.对于每一给定的$j$, 这种比较运算共需$n$次, 相当于$n$次加法运算.考虑最坏情况, 即当所有的$a_{1j} = 1\; (1 \leq j \leq n)$时, 这种比较运算总共需要$n^2$次加法运算.
2) 当$A_1 \cap A_i\; (2 \leq i \leq n)$为非零邻居集时, 需进行$A_1 \cup A_i$运算.考虑最坏情况, 即当所有的$a_{ik} = 1\; (2 \leq k \leq n)$时, $A_1 \cup A_i$需要$2(n - 1)$次布尔或运算, 当$i$遍历所有的取值时, 总共需要$2(n - 1)^2$次布尔或运算.
3) 本文所给算法最后需要求$|A_1|$并判定$|A_1|$是否小于$n$, 这部分总共需要$n$次加法运算.
设$J$为总的计算次数, 由上述3部分计算结果可知
$$ J = n^2 + 2(n - 1)^2 + n = 3n^2 - 3n + 2 $$ 因此, 本文所给算法的时间复杂度的上界为O$(3n^2)$.相比之下可知, 就复杂无向网络的连通性判定而言, 本文所给算法的时间复杂度远低于Warshall算法(O$(2n^3)$)和基于可达矩阵算法(O$(n^4)$)的时间复杂度.
3.2 算法的空间复杂度
本文所给算法仅需生成和使用一个邻居矩阵$A(a_{ij}) \in {\bf R}^{n \times n}$和一个标号集$H = \{h_i = 0$或$h_i = 1|i = 1, 2, \cdots, n\}$.因邻居矩阵元素的取值或为0或为1, 所以生成邻居矩阵共需占用$n^2$个存储单元.同理, 标号集$H$共需占用$n$个存储单元.因此, 本文所给算法的空间复杂度的上界为O$(n^2 + n)$.不难理解, 本文所给算法比Warshall算法和基于可达矩阵的算法具有更低的空间复杂度.
3.3 算法的最优分布式实现
分布式计算是一种分组并行计算, 可极大地提高计算效率.由图论和算法结构理论可知, 本文所给算法适合分布式计算.下面, 我们将简要讨论这个问题.
给定$n\; (n \geq 2)$阶无向网络$G$, 我们可以按如下规则将$n$个节点分成$k\; (2 \leq k \leq n)$组, 使得:
1) 每个组中的节点数不少于1个;
2) 任意两个组不包含相同的节点.
如此:
1) 当我们将每个组中的全部节点集结成(视作)一个节点时, $G$就成为具有$k$个节点的网络;
2) 每个组中的全部节点连同它们的邻接边一起构成$G$的一个子网络, 且全部$k$个子网络的并就是$G$;
3) 每个子网络都连通且全部$k$个子网络也连通, 则$G$连通, 否则, $G$不连通.
如果能将本文所给算法分别用于上述每个子网络及全部$k$个子网络时, 除仍可判定$G$的连通性外, 计算量将会大幅度减小.现在的问题是, 如何分组可使总的计算量达到最小?
定理2. 任给$n\; (n \geq 2)$阶无向网络$G$, 将$n$个节点分成$k$组.若分组数$k = \left(\dfrac{n^2}{2}\right)^{\frac{1}{3}}$且每个组中的节点数均为$m = (2n)^{\frac{1}{3}}$, 则将本文所给算法用于$G$的连通性判定时, 计算量将会达到最小.
证明. 本文所给算法的时间复杂度为O$(3n^2)$, 即最大可能的计算量为$3n^2$.设将$n$个节点分成$k\; (2 \leq k \leq n)$组, 每个组中的节点数为$m_i\; (1 \leq i \leq k)$, $\sum_{i = 1}^{k}{ m_i} = n$, $J$为判定$G$的连通性所需最大计算量.由前面的分析可知, 判定每个子网络($m_i$个节点)连通性所需最大计算量为$3m_i^2$, 判定$k$个子网络连通性所需最大计算量为$3k^2$.如此
$$ \begin{align} \label{eq:3} J = \, &3k^2 + \sum\limits_{i = 1}^{k}{ [3m_i^2]} =\nonumber\\ & 3\left\{k^2 + \sum\limits_{i = 1}^{k - 1}{ m_i^2} + m_k^2\right\} =\nonumber\\ & 3\left\{k^2 + \sum\limits_{i = 1}^{k - 1}{ m_i^2} + (n - \sum\limits_{i = 1}^{k - 1}{ m_i})^2\right\} \end{align} $$ (3) 对于$1 \leq i \leq (k - 1)$, 我们有
$$ \begin{align} \label{eq:2} \frac{\partial J}{\partial m_i} =\, & 6\left[m_i - \left(n - \sum\limits_{i = 1}^{k - 1}{ m_i}\right)\right] =\nonumber\\& 6(m_i - m_k) \end{align} $$ (4) 令$\dfrac{\partial J}{\partial m_i} = 0$, 可得$m_1 = m_2 = \cdots = m_{k - 1} = m_k$.这表明, 若要$J$达到最小, 每个组中的节点数必须相等.设每个组的节点数为$m_i = m\; (1 \leq i \leq k)$, 代入前式可得: $J = 3(k^2 + km^2) = 3\left(k^2 + \dfrac{n^2}{k}\right)$.令$\dfrac{\partial J}{\partial k} = 3\left(2k - \dfrac{n^2}{k^2}\right) = 0$, 可得$k = \left(\dfrac{n^2}{2}\right)^{\frac{1}{3}}$.另一方面, $J = 3(k^2 + km^2) = 3\left(\dfrac{n^2}{m^2} + nm\right)$.令$\dfrac{\partial J}{\partial m} = 3\left(n - \dfrac{2n^2}{m^3}\right) = 0$, 可得$m = (2n)^{\frac{1}{3}}$.这表明, 当$k = \left(\dfrac{n^2}{2}\right)^{\frac{1}{3}}$, $m = (2n)^{\frac{1}{3}}$时, 使用本文所给算法可使计算量达到最小.
定理2所确定的分组方式就是本文所给算法的最优分布式实现方式.分组与不分组情况下的计算量之比为$3(2n)^{-\frac{2}{3}}$.显然, $n$越大, 计算量下降的幅度也越大.当$n = 500$时, 分组情况下的计算量仅是不分组情况下的计算量的$3\, \%$.
需要说明的是, 定理2中的$k$和$m$需取整数.下面, 我们举例说明如何确定$k$和$m$的取值问题.
例3. 设某一无向网络$G$具有$n = 497$个节点, 试确定节点的最优分组结果.
由定理2可得: $k = \left(\dfrac{n^2}{2}\right)^{\frac{1}{3}} = \left(\dfrac{1}{2} \times 247\, 009\right)^{\frac{1}{3}} < \left(\dfrac{1}{2} \times 250\, 000\right)^{\frac{1}{3}} = 50$, 即$k < 50$; 同理可得, $k = \left(\dfrac{n^2}{2}\right)^{\frac{1}{3}} = \left(\dfrac{1}{2} \times 247\, 009\right)^{\frac{1}{3}} > \left(\dfrac{1}{2} \times 235\, 298\right)^{\frac{1}{3}} = 49$, 即$k > 49$.我们按两种方式分组: 1) $k = 50$, $m_i = 10\; (1 \leq i \leq 49)$, $m_{50} = 7$, 最大可能的计算量为$J = 3(50^2 + 49 \times 10^2 + 7^2) = 22\, 347$; 2) $k = 49$, $m_i = 10\; (1 \leq i \leq 42)$, $m_i = 11\; (43 \leq i \leq 49)$, 最大可能的计算量为$J = 3(49^2 + 42 \times 10^2 + 7 \times 11^2) = 20\, 166$.显然, 第2种分组方式可使最大可能的计算量达到最小.因此, $k$和$m$的取值应按第2种分组方式确定.
在大规模多智能体编队控制问题中, 各个智能体的相对位置比较固定, 定理2所给的最优分组方法在其通信网络的连通性判定方面更能发挥作用.
4. 结论
在引言部分, 我们论述了网络连通性判定算法、特别是高效连通性判定算法的理论与现实意义.
本文第1节给出了复杂无向网络邻居矩阵和邻居集的定义及相关概念, 它们是基于邻居矩阵的复杂无向网络连通性判定算法, 即本文所给算法的前提.
本文第2节给出了邻居集交与并的运算规则、相关概念及其集合解释.在此基础上, 给出了基于邻居矩阵的复杂无向网络连通性判定算法.该算法是本文的主要贡献, 显然它也适用于简单无向网络的连通性判定.
第3节分析给出了本文所给算法的时间复杂度O$((3n^2))$和空间复杂度O$((n^2 + n))$, 它较Warshall算法和基于可达矩阵的算法具有低得多的时间复杂度和空间复杂度.此外, 本节还给出了可使最大可能的计算量达到最小的最优分布式计算规则, 相关结果则是本文的另一有意义的贡献.
与现有算法相比, 本文所给算法的时间复杂度和空间复杂度均非常低、易于分布式计算, 更适合大规模动态复杂无向网络的连通性判定.需要说明的是, 本文所给算法不能直接用于复杂有向网络的连通性判定.我们今后的工作是将上述结果推广到复杂有向网络, 以期得到更一般和更高效的连通性判定算法.
-
图 3 贝叶斯网络DeeperLab的编码器 − 解码器架构
Fig. 3 Encoder-decoder architecture of the proposed DeeperLab
图 6 不同钢轨场景下LAN网络对不同尺度表面缺陷的检测结果
Fig. 6 LAN detection results of different scaled defects in various rail scenes
图 8 本文方法和其他方法在不同钢轨样本的测试结果
Fig. 8 Results of the proposed method and other methods on various rail samples
表 1 本文方法和其他方法在不同钢轨样本的定量结果
Table 1 Quantitative results of our method and other methods in various rail samples
图像 指标/方法 FCN[32] Unet[34] SegNet[35] PSPNet[36] 之前工作[29] DeepLab v3+[25] Mask RCNN[23] 本文方法 样本 1 MCR (%) 2.25 11.28 1.87 1.12 4.71 1.33 0.94 1.01 RI (%) 97.65 80.87 98.33 98.57 92.46 98.39 98.65 99.60 PSNR (dB) 19.18 28.93 21.09 25.56 24.33 21.46 29.07 32.78 Jacc (%) 31.86 41.67 41.92 64.06 58.35 44.15 81.55 91.09 VI (pixel) 0.20 0.91 0.16 0.12 0.50 0.14 0.11 0.08 样本 2 MCR (%) 1.69 29.72 1.58 1.35 3.43 2.40 2.27 2.49 RI (%) 98.19 53.90 98.31 98.65 96.63 98.42 98.36 98.61 PSNR (dB) 19.37 23.50 19.97 21.49 20.01 24.76 24.53 26.07 Jacc (%) 57.60 27.43 61.19 69.01 59.23 81.84 78.72 85.99 VI (pixel) 0.16 2.24 0.17 0.13 0.31 0.17 0.17 0.15 样本 3 MCR (%) 6.79 31.77 8.95 3.24 14.78 7.91 6.73 6.85 RI (%) 89.00 57.92 93.65 95.35 82.54 95.79 96.40 97.63 PSNR (dB) 12.12 16.95 15.40 15.81 11.41 18.29 19.89 23.37 Jacc (%) 46.47 38.81 64.76 66.97 39.73 78.69 81.00 91.99 VI (pixel) 0.52 2.65 0.44 0.31 1.04 0.35 0.35 0.24 样本 4 MCR (%) 4.66 45.13 10.85 4.45 14.95 11.25 8.43 8.51 RI (%) 94.41 44.64 92.49 13.62 84.56 91.29 95.16 96.10 PSNR (dB) 14.93 16.94 14.15 15.98 19.97 14.96 19.80 21.53 Jacc (%) 64.13 31.80 60.45 67.33 83.72 64.04 82.88 88.98 VI (pixel) 0.44 3.67 0.61 0.47 1.16 0.68 0.49 0.42 样本 5 MCR (%) 7.83 23.93 7.61 12.30 13.98 14.07 11.98 12.21 RI (%) 89.42 76.97 89.73 92.63 91.11 89.75 91.80 95.91 PSNR (dB) 12.34 19.27 12.53 16.67 16.36 13.42 15.80 19.98 Jacc (%) 59.42 70.08 61.14 76.56 76.15 65.02 71.83 89.84 VI (pixel) 0.68 2.09 0.66 0.81 1.00 0.66 0.79 0.51 样本 6 MCR (%) 9.00 17.68 8.64 8.31 14.30 9.54 6.60 7.35 RI (%) 94.33 79.14 95.12 94.87 84.60 93.16 98.00 97.44 PSNR (dB) 16.11 20.54 16.56 17.70 12.45 15.80 22.38 22.64 Jacc (%) 69.14 59.89 71.84 74.68 49.52 67.57 89.78 91.15 VI (pixel) 0.45 1.62 0.40 0.47 0.98 0.53 0.28 0.26 
下载: 导出CSV
表 2 不同贝叶斯变体的性能(%)
Table 2 Performance of difierent Bayesian variants (%)
概率变体 加权平均法 蒙特卡罗采样法 Jacc Dice Jacc Dice 无 Dropout 68.36 68.95 − − 编码器 55.24 56.71 64.60 66.07 解码器 61.78 61.34 63.92 65.88 编−解码器 58.62 60.12 60.57 62.49 输入流 75.44 76.21 82.65 80.33 中间流 83.12 80.69 90.43 91.52 输出流 68.50 67.33 77.21 78.06
下载: 导出CSV
表 3 综合性能的消融研究
Table 3 Ablation experiment of comprehensive performance
方法 Pixel Jacc.
(%)运行时间 (ms) 模型成本(MB) 训练成本(GB) 60 × 40 250 × 160 500 × 300 MobileNet (β = 16) 77.17 19.91 53.10 133.49 23 3.82 ResNet50 (β = 16) 77.80 40.55 141.92 336.36 274 4.43 ResNet101 (β = 16) 78.45 66.37 181.80 431.42 477 6.99 Xception34 (β = 16) 81.66 46.64 149.13 352.70 288 3.97 Xception34 + DA (β = 16) 83.25 − − − − 3.95 Xception65 + DA (β = 16) 88.73 79.64 159.29 517.70 439 4.20 Xception65 + DA + MC (β = 16) 91.46 90.26 180.53 586.73 − 5.56
下载: 导出CSV
-
[1] 贺振东, 王耀南, 毛建旭, 印峰. 基于反向P-M扩散的钢轨表面缺陷视觉检测. 自动化学报, 2014, 40(8): 1667−16791 He Zhen-Dong, Wang Yao-Nan, Mao Jian-Xu, Yin Feng. Research on inverse P-M diffusion-based rail surface defect detection. Acta Automatica Sinica, 2014, 40(8): 1667−1679 [2] 2 He Z D, Wang Y N, Yin F, Liu J. Surface defect detection for high-speed rails using an inverse PM diffusion model. Sensor Review, 2016, 36(1): 86−97 doi: 10.1108/SR-03-2015-0039 [3] 3 Resendiz E, Hart J M, Ahuja N. Automated visual inspection of railroad tracks. IEEE Transactions on Intelligent Transportation Systems, 2013, 14(2): 751−760 doi: 10.1109/TITS.2012.2236555 [4] 孙次锁, 张玉华. 基于智能识别与周期检测的钢轨伤损自动预警方法研究. 铁道学报, 2018, 40(11): 140−146 doi: 10.3969/j.issn.1001-8360.2018.11.0204 Sun Ci-Suo, Zhang Yu-Hua. Research on automatic early warning method for rail flaw based on intelligent identification and periodic detection. Journal of the China Railway Society, 2018, 40(11): 140−146 doi: 10.3969/j.issn.1001-8360.2018.11.020 [5] 5 Liang B, Iwnicki S, Ball A, Young A E. Adaptive noise cancelling and time-frequency techniques for rail surface defect detection. Mechanical Systems and Signal Processing, 2015, 54−55: 41−51 [6] 6 Gibert X, Patel V M, Chellappa R. Deep multitask learning for railway track inspection. IEEE Transactions on Intelligent transportation systems, 2017, 18(1): 153−164 doi: 10.1109/TITS.2016.2568758 [7] Giben X, Patel V M, Chellappa R. Material classification and semantic segmentation of railway track images with deep convolutional neural networks. In: Proceedings of the 2015 IEEE International Conference on Image Processing (ICIP), Québec, Canada: IEEE, 2015: 621−625 [8] Faghih-Roohi S, Hajizadeh S, Núñez A, Babuska R. Deep convolutional neural networks for detection of rail surface defects. In: Proceedings of the 2016 International Joint Conference on Neural Networks (IJCNN), IEEE, 2016: 2584−2589 [9] Masci J, Meier U, Ciresan D, et al. Steel defect classification with max-pooling convolutional neural networks. In: Proceedings of the 2012 International Joint Conference on Neural Networks (IJCNN), IEEE, 2012: 1−6 [10] 10 Chen J W, Liu Z Y, Wang H R, Núñez A, Han Z W. Automatic defect detection of fasteners on the catenary support device using deep convolutional neural network. IEEE Transactions on Instrumentation and Measurement, 2018, 67(2): 257−269 doi: 10.1109/TIM.2017.2775345 [11] 11 Liu Z G, Wang L Y, Li C J, Yang G J, Han Z W. A high-precision loose strands diagnosis approach for isoelectric line in high-speed railway. IEEE Transactions on Industrial Informatics, 2018, 14(3): 1067−1077 doi: 10.1109/TII.2017.2774242 [12] 12 Zhong J P, Liu Z T, Han Z W, Han Y, Zhang W X. A CNN-based defect inspection method for catenary split pins in high-speed railway. IEEE Transactions on Instrumentation and Measurement, 2018 [13] 袁静, 章毓晋. 融合梯度差信息的稀疏去噪自编码网络在异常行为检测中的应用. 自动化学报, 2017, 43(4): 604−61013 Yuan Jing, Zhang Yu-Jin. Application of sparse denoising auto encoder network with gradient difference information for abnormal action detection. Acta Automatica Sinica, 2017, 43(4): 604−610 [14] 唐贤伦, 杜一铭, 刘雨微, 李佳歆, 马艺玮. 基于条件深度卷积生成对抗网络的图像识别方法. 自动化学报, 2018, 44(5): 855−86414 Tang Xian-Lun, Du Yi-Ming, Liu Yu-Wei, Li Jia-Xin, Ma Yi-Wei. Image recognition with conditional deep convolutional generative adversarial networks. Acta Automatica Sinica, 2018, 44(5): 855−864 [15] 辛宇, 杨静, 谢志强. 基于标签传播的语义重叠社区发现算法. 自动化学报, 2014, 40(10): 2262−227515 Xin Yu, Yang Jing, Xie Zhi-Qiang. An overlapping semantic community structure detecting algorithm by label propagation. Acta Automatica Sinica, 2014, 40(10): 2262−2275 [16] 16 Denker J S, Lecun Y. Transforming neural-net output levels to probability distributions. Advances in Neural Information Processing Systems, 1991: 853−859 [17] 17 MacKay D J C. A practical Bayesian framework for backpropagation networks. Neural Computation, 1992, 4(3): 448−472 doi: 10.1162/neco.1992.4.3.448 [18] 18 Srivastava N, Hinton G, Krizhevsky A, Sutskever I, Salakhutdinov R. Dropout: a simple way to prevent neural networks from overfitting. The Journal of Machine Learning Research, 2014, 15(1): 1929−1958 [19] Gal Y, Ghahramani Z. Dropout as a Bayesian approximation: representing model uncertainty in deep learning. In: Proceedings of the 2016 International Conference on Machine Learning, 2016: 1050−1059 [20] 郑文博, 王坤峰, 王飞跃. 基于贝叶斯生成对抗网络的背景消减算法. 自动化学报, 2018, 44(5): 878−89020 Zheng Wen-Bo, Wang Kun-Feng, Wang Fei-Yue. Background subtraction algorithm with Bayesian generative adversarial networks. Acta Automatica Sinica, 2018, 44(5): 878−890 [21] Fu J, Zheng H, Mei T. Look closer to see better: recurrent attention convolutional neural network for fine-grained image recognition. In: Proceedings of the 2017 IEEE Conference on Computer Vision and Pattern Recognition, 2017: 4438−4446 [22] Wang F, Jiang M Q, Qian C, Yang S, Li C, Zhang H G, et al. Residual attention network for image classification. In: Proceedings of the 2017 IEEE Conference on Computer Vision and Pattern Recognition, 2017: 3156−3164 [23] He K M, Gkioxari G, Dollar P, Girshick R. Mask R-CNN. In: Proceedings of the 2017 IEEE International Conference on Computer Vision, 2017: 2961−2969 [24] 24 Lin H, Shi Z, Zou Z. Fully convolutional network with task partitioning for inshore ship detection in optical remote sensing images. IEEE Geoscience and Remote Sensing Letters, 2017, 14(10): 1665−1669 doi: 10.1109/LGRS.2017.2727515 [25] Chen L C, Zhu Y K, Papandreou G, Schroff F, Adam H. Encoder-decoder with atrous separable convolution for semantic image segmentation. In: Proceedings of the 2018 European Conference on Computer Vision (ECCV), 2018: 801−818 [26] 韩江洪, 乔晓敏, 卫星, 陆阳. 基于空间卷积神经网络的井下轨道检测方法. 电子测量与仪器学报, 2018, 32(12): 34−4326 Han Jiang-Hong, Qiao Xiao-Min, Wei Xing, Lu Yang. Downhole track detection method based on spatial convolutional neural network. Journal of Electronic Measurement and Instrumentation, 2018, 32(12): 34−43 [27] 时增林, 叶阳东, 吴云鹏, 娄铮铮. 基于序的空间金字塔池化网络的人群计数方法. 自动化学报, 2016, 42(6): 866−87427 Shi Zeng-Lin, Ye Yang-Dong, Wu Yun-Peng, Lou Zheng-Zheng. Crowd counting using rank-based spatial pyramid pooling network. Acta Automatica Sinica, 2016, 42(6): 866−874 [28] Chen L C, Papandreou G, Kokkinos I, Murphy K, Yuille A L. Semantic image segmentation with deep convolutional nets and fully connected CRFs, arXiv preprint arXiv: 1412. 7062, 2014 [29] 张辉, 金侠挺, Wu Q M Jonathan, 贺振东, 王耀南. 基于曲率滤波和改进GMM的钢轨缺陷自动视觉检测方法. 仪器仪表学报, 2018, 39(4): 181−19429 Zhang Hui, Jin Xia-Ting, Wu Q. M. Jonathan, He Zhen-Dong, Wang Yao-Nan. Automatic visual detection method of railway surface defects based on curvature filtering and Improved GMM. Chinese Journal of Scientific Instrument, 2018, 39(4): 181−194 [30] 骆小飞, 徐军, 陈佳梅. 基于逐像素点深度卷积网络分割模型的上皮和间质组织分割. 自动化学报, 2017, 43(11): 2003−201330 Luo Xiao-Fei, Xu Jun, Chen Jia-Mei. A deep convolutional network for pixel-wise segmentation on epithelial and stromal tissues in histologic images. Acta Automatica Sinica, 2017, 43(11): 2003−2013 [31] Chollet F. Xception: deep learning with depthwise separable convolutions. In: Proceedings of the 2017 IEEE Conference on Computer Vision and Pattern Recognition, 2017: 1251−1258 [32] Long J, Shelhamer E, Darrell T. Fully convolutional networks for semantic segmentation. In: Proceedings of the 2015 IEEE Conference on Computer Vision and Pattern Recognition, 2015: 3431−3440 [33] Redmon J, Divvala S, Girshick R, Farhadi A. You only look once: unified, real-time object detection. In: Proceedings of the 2016 IEEE Conference on Computer Vision and Pattern Recognition, 2016: 779−788 [34] Ronneberger O, Fischer P, Brox T. U-net: convolutional networks for biomedical image segmentation. In: Proceedings of the 2015 International Conference on Medical image Computing and Computer-assisted Intervention, Springer, Cham, 2015: 234−241 [35] 35 Badrinarayanan V, Kendall A, Cipolla R. Segnet: a deep convolutional encoder-decoder architecture for image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2017, 39(12): 2481−2495 doi: 10.1109/TPAMI.2016.2644615 [36] 36 Zhao H S, Shi J P, Qi X J, Wang X G, Jia J Y. Pyramid scene parsing network. In: Proceedings of the 2017 IEEE Conference on Computer Vision and Pattern Recognition, 2017: 2881−2890 期刊类型引用(28)
1. 何成刚，张坤雄，俞茹昕，王欣纪，徐逸勋，刘吉华. 机器视觉在钢轨表面病害检测应用研究综述. 高速铁路新材料. 2024(01): 7-13 . 
百度学术2. 杨春龙，吕东澔，张勇，任彦，李少波. 融合自适应下采样的带钢表面缺陷检测算法. 钢铁研究学报. 2024(06): 806-816 . 百度学术3. 李磊，李妍. 基于改进YOLOV7的钢轨表面伤损智能检测研究. 中国战略新兴产业. 2024(17): 140-143 . 百度学术4. 郑广智，彭添强，肖计春，吴高昌，李智，柴天佑. 基于语义信息增强的化纤丝线网络度检测方法. 自动化学报. 2024(10): 1963-1976 . 本站查看5. 王煜，齐宏拓，杨整涛，程柯帏，伍洲. 基于点云分层融合架构的混凝土气孔缺陷量化评估方法. 仪器仪表学报. 2024(07): 86-98 . 百度学术6. 井庆龙，闵永智，李成学. 融合贝叶斯优化的轨面缺陷检测模型压缩方法. 兰州交通大学学报. 2024(05): 130-138 . 百度学术7. 王耀东，于航，李宁，朱力强，史红梅，余祖俊. 基于纹理特征增强的重载铁路钢轨缺陷检测算法. 铁道学报. 2024(11): 93-101 . 百度学术8. 马居坡，陈周熠，吴金建. 基于动态视觉传感器的铝基盘片表面缺陷检测. 自动化学报. 2024(12): 2407-2419 . 本站查看9. 张晓宇，李立明，柴晓冬，郑树彬，汪晨曦. 基于级联网络的钢轨顶面缺陷检测方法研究. 铁道标准设计. 2023(03): 90-97 . 百度学术10. 兰欢，余建波. 基于深度学习三维成型的钢板表面缺陷检测. 浙江大学学报(工学版). 2023(03): 466-476+561 . 百度学术11. 周云海，靳广伟，于高缘，黄伟，迟婉求，黄南天. 基于BAGAN-CNN的局部放电模式识别. 电气应用. 2023(07): 25-33 . 百度学术12. 吴福培，谢晓扬，黄耿楠，吴涛，李昇平. 基于Anchors设计和模型迁移的钢轨内部伤损检测方法. 铁道学报. 2023(10): 112-119 . 百度学术13. 张泽辉，李庆丹，富瑶，何宁昕，高铁杠. 面向非独立同分布数据的自适应联邦深度学习算法. 自动化学报. 2023(12): 2493-2506 . 本站查看14. 杨杨，黄菊. 基于机器视觉的直插式网络变压器PIN脚平整度检测. 四川职业技术学院学报. 2023(06): 152-157 . 百度学术15. 曹义亲，刘龙标，何恬，丁要男. 基于贪心选择及斜率探测扩充的轨面提取方法. 计算机科学与探索. 2022(01): 205-216 . 百度学术16. 王品学，张绍兵，成苗，何莲，秦小山. 基于可变形卷积和自适应空间特征融合的硬币表面缺陷检测算法. 计算机应用. 2022(02): 638-645 . 百度学术17. 马天鸽. 基于光纤感测技术的城市轨道交通钢轨状态实时监测方法. 机械与电子. 2022(02): 50-54 . 百度学术18. 吴捷. 基于改进YOLOv3模型的接触轨表面缺陷检测方法. 设备管理与维修. 2022(06): 30-32 . 百度学术19. 余文勇，张阳，姚海明，石绘. 基于轻量化重构网络的表面缺陷视觉检测. 自动化学报. 2022(09): 2175-2186 . 本站查看20. 赵晨阳，张辉，廖德，李晨. 基于注意力机制与混合监督学习的钢轨表面缺陷检测模型. 计算机科学. 2022(S2): 488-493 . 百度学术21. 刘金海，赵真，付明芮，左逢源，王雷. 基于主动小样本学习的管道焊缝缺陷检测方法. 仪器仪表学报. 2022(11): 252-261 . 百度学术22. 邓泽林，刘行，董云龙，袁烨. 无纺布疵点实时检测技术与系统设计. 自动化学报. 2021(03): 583-593 . 本站查看23. 徐科，甘伟，焦建朋，张俊升，朱华林，周东东. 基于光度立体的钢轨表面三维重建方法. 河北冶金. 2021(05): 18-22+82 . 百度学术24. 黄健，郑春厚，章军，王兵，陈鹏. 基于小样本度量迁移学习的表面缺陷检测. 模式识别与人工智能. 2021(05): 407-414 . 百度学术25. 曹义亲，丁要男. 基于HSV色彩空间S分量的轨面区域提取方法. 南京理工大学学报. 2021(04): 464-471 . 百度学术26. 姜迪，刘慧，李钰，张彩明. 结合稠密特征映射的CT图像肿瘤分割模型. 计算机辅助设计与图形学学报. 2021(08): 1273-1286 . 百度学术27. 景志远，王二化，朱彪. 粗轧板坯表面裂纹检测与控制的应用. 冶金自动化. 2021(06): 76-83 . 百度学术28. 李杰，李响，许元铭，杨绍杰，孙可意. 工业人工智能及应用研究现状及展望. 自动化学报. 2020(10): 2031-2044 . 本站查看其他类型引用(51)
-
下载:
计量
- 文章访问数: 3932
- HTML全文浏览量: 1249
- PDF下载量: 650
- 被引次数: 79
