算法实战 | 图像处理, 宽度优先搜索, 位运算
前言
本来野心满满的打算写一周一算法，但经过一段时间的面试，发现大多数中等程序员。连逻辑都捋不顺，谈何算法？
我面试特别爱问的一道题： 100w 个整数去重复，你怎么做？
对话经常是这样的：
面试者：我一个个的枚举，把重复去掉。
我：好吧，你能手写一下么？
然后就看他吭哧半天，写了五六个循环后和我说：对不起太难我做不出来。
我：好的，那换个问法，100w 个有序的数组去重复，你怎么做？
又看面试者吭哧吭哧了些两三个 For，有可能做出来了。
我：时间复杂度太高，你看看能不能优化一下。
面试者：太难做不出来。这并不是我胡编滥造，而是我四五月份两个月份的面试，基本上每天都会发生的事情。一个有序数组去重复，真的算是考算法么？明明一个循环就搞定的事情，却要憋那么久。（当然这道题用 Set 是最优解，毕竟我没说是在考算法）。
于是我觉得我辛辛苦苦备课讲算法，是没有价值的事情。大多数人还是在看热闹，真正写的话根本写不出来。
而且很多人都觉得：算法仅在面试时有用，工作根本用不上，于是我开了这么个新坑。专门讲日常开发的时候，我都在哪里使用了这些基础算法。
背景
众所周知，我是礼物说的技术合伙人，而礼物说是一家礼物电商。作为一家电商，运营部门是公司的第一大部，她们（嗯，你没看错，都是妹子，我司男女比例 3:7 左右）经常要把官方授权的商品图，抠下来放到各种需要的地方去。例如：
然而这是个很机械的劳动，而且 PS 卡得不行，于是运营部门的一个萌妹子就求我们技术部门能不能帮他们写个软件，自动的把上万张图干掉背景。这种大幅提升工作效率的工具，肯定要同意嘛。
选平台，定语言
我们要先定一下用什么东西开发，总不能用 iOS SDK 吧，为了跑个图，起一个模拟器，想想就觉得蛋疼。可选方案：
CoreGraphics //Objective-C, Swift
ImageMagick //C++
PIL //Python
对于这种大量的图片，效率还是需要考虑的。于是就用 CoreGraphics，毕竟我们知道 macOS 的命令行工具 sips 的性能碾压 ImageMagick。而语言呢，这里我选择了 OC，因为我知道我会混 C++ 的，Swift 混编就太蛋疼了。
流程
其实流程很简单：
取出像素矩阵
去掉白色部分
保存图片
于是，先把和算法无关的东西写好，也就是把图片读成像素矩阵再写回去的过程。
读的话很方便，几行就好了：
而保存就相对复杂多了，因为要创建一个新的 CGImage:
去除白色
识别白色
想要去除白色，首先要知道什么是白色。毕竟每一个像素是一个 UInt32，而不是 [NSColor whiteColor]。
于是，我们需要知道他的表现方式，则对拿到的像素点执行:
printf("%x\n", pixels[0]);//OUTPUT: 0xffffffff于是我们可以这样把 rgb 拿出来：
解释一下位运算:
& 操作符是二进制每一位做与运算。例如二进制：1111 & 0010 ＝ 0010>> 操作符是二进制位移。例如二进制：100 >> 2 = 1
于是 0xffffff & 0xff000000 就是 0xff000000，为什么右移 24 位，而不是 6 位呢？别忘了这里是十六进制。十六进制的一位，兑换成二进制就是四位。毕竟 2^4 = 16。
于是我们只要把 rgb 等于 255 的颜色踢掉就够了～
找白色
对于如何找白色是个问题，最暴力的就是循环一遍矩阵，把所有白色的地方全干掉。但这样带来一个问题，如果商品中也有白色就一起被干掉了。
这个时候需要用一个算法，叫做 FooldFill，相当于把颜色相同的部分圈起来。这个算法有深度优先搜索和宽度优先搜索两个版本，这里我选择了宽度优先。
宽度优先搜索算法，也就是 BFS 他的思想是：
BFS是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。
用魔性的画风画出来呢，访问路径就是这样的了：
算法流程：
创建一个队列，把 {0, 0} 等四个角塞入队列中，作为出发点，并把这四个角的颜色改成透明。
取队首的点，判断他的上下左右是白色的么，若是白色的则：
把白色改成透明
把这个点加入队列
当前点出队
如果队列为空，结束循环
GOTO #2
写出来非常简单的，这里用了 C++ STL 的 QUEUE 和 智能指针，以及偏移量数组：
跑一下效果:
和我们想象中不一样，为什么呢？用取色发现，由于 JPEG 编码的原因，主体周围混入了大量和白色差不多的杂色。于是我们应该给颜色算一个相似度，而不是直接判断 255，但相似度怎么算？
余弦定理
一个颜色可以看成 RGB 三维向量。而向量的相似度是可以计算的，常用的做法就是余弦定理，于是我们有：
cos 的取值范围是 -1~1，我们期望夹角越逼近0是越好，也就是 cos 逼近 1 的时候。
再跑一次：
搞定！