图像的最短路径求取（有一点问题和局限性）

#include <math.h>#include <iomanip.h> #include <stdlib.h>#include <windows.h>#include <stdio.h>#include <stdlib.h>#include <iostream.h>#include <fstream.h>#include "string.h"//画出任意坐标点到终点最短路径的路线void roadPath(int i,int j,int m_lineByte,unsigned char *m_pBmpBuf);//八个方向的最短路void minDire(int i,int j);// int bmp[1000][1000];int N,M;//char *bmp;//---------------------------------------------------------------------------------------//以下该模块是完成BMP图像(彩色图像是24bit RGB各8bit)的像素获取，并存在文件名为xiang_su_zhi.txt中unsigned char *pBmpBuf;//读入图像数据的指针

int bmpWidth;//图像的宽int bmpHeight;//图像的高int lineByte;RGBQUAD *pColorTable;//颜色表指针

int biBitCount;//图像类型，每像素位数//-------------------------------------------------------------------------------------------//读图像的位图数据、宽、高、颜色表及每像素位数等数据进内存，存放在相应的全局变量中

int **d,****road;//d[][]是坐标数据,road[N+2][M+2][3][3]是记录行走方向的数组double **c,****juli;int dire[8][2]={{1,0},{1,1},{1,-1},{-1,0},{-1,1},{-1,-1},{0,1},{0,-1}};//八个方向;

bool readBmp(char *bmpName) {    FILE *fp=fopen(bmpName,"rb");//二进制读方式打开指定的图像文件

    if(fp==0) return 0;

    //跳过位图文件头结构BITMAPFILEHEADER

    fseek(fp, sizeof(BITMAPFILEHEADER),0);

    //定义位图信息头结构变量，读取位图信息头进内存，存放在变量head中

    BITMAPINFOHEADER head; 

    fread(&head, sizeof(BITMAPINFOHEADER), 1,fp); //获取图像宽、高、每像素所占位数等信息

    bmpWidth = head.biWidth;

    bmpHeight = head.biHeight;

    biBitCount = head.biBitCount;//定义变量，计算图像每行像素所占的字节数（必须是4的倍数）

    lineByte=(bmpWidth * biBitCount/8+3)/4*4;//灰度图像有颜色表，且颜色表表项为256

    if(biBitCount==8) {

        //申请颜色表所需要的空间，读颜色表进内存

        pColorTable=new RGBQUAD[256];

        fread(pColorTable,sizeof(RGBQUAD),256,fp);

 }

    //申请位图数据所需要的空间，读位图数据进内存

    pBmpBuf=new unsigned char[lineByte * bmpHeight];    fread(pBmpBuf,1,lineByte * bmpHeight,fp);

    fclose(fp);//关闭文件

    return 1;//读取文件成功}//-----------------------------------------------------------------------------------------//给定一个图像位图数据、宽、高、颜色表指针及每像素所占的位数等信息,将其写到指定文件中bool saveBmp(char *bmpName, unsigned char *imgBuf, int width, int height,

             int biBitCount, RGBQUAD *pColorTable)

{

    //如果位图数据指针为0，则没有数据传入，函数返回 M=width;N=height; int i,j,k; //动态分配原始数组d[][],距离数组c[][] d=(int **)malloc((N+2)*sizeof(int*)); c=(double **)malloc((N+2)*sizeof(double *)); road=(int ****)malloc((N+2)*sizeof(int***)); juli=(double ****)malloc((N+2)*sizeof(double***)); for (i=0;i<=N+1;i++) {  d[i]=(int *)malloc((M+2)*sizeof(int));  c[i]=(double *)malloc((M+2)*sizeof(double));        road[i]=(int ***)malloc((M+2)*sizeof(int**));  juli[i]=(double ***)malloc((M+2)*sizeof(double**));  for (j=0;j<=M+1;j++)  {   d[i][j]=0;   c[i][j]=100000; //初始化            road[i][j]=(int **)malloc((3)*sizeof(int*));   juli[i][j]=(double **)malloc((3)*sizeof(double*));   for (int i1=0;i1<=2;i1++)   {                road[i][j][i1]=(int *)malloc((3)*sizeof(int));    juli[i][j][i1]=(double *)malloc((3)*sizeof(double));    for(int j1=0;j1<=2;j1++)    {     road[i][j][i1][j1]=0;     //juli[i][j][0][0]代表（-1，-1）这个方向，juli[i][j][1][2]代表（0，1）这个方向，其余类推     juli[i][j][i1][j1]=0;    }   }   } }

    if(!imgBuf)

        return 0;

    //颜色表大小，以字节为单位，灰度图像颜色表为1024字节，彩色图像颜色表大小为0

    int colorTablesize=0;

    if(biBitCount==8)

        colorTablesize=1024;

    //待存储图像数据每行字节数为4的倍数

    int lineByte=(width * biBitCount/8+3)/4*4;

    //以二进制写的方式打开文件

    FILE *fp=fopen(bmpName,"wb");

    if(fp==0) return 0;

    //申请位图文件头结构变量，填写文件头信息

    BITMAPFILEHEADER fileHead;

    fileHead.bfType = 0x4D42;//bmp类型

    //bfSize是图像文件4个组成部分之和

    fileHead.bfSize= sizeof(BITMAPFILEHEADER) + sizeof(BITMAPINFOHEADER)

        + colorTablesize + lineByte*height;

    fileHead.bfReserved1 = 0;

    fileHead.bfReserved2 = 0;

    //bfOffBits是图像文件前3个部分所需空间之和

    fileHead.bfOffBits=54+colorTablesize;

    //写文件头进文件

    fwrite(&fileHead, sizeof(BITMAPFILEHEADER),1, fp);

    //申请位图信息头结构变量，填写信息头信息

    BITMAPINFOHEADER head;

    head.biBitCount=biBitCount;

    head.biClrImportant=0;

    head.biClrUsed=0;

    head.biCompression=0;

    head.biHeight=height;

    head.biPlanes=1;

    head.biSize=40;

    head.biSizeImage=lineByte*height;

    head.biWidth=width;

    head.biXPelsPerMeter=0;

    head.biYPelsPerMeter=0;

    //写位图信息头进内存

    fwrite(&head, sizeof(BITMAPINFOHEADER),1, fp);

    //如果灰度图像，有颜色表，写入文件

    if(biBitCount==8)

        fwrite(pColorTable, sizeof(RGBQUAD),256, fp);       //写位图数据进文件 int count=0;     if(biBitCount==24){//彩色图像

        for(int i=1;i<=N;i++)  {                       for(int j=1;j<=M;j++)   {

     if (*(imgBuf+(i-1)*lineByte+(j-1)*3)==255&&(*(imgBuf+(i-1)*lineByte+(j-1)*3+1)==255)&&(*(imgBuf+(i-1)*lineByte+(j-1)*3+2)==255))     {     // *(imgBuf+(i-1)*lineByte+(j-1)*3)=0;     // *(imgBuf+(i-1)*lineByte+(j-1)*3+1)=0;      d[N+1-i][j]=1;     }     else     {      d[N+1-i][j]=0;     }

   }  }  }  for (i=1;i<=N;i++)  {   for (j=1;j<=M;j++)   {    for (k=0;k<8;k++)    {     //为每个坐标赋各个方向距离值，只有2点都为1的时候才有距离     if (d[i][j]!=0)     {      //x坐标变大，j变大，y坐标变大，i变小！      if (d[i-dire[k][1]][j+dire[k][0]]!=0)//保证dire[k][0]+1，dire[k][1]+1非负      {       juli[i][j][dire[k][0]+1][dire[k][1]+1]=sqrt(dire[k][0]*dire[k][0]+dire[k][1]*dire[k][1]);      }           }    }   }  }  //我的动态规划采取波浪外推得方式，就是令终点周围的点先获取最短路，然后再类似往外层扩散  i=N;j=M;  int t=0,m_t;  if (N<M) m_t=N;  else m_t=M;    //开始按照正方形往外推  while(t<m_t)  {   i=N-t;   for (j=M;j>=M-t;j--)   {    if (i==N&&j==M){     c[i][j]=0;}    else    {     minDire(i,j);    }   }   j=M-t;   for (i=N;i>=N-t;i--)   {    if (i==N&&j==M){     c[i][j]=0;}    else    {     minDire(i,j);    }   }      t++;  }  //然后一排一排的往外推  if (N<M)  {   for(j=M-N;j>=1;j--)    for (i=N;i>=1;i--)    {     minDire(i,j);    }      }  else  {   for(i=N-M;i>=1;i--)    for (j=M;j>=1;j--)    {    minDire(i,j);    }  }//  i=1;j=1; printf("请输入第几行，第几列：/n"); scanf("%d%d",&i,&j); roadPath(i,j,lineByte,imgBuf); 

    fwrite(imgBuf, height*lineByte, 1, fp); fclose(fp);

    return 1;

}

//----------------------------------------------------------------------------------------//以下为像素的读取函数void xiang_su_du_qu()

{

    //读入指定BMP文件进内存

    char readPath[]="map.bmp";

    readBmp(readPath);    //输出图像的信息

    cout<<"width="<<bmpWidth<<" height="<<bmpHeight<<" biBitCount="<<biBitCount<<endl;        //循环变量，图像的坐标

    //每行字节数

    int lineByte=(bmpWidth*biBitCount/8+3)/4*4;

    //循环变量，针对彩色图像，遍历每像素的三个分量

    int m=0,n=0,count_xiang_su=0;

    //将图像左下角1/4部分置成黑色     ofstream outfile("图像像素.txt",ios::in|ios::trunc);

    if(biBitCount==24){//彩色图像

        for(int i=bmpHeight-1;i>=0;i--)  {            for(int j=0;j<bmpWidth;j++)   {                 for(int k=0;k<3;k++)//每像素RGB三个分量分别置0才变成黑色

    {                    m=*(pBmpBuf+i*lineByte+j*3+k);     outfile<<m<<" ";     count_xiang_su++;     if(count_xiang_su%bmpWidth==0)     {      outfile<<endl;     }    }              n++;            }

        }  cout<<"总的像素个素为:"<<n<<endl;  cout<<"----------------------------------------------------"<<endl;

    }        //将图像数据存盘        char writePath[]="nvcpy.BMP";//图片处理后再存储

    saveBmp(writePath, pBmpBuf, bmpWidth, bmpHeight, biBitCount, pColorTable);

    //清除缓冲区，pBmpBuf和pColorTable是全局变量，在文件读入时申请的空间 delete []pBmpBuf;    if(biBitCount==8)        delete []pColorTable;

}

//画出任意坐标点到终点最短路径的路线void roadPath(int i,int j,int m_lineByte,unsigned char *m_pBmpBuf){ int flag=0,i1,j1; for (i1=0;i1<=2;i1++) {  for(j1=0;j1<=2;j1++)  {   if (road[i][j][i1][j1]==1)    {    *(m_pBmpBuf+(N-1-(i-1))*m_lineByte+(j-1)*3+2)=255;    *(m_pBmpBuf+(N-1-(i-1))*m_lineByte+(j-1)*3+1)=0;    *(m_pBmpBuf+(N-1-(i-1))*m_lineByte+(j-1)*3)=0;

    *(m_pBmpBuf+(N-1-(i-(j1-1)-1))*m_lineByte+((j+(i1-1)-1))*3+2)=255;    *(m_pBmpBuf+(N-1-(i-(j1-1)-1))*m_lineByte+(j+(i1-1)-1)*3+1)=0;    *(m_pBmpBuf+(N-1-(i-(j1-1)-1))*m_lineByte+(j+(i1-1)-1)*3+0)=0;

    if ((i-(j1-1))!=N||(j+(i1-1))!=M)    {     roadPath(i-(j1-1),j+(i1-1),m_lineByte,m_pBmpBuf);    }   }    } }           

}

//八个方向的最短路void minDire(int i,int j){ double min=1000; for (int k=0;k<8;k++) {  if (juli[i][j][dire[k][0]+1][dire[k][1]+1])  {   if( (c[i-dire[k][1]][j+dire[k][0]]+juli[i][j][dire[k][0]+1][dire[k][1]+1]) <min)   {    min=c[i-dire[k][1]][j+dire[k][0]]+juli[i][j][dire[k][0]+1][dire[k][1]+1];    c[i][j]=min;    //先对原来存储的清0    for (int i1=0;i1<=2;i1++)    {     for(int j1=0;j1<=2;j1++)     {      road[i][j][i1][j1]=0;     }    }        road[i][j][dire[k][0]+1][dire[k][1]+1]=1;   }     } }}

void main(){    xiang_su_du_qu();}