- Region Growing Algorithm:
- Select a seed pixel (x,y)
- Examine the nearest neighbors (4 or 8 neighbors depending on whether we assume 4-connectivity or 8-connectivity) of (x,y) one by one.The neighboring pixel is accepted in the same region as (x,y) if they together satisfy the homogeneity property of a region.
- Once a new pixel is accepted as a member of current region, the neighbors of the new pixel are examined. The procedure goes on recursively until no new pixel is accepted. All the pixels of current region are given a unique label.
- Select a new seed pixel and repeat same procedure until all pixels are assigned to some region.
Create Pixel class which has below attributes:
x-position, y-position, rgb value, label.
Pixel.java
package com.imgseg;
public class Pixel {
private int x;
private int y;
private int rgb;
private boolean isTagged;
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
public int getRgb() {
return rgb;
}
public void setRgb(int rgb) {
this.rgb = rgb;
}
public void setTagged(boolean isTagged) {
this.isTagged = isTagged;
}
public boolean isTagged() {
return isTagged;
}
}
Create Region class which has below attributes:
rgb value, List of pixels
Region.java
package com.imgseg;
import java.util.ArrayList;
import java.util.List;
public class Region {
private int rgb;
private List<Pixel> pixelList = new ArrayList<Pixel>();
public int getRgb() {
return rgb;
}
public void setRgb(int rgb) {
this.rgb = rgb;
}
public List<Pixel> getPixelList() {
return pixelList;
}
public void setPixelList(List<Pixel> pixelList) {
this.pixelList = pixelList;
}
}
Create Segmenter class. List of regions is generated.
Segmenter.java
package com.imgseg;
import java.awt.Color;
import java.awt.image.BufferedImage;
import java.awt.image.PixelGrabber;
import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import javax.imageio.ImageIO;
public class Segmenter {
private BufferedImage image;
private File inputFile;
private File outputFile;
private Pixel[][] rgbMatrix;
private List<Region> regionList = new ArrayList<Region>();
/**
* readImage(): Reads image file.
*/
public void readImage(String path) {
try {
inputFile = new File(path);
image = ImageIO.read(inputFile);
System.out.println("Input image path: "+path);
String reg = "[.*]";
String replacingtext = "";
Pattern pattern = Pattern.compile(reg);
Matcher matcher = pattern.matcher(path);
StringBuffer buffer = new StringBuffer();
while(matcher.find()) {
matcher.appendReplacement(buffer, replacingtext);
}
int indexOf = path.indexOf(".");
String imageType = path.substring(indexOf);
System.out.println("Input image type: "+imageType);
String outputFilePath = buffer.toString()+"_segmented"+imageType;
outputFile = new File(outputFilePath);
System.out.println("Output image path: "+outputFilePath);
}
catch (IOException e) {
System.err.println("IO Exception : "+e);
}
}
/**
* populatePixelMatrix(): Populates 2-D array of type Pixel.
*/
public void populatePixelMatrix(){
rgbMatrix = new Pixel[image.getHeight()][image.getWidth()];
PixelGrabber pg = new PixelGrabber(image, 0, 0, -1, -1, false);
try {
pg.grabPixels();
} catch (InterruptedException e) {
System.err.println("Interrupted Exception : "+e);
}
int[] pixels = (int[]) pg.getPixels();
for(int i=0; i<image.getHeight(); i++) {
for(int j=0; j<image.getWidth(); j++) {
rgbMatrix[i][j] = new Pixel();
rgbMatrix[i][j].setX(i);
rgbMatrix[i][j].setY(j);
rgbMatrix[i][j].setRgb(pixels[i*image.getWidth()+j]);
rgbMatrix[i][j].setTagged(false);
}
}
}
/**
* segment(): Implements region growing algorithm.
*/
public void segment() {
Region region = null;
while(selectSeedPixel() != null) {
region = new Region();
region.setRgb(selectSeedPixel().getRgb());
regionList.add(region);
startGrowing(selectSeedPixel(), region);
}
changeRGB();
}
/**
* selectSeedPixel(): Selects seed pixel.
*/
public Pixel selectSeedPixel() {
for(Pixel[] rgbRow: rgbMatrix) {
for(Pixel pixel: rgbRow) {
if(!pixel.isTagged()) {
return pixel;
}
}
}
return null;
}
/**
* startGrowing(): Region is grown using this method.
* Reference: http://stackoverflow.com/questions/5851266/region-growing-algorithm
*/
public void startGrowing(Pixel seedPixel, Region region) {
Queue<Pixel> pixelQueue = new LinkedList<Pixel>();
pixelQueue.offer(seedPixel);
seedPixel.setTagged(true);
region.getPixelList().add(seedPixel);
while(!pixelQueue.isEmpty()) {
Pixel pixel = pixelQueue.poll();
for(Pixel neighborPixel: getNeighborList(pixel)) {
if(!neighborPixel.isTagged() && getColourDistance(pixel.getRgb(), neighborPixel.getRgb())<10) {
pixelQueue.offer(neighborPixel);
neighborPixel.setTagged(true);
region.getPixelList().add(neighborPixel);
}
}
}
}
/**
* getNeighborList(): Gives list of 4-neighbors.
*/
public List<Pixel> getNeighborList(Pixel pixel) {
List<Pixel> neighborPixelList = new ArrayList<Pixel>();
int x = pixel.getX();
int y = pixel.getY();
//Get left neighbor
if(y != 0)
neighborPixelList.add(rgbMatrix[x][y-1]);
//Get up neighbor
if(x != 0)
neighborPixelList.add(rgbMatrix[x-1][y]);
//Get right neighbor
if(y != image.getWidth()-1)
neighborPixelList.add(rgbMatrix[x][y+1]);
//Get down neighbor
if(x != image.getHeight()-1)
neighborPixelList.add(rgbMatrix[x+1][y]);
return neighborPixelList;
}
/**
* getColourDistance(): Gives Euclidian distance between 2 rgb values.
*/
public int getColourDistance(int rgb1, int rgb2) {
Color color1 = new Color(rgb1);
Color color2 = new Color(rgb2);
int r = color1.getRed() - color2.getRed();
int g = color1.getGreen() - color2.getGreen();
int b = color1.getBlue() - color2.getBlue();
return (int)Math.sqrt(r*r + g*g + b*b);
}
/**
* changeRGB(): Saves the modified colors based on region.
*/
public void changeRGB() {
for(Region region: regionList) {
for(Pixel pixel: region.getPixelList()) {
rgbMatrix[pixel.getX()][pixel.getY()].setRgb(region.getRgb());
}
}
}
/**
* writeImage(): Writes image file.
*/
public void writeImage() {
int[] pixels = new int[image.getWidth() * image.getHeight()];
for(int i=0; i<image.getHeight(); i++) {
for(int j=0; j<image.getWidth(); j++) {
pixels[i*image.getWidth()+j] = rgbMatrix[i][j].getRgb();
}
}
BufferedImage changedImg = new BufferedImage(image.getWidth(), image.getHeight(), BufferedImage.TYPE_INT_ARGB);
changedImg.setRGB(0, 0, image.getWidth(), image.getHeight(), pixels, 0, image.getWidth());
try {
ImageIO.write(changedImg, "png", outputFile);
} catch (IOException e) {
System.err.println("IO Exception : "+e);
}
}
}
Finally we will test it in main method.
Main.java
package com.imgseg;
public class Main {
public static void main(String[] args) {
Segmenter segmenter = new Segmenter();
segmenter.readImage("C:\\images.jpg");
segmenter.populatePixelMatrix();
segmenter.segment();
segmenter.writeImage();
}
}
Input image
Segmented output image
