第二节 空间数据压缩编码
二、自适应二维行程编码
1．基于线性四叉树的二维Morton行程编码
在线性四叉树的构造中，一种高效的算法是按Morton扫描顺序检查每个像元，并依Morton地址递增的顺序产生四叉树的结点。若按Morton扫描顺序将二维影像变成一维线性表，然后进行行程编码，便得到所谓的二维Morton行程编码。这种行程码突破了四叉树以方块为单元的限制（但失去了四叉树的性质），因而比四叉树具有更大的压缩比。形成这种码和解这种码的关键是了解Morton地址与对应的二维影像地址之间的关系。
设影像大小为2n×2n，y为行号，x为列号，Morton地址为morton，二维影像地址为offset=y·2n+x。
1）由Morton地址求对应的二维影像地址
int power2[]=｛1，2，4，8，16，32，64，128，256，512，1024｝；
long offset（int n，long morton）
｛
int x，y，1；
X=y=0；
for（i=0；i＜n；i++）｛
if（morton ＆1）！=0 x+=power2[i]；
if（morton ＆2）！=0 y+=power2[i]；
morton＞＞=2；
｝
return（（long）（y＜＜n）+x）；
｝
2）由二维影像的行号和列号求对应的Morton地址
long power4[]=｛1L，4L，16L，64L，256L，1024L，4096L，16384L，65536L，262144L，1048576L｝；
long morton（int n，int y，int x）
｛
intk；
long i，j；
i=j=OL；
for（k=0；k＜n；k++）｛
j+=（y％2）* power4[k]；
y＞＞=1；
i+=（x％2）* power4[k]；
X＞＞=1；
｝
return（2*j+i）；
｝
2．n-Morton行程编码
将大小为2m×2m的影像划分成大小为2n×2n（1≤n≤m）的子块，依Morton扫描顺序取各子块，各子块按行列顺序计算二维行程，子块（末子块除外）的最后一行程延续到下一子块，这样便得到整块影像的行程编码。我们将这种编码定义为n-Morton行程编码。当n=1时，1-Morton行程编码就是通常的二维Morton行程编码。当n=m时，m-Morton行程编码就是对整块影像按行列顺序扫描的二维行程编码。可见，n-Morton行程编码扩展了基于线性四叉树的二维Morton行程编码。
3．自适应二维行程编码
二维行程编码的效率取决于形成行程的顺序。不同的影像可能信息量变化很大，每块影像的局部也可能变化很大。由此，产生了随影像局部活动性变化而变化的自适应二维行程编码。其基本思想是：首先将影像分成较大的子块（假设大小为2m×2m），然后对各子块进行分析，计算子块的n-Morton（n=1，2，…，m）行程数，取其最小者为此子块的行程编码，各子块按各自最合适的顺序编码，最后形成整块影像的编码顺序，按此顺序计算行程，便可得到行程数较少、压缩比较大的行程编码。若对行程进行MHC编码，则又可进一步提高压缩比。
这种编码的效率比任何一种单一的Morton行程编码都高。对密集图形影像来说，若采用准等长编码，则行程编码的效率不一定高于按位面存贮的效率。对稀疏图形影像来说，无论采用何种行程编码，其效率都远高于按位面存贮的效率。一种较实用的存贮策略是，直接按位面存贮较密集的图形影像，而用自适应Morton行程编码存贮较稀疏的图形影像。