人生若只如初见

木兰花 拟古绝决词

纳兰性德（清）

人生若只如初见，何事西风悲画扇？
等闲变却故人心，却道故人心易变。
骊山语罢清宵半，夜雨霖铃终不怨。
何如薄幸锦衣儿，比翼连枝当日愿。

水源上看到这首诗，才知道 人生若只如初见 的出处。
此前也常读到这句诗，或是同学签名中引用，均未细想，此刻品味之余，方觉有味。
大概人生便是如此，初见惊鸿，时间一长，便觉平淡，亦或生厌。

以下为别人的注解：

人生若只如初见，这一句实在令人哑然
悲剧往往都是这样没有征兆的开始，
而种子已深埋在初见的那一刻。
漆黑一片的世界里，有喑哑的胡琴声响起；

隆中初见，羽扇纶巾，笑谈中三分天下，
再见时已是白帝托孤，六出祁山，壮志未酬身先死；
西厢初见，风流不用千金买，月影花移玉人来，
再见时却是弃掷今何在，悔教夫婿觅封侯；
梁山初见，天罡地煞席卷天下，
那一派豪侠风光令人血脉愤张，
乃至再见，听潮而圆，遇信而寂，
寥儿洼招魂幡动，依稀鬼哭；
金屋初见，千娇百媚，永世相守，
而色衰爱驰之日，终晓千金难买长门赋；
华清池中温泉水滑，生长殿里夜半私语，
谁会料到结局是马隗坡前数丈白绫，一捏黄土；
原来所有的名字，所有的故事，都是写在水上的，
那些波澜和涟漪，在当时看来惊心动魄，
而长江滚滚，只是一朵小小的浪花而已，
流过，终于迹；
年少的意气风发，最初的感动和梦想，
在时间的浸润下渐渐磨灭；
一见如故的亲切，山盟海誓的诺言，
只剩下一个依稀的背影；
金甲的战神披着天边的彩霞，
在故事中定格成永恒的记忆；
即便是猜得中绚丽的开头，
又有谁见到了那早已注定的结尾？

初见，惊艳，蓦然回首，
曾经沧海，早已是换了人间。

线性方程组求解库

求解线性方程组 Ax=b，常用的方法包括 直接解法（一般是对 A 进行矩阵分解）和 迭代法。常用的数值计算平台，如 Matlab，Octave，numpy 中都支持对线性方程组的求解，以 Matlab 的性能最优，支持的方法也最多，直接求解时用 x=b\A 会根据 A 的性质（如对称、稀疏）选择最优的算法，在用迭代求解时还可以先进行不完全分解来加速收敛速度。

下面总结一下我所知道的开源的求解线性方程组的相关的数值计算库，一般都是 Fortran 或 C／C＋＋开发。

• BLAS(Basic Linear Algebra Subprograms)

  blas 是许多数值计算软件库的核心, 一般是用 Fortran77 实现, 支持矩阵、向量基本操作。也有 C／C＋＋的封装。
  据说性能最优的 BLAS 实现是 gotoBLAS。

• Sparse BLAS

  BLAS的 Sparse matrix 版本。见到的都是 NIST 版本，C＋＋的，netlib 上的 是一个 Fortran 版本。

• LAPACK（Linear Algebra PACKage）

  专用于线性运算的，如求解 AX=b, 矩阵分解、求逆，求矩阵特征值、奇异值等，在 www.netlib.org/lapack/ 是 Fortran 版本的，应用很广，但还未见到针对 Sparse matrix 的版本。

• ScaLapck

  可以在分布内存的计算机上并行求解线性问题，即并行版的 LAPACK。

• SuiteSparse

  SuiteSparse 是 Prof. Tim Davis的 Sparse matrix solver 的程序包，涉及希疏矩阵分解，大多用 C 开发，提供 Matlab 接口。Matlab 中的很多数希疏矩阵函数的原型都可以在其中找到。性能非常出色。强烈推荐看看他的主页！

• TNT(Template Numerical Toolkit)

  C++的数值计算库，目标很大，据说还要集成 LAPACK++,Sparselib++,IML++,MV++。但目前还很薄弱，也就是定义了一些数据结构，求解线性方程组的能力基本没有，Sparse matrix 的操作功能也没有。

• Sparselib++

  C++的 Sparse matrix 库，与 sparse BLAS 差不多，多了对矩阵的 preconditioner功能，可以配合 IML++ 做线性方程组的迭代求解。

• IML++(Iterative Methods Library)

  C＋＋的。支持对 dense or sparse 的线性方程组的迭代求解，包括
  * Richardson Iteration
  * Chebyshev Iteration
  * Conjugate Gradient (CG)
  * Conjugate Gradient Squared (CGS)
  * BiConjugate Gradient (BiCG)
  * BiConjugate Gradient Stabilized (BiCGSTAB)
  * Generalized Minimum Residual (GMRES)
  * Quasi-Minimal Residual Without Lookahead (QMR)
  等方法，可配合使用 sparselib++。

• ITL (The Iterative Template Library)
  The ITL currently includes the following methods:

  • Conjugate Gradient (cg)
  • Conjugate Gradient Squared (cgs)
  • BiConjugate Gradient (bicg)
  • BiConjugate Gradient Stabilized (bicgstab)
  • Chebyshev Iteration (cheby)
  • Richardson Iteration (richardson)
  • Generalized Conjugate Residual (gcr)
  • Generalized Minimal Residual (gmres)
  • Quasi-Minimal Residual Without Lookahead (qmr)
  • Transpose Free Quasi-Minimal Residual Without Lookahead (tfqmr)

  The ITL currently includes the following preconditioners:

• Incomplete Cholesky (cholesky)
• Incomplete LU without fill-in (ILU)
• Incomplete LU with n fill-in and with threshold (ILUT)
• SSO
  
• SuperLU

  对大型、稀疏、非对称的线性系统的直接求解，用 Gauss 消去法做 LU 分解。用 C 开发。

• SPOOLES

  C。可求解对称和非对称的线性问题。

• MTL

  基于 C++ template 的 matrix class lib，技术比较眩，性能据说也不错，但支持的操作太少，线性方程组的只有 LU 分解，和几种迭代方法，不支持 sparse matrix。

• blitz++

  技术上更眩，但对线性方程组的支持很少。

• GSL

  GNU scientific library，很正统，但对 sparse matrix 的支持为0，性能也不突出。

• 其它

  MKL（intel math kernel library）非常强大，包括了优化过的 blas，LAPACK，又支持 sparse direct solver，可惜不开源，使用起来不方便。
  这儿对 sparse linear system direct solve software 有非常全面的总结。

I've tested some of the libraries, with following results :
testing data : sparse symmetric positive matrix
dimension : 3000x3000
density : 0.3
non-zeros : 1284213
condition : 2.7015e+04
opencv : CV_LU 45.7s(linux)
mkl : pardiso 3.17s(win)
matlab : \ 2.57s(win)
CHOLMOD : cholmod 2.48s(linux)

and I've found that linux(ubuntu-6.10 in my workstation) is far more flexible than windows in programming and scientific research!

Recipes of Books

Having just finished reading two of the exceptional c++ serials today, and it worth the two weeks time, really !
I'll focus on algorithm on the next stage, and will be my next book.
Reading, thinking, and then practising, are of great interest !

SIFT-Based Object Recognition

David Lowe提出的SIFT算法得到的SIFT特征具有很好的稳定性和不变性，已经被证实是目前最好的不变局部特征提取算法之一。去年大半年时间都在研究这个算法，以及Lowe在Distinctive image features from scale-invariant keypoints(IJCV.2004)中提出的目标识别框架。去年12月时已经有比较好的识别结果了，并提出了一些自己的想法和改进方案，效果也可以，最近又对算法作了些优化，已经能做到2~3fps的识别速度了。
SIFT算法复杂度比较高，多次卷积计算量比较大，并且由于产生的特征点很多，生成特征向量的时间也就比较长；至于后期的匹配和识别过程，也需要一定的时间，比如基于kd-tree的BBF算法，虽说搜索速度比逐一比较加快了几个数量级，但数据库一大，输入特征点比较多的话，还是挺耗时的。而hash hough即需要空间上资源(每个feature需要对应16个bin)，也需要一定的计算量，如求解基于最小二乘的仿射变换。因此要做到实时真是太难了。目前看到的最快速度大概也就是10帧左右吧，那已是commercial product了，并且David Lowe本人亲自参与开发，自是不可比拟的了。
SIFT算法过程也比较复杂，目前网上有一些参考代码，质量参差不齐，倒是不错的参考，完全自己写，还是比较难的，目前还没这样的算法素养。kd-tree比较成熟了，拿来用就是了，倒是generalized hash hough有点费神，Lowe的paper写得挺含糊，也并没有找到可参考的代码，只能自己边想边写了。hough变换的原理很简单，只想不明白hash与hough是如何结合的，看了一大堆hough变换的应用资料，再结合hash原理，用了三天才将代码写出，其中用到了STL中的hashmap(STL还是挺方便的，后来自己用C写了个hashtable实现hash hough，效果就有点差，可能是hash函数不够hash，数据结构安排也不合理)，效果还是挺好的，挺开心的，也挺佩服Lowe提出的算法和框架，确实很有效。
下面是一些截图，已经将SIFT-Based目标识别做成模块，集成到Demo中了：
第四张图为landmark，前三张为在线识别视频截图，左边主窗口为识别图像，左边小窗口为视频图像，中下数据窗口为识别结果，右边竖条为landmark image database。

Panoramic Image Transform

也是去年十二月写的一个小程序，全景图像展开，很简单的算法，两天便完成了。不过刚开始想得比较复杂，比如考虑镜面方程(二次抛物面)，成像模型等等。这样恢复的图像质量当然比较好，不过比较麻烦。后来使用了简易算法：project circle to clinder， 公式如下：
panoramic(w, h) omni-directional(R, r) // center of omni-directional image
p(x, y) --> p1(x1, y1) p0(x0, y0)
w = (R + r) / 2
h = R - r
theta = x / w
x1 = x0 + (r + x) * sin(theta)
y1 = y0 + (r + y) * cos(theta)

按上面公式展开得到的图像会有比例失调：上半部分拉伸了，下半部分压缩了，这是由于镜面的非线性映射造成的。于是我拟了一个简单的二次函数对下半部分图像进行非线性拉伸(注:与镜面方程无关，在此就不透露公式了:)，下面是一些实验结果:




全景图















NN未拉伸的图



双线性插值并拉伸后的图




可以看到，拉伸处理后的图与实际环境的尺寸比例比较接近，效果还是挺好的。
此外也在linux下做了实时视频展开实验，将494x464的彩色图展成864x244的彩色图，使用双线性插值算法，也有很好的实时性，核心算法代码写得比较高效。

Digit Number Recognition

去年十二月写了一段针对仪表的数字识别代码，功能比较简单，现总结一下其中的过程。
分别用模板匹配和神经网络实现了识别过程，其中模板匹配算法借鉴了茅老师的idea。
template match ：
image[in] => rgb2gray -> segment(ostu) -> find digits(flood) -> normalize -> NN or Correlation => recognized digits[out]

neuronetwork :
image[in] => rgb2gray -> segment(ostu) -> binary -> find digits(projection) -> normalize ROI -> skeletonize -> generate features(top, bottom, right, left, width, height) -> normalize feature -> BP network(3 layers) => recognized digits[out]

训练与识别过程类似。
template方法比较简单，而且在实际操作中发现识别准确率也比较高，事实上对于固定的摄像机位置和固定形状的数字，模板与实际提取出来的数字不会有太大的差别，因此效果好，速度快，比较适合仪表数字识别应用。
神经网络方法有些复杂，我参考的是一个手写数字识别算法，识别效果也可以，但ANN的参数比较难调，最终选择96-192-10的3层BP网络。在调BP时也遇到了一些问题，训练BP时很多次迭代后RMS老是不能收敛到比较小的值，仔细读了pattern classification中关于ANN的介绍，明白了一些数据处理要求，如训练数据归一化，S函数选择技巧等，实践一下后，效果确实好了些。利用十个样本(0~9)进行监督学习，然后在线识别，效果不如template方法，但也是不错的。猜想使用更多样本学习后，可能效果会更好(有待实验证实)。

这样的小工程还是挺有意思的，前后也就用了两个星期，练练手，不错的。c++代码也写得也还满意，factory模式，支持xml配置文件读写，cross platform(linux, windows)，在windows上做了个Demo：一个数字仪表模拟器，一个USB摄像头视频捕捉和在线识别Demo(这些灵感也来自于茅老师，看过他们的电路实验:)，下面是Demo截图：

一些说明：左图为数字发生器，模拟LED数字，可以定时随机生成，右图为视频采集与在线实时识别Demo，识别前先要手动选择数字区域，固定好位置后就能实时识别了。

Testing Tesseract-1.0.3

有关tesseract的报道不再多述，google一下就会有很多结果。早在去年12月就因为要做数字识别而尝试过tesseract-1.0.2，2月底google在sourceforge上又发布了1.0.3，修正了一些内存泄露bug，并作了不少改进，至少编译起来很少了错误(vc2005对一些语法检查比较严，有一些类型转换的错误)。
1.0.3中运动WinMain，但还是通过间接调用main，完成识别工作，也就是在控制台下工作。觉得不太方便，今天花了点时间在已有的基础上增加了剪贴板功能，直接对文字识别，其中做了些彩色变换，因为目前tesseract只支持灰度图，只能识别英文和数字。下面是截图:

Our generalized Rough algorithm uses edge inlors
matron lu dehne a mapping [rot-n the orientation nfan edge paint to a reference point of the shape. Tht: reference point may be though! of as the origin of a loualeo-ordinate system for the shape Then there is an easy way ofcompuling a measure which rates how well points in the image are likely to be ortgins of the specified shape. Figure X shows a few graphic examples of the information used by the generalized Rough
transform. Lines indicate gradient directions A feature of the transform is that it will work even when the boundary is disconnected due to noise or occlusions.This is generally not true [or other strategia whichtrack edge segments
The original algonthrn by Houghm did not use

准确率还是挺高的。
目前还没有关于tesseract的官方文章，相信google不久会整理并发布的。现在也没有时间研究它，先好好把Duda的pattern classification看完再说.

further more, perhaps I've found an interesting application of tesseract, that is Visual Reader on our PC. more details, read web pages, papers, books, etc for us. This is obvious possible with tesseract and MS's Speech SDK, plus some additional image processing, for example, selecting the text region, finding out the time to perform OCR on current screen content. I've got a picture about this demo, just some programming work remained:)
life should be ease for us slothful man ~~