【算法解析】抖音分割特效算法复现尝试
点击上方"蓝色小字"关注我呀
1，前言
大家好呀，好久没写技术文了，一个是最近在秋招就光是刷题了，另一个就是水平有限，还做不到持续输出，菜... ...
另外最近接了几篇广告，2018年之后的公众号都没有留言评论功能了，导致沟通非常受限制，想要开通就需要花4K块钱给中介公司。所以希望大家多多支持一下，赶紧攒够钱然后去开评论。
本文解析一个抖音算法，我试着想复现一下，不过目前还比较失败。先将现在的效果写一篇文章，希望大家可以有所收获。
2，抖音算法效果
原特效算法视频如上，真正咋实现的我也不知道，只能根据它的操作来猜了。
首先视频中，需要选取颜色，该颜色作为分割的依据以及最后分割效果的颜色。
然后需要用画刷人工粗略的划分区域。
所以算法的输入就是人工预分割好的这个mask。包括颜色以及像素位置两部分。
不过我目前写的kmeans算法只用到了选取的颜色。
当前算法实现思路：
通过QT进行了人工分割之后，将各个区域的颜色传递给Kmeans算法，算法根据输入的K个颜色进行迭代，每次迭代遍历所有像素并计算该像素最为接近的颜色区域，然后将该像素分配给该颜色区域。
所以整个算法并没有应用到人工预分割时给每个像素分配的区域，只用到了选取的几个颜色。
3，QT界面以及算法效果演示
为了复现抖音视频中的人工预分割的操作，我写了一个简单的QT界面，操作过程以及算法效果如下视频：
QT界面包括一个菜单栏，主要就是读图与保存图片。
一个工具栏，包括取色器，画笔，生成预览，撤销操作。
一个状态栏，状态栏的颜色可以根据取色器的颜色而变化，并进行一些提示信息。
4，Kmeans算法介绍
本次实验算法就是根据以前写的Kmeans进行了一点小小的改写。
Kmeans之前【手撕算法】系列写过一篇：
kmeans算法接口：
KMean(Mat srcImage_, Mat& dstImage_, vector<Vec3b> colors_,int clusters_num, int iterations)分别是输入图像，输出图像，人工选取的颜色们，以及颜色数量（Kmeans的K值），迭代次数。
算法第一步：
读取人工颜色作为分割聚类的种子点。
//簇的一个容器，来跟踪图像的变化
vector<Cluster> clusters;
//【1】处理color种子点
int rand_x, rand_y;
Vec3b pixel;
for (int i = 0; i < clusters_num; i++) {
rand_x = rand() % srcImage_.rows;
rand_y = rand() % srcImage_.cols;
pixel = colors_.at(i);
clusters.push_back(Cluster(pixel, rand_x, rand_y));
}算法第二，三步：
开启迭代，每次迭代遍历所有像素，并根据颜色距离进行分类。
//【2】迭代
//K - Means的开始:我们将算法的所有逻辑放入一个for循环中
//这是因为，我们可以进行固定次数的迭代:如果过程中算法收敛，它的质心不再变化，我们则打破for
for (int i = 0; i < iterations; i++) {
//在每次迭代中，我们重新初始化一些变量，例如距离和索引，这将帮助我们在每次迭代中找到集群最小阈值和索引
float distance;
int index;
//【3】遍历图像每个像素，以选择它们属于哪个集群 :
for (int x = 0; x < srcImage_.rows; x++) {
for (int y = 0; y < srcImage_.cols; y++) {
//现在，对于一个普通的(x, y)像素，分析这个像素属于哪个集群
//我们遍历k个簇，寻找与该像素距离最近的簇
float min_dist = FLT_MAX;
for (int k = 0; k < clusters.size(); k++) {
//getting the distance
distance = norm(srcImage_.at<Vec3b>(x, y), clusters.at(k).centroid);
//check
if (distance < min_dist) {
//update the index and the minimum distance found
index = k;
min_dist = distance;
}
}
//将像素添加到其簇中
clusters.at(index).add_pixel(srcImage_.at<Vec3b>(x, y), x, y);
}
}算法第四步：
进行均值漂移，并判断是否达到迭代结束条件。
bool changed = false;
for (int k = 0; k < clusters.size(); k++) {
//获取当前质心作为旧的质心
Vec3b old_centroid = clusters.at(k).centroid;
//计算新的质心
clusters.at(k).calculate_center();
//check if the new centroid differs by a significative amount to the old one
if (norm(old_centroid, clusters.at(k).centroid) > 10) {
changed = true;
}
}
//如果他们都没有改变
if (!changed || i + 1 == iterations) {
//break the cycle and go to build the destination image with the cluster
break;
iterations = i;
}
else {
//如果改变了，至少需要进行另一次迭代以获得收敛，重置簇但保持新计算的质心
for (int k = 0; k < clusters.size(); k++) {
clusters.at(k).clear();
}
}
}算法第五步：
完成分割，根据结果重新构建结果图。
Mat showImage = Mat(srcImage_.size(),CV_8UC3);
for (quint64 k = 0; k < clusters.size(); k++) {//遍历每个簇
for (quint64 p = 0; p < clusters.at(k).pixel_num; p++)//遍历簇中所有像素
{
vector<Point> pix = clusters.at(k).pixels;
showImage.at<Vec3b>(pix.at(p).x, pix.at(p).y) = colors_.at(k);b(0,255,0);
}
}
showImage.copyTo(dstImage_);最终的算法效果：
5，算法总结
其实算法效果还是很拉胯的，将整幅图分割为了固定的几个颜色，但没有达到成块的类似语义分割的效果。
目前打算改进的就是将人工预分割的像素位置分类考虑进算法，并优化计算距离的方法。
整篇文所展示的效果花了我五天时间。。。后续有进展再发文和大家交流。
大家有思路和建议的可以加我微信备注加群，我们在群里讨论哦。
THE END
整个QT项目的代码放百度网盘了：
链接：https://pan.baidu.com/s/1XeU7s0SATfRTR4wGFCQ-OQ
提取码：aatg感谢大家的支持！