TILT阅读报告
相关概念调研：
- low rank matrix
Suppose that we have a rank-r matrix A of size m x n, where r << min(m,n). In many engineering problems, the entries of the matrix are often corrupted by errors or noise, some of the entries could even be missing, or only a set of measurements of the matrix is accessible rather than its entries directly. In general, we model the observed matrix D to be a set of linear measurements on the matrix A, subject to noise and gross corruptions i.e., D = L(A) + η, where L is a linear operator, and η represents the matrix of corruptions. We seek to recover the true matrix A from D.
http://blog.sina.com.cn/s/blog_49b5f5080100yut4.html
http://blog.csdn.net/smilebluesky/article/details/41154419 （低秩矩阵在机器视觉中的理解）
http://blog.csdn.net/wangchangqing2008521/article/details/26961467
（Low-Rank模型及其在图像分析中的应用）
http://www.cnblogs.com/txg198955/p/4096003.html （RASL & TILT）
http://blog.csdn.net/jzwong/article/details/51959131 （TILT）
http://blog.sina.com.cn/s/blog_631a4cc401019gqx.html （CVPR关于low-rank的文章）
LMaFit is a MATLAB package that currently solves the following problems
3. Low rank approximation
In mathematics, low-rank approximation is a minimization problem, in which the cost function measures the fit between a given matrix (the data) and an approximating matrix (the optimization variable), subject to a constraint that the approximating matrix has reduced rank.
https://en.wikipedia.org/wiki/Low-rank_approximation
4. Low-rank method
Chapter8 Sparse and Low-Rank Methods
5. Sparse method
Chapter8 Sparse and Low-Rank Methods
6. Convex optimization
- Image Congealing (Alignment)
http://www.docin.com/p-1723497117.html
文章题目叫做Transform Invariant Low-rank Texture
可以简单翻译为"变换不变的低秩纹理"
低秩纹理
首先来说一下什么是低秩纹理。文章中的定义比较复杂。
把图像定义为一个二维矩阵I0，并将其将y作为单变量。如果I0张成的低维线性子空间的基底的个数为r<=k, k为我们给定的一个正整数，那么我们就称I0为秩为r的纹理。
简单说，低秩矩阵就是一个图像模型，可以用来描述规则化的纹理图像的模型。举个例子：
从上面可以看出，一个水平或者竖直的边(e)可以看成秩为1的纹理，一个角(f)可以看成秩为2的纹理。从广义上讲，低秩纹理的概念包含了许多传统的局部纹理特征。通过该定义可以看出，包含规则对称模式的图像更容易形成低秩纹理。这样，低秩纹理(Low-rank texture) 的概念包含了更广泛的特征(feature)和区域(region)，而不仅仅只局限于角点(corners)和边(edges)等特征。
在实际应用中，2D纹理图像是用m×n的矩阵来表示的，那么，当矩阵的秩r«min{m,n}时，我们可以将该图像视为低秩纹理。
一、摘要
在3D场景中，低秩纹理随处可见。但是，从3D场景映射到2D图像之后，由于变形、退化和遮挡，原本的低秩纹理便不再有低秩的性质。
如图所示，当边简单的不再严格水平或竖直，那么该图像的秩便是满秩，不再是低秩纹理。
这篇文章的主要工作是从存在退化和形变的2D图像中提出3D场景中的低秩纹理(Low-texture)。
低秩纹理包含了图像中许多有意义的几何结构，包括一些传统的局部特征，包括边缘、角点，以及许多在自然环境和人造物体中普片存在的规则对称模式。
文章的方法利用了最近取得重大突破的凸优化方法，该方法能够鲁棒地从包含粗略稀疏误差(gross sparse errors)的情况下对高维低秩矩阵进行恢复。后面将对该方法进行详细介绍。
文章方法可以从包含显著仿射和射影退化的区域中准确地恢复出其中的低秩纹理区域以及变换。文章做了许多实验来证明该方法对许多情况是有效的。
二、Introduction
在计算机视觉的基础研究中，最基本的一个问题是确定图像中的特征点和显著区域。这些点和区域是其他更高层次的视觉应用中的基础材料，包括图像匹配、三维重建、物体识别、场景理解等等。
在过去的研究当中，提出了许多特征点和显著区域的提取方法，包括canny边缘检测算法，harris角点检测，以及纹理基元等等(textons)。
这些特征点和区域的一个重要应用就是建立点对的匹配和测量同一物体的两幅图像之间的相似性。如果图像是从不同的角度以及不同的成像条件下获得的，那么该问题将变得非常复杂。因此，如何能够得到在视角和光照的变换下得到稳定的或保持不变的图像特征成为研究的热点。在过去的几十年，提出了许多不变特征和描述子，有些基于马尔可夫模型，有些基于小波等等。应用最为广泛的不变特征是SIFT，但是不是仿射的，虽然后续被解决affine-SIFT，但是不是摄影的。从我们现有的知识来看，没有真正的射影不变量。并且，这些方法并不能处理其他退化，包括光照变化，部分遮挡以及退化等等。
虽然有很多努力，但是却陷入了一个困境，现有的方法无法解决：一方面，严格的不变量几乎没有，只有一个拓扑意义下的不变量(ART-attributed Reeb tree)，其他的都是近似的，或者是包含了某些限制条件。另一方面，3D场景中包含了许多规则的结构。
因此，本文主张通过仿射或射影变换，从2D图像中提取出确定的不变结构。因此，我们将提取不变量的问题转换为了一个恢复问题(inverse problem)。因此，需要用到新的计算工具-利用凸优化(convex optimization)的方法进行矩阵秩的最小化(matrix rank minimization)。
该方法的几个特点：
- 直接利用像素信息，不会产生中间特征
- 对于形变、遮挡、退化引起的误差鲁棒(robust to gross errors)
- 对任意大小、任意位置都适用。
三、TILT的定义以及TILT提取的公式化描述
低秩纹理定义
下面来说一下什么是低秩纹理。文章中的定义比较复杂。
把图像定义为一个二维矩阵I0，并将其将y作为单变量。如果I0张成的低维线性子空间的基底的个数为r<=k, k为我们给定的一个正整数，那么我们就称I0为秩为r的纹理。
简单说，低秩矩阵就是一个图像模型，可以用来描述规则化的纹理图像的模型。举个例子：
从上面可以看出，一个水平或者竖直的边(e)可以看成秩为1的纹理，一个角(f)可以看成秩为2的纹理。从广义上讲，低秩纹理的概念包含了许多传统的局部纹理特征。通过该定义可以看出，包含规则对称模式的图像更容易形成低秩纹理。这样，低秩纹理(Low-rank texture) 的概念包含了更广泛的特征(feature)和区域(region)，而不仅仅只局限于角点(corners)和边(edges)等特征。
在实际应用中，2D纹理图像是用m×n的矩阵来表示的，那么，当矩阵的秩r«min{m,n}时，我们可以将该图像视为低秩纹理。
对于一个低秩纹理，很明显，矩阵的秩r对于尺度和平移变换是保持不变的。
g和I0具有相同的秩。这个变换群可以描述为如下形式：
Remark1 与随机纹理的区别
变形的和退化的低秩纹理
在真实的图像中，我们并不会看到真正的低秩纹理，原因有二：
- 视角变换引起的纹理矩阵的变化
- 量化、噪声、遮挡等引起的纹理矩阵的变化
我们必须对这些因素进行建模，并找到方法来消除他们。
-形变模型
图像I(x,y)是低秩纹理I0(x,y)从不同的视角观察到的图像，该形变过程可以描述为：
In this paper, we assume G is either the rotation group SO(2), or the 2D affine group Aff(2), or the homography group GL(3) acting linearly on the image domain.
T是一个确定的李群，在本文中也可是假设为旋转群，2维仿射群或单应群。
-退化模型
除了变换之外，还会有噪声、遮挡、或者周围的干扰背景，可以用下模型来描述：
E成为误差矩阵(erroe matrix)，在文章中，假设图像中只有一小部分具有较大的误差，因此E可以看做是一个稀疏矩阵(sparse matrix)。
因此，文章的最终目标可以用以下问题来建模：
该问题可以退化为如下形式的优化问题：
||E||0代表E中的非0元素。
那么，问题变成了，我们要在约束条件下，找到具有最低秩的纹理I0，和最少非0元素的误差E。这个过程称为TILT。
Remark2 与仿射不变特征的区别
WYSIWYG-what you see is what you get
Remark3 与RASL的区别
Remark4 与TPCA的区别
- 算法
该问题可以是一个NP难问题，具体见
Sparse Representation And Low- Rank Matrix Recovery
--Chapter 8 Sparse and Low-Rank Methods
要求目标函数是凸函数，变量所属集合是凸集合的优化问题。或者目标函数是凸函数，变量的约束函数是凸函数（不等式约束时），或者是仿射函数（等式约束时）。
http://blog.csdn.net/sunmenggmail/article/details/13998255
基本解法
经过改进后，变成了如下优化问题：
为什么用l1范数来近似l0范数
L0范数是指向量中非0的元素的个数。如果我们用L0范数来规则化一个参数矩阵W的话，就是希望W的大部分元素都是0。这太直观了，太露骨了吧，换句话说，让参数W是稀疏的。OK，看到了"稀疏"二字，大家都应该从当下风风火火的"压缩感知"和"稀疏编码"中醒悟过来，原来用的漫山遍野的"稀疏"就是通过这玩意来实现的。但你又开始怀疑了，是这样吗？看到的papers世界中，稀疏不是都通过L1范数来实现吗？脑海里是不是到处都是||W||1影子呀！几乎是抬头不见低头见。没错，这就是这节的题目把L0和L1放在一起的原因，因为他们有着某种不寻常的关系。那我们再来看看L1范数是什么？它为什么可以实现稀疏？为什么大家都用L1范数去实现稀疏，而不是L0范数呢？
L1范数是指向量中各个元素绝对值之和，也有个美称叫"稀疏规则算子"（Lasso regularization）。现在我们来分析下这个价值一个亿的问题：为什么L1范数会使权值稀疏？有人可能会这样给你回答"它是L0范数的最优凸近似"。实际上，还存在一个更美的回答：任何的规则化算子，如果他在Wi=0的地方不可微，并且可以分解为一个"求和"的形式，那么这个规则化算子就可以实现稀疏。这说是这么说，W的L1范数是绝对值，|w|在w=0处是不可微，但这还是不够直观。这里因为我们需要和L2范数进行对比分析。所以关于L1范数的直观理解，请待会看看第二节。
OK，来个一句话总结：L1范数和L0范数可以实现稀疏，L1因具有比L0更好的优化求解特性而被广泛应用。
http://blog.csdn.net/lj695242104/article/details/38801025
为什么要用核范数来近似rank()
核范数||W||*是指矩阵奇异值的和，英文称呼叫Nuclear Norm。这个相对于上面火热的L1和L2来说，可能大家就会陌生点。那它是干嘛用的呢？霸气登场：约束Low-Rank（低秩）。
好了，低秩有了，那约束低秩只是约束rank(w)呀，和我们这节的核范数有什么关系呢？他们的关系和L0与L1的关系一样。因为rank()是非凸的，在优化问题里面很难求解，那么就需要寻找它的凸近似来近似它了。rank(w)的凸近似就是核范数||W||*。
http://blog.csdn.net/lj695242104/article/details/38801025
nuclear norm 是奇异值的和，rank是非零奇异值的个数。nuclear norm能近似rank就跟l_1 norm能近似l_0norm一样。
矩阵的范数
0范数是指矩阵非零元素的个数
1范数是矩阵所有元素绝对值的和
2范数对应欧式距离
无穷范数对应矩阵所有元素绝对值中最大的那个值
核范数||W||*是指矩阵奇异值的和，英文称呼叫Nuclear Norm
http://blog.csdn.net/liyuan123zhouhui/article/details/51446116
文章中说，虽然目标函数是凸函数，但是约束条件是非线性的，在t属于G的情况下；因此该问题不是一个凸优化问题。因此，可以把约束条件进行线性化
A∇I 是关于图像变换矩阵参数的雅克比行列式，那么该优化问题又退化为
经过改进后的迭代凸优化算法Solution by Iterative Convex Optimization
拉格朗日乘子法大家应该都知道，就是求函数f(x1,x2,...)在g(x1,x2,...)=0的约束条件下的极值的方法。
假设需要求极值的目标函数(objectivefunction)为f(x,y)，限制条件为φ(x,y)=M设
求出x,y,λ的值，代入即可得到目标函数的极值。
增广拉格朗日乘子法，不仅添加了拉格朗日项，还添加了二次惩罚项。
这个二次惩罚项具体是用来干嘛的也没有理解明白。
ALM算法是用来求解增广拉格朗日乘子法的一般方法，
ALM算法的迭代版本在Bertsekas (2004)中给出，具体在这就不赘述了。
TILT问题的ADM版本
对于本文的优化问题，可以用增广拉格朗日乘子法来求解：
利用ALM迭代算法来进行计算就可以得到结果，具体细节也不赘述了。
通过实验比较，该方法要比其他的凸优化方案要快很多。
ADM又是ALM的一个改进版本，简单快速，但是收敛问题仍有待研究。以下是TILT算法的ADM版本：
其中SVD计算是该算法中最耗时的一步。
实现细节
低秩纹理的定义中有几个不确定的点：低秩纹理对尺度和平移变换具有不变性，因此，我们需要消除这些不确定因素。算法1中，每一次迭代开始，图像的像素值要重新归一化，否则就会收敛到黑色像素点或黑色区域。
对于射影变换，我们要固定两个对角点。一个射影矩阵包含8个自由度，低秩纹理包含两对平行线，xy轴对应两个消失点，两个消失点和两个固定点就组成了8个限制条件，就可以把矩阵确定下来。
形状Shape from Low-rank textures
将2D图像建模为transformed low-rank plus sparse structures model
将2D图像还原低秩纹理的问题，建模为一个Sparse Representation And Low- Rank Matrix Recovery的开放问题，并利用凸优化的方法进行求解。
该方法可以处理许多仿射和射影的问题，并且不依赖与局部特征，提供了一种新的解决途径。
用低秩纹理这个性质来校正图像，直接从图像中的不变特征出发，在原始的输入图像上选取变换区域进行处理。
在该算法的模型构建过程中，加入对噪声图像的估计和约束，使得模型对图像中少量的噪声具有鲁棒性，其校正效果也比传统的方法有很大的改善。
一是平面问题，当输入图像的变换区域不再同一平面时，校正失败。
另一个是阴影问题，TILT基于模型是低秩纹理(low-rank)+稀疏噪声(sparse)，因此，存在较大阴影时，校正失败。
