怎样检索图形

panda

请教大家一个问题： 如何进行图形检索？比如下面这个图片。我试着用google的图片检索功能，结果出来一堆很诡异的东西。类似问题大家的解决策略是什么呢？ 谢谢！

huangstc

刚好知道一点，抛砖引玉吧。大致可以分三步，第一步把图片转化为高维空间中的向量，第二步把高维空间中的向量投影到一个低维空间，保证相似图片在低维空间中的距离也接近，第三步对低维空间中的向量建立索引。
4 t$ k, z- g9 w
( w. Z" D% p7 ~  Y第一步是特征提取（feature extraction），基本一切模式识别问题都从此开始。特征提取可以各显神通，比如对原图进行小波变换，算一下颜色直方图之类。最后得到一个几千几万维的特征空间。特征选取得好的话，相似的图片在特征空间里就比较接近了。特征选得不好的话，按俗话说，garbage in, garbage out，下面两步也没意义。选好了特征之后的问题是，特征空间的维数太高，无法高效检索，于是可以有第二步把特征空间向量投影到一个低维空间。低维空间可以随便选，选100个正交的向量都行。更好的做法是PCA（principal component analysis）。PCA的思想是收集很多样本，选取一个低维空间使得这些样本投影之后的方差尽量大。这里有很漂亮的数学结果，好的低维空间恰好是样本在特征空间里的向量的协方差矩阵的最大的几个特征值对应的特征向量张成的空间。解这个特征值不容易，好在有近似数值算法，略过。第三步呢，基本是在低维空间里做一个树，把爬虫爬到的图片都装进去。
! R9 K" H6 ]6 X( O, b+ {
; m. Y1 h7 |: e; |; _: P, H' c9 Q0 M参考文献：
4 x6 D' P) r/ e9 |+ k& tClustering Billions of Images with Large Scale Nearest Neighbor Search，
: H; E1 m7 z2 Y. ]0 E3 T+ v* Nhttp://research.google.com/pubs/author30937.html
当然这篇文章很老了，现在应该有更先进的做法。

潜了又潜

这个得看你的应用了，或者说你检索样本的复杂程度，越通用的做法适应度越广，但效果比较差。