Filed under: 技术体会
最近看到一篇关于寻找图像中连续颜色区域的文章，作者的想法相当巧妙。传统的方法是自左至右自上至下逐个扫描图像中的每一个像素(pixel)，对于每一个像素，假如坐标是(x,y)，需要比较它左边(x-1,y)和右边(x,y-1)上的像素，时间复杂度是O(m*n)，m和n分别为图像的宽度和高度；作者的想法是，不要一个像素一个像素的赵了，改作先把每一行像素拆分成连续颜色的一段一段，称为Span，这样就只需作Span得比较就好了，时间复杂度还是O(m*n)，但是这种实现更加优化。
这段算法的原理如果你没兴趣了解也没关系，有意思的在后面:-)
很明显，作者对自己的“发现”沾沾自喜： For the tuning wizards, if my algorithm takes 100% time, how many percent can you get? I myself expect (but not guarantee) to be around 5-10% faster. Can anyone do better?
说老实话，我第一眼看到这哥们的想法也被折服了，毫无疑问这样的实现效率会更高啊！出于练习的目的，我用传统方法实现了一遍(姑且叫pixel-by-pixel方法），然后觉得他的实现过于复杂，用类似他的建议（span-by-span方法）实现了一遍。这位提供了自己的code，而且还有一个GUI应用程序自动生成随机的黑白点阵，然后用自己的实现的算法来寻找连续的黑色或者白色区域，我就把自己实现的code也结合到他的应用程序里面去比较一下。一开始，我只是想比较一下我实现的Span-by-Span方法和他实现的Span-by-Span方法的的效率，希望我得比他的快，结果还比较让人满意，我的比他的要快大约30%，不过让人吃惊的是，我的传统的Pixel-by-Pixel方法实现，比两种Span-by-Span实现都要快得多！几乎快5倍！
怎么回事？我反复演算了一下code，所有的实现结果都是正确一致的，所以不存在pixel-by-pixel算法不正确的问题，那为什么一个显而易见效率会更高的算法居然不快呢？问题出在实验对象上，这位仁兄的应用程序自动生成黑白点阵，因为用的是随机数，所以几乎就没有多少很长的Span，也就是说，Span-by-Span的优势完全没有发挥出来，相反，为了维护这些只有少数pixel的span，需要额外的运算和内存，效率反而不如pixel-by-pixel。
这件事告诉我们，说一样东西能工作，唯一的方式是跑它一下；说一样东西强壮，唯一的方式是折腾他一顿；说一样东西效率高，唯一的办法是比较它和其他东西的结果。
当然，现实中的图像处理往往不是这么随机的，图像上一件物体有颜色，那一块就基本上是这种连续的颜色像素，这样就有比较长的Span，这样Span-by-Span的方法的确就会快一些。啊，刚说的，不能空想着觉得它会快，我试验了一下，基本上Span-by-Span效率比pixel-by-pixel快一倍。
2条评论 so far
留下评论
巴别塔上的雇工 
有意思，我觉得自然界物体已连续颜色为主体的这个假设更有意思，说明了很多算法针对实际情况作一下变更马上就不一样，就好比GOOGLE针对ARM做的VM优化，就是这个道理，不应该上来就假设VM支持所有的CPU，当发现市场上90%是ARM体系的时候，自然算法就会相应的改进与优化了。
评论 由 Jinghua 5月 23, 2008 @ 4:36 上午30%, not bad Morgan 🙂
评论 由 Kirill 6月 18, 2008 @ 6:22 下午Not that I completely understand your post, but I know what’s it all about 🙂