SLICAP图像分割C++实现
代码仓库
https://github.com/SingleZombie/SLICAP-image-segmentation-cpp
需求分析
输入一幅图像，输入图像中每个像素的分类。比如产生以下的效果：
由于我的软件工程天赋过于高超，加上用户、产品经理、程序员都是我自己，因此分析阶段的功能建模部分就略过了。
技能学习
算法原理
概要设计
学完算法，准备开始写程序后，我的脑中立刻就浮现了以下的程序结构图：
和以往一样，主函数分成预处理、执行操作、输出处理三个模块。执行操作可以分成生成超像素和利用超像素进行图像分割，在用超像素模块分割模块中会利用到AP聚类算法。
这次程序的两个主要模块非常清晰：用SLIC生成超像素的模块和用AP聚类的模块。两个模块独立性高，且具有先后关系。应该逐模块进行开发，每个模块开发完成后进行单元测试，确认模块工作正常后再进行后续的开发。同时，由于项目时间十分紧张，我还需要采用敏捷开发，不浪费一分一秒在无谓的写文档上。
详细设计
虽然划分模块用的是结构化设计的思想，但我还是喜欢设计类并进行面向对象编程。
超像素生成模块
时间紧张，不画UML图了，直接用文字表达思想，之后直接写代码。
首先要有一个SuperPixels类。该类用于在超像素生成和超像素图像分割模块间传递信息。该类存了一个图像矩阵、一个存储每个像素所述超像素类的数组、一个存储每个超像素信息（平均颜色向量）的数组。外部操作有根据图像矩阵创建新对象。由于算法对数据操作较多，该类可以被看成一个“结构”，标记数组、超像素信息是透明的。超像素信息用SuperPixel结构表示，该结构就是一个五维量（颜色和坐标）加一个像素数。
SuperPixelsGenerator提供生成超像素的算法，与一个SuperPixels关联，被处理模块调用。该类要存储一个图像矩阵，超像素期望的个数superPixelCount, 颜色距离参数colorDisM，最大迭代次数maxIterTime，计算一个期望距离expectedDis。我按算法流程顺序来设计每一个部分。设计时参考了这篇博客。
首先我需要一个RGB和LAB互相转换的函数，供SuperPixelsGenerator调用。这个函数应该单独写在一个模块中。上面那篇博客的作者还写了一篇RGB转LAB的博客。但由于自己实现比较复杂，我打算直接用OpenCV自带的方法转换。
std::vector SuperPixelsGenerator::computeGradient()，计算图像每一点的梯度。
void SuperPixelsGenerator::initSuperPixelsCenter()调用computeGradient()来计算初始的超像素中心。
void SuperPixelsGenerator::updateEachPixel()更新每个像素的标记（类别）。
void SuperPixelsGenerator::updateSuperPixelsCenter()更新超像素中心为平均值。
void SuperPixelsGenerator::enforceConnectivity()对最终的标记进行强制连续性的处理。
超像素聚类模块
我先完成AP算法模块的设计，再完成调用AP算法模块的设计。
AP算法应该可以对任何形式的数据进行。因此，AP算法应该写成一个模板函数。
AP算法接收一个数据间相似二元关系的矩阵，输出一个标记表，表示每一个数据的数据中心是哪个数据。唯一一个可调参数是更新率$\lambda$。我本来想写一个和STL风格类似的模板函数，结果发现我忘记了怎么声明一个参数的指针或迭代器参数。再进一步思考，不管什么类型的数据，都可以用一个整数索引来表示，相似度可以直接存在一个数组里。那么我就不需要使用模板函数了。最终，函数声明写成了这样：
1 | std::vector<int> apClustering(const std::vector<int>& similarity, unsigned dataCount,double lambda = 0.5) |
再思考一下程序设计细节。对于每对数据，要计算除某点之外的某值的最大值，这个可以通过记录每对点某值的最大值和次大值实现（打ACM做树形dp的时候实现了好多遍了）。另外，每对数据间还需要一个除了某两点以外的累计值，这个直接存一个累计值，用的时候减掉那两个不要的值就可以了。
这个算法直接写在一个函数里没什么问题。要让代码模块性更好的话，可以把$r,a$矩阵的更新分别写一个函数。
超像素聚类算法单独写一个类。该类初始化时接收算法权值参数。调用该类的clustering函数可以对一个超像素集合进行聚类，直接返回AP聚类的标记数组。该函数调用一个函数计算相似度，在调用AP算法返回结果。
1 | SuperPixelClusteringAlgorithm::SuperPixelClusteringAlgorithm(int wl = 3, int wa = 10, int wb = 10); |
程序设计及性能优化
由于时间紧、算法对数据操作量复杂而软件流程复杂性低，本次程序我写得十分“暴力”，很多地方都没有进行模块化、封装。
超像素生成模块
我用四个半小时的实际工作时间完成了看似正确的超像素生成模块。在三种参数下的生成结果如下：（鼠标放到图片上可以看到参数信息）
但是，程序的性能非常差。明明我已经有意识地降低时间和空间使用程度，但程序依然要20多秒才能完成4次迭代的生成算法（生成上面的第三幅图）。
凭借着上次软件工程项目的经验，我使用VS的性能分析工具来改进程序，结果如下：
大部分时间都是画在迭代函数上。令我惊讶的是，几乎所有时间都浪费在了这个计算五维量距离的函数上。
仔细看了一遍网上实现代码和论文中的算法，发现我对算法的理解错了！每次是搜索超像素中心附近的$2S\times2S$个像素，不是对每个像素进行搜索。我立马修改了上一篇博客和代码。
这下算法的结果也正常了，性能也正常了。程序1.7秒可以完成4次迭代、500个超像素、图片大小510X385的超像素生成算法。哪怕不经过任何优化，这个性能也能满足一般的要求。调试的时候不会浪费太多时间，做为作业提交也十分足够。有机会的话，我还是会优化一下代码。
在算法正确的基础上，我又做了3次实验：
目前开发调试外加吹牛的时间共计五个半小时。
超像素聚类模块
这个模块实现起来并不复杂，但我还是浪费了很多时间在调试上。
一开始，我发现我没有正确理解AP算法，没有对相似度矩阵对角线上的值进行特殊处理。我把对角线的值设为平均值后，还是发现聚类算法只会把每一块的数据中心划成自己。由于图片不好调试，我构造了6个点相似度矩阵进行算法调试，其中每三个点有一个很明确的数据中心。算法迟迟得不到正确结果。我浪费了大量时间在代码比对上。突然，我一气之下修改了AP算法的循环停止条件，让它迭代进行100次，结果竟然正常了。我发现在AP算法迭代的过程中，每个点的数据中心可能会固定一段时间，但实际上两个矩阵的值还没有收敛。我把循环停止条件改成了数据中心连续5次迭代都不变才解决AP算法的收敛问题。可是，我把数据从6个点换成了原图像，算法还是进行失败。我又偶然间把计算相似度矩阵对角线的公式去掉了SLICAP论文中提到的比例系数，算法竟然正常工作了。不知道是不是我没有认真看那篇论文，我觉得那篇论文太坑人了，加上比例系数后算法完全工作不了，我还以为是自己写错了。
和设计的一样SuperPixelClusteringAlgorithm类只负责相似度计算和算法调用，AP算法的细节在APClustering中。
程序设计真的没什么可以说的。假设有$N$个数据，迭代$I$次，那么AP算法时间复杂度是$O(IN^2)$，空间复杂度$O(N^2)$。稍微优化一下求最大值和求和的过程就能把看似$O(N^3)$的单次迭代变成$O(N^2)$。
图片显示模块
我打算显示3幅图片：超像素分割结果、超像素聚类结果、图片分割处理结果。
理论上需要一个模块来专门处理输出图片的处理。由于时间不够，我也很懒，只把超像素聚类结果生成函数放到了单独的文件里。超像素分割结果图像放到了超像素类里，图像分割处理结果直接放到了main函数里。这样写程序是非常不好的，我会在之后的版本中修改。
命令行参数模块
理论上，所有的参数都是可以调整的，而且程序可以在不关闭的情况下保存之前的参数设定，循环处理图片。做为一个完整的软件来说，应该提供这些丰富的功能。但我暂时没有写，我写的东西暂时只能算一个程序。
最终结果
（我也忘了当时参数是什么了，但这绝对是程序生成出来的）
感想
我觉得自己很帅。在一天之内不仅实现了图像分割程序的功能，而且凭借着强大的心理抗挫折能力，没有被烦人的BUG击溃，最终站到了胜利的高点。当我回首过去，看着一条条充满荆棘的路，看着我踩的一个个坑，我感到一丝心酸；但当我俯视大地，看着程序能够产生较好的图像分割结果时，我又感到苦尽甘来，心旷神怡。
更新记录
20.2.1
- 上传博客