Java课程设计-连通问题

第1章课题概述本次Java课程设计的题目是求解一个bmp格式图片中像素点互相连通的面积。1.1课题的目的连通问题在日常生活中非常常见，比如说互联网络、每个城市的道路连通都属于连通相关的问题，在本次课设中是求解一个bmp格式图片中像素点之间的连通，可以通过本程序来，采用数据结构中图的知识可以高效率直接计算出图片中连通分量的数量和每一个连通分量的面积，这样比人为判断连通问题更加简单、快捷。1.2课题的要求1.2.1文件格式的概述BMP文件格式，又称为Bitmap（位图）或是DIB(Device-Independent

Device，设备无关位图)，是Windows系统中广泛使用的图像文件格式。由于它可以不作任何变换地保存图像像素域的数据，因此成为我们取得RAW数据的重要来源。Windows的图形用户界面（graphical

user

interfaces）也在它的内建图像子系统GDI中对BMP格式提供了支持。

下面以UltraEdit为分析工具，用16进制打开bmp格式图片，其内容信息如下所示:图1-1Bmp格式详解图1.2.2程序实现的功能要求程序的目标是：根据给定的黑白位图，分析出所有独立连通的群体，输出每个连通群体的面积。所谓面积，就是它含有的像素的个数。第2章课设概要2.1程序运行流程根据课设的题目的要求，要实现bmp图片中像素点连通的数量和每个连通分量的面积，程序只需要选择本地的一张图片，不需要进行程序的输入和输出。图2-1整个程序各功能模块间的流程2.2bmp格式图片数据的存储结构in.bmp文件如下：t1.bmp文件如下：BMP是常见的图像存储格式。如果用来存黑白图像（颜色深度=1），则其信息比较容易读取。与之相关的数据：（以下偏移均是从文件头开始）偏移：10字节,长度4字节：图像数据真正开始的位置。偏移：18字节,长度4字节：位图的宽度，单位是像素。偏移：22字节,长度4字节：位图的高度，单位是像素。从图像数据开始处，每个像素用1个二进制位表示。从图片的底行开始，一行一行向上存储。Windows规定图像文件中一个扫描行所占的字节数必须是4字节的倍数，不足的位均以0填充。例如，图片宽度为45像素，实际上每行会占用8个字节。可以通过Windows自带的画图工具生成和编辑二进制图像。需要在“属性”中选择“黑白”，指定为二值图像。可能需要通过查看|缩放|自定义...把图像变大比例一些，更易于操作。图像的左下角为图像数据的开始位置。白色对应1，黑色对应0我们可以定义：两个点距离如果小于2个像素，则认为这两个点连通。也就是说：以一个点为中心的九宫格中，围绕它的8个点与它都是连通的。如：t1.bmp所示，左下角的点组成一个连通的群体；而右上角的点都是孤立的。2.3图片选择的合法性判断Bmp格式图片Windows系统最基本的图片信息存储格式，格式文件用固定的格式来存储每一张图片的信息，只有选择了正确图片，才能保证IO流对文件的正确读写，保证程序不会崩溃。如果用户选择一个不是bmp格式的文件，在读取文件信息的就会出现相应的异常，可以针对这种异常进行判断程序格式图片选择是否合法。2.4各个操作算法的描述2.4.1递归算法在定义一个过程或函数时出现调用本过程或本函数的成分,称之为递归[1]。若调用自身,称之为直接递归。若过程或函数p调用过程或函数q,而q又调用p,称之为间接递归。如果一个递归过程或递归函数中递归调用语句是最后一条执行语句,则称这种递归调用为尾递归。图2-1递归算法示意图2.4.2图的深度优先遍历算法图的深度优先遍历[2]是连通图的一种遍历策略。其基本思想如下：设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的边(x，y)。若发现顶点y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边(x，y)到达未曾访问过的y，对y访问并将其标记为已访问过；然后从y开始搜索，直到搜索完从y出发的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点x，并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。图的深度优先遍历示意图如下：图2-1图的深度优先搜索示意图第3章程序图形界面的设计3.1主窗体的设计3.2.1主窗体的布局和设计程序的主窗体是一个JFrame顶级窗体，采用的是边界布局管理器（BorderLayout）,为主窗体定义一个静态的桌面面板组件，用于存放所有的内部窗体，将其至于主窗体边界布局的中心部位，然后定义一个标签组件，设置内容为图片，将其置于桌面面板的最底部，显示主窗体的主界面图片。图3-1程序主界面设计主窗体的代码展示/** * */ privatestaticfinallongserialVersionUID=1L;//版本号 publicstaticJDesktopPaneDESKTOP_PANE=newJDesktopPane();//创建桌面面板 JMenuItemconnetion_item,exit_item,help_item,exit_system;//声明菜单项 publicstaticMap<String,JInternalFrame>map=newHashMap<String,JInternalFrame>();//创建集合，用来保存的所有的内部窗格 MainJFrame(){ Containerc=this.getContentPane(); setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); setSize(780,600); ImageIconicon=CreateIcon.getIcon("image.jpg"); if(icon.getIconWidth()==-1){//当没有读取到图片的时候 JOptionPane.showMessageDialog(this, "图片加载失败,头图像设置失败!\n请将images文件夹放置至D盘下再重新运行!"); System.exit(-1); }else this.setIconImage(icon.getImage()); //在屏幕中间显示顶级窗体 Toolkittoolkit=Toolkit.getDefaultToolkit(); DimensionscreenSize=toolkit.getScreenSize(); intx=(screenSize.width-getSize().width)/2; inty=(screenSize.height-getSize().height)/2; setLocation(x,y); setResizable(false);//设置窗口不可改变大小 setTitle("连通问题"); JMenuBarjmb=null; jmb=createJMenuBar(); setJMenuBar(jmb);//设置菜单栏 //设置背景图片标签 JLabellabel=newJLabel(); icon=CreateIcon.getIcon("back.jpg"); if(icon.getIconWidth()==-1){ JOptionPane.showMessageDialog(this,"背景图片加载失败,窗体打开失败!"); System.exit(-1); }else{ label.setBounds(0,0,icon.getIconWidth(),icon.getIconHeight()); label.setIcon(icon); } //向面板中添加组件 DESKTOP_PANE.add(label,newInteger(Integer.MIN_VALUE)); c.add(DESKTOP_PANE,BorderLayout.CENTER); setVisible(true);//设置窗体可见 } /** *创建菜单栏 * *@return菜单栏 */ privateJMenuBarcreateJMenuBar(){ JMenuBarmenuBar=newJMenuBar(); JMenuopen=newJMenu(); open.setIcon(CreateIcon.getIcon("open.jpg"));//打开 connetion_item=newJMenuItem(); connetion_item.setIcon(CreateIcon.getIcon("connection.jpg")); connetion_item.addActionListener(this); open.add(connetion_item); exit_item=newJMenuItem(); exit_item.setIcon(CreateIcon.getIcon("exists.jpg")); exit_item.addActionListener(this); open.addSeparator(); open.add(exit_item); menuBar.add(open); JMenuhelp=newJMenu(); help.setIcon(CreateIcon.getIcon("help.jpg"));//帮助 help_item=newJMenuItem(); help_item.setIcon(CreateIcon.getIcon("Instructions.jpg")); help_item.addActionListener(this); help.add(help_item); menuBar.add(help); JMenuexit=newJMenu(); exit.setIcon(CreateIcon.getIcon("exist.jpg"));//退出 exit_system=newJMenuItem(); exit_system.setIcon(CreateIcon.getIcon("exists.jpg")); exit_system.addActionListener(this); exit.add(exit_system); menuBar.add(exit); returnmenuBar; }3.2内部窗体的设计3.2.1连通求解窗体的设计连通问题求解窗体是一个内部窗体，是镶嵌在主窗体的内部，其采用边界布局管理器（BorderLayout）,北部添加一个图片标签；南部添加一个面板，面板设置成流布局管理器，右对齐，再在面板中添加确定和取消按钮，并加坚监听效果；中部添加一个面板，设置成流布局，在中部面板中添加文本面板和相应的标签和文本框。最后选择图片后，在文本面板中显示连通详细。图3-2连通求解窗体设计连通求解内部窗体的代码展示/** * */ privatestaticfinallongserialVersionUID=1L; JTextFieldfileName,result; JTextPanetextPane; JButtonconfirm,cancel,openFile; publicConnectionFrame(){ Containerc=this.getContentPane(); c.setLayout(newBorderLayout()); setIconifiable(true);//设置窗体可最小化 setResizable(false);//设置窗体不可改变大小 setClosable(true);//设置窗体可关闭 setTitle("连通问题");//设置窗体标题 setBounds(100,10,600,500);//设置窗体位置和大小 Iconicon=CreateIcon.getIcon("headLabel.jpg"); if(icon.getIconWidth()==-1) JOptionPane.showMessageDialog(this,"图片丢失,图标设置失败!"); else setFrameIcon(icon); //北部面板 JPanelnorthPane=newJPanel(); northPane.setBorder(newEtchedBorder()); JLabell1=newJLabel(); icon=CreateIcon.getIcon("bb.jpg"); if(icon.getIconWidth()==-1) JOptionPane.showMessageDialog(this,"图片丢失,请先添加图片再重新启动!"); else l1.setIcon(icon); northPane.add(l1); //中间面板 JPanelcenterPane=newJPanel(); centerPane.setBorder(newTitledBorder("连通图片")); centerPane.setLayout(newFlowLayout(FlowLayout.CENTER)); textPane=newJTextPane(); textPane.setCaretColor(Color.BLUE); textPane.setSelectedTextColor(Color.RED); textPane.setEditable(false); textPane.setPreferredSize(newDimension(500,250)); JScrollPanejsp=newJScrollPane(textPane); jsp.setVerticalScrollBarPolicy(JScrollPane.VERTICAL_SCROLLBAR_ALWAYS);//始终显示滚动条 openFile=newJButton(); openFile.addActionListener(this); openFile.setIcon(CreateIcon.getIcon("openFile.jpg")); openFile.setPreferredSize(newDimension(77,29));//设定指定组件的大小 JLabeljl1=newJLabel("文件:"); fileName=newJTextField(10); fileName.setFont(newFont("宋体",Font.BOLD,18)); JLabeljl2=newJLabel("连通结果:"); result=newJTextField(18); result.setFont(newFont("宋体",Font.BOLD,16)); result.setEditable(false); JPaneljp4=newJPanel(); jp4.setLayout(newFlowLayout(FlowLayout.RIGHT,20,10)); jp4.add(jl1); jp4.add(fileName); jp4.add(openFile); jp4.add(jl2); jp4.add(result); centerPane.add(jsp); centerPane.add(jp4); //南部面板 JPanelsouthPanel=newJPanel(); southPanel.setBorder(newEtchedBorder()); southPanel.setLayout(newFlowLayout(FlowLayout.RIGHT,60,5)); confirm=newJButton(); confirm.addActionListener(this); confirm.setPreferredSize(newDimension(65,34)); confirm.setIcon(CreateIcon.getIcon("confirm.jpg")); cancel=newJButton(); cancel.addActionListener(this); cancel.setPreferredSize(newDimension(65,34)); cancel.setIcon(CreateIcon.getIcon("cancel.jpg")); southPanel.add(confirm); southPanel.add(cancel); //将各个面便添加到容器中 c.add(northPane,BorderLayout.NORTH); c.add(centerPane,BorderLayout.CENTER); c.add(southPanel,BorderLayout.SOUTH); setVisible(true); }3.2.2使用说明窗体设计使用说明窗体为内部窗体，采用边界布局管理器，在中部添加一个滚动面板，在面板中添加一个使用图片标签，并设置内部窗体为可最小化，可关闭属性。图3-3使用说明窗体设计使用说明窗体代码展示/** * */ privatestaticfinallongserialVersionUID=1L; publicUseInstructions(){ Containerc=this.getContentPane(); c.setLayout(newBorderLayout()); setIconifiable(true);//设置窗体可最小化 setClosable(true);//设置窗体可关闭 setTitle("使用说明");//设置窗体标题 setBounds(60,10,650,500);//设置窗体位置和大小 Iconicon=CreateIcon.getIcon("headLabel.jpg"); if(icon.getIconWidth()==-1) JOptionPane.showMessageDialog(this,"图片加载失败!头标签设置失败!"); else setFrameIcon(icon); //设置中间面板 JPanelcenter=newJPanel(); center.setBorder(newEtchedBorder());//设置边框 JLabellabel=newJLabel(); icon=CreateIcon.getIcon("useInstructions.jpg"); if(icon.getIconWidth()==-1) JOptionPane.showMessageDialog(this,"图片加载失败!"); else label.setIcon(icon); JScrollPanescrollPane=newJScrollPane(label); c.add(scrollPane); setVisible(true); }第4章程序功能的实现4.1bmp格式文件的读取4.2.1bmp图片分辨率的读取偏移：18字节,长度4字节：位图的宽度，单位是像素。偏移：22字节,长度4字节：位图的高度，单位是像素。创建Java随机读取文件流，从文件头开始跳过18个字节，开始读取解析文件的大小，将读取出来的信息存放在一个二维数组中:RandomAccessFilera=newRandomAccessFile(file,"r"); ra.seek(18); byteb[]=newbyte[8];//储存八个字节大小的图片的宽度和高度 for(inti=0;i<b.length;i++){ b[i]=ra.readByte(); }在bmp格式图片存储文件中，存储图片宽度或高度有4byte,前一个字节为低位，而最后一个字节为高位，因此要用位运算符进行解析数据，如图:图4-1图片大小存储格式解析图高度和宽度的计算://读取图片的宽度和高度 width=(int)((b[0]&0xFF)|((b[1])<<8&0xFF00) |((b[2]<<16)&0xFF0000)|((b[3]<<24)&0xFF000000)); height=(int)((b[4]&0xFF)|((b[5])<<8&0xFF00) |((b[6]<<16)&0xFF0000)|((b[7]<<24)&0xFF000000)); point=newint[height][width];4.2.2bmp图片连通信息的读取要获取连通信息，必须将读取的信息保存起来，这里定义一个二维数组用来保存图片信息，即每一个像素点的信息（0或1），所以二维数组的行数为图片的高度，列数为图片的宽度。publicstaticint[][]point;//邻接矩阵存储二维数组，存储文件信息point=newint[height][width];Windows规定图像文件中一个扫描行所占的字节数必须是4字节的倍数，不足的位均以0填充，因此必须先确定每一行的字节数，保证其字节数为4的倍数。//计算出每行所需的最少字节数,保证每行的字节数是4的倍数 intwByteNum=(width%8==0)?(width/8):(width/8+1);//字节数 if(wByteNum%4!=0){ wByteNum=(wByteNum/4+1)*4;//将每一行的字节数变成4字节的倍数 }从图像数据开始处，每个像素用1个二进制位表示。所以每次从文件中读取一个字节，读取出来的是一个整数，用Java内库的方法将该整数转换成一个String型的二进制数，但是这个二进制数可能长度超过8，也可能小于8，因此要用字符串变量对其字符串进行处理，长度大于8时截取字符串的后8个字符，当长度小于8时，对其前面补0处理，最后将字符串型的二进制串解析成整数存在二位数组中，最后通过判断二位数组的信息来判断连通信息。StringBuffersb; for(inti=0;i<height;i++){ for(intp=0,j=0;p<wByteNum;p++){ sb=newStringBuffer(Integer.toBinaryString(ra.readByte())); //当二进位字符串长度大于8，截取低8位 if(sb.length()>8){ sb.delete(0,sb.length()-8); } //当二进位字符串长度小于8，前面补0直至二进制位为8位 while(sb.length()<8){ sb.insert(0,0); } //将二进制字符串转换成整数，存到二维数组中 for(intch=0;ch<sb.length()&&j<width;ch++){ point[i][j++]=Integer.parseInt(sb.charAt(ch)+""); } } }4.2连通求解功能的实现用Windows系统的中画图软件打开bmp格式文件，将其放大，可以看到图片中每一个像素点的信息，它对应着二位数组中的数值，即每一个黑色像素点代表二位数组值为0的单元，反之白色代表数值1的单元，可以通过判断二位数组中的值的信息来判断像素点之间的连通情况。图4-2bmp图片像素点信息判断像素点之间连通情况，必须用数据结构中的递归算法和图的深度优先遍历算法，这里可以将所有黑点看作是一个数据结构中的图，每一个黑点代表图中的一个顶点，从二维数组的0行0列开始遍历，另外定义一个布尔型的二维数组，标记每一个定点是否被访问过，当该定点被访问过，将其值设为true,否则为false,避免程序下一次再重新访问。当访问到下一个没有被访问的顶点时，递归调用该方法访问该点周围的8个定点，当周围的顶点已被访问过就不访问，直到该连通分量的每一个点都被访问且周围8个定点都为白色像素点，即该连通分量结束，继续访问下一个连通分量。当二维数组中的每一点都被访问过了，整个图的遍历就结束。//访问二维数组，判断是否连通 for(intx=point.length-1;x>=0;x--){ for(inty=0;y<point[x].length;y++){ result=0; resultList.add(0); scanner(x,y);//扫描当前点 if(result==0){ resultList.remove(resultList.size()-1); } } } ra.close();//关闭流,释放资源 } /** *扫描每一个点的周围点 * *@paramx *@paramy */ publicvoidscanner(intx,inty){ if(x<0||x>=height||y<0||y>=width){ return; } if(!visited[x][y]){ visited[x][y]=true; resultList.set(resultList.size()-1,result); if(point[x][y]==0){ result++; //递归调用,分别判断该点与周围八个点是否于当前点连通 scanner(x-1,y); scanner(x-1,y-1); scanner(x-1,y+1); scanner(x+1,y); scanner(x+1,y-1); scanner(x+1,y+1); scanner(x,y-1); scanner(x,y+1); } } }}第5章程序的调试和问题的解决在进行课程设计的过程中，遇到了很多的Bug，最后通过网上查阅资料和在老师的指导下，终于解决了所有的错误，其出现的问题及解决办法如下所示:1.在进行图片大小的读取的过程中，为什么读到的宽度和高度为负数？解决办法:当时读取图片宽度和高度的时候，只读取了最低位的一个字节，8bit，刚好该字节的最高位为1，此时程序把第一位当作了符号位，结果读出来的就是一个负数；最后将存储宽度的4个字节全部读取到一个字节数组中，进行移位运算，最后得到正确的答案。2.在程序运行过程之中，二位数组的连通信息和像素点的信息已经保持一致，但是判断连通分量和面积的时候为什么判断出来的面积错误呢?解决办法:当扫描二位数组中的数据时候，正常情况下扫描到图片的尾端就不进行扫描了，但是由于程序中没有进行终止，导致程序又进行错误的扫描，最后导致结果错误。 if(x<0||x>=height||y<0||y>=width){ return; }第6章程序测试及分析运行程序，首先显示的是程序主界面，可以进行功能的选择，即连通求解、使用说明、退出程序。图6-1程序运行主窗体主窗体显示出来之后，打开连通求解内部窗体，选择正确的bmp格式图片，求解图片中连通信息，这里选择课设要求进行测试连通