图像矢量化源码

//Skeleton.cpp 线条方式的处理 矢量化处理类
#include "stdafx.h"
#include "stdlib.h"
#include "stdio.h"
#include "math.h"
#include "Skeleton.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

#define sqrt(x) sqrt((double)(x))

//标号的“很大”值，内部用，注意当图象中有效区域的“半径”>ZCONST时，
//结果不可预料。
#define ZCONST 1000
//this constant is used by pruning,internal use.
#define THRESHOLD 5

//定义模板
#define n1(p,w) (*((p)-1))
#define n2(p,w) (*((p)-(w)-1))
#define n3(p,w) (*((p)-(w)))
#define n4(p,w) (*((p)-(w)＋1))
#define n5(p,w) (*((p)＋1))
#define n6(p,w) (*((p)＋(w)＋1))
#define n7(p,w) (*((p)＋(w)))
#define n8(p,w) (*((p)＋(w)-1))
#define G(p,w) (n1(p,w)＋n2(p,w)＋n3(p,w)＋n4(p,w)＋n5(p,w)＋n6(p,w)＋n7(p,w)＋n8(p,w))

#define PI 3.1415926

//BOOL m_bTrans=TRUE;
//int m_iLineWidth=10, m_iTinyPels=10, m_iLocalPixels=40;
//int m_iDegreeLimit=15, m_iDisLimit=8;

//调用接口，结果存放在链表m_pLineList中，从第二个元素开始。
//返回值表示是否出错。
//生成一个skeleton对象后，可多次调用该函数。
int CSkeleton::NewSkeleton(
char* strBmpName,//图象文件名
int bNormal,//bNormal==TRUE，线条图，FALSE，样片图
int bTran,//TRUE，求取分段尽量贯穿，FALSE，不贯穿
int nLineWidth,//样片图中，样片间线条的宽度，一定要大于等于最大宽度
int nTinyPels,//需消除的小段的像素数阈值
int iLocalPixels,//贯穿时，用于求斜率的像素数
int iDegreeLimit,//允许贯穿的角度阈值，单位为度，正锐角
int iDisLimit//允许贯穿的线条端点距离的阈值
)
{
BOOL ret;

DeleteList(m_pHead);
DeleteLineList();
if (m_pLabel) delete [] m_pLabel;
m_pLabel=NULL;

int nWdt,nHgt;
BYTE* pImg;
pImg=LoadBmpGray(strBmpName,&nWdt,&nHgt);
if (pImg==NULL) return FALSE;

ToBinary(pImg, nWdt,nHgt,150);
delete [] pImg;//it's not needed any more.

if (!bNormal) DoReverse(nLineWidth);

DT();
FindSPPath();
PathMerge();
Removal();
Pruning(THRESHOLD);

///Debug
////Vectorize("xie.txt",5,6);

GetSegments();
DeletePtList(m_pPtList);
m_pPtList = NULL;

EliminateTiny(nTinyPels);
///Debug
///OutputToFile("c:\xieseg0.txt");

if (bTran) Traverse(iLocalPixels,iDegreeLimit,iDisLimit);

// Add by PPP
ret = NodeMaking();

#ifdef _DEBUG
//OutputToFile("c:\xieseg.txt");
#endif
return ret;
}

//载入BMP图像以进行处理，要求为线型图
BYTE* CSkeleton::LoadBmpGray(char* fn,int* pWidth,int* pHeight)
{
BITMAPFILEHEADER bmpfhTmp;
BITMAPINFOHEADER bmpihTmp;
BYTE *palette;
BYTE *line,*pline,b;
int linelen;
int colors;
int i,j,x,y;
int bytes,linebytes;
CFile bmp;
CFileStatus fileStat;
int m_iWidth,m_iHeight,m_iLineBytes;
BYTE *m_pF,*pF;
if (! CFile::GetStatus(fn,fileStat)) return NULL;//NOT EXIST
bmp.Open(fn,CFile::modeRead);
if (bmp.Read((char*)&bmpfhTmp,sizeof(bmpfhTmp))!=sizeof(bmpfhTmp))
return NULL;
if (bmpfhTmp.bfType!=unsigned short(('M'<<8) | 'B')) return NULL;
if (bmp.Read((char*) &bmpihTmp,sizeof(BITMAPINFOHEADER))!=
sizeof(BITMAPINFOHEADER)) return NULL;

m_iWidth=bmpihTmp.biWidth;
m_iHeight=bmpihTmp.biHeight;
m_iLineBytes=((m_iWidth*3＋3)/4)*4;
m_bixDPM=bmpihTmp.biXPelsPerMeter;
if (m_bixDPM == 0) m_bixDPM = 2000;

if ( bmpihTmp.biCompression) return NULL;
if (bmpihTmp.biBitCount!=1 && bmpihTmp.biBitCount!=8 && bmpihTmp.biBitCount!=24) return NULL;

if (bmpihTmp.biBitCount==1) colors=2;
else if (bmpihTmp.biBitCount==4) colors=16;
else if (bmpihTmp.biBitCount==8) colors=256;
else colors=0;
palette=new BYTE [colors*3];
for (i=0;i<colors;i＋＋) {
bmp.Read(palette＋3*i,3);
bmp.Seek(1,CFile::current);
}

m_pF= new BYTE[(long)m_iWidth*m_iHeight];
pF=m_pF;

bmp.Seek(bmpfhTmp.bfOffBits,CFile::begin);

if (bmpihTmp.biBitCount==24) {
linelen=((m_iWidth*3L＋3)/4)*4;
line=new BYTE [linelen];
for (i=0;i<m_iHeight;i＋＋) {
bmp.Read(line,linelen);
pline=line;
for (j=0;j<m_iWidth;j＋＋) {
*pF=(pline[0]＋pline[1]＋pline[2])/3;
pF＋＋;
pline＋=3;
}
}
delete [] line;
} else if (bmpihTmp.biBitCount==8) {
y=0;
linelen=((m_iWidth＋3)/4)*4;
line=new unsigned char [linelen];
while (y<m_iHeight && (bmp.Read(line,linelen))) {
for (x=0;x<m_iWidth;x＋＋) {
*pF=(palette[line[x]*3]＋palette[line[x]*3＋1]＋palette[line[x]*3＋2])/3;
pF＋＋;
}
y＋＋;
}
delete [] line;
} else {
bytes=m_iWidth/8;
linebytes=((bytes＋3)/4)*4;
y=0;
line=new unsigned char [linebytes];
while (y<m_iHeight && (bmp.Read(line,linebytes))) {
x=0;
for (i=0;i<linebytes;i＋＋) {
b=line[i];
for (j=0;j<8;j＋＋) {
if (x>=m_iWidth) break;
if (b&0x80) {
*pF=(palette[3]＋palette[4]＋palette[5])/3;
} else {
*pF=(palette[0]＋palette[1]＋palette[2])/3;
}
b<<=1;
pF＋＋;
x＋＋;
}
if (x>=m_iWidth) break;
}
y＋＋;
}
delete [] line;
}
delete [] palette;
*pWidth=m_iWidth;
*pHeight=m_iHeight;
return m_pF;
}

CSkeleton::CSkeleton()
{
m_pHead=new list;
m_pHead->next=NULL;

m_pPtList = NULL;

m_pLineList=new CLineList;
m_pLineList->next=NULL;

m_pLabel=NULL;
}
CSkeleton::~CSkeleton()
{
DeleteList(m_pHead);
delete m_pHead;

DeleteLineList();
delete m_pLineList;

if (m_pLabel) delete [] m_pLabel;
}

//
void CSkeleton::ToBinary(BYTE* pImg, int nWdt,int nHgt,int threshold)
{
BYTE* pSrc,*pCol;
label* pL;
int i,j;

m_iWdt=nWdt＋2;
m_iHgt=nHgt＋2;
m_pLabel=new label [(long)m_iWdt*m_iHgt];

//retrive data from gray image.
pSrc=pImg＋nWdt*nHgt;
pL=m_pLabel;
memset(pL,0,sizeof(label)*m_iWdt);
pL＋=m_iWdt;
for (i=0;i<nHgt;i＋＋) {
*pL＋＋=0;
pSrc-=nWdt;
pCol=pSrc;
for (j=0;j<nWdt;j＋＋) {
(*pL＋＋)=((*pCol)<threshold) ? 1 : 0;
pCol＋＋;
}
*pL＋＋=0;
}
memset(pL,0,sizeof(label)*m_iWdt);

// Enclosed by psr on 2001-02-18
//do cleanning one time, it can be done more times to deal with more noise
/*
pL1=new label [(long)m_iWdt*m_iHgt];
vpL1=pL1;
memset(vpL1,0,sizeof(label)*m_iWdt);
vpL1＋=m_iWdt;
pL=m_pLabel＋m_iWdt;
for (i=0;i<nHgt;i＋＋) {
pL＋＋;
*vpL1＋＋=0;
for (j=0;j<nWdt;j＋＋) {
g=G(pL,m_iWdt);
if (g>5) {
*vpL1=1;
}
else if (g==5 && ( n8(pL,m_iWdt)==0 && n1(pL,m_iWdt)==0 && n2(pL,m_iWdt)==0
|| n2(pL,m_iWdt)==0 && n3(pL,m_iWdt)==0 && n4(pL,m_iWdt)==0
|| n4(pL,m_iWdt)==0 && n5(pL,m_iWdt)==0 && n6(pL,m_iWdt)==0
|| n6(pL,m_iWdt)==0 && n7(pL,m_iWdt)==0 && n8(pL,m_iWdt)==0)) {
*vpL1=1;
}
else if (g<3) {
*vpL1=0;
}
else if (g==3 && ( n8(pL,m_iWdt)==1 && n1(pL,m_iWdt)==1 && n2(pL,m_iWdt)==1
|| n2(pL,m_iWdt)==1 && n3(pL,m_iWdt)==1 && n4(pL,m_iWdt)==1
|| n4(pL,m_iWdt)==1 && n5(pL,m_iWdt)==1 && n6(pL,m_iWdt)==1
|| n6(pL,m_iWdt)==1 && n7(pL,m_iWdt)==1 && n8(pL,m_iWdt)==1)) {
*vpL1=0;
} else {
*vpL1=*pL; //default:no change made to *pL
}
vpL1＋＋;
pL＋＋;
}
pL＋＋;
*vpL1＋＋=0;
}
memset(vpL1,0,sizeof(label)*m_iWdt);

memcpy(m_pLabel,pL1,m_iWdt*m_iHgt);
delete [] pL1;
*/
}
void CSkeleton::DT()
{
int i,j,w;
label* pL;
pL=m_pLabel＋m_iWdt;
w=m_iWdt;
for (i=0;i<m_iHgt-2;i＋＋) {
pL＋＋;
for (j=0;j<m_iWdt-2;j＋＋) {
if (*pL) *pL=__min(__min(n1(pL,w),n2(pL,w)),__min(n3(pL,w),n4(pL,w)))＋1;
pL＋＋;
}
pL＋＋;
}
pL=m_pLabel＋m_iWdt*(m_iHgt-1)-1;
for (i=m_iHgt-2;i>=1;i--) {
pL--;
for (j=0;j<m_iWdt-2;j＋＋) {
if(*pL) *pL=__min(*pL,__min(__min(n5(pL,w),n6(pL,w)),__min(n7(pL,w),n8(pL,w)))＋1);
pL--;
}
pL--;
}
}
int CSkeleton::C4(unsigned char* n)// n[9] should be assigned n[1]
{
int k,r=0;
for (k=1;k<=4;k＋＋)
if (n[2*k-1] && !(n[2*k] && n[2*k＋1])) r＋＋;
return r;
}
int CSkeleton::C8(unsigned char* n)// n[9] should be assigned n[1]
{
int k,r=0;
for (k=1;k<=4;k＋＋)
if (!n[2*k-1] && (n[2*k] || n[2*k＋1])) r＋＋;
return r;
}
int CSkeleton::CN(unsigned char* n)// n[9] should be assigned n[1]
{
int k,r=0;
for (k=1;k<=8;k＋＋)
if (n[k]!=n[k＋1]) r＋＋;
r/=2;
return r;
}

//
void CSkeleton::FindSPPath()
{
unsigned char * n8,* N8;
int i,j,w;
label* pL,*pLtmp;
label p,pm1;
label v1,v2,v3,v4,v5,v6,v7,v8;
n8=new unsigned char[10];
N8=new unsigned char[10];
w=m_iWdt;

pL=m_pLabel＋w;
for (i=0;i<m_iHgt-2;i＋＋) {
pL＋＋;
for (j=0;j<w-2;j＋＋) {
if (!*pL) {pL＋＋;continue;}
p=*pL;pm1=p-1;
v1=n1(pL,w);v2=n2(pL,w);
v3=n3(pL,w);v4=n4(pL,w);
v5=n5(pL,w);v6=n6(pL,w);
v7=n7(pL,w);v8=n8(pL,w);
if (abs(v1)==pm1) n8[1]=1; else n8[1]=0;
if (abs(v2)==pm1) n8[2]=1; else n8[2]=0;
if (abs(v3)==pm1) n8[3]=1; else n8[3]=0;
if (abs(v4)==pm1) n8[4]=1; else n8[4]=0;
if (v5==pm1) n8[5]=1; else n8[5]=0;
if (v6==pm1) n8[6]=1; else n8[6]=0;
if (v7==pm1) n8[7]=1; else n8[7]=0;
if (v8==pm1) n8[8]=1; else n8[8]=0;
n8[9]=n8[1];
if (abs(v1)==p) N8[1]=1; else N8[1]=0;
if (abs(v2)==p) N8[2]=1; else N8[2]=0;
if (abs(v3)==p) N8[3]=1; else N8[3]=0;
if (abs(v4)==p) N8[4]=1; else N8[4]=0;
if (v5==p) N8[5]=1; else N8[5]=0;
if (v6==p) N8[6]=1; else N8[6]=0;
if (v7==p) N8[7]=1; else N8[7]=0;
if (v8==p) N8[8]=1; else N8[8]=0;
N8[9]=N8[1];

if (CN(n8)>=2 || C4(N8)!=2 || N8[1]＋N8[3]＋N8[5]＋N8[7]!=2) goto findsp;

if (v1<0 && -v1<p || v3<0 && -v3<p) goto findsp;

if (v2<0 && -v2<p && abs(v1) != p && abs(v3)!=p ) goto findsp;

if (v4<0 && -v4<p && abs(v3) !=p && abs(v5)!=p ) goto findsp;
pL＋＋;
continue;
findsp: *pL＋＋=-p;
pLtmp=pL-2;
while (*pLtmp>0 && *pLtmp>-*(pLtmp＋1)) {*pLtmp=-*pLtmp;pLtmp--;}
}
pL＋＋;
}
//then do second scan
pL=m_pLabel＋w*(m_iHgt-1)-1;
for (i=0;i<m_iHgt-2;i＋＋) {
pL--;
for (j=0;j<w-2;j＋＋) {
if (*pL<=0) {pL--;continue;}
p=*pL;
v1=n1(pL,w);
v5=n5(pL,w);v6=n6(pL,w);
v7=n7(pL,w);v8=n8(pL,w);

if (v5<0 && -v5<p || v7<0 && -v7<p) goto findsp1;

if (v6<0 && -v6<p && abs(v5) != p && abs(v7)!=p ) goto findsp1;

if (v8<0 && -v8<p && abs(v1) !=p && abs(v7)!=p ) goto findsp1;

pL--;
continue;

findsp1: *pL--=-p;
}
pL--;
}

delete [] n8;
delete [] N8;
}

//合并路径
void CSkeleton::PathMerge()
{
label* pL;
int i,j;
pL=m_pLabel＋m_iWdt;
for (i=0;i<m_iHgt-2;i＋＋) {
pL＋＋;
for (j=0;j<m_iWdt-2;j＋＋) {
if (*pL>=0 && n1(pL,m_iWdt)<0 && n3(pL,m_iWdt)<0 && n5(pL,m_iWdt)<0 && n7(pL,m_iWdt)<0)
*pL=-*pL;
pL＋＋;
}
pL＋＋;
}
}

void CSkeleton::Removal()
{
unsigned char *n8,*N8;
int i,j,k,w;
label* pL;
label v1,v2,v3,v4,v5,v6,v7,v8;
label absp;
list* pList;
n8=new unsigned char [10];
N8=new unsigned char [10];

pL=m_pLabel＋m_iWdt*(m_iHgt-1)-1;
w=m_iWdt;
for (i=0;i<m_iHgt-2;i＋＋) {
pL--;
for (j=0;j<m_iWdt-2;j＋＋) {
if (*pL>=0) {pL--;continue;}
v1=n1(pL,w);v2=n2(pL,w);
v3=n3(pL,w);v4=n4(pL,w);
v5=n5(pL,w);v6=n6(pL,w);
v7=n7(pL,w);v8=n8(pL,w);

if (v1<0) n8[1]=1;else n8[1]=0;
if (v2<0) n8[2]=1;else n8[2]=0;
if (v3<0) n8[3]=1;else n8[3]=0;
if (v4<0) n8[4]=1;else n8[4]=0;
if (v5<0) n8[5]=1;else n8[5]=0;
if (v6<0) n8[6]=1;else n8[6]=0;
if (v7<0) n8[7]=1;else n8[7]=0;
if (v8<0) n8[8]=1;else n8[8]=0;
n8[9]=n8[1];

absp=-*pL;
if (v1>0 && v1%ZCONST<=absp) N8[1]=1;else N8[1]=0;
if (v2>0 && v2%ZCONST<=absp) N8[2]=1;else N8[2]=0;
if (v3>0 && v3%ZCONST<=absp) N8[3]=1;else N8[3]=0;
if (v4>0 && v4%ZCONST<=absp) N8[4]=1;else N8[4]=0;
if (v5>0 && v5%ZCONST<=absp) N8[5]=1;else N8[5]=0;
if (v6>0 && v6%ZCONST<=absp) N8[6]=1;else N8[6]=0;
if (v7>0 && v7%ZCONST<=absp) N8[7]=1;else N8[7]=0;
if (v8>0 && v8%ZCONST<=absp) N8[8]=1;else N8[8]=0;
N8[9]=N8[1];

if (C8(n8)!=1) {pL--;continue;}

if (N8[1]＋N8[2]＋N8[3]＋N8[4]＋N8[5]＋N8[6]＋N8[7]＋N8[8]>=3
&& n8[1]*n8[3]＋n8[3]*n8[5]＋n8[5]*n8[7]＋n8[7]*n8[1]==0){
pList=new list;
pList->l=pL;
pList->next=m_pHead->next;
m_pHead->next=pList;
pL--;
continue;
}
if (n8[1] && n8[5] && v7>ZCONST) {pL--;continue;}
*pL--=absp＋ZCONST;
}
pL--;
}
//second scan
pL=m_pLabel＋m_iWdt*(m_iHgt-1)-1;
for (i=0;i<m_iHgt-2;i＋＋) {
pL--;
for (j=0;j<m_iWdt-2;j＋＋) {
if (*pL>=0) {*pL--=0;continue;}
*pL=-*pL;
v1=n1(pL,w);v2=n2(pL,w);
v3=n3(pL,w);v4=n4(pL,w);
v5=n5(pL,w);v6=n6(pL,w);
v7=n7(pL,w);v8=n8(pL,w);
if (v1<0) n8[1]=1;else n8[1]=0;
if (v2<0) n8[2]=1;else n8[2]=0;
if (v3<0) n8[3]=1;else n8[3]=0;
if (v4<0) n8[4]=1;else n8[4]=0;
if (v5>0) n8[5]=1;else n8[5]=0;
if (v6>0) n8[6]=1;else n8[6]=0;
if (v7>0) n8[7]=1;else n8[7]=0;
if (v8>0) n8[8]=1;else n8[8]=0;
n8[9]=n8[1];

if ((k=n8[1]＋n8[2]＋n8[3]＋n8[4]＋n8[5]＋n8[6]＋n8[7]＋n8[8])<=2) {pL--;continue;}

if (C8(n8)!=1)
*pL＋=(k-2)*ZCONST;
else {
*pL=0;
if (v5>ZCONST) n5(pL,w)=v5-ZCONST;
if (v6>ZCONST) n6(pL,w)=v6-ZCONST;
if (v7>ZCONST) n7(pL,w)=v7-ZCONST;
if (v8>ZCONST) n8(pL,w)=v8-ZCONST;
}
pL--;
}
pL--;
}

delete [] n8;
delete [] N8;
}