Wednesday, May 2, 2007

Really simple blob detector

Few days ago while i was reading news at Blognone, I spotted an interesting topic on how to detect
(and calculate the area of ..) circles in an image. This is a well-known problem in the field of Computer Vision known as Blob Detection. I had some experiences in implementing the blob detector in C and C# but had never done it in Java. So I decided to write one. The code was more compact and straight to the point than my C and C# version.

This is the input image.



And here is my code.




package blobdetector;

import java.awt.Point;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
import javax.imageio.ImageIO;
import javax.management.Query;

/**
*
* @author m3rlinezatgmaildotcom
*/
public class Main {

public Main() {
}

public static boolean isBlack(BufferedImage image,int posX,int posY){
// หาสีที่สุดที่สนใจ
int color = image.getRGB(posX,posY);

// หาค่าความสว่างจากการเฉลี่ย RGB
int brightness =
(color & 0xFF) +
((color >> 2) & 0xFF) +
((color >> 4) & 0xFF);
brightness /= 3;
return brightness < 128;
}

public static void main(String[] args) {
if(args.length != 1){
System.err.println("ERROR: Pass filename as argument.");
return;
}

String filename = args[0];
// String filename = "C:\\Users\\Natthawut\\Desktop\\Polymorphism\\blob.jpg";
try {
BufferedImage bimg = ImageIO.read(new File(filename));

// map สำหรับเก็บว่าจุดใดบ้างที่ได้รับการสำรวจไปแล้ว
boolean[][] painted =
new boolean[bimg.getHeight()][bimg.getWidth()];

// วนรอบทุกจุดในรูป
for(int i = 0 ; i < bimg.getHeight() ; i++){
for(int j = 0 ; j < bimg.getWidth() ; j++) {
// System.out.println(i + " " + j + " b " + isBlack(bimg,j,i));
// ถ้าจุดนั้นเป็นสีดำ และยังไม่เคยถูกสำรวจ
if(isBlack(bimg,j,i) && !painted[i][j]){

// ทำการ floodfill
Queue<Point> queue = new LinkedList<Point>();
queue.add(new Point(j,i));

int pixelCount = 0;
while(!queue.isEmpty()){
Point p = queue.remove();

// เช็คว่าจุดที่ดึงมาอยู่ในขอบเขต
if((p.x >= 0) && (p.x < bimg.getWidth() && (p.y >= 0) && (p.y < bimg.getHeight()))){
if(!painted[p.y][p.x] && isBlack(bimg,p.x,p.y)){
painted[p.y][p.x] = true;
pixelCount++;

// ใส่จุดรอบๆจุดที่ดึงออกมาลงไปในคิว
queue.add(new Point(p.x + 1,p.y)); queue.add(new Point(p.x - 1,p.y));
queue.add(new Point(p.x,p.y + 1)); queue.add(new Point(p.x,p.y - 1));
}
}
}
System.out.println("Blob detected : " + pixelCount + " pixels");
}

}
}

} catch (IOException ex) {
ex.printStackTrace();
}

}

}




And here is the output.

Blob detected : 1 pixels
Blob detected : 1339 pixels
Blob detected : 1 pixels
Blob detected : 5582 pixels
Blob detected : 1 pixels
Blob detected : 1 pixels
Blob detected : 1 pixels
Blob detected : 1 pixels
Blob detected : 1 pixels
Blob detected : 1 pixels
Blob detected : 1 pixels
Blob detected : 1 pixels
Blob detected : 1 pixels
Blob detected : 1 pixels
Blob detected : 1 pixels
Blob detected : 4018 pixels
Blob detected : 1 pixels
Blob detected : 1 pixels
Blob detected : 1 pixels
Blob detected : 1 pixels
Blob detected : 1 pixels
Blob detected : 1 pixels
Blob detected : 1 pixels
Blob detected : 1 pixels
Blob detected : 1 pixels
Blob detected : 1 pixels
Blob detected : 1 pixels
Blob detected : 1 pixels
Blob detected : 1 pixels
Blob detected : 1 pixels
Blob detected : 1 pixels


Edit: P'Deans4J suggested me to write the same program using recursion too. Here is my code in recursive version. I added another static method "floodfill" which returns number of pixels in current blob.




package blobdetector;

import java.awt.Point;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
import javax.imageio.ImageIO;
import javax.management.Query;

/**
*
* @author m3rlinezatgmaildotcom
*/
public class Main {

public Main() {
}

public static boolean isBlack(BufferedImage image,int posX,int posY){
// หาสีที่สุดที่สนใจ
int color = image.getRGB(posX,posY);

// หาค่าความสว่างจากการเฉลี่ย RGB
int brightness =
(color & 0xFF) +
((color >> 2) & 0xFF) +
((color >> 4) & 0xFF);
brightness /= 3;
return brightness < 128;
}

public static int floodfill(
BufferedImage image,
boolean[][] painted,
int posX, int posY){

// ตรวจสอบขอบเขต
if((posX < 0) || (posX >= image.getWidth()) || (posY < 0) || (posY >= image.getHeight()))
return 0;

if(!painted[posY][posX] && isBlack(image,posX,posY)){
painted[posY][posX] = true;
return 1 + floodfill(image,painted,posX+1,posY) +
floodfill(image,painted,posX-1,posY) +
floodfill(image,painted,posX,posY+1) +
floodfill(image,painted,posX,posY-1);
}

return 0;
}

public static void main(String[] args) {
if(args.length != 1){
System.err.println("ERROR: Pass filename as argument.");
return;
}

String filename = args[0];

try {
BufferedImage bimg = ImageIO.read(new File(filename));

// map สำหรับเก็บว่าจุดใดบ้างที่ได้รับการสำรวจไปแล้ว
boolean[][] painted =
new boolean[bimg.getHeight()][bimg.getWidth()];


// วนรอบทุกจุดในรูป
for(int i = 0 ; i < bimg.getHeight() ; i++){
for(int j = 0 ; j < bimg.getWidth() ; j++) {

// ถ้าจุดนั้นเป็นสีดำ และยังไม่เคยถูกสำรวจ
if(isBlack(bimg,j,i) && !painted[i][j]){

int pixelCount = floodfill(bimg,painted,j,i);

System.out.println("Blob detected : " + pixelCount + " pixels");
}

}
}

} catch (IOException ex) {
ex.printStackTrace();
}

}

}


While the recursive version uses less LOC, easier to understand and easier to code than the first solution, its performance is not as good as the first one and it actually gives me java.lang.StackOverflowError when used with the sample image. But if the problem's size is small, I prefer implementing the recursive version too.

10 comments:

rchatsiri said...

wow! image processing:)

nekrataal said...

โอ๊ะ น่าสน

ว่าแต่ตรงบรรทัด IF ที่เช็คว่าอยู่ในขอบนั่นมันทำอะไรอ่า งง? p.x < color(0,102,0) ??

อืมถ้า assume ขนาดอย่างต่ำของ Blob ก็น่าจะทำให้ลดปริมาณการวนลูปไปได้เยอะเลยนะ อย่างเช่นถ้า Blob มันต้องมีขนาดอย่างน้อย 4-pixel (2x2 px) ก็วนลูปกระโดดทีละ 2-pixel ลดเวลาได้ตั้งครึ่ง

ไม่ได้เขียนอะไรแนวนี้นานละ หุหุ ลองมั่งดีก่า

Unknown said...

Hi nekrataal.
There was a HTML formatting error. I had fixed them. Please check the source code again. And thanks for the great technique :)

Anonymous said...

this looks nice and interesting...

I didn't look at the code seriously. but reading the way you implemented, it seems like you can implement the same algorithm in a recursive way.

I challenge you to do it. maybe It will take less LOC.

Anonymous said...

I think recursive way can be slower than iterative way

Unknown said...

Hi P'Dean,
I have added the recursive version into my entry. Thanks for suggestion.

Anonymous said...

in the recursive version u should store the calculated points in a collection, say HashMap, so you wouldn't have to recalculate them again.

good job anyway : )

Anonymous said...

nice nice, but how do you actually find the blob location within the image - that's the challence!

Unknown said...

Hi Mobi! Thanks for the comment :)

I can think of one method that can approximately determine the locations of the blobs by finding the centroids of the bounding boxes of them.

Anonymous said...

Can u plz explain the steps of this blob detection algorithm in English.
Plzzzz :)