This is a summary of the algorithms I used to write OpenPano: an open source panorama stitcher. You can find the source code on github.

上学期组团参加了 SIGMOD Programming Contest 2014, 进入了 Finalist. 因此 6 月 23 日至 26 日, 我在 Utah 州 Snowbird 度假村参加 ACM SIGMOD/PODS 2014 会议.

每年的比赛题目跟 ACM-ICPC 比较像, 就是给输入, 产生确定的输出. 比赛形式的不同在于, ICPC 中选手要尽量快的写出一个运行速度可以接受的程序, 而在 SIGMOD 比赛里, 我们需要在一个多月时间里写出一个在给定机器上运行速度尽量快的程序, 而且可以用任何手段 (并行, 汇编, SIMD, 文件读写).

最终结果与之前的 online 测试结果基本一致, 获得了第四名. 听了其他选手的报告, 深深的感觉到, 压榨程序效率时, 算法并不怎么重要.

在知乎上看到这么一道题, 原题描述的不太严谨, 其大意是:

一幢 200 层的大楼, 给你两个鸡蛋. 如果在第 n 层扔下鸡蛋, 鸡蛋不碎, 那么从前 n-1 层扔鸡蛋都不碎. 这两只鸡蛋一模一样, 不碎的话可以扔无数次. 已知鸡蛋在 0 层扔不会碎.

提出一个策略, 要保证能测出鸡蛋恰好会碎的楼层, 并使此策略在最坏情况下所扔次数最少.

图像处理课期中要写一个图像拼接程序.

这方面的技术当然已经很成熟了, 开源界最著名的当属 hugin, 拼全景图效果非常好. 在学术界也已经不是难题了, Lowe 在 IJCV2007 的一篇 Automatic Panoramic Image Stitching using Invariant Features 是一个完整的流程介绍. MSRA 的 Szeliski 有过一本几十页的 Image Alignment and Stitching: A Tutorial, 也详细的介绍了图像拼接的众多方法. 我基本就照着 Lowe, Szeliski 的一堆论文的方法在搞.