四元树编码在医学图象处理中的应用
作者：冯诗齐
单位：冯诗齐(上海三维计算机技术服务公司 上海200120)
关键词：四元树；二值图
数理医药学杂志000115
摘 要：介绍了四元树编码方法的原理及其在医学图象处理中的应用，并给出了四元树编码-解码的算法。
中图分类号：O 243
文章编号：1004-4337(2000)01-0029-03▲
1 引言
在图象处理领域，对二值光栅图象的压缩有多种方法，常用的如Freeman链码、十进制长链码、Wyle法游程长编码、2比特分隔游程长编码等[1]。这些方法都有各自的特点和局限性。九十年代初，出现了一种全新的称为四元树(或四叉树，quadtree)的数据结构用来表示二值图象。该方法将一个2n×2n的二值图象的二维几何区域递归地分解为四个象限，以树的一个结点来表示，这样一层层分下去直至分解到单个象素为止。
, http://www.100md.com
四元树结构的优点在于其规则的分解保证了数据的存贮、检索和处理的简单高效。由于分解可进行至象素，因此对于一个多边形二值图其边界几乎可以做到无限细分，可达到矢量或光栅结构所能达到的任何精度。通过改进其算法，可大大节省存贮空间。
这一新颖的表示法最初被用在GIS中表示地理信息。由于四元树结构很适合于将多边形的专题图(如地质图)与连续灰阶的光栅图象(如遥感和航空物探)组合起来，因而被人称之为超灵活结构。
2 四元树方法原理[2]。
设有一如图1(a)所示的2n×2n的二值图(围线内为二值图黑区，n=3)，则它的灰度值可用矩阵表示为图1(b)。按照上节所述的方法，将该区域的两个方向：X方向和Y方向各作二等分，分解为四个子区域，分别处于左上、右上、左下、右下位置(可以用方位NW，NE，SW，SE表示)。于是，若表示为树，则相当于将一个结点(根结点，代表整个二值图区域)分裂成为四个子结点。
, 百拇医药
图1 二值图
分别对这四个子结点再作如上所述的分裂，每个子区域又可对其X方向和Y方向各作二等分，分解为更小的四个子区，同样是以左上、右上、左下、右下的顺序排列。于是，根结点的四个子结点各自有了四个自己的子结点，它们是根结点的第二代子孙。这样一直分解下去，直至每个子区域都已是单个象素，不能再分解为止(见图2)。这时，构成了一棵有序正则(ordered regular)四元树，树中的每个非叶结点都有四个子结点，因而总的结点数应为4i(i=0-n)，而叶结点因其代表一个象素，所以它的值非0即1，即不是白结点就是黑结点。
图2 二值区域的分裂
注意到在四元树中，有些叶结点的父结点拥有的子结点全都具有相同的值。例如，上例中，结点6、7、8、9、10、11、14、16、21的子结点均为白，结点12、13、17、18、19的子结点均为黑，我们称它们是同质的。对于子结点同质的结点，将子结点去掉，而以其父结点来表示，这样，正则四元树就发生了变化，没有了子结点22、23、24、25，而它们的父结点6成为叶结点(白)。同样，结点7、8、9、10、11、14、16、21(白)；结点12、13、17、18、19(黑)现在成了叶结点。同理，结点6、7、8、9由于是同质的(全白)，故也可去掉，去掉后结点2成为叶结点(白)。于是，有序正则四元树如图3所示：
, http://www.100md.com
图3 非正则四元树表示
上述四元树在平面区域上所对应的二值区域为：
图4 二值区域
与正则四元树相比，非正则四元树存贮量大为减少。考虑到我们表示的是二值图象，因此还可以将表示方法再作简化，即只存贮黑(或白)结点，因为除了黑结点外剩下的就是白结点。于是，可将四元树表示为只有黑结点的单值四元树，这样可进一步压缩存贮空间。
3 线性四元树
用结点的位置码(locational code)来表示一个仅含有黑结点四元树，这样的表示法称为线性四元树(Linear Quadtree)方法。
由前面的讨论我们知道，对于一个非正则的四元树，它的结点应当包括两部分信息：
, 百拇医药
3.1 该结点所处的级(level)，即它是根结点的第几代子孙。这个信息决定了该结点所代表的区域的大小(边长)。例如，如果令根结点的级为n,则它所代表的区域(整个二值图)的边长就是2n。依此类推，处于m级(mm，而第0级即表示最小象素的结点它所代表的区域边长为20=1，就是说，它表示的是单个象素。
3.2 该结点在父结点所代表的区域中的位置(四个象限之一)以及上推至各代祖先结点所代表的区域中的位置。这个信息决定了本结点区域的起始坐标(左上角点)。
有了上面两部分信息，我们就能将位置码解码还原为相应的二值位置，从而恢复成灰度图。
位置码的构成方式有多种。有固定长度的(Fixed Length)，简记为FL位置码；有可变长度的(Variable Length)，简记为VL位置码。为便于理解，我们在此简单介绍一下一种FL位置码的表示。
, http://www.100md.com
设有一2n×2n的二值图，则它所对应的四元树结点可表示为一有n位数字的5进制数序列〈qn-1,qn-2,…,q0〉，其中，qi由关系式(1)确定：
(1)
式中，qi表示序列〈qn-1,qn-2,…,q0〉中第i位数字，而i则表示级，i=n为第n级，i=0为第0级；SNOTYPE4()根据本结点表示的区域在父结点区域中的象限返回一个方向码，分别以1，2，3，4表示左上、右上、左下、右下。
于是，序列〈qn-1,qn-2,…,q0〉中数字qn-1,qn-2,…,q0即表示从根结点起到叶结点止所经路径上各个结点的方向码。例如，图4中结点59的位置码可表示为3位5进制数322，而结点13的位置码为240，这里，最末位的0表示其下一级子结点已退化。
, http://www.100md.com
按照只表示和存贮黑结点的原则，图1所示的二值图现在仅用11个结点的位置码即可表示。
4 医学图象的四元树表示
图象在医学领域有着广泛的应用。由于在医疗领域引入了越来越多的先进诊疗检测手段，如X光、B超、CT以及核磁共振技术(MRT)等，因而获取的图象信息也成倍增加。这些图象信息对于直观反映病灶病变、定量给出检测指标特别是形态学方面的指标具有重要的意义。
以显微光度计对细胞切片的测定为例，医学图象的表示和存贮大致可用如下流程说明：
原始测量值→灰度图→三值图→两个二值图→四元树
↑ ↑ ↑ ↑
量化 阈值分割 分解 编码
, 百拇医药
图5 医学图象的转换流程
细胞切片经显微光度计测定后得到的是X-Y平面上由离散的一系列透光值组成的矩阵，它代表了细胞透光度曲面。透光值的精度取决于显微光度计本身的精度和测量时所调定的参数，如高电压值、增益放大倍数等。而X-Y方向的步长则根据测量要求及仪器本身的配置而定。这样所获得的测量值在X、Y方向上进行了量化(即对坐标值进行了离散化)，而在Z方向上则尚未进行。
将原始测值在Z方向进行量化，就形成了灰度图。灰度图的分级依据具体物理问题对分辨率的要求而定。比如对于航测遥感或卫星遥感图片，可分256级(每个象素8bit信息量，表示0～255)，而对细胞切片的测量来说，一般有100级灰度已足够了。
根据灰度图所显示的形态及灰度直方图，可用人工选择或通过统计方法得出最佳阈值，用于将灰度图所显示的信息，分为背景/细胞质/细胞核三部分，这称为阈值分割。这一步是较为关键的一步。阈值选择的合适与否，直接影响到得出的细胞形态学信息是否准确。目前除了采用人工交互方式(闭环控制方式)调整和选择阈值(即循环执行灰度直方图-选阈值-显示结果)外，还有一些基于数理统计原理的方法可供选择，如最小-最大方差法(判断分析法)、P-参数法、微分直方图法、灰度差直方图法、非等同熵系数法等。经过阈值分割，得到的是仅含背景-细胞质-细胞核三个值的细胞形态图，我们称之为三值图。
, 百拇医药
对于图象处理而言，三值图的处理仍不够方便，因而有必要将其再作分解，分解为两个二值图，即背景-细胞质二值图和背景-细胞核二值图。这样，在这两个二值图内，每个象素均仅有两种状态，即背景(0)和细胞质/细胞核(1)，可分别加以处理。
经过上述变换后得到的二值图，可用四元树方式编码存贮。在需要作图象处理(如噪声消除、特征提取、边缘增强及检测)及应用(如形态分析对比)时，再将其还原为二值图。
5 四元树的编码和译码
四元树的编码过程就是对二值区域不断进行X、Y方向二等分分割，并判是否同质。令欲编码的2n×2n的二值区域为根结点。从根结点出发，进行X、Y方向分割，得四个子区域。依次对各子区域再进行同样的过程，直至子区域内全为黑点时返回位置码。
分割-编码可以按深度优先方式也可以按宽度优先方式进行。深度优先方式适于以递归形式表达，较好理解，但在实际编码操作中，函数的递归调用消耗的计算机资源量较大。宽度优先方法的做法是，将非同质(即需进一步分解)的结点加入到一个队列中。检查队列的长度，若长度不为0(队列非空)，则从队列中取出一个结点继续分解。
, 百拇医药
四元树码的解码即将位置码恢复成二值图。它的过程是：取出位置码，将其分解为子区域左上角点坐标和子区域边长，然后将该子区域所有象素填黑。■
参考文献：
[1] 马建波.C语言图象处理程序集.海洋出版社，1992.
[2] Samet,Hanan, Applications of spatial data structures: Computer graphics, image processing and GIS, Addison-Wesley,1990.
收稿日期：1999-03-24, 百拇医药
单位：冯诗齐(上海三维计算机技术服务公司 上海200120)
关键词：四元树；二值图
数理医药学杂志000115
摘 要：介绍了四元树编码方法的原理及其在医学图象处理中的应用，并给出了四元树编码-解码的算法。
中图分类号：O 243
文章编号：1004-4337(2000)01-0029-03▲
1 引言
在图象处理领域，对二值光栅图象的压缩有多种方法，常用的如Freeman链码、十进制长链码、Wyle法游程长编码、2比特分隔游程长编码等[1]。这些方法都有各自的特点和局限性。九十年代初，出现了一种全新的称为四元树(或四叉树，quadtree)的数据结构用来表示二值图象。该方法将一个2n×2n的二值图象的二维几何区域递归地分解为四个象限，以树的一个结点来表示，这样一层层分下去直至分解到单个象素为止。
, http://www.100md.com
四元树结构的优点在于其规则的分解保证了数据的存贮、检索和处理的简单高效。由于分解可进行至象素，因此对于一个多边形二值图其边界几乎可以做到无限细分，可达到矢量或光栅结构所能达到的任何精度。通过改进其算法，可大大节省存贮空间。
这一新颖的表示法最初被用在GIS中表示地理信息。由于四元树结构很适合于将多边形的专题图(如地质图)与连续灰阶的光栅图象(如遥感和航空物探)组合起来，因而被人称之为超灵活结构。
2 四元树方法原理[2]。
设有一如图1(a)所示的2n×2n的二值图(围线内为二值图黑区，n=3)，则它的灰度值可用矩阵表示为图1(b)。按照上节所述的方法，将该区域的两个方向：X方向和Y方向各作二等分，分解为四个子区域，分别处于左上、右上、左下、右下位置(可以用方位NW，NE，SW，SE表示)。于是，若表示为树，则相当于将一个结点(根结点，代表整个二值图区域)分裂成为四个子结点。
, 百拇医药
图1 二值图
分别对这四个子结点再作如上所述的分裂，每个子区域又可对其X方向和Y方向各作二等分，分解为更小的四个子区，同样是以左上、右上、左下、右下的顺序排列。于是，根结点的四个子结点各自有了四个自己的子结点，它们是根结点的第二代子孙。这样一直分解下去，直至每个子区域都已是单个象素，不能再分解为止(见图2)。这时，构成了一棵有序正则(ordered regular)四元树，树中的每个非叶结点都有四个子结点，因而总的结点数应为4i(i=0-n)，而叶结点因其代表一个象素，所以它的值非0即1，即不是白结点就是黑结点。
图2 二值区域的分裂
注意到在四元树中，有些叶结点的父结点拥有的子结点全都具有相同的值。例如，上例中，结点6、7、8、9、10、11、14、16、21的子结点均为白，结点12、13、17、18、19的子结点均为黑，我们称它们是同质的。对于子结点同质的结点，将子结点去掉，而以其父结点来表示，这样，正则四元树就发生了变化，没有了子结点22、23、24、25，而它们的父结点6成为叶结点(白)。同样，结点7、8、9、10、11、14、16、21(白)；结点12、13、17、18、19(黑)现在成了叶结点。同理，结点6、7、8、9由于是同质的(全白)，故也可去掉，去掉后结点2成为叶结点(白)。于是，有序正则四元树如图3所示：
, http://www.100md.com
图3 非正则四元树表示
上述四元树在平面区域上所对应的二值区域为：
图4 二值区域
与正则四元树相比，非正则四元树存贮量大为减少。考虑到我们表示的是二值图象，因此还可以将表示方法再作简化，即只存贮黑(或白)结点，因为除了黑结点外剩下的就是白结点。于是，可将四元树表示为只有黑结点的单值四元树，这样可进一步压缩存贮空间。
3 线性四元树
用结点的位置码(locational code)来表示一个仅含有黑结点四元树，这样的表示法称为线性四元树(Linear Quadtree)方法。
由前面的讨论我们知道，对于一个非正则的四元树，它的结点应当包括两部分信息：
, 百拇医药
3.1 该结点所处的级(level)，即它是根结点的第几代子孙。这个信息决定了该结点所代表的区域的大小(边长)。例如，如果令根结点的级为n,则它所代表的区域(整个二值图)的边长就是2n。依此类推，处于m级(m
3.2 该结点在父结点所代表的区域中的位置(四个象限之一)以及上推至各代祖先结点所代表的区域中的位置。这个信息决定了本结点区域的起始坐标(左上角点)。
有了上面两部分信息，我们就能将位置码解码还原为相应的二值位置，从而恢复成灰度图。
位置码的构成方式有多种。有固定长度的(Fixed Length)，简记为FL位置码；有可变长度的(Variable Length)，简记为VL位置码。为便于理解，我们在此简单介绍一下一种FL位置码的表示。
, http://www.100md.com
设有一2n×2n的二值图，则它所对应的四元树结点可表示为一有n位数字的5进制数序列〈qn-1,qn-2,…,q0〉，其中，qi由关系式(1)确定：
(1)式中，qi表示序列〈qn-1,qn-2,…,q0〉中第i位数字，而i则表示级，i=n为第n级，i=0为第0级；SNOTYPE4()根据本结点表示的区域在父结点区域中的象限返回一个方向码，分别以1，2，3，4表示左上、右上、左下、右下。
于是，序列〈qn-1,qn-2,…,q0〉中数字qn-1,qn-2,…,q0即表示从根结点起到叶结点止所经路径上各个结点的方向码。例如，图4中结点59的位置码可表示为3位5进制数322，而结点13的位置码为240，这里，最末位的0表示其下一级子结点已退化。
, http://www.100md.com
按照只表示和存贮黑结点的原则，图1所示的二值图现在仅用11个结点的位置码即可表示。
4 医学图象的四元树表示
图象在医学领域有着广泛的应用。由于在医疗领域引入了越来越多的先进诊疗检测手段，如X光、B超、CT以及核磁共振技术(MRT)等，因而获取的图象信息也成倍增加。这些图象信息对于直观反映病灶病变、定量给出检测指标特别是形态学方面的指标具有重要的意义。
以显微光度计对细胞切片的测定为例，医学图象的表示和存贮大致可用如下流程说明：
原始测量值→灰度图→三值图→两个二值图→四元树
↑ ↑ ↑ ↑
量化 阈值分割 分解 编码
, 百拇医药
图5 医学图象的转换流程
细胞切片经显微光度计测定后得到的是X-Y平面上由离散的一系列透光值组成的矩阵，它代表了细胞透光度曲面。透光值的精度取决于显微光度计本身的精度和测量时所调定的参数，如高电压值、增益放大倍数等。而X-Y方向的步长则根据测量要求及仪器本身的配置而定。这样所获得的测量值在X、Y方向上进行了量化(即对坐标值进行了离散化)，而在Z方向上则尚未进行。
将原始测值在Z方向进行量化，就形成了灰度图。灰度图的分级依据具体物理问题对分辨率的要求而定。比如对于航测遥感或卫星遥感图片，可分256级(每个象素8bit信息量，表示0～255)，而对细胞切片的测量来说，一般有100级灰度已足够了。
根据灰度图所显示的形态及灰度直方图，可用人工选择或通过统计方法得出最佳阈值，用于将灰度图所显示的信息，分为背景/细胞质/细胞核三部分，这称为阈值分割。这一步是较为关键的一步。阈值选择的合适与否，直接影响到得出的细胞形态学信息是否准确。目前除了采用人工交互方式(闭环控制方式)调整和选择阈值(即循环执行灰度直方图-选阈值-显示结果)外，还有一些基于数理统计原理的方法可供选择，如最小-最大方差法(判断分析法)、P-参数法、微分直方图法、灰度差直方图法、非等同熵系数法等。经过阈值分割，得到的是仅含背景-细胞质-细胞核三个值的细胞形态图，我们称之为三值图。
, 百拇医药
对于图象处理而言，三值图的处理仍不够方便，因而有必要将其再作分解，分解为两个二值图，即背景-细胞质二值图和背景-细胞核二值图。这样，在这两个二值图内，每个象素均仅有两种状态，即背景(0)和细胞质/细胞核(1)，可分别加以处理。
经过上述变换后得到的二值图，可用四元树方式编码存贮。在需要作图象处理(如噪声消除、特征提取、边缘增强及检测)及应用(如形态分析对比)时，再将其还原为二值图。
5 四元树的编码和译码
四元树的编码过程就是对二值区域不断进行X、Y方向二等分分割，并判是否同质。令欲编码的2n×2n的二值区域为根结点。从根结点出发，进行X、Y方向分割，得四个子区域。依次对各子区域再进行同样的过程，直至子区域内全为黑点时返回位置码。
分割-编码可以按深度优先方式也可以按宽度优先方式进行。深度优先方式适于以递归形式表达，较好理解，但在实际编码操作中，函数的递归调用消耗的计算机资源量较大。宽度优先方法的做法是，将非同质(即需进一步分解)的结点加入到一个队列中。检查队列的长度，若长度不为0(队列非空)，则从队列中取出一个结点继续分解。
, 百拇医药
四元树码的解码即将位置码恢复成二值图。它的过程是：取出位置码，将其分解为子区域左上角点坐标和子区域边长，然后将该子区域所有象素填黑。■
参考文献：
[1] 马建波.C语言图象处理程序集.海洋出版社，1992.
[2] Samet,Hanan, Applications of spatial data structures: Computer graphics, image processing and GIS, Addison-Wesley,1990.
收稿日期：1999-03-24, 百拇医药