图像分析的数据结构

1 图像数据表示的层次

四个层次：

1. 图标图像(iconic images)：最底层的表示，有含有原始数据的图像组成，原始数据也就是像素亮度数据的整数矩阵。为了突出对后续处理重要 的图像的某些方面，需要进行预处理（滤波或边缘锐化）
2. 分割图像(segmented images)：为可能属于同一物体的区域。
3. 几何表示(geometric representation)：保存2D和3D形状知识。
4. 关系模型(relational models)：使我们能更有效地，并且在更高的抽象层次上的处理数据。

2 传统图像数据结构

矩阵，链，图，物体属性表，关系数据库

2.1 矩阵

矩阵是底层图像表示的最普通的数据结构，矩阵元素是整型的数值。

特殊图像

• 二值图像(binary image)：仅有两个亮度级别的图像，用仅含有0和1的矩阵来表示
• 多光谱图像(multispectral image)：可以用多个矩阵来表示，每个矩阵含有一个频带的图像。
• 分层图像数据结构(bierarchical image data structures)：用不同的分辨率的矩阵来获得。

共生矩阵(co-occurrence matrix)

​ 它是亮度为zz<script type="math/tex" id="MathJax-Element-1">z</script>的像素(i1,j1) $(i_1,j_1)$<script type="math/tex" id="MathJax-Element-2">(i_1,j_1)</script>和亮度为y的像素(i2,j2)(i2,j2)<script type="math/tex" id="MathJax-Element-3">(i_2,j_2)</script>的具有空间关系的两个像素的概率估计。

​ 假设这个概率仅依赖于亮度zz<script type="math/tex" id="MathJax-Element-4">z</script>的像素和亮度y $y$<script type="math/tex" id="MathJax-Element-5">y</script>的像素之间的某个空间关系rr<script type="math/tex" id="MathJax-Element-6">r</script>，那么关于关系r $r$<script type="math/tex" id="MathJax-Element-7">r</script>的信息就记录在方形的共生矩阵C中，它的维数对应图像的亮度级别数。

算法：关系rr<script type="math/tex" id="MathJax-Element-8">r</script>的共生矩阵Cr(x,y) $C_r(x,y)$<script type="math/tex" id="MathJax-Element-9">C_r(x,y)</script>

1. 置Cr(z,y)=0Cr(z,y)=0<script type="math/tex" id="MathJax-Element-10">C_r(z,y) =0</script>,对于所有的z,y∈[0,L]z,y∈[0,L]<script type="math/tex" id="MathJax-Element-11">z,y\in[0,L]</script>,L是最大的亮度。
2. 对于图像中所有的像素(i1,j1)(i1,j1)<script type="math/tex" id="MathJax-Element-12">(i_1,j_1)</script> ，找到与像素(i1,j1)(i1,j1)<script type="math/tex" id="MathJax-Element-13">(i_1,j_1)</script>有关系r的像素(i2，j2)(i2，j2)<script type="math/tex" id="MathJax-Element-14">(i_2，j_2)</script>,做Cr[f(i1,j1),f(i2,j2)]=Cr[f(i1,j1),f(i2,j2)]+1Cr[f(i1,j1),f(i2,j2)]=Cr[f(i1,j1),f(i2,j2)]+1<script type="math/tex" id="MathJax-Element-15">C_r[f(i_1,j_1),f(i_2,j_2)] = C_r[f(i_1,j_1),f(i_2,j_2)]+1</script>.

积分图像

​ 描述全局信息的矩阵表示方法。积分图像的构造方式是位置(i,j)(i,j)<script type="math/tex" id="MathJax-Element-16">(i,j)</script>处的值ii(i,j)ii(i,j)<script type="math/tex" id="MathJax-Element-17">ii(i,j)</script>是原图像的(i,j)(i,j)<script type="math/tex" id="MathJax-Element-18">(i,j)</script>左上角所有像素的和：ii(i,j)=∑k≤i,l≤jf(k,l)ii(i,j)=∑k≤i,l≤jf(k,l)<script type="math/tex" id="MathJax-Element-19">ii(i,j) = \sum\limits_{k\le i,l\le j}f(k,l)</script>

算法：积分图像的构建

1. 用s(i,j)s(i,j)<script type="math/tex" id="MathJax-Element-20">s(i,j)</script>表示行方向的累加和，初始化s(i,−1)=0s(i,−1)=0<script type="math/tex" id="MathJax-Element-21">s(i,-1) =0</script>

2. 用ii(i,j)ii(i,j)<script type="math/tex" id="MathJax-Element-22">ii(i,j)</script>表示一个积分图像，初始化ii(−1,i)=0ii(−1,i)=0<script type="math/tex" id="MathJax-Element-23">ii(-1,i)=0</script>

3. 逐行扫描图像，递归计算每个像素(i,j)(i,j)<script type="math/tex" id="MathJax-Element-24">(i,j)</script>行方向的累加和s(i,j)s(i,j)<script type="math/tex" id="MathJax-Element-25">s(i,j)</script>和积分图像ii(i,j)ii(i,j)<script type="math/tex" id="MathJax-Element-26">ii(i,j)</script>的值

   ​ s(i,j)=s(i,j−1)+f(i,j)s(i,j)=s(i,j−1)+f(i,j)<script type="math/tex" id="MathJax-Element-27">s(i,j) = s(i,j-1)+f(i,j)</script>

   ​ ii(i,j)=ii(i−1,j)+s(i,j)ii(i,j)=ii(i−1,j)+s(i,j)<script type="math/tex" id="MathJax-Element-28">ii(i,j) =ii(i-1,j)+s(i,j)</script>

4. 扫描图像一遍，当到达图像右下角像素时，积分图像iiii<script type="math/tex" id="MathJax-Element-29">ii</script>构造好了。

积分图像这个数据结构主要用来快速计算多个尺度的简单矩阵图像特征。

2.2 链

​ 链在计算机视觉中用于描述物体的边界。链的元素是一个基本符号，这种方法使得在计算机视觉任务中可以使用任何形式的理论。链适合组织成符号序列的数据，链中相邻的符号通常对应于图像中邻接的基元。

2.3 拓扑数据结构

​ 图(graph)：G(V,E)G(V,E)<script type="math/tex" id="MathJax-Element-62">G(V,E)</script>是一个代数结构，有一组结点V=v1,v2,⋯,vnV=v1,v2,⋯,vn<script type="math/tex" id="MathJax-Element-63">V = {v_1,v_2,\cdots,v_n}</script>和一组弧E=e1,e2,⋯,enE=e1,e2,⋯,en<script type="math/tex" id="MathJax-Element-64">E = {e_1,e_2,\cdots,e_n}</script>构成。每条弧ekek<script type="math/tex" id="MathJax-Element-65">e_k</script>代表一对无次序的结点{vi,vj}{vi,vj}<script type="math/tex" id="MathJax-Element-66">\{v_i,v_j\}</script>。结点的度数等于该结点所具有的弧数。

​ 赋值图(evaluated graph)：指弧和结点或两者都带有数值的图。

​ 区域邻接图(region adjacency graph)：其中结点对应与区域，相邻的区域用弧连接起来。

2.4 关系结构

3 分层数据结构

3.1 金字塔

M型金字塔(M-pyramids)矩阵

​ M型金字塔：是一个图像序列{ML,ML−1,⋯,M0}{ML,ML−1,⋯,M0}<script type="math/tex" id="MathJax-Element-73">\{M_L,M_{L-1},\cdots ,M_0\}</script>其中MLML<script type="math/tex" id="MathJax-Element-74">M_L</script>是具有与原图像同样的分辨率和元素的图像Mi−1Mi−1<script type="math/tex" id="MathJax-Element-75">M_{i-1}</script>是MiMi<script type="math/tex" id="MathJax-Element-76">M_i</script>降低一半分辨率得到的图像。通常我们只考虑维数是2的幂的方阵。

​ MM<script type="math/tex" id="MathJax-Element-77">M</script>型金字塔存储所有图像矩阵需要的像素个数为N2(1+14+116+⋯)=1.33N2 $N^2(1+\frac{1}{4}+\frac{1}{16}+\cdots )=1.33N^2$<script type="math/tex" id="MathJax-Element-78">N^2(1+\frac{1}{4}+\frac{1}{16}+\cdots) =1.33N^2</script>

T型金字塔(T-pyramids)树形

T型金字塔：树状结构。设2l2l<script type="math/tex" id="MathJax-Element-41">2^l</script>是原图像的大小（最高分辨率）。

定义：

1. 一个结点集合P={P=(k,i,j)}P={P=(k,i,j)}<script type="math/tex" id="MathJax-Element-42">P=\{P=(k,i,j)\}</script>使得级别k∈[0,L]k∈[0,L]<script type="math/tex" id="MathJax-Element-43">k\in [0,L]</script>，i,j∈[0,2k−1]i,j∈[0,2k−1]<script type="math/tex" id="MathJax-Element-44">i,j\in[0,2^k-1]</script>。
2. 一个映射FF<script type="math/tex" id="MathJax-Element-45">F</script>，定义在金字塔的结点Pk−1,Pk $P_{k-1},P_k$<script type="math/tex" id="MathJax-Element-46">P_{k-1},P_k</script>之间F(k,i,j)=(k−1,i div 2,j div 2)F(k,i,j)=(k−1,i div 2,j div 2)<script type="math/tex" id="MathJax-Element-47">F(k,i,j) = (k-1,i\ div \ 2,j\ div\ 2)</script> 。divdiv<script type="math/tex" id="MathJax-Element-48">div</script>表示整除

3. 一个函数VV<script type="math/tex" id="MathJax-Element-49">V</script>，将金字塔的结点P $P$<script type="math/tex" id="MathJax-Element-50">P</script>映射到ZZ<script type="math/tex" id="MathJax-Element-51">Z</script>，其中Z $Z$<script type="math/tex" id="MathJax-Element-52">Z</script>是对应于亮度级别数的所有数的子集合

   特点：

4. 对于给定的k,Tk,T<script type="math/tex" id="MathJax-Element-53">k,T</script>型金字塔的结点对应于M型金字塔的一些图像点，结点P={(k,i,j)}P={(k,i,j)}<script type="math/tex" id="MathJax-Element-54">P=\{(k,i,j)\}</script>集合的每个元素对应于M型金字塔的一个矩阵，称kk<script type="math/tex" id="MathJax-Element-55">k</script>为金字塔的层数。

5. 对于给定的k $k$<script type="math/tex" id="MathJax-Element-56">k</script> ，图像P={(k,i,j)}P={(k,i,j)}<script type="math/tex" id="MathJax-Element-57">P =\{(k,i,j)\}</script>构成金字塔的第kk<script type="math/tex" id="MathJax-Element-58">k</script>层的一个图像。
6. F $F$<script type="math/tex" id="MathJax-Element-59">F</script>是所谓的父亲映射，在T型金字塔中，除了根(0,0,0)(0,0,0)<script type="math/tex" id="MathJax-Element-60">(0,0,0)</script>之外的所有的结点PkPk<script type="math/tex" id="MathJax-Element-61">P_k</script>都有定义。

7. 除了叶子结点外，T型金字塔的每个结点都有4个子结点，叶子结点是第L层的结点，对应于图像的单个像素。

3.2 四叉树

​ 对T型金字塔的改进，除叶子结点外每个结点有4个子结点(西北NW，东北NE，西南SW，东南SE)，在每个层次图像被分解为4个象限。