Saturday, January 28, 2012

Summary of Block Compressed Sensing on Image

Last article, I briefly introduce existing cs method on image. This article aims to summary how block cs worked on image.

Before I go on, I need to introduce something about measurement matrix.
Currently, there are several way to generate a measurement matrix. For a complete list of possible measurement matrix, please refer to  https://sites.google.com/site/igorcarron2/cs . Here I only discuss three of them: 
  • Random Fourier Ensemble: The signal is a discrete function f on Z/NZ, and the measurements are the Fourier coefficients at a randomly selected set Omega of frequencies of size M ( A is an M x N matrix.)
  • Gaussian ensemble: A is an M x N matrix (M x N Gaussian variables).
  • Bernoulli ensemble: A is an M x N matrix (M x N Bernoulli variables). 
It should be noticed that for most of the case, the measurement matrix should be orthonormal.

For 1d signal, Gaussian ensemble is enough to reconstruct the signal[1]. However, for 2d image,  N can be fairly large, which makes the storage and computations of a Gaussian ensemble very difficult. Thus, [2] suggested to apply a partial random Fourier matrixFor sparse basis, it employed waveletBesides, it uses min tv instead of l1norm as recon strategy. However, I've found no simulation code available for [2].

Another possible way to solve the problem addressed before is to sample the image block by block. This is quite similar with what JPEG did. [3] gives out corresponding research. For measurement matrix, the paper uses i.i.d Gaussian ensembles. For sparse basis, it uses LT. The reconstruction is based on PoCS and Hard Thresholding . No simulation code available now. But you may refer to https://sites.google.com/site/igorcarron2/cscodes. There is a code called sbhe.m
Implemented from Fast compressive imaging using scrambled block Hadamard ensemble by Lu GanThong Do and Trac Tran. This is another algorithm proposed by the same author. It may help you.


To improve the performance of [3], [4] proposed to first decompose the coefficients into dense and sparse component. For dense component, it uses conventional encoding; for sparse component, it uses cs. For measurement matrix, it didn't clearly indicate in the paper. But from inference, it should use i.i.d Gaussian ensembles as in [3]. It still employs wavelet as sparse basis. The reconstruction is based on PoCS[2] and prediction by adaptive interpolation. The paper gives out the detailed reconstruction scheme. No simulation code available now.


After that, [5] gives some interesting simulation results. Here for measurement matrix, it should still use i.i.d Gaussian ensembles.But for sparse basis, it proposed to use Directional Transformation(CT and DDWT).The reconstruction is based on SPL. Simulation code is available at http://www.ece.msstate.edu/~fowler/BCSSPL/. Besides I am quite interested in analyzing the EXPERIMENTAL RESULTS part in this paper. It compares with several other methods.
1. To compare the effectiveness of CT and DDWT, it compares to BCS-SPL-DWT, BCS-SPL-DCT. The simulation code is not available now.
2. To compare SPL with TV, it compares with BCS-TV. The implementation is using l1-Magic(http://acm.caltech.edu/l1magic/). I have implemented the code at http://www.ualberta.ca/~hfang2/pub/Block CS-TV.zip .
3. To compare SPL with GPSR and SAMP, it uses the implementation provided by their respective authors(http://www.lx.it.pt/~mtf/GPSR/ http://thongdojhu.googlepages.com/samp_intro/ ).

The last one is [6]. It perform random permutation among blocks to achieve better performance. It uses DCT as sparse basis. For measurement matrix, it uses i.i.d Gaussian ensembles.It uses min l1-norm instead of min tv as reconstruction method. I recommend you use cvx_toolbox(http://cvxr.com/cvx/download/) for simulation.

If you find any simulation code published, or any error in the article, please contact me.
Thanks a lot.


[1] Robust uncertainty principles: Exact signal reconstruction form highly incomplete frequency information
[2] Practical Signal Recovery from Random Projections
[3] Block Compressed Sensing of Natural Images
[4] Image Representation by Compressed Sensing
[5] Block compressed sensing of images using directional transforms
[6] Compressive Sampling With Coefficients Random Permutations for Image Compression

Wednesday, January 25, 2012

Compressed Sensing(压缩感知)用于图像的综述

CS最初由[1][2][3]提出。[1, 2]没有看,[3]中理论推导比较多。我建议读[4]作为入门。
最初的CS理论只提出了noiseless的情况下,可以accurately recover compressible signal,注意是需要compressible signal的,不过大多数信号的是compressible signal,所以适用面很广。
于是有人就会想在noisy的情况下,是否可以使用CS呢?
最初的研究是,Noisy measurements的恢复效果不是很好。所以Wisconsin的俩人J. Haupt和R. Nowak就对zero-mean additive noise的情况进行了研究,相关工作可以参看[5]。他们的结论当时是可以在这种加性噪声的情况下恢复原信号(否则就没法发paper了...)。
对之后CS方面的文献就不在这片文章里描述了。


接下来我想重点讲一下cs用于imaging的文献发展历程。
一般来说,研究都放在如何采样一个图像或者如何压缩一个图像。
对于2D的图像,由于维数较大,导致CS面临有以下几个问题:
1. 重建算法计算量大
2. 需要大量的存储空间来保存随机采样operator,即measurement matrix

05年的时候,在[6]中最初对2D图像信号进行了CS reconstruction并给出了其仿真结果,不过这篇文章只讨论了无噪的情况,而且没有给出有噪情况的分析。作者的主要方案是apply a partial random Fourier matrix in the wavelet domain。
06年[3]提出multiscale CS:different scales of wavelet coefficients are segregated and sampled with partial Fourier ensembles。
也是06年的时候,[9]就对CS是否能作为一种imaging method进行了检验,主要考虑有噪情况下是否能够有很好的性能,将其performance与标准的pixel-based采样方案进行比较。最终结论是:CS在以下情况下优于传统像素采样:

  • if the underlying image is highly compressible or
  • or if the SNR is sufficiently large
外[9]还比较全面的介绍了对piecewise constant这个类别的图像进行压缩传统的做法。并给出了相应的squared approximation error作为性能衡量标准。


07年L. Gan基于[6]的理论提出了block compressed sensing[7]。这篇文章是我认为很多后续对图像压缩的研究的基础,非常建议一读。


08年MSRA的一帮人提出了将图像的coefficients进行分解[8],对于dense的部分进行conventional encoding (变换编码),sparse的部分进行CS。


[7]和[8]都给出了PSNR效果,是很好的比照对象。


[14]是基于[6]的一个改进。除了算法部分,我推荐看一下Background这一部分,它比较完整的介绍了当前CS的一些算法。同时,这篇文章也对[6]进行了review,有助于理解[6]的算法。另外,这篇文章给出了不同CS算法下的PSNR,有比较系统的仿真结果,可供参考。


11年,[15]提出了基于[6]的另一种改进。作者对稀疏系数矩阵进行random permutation从而使稀疏度分布趋近一致,从而提高CS的性能。


08年T. Wan等人提出将cs应用于image fusion[10],09年A. Divekar也作了类似的研究[11]。image fusion就是将从不同sensor对同一个场景的图像结合起来一发现其中的信息。有兴趣的同学可以看看这两篇文章,这里不多做解释。


09年开始,研究者开始考虑colored image,从而将CS从2D image转到了3D。[12]的作者提出使用Bayer Filter以及Joint Sparsity Model来exploit不同色彩信道之间的相关性。结果显示这种方法比普通的对各个信道独立进行CS效果更好。


08年,CS界的一位牛人J. Romberg使用noiselet概念(类似wavelet),并且使用min TV而不是min l1进行图像重建[13]。TV中的梯度运算可以促进smoothing,更加适合images。这也是大多数CS imaging的恢复算法。但是Noiselet用于稀疏基在图像方面的后续研究我还没有看到,有可能是我遗漏了。


以上就是05年到11年大部分关于cs用于image方面的paper综述,希望有助于大家理解。
有错误之处欢迎指出。


[1] Roubust uncertainty principles: Exact Signal Reconstruction from Highly Incomplete Frequency Information
[2] Near optimal signal recovery from random projections: Universal Encoding Strategies?
[3] Compressed Sensing
[4] Introduction to compressed sampling
[5] Signal reconstruction from noisy random projections
[6] Practical Signal Recovery from Random Projections
[7] Block compressed sensing of natural images
[8] Image representation by compressed sensing
[9] Compressive Sampling VS. Conventional Imaging
[10]Compressive image fusion
[11]Image fusion by compressive sensing
[12]Compressive imaging of color images
[13]Imaging via Compressive Sampling
[14]Block compressed sensing of images using directional transforms
[15]Compressive Sampling with Coefficients Random Permutations for Image Compression

Tuesday, January 24, 2012

Apache2.2 + PHP5.3.3 Windows下的配置


昨天给自己配了一下PHP的环境,弄了有一会。
网上的教程也看了,还是自己写一下,以后可以参考,呵呵。

首先要注意的是这个教程有几个前提要求:
1. Windows; Linux下的我没配过,所以不是很清楚。
2. Apache2.2;版本比较重要,不同的版本也有可能是不一样的配法~所以,如果是要配置其他版本的话,请换关键字搜索~~呵呵~
3.PHP5.3.3; 同样是版本的问题~

好了,现在开始配置吧。
1. 首先,先要下Apache2.2。我下的是httpd-2.2.16-win32-x86-no_ssl.msi,安装到C:\Program Files里了
2. 然后,把PHP5.3.3也下下来,注意,要下php-5.3.3-Win32-VC6-x86.zip这个文件,不要有nts,也不要是VC9什么的。我一开始就下错了,然后缺文件之类的- -。
这个就直接解压缩就好了,放在C:\php目录下。(这个目录底下应该就直接是文件了,不是解压得到的文件夹哦)。

3. 装好Apache之后,可以打开Apache服务,然后访问localhost一下,看看是不是装好了。基本上这步不会出问题的。
4. 配置PHP。
关键步骤~(我引用了http://www.blogjava.net/zyw090111/archive/2010/08/07/328197.html里面的方法),不过有一些注释的地方是我做错的点。
1) 配置PHP5.3.3,打开php安装目录(C:\php)可以看到目录下有两个这样的文件 php.ini-development和php.ini-production,第一个是开发使用的配置文件,第二个是标准的生产环境的配置。
2)选择php.ini-development复制一份到同目录下,并改名为php.ini使用文本工具打开,查找extension_dir,可以看到两个,选择On windows:
下面的那个并去得前面的分号修改为extension_dir = "C:/php/ext",读者根据自己的目录结构配置,目的是找到和php.ini同目录下的ext文件夹中的扩展库。
!!这里一定要注意的是,不要只改了目录,而没有把分号去掉- -分号没去掉这句话是不起作用的。
检测方法是,写一个index.php文件
<? phpinfo()?>放在Apache的访问的文件夹下(可以查看Apache22/conf/httpd.conf,搜索DocumentRoot),默认是Apache22/htdoc这个文件夹。然后访问localhost/index.php,可以看到

Configuration File (php.ini) PathC:/Windows
Loaded Configuration FileC:/php/php.ini

以及

extension_dirC:/php/extC:/php/ext

这就说明配置对了,否则,需要在下面的步骤中把文件拷贝到相应目录。
3)查找extension=php_,去掉
extension=php_curl.dll、extension=php_gd2.dll、extension=php_mbstring.dll、
extension=php_mysql.dll、extension=php_mysqli.dll、extension=php_pdo_mysql.dll、extension=php_xmlrpc.dll
前面的分号。查找short_open_tag = Off把它修改成short_open_tag = On,让其支持短标签。
这一步的作用是开启一些功能,如curl,mysql等。而这些dll文件都是放在C:/PHP/EXT目录下的,也就是由上一步设置的extension_dir决定的。
4)复制php5ts.dll文件到WINDOWS/system32目录下,只有php-5.3.3-Win32-VC6-x86版本中才有php5ts.dll php-5.3.3-nts-Win32-VC6-x86版本是没有的。
5)复制libeay32.dll ssleay32.dll(C:/PHP)到C:/windows下。
(之所以有这一步,可能是因为类似的某个目录没有配好,默认在C:/windows下。但暂时我还不知道在哪配,所以也就只好默认了- -)


这样,php的配置基本就完成了、

Wednesday, January 18, 2012

免费软件打造你的学术PC

上一篇博文写的关于如何打造你的iPad成为学术利器
很多软件是和电脑之间需要同步的 所以 同步是下列软件共有的特点
另外 本篇博文还将介绍一系列自身管理的软件


1. Tiddlywiki + Git + Github
Tiddlywiki 是一款基于Html的单文件个人知识管理系统 十分容易上手
你可以在上面写whatever you want 随意记录你遇到过的各种问题以及如何解决
可以记录你的research diary
可以写paper review
etc...
而且它有很强大的plugin支持 可以安装各种你想要的功能
这么多个人知识管理系统里推荐他的原因是他是单文件 所以便携 任何场合只要有浏览器就能打开
另外他是唯一一个可以跨平台的wiki 你可以随意在windows linux mac之间切换
并且他和Git搭配起来功能可以发挥到极致

Git是一款版本管理软件 有过项目开发经验的同学都应该接触过这个软件
如果没有用过 强烈建议学习一下 很容易上手 对于代码的管理绝对是必不可少的软件
这里使用Git一是为了管理你的wiki版本 这样即使某个版本的wiki崩溃 也能很快回滚到之前的状态
另一个目的是同步 结合Github 你可以随时随地从你的github库上clone你的wiki 并且push你的修改 当然 你也可以使用dropbox等来完成类似功能(但是只有git才有这么强大的版本管理能力)

下面是我自己的两个基于tiddlywiki的实现,大家可以参考
我的tiddlywiki: http://funny.tiddlyspot.com
我的Homepage: http://hfang2.tiddlyspot.com

2. mGSD
对时间管理有一定了解的人都应该知道著名的Get Things Done
没有看过的同学强烈推荐看以下这本讲时间管理的书
现在有很多GTD的软件 这里介绍基于tiddlywiki的mGSD
个人对tiddlywiki情有独钟 当然喜欢它的各种应用
mGSD算是tiddlywiki中发展很健全的一个例子 它完全实现了GTD的所有功能
又有tiddlywiki的特性 当然你也可以搭配上git进行版本管理

3. Live Mesh
上次介绍过这个软件 这个软件的牛逼之处是你不但可以在不同电脑之间同步文件夹 还可以远程登录 简直就是神器啊!你可以在实验室让打开你的代码跑仿真 也可以在家里打开实验室电脑打印文件 总之 如果你有两个以上的常用电脑 这个软件绝对是TOP 1

4. MindManager
这是个思维导图软件 上次在ipad app推荐的时候推荐个这个软件
这也是为什么我推荐他的原因 他可以更好的和ipad搭配使用 他可以把文件上传到其网上空间 和ipad同步
当然 你也可以用freeMind/XMind 然后使用Dropbox和ipad同步 但是似乎ipad MindManager上兼容性还不是太好
不过 这个不是个免费的软件 但是我相信这难不倒我们强大人中国人民的智慧的~呵呵

5. Mendeley
好了 这个是个免费文献管理软件 这个软件可以把你的文献上传到网络空间 可以在不同电脑之间同步管理 同时可以在ipad上同步文献 随时随地看paper 呵呵

6. Dropbox
这也是 为了结合ipad使用的软件 可以随时同步你的文件 唯一的缺点就是必须把文件放在dropbox这个文件夹下 所以我之前介绍的Live Mesh就是为了弥补这个不足所用的软件

7. Evernote
强大的云笔记软件 可以随时在手机 平板 各处电脑记录事件 这可以弥补在手机上浏览mGSD不方便的问题 也可以作为记录一些备忘录的工具

8. Vim
超强的text editor 用过linux的人都应该知道它 比记事本强大很多
可以有很多配置 一开始用可能会不习惯 但是一旦上手 绝对是text editor中的神器

9. TexMaker
Latex编辑器 写paper的专业工具 在格式排版方面 比word好用很多

Saturday, January 14, 2012

免费app打造你的学术iPad

iPad除了用来玩 对于researcher来说 当然也可以用来作为一个学术利器
下面介绍的应用基本上都是free的 所以无论你的ipad有木有越狱 都是ok的


  1. Mendeley
    这是一款免费的文献管理软件 你可以在电脑上管理你的所有文献 同步到服务器端 在ipad上你也可以看到你电脑上所有的文献
  2. Dropbox
    很强的一款同步文件的软件 可以在电脑和ipad之间同步很多文档 注册就有2G免费空间 它之所以强大是因为基本上需要用到数据共享的app(不管ipad android)都会整合dropbox 所以绝对是不可或缺
  3. SlideShark
    播放PPT的软件 可以让你的ipad播放PPT文件 需要电脑通过软件Upload到服务器进行同步
  4. 金山词霸
    没啥好说的 查单词
  5. Caculator++
    免费的计算器软件
  6. Evernote
    很好用的云端记事本软件 可以和电脑 手机同步 我用它来记一些小事情 其他事情我使用mGSD 一款基于tiddlywiki的GTD工具 有机会下次介绍
  7. pdf-notes
    免费的看pdf的软件 并且可以作注释 功能很强大
  8. CloudOn
    编辑 查看office文档的软件
  9. iNoteBook Lite
    集合日历 日记 笔记 文档管理于一身的软件 有兴趣的朋友可以使用一下
  10. PocketCloud
    远程登录电脑软件 可以在任何地方登录你的电脑
  11. WifiSendFree
    让你的ipad成为电脑的键盘和鼠标
  12. Mindjet
    思维导图工具 可以和电脑的MindManager一起使用 一个用来编辑 ipad主要用来演示 MindManager的破解版大家好好利用google就好了
  13. Timeli
    项目日程管理软件 用户界面友好
  14. OfficeDrop
    可以随时将纸质文档通过摄像头扫描保存为电子文档并上传到服务器保存
  15. i-Clickr
    一款控制电脑PPT播放的软件 这个软件是收费的 但是是坐presentation的绝对利器 可以设置timer提醒时间 可以看ppt的备注 控制PPT播放 进行涂鸦等等 所以花钱买or越狱装都是值得的


Monday, January 9, 2012

推荐两款文件夹同步软件Live Mesh和SyncToy

大家现在不免有多台电脑 比如实验室一台 家里一台
所以同步文件夹就比较麻烦 需要用U盘拷来拷去

Dropbox是一款不错的同步软件 可以和tablet ipad等同步 但是他需要把所有的文件放在一个文件夹下 比较麻烦
Windows Live Mesh 是Microsoft推出的功能 可以将文件夹同步到网络端 从而在不同的机器上同步 而且注册就有5G的免费空间 并且可以远程登录桌面 非常好用

另一款软件SyncToy主要用于局域网同步或者本机文件夹备份 比较适合需要同步移动硬盘文件 或者同一个局域网的电脑文件夹 但是对于不同局域网的文件夹就比较复杂了

WikiCFP : Call For Papers of Conferences , Workshops and Jounals

发现一个网站 可以用来关注最近开的conferences workshops等消息
也可用来发布消息
WikiCFP : Call For Papers of Conferences , Workshops and Jounals

Sunday, January 8, 2012

X10i Root 2.3.3教程

系统要求:
android 2.3.3

准备工作:
下载 Flashtool0.4.2.0.rar

Root
  1. 安装驱动
    1. 解压缩 flashtool/drivers 中的X10_ADB_drivers.zip
    2. 设备管理器-> X10 (未知USB设备)-> 更新驱动 (选择文件夹 Flashtool -> drivers)
  2. 打开X10FlashTool.exe
  3. 手机设置 未知来源 (设置->应用程序)和 USB调试,保持唤醒(设置->应用程序->开发)
  4. 连接手机
  5. 等待Root图标亮起 点击ROOT
  6. 期间会重启
  7. 显示'root access allowed',表示root成功

图文教程可以参考:http://sebbs.cnmo.com/thread-10614705-1-1.html

FAQ:
  • Root图标不亮起是为什么?
检查驱动是否安装成功(按照步骤1)
  • 刷机失败 启动时一直卡在开机画面
如果驱动没有安装正确,或者没有开启未知来源和USB调试,或者使用低版本的FlashTool,都有可能出现该情况
可以用update service(SE提供的更新软件 升级过系统的人应该都知道)重新更新一遍就好了

Friday, January 6, 2012

TrackMyTour: 记录旅行的iPad app

可以在当前地点创建图片 纪录 有点像日记 不过结合地点和图像 很有意思

Clibe: 一个有意思的记笔记的iPad app

之前一直用的是Evernote 当然很好用
不过clibe不同的是 它可以作手写板 可以涂鸦 可以随意乱画
而且能够创建不同的笔记本
可以用来头脑风暴 做小型思维导图

推荐大家试用 免费的咯

Thursday, January 5, 2012

The reason for using 8x8 as the block size in image processing

The DCT usually use 8x8 as the block size to be applied to images. This is a trade-off between computational complexity, compression speed and quality.

A lot of research work show that after 15 or 20 pixels, the relationship among them begins to reduce; that is to say, a group of similar pixels usually lasts for 15 to 20, after that, the amplitude would change.