基于复杂网络与核模糊C均值的图像分割算法研究

### 基于复杂网络与核模糊C均值的图像分割算法研究 #### 1. CAPTCHA分割算法背景与研究动机 CAPTCHA（全自动区分计算机和人类的公开图灵测试）是一种广泛应用的安全技术，常用于免费电子邮件和论坛账户注册，以防止不良或恶意的计算机机器人程序注册和垃圾邮件。目前，基于文本的CAPTCHA方案最为常见，通常要求用户识别连接和扭曲的字符。然而，CAPTCHA的分割比识别更具挑战性，因为虽然机器学习算法能有效解决一般的识别问题，但目前尚无通用的有效算法来解决所有CAPTCHA的分割问题。 已有多种CAPTCHA分割机制被提出，如Mori和Malik用复杂的目标识别算法破解EZ - Gimpy和Gimpy CAPTCHA；Chellapilla等人使用机器学习算法攻击早期的CAPTCHA；Huang等人使用基于投影的分割算法破解MSN和YAHOO CAPTCHA等。但当遇到连接和扭曲字符的CAPTCHA时，这些算法效果不佳。因此，本文提出了一种基于复杂网络的社区划分模型（Community Divided Model）分割算法来处理此类问题。 #### 2. 动机与数据库创建 近年来，复杂网络成为研究热点，社区结构是其重要属性。Girvan和Newman强调了社区结构的特性，即网络节点紧密连接成组，组间连接较松散，且该方法在计算机生成和真实世界的图上表现出高敏感性和可靠性。 对于CAPTCHA，其具有固定长度，即已知社区数量，每个字符内部紧密连接，而相邻字符间连接松散，且相邻连接和扭曲的字符通常在核心区域中部接触。基于此，本文修改了Girvan和Newman算法，提出社区划分模型用于分割连接和扭曲的字符。 为确定该模型的有效性，随机收集了来自Authorize、360buy、Tianya、Windows Live和Taobao等网站用于账户注册的数百个CAPTCHA。这些CAPTCHA的特点包括：部分背景有不同颜色的浅色斑点，部分字符倾斜、挤压、弯曲、上下移动、连接或扭曲，但都包含数字和大小写字母，且字符长度固定。 #### 3. 提出的分割算法 ##### 3.1 社区划分模型 连接图 $G(V, E)$ 由顶点集 $V(G)$ 和边集 $E(G)$ 组成。顶点 $v_i$ 和 $v_j$ 是 $V$ 的元素，它们的边权重 $e_{ij}$ 是 $E$ 的元素，初始值都为0。邻接表 $L[i]$（$i = 1…n$）是 $v_i$ 邻居的元素，队列 $Q[k]$ 是第 $k$ 个非连接节点组的元素，$N$ 是社区数量。由于每个CAPTCHA有固定长度，识别社区的算法步骤如下： 1. 计算所有顶点的邻接表：使用细化模式上每个前景像素的八个邻居搜索整个图像。如果 $v_j$ 是 $v_i$ 的八个邻居节点之一（$j≠i$），则 $v_j$ 是 $v_i$ 的邻边，并将其放入 $L[i]$。 2. 计算非连接节点组的数量：根据邻接表 $L$，计算所有连接节点组并添加到 $Q$ 中，如果非连接节点组的数量等于 $N$，则系统停止。 3. 计算所有边的介数得分：使用深度优先搜索（DFS）算法计算所有顶点之间的最短路径。如果边 $e_{ij}$ 被经过一次，其得分加1。然后计算其中最高的介数得分。 4. 删除得分最高的边：删除最高介数得分的边 $e_{ij}$ 并更新边集 $E(G)$，同时删除列表 $L[i]$ 中的连接边。 5. 从步骤2开始重复，重新计算受删除影响的所有边的介数得分，直到所有边都被删除，系统分解为 $N$ 个非连接节点组。 ##### 3.2 预处理 二值化是第一步也是最重要的一步，分割的效果取决于二值图像的质量。通过标准阈值法将原始图像转换为二值图像，即颜色值高于预定阈值的像素转换为黑色，低于阈值的转换为白色。有时图像存在噪声点，扫描整个图像，若连通区域的像素数大于阈值，则将其视为噪声并去除。为减少处理时间，使用Zhang算法对图像进行细化。 ##### 3.3 分割 使用提出的社区划分模型分割字符。如果字符相连，绘制红线表示应删除的最高得分边，从而得到分割结果。对于Authorize和360buy的CAPTCHA，大多字符不相连且有四到五个社区，可直接得到分割结果；对于Tianya、Windows Live和Taobao的CAPTCHA，字符相连，绘制红线表示删除点。实验结果表明