基于上下文模糊C均值聚类的图像分割算法

徐金东; 赵甜雨; 冯国政; 欧世峰

doi:10.11999/JEIT200263

基于上下文模糊C均值聚类的图像分割算法

doi: 10.11999/JEIT200263

1.
烟台大学计算机与控制工程学院烟台 264005
2.
烟台大学光电信息科学与技术学院烟台 264005

基金项目: 国家自然科学基金(62072391, 62066013)，山东省自然科学基金(ZR2019MF060, ZR2017MF008)，山东省高等教育科学技术重点计划(J18KZ016)，烟台市科技计划(2018YT06000271)

详细信息

作者简介:
徐金东：男，1980年生，副教授，硕士生导师，研究方向为图像处理、模式识别、盲源分离

赵甜雨：女，1996年生，硕士生，研究方向为图像聚类、计算机视觉、模式识别和人工智能

冯国政：男，1996年生，博士生，研究方向为图像分类、模式识别和机器学习

欧世峰：男，1979年生，教授，硕士生导师，研究方向为信号处理、盲信号分析

通讯作者:
徐金东　jindong.xu@nlpr.ia.ac.cn

中图分类号: TN911.73
计量
- 文章访问数: 1227
- HTML全文浏览量: 566
- PDF下载量: 120
- 被引次数: 7
出版历程
- 收稿日期: 2020-04-10
- 修回日期: 2020-10-23
- 网络出版日期: 2021-03-30
- 刊出日期: 2021-07-10

Image Segmentation Algorithm Based on Context Fuzzy C-Means Clustering

1.
School of Computer and Control Engineering, Yantai University, Yantai 264005, China
2.
School of Opto-Electronic Information Science and Technology, Yantai University, Yantai 264005, China

Funds: The National Natural Science Foundation of China (62072391, 62066013), The Natural Science Foundation of Shandong Province (ZR2019MF060, ZR2017MF008), The Project of Shandong Province Higher Educational Science and Technology Key Program (J18KZ016), The Yantai Science and Technology Plan (2018YT06000271)

摘要

摘要: 像素间的上下文相关信息对图像分割算法的抗噪性和准确性具有重要意义，现有的模糊C均值(FCM)聚类算法对此缺乏充分考虑。该文基于对空间上下文的可靠性度量，提出一种模糊C均值聚类算法(RSFCM)应用于图像分割：通过对空间上下文有效建模来提高聚类算法的抗噪声干扰性能，并研究了一种新的可靠性模糊度量指标，使聚类算法能更好地平衡细节保留和去噪，从而获得更加准确的分割结果。实验选取人工合成图像、交通标志图像和遥感图像3类数据测试聚类算法性能，结果表明，RSFCM在图像分割过程中能有效地抑制椒盐噪声和高斯噪声引起的类内异构及类间同构问题，能提高图像的像素可分性，并有效地保留了图像的边缘细节。
- 图像分割 /
- 聚类 /
- 模糊C均值 /
- 空间上下文
Abstract: The correlation information between pixels is of great significance for image segmentation. The existing Fuzzy C-Means (FCM) clustering algorithm lacks sufficient consideration for it. Based on the reliability measure of spatial context, this paper proposes a Reliability-based Spatial context Fuzzy C-Means (RSFCM) clustering algorithm: The clustering algorithm anti-noise performance is improved by effectively modeling the spatial neighborhood; A new reliability fuzzy metric is proposed, which balances the relationship between detail retention and anti-noise, so that the clustering results are more accurate. A synthetic image, a traffic sign image and a remote sensing image are used to test the algorithms performance. The results show, compared with the existing FCM algorithm, RSFCM can effectively suppress heterogeneity of intra-class objects caused by Salt & Pepper noise and Gaussian noise for the image segmentation, improve pixels separability and preserve the edge details of the image greatly.
- Image segmentation /
- Clustering /
- Fuzzy C-Means (FCM) /
- Spatial context

HTML全文

1. 引言

2019年9月，芬兰奥卢大学6G旗舰研究计划组发布了全球首个6G白皮书，该白皮书认为6G的大多数性能指标相比5G将提升10～100倍。其中通信时延可低至0.1 ms，将是5G的1/10，并且具有超高可靠性^[1]。这些需求对移动通信中的信道编解码的延迟特性和译码性能提出了更高的要求。极化码是第1种被证明在二进制离散无记忆信道下能够达到信道容量的纠错码^[2]，具有较高的可靠度和实用价值，已经成为5G控制信道的编码方案，并有望成为6G通信中主要的信道编码方案。在极化码的译码算法方面，串行抵消(Successive Cancellation, SC)算法^[3,4]和串行抵消列表(Successive Cancellation List, SCL)^[5]作为极化码的低复杂度译码方案，具有较高的可靠性，但在译码时均需遍历译码二叉树的每个节点，导致译码延迟较高。与SC, SCL算法不同，置信度传播算法(Belief Propagation, BP)是一种并行迭代的译码算法，可获得较低的译码延迟。然而，大量的迭代次数仍造成BP较高的计算复杂度。由于大部分BP译码器在到达最大迭代次数之前已经收敛于原始码字，因此需要引入迭代早期迭代停止准则提前判断。为了减少迭代冗余，Yuan等人^[6]提出了G矩阵(G-matrix)和最小对数似然比 (minimum Log Likelihood Ratio, minLLR)两个准则。其中，G-Matrix包含 $N\log N$ 次二进制操作，而minLLR需要进行大量的比较运算。Yan等人^[7]提出一种基于局部固定比特的早期停止准则，将固定位作为提前停止的准则。为降低资源消耗，文献[8]提出一种有效节省资源消耗的提前迭代终止准则，与基于阈值的算法相比，该准则可降低资源消耗且不会造成译码性能损失。Ren等人^[9]提出了LLR辅助(LLR-Magnitude Aided, LMA)和循环冗余校验辅助(CRC Aided, CA)两种早期停止准则，当信噪比为4 dB、最大迭代次数为30时，LMA和CA分别能减少72.6%和84.5%的迭代次数。此外，Simsek等人^[10]提出一种基于最坏信息位(Worst of Information Bits, WIB)的早期停止准则，它只需检测一部分LLR的符号位，可使译码复杂度有所降低，但译码性能低于G-Matrix。Simsek等人^[11]通过去除冗余加法器阵列对WIB进行了优化。另外，Albayrak等人^[12]提出了一种基于Luby变换的提前停止准则，通过观察译码器中LLR信息的符号位变化，确定译码输出是否收敛到原始序列。文献[13]于2017年提出了一种检测冻结位误码率(Frozen Bit Error Rates, FBER)的早期停止准则，该准则只检测在最可靠的冻结子信道中传输的冻结位。受到早期停止准则的启发，Giard等人^[14]提出了基于极化码BP译码算法的盲检测法。上述准则都取决于 $\hat u$ 或与 $\hat u$ 对应的对数似然比(Log Likelihood Ratio, LLR)。

本文研究了信息序列估值( $\hat u$ )与码字估值( $\hat x$ )之间的关系，当 $\hat u$ 和 $\hat x$ 满足编码算法施加的约束时，可获得有效的码字估值。当 $\hat x$ 收敛到有效估值时， $\hat u$ 亦收敛到有效估值。基于这一思想，本文提出了一种新的早期停止准则，该方案只监测 $\hat x$ 的收敛性。同时，借助高斯近似(Gaussian Approximation, GA)^[15]分析了 $\hat x$ 中每位比特的出错概率，发现一些出错概率较低的 $\hat x$ 需要较少的迭代次数。因此，该准则构造了一个由 $\hat x$ 中出错概率较低的部分构成的比较空间。由于只检测 $\hat x$ 中一部分比特的收敛性，所提出的准则进一步节省了硬件资源消耗。另外，由于译码器的最终输出是 $\hat u$ ，如果早期停止准则取决于 $\hat u$ ，那么它只能在获得 $\hat u$ 后开始执行，将导致额外的计算复杂性和延迟。所提出的方案只取决于 $\hat x$ ，可避免这种情况。仿真结果表明，所提算法在不损失译码性能的情况下，可有效降低计算复杂度并减少译码的平均迭代次数。

2. 基本理论

2.1 极化码

极化码可定义为{N, K, A, A^C}，其中N=2ⁿ, K, A, A^C分别表示码长、信息位个数、信息位集合和冻结位集合。信息 ${{u}}$ 由K个信息位和(N-K)个冻结位组成，与生成矩阵G相乘获得码字 ${{x}}$ 。其中 ${{G}} = {{B}} \cdot {{{F}}^{ \otimes n}}$ , $B$ 是位置换矩阵， ${{{F}} ^{ \otimes n}}$ 表示 ${{F}} = \left[ {\begin{array}{*{20}{c}} 1&0 \\ 1&1 \end{array}} \right]$ 的n次克罗内克积。

2.2 BP译码算法

一个 (N, K)极化码可用一个 $n$ 阶因子图来表示，它在每阶都有N/2个处理单元(Processing Element, PE)，整个因子图包含 (n+1)N个节点。图1为(8, 4)极化码的因子图。BP算法的每次迭代过程由一个右向信息更新和一个左向信息更新组成。令 $L_{i,j}^t$ 和 $R_{i,j}^t$ 分别表示节点(i, j)在第t次迭代中自右向左和自左向右传播的信息，其中i是位索引，j是阶数索引。BP译码器中的节点更新如式(1)所示

图 1 (8, 4)极化码的因子图

下载: 全尺寸图片幻灯片

$\left. \begin{aligned} & L_{i,j}^t = \left\{ {{{f}} \left( {R_{i + N/2,j}^t + L_{2i,j + 1}^t,L_{2i - 1,j + 1}^t} \right)} \right\} \\ & L_{i + N/2,j}^t = \left\{ {{{f}} \left( {R_{i + N/2,j}^t + L_{2i,j + 1}^t} \right) + L_{2i,j + 1}^t} \right\} \\ & R_{2i - 1,j + 1}^t = \left\{ {{{f}} \left( {L_{2i,j + 1}^{t - 1} + R_{i + N/2,j}^t,R_{i,j}^t} \right)} \right\} \\ & R_{2i,j + 1}^t = \left\{ {{{f}} \left( {L_{2i - 1,j + 1}^{t - 1},R_{i,j}^t} \right) + R_{i + N/2,j}^t} \right\} \end{aligned} \right\}$

(1)

其中

${{f}} ({{x}},{{y}}) \approx \alpha *{\rm{sign}} ({{x}}){\rm{sign}} ({{y}})\min {\kern 1pt} (|{{x}}|,|{{y}}|)$

(2)

式(2)中α是伸缩因子。在右向更新信息期间，按照 $j = 2,3, ··· ,n + 1$ , $R_{i,j}^t$ 进行串行更新。在 $n + 1$ 列的 $R_{i,j + 1}^t$ 更新之后进行左向更新， $L_{i,j}^t$ 按照 $j = n,n - 1, ··· ,1$ 进行串行更新。当BP译码器达到最大迭代次数 ${I_{\max }}$ 时，第 $i$ 个信息位的估值可通过式(3)得到

${\hat u_i} = {\rm{sign}} (L_{i,1}^{{I_{\max }}}),i \in A$

(3)

3. 提出的早期迭代停止准则

3.1 X-tolerance早期迭代停止准则

BP算法的迭代过程可用极化码的因子图来表示。因子图中的每一个节点都与编码过程中的节点相对应，由于因子图节点中包含相应节点的LLR，则对因子图节点中的LLR进行硬判决即可得到相应的编码过程的中间估计值。对最左侧列节点中的LLR进行硬判决可得 ${u_i}$ 的估值 ${\hat u_i}$ ，类似地对最右侧即因子图中第n+1列节点中的LLR进行判决可得到 ${x_i}$ 的估值 ${\hat x_i}$ 。设 $R_{i,n + 1}^t = \ln ({P} ({\hat x_i} = 0)/{P} ({\hat x_i} = 1)$ , ${\hat x_i}$ 代表码字估值中的第i位。因此， ${\hat x_i}$ 定义为

${\hat x_i} = {s_{i,n + 1}} = {\rm{sign}} (R_{i,n + 1}^t)$

(4)

$\hat x = \left\{ {{{\hat x}_1},{{\hat x}_2},···,{{\hat x}_N}} \right\} = ({s_{1,n + 1}},{s_{2,n + 1}}, ··· ,{s_{N,n + 1}})\!\!\!\!\!$

(5)

对于任何极化码， ${{x}} = {{u}} \cdot {{G}}$ ，如果 $\hat x$ 和 $\hat u$ 是有效的估值，则必须满足式(6)

$\hat {{x}} = \hat {{u}} \cdot {{G}}$

(6)

基于该推论， ${{ \hat x}} = {{\hat u }}\cdot {{G}}$ 可被用于在迭代过程中检测 ${{\hat x}}$ 与 ${{\hat u}}$ 是否为有效的估值。G-Matrix早期停止准则根据极化码编码中信息序列 $u$ 和码字 $x$ 之间的关系，在译码迭代中通过判断是否满足式(6)来决定是否提前停止译码迭代，因此每一次判断都相当于进行一次极化码编码。本文对G-Matrix做了进一步分析，依据式(6)，发现译码中信息序列估值 ${{\hat u}}$ 和码字估值 ${{\hat x}}$ 存在下列3种类型：类型1， ${{\hat x}}$ 和 ${{\hat u}}$ 满足式(6), ${{\hat x}}$ 和 ${{\hat u}}$ 均为有效估值；类型2， ${{\hat x}}$ 和 ${{\hat u}}$ 满足式(6), ${{\hat x}}$ 和 ${{\hat u}}$ 均为有效估值，但 ${{\hat u}}$ 并不是发送端所传输的信息序列；类型3：迭代次数达到最大迭代次数时依旧不满足式(6)。

对于类型2, ${{\hat x}}$ 和 ${{\hat u}}$ 在迭代过程中满足这种约束，即 ${{\hat x}}$ 的确是 ${{\hat u}}$ 经过极化编码后的码字，但 $\hat u_1^N \ne u_1^N$ ，即该信息序列并不是发送端所发送的信息。该类型情况在译码过程中极少发生，可忽略。类型3属于提前终止准则无法处理的情况，该类型会在迭代次数到达预设的最大迭代次数后停止。由以上分析可知，有效处理类型1是本文研究的重点。

对于类型1，为了满足式(6), ${{\hat x}}$ 和 ${{\hat u}}$ 需要同时为有效的估值。令 ${T_u}$ 表示 ${{\hat u}}$ 收敛所需的最小迭代次数， ${T_x}$ 表示 ${{\hat x}}$ 收敛所需的最小迭代次数，则类型1中迭代终止所需迭代次数由 ${T_u}$ 和 ${T_x}$ 中的较大值决定。

令 ${T_d}$ 表示译码成功所需的最小迭代次数。通过仿真得到 ${T_d}$ , ${T_u}$ 和 ${T_x}$ 之间的大小关系。图2展示了 ${T_u} - {T_d} > 0$ 和 ${T_x} - {T_u} > 0$ 的比例，灰色部分为 ${T_u} - {T_d} = 0$ 的比例。从图2中可看到 ${T_x}$ 是 ${T_u}$ 和 ${T_x}$ 之间较大的那个。因此，对于类型1，迭代终止准则可简化为判断 $\hat x$ 是否收敛。如图3所示，当E_b/N₀= $2.5\;{\rm{dB}}$ 时，随着迭代次数的增加， ${{\hat x}}$ 中的符号改变个数和 ${{\hat u}}$ 中的错误估值位数均迅速下降。当 ${{\hat u}}$ 中的错误估值位数下降到0，得到一个有效估值。

图 2

${T_d}$ ,

${T_u}$ 和

${T_x}$ 的大小关系

下载: 全尺寸图片幻灯片

图 3

$\hat x$ 中符号变化和

$\hat u$ 中错误位数

下载: 全尺寸图片幻灯片

在BP译码过程中，如果 ${{\hat x}}$ 连续几次迭代保持不变，则认定 ${{\hat x}}$ 已经收敛。因此，本文提出了一种新的停止准则，称之为X-tolerance。当 ${{\hat x}}$ 在连续X次迭代中保持不变时停止迭代。X-tolerance检测规则如式(7)所示。该准则不同于G-Matrix，它只依赖码字估计值 ${{\hat x}}$ ，无须每次迭代均对 ${{\hat u}}$ 进行重新编码，因此减少了计算复杂度

$\sum\limits_{t - X + 1}^t {\sum\limits_{i = 1}^N {\hat x_i^t} } \oplus \hat x_i^{t - 1} = 0$

(7)

3.2 比较空间的构造

在式(7)中，X-tolerance在一次迭代中需要N个异或(XOR)操作，为了进一步减小计算复杂度，本文定义了一个集合 $S \subseteq \left\{ {1,2, ··· ,N} \right\}$ ，称为比较空间，是由 $\hat x$ 中部分比特的索引构成的集合。设 $P({\hat x_i} \ne {x_i})$ 是当 $t = {I_{\max }}$ 时的 ${\hat x_i}$ 的出错概率。对于BP译码器，具有较低 $P({\hat x_i} \ne {x_i})$ 的 $\hat x_1^N$ 需要较少的译码迭代。利用这一思想，根据 $P({\hat x_i} \ne {x_i})$ 构造了比较空间。

对于n=3，极化码的Tanner图如图4所示。圆圈表示变量节点，方块表示校验节点。变量节点中的信息用LLR表示。设 ${a_{i,j}}$ 表示节点 $v(i,j)$ 的LLR的概率密度函数(Probability Density Function, PDF)。假设传输全零码字，基于密度进化理论^[11]，采用式(8)和式(9)递归地计算 ${a_{i,j}}$

图 4 (8, 4)极化码的Tanner图

下载: 全尺寸图片幻灯片

$\begin{split} \qquad\quad\ & {a_{2i - 1,j}} = {a_{i,j + 1}} \odot {a_{i + {2^{j + 1}},j + 1}},\\ & {a_{2i,j}} = {a_{i,j + 1}} \otimes {a_{i + {2^{j + 1}},j + 1}} \end{split}$

(8)

$\quad {a_{i,n + 1}} = {a_w}$

(9)

其中， $\odot$ 和 $\otimes$ 分别是变量节点和校验节点的卷积操作。 ${a_w}$ 是信道W接收到的LLR的概率密度函数。对于BP译码，设 $r_{i,j}^t$ 和 $l_{i,j}^t$ 表示 $v(i,j)$ 中 $R_{i,j}^t$ 和 $L_{i,j}^t$ 的概率密度函数。根据式(1)和密度进化理论， $r_{i,j}^t$ 和 $l_{i,j}^t$ 可通过式(10)计算

$\left. \begin{aligned} & r_{i,{{j}} + 1}^t = \left\{ {r_{2i - 1,{{j}}}^t \odot (r_{2i,{{j}}}^t \otimes l_{i + {2^{j + 1}},{{j}} + 1}^{t - 1})} \right\} \\ & r_{i + {2^{j + 1}},{{j}} + 1}^t = \left\{ {(r_{2i - 1,{{j}}}^t \otimes l_{i,{{j}} + 1}^{t - 1}) \odot r_{2i,{{j}}}^t} \right\} \\ & l_{2i - 1,{{j}}}^t = \left\{ {l_{i,{{j}} + 1}^t \odot (l_{i + {2^{j + 1}},{{j}} + 1}^t \otimes r_{2i,{{j}}}^t)} \right\} \\ & l_{2i,{{j}}}^t = \left\{ {(l_{i,{{j}} + 1}^t \otimes r_{2i - 1,{{j}}}^t) \odot l_{i + {2^{j + 1}},{{j}} + 1}^t} \right\} \end{aligned}\right\}$

(10)

根据BP算法的初始化可得， $r_{i,1}^t$ 满足

$\int\limits_{ - \infty }^0 {r_{i,1}^t} {\rm{d}}z = \left\{ \begin{aligned} & {0.5,i \in A} \\ & {0,\ \ i \notin A} \end{aligned} \right.,\;l_{i,n + 1}^t = {a_w}$

(11)

可用GA简化计算， $r_{i,j}^t$ 和 $l_{i,j}^t$ 分别表示为 ${\cal{N}}(m_{i,j}^{r,t},2m_{i,j}^{r,t})$ 和 ${\cal{N}}(m_{i,j}^{l,t},2m_{i,j}^{l,t})$ ^[13]。因此，式(10)和式(11)可近似为

$\begin{split} & m_{i,j + 1}^{r,t} = \left\{ {\varphi ^{ - 1}}(1 - [1 - \varphi (m_{2i - 1,j}^{r,t})]\right.\\ & \qquad\quad\ \ \left.\cdot [1 - \varphi (m_{2i,j}^{r,t} + m_{i + {2^{j + 1}},j + 1}^{l,t - 1})]) \right\}, \\ & m_{i + {2^{j + 1}},j + 1}^{r,t} = \left\{ {\varphi ^{ - 1}}(1 - [1 - \varphi (m_{2i - 1,j}^{r,t})]\right.\\ & \qquad\qquad\qquad \left.\cdot [1 - \varphi (m_{i,j + 1}^{l,t - 1})]) + m_{2i,j}^{r,t} \right\}, \\ & m_{2i - 1,j}^{l,t} = \left\{ {\varphi ^{ - 1}}(1 - [1 - \varphi (m_{i,j + 1}^{l,t})]\right.\\ & \qquad\quad\ \ \ \left.\cdot [1 - \varphi (m_{2i,j}^{l,t} + m_{i + {2^{j + 1}},j + 1}^{r,t})]) \right\}, \\ & m_{2i,j}^{l,t} = \left\{ {\varphi ^{ - 1}}(1 - [1 - \varphi (m_{2i - 1,j}^{l,t})] \right.\\ & \qquad\quad\ \left. \cdot [1 - \varphi (m_{i,j + 1}^{l,t})]) + m_{i + {2^{j + 1}},j + 1}^{l,t} \right\} \!\!\!\!\! \end{split}$

(12)

$m_{i,1}^{r,t} = \left\{ \begin{aligned} & {0,\quad\ i \in A} \\ & { + \infty ,i \notin A} \end{aligned} \right.$

(13)

$m_{i,n + 1}^{l,t} = 2/{\sigma ^2}$

(14)

在得到 $m_{i,n + 1}^{l,{I_{\max }}}$ 后， ${\hat x_i}$ 的错误概率通过式(15)计算

$\begin{split} P({\hat x_i} \ne {x_i}) =\,& \int\limits_{ - \infty }^0 {\frac{1}{{2\sqrt {\pi a_{i,n + 1}^t} }}} \\ & \cdot \exp \left( {\frac{{ - {{(x - m_{i,n + 1}^{l,{I_{\max }}})}^2}}}{{4m_{i,n + 1}^{l,{{{I}} _{\max }}}}}} \right){\rm{d}}x \end{split}$

(15)

式(15)可简化为^[16]

$\begin{split} & P({\hat x_i} \ne {x_i}) \\ & = \left[ {{\rm{1}} - {{\left( {1 - \exp \left( { - \left( {m_{i,n + 1}^{l,{I_{\max }}}/2} \right)/1.6058} \right)} \right)}^{1/2}}} \right]\Bigr/2 \end{split}$

(16)

对于X-tolerance，当采用比较空间缩小检测范围时，错误率会增加。然而，当增加X来弥补性能损失时，又增加了平均迭代次数。因此，为尽可能降低平均迭代次数，S由 $\{ P({\hat x_i} \ne {x_i})\left| {i = 1,2, ··· ,{{N}}} \right.\}$ 中Q个最小值的索引构成。当式(17)满足时，X-tolerance停止迭代译码，在算法1中给出了具体的BP译码过程

算法1　(N, K) X-tolerance BP译码器
(1) 输入：
(2) 信道输出： ${\rm{ LLR}}\left( { {r_i} } \right)$
(3) 冻结位集合： $A^C$
(4) 比较空间：S
(5) 初始化：
(6) 设定 ${I_{\max }}$ 和X
(7) For 每个节点的传播信息 $L_{i,j}^t$ 和 $R_{i,j}^t$
(8)　　if $(j = = 1)$ & $\left( {i \in {A^C}} \right)$ $R_{i,1}^t = \infty$ 对于t=0, 1,···, I_max
(9)　　else if $(j = = 1 + n)$ $L_{i,n + 1}^t = {\rm{LLR}}\left( { {r_i} } \right)$ 对于t=0, 1,···, 　　　　 I_{max x}
(10)　　else $L_{i,j}^0 = R_{i,j}^0 = 0$
(11) 迭代过程：
(12) While $t < {I_{\max }}$ do
(13) 根据(1)更新每个节点的 $L_{i,j}^t$ and $R_{i,j}^t$
(14) 更新 $\hat x_1^N$
(15)　　if $R_{i,n + 1}^t > 0$ then ${{\hat x}_i} = 0$
(16)　　else ${{\hat x}_i} = 1$
(17) end while
(18) 提前停止准则：
(19)　　if (17) 成立 then
(20) 迭代终止
(21)　　else $t=t+1$
(22) 输出： $\hat u_1^N = \left( {{{\hat u}_1},{{\hat u}_2}, ··· ,{{\hat u}_N}} \right)$

下载: 导出CSV

| 显示表格

$\sum\limits_{t - X + 1}^t {\sum\limits_{i \in S} {\hat x_i^t} } \oplus \hat x{}_i^{t - 1} = 0$

(17)

4. 性能分析

采用二进制相移键控(Binary Phase Shift Keying, BPSK)调制，在二进制加性高斯白噪声(Binary-Input Additive White Gaussian Noise, BI-AWGN)信道下，对(1024, 512)极化码进行BP算法仿真，其中 $\alpha = 0.9375$ ，最大迭代次数设置为40次。

4.1 译码性能分析

如图5所示，当Q=128, X=2时，所提出的准则在误帧率和误码率上与40次固定迭代(fixed 40), WIB和FBER译码性能相似。如果Q降低到64，则需将X至少增加到3，以弥补性能损失。每当X增加1时，它将至少导致平均迭代次数上升一次。同样可观察到Q值越大，译码性能越好。然而，较高的Q值增加了计算复杂度。因此，可通过仿真选择合适的(X,Q)来权衡硬件复杂度和平均迭代次数。

图 5 不同迭代终止准则的极化码译码性能比较

下载: 全尺寸图片幻灯片

4.2 对迭代次数的分析

在相同的误码率条件下，比较不同迭代终止算法的平均迭代次数。如图6所示，在BER=1.48×10^–5, E_b/N₀=3.5 dB时，与40次固定迭代(fixed 40)的算法相比，G-Matrix准则可以减少87.96%的迭代，本文所提准则在Q=128和X=2时可以减少83.03%的迭代；当 $Q = 1024, X = 1$ 时，与G-Matrix相比，平均迭代次数上升了29.98%；当 $Q = 128, X = 2$ 和 $Q = 64,X = 3$ 时分别与WIB(n_WIB=128, M=6)和FBER(N_F=64, M=6)相比平均迭代次数减少了39.44%和27.67%。当检测位数相等时，所提准则比WIB和FBER需要更少的迭代。

图 6 不同迭代终止准则的平均迭代次数比较

下载: 全尺寸图片幻灯片

4.3 硬件结构

X-tolerance的硬件结构如图7所示。通过硬判决得到 $R_{{S_i},n + 1}^t$ 的符号；异或(XOR)用于计算 $\hat x_{{S_i}}^t \oplus \hat x_{{S_i}}^{t - 1}$ 。在第t次迭代中， ${D_t}$ 是与门(OR)的结果；Comp检测 $\left\{ {{D_t},{D_{t - 1}}, ··· ,{D_{t - X + 1}}} \right\}$ 是否等于0；当 ${E_t}$ 为0时终止译码。

图 7 X-tolerance的硬件结构

下载: 全尺寸图片幻灯片

图8中给出了(8, 4)极化码的BP译码流程。虚线部分表示处理单元的阶段和停止准则之间的数据依赖关系。采用X-tolerance时，在第t次迭代的第3个时钟中，译码器输出 $R_{t,4}^t,i \in \left[ N \right]$ ，然后确定 ${\hat x^t}$ 。接下来， ${\hat x^t}$ 和 ${\hat x^{t - 1}}$ 被发送到相等检测器。第5个时钟，计算X比较器的结果。如果满足X-tolerance，译码器将计算 $L_{i,1}^t,i \in [N]$ ，终止译码，否则继续下一次迭代。对于大多数具有实际长度 $(n \le 10000)$ 的极化码，相等检测器和X比较器的关键路径延迟总是小于PE^[7]。因此，X-tolerance不会增加整个译码器的关键路径延迟。此外，G-Matrix, WIB和FBER只能在得到 ${{\hat u}}$ 后开始早期停止准则的判决，由于译码器和早期停止准则并行运行，在得到早期停止准则的结果前，译码无法终止，这会导致额外的延迟和复杂度。如图8所示，在第t次迭代的第6个时钟中译码器计算输出 $L_{i,4}^t,i \in \left[ N \right]$ ，之后的第7个时钟其他准则才会开始判断是否终止译码，相对于X-tolerance会多出部分时钟译码延迟。当 $n > 2$ 时，X-tolerance不会导致额外的延迟，因为X-tolerance的检测在获得 ${{\hat u}}$ 之前已完成。

图 8 采用X-tolerance的BP译码流程

下载: 全尺寸图片幻灯片

4.4 计算复杂度和资源消耗分析

表1列出了一次迭代停止准则的计算复杂度。对于 ${\hat x_i},i \in S$ , X-tolerance使用Q个XOR操作来计算 $\hat x_i^t \oplus \hat x{}_i^{t - 1}$ 。同时，X-tolerance需要X+Q个OR操作和1个比较操作来检测连续X次迭代是否有变化。虽然X-tolerance消耗更多或操作，但因为没有加法操作，其具有最低的计算复杂度。表2比较了多种早期迭代停止准则在Stratix V 5SGXEA7N2F45C2上的综合结果，统一采用8 bit量化LLR。与其他迭代终止准则相比，X-tolerance可有效降低硬件消耗。在ALM方面，它减少了90%以上的资源消耗。与G-Matrix, WIB和FBER相比，X-tolerance可节省37.6%～97.2%的寄存器。

表 1 早期停止准则的计算复杂度比较

停止准则	G-Matrix	WIB	FBER	X-tolerance
停止准则	G-Matrix	WIB	FBER	Q=N/8	Q=N/16
加法运算	2N	M+2N/8	M+N/16	–	–
比较运算	3N	–	–	–	1
异或(XOR)	NlogN	N/8	N/16	N/8	N/16
或(OR)		–	–	X+N/8	X+N/16

下载: 导出CSV

| 显示表格

表 2 不同早期停止准则的综合结果

停止准则	G-Matrix	WIB	FBER	X-tolerance
停止准则	G-Matrix	WIB	FBER	Q=128 X=2	Q=64 X=3
ALMs	30265	1820	1260	50	27
Registers	3073	330	210	131	68

下载: 导出CSV

| 显示表格

5. 结束语

为了降低极化码置信度传播算法的译码延迟，减少迭代次数，本文提出一种基于码字估值的早期迭代停止准则。通过构造比较空间，只需检测码字估值 ${{\hat x}}$ 中的部分位置，进一步降低计算复杂度，且不会引入额外的延迟。仿真表明，当最大迭代次数为40，信噪比为3.5 dB时，与G-Matrix相比，X-tolerance平均迭代次数上升了29.98%，与WIB, FBER相比，X-tolerance平均迭代次数分别降低39.44%和27.67%。综合结果表明，与G-Matrix, WIB和FBER相比，X-tolerance可节省90%以上的ALM资源。

图 1 基于上下文可靠性度量模型示意图

下载: 全尺寸图片幻灯片

图 2 RSFCM聚类算法流程图

下载: 全尺寸图片幻灯片

图 3 RSFCM对含噪声合成图像的聚类结果(情况1)

下载: 全尺寸图片幻灯片

图 4 RSFCM对含噪声合成图像的聚类结果(情况2)

下载: 全尺寸图片幻灯片

图 5 合成图像的分割结果

下载: 全尺寸图片幻灯片

图 6 实际交通标志图像的分割结果

下载: 全尺寸图片幻灯片

图 7 遥感图像的分割结果

下载: 全尺寸图片幻灯片

表 1 合成图像分割结果的PSNR比较(dB)

算法	FCM	FCM_S1	FCM_S2	FLICM	nr-IT2FCM	FRFCM	RSFCM
PSNR	18.8293	25.8502	25.0842	24.6283	18.6673	24.2498	26.0099

下载: 导出CSV

表 2 不同噪声级别下合成图像分割结果的JS系数比较

算法	FCM	FCM_S1	FCM_S2	FLICM	nr-IT2FCM	FRFCM	RSFCM
Gaussian 8%	74.517	96.436	35.773	96.820	74.011	83.179	97.015
Gaussian 10%	72.729	94.489	37.830	96.954	72.217	72.278	95.673
Gaussian 15%	68.671	90.356	38.300	89.435	68.427	70.465	91.817
Salt &Pepper 8%	95.599	98.627	49.780	97.333	95.599	58.044	99.237
Salt &Pepper 10%	94.519	97.882	96.478	96.289	94.519	85.925	98.743
Salt &Pepper 15%	92.609	96.619	49.689	94.763	92.609	74.500	97.882

下载: 导出CSV

表 3 交通标志图像分割结果的PSNR比较 (dB)

算法	FCM	FCM_S1	FCM_S2	FLICM	nr-IT2FCM	FRFCM	RSFCM
PSNR	21.4062	27.7089	27.0842	24.6283	18.6752	24.2498	29.6100

下载: 导出CSV

表 4 遥感图像分割结果的OA(%)和Kappa系数比较

类别	算法
类别	样本点	FCM	FCM_S1	FCM_S2	FLICM	nr-IT2FCM	FRFCM	RSFCM
水域	16029	95.63	96.56	96.45	92.76	91.15	94.78	97.61
草地	2216	96.79	97.29	97.83	97.96	98.28	58.39	97.79
林地	2449	62.07	72.02	68.31	62.18	43.98	34.46	67.95
裸地	1140	74.82	82.33	80.79	84.14	72.91	59.06	71.74
建筑工地	4333	69.91	72.79	72.63	70.92	72.79	84.35	84.47
OA	总体	87.44	89.78	89.32	86.35	83.52%	82.81	91.57
Kappa	总体	0.7884	0.8279	0.8201	0.7751	0.7263	0.7078	0.8562

下载: 导出CSV

参考文献(21)

[1]	LU Zhenyu, QIU Yunan, and ZHAN Tianming. Neutrosophic C-means clustering with local information and noise distance-based kernel metric image segmentation[J]. Journal of Visual Communication and Image Representation, 2019, 58: 269–276. doi: 10.1016/j.jvcir.2018.11.045
[2]	SOOMRO S, MUNIR A, and CHOI K N. Fuzzy c-means clustering based active contour model driven by edge scaled region information[J]. Expert Systems with Applications, 2019, 120: 387–396. doi: 10.1016/j.eswa.2018.10.052
[3]	施伟锋, 卓金宝, 兰莹. 一种基于属性空间相似性的模糊聚类算法[J]. 电子与信息学报, 2019, 41(11): 2722–2728. doi: 10.11999/JEIT180974 SHI Weifeng, ZHUO Jinbao, and LAN Ying. A novel fuzzy clustering algorithm based on similarity of attribute space[J]. Journal of Electronics &Information Technology, 2019, 41(11): 2722–2728. doi: 10.11999/JEIT180974
[4]	吴志勇, 丁香乾, 许晓伟, 等. 基于深度学习和模糊C均值的心电信号分类方法[J]. 自动化学报, 2018, 44(10): 1913–1920. doi: 10.16383/j.aas.2018.c170417 WU Zhiyong, DING Xiangqian, XU Xiaowei, et al. A method for ECG classification using deep learning and fuzzy C-means[J]. Acta Automatica Sinica, 2018, 44(10): 1913–1920. doi: 10.16383/j.aas.2018.c170417
[5]	BEZDEK J C. Pattern Recognition with Fuzzy Objective Function Algorithms[M]. Boston: Springer, 1981: 203–239. doi: 10.1007/978-1-4757-0450-1.
[6]	ZHANG Tong, SU Guoxi, QING Chunmei, et al. Hierarchical lifelong learning by sharing representations and integrating hypothesis[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2021, 51(12): 1004–1014. doi: 10.1109/TSMC.2018.2884996
[7]	SINGH C and BALA A. A local Zernike moment-based unbiased nonlocal means fuzzy C-Means algorithm for segmentation of brain magnetic resonance images[J]. Expert Systems with Applications, 2019, 118: 625–639. doi: 10.1016/j.eswa.2018.10.023
[8]	费博雯, 邱云飞, 刘万军, 等. 距离决策下的模糊聚类集成模型[J]. 电子与信息学报, 2018, 40(8): 1895–1903. doi: 10.11999/JEIT171065 FEI Bowen, QIU Yunfei, LIU Wanjun, et al. Fuzzy clustering ensemble model based on distance decision[J]. Journal of Electronics &Information Technology, 2018, 40(8): 1895–1903. doi: 10.11999/JEIT171065
[9]	AHMED M N, YAMANY S M, MOHAMED N, et al. A modified fuzzy c-means algorithm for bias field estimation and segmentation of MRI data[J]. IEEE Transactions on Medical Imaging, 2002, 21(3): 193–199. doi: 10.1109/42.996338
[10]	CHEN Songcan and ZHANG Daoqiang. Robust image segmentation using FCM with spatial constraints based on new kernel-induced distance measure[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) , 2004, 34(4): 1907–1916. doi: 10.1109/TSMCB.2004.831165
[11]	ZHANG Hua, WANG Qunming, SHI Wenzhong, et al. A novel adaptive fuzzy local information C-means clustering algorithm for remotely sensed imagery classification[J]. IEEE Transactions on Geoscience and Remote Sensing, 2017, 55(9): 5057–5068. doi: 10.1109/TGRS.2017.2702061
[12]	KRINIDIS S and CHATZIS V. A robust fuzzy local information C-means clustering algorithm[J]. IEEE Transactions on Image Processing, 2010, 19(5): 1328–1337. doi: 10.1109/TIP.2010.2040763
[13]	LEI Tao, JIA Xiaohong, ZHANG Yanning, et al. Significantly fast and robust fuzzy C-means clustering algorithm based on morphological reconstruction and membership filtering[J]. IEEE Transactions on Fuzzy Systems, 2018, 26(5): 3027–3041. doi: 10.1109/TFUZZ.2018.2796074
[14]	XING Haihua, HE Hui, HU Dan, et al. An interval Type-2 fuzzy sets generation method for remote sensing imagery classification[J]. Computers & Geosciences, 2019, 133: 104287. doi: 10.1016/j.cageo.2019.06.008
[15]	CHEN C L P, ZHANG Tong, CHEN Long, et al. I-ching divination evolutionary algorithm and its convergence analysis[J]. IEEE Transactions on Cybernetics, 2017, 47(1): 2–13. doi: 10.1109/TCYB.2015.2512286
[16]	ZHANG Tong, CHEN C L P, CHEN Long, et al. Design of highly nonlinear substitution boxes based on I-ching operators[J]. IEEE Transactions on Cybernetics, 2018, 48(12): 3349–3358. doi: 10.1109/TCYB.2018.2846186
[17]	NEWTON I. Mathematical Principles of Natural Philosophy[M]. London: Benjamin Motte Publishing, 1687.
[18]	徐超, 詹天明, 孔令成, 等. 基于学生t分布的鲁棒分层模糊算法及其在图像分割中的应用[J]. 电子学报, 2017, 45(7): 1695–1700. doi: 10.3969/j.issn.0372-2112.2017.07.020 XU Chao, ZHAN Tianming, KONG Lingcheng, et al. A robust hierarchical fuzzy algorithm with student’s t-distribution for image segmentation application[J]. Acta Electronica Sinica, 2017, 45(7): 1695–1700. doi: 10.3969/j.issn.0372-2112.2017.07.020
[19]	赵凤, 张咪咪, 刘汉强. 区域信息驱动的多目标进化半监督模糊聚类图像分割算法[J]. 电子与信息学报, 2019, 41(5): 1106–1113. doi: 10.12000/JRIT180605 ZHAO Feng, ZHANG Mimi, and LIU Hanqiang. Multi-objective evolutionary semi-supervised fuzzy clustering image segmentation motivated by region information[J]. Journal of Electronics &Information Technology, 2019, 41(5): 1106–1113. doi: 10.12000/JRIT180605
[20]	CAO Changyu, ZHENG Jiachun, HUANG Yiqi, et al. Investigation of a promoted you only look once algorithm and its application in traffic flow monitoring[J]. Applied Sciences, 2019, 9(17): 3619. doi: 10.3390/app9173619
[21]	ZHANG Lefei, ZHANG Liangpei, DU Bo, et al. Hyperspectral image unsupervised classification by robust manifold matrix factorization[J]. Information Sciences, 2019, 485: 154–169. doi: 10.1016/j.ins.2019.02.008

施引文献

期刊类型引用(3)

1.	高珍，张国伟. 改进区块链的移动网络敏感数据防篡改仿真. 计算机仿真. 2023(03): 409-412+430 . 百度学术
2.	文豪，曹阳，党宇超. 无线光通信下极化码DNN-NOMS译码方法研究. 红外与激光工程. 2022(05): 262-272 . 百度学术
3.	袁建国，张瑞，张丰果，李志伟，黄胜. CRC辅助PC-polar码的新颖编码算法. 重庆邮电大学学报(自然科学版). 2022(06): 929-934 . 百度学术

其他类型引用(4)

资源附件(0)

访问统计

图(7) / 表(4)

计量

文章访问数: 1227
HTML全文浏览量: 566
PDF下载量: 120
被引次数: 7

1. 引言
2. 基本理论
2.1 极化码
2.2 BP译码算法
3. 提出的早期迭代停止准则
3.1 X-tolerance早期迭代停止准则
3.2 比较空间的构造
4. 性能分析
4.1 译码性能分析
4.2 对迭代次数的分析
4.3 硬件结构
4.4 计算复杂度和资源消耗分析
5. 结束语

姓名
邮箱
手机号码
标题
留言内容
验证码

留言板

基于上下文模糊C均值聚类的图像分割算法

doi: 10.11999/JEIT200263

通讯作者:
徐金东　jindong.xu@nlpr.ia.ac.cn

计量

Image Segmentation Algorithm Based on Context Fuzzy C-Means Clustering

1. 引言

2. 基本理论

2.1 极化码

2.2 BP译码算法

3. 提出的早期迭代停止准则

3.1 X-tolerance早期迭代停止准则

3.2 比较空间的构造

4. 性能分析

4.1 译码性能分析

4.2 对迭代次数的分析

4.3 硬件结构

4.4 计算复杂度和资源消耗分析

5. 结束语

期刊类型引用(3)

其他类型引用(4)

计量

目录

1. 引言

2. 基本理论

2.1 极化码

2.2 BP译码算法

3. 提出的早期迭代停止准则

3.1 X-tolerance早期迭代停止准则

3.2 比较空间的构造

4. 性能分析

4.1 译码性能分析

4.2 对迭代次数的分析

4.3 硬件结构

4.4 计算复杂度和资源消耗分析

5. 结束语

留言板

基于上下文模糊C均值聚类的图像分割算法

doi: 10.11999/JEIT200263

通讯作者: 徐金东 jindong.xu@nlpr.ia.ac.cn

计量

出版历程

Image Segmentation Algorithm Based on Context Fuzzy C-Means Clustering

1. 引言

2. 基本理论

2.1 极化码

2.2 BP译码算法

3. 提出的早期迭代停止准则

3.1 X-tolerance早期迭代停止准则

3.2 比较空间的构造

4. 性能分析

4.1 译码性能分析

4.2 对迭代次数的分析

4.3 硬件结构

4.4 计算复杂度和资源消耗分析

5. 结束语

期刊类型引用(3)

其他类型引用(4)

计量

出版历程

目录

1. 引言

2. 基本理论

2.1 极化码

2.2 BP译码算法

3. 提出的早期迭代停止准则

3.1 X-tolerance早期迭代停止准则

3.2 比较空间的构造

4. 性能分析

4.1 译码性能分析

4.2 对迭代次数的分析

4.3 硬件结构

4.4 计算复杂度和资源消耗分析

5. 结束语

通讯作者:
徐金东　jindong.xu@nlpr.ia.ac.cn