17863人阅读
图像处理（94）
泛洪填充算法(Flood Fill Algorithm)
泛洪填充算法又称洪水填充算法是在很多图形绘制软件中常用的填充算法，最熟悉不过就是
windows paint的油漆桶功能。算法的原理很简单，就是从一个点开始附近像素点，填充成新
的颜色，直到封闭区域内的所有像素点都被填充新颜色为止。泛红填充实现最常见有四邻域
像素填充法，八邻域像素填充法，基于扫描线的像素填充方法。根据实现又可以分为递归与
非递归（基于栈）。
在介绍算法的三种实现方式之前，首先来看一下测试该算法的UI实现。基本思路是选择一
张要填充的图片，鼠标点击待填充的区域内部，算法会自动填充该区域，然后UI刷新。完
整的UI代码如下：
package com.gloomyfish.paint.
import java.awt.C
import java.awt.D
import java.awt.G
import java.awt.Graphics2D;
import java.awt.MediaT
import java.awt.event.MouseE
import java.awt.event.MouseL
import java.awt.image.BufferedI
import java.io.F
import java.io.IOE
import javax.imageio.ImageIO;
import javax.swing.JC
import javax.swing.JFileC
import javax.swing.JF
public class FloodFillUI extends JComponent implements MouseListener{
private static final long serialVersionUID = 1L;
private BufferedImage rawI
private MediaT
private Dimension myS
FloodFillA
public FloodFillUI(File f)
rawImg = ImageIO.read(f);
} catch (IOException e1) {
e1.printStackTrace();
tracker = new MediaTracker(this);
tracker.addImage(rawImg, 1);
// blocked 10 seconds to load the image data
if (!tracker.waitForID(1, 10000)) {
System.out.println(&Load error.&);
System.exit(1);
}// end if
} catch (InterruptedException e) {
e.printStackTrace();
System.exit(1);
}// end catch
mySize = new Dimension(300, 300);
this.addMouseListener(this);
ffa = new FloodFillAlgorithm(rawImg);
JFrame imageFrame = new JFrame(&Flood File Algorithm Demo - Gloomyfish&);
imageFrame.getContentPane().add(this);
imageFrame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
imageFrame.pack();
imageFrame.setVisible(true);
public void paint(Graphics g) {
Graphics2D g2 = (Graphics2D)
g2.drawImage(rawImg, 10, 10, rawImg.getWidth(), rawImg.getHeight(), null);
public Dimension getPreferredSize() {
return myS
public Dimension getMinimumSize() {
return myS
public Dimension getMaximumSize() {
return myS
public static void main(String[] args) {
JFileChooser chooser = new JFileChooser();
chooser.showOpenDialog(null);
File f = chooser.getSelectedFile();
new FloodFillUI(f);
public void mouseClicked(MouseEvent e) {
System.out.println(&Mouse Clicked Event!!&);
int x = (int)e.getPoint().getX();
int y = (int)e.getPoint().getY();
System.out.println(&mouse location x = & + x); // column
System.out.println(&mouse location y = & + y); // row
System.out.println();
long startTime = System.nanoTime();
// ffa.floodFill4(x, y, Color.GREEN.getRGB(), ffa.getColor(x, y));
// ffa.floodFill8(x, y, Color.GREEN.getRGB(), ffa.getColor(x, y));
// ffa.floodFillScanLine(x, y, Color.GREEN.getRGB(), ffa.getColor(x, y)); //
ffa.floodFillScanLineWithStack(x, y, Color.GREEN.getRGB(), ffa.getColor(x, y)); // -
long endTime = System.nanoTime() - startT
System.out.println(&run time = & + endTime);
ffa.updateResult();
this.repaint();
public void mousePressed(MouseEvent e) {
// TODO Auto-generated method stub
public void mouseReleased(MouseEvent e) {
// TODO Auto-generated method stub
public void mouseEntered(MouseEvent e) {
// TODO Auto-generated method stub
public void mouseExited(MouseEvent e) {
// TODO Auto-generated method stub
首先介绍四邻域的泛洪填充算法，寻找像素点p(x, y)的上下左右四个临近像素点，如果没有
被填充，则填充它们，并且继续寻找它们的四邻域像素，直到封闭区域完全被新颜色填充。
蓝色方格为四个邻域像素， p(x, y)为当前像素点。
基于递归实现代码很简单：
public void floodFill4(int x, int y, int newColor, int oldColor)
if(x &= 0 && x & width && y &= 0 && y & height
&& getColor(x, y) == oldColor && getColor(x, y) != newColor)
setColor(x, y, newColor); //set color before starting recursion
floodFill4(x + 1, y,
newColor, oldColor);
floodFill4(x - 1, y,
newColor, oldColor);
floodFill4(x,
y + 1, newColor, oldColor);
floodFill4(x,
y - 1, newColor, oldColor);
八邻域的填充算法，则是在四邻域的基础上增加了左上，左下，右上，右下四个相邻像素。
并递归寻找它们的八邻域像素填充，直到区域完全被新颜色填充。
蓝色方格为四个邻域像素，黄色为左上，左下，右上，右下四个像素， p(x, y)为当前像素点。
基于递归实现的代码也很简单：
public void floodFill8(int x, int y, int newColor, int oldColor)
if(x &= 0 && x & width && y &= 0 && y & height &&
getColor(x, y) == oldColor && getColor(x, y) != newColor)
setColor(x, y, newColor); //set color before starting recursion
floodFill8(x + 1, y,
newColor, oldColor);
floodFill8(x - 1, y,
newColor, oldColor);
floodFill8(x,
y + 1, newColor, oldColor);
floodFill8(x,
y - 1, newColor, oldColor);
floodFill8(x + 1, y + 1, newColor, oldColor);
floodFill8(x - 1, y - 1, newColor, oldColor);
floodFill8(x - 1, y + 1, newColor, oldColor);
floodFill8(x + 1, y - 1, newColor, oldColor);
基于扫描线实现的泛洪填充算法的主要思想是根据当前输入的点p(x, y)，沿y方向分别向上
与向下扫描填充，同时向左p(x-1, y)与向右p(x+1, y)递归寻找新的扫描线，直到递归结束。
代码如下：
public void floodFillScanLine(int x, int y, int newColor, int oldColor)
if(oldColor == newColor)
if(getColor(x, y) != oldColor)
//draw current scanline from start position to the top
while(y1 & height && getColor(x, y1) == oldColor)
setColor(x, y1, newColor);
//draw current scanline from start position to the bottom
y1 = y - 1;
while(y1 &= 0 && getColor(x, y1) == oldColor)
setColor(x, y1, newColor);
//test for new scanlines to the left
while(y1 & height && getColor(x, y1) == newColor)
if(x & 0 && getColor(x - 1, y1) == oldColor)
floodFillScanLine(x - 1, y1, newColor, oldColor);
y1 = y - 1;
while(y1 &= 0 && getColor(x, y1) == newColor)
if(x & 0 && getColor(x - 1, y1) == oldColor)
floodFillScanLine(x - 1, y1, newColor, oldColor);
//test for new scanlines to the right
while(y1 & height && getColor(x, y1) == newColor)
if(x & width - 1 && getColor(x + 1, y1) == oldColor)
floodFillScanLine(x + 1, y1, newColor, oldColor);
y1 = y - 1;
while(y1 &= 0 && getColor(x, y1) == newColor)
if(x & width - 1 && getColor(x + 1, y1) == oldColor)
floodFillScanLine(x + 1, y1, newColor, oldColor);
基于递归实现的泛洪填充算法有个致命的缺点，就是对于大的区域填充时可能导致JAVA栈溢出
错误，对最后一种基于扫描线的算法，实现了一种非递归的泛洪填充算法。
public void floodFillScanLineWithStack(int x, int y, int newColor, int oldColor)
if(oldColor == newColor) {
System.out.println(&do nothing !!!, filled area!!&);
emptyStack();
boolean spanLeft, spanR
push(x, y);
while(true)
x = popx();
if(x == -1)
y = popy();
while(y1 &= 0 && getColor(x, y1) == oldColor) y1--; // go to line top/bottom
y1++; // start from line starting point pixel
spanLeft = spanRight =
while(y1 & height && getColor(x, y1) == oldColor)
setColor(x, y1, newColor);
if(!spanLeft && x & 0 && getColor(x - 1, y1) == oldColor)// just keep left line once in the stack
push(x - 1, y1);
spanLeft =
else if(spanLeft && x & 0 && getColor(x - 1, y1) != oldColor)
spanLeft =
if(!spanRight && x & width - 1 && getColor(x + 1, y1) == oldColor) // just keep right line once in the stack
push(x + 1, y1);
spanRight =
else if(spanRight && x & width - 1 && getColor(x + 1, y1) != oldColor)
spanRight =
}运行效果：
算法类源代码如下：
package com.gloomyfish.paint.
import java.awt.image.BufferedI
import com.gloomyfish.filter.study.AbstractBufferedImageOp;
public class FloodFillAlgorithm extends AbstractBufferedImageOp {
private BufferedImage inputI
private int[] inP
stack data structure
private int maxStackSize = 500; // will be increased as needed
private int[] xstack = new int[maxStackSize];
private int[] ystack = new int[maxStackSize];
private int stackS
public FloodFillAlgorithm(BufferedImage rawImage) {
this.inputImage = rawI
width = rawImage.getWidth();
height = rawImage.getHeight();
inPixels = new int[width*height];
getRGB(rawImage, 0, 0, width, height, inPixels );
public BufferedImage getInputImage() {
return inputI
public void setInputImage(BufferedImage inputImage) {
this.inputImage = inputI
public int getColor(int x, int y)
int index = y * width +
return inPixels[index];
public void setColor(int x, int y, int newColor)
int index = y * width +
inPixels[index] = newC
public void updateResult()
setRGB( inputImage, 0, 0, width, height, inPixels );
* it is very low calculation speed and cause the stack overflow issue when fill
* some big area and irregular shape. performance is very bad.
* @param x
* @param y
* @param newColor
* @param oldColor
public void floodFill4(int x, int y, int newColor, int oldColor)
if(x &= 0 && x & width && y &= 0 && y & height
&& getColor(x, y) == oldColor && getColor(x, y) != newColor)
setColor(x, y, newColor); //set color before starting recursion
floodFill4(x + 1, y,
newColor, oldColor);
floodFill4(x - 1, y,
newColor, oldColor);
floodFill4(x,
y + 1, newColor, oldColor);
floodFill4(x,
y - 1, newColor, oldColor);
* @param x
* @param y
* @param newColor
* @param oldColor
public void floodFill8(int x, int y, int newColor, int oldColor)
if(x &= 0 && x & width && y &= 0 && y & height &&
getColor(x, y) == oldColor && getColor(x, y) != newColor)
setColor(x, y, newColor); //set color before starting recursion
floodFill8(x + 1, y,
newColor, oldColor);
floodFill8(x - 1, y,
newColor, oldColor);
floodFill8(x,
y + 1, newColor, oldColor);
floodFill8(x,
y - 1, newColor, oldColor);
floodFill8(x + 1, y + 1, newColor, oldColor);
floodFill8(x - 1, y - 1, newColor, oldColor);
floodFill8(x - 1, y + 1, newColor, oldColor);
floodFill8(x + 1, y - 1, newColor, oldColor);
* @param x
* @param y
* @param newColor
* @param oldColor
public void floodFillScanLine(int x, int y, int newColor, int oldColor)
if(oldColor == newColor)
if(getColor(x, y) != oldColor)
//draw current scanline from start position to the top
while(y1 & height && getColor(x, y1) == oldColor)
setColor(x, y1, newColor);
//draw current scanline from start position to the bottom
y1 = y - 1;
while(y1 &= 0 && getColor(x, y1) == oldColor)
setColor(x, y1, newColor);
//test for new scanlines to the left
while(y1 & height && getColor(x, y1) == newColor)
if(x & 0 && getColor(x - 1, y1) == oldColor)
floodFillScanLine(x - 1, y1, newColor, oldColor);
y1 = y - 1;
while(y1 &= 0 && getColor(x, y1) == newColor)
if(x & 0 && getColor(x - 1, y1) == oldColor)
floodFillScanLine(x - 1, y1, newColor, oldColor);
//test for new scanlines to the right
while(y1 & height && getColor(x, y1) == newColor)
if(x & width - 1 && getColor(x + 1, y1) == oldColor)
floodFillScanLine(x + 1, y1, newColor, oldColor);
y1 = y - 1;
while(y1 &= 0 && getColor(x, y1) == newColor)
if(x & width - 1 && getColor(x + 1, y1) == oldColor)
floodFillScanLine(x + 1, y1, newColor, oldColor);
public void floodFillScanLineWithStack(int x, int y, int newColor, int oldColor)
if(oldColor == newColor) {
System.out.println(&do nothing !!!, filled area!!&);
emptyStack();
boolean spanLeft, spanR
push(x, y);
while(true)
x = popx();
if(x == -1)
y = popy();
while(y1 &= 0 && getColor(x, y1) == oldColor) y1--; // go to line top/bottom
y1++; // start from line starting point pixel
spanLeft = spanRight =
while(y1 & height && getColor(x, y1) == oldColor)
setColor(x, y1, newColor);
if(!spanLeft && x & 0 && getColor(x - 1, y1) == oldColor)// just keep left line once in the stack
push(x - 1, y1);
spanLeft =
else if(spanLeft && x & 0 && getColor(x - 1, y1) != oldColor)
spanLeft =
if(!spanRight && x & width - 1 && getColor(x + 1, y1) == oldColor) // just keep right line once in the stack
push(x + 1, y1);
spanRight =
else if(spanRight && x & width - 1 && getColor(x + 1, y1) != oldColor)
spanRight =
private void emptyStack() {
while(popx() != - 1) {
stackSize = 0;
final void push(int x, int y) {
stackSize++;
if (stackSize==maxStackSize) {
int[] newXStack = new int[maxStackSize*2];
int[] newYStack = new int[maxStackSize*2];
System.arraycopy(xstack, 0, newXStack, 0, maxStackSize);
System.arraycopy(ystack, 0, newYStack, 0, maxStackSize);
xstack = newXS
ystack = newYS
maxStackSize *= 2;
xstack[stackSize-1] =
ystack[stackSize-1] =
final int popx() {
if (stackSize==0)
return -1;
return xstack[stackSize-1];
final int popy() {
int value = ystack[stackSize-1];
stackSize--;
public BufferedImage filter(BufferedImage src, BufferedImage dest) {
// TODO Auto-generated method stub
转载文章请务必注明
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：1734689次
积分：18105
积分：18105
排名：第330名
原创：215篇
评论：1062条
个人独立开发者
承接图像处理算法开发
提供图像处理相关技术咨询
精通数据可视化技术
超过12年Java编程经验
特别说明：谢绝源码索取
Java初学者群：
注明来自CSDN
《Java数字图像处理-编程技巧与应用实践》
文章：14篇
阅读：172993
文章：62篇
阅读：658806
(1)(1)(3)(2)(1)(1)(3)(3)(7)(5)(2)(1)(1)(1)(2)(1)(1)(1)(2)(1)(1)(3)(1)(4)(7)(5)(5)(3)(4)(9)(6)(4)(4)(2)(6)(6)(7)(6)(6)(4)(7)(10)(8)(7)(7)(8)(4)(4)(3)(5)(3)(1)(1)(3)(2)(2)(1)(1)(3)(1)(1)(4)一种基于P2P的网络拓扑发现算法--《2007通信理论与技术新发展——第十二届全国青年通信学术会议论文集（下册）》2007年
一种基于P2P的网络拓扑发现算法
【摘要】：网络拓扑是指网络实体及其相互联接关系,网络拓扑发现是指探求网络实体之间联接关系的过程。自动、高效率地探求网络拓扑情况,是现代网络管理系统的基本功能。同时,获得准确的网络拓扑信息,对网络性能优化、路由算法验证及网络拓扑研究也有重要的意义。本文研究了 P2P 技术在网络拓扑发现中的应用,提出了一种基于 P2P 计算的网络拓扑发现算法,仿真实验结果表明,该算法具有较高的效率。
【作者单位】：
【关键词】：
【分类号】：TP393.02【正文快照】：
1引言 现代通信网络节点数量众多且在地理上分散，体系结构复杂，随着无线网络应用和移动IP的增多，网络 拓扑的变化增大。如果人工维护网络拓扑信息，无疑是一项十分繁重的工作，有时甚至是不可能的，所以需 要一种能高效、自动地发现网络拓扑的软件。本文在对常见的网络拓
欢迎：、、)
支持CAJ、PDF文件格式，仅支持PDF格式
【参考文献】
中国期刊全文数据库
杨家海,吴建平,朱虹;[J];清华大学学报(自然科学版);2004年01期
郑洪方;韩传冰;王光兴;;[J];计算机科学;2005年03期
中国硕士学位论文全文数据库
黄晓波;[D];浙江大学;2006年
【共引文献】
中国硕士学位论文全文数据库
李江峰;[D];华中科技大学;2005年
张晓燕;[D];燕山大学;2006年
霍迎秋;[D];西北农林科技大学;2006年
徐峰;[D];上海交通大学;2007年
赵春昊;[D];上海交通大学;2007年
刘鹏;[D];北京邮电大学;2007年
郭绪坤;[D];华南师范大学;2007年
李波;[D];山东科技大学;2007年
王学;[D];大连理工大学;2007年
李旻;[D];武汉科技大学;2005年
【二级参考文献】
中国期刊全文数据库
谢红漫,钱德沛,栾钟治,陈衡;[J];北京航空航天大学学报;2004年06期
赵永翼,王光兴;[J];东北大学学报(自然科学版);2002年02期
刘奕明,陈涵生;[J];计算机工程;2003年21期
刘姝,李成忠;[J];计算机应用研究;2002年02期
由维昭,刘强,韦卫,陈玉健;[J];计算机应用研究;2004年12期
冯新宇,吕建,曹建农;[J];软件学报;2003年05期
李晓鸿,张大方;[J];同济大学学报(自然科学版);2002年10期
朱畅华,裴昌幸,李建东,金旗;[J];西安电子科技大学学报;2002年06期
中国硕士学位论文全文数据库
刘姝;[D];西南交通大学;2002年
陈旭;[D];太原理工大学;2003年
【相似文献】
中国期刊全文数据库
林晓勇;徐名海;吕珺;王发鹏;;[J];计算机工程;2011年13期
申金媛;赵旭东;刘润杰;穆维新;;[J];郑州大学学报(工学版);2011年03期
马志欣;赵鼎新;谢显中;王昭然;;[J];吉林大学学报(理学版);2011年04期
刘恒;何光耀;;[J];电脑知识与技术;2011年19期
李婷;杨文虎;;[J];微计算机信息;2011年08期
董成根;吴今培;张其善;;[J];现代电子技术;2011年11期
张良;杨东;;[J];科技广场;2011年05期
张良;郭延峰;何华;;[J];科技导报;2011年18期
赵新慧;冯锡炜;石元博;;[J];科学技术与工程;2011年21期
张铮;王斌;;[J];微计算机信息;2011年07期
中国重要会议论文全文数据库
王学;郝应光;;[A];2007通信理论与技术新发展——第十二届全国青年通信学术会议论文集（下册）[C];2007年
胡兴华;王惠龄;舒水明;张晓青;丁国忠;吴钢;;[A];第八届全国低温工程大会暨中国航天低温专业信息网2007年度学术交流会论文集[C];2007年
于锦玲;;[A];2007第二届全国广播电视技术论文集2（上）[C];2007年
姜誉;方滨兴;胡铭曾;;[A];全国网络与信息安全技术研讨会'2005论文集（下册）[C];2005年
王健;刘衍珩;徐沛娟;魏达;田大新;;[A];2006全国复杂网络学术会议论文集[C];2006年
王海梅;周献中;;[A];计算机技术与应用进展——全国第17届计算机科学与技术应用（CACIS）学术会议论文集（下册）[C];2006年
赵英勇;高洁;;[A];四川、贵州、云南三省水电厂（站）机电设备运行技术研讨会论文集[C];2010年
常鲜戎;孙耀芹;郑焕坤;;[A];第三届和谐人机环境联合学术会议（HHME2007）论文集[C];2007年
连金欣;郭俊;郑国强;钱云亮;;[A];第九届全国电除尘、第一届脱硫学术会议论文集[C];2001年
高倩;陈德旺;;[A];2007第三届中国智能交通年会论文集[C];2007年
中国重要报纸全文数据库
梁忠辉;[N];通信产业报;2005年
张峰　赵德超;[N];人民邮电;2009年
郎筠;[N];电子报;2006年
齐飞;[N];中国计算机报;2003年
;[N];人民邮电;2008年
卯玉成;[N];通信产业报;2004年
工业和信息化部电信研究院
马军锋　何宝宏;[N];通信产业报;2011年
;[N];人民邮电;2006年
;[N];中国财经报;2003年
北京格林威尔科技发展有限公司;[N];通信产业报;2005年
中国博士学位论文全文数据库
曹佳;[D];中国科学院研究生院（计算技术研究所）;2006年
陈松;[D];电子科技大学;2010年
洪利;[D];中国石油大学;2010年
顾德;[D];浙江大学;2012年
赵静;[D];上海交通大学;2008年
吴廷勇;[D];电子科技大学;2008年
申文武;[D];北京邮电大学;2011年
申文武;[D];北京邮电大学;2011年
吕长虹;[D];南京大学;2000年
胡晓娅;[D];华中科技大学;2006年
中国硕士学位论文全文数据库
李倩;[D];南京师范大学;2002年
陈旭;[D];太原理工大学;2003年
刘家芬;[D];电子科技大学;2004年
张文博;[D];北京邮电大学;2010年
季伟东;[D];哈尔滨理工大学;2004年
段若琳;[D];北京邮电大学;2010年
赵玲;[D];吉林大学;2011年
杨祎;[D];华中师范大学;2003年
付利建;[D];西安电子科技大学;2011年
刘杰;[D];四川大学;2004年
&快捷付款方式
&订购知网充值卡
400-819-9993
《中国学术期刊（光盘版）》电子杂志社有限公司
同方知网数字出版技术股份有限公司
地址：北京清华大学 84-48信箱 大众知识服务
出版物经营许可证 新出发京批字第直0595号
订购热线：400-819-82499
服务热线：010--
在线咨询：
传真：010-
京公网安备75号计算机网络第五章_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
计算机网络第五章
上传于||文档简介
&&计​算​机​网​络​第​五​章​内​容​整​理​
​
​
​
​复​习​回​顾​知​识​必​备​哦​!
阅读已结束，如果下载本文需要使用0下载券
想免费下载更多文档？
定制HR最喜欢的简历
下载文档到电脑，查找使用更方便
还剩5页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢}