Monthly Archives: March 2012

future in c++0x

标题玩了个文字游戏,其实只是小试了下 c++0x 的 std::future 及相关类。 gcc 对 c++0x 的支持还算可以。记得编译时加上 -std=c++0x 参数。 注意 std::thread task_thread(std::move(task)); 这句因为 gcc 4.6 std::bind 的 bug 编译错误。 coding 的感想是,c++ 模板编程的错误消息实在极不友好,作为一个语言和标准库来说,这是没法容忍的。 Advertisements

Posted in Computer and Internet, Programming and Algorithm | Tagged | Leave a comment

Hough变换 检测矩形

最近要写个算法自动找出图片中用来标示的指定颜色的矩形,最先想到的是古典并简洁的 Hough变换。不过真动手实现起来却也不是那么简单。 Hough变换 最简单的应用是辨识图片中的直线,对应的变换是将图中的点变换成 Hough空间 中的两个参数(直线的斜率和截距,或者其它参数表示)。而对于矩形来说,Hough空间 就需要有4个参数(左上点 和右下点 的坐标)。这样相对于直线检测,算法的空间复杂度和时间复杂度有了平方级数的增加,对于大一些的图片很容易就吃掉数G的内存。 对于时间复杂度,因为要找的是指定颜色的矩形,那么颜色差别大的点可以完全不用考虑进去,这样可以使需要处理的点减少大半。 对于空间复杂度,显然4维的 Hough空间 中有相当大的冗余(右下点一定在左上点的,嗯,右下,就是说 ),用更有效的数据结构可以消除掉这部分的空间冗余。 当然,如果上面的优化还不够的话,就得用图像处理中常用的最后一手——降低原始图片的分辨率,做完计算再升回去。 还需要注意的是,最后在 Hough空间 里选择矩形的时候需要做一次归一化。不同大小的矩形在 Hough空间 的权重也不同。 1962年为了找气泡室中粒子轨迹而发明的 Hough变换 在今天仍应用频繁。有回归起源的在 LHC 中找 μ介子 的轨迹,也有应用在车载系统中检测行驶中车辆是否偏离车道。

Posted in Computer and Internet, Programming and Algorithm | Tagged | Leave a comment

H5N1的故事

Bird Flu Scientists Agree to Pause H5N1 Research Research on Deadly Bird Flu to Be Published in Full Maker Says Bird Flu Virus Not as Dangerous as Thought 这几篇报道连起来看有些像现代的好莱坞恐怖片。试想如果致死率超过五成的 H5N1 能够感染人类并在空气中传播,这个世界会变成怎样。作为参考,1918年西班牙流感(其实发源于美国)死了数千万人,而它的致死率只有百分之二。 (上面的描述有不少简化的部分,实际情形会有很大的不确定性。) 于是这次的争论就是是否应该全文公开两个实验室将 H5N1 基因改造成空气传播性的文献。同样,最有趣的部分不是报道,而是紧接着报道之后的读者评论。评论一边倒的倾向于只公开删减版(原因多种多样,科学家的道德,恐怖组织,民族国家,等等;或者也可以说很单纯,就是不信任感),而 Science 和 WHO 则决定全文公开(单一理由,分享和研究的自由会更有助于相关研究的进展)。 不过,这场现实版恐怖片的第一幕只能激起基于理性层面的恐惧,感性层面的话也许只有体验过1918的人能引起共鸣。 … Continue reading

Posted in News | Tagged | Leave a comment

Why Functional Programming Matters

乘着看 Haskell 的机会回头又读了一遍 Why Functional Programming Matters。 “It is a logical impossibility to make a language more powerful.” 这句话有些意思。函数式编程并不是由于取消了赋值语句而更强大,而是因为高阶函数和惰性求值的引入,使得函数拥有了更强的抽象表现能力,使程序有了更新颖的模块化方式;正如结构化编程并不是去掉了goto,而是加入结构化语句,使得程序的模块化更为清晰。另一个类比是 Java 并不是因为放弃了内存操作,而是由于引进了垃圾回收机制而提高了编程效率。同样是 Java,没有多重继承就只能说是缺点。 即使在实际应用中不打算使用函数式编程语言,它的一些想法仍然有着启示作用。 比如 Google 的 MapReduce 的抽象模式便是由函数式编程的 map 和 reduce 启发的,而其库实现则完全是指令式编程语言 C++。 Haskell 下,reduce 的命令是 foldl。于是, > let sum … Continue reading

Posted in Computer and Internet, Programming and Algorithm | Tagged , | 1 Comment