1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165
| /**
* Gray-Level Watershed Segmentation
*
* @author Xavier Philippeau
*/
public class WatershedGrayLevel {
// original gray-level image
private int width,height;
private int[][] image = null;
private final int GRAYLEVEL = 256;
// region map
private int[][] rmap = null;
private int maxid=0;
private int WATERSHED=-1;
// pixel and list of pixel structure
class Pixel {
int x,y,level;
public Pixel(int x,int y,int l) {
this.x=x; this.y=y; this.level=l;
}
}
class ListOfPixels extends LinkedList<Pixel> {}
// list of pixels (one per level) to process
private ListOfPixels[] explorelist;
// offsets of the 8 neighbors
private int[] dx8 = new int[] {-1, 0, 1, 1, 1, 0,-1,-1};
private int[] dy8 = new int[] {-1,-1,-1, 0, 1, 1, 1, 0};
// ---------------------------------------------------
public WatershedGrayLevel(int[][] image, int width, int height, boolean isBrightOnDark) {
this.image = image;
this.width = width;
this.height = height;
// negative image if needed
if (isBrightOnDark)
for(int y=0;y<height;y++)
for(int x=0;x<width;x++)
this.image[x][y]=GRAYLEVEL-1-this.image[x][y];
}
// ------------------------------------------------------------------------------------
// allocate memory
private void init() {
maxid=0;
this.rmap = new int[this.width][this.height];
this.explorelist = new ListOfPixels[GRAYLEVEL];
for(int i=0;i<GRAYLEVEL;i++)
this.explorelist[i]=new ListOfPixels();
}
// free memory
private void clear() {
this.rmap = null;
this.explorelist = null;
}
// ------------------------------------------------------------------------------------
// gray-level watershed algorithm : return the boolean watershep map
public boolean[][] process(int step) {
init();
// flooding level by level
int level=0,yoffset=0;
while(level<GRAYLEVEL) {
// extend region by exploring neighbors of known pixels
while(true) {
Pixel p = nextPixel(level,step);
if (p==null) break;
extend(p);
}
// find a new seed for this level
Pixel seed = findSeed(level,yoffset);
if (seed!=null) {
// create and assign a new region to this seed
this.rmap[seed.x][seed.y]=(++maxid);
yoffset=seed.y;
// add this seed to the list of pixel to explore
explorelist[level].add(seed);
} else {
// no more seed for this level -> next level
level++;
yoffset=0;
}
}
// build the watershed map
boolean[][] shedmap = new boolean[this.width][this.height];
for(int y=0;y<this.height;y++)
for(int x=0;x<this.width;x++)
if (this.rmap[x][y]==WATERSHED) shedmap[x][y]=true;
// free memory
clear();
// return the watershed map
return shedmap;
}
// find a seed ( = unassigned pixel ) at the specified level
private Pixel findSeed(int level,int yoffset) {
for (int y = yoffset; y < this.height; y++)
for (int x = 0; x < this.width; x++)
if (this.image[x][y]==level && this.rmap[x][y]==0)
return new Pixel(x,y,level);
return null;
}
// return the next pixel to explore
private Pixel nextPixel(int level, int step) {
// return the first pixel found in the explorelist
for(int i=level;i<level+step && i<GRAYLEVEL;i++) {
if (!explorelist[i].isEmpty())
return explorelist[i].remove(0);
}
return null;
}
// explore the 8 neighbors of a pixel and set the region
private void extend(Pixel p) {
int region=this.rmap[p.x][p.y];
// this pixel is a watershed => cannot extend it
if (region==WATERSHED) return;
// for each neighbor pixel
for(int k=0;k<8;k++) {
int xk = p.x+dx8[k];
int yk = p.y+dy8[k];
if (xk<0 || xk>=this.width) continue;
if (yk<0 || yk>=this.height) continue;
// level and region of neighbor
int vk = this.image[xk][yk];
int rk = this.rmap[xk][yk];
// neighbor is a watershed => ignore
if (rk==-1) continue;
// neighbor as no region assigned => set it
if (rk==0) {
this.rmap[xk][yk]=region;
this.explorelist[vk].add(new Pixel(xk,yk,vk));
continue;
}
// neighbor is assigned to the same region => nothing to do
if (rk==region) continue;
// neighbor is assigned to another region => it's a watershed
this.rmap[xk][yk]=-1;
}
}
} |