图像描边

image border

最近项目中搞了个图像描边的需求,常见的美图工具App都有类似的功能,典型的如美图秀秀,一开始觉得应该不太复杂,正常评估时间,实际做的时候,发现问题比想象中的复杂多了,结果项目不得不延期 😭,所以有必要搞篇文章来总结下教训。

先说整体的流程: 1、原图 -> 2、抠图 -> 3、边缘检测 -> 4、绘制边缘 -> 5、结果导出

这个流程还是很容易想到,但是除了最后一步相对来说容易点,2、3、4都是一路坑 😞

image matting

首先是抠图,就是这样的

跟我们这边的算法同学对接,爬虫收集图像、标注、模型训练 一套组合下来,效果不理想,生产环境不可用,第一步就卡住了 😞

为了赶项目周期,最后使用了阿里云的方案,这里就不多说了,算法同学持续优化模型,待成熟之后替换阿里云。

Edge detection

这一步相对来说是最复杂的,这里遇到的问题也是最大,耗时最久

最初的方案大致是这样的:抠图结果->采样缩放图像->遍历图像bitmap取满足条件的点,条件简单的理解就是点周围3x3范围的点像素值取平均值。
为什么要检测边缘,是因为要做虚线描边,获取连续的边缘点之后然后在画布上连接点画出来。

代码大概是这样的…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
+ (NSArray *)imageFindContours:(UIImage *)image {
NSMutableArray *points = [[NSMutableArray array] init];
UIImage *newImage = [image mediumResolution:CGSizeMake(30, 30)];

CFDataRef imageData = CGDataProviderCopyData(CGImageGetDataProvider(newImage.CGImage));
const uint8_t *data = CFDataGetBytePtr(imageData);

int w = newImage.size.width;
int h = newImage.size.height;
unsigned char *bitmap = malloc(w * h * 4);
memcpy(bitmap, data, w * h * 4);

CGFloat leftmost = 1;
CGFloat rightmost = 0;
for (int i = 1; i < h - 1; i += 2) {
for (int j = 1; j < w - 1; j += 2) {
unsigned int left = [WDImageBorder valueForBitmap:data stride:w position:CGPointMake(i, j) offsets:CGSizeMake(-1, 0)];
unsigned int right = [WDImageBorder valueForBitmap:data stride:w position:CGPointMake(i, j) offsets:CGSizeMake(1, 0)];
unsigned int up = [WDImageBorder valueForBitmap:data stride:w position:CGPointMake(i, j) offsets:CGSizeMake(0, -1)];
unsigned int down = [WDImageBorder valueForBitmap:data stride:w position:CGPointMake(i, j) offsets:CGSizeMake(0, 1)];
unsigned int leftUp = [WDImageBorder valueForBitmap:data stride:w position:CGPointMake(i, j) offsets:CGSizeMake(-1, -1)];
unsigned int rightUp = [WDImageBorder valueForBitmap:data stride:w position:CGPointMake(i, j) offsets:CGSizeMake(1, -1)];
unsigned int leftDown = [WDImageBorder valueForBitmap:data stride:w position:CGPointMake(i, j) offsets:CGSizeMake(-1, 1)];
unsigned int rightDown = [WDImageBorder valueForBitmap:data stride:w position:CGPointMake(i, j) offsets:CGSizeMake(1, 1)];
unsigned int center = [WDImageBorder valueForBitmap:data stride:w position:CGPointMake(i, j) offsets:CGSizeMake(0, 0)];
unsigned int avg = (left + right + up + down + leftUp + rightUp + leftDown + rightDown + center) / 9;

int offset = i * w + j;
if ((avg >= (255. * 0.4) && avg <= (255. * 0.9)) && center > 65) {
bitmap[offset * 4] = 255;
bitmap[offset * 4 + 1] = 0;
bitmap[offset * 4 + 2] = 0;
bitmap[offset * 4 + 3] = 255;

CGFloat scale = 1.15;
CGFloat x = (CGFloat)((((float) j / w) - 0.5) * scale + 0.5);
CGFloat y = (CGFloat)((((float) i / h) - 0.5) * scale + 0.5);
CGPoint point = CGPointMake(x, y);
[points addObject:[NSValue valueWithCGPoint:point]];

if (x <= leftmost) leftmost = x;
if (x >= rightmost) rightmost = x;
}
}
}
...
}

这个有个致命的问题,就是找到点之后,但是没办法有序的连起来,也试过一些方案,但是图像的边缘情况太复杂了,总是有问题,这里就不多说了。

接下来就需求其他的方案,大名鼎鼎的OpenCV出场了,参考官方文档,编译产物,接入app 调试下来就能获取正确的结果了,这里就不多说了,直接看下代码,对应的节点有注释说明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
+ (NSArray *)findContours:(UIImage *)image {

Mat src;
Mat src_gray;

src = [self cvMatFromUIImage:image];
cvtColor(src, src_gray, COLOR_BGR2GRAY);

//UIImage *grayImg = [self UIImageFromCVMat:src_gray];

blur(src_gray, src_gray, cv::Size(3, 3));

//UIImage *blurgrayImg = [self UIImageFromCVMat:src_gray];

/// 利用阈值二值化
threshold(src_gray,src_gray,128,255,cv::THRESH_BINARY);
/// 用Canny算子检测边缘
//Canny(src_gray, src_gray, 128, 255 , 3);

//UIImage *canny_outputImg = [self UIImageFromCVMat:src_gray];

vector<vector<cv::Point> > contours;
vector<Vec4i> hierarchy;


/// 寻找轮廓
findContours(src_gray, contours, hierarchy, RETR_EXTERNAL, CHAIN_APPROX_SIMPLE, cv::Point(0, 0));

/// 绘出轮廓
Mat drawing = Mat::zeros(src_gray.size(), CV_8UC3);
for (int i = 0; i < contours.size(); i++) {
Scalar color = Scalar(255, 255, 255);
drawContours(drawing, contours, i, color, 1, 8, hierarchy, 0, cv::Point());
}
//UIImage *contoursImg = [self UIImageFromCVMat:drawing];

NSMutableArray *array = [NSMutableArray arrayWithCapacity:contours.size()];

for (int i = 0; i < contours.size(); i++) {

if (hierarchy[i][3] >= 0 || hierarchy[i][2] >= 0) {
continue;
}

vector<cv::Point> vect = contours[i];

std::vector<cv::Point>::const_iterator it; // declare a read-only iterator
it = vect.cbegin(); // assign it to the start of the vector

while (it != vect.cend()) { // while it hasn't reach the end
//std::cout << it->x <<' '<< it->y <<' '; // print the value of the element it points to

[array addObject:@(CGPointMake(it->x / image.size.width, it->y / image.size.height))];
++it; // and iterate to the next element
}
}

return @[array];
}

这个方案唯一的缺陷就是需要引入OpenCV静态库,增加包大小,也想过咱只用到了边缘检测,其他的牛逼功能暂时也用不到,裁剪下只保留需要的类是不是就可以,但是大致翻了下,牵扯的太多,最终放弃了, 最后也并没有使用OpenCV的方案。

因为发现了更轻量级的方案,Suzuki边缘检测算法,后面也了解该算法其实就是OpenCV内部的一种边缘检测方案。 恰好Android同学找到了一个开源库,java版本的Suzuki边缘检测算法。
代码拉下来结合算法文档来回撸几遍,大致能理解了,android直接java拖进去用上,ios翻译成OC,也不复杂,因为算法核心方法也不过几十行代码,就算不理解,硬翻也能翻译过来。

贴一下翻译成OC的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
+ (NSArray *)findContours:(UIImage *)img threshold:(CGFloat)threshold {
img = [self blurImage:img blur:0.2];

/// 记录原图尺寸
int ow = (int) img.size.width;

int w = ow;
int h = (int) img.size.height;

/// 考虑字节对齐 w 要重新计算

CFDataRef imageData = CGDataProviderCopyData(CGImageGetDataProvider(img.CGImage));
const uint8_t *data = CFDataGetBytePtr(imageData);

w = (int) CFDataGetLength(imageData) / (h*4);

char *F = malloc((size_t) CFDataGetLength(imageData)/4);

/// 二值化处理
threshold *= 255.f;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (data[(i * w + j) * 4] > threshold) {
F[i * w + j] = 1;
} else {
F[i * w + j] = 0;
}
}
}

NSMutableArray<Contour *> *contours = [NSMutableArray array];

for (int i = 1; i < h - 1; i++) {
F[i * w] = 0;
F[i * w + w - 1] = 0;
}
for (int i = 0; i < w; i++) {
F[i] = 0;
F[w * h - 1 - i] = 0;
}

int nbd = 1;
int lnbd = 1;

for (int i = 1; i < h - 1; i++) {
lnbd = 1;

for (int j = 1; j < w - 1; j++) {

int i2 = 0, j2 = 0;
if (F[i * w + j] == 0) {
continue;
}
//(a) If fij = 1 and fi, j-1 = 0, then decide that the pixel
//(i, j) is the border following starting point of an outer
//border, increment NBD, and (i2, j2) <- (i, j - 1).
if (F[i * w + j] == 1 && F[i * w + (j - 1)] == 0) {
nbd++;
i2 = i;
j2 = j - 1;

//(b) Else if fij >= 1 and fi,j+1 = 0, then decide that the
//pixel (i, j) is the border following starting point of a
//hole border, increment NBD, (i2, j2) <- (i, j + 1), and
//LNBD + fij in case fij > 1.
} else if (F[i * w + j] >= 1 && F[i * w + j + 1] == 0) {
nbd++;
i2 = i;
j2 = j + 1;
if (F[i * w + j] > 1) {
lnbd = F[i * w + j];
}
} else {
//(c) Otherwise, go to (4).
//(4) If fij != 1, then LNBD <- |fij| and resume the raster
//scan from pixel (i,j+1). The algorithm terminates when the
//scan reaches the lower right corner of the picture
if (F[i * w + j] != 1) {
lnbd = ABS(F[i * w + j]);
}
continue;

}
//(2) Depending on the types of the newly found border
//and the border with the sequential number LNBD
//(i.e., the last border met on the current row),
//decide the parent of the current border as shown in Table 1.
// TABLE 1
// Decision Rule for the Parent Border of the Newly Found Border B
// ----------------------------------------------------------------
// Type of border B'
// \ with the sequential
// \ number LNBD
// Type of B \ Outer border Hole border
// ---------------------------------------------------------------
// Outer border The parent border The border B'
// of the border B'
//
// Hole border The border B' The parent border
// of the border B'
// ----------------------------------------------------------------

Contour *B = [Contour new];
B.points = [NSMutableArray array];
[B.points addObject:[NSValue valueWithCGPoint:CGPointMake(j * 1.f / ow, i * 1.f / h)]];
B.isHole = (j2 == (j + 1));
B.idx = nbd;
[contours addObject:B];

Contour *B0 = [Contour new];
for (int c = 0; c < contours.count; c++) {
if (contours[c].idx == lnbd) {
B0 = contours[c];
break;
}
}
if (B0.isHole) {
if (B.isHole) {
B.parentIdx = B0.parentIdx;
} else {
B.parentIdx = lnbd;
}
} else {
if (B.isHole) {
B.parentIdx = lnbd;
} else {
B.parentIdx = B0.parentIdx;
}
}

//(3) From the starting point (i, j), follow the detected border:
//this is done by the following substeps (3.1) through (3.5).

//(3.1) Starting from (i2, j2), look around clockwise the pixels
//in the neigh- borhood of (i, j) and tind a nonzero pixel.
//Let (i1, j1) be the first found nonzero pixel. If no nonzero
//pixel is found, assign -NBD to fij and go to (4).

int i1j1[2] = {-1, -1};

cwNon0(F, w, h, i, j, i2, j2, 0, i1j1);
if (i1j1[0] == -1 && i1j1[1] == -1) {
F[i * w + j] = -nbd;
//go to (4)
if (F[i * w + j] != 1) {
lnbd = ABS(F[i * w + j]);
}
continue;
}
int i1 = i1j1[0];
int j1 = i1j1[1];

// (3.2) (i2, j2) <- (i1, j1) ad (i3,j3) <- (i, j).
i2 = i1;
j2 = j1;
int i3 = i;
int j3 = j;


while (true) {
//(3.3) Starting from the next elementof the pixel (i2, j2)
//in the counterclock- wise order, examine counterclockwise
//the pixels in the neighborhood of the current pixel (i3, j3)
//to find a nonzero pixel and let the first one be (i4, j4).

int i4j4[2] = {-1, -1};

ccwNon0(F, w, h, i3, j3, i2, j2, 1, i4j4);

int i4 = i4j4[0];
int j4 = i4j4[1];

[contours[contours.count - 1].points addObject:[NSValue valueWithCGPoint:CGPointMake(j4 * 1.f / ow,
i4 * 1.f / h)]];

//(a) If the pixel (i3, j3 + 1) is a O-pixel examined in the
//substep (3.3) then fi3, j3 <- -NBD.
if (F[i3 * w + j3 + 1] == 0) {
F[i3 * w + j3] = (char) -nbd;

//(b) If the pixel (i3, j3 + 1) is not a O-pixel examined
//in the substep (3.3) and fi3,j3 = 1, then fi3,j3 <- NBD.
} else if (F[i3 * w + j3] == 1) {
F[i3 * w + j3] = (char) nbd;
} else {
//(c) Otherwise, do not change fi3, j3.
}

//(3.5) If (i4, j4) = (i, j) and (i3, j3) = (i1, j1)
//(coming back to the starting point), then go to (4);
if (i4 == i && j4 == j && i3 == i1 && j3 == j1) {
if (F[i * w + j] != 1) {
lnbd = ABS(F[i * w + j]);
}
break;

//otherwise, (i2, j2) + (i3, j3),(i3, j3) + (i4, j4),
//and go back to (3.3).
} else {
i2 = i3;
j2 = j3;
i3 = i4;
j3 = j4;
}
}
}
}

free(F);

...
}

SDF

上面提到边缘检测找连续的边缘点只是为了解决虚线描边,其他的描边情况其实是用不到这些点的,但是这里也遇到问题了。

一开始的想法跟上面通过3x3范围取平均值,通过条件过滤来做的,kernel code大概是这样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static NSString *KernelString = @"\
kernel vec4 borderDraw(sampler image, sampler mask, sampler source, vec4 rgba, float midpoint, float width) \
{\
vec2 uv = destCoord();\
vec4 color = sample(image, samplerTransform(image, uv));\
vec4 sumColor = vec4(0.0);\
float radiu = 2 * width;\
for (float m = -radiu; m <= radiu; m += 2) {\
for (float n = -radiu; n <= radiu; n += 2) {\
vec4 rgba = sample(image, samplerTransform(image, vec2(uv.x + m, uv.y + n)));\
sumColor += rgba;\
}\
}\
float avg = sumColor.a / float(radiu * radiu / 2.0);\
if (color.a < 1.0 && (avg > .05 && avg < 1.)) {\
return rgba;\
}\
return color;\
}";

这套方案做demo的时候,感觉效果还行,一点点毛疵,以为是条件判断不严谨,以为后续调整下可以解决,还有个严重的问题,就是这个方案计算量太大,图片分辨率1080左右,表现就有点卡,尤其是拖动滑竿调整,描边粗细 、间距 ,实时渲染有明显的卡顿,但是我们又不能降低图片质量,所以这个方案最终也就是停留在demo阶段了。

因为计算量太大,所以想办法降低像素计算量,SDF出场了,通过距离场,可以生成一张图,这张图可以告知像素边界信息,直接通过边界信息,省去了极大的计算量。

SDFsigned distance filed 有向距离场
sdf有两种方式,一种是循环(横向x纵向) 一种是双线性(横向+纵向),很明显前一种计算量远远大于后一种,联调下来第二种方案实际效果也是相当不错了。

这里还要考虑一个问题,因为描边是有粗细跟间距的,所以可以通过调整距离参数生成图,很好的解决了描边粗细跟间距问题的,SDF方案在虚线描边的case也是有用的,通过把SDF生成图拿去做边缘检测找连续点。

来看下SDF生成图的效果

抠图

横向SDF结果

接纵向SDF结果

贴一下Metal版本的SDF计算逻辑

横向SDF

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
extern "C" { namespace coreimage {

constant float threshold = 0.5;

float source(sampler image,float2 uv)
{
return image.sample(image.transform(uv)).a - threshold;
}

float4 sdfhor(sampler image,float width,destination dest)
{
float D2 = width * 2.0 + 1.0;

// 获取当前点坐标
float2 uv = dest.coord();
float s = sign(source(image,uv));

float d = 0.;
for(int i= 0; i < width; i++) {
d ++;

float sp = sign(source(image,float2(uv.x + d, uv.y)));

if(s * sp < 0.) {
break;
}

sp = sign(source(image,float2(uv.x - d, uv.y)));

if(s * sp < 0.) {
break;
}
}

float sd = -s * d / D2 ;

return float4(float3(sd),1.0);
}

}}

纵向SDF

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
extern "C" {
namespace coreimage {

float sd(sampler image,float2 uv,float width)
{
float D2 = float(width * 2 + 1);

float x = image.sample(image.transform(uv)).x;
return x * D2;
}

float4 sdf(sampler image,float width,destination dest)
{
// 获取当前点坐标
float2 uv = dest.coord();

float dx = sd(image,uv,width);
float dMin = abs(dx);
float dy = 0.0;

for(int i= 0; i < width; i++){
dy += 1.0;
float2 offset = float2(0.0, dy);

float dx1 = sd(image,uv+offset,width);

//sign switch
if(dx1 * dx < 0.){
dMin = dy;
break;
}

dMin = min(dMin, length (float2(dx1, dy)));

float dx2 = sd(image,uv-offset,width);

//sign switch
if(dx2 * dx < 0.){
dMin = dy;
break;
}

dMin = min(dMin, length (float2(dx2, dy)));

if(dy > dMin)break;
}

float D2 = float(width * 2 + 1);

dMin *= sign(dx);
float d = dMin/D2;
d = 1.0 - d;
d = smoothstep(0.5 ,1.0, d);

return float4(float3(d),1.0);
}
}
}

border

有了距离场,描边的工作就一下子简单多了。 目前实现的五种描边效果就是这样式的

项目中使用coreimage自定义kernel做的,当然也可以metal搞定

sdfsourceKernelString 对应上面第三个效果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
static NSString *sdfsourceKernelString = @"\
kernel vec4 borderDraw(sampler image, sampler sdf, sampler source, float d1, float d2) \
{\
vec2 uv = destCoord();\
vec4 color = sample(image, samplerTransform(image, uv));\
vec4 sdfcolor = sample(sdf, samplerTransform(sdf, uv));\
vec4 sourcecolor = sample(source, samplerTransform(source, uv));\
if (sdfcolor.x >= d1 && sdfcolor.x <= d2) {\
return sourcecolor;\
}\
return color;\
}";


static NSString *sdfKernelString = @"\
kernel vec4 borderDraw(sampler image, sampler sdf, sampler source, vec4 rgba, vec2 offset, float d1, float d2) \
{\
vec2 uv = destCoord();\
vec4 color = sample(image, samplerTransform(image, uv));\
vec4 offsetColor = sample(image, samplerTransform(image, uv-offset));\
vec4 sdfcolor = sample(sdf, samplerTransform(sdf, uv));\
vec4 sourcecolor = sample(source, samplerTransform(source, uv));\
if(offset.x != 0.0 || offset.y != 0.0) {\
if(color.a < 0.5 && offsetColor.a > 0.5 ) {\
return mix(rgba,color,color.a);\
}\
} else if (sdfcolor.x >= d1 && sdfcolor.x <= d2) {\
return mix(rgba,sourcecolor,offsetColor.a);\
}\
return color;\
}";

最后一个虚线描边就是常规的连接边缘点安排画布绘制,然后跟抠图做一个合并导出,就不展开说了。

Othter

最后还有一些注意点,比如抠图图像是在边缘,则需要考虑下预留描边空间,判断是否有落在边缘,如果有则补充点空间。
还有一个就是最小包围盒,抠图很可能只占据原图的一部分预期,为了展示效果,需要把抠图的最小包围盒找到,找这个最小包围盒,不需要那么精确,找出一个差不多的最小矩形框就行,项目上用的就是粗暴的像素遍历,找四个角的位置就可以了,通过最小包围盒,也能判断抠图是否靠近边缘。

The Last

综上,关键的几个步骤基本都尝试了多种方式,分析比较得出最合适项目需求的技术方案, 最终从性能、体验等维度拿到相对不错的结果,单纯从描边功能上来说,对比修复工具也不输 O(∩_∩)O哈哈~

reference

PContour
SDF
双线性SDF