图像描边

image border

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

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

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

image matting

首先是抠图，就是这样的

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

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

Edge detection

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

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

代码大概是这样的…

+ (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 调试下来就能获取正确的结果了，这里就不多说了，直接看下代码，对应的节点有注释说明

+ (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的代码：

+ (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大概是这样

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出场了，通过距离场，可以生成一张图，这张图可以告知像素边界信息，直接通过边界信息，省去了极大的计算量。

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

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

来看下SDF生成图的效果

抠图

横向SDF结果

接纵向SDF结果

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

横向SDF

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

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 对应上面第三个效果

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