把一个平面区域简化成图（ graph ）是一种重要的结构形状表示法。利用细化技术以得到区域的骨架是常用的方法。中轴变换（ medial axis transform,MAT ）是一种用来确定物体骨架的细化技术。具有边界 B 的区域 R 的 MAT 是如下确定的。对每个 R 中的点 P ，我们在 B 中搜寻与它最近的点。如果对 P 能找到多于一个这样的点（即有 2 个或以上的 B 中的点与 P 同时最近），就可认为 P 属于 R 的中线或骨架，或者说 P 是 1 个骨架点。理论上讲，每个骨架点保持了其与边界距离最小的性质，所以如果用以每个骨架点为中心的圆的集合（利用适当的量度），就可以恢复出原始的区域来。具体就是以每个骨架点为圆心，以前述最小距离为半径作圆周。它们的包络就构成了区域的边界，填充圆周就得到区域。或者以每个骨架点为圆心，以所有小于和等于最小距离的长度为半径作圆，这些圆的并集就覆盖了整个区域。

由上述讨论可知，骨架是用1个点与1个点集的最小距离来定义的，可写成：

其中距离量度可以是欧氏的、城区的、或棋盘的。因为最近距离取决于所用的距离量度，所以MAT的结果也和所用的距离量度有关。

图6.1给出一些区域和它们的用欧氏距离算出的骨架。由图(a)和图(b)可知，对较细长的物体其骨架常能提供较多的形状信息，而对较粗短的物体则骨架提供的信息较少。注意，有时用骨架表示区域受噪声的影响较大，例如比较图(c)和图(d)，其中图(d)中的区域与图(c)中区域只有一点儿差别（可认为由噪声产生），但两者的骨架相差很大。

根据上式求区域骨架需要计算所有边界点到所有区域内部点的距离，因而计算量是很大的。实际中都是采用逐次消去边界点的迭代细化算法。在这个过程中有3个限制条件需要注意：① 不消去线段端点；② 不中断原来连通的点；③ 不过多侵蚀区域。

本文采用下面的方法求二值目标区域骨架。设已知目标点标记为1，背景点标记为0。定义边界点是本身标记为1而其8－连通邻域中至少有1个点标记为0的点。算法对边界点的操作如下：

(1) 考虑以边界点为中心的8－邻域，记中心点为p₁，其邻域的8个点顺时针绕中心点分别记为p₂，p₃，p₄，p₅，p₆，p₇，p₈，p₉，其中p₂在p₁上方。首先标记同时满足下列条件的边界点：

其中N(p1)是p₁非零邻点的个数，S(p1)是以p₂，p₃，…，p₉为序时这些点的值从0到1变化的次数。当对所有边界点都检验完毕后，将所有标记了的点除去。

(2) 同第(1)步，仅将前面条件(1.3)改为条件(2.3) ；条件(1.4)改为条件(2.4)

 

。同样当对所有边界点都检验完毕后，将所有标记了的点除去。

以上2步操作构成1次迭代。算法反复迭代直至没有点再满足标记条件，这时剩下的点组成区域的骨架。在以上各标记条件中，条件(1.1)除去了p₁只有一个标记为1的邻点，即p₁为线段端点的情况以及p₁有7个标记为1的邻点，即p₁过于深入区域内部的情况；条件(1.2)除去了对宽度为单个象素的线段进行操作的情况以避免将骨架割断；条件(1.3)和条件(1.4)除去了p₁为边界的右或下端点(p₄=0或p₆＝0)或左上角(p₂=0或p₈＝0)亦即不是骨架点的情况。类似地，条件(2.3)和条件(2.4)除去了p₁为边界的左或上端点(p₂=0或p₈＝0)或右下角(p₄=0或p₆＝0)亦即不是骨架点的情况。最后注意到，如p₁为边界的右上端点则有p₄＝0和p₂＝0，如p₁为边界的左下端点则有p₆＝0和p₈＝0，它们都同时满足(1.3)和(1.4)以及(2.3)和(2.4)各条件。以本文的车牌字符为例，请看骨架的计算结果：

 

 

部分代码:void NumberCross(char *F,int xW,int yW){  int    k,CRN; int    off,total,off0; int    of[9]; char   N[9];   total = xW*yW; of[3]=-xW-1; of[2]=-xW; of[1]=-xW+1; of[4]=   -1;            of[0]=    1; of[5]= xW-1; of[6]= xW; of[7]= xW+1;  for(off=0;off<total;off++)    {   if(F[off])  {    for(k=0;k<8;k++)    { off0=off+of[k]; if(F[off0]) N[k]=1; else N[k]=0;}   N[8]=N[0];      if(N[0]&&N[7]&&N[6])   {     F[off]=4;    off0 = off+of[0]; F[off0]=4;    off0 = off+of[7]; F[off0]=4;    off0 = off+of[6]; F[off0]=4;   }   else   {     CRN=0; for(k=0;k<8;k++) if(N[k]!=N[k+1]) CRN++;    CRN =CRN/2;    F[off]=CRN;   }  }    }}

void ThinImage(char *F,char *G,int xW,int yW)

{   int    off,total;  int    i,j;  int    k,XX,NRN;  char   N[10],C[4],C1,C2;  int    off1,off2,off3;  char   *row_use_flag;  char   flag,endflag;  int    *soff[3];  int    Num,Len[3],CurRow;

  off1 = 0; off2 = xW*(yW-1);

  for(i=0;i<xW;i++) { F[off1]=0; F[off2]=0; off1++;off2++;}  off1 = 0; off2 = xW-1;  for(i=0;i<yW;i++) { F[off1]=0; F[off2]=0; off1 = off1+xW;off2 = off2+xW;}

  total = xW*yW;  for(off=0;off<total;off++)  { if(F[off]) F[off]=1; G[off]=F[off];}

  k =xW; if(yW>k) k=yW;  k+=100;

  row_use_flag =  new char[k];

  for(i=0;i<yW;i++) row_use_flag[i]=1;

  for(i=0;i<3;i++)

  {    soff[i] =  new int[k]; Len[i]=0;  }

  do

    {       endflag=0;      for(j=1;j<yW-1;j++)       {      if(row_use_flag[j]==0) continue; endflag++;     CurRow = j%3;     for(i=0;i<Len[CurRow];i++)        { F[soff[CurRow][i]]=0;G[soff[CurRow][i]]=0;}     Num = 0;off2=(long)j*(long)xW+1;flag=0;     for(i=1;i<xW-1;i++)  {         if(F[off2]!=1) { off2++;continue;}        off1 = off2-xW; off3 = off2+xW;

        if((G[off1]&G[off2-1]&G[off2+1]&G[off3])!=0)

     { off2++;continue;}        NRN = G[off1-1]+G[off1]+G[off1+1]+G[off2-1]+G[off2+1]+G[off3-1]+G[off3]+G[off3+1];

        if(NRN <=1 ) { F[off2]=2; off2++;continue;}

        N[4] = F[off1-1];N[3]=F[off1];N[2]=F[off1+1];

        N[5] = F[off2-1];             N[1]=F[off2+1];        N[6] = F[off3-1];N[7]=F[off3];N[8]=F[off3+1];        N[9] = N[1];

        if((!N[1])&&(N[2]||N[3])) C[0]=1; else C[0]=0;

        if((!N[3])&&(N[4]||N[5])) C[1]=1; else C[1]=0;        if((!N[5])&&(N[6]||N[7])) C[2]=1; else C[2]=0;        if((!N[7])&&(N[8]||N[9])) C[3]=1; else C[3]=0;        XX = C[0]+C[1]+C[2]+C[3];

        if(XX !=1 )  { F[off2]=2; off2++;continue;}

        if(F[off1] == -1)

     {           F[off1]=0; N[3]=0;          if((!N[1])&&(N[2]||N[3])) C1=1; else C1=0;          if((!N[3])&&(N[4]||N[5])) C2=1; else C2=0;          k = XX+C1+C2-C[0]-C[1];           if(k != 1) { F[off1] = -1; off2++;continue;}          F[off1]=-1; N[3]=-1;     }

        if(F[off2-1]!=-1)

    {       F[off2]=-1; soff[CurRow][Num]=off2;Num++;      flag=1;off2++;continue;     }       F[off2-1]=0;N[5]=0;

       if((!N[3])&&(N[4]||N[5])) C1=1; else C1=0;

       if((!N[5])&&(N[6]||N[7])) C2=1; else C2=0;

       k = XX+C1+C2-C[1]-C[2];

       if(k == 1)  

    {    F[off2-1] = -1;F[off2]= -1;   soff[CurRow][Num]=off2;Num++;flag=1;     }      else            F[off2-1] = -1;      off2++;      }      row_use_flag[j]=flag;    Len[CurRow] =Num;    }    for(i=0;i<3;i++) for(j=0;j<Len[i];j++) { F[soff[i][j]]=0;G[soff[i][j]]=0;}  } while(endflag);  delete []row_use_flag; delete []soff[0]; delete []soff[1]; delete []soff[2]; NumberCross(F,xW,yW);}