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.

Polymorphism example in Java, C# and C++

It has been a while since I coded my first C program. Now, because many of my friends at the department began to interest themselves in C++ programming. So I think I should learn some of the basics of it too :P

C++ is a powerful programming language with tons of language features and hard-to-understand syntaxes. However, I am only interested in its object oriented features such as Class, Inheritance, Composition, Polymorphism, blah blah. Thanks to my background knowledge in OO, it did not take me long to understand all these.

I tried to create a very simple Polymorphism example in C++ using the famous open-source IDE, Dev-C++. Unfortunately, I experienced some problems about building C++ project with multiple files. The IDE kept telling me that there is multiple definition of functions in my code. So, I went googling and found this page, Organizing Code Files in C and C++. It provided me the basic understandings of compiling and linking process.

After finished coding the C++ example, I thought I should create the Java and C# version to compare with it too. I noticed that C# is more like C++ in that the functions (or methods) to be overriden must declared to be virtual while there is no such modifier in Java.


Here are my output and codes.



C++
main.cpp

#include 
#include "shape.h"
#include "circle.h"

using namespace std;

int main(int argc, char *argv[])
{
Shape *shape = new Shape();
shape->calculateArea();
shape->test();

Shape *circle = new Circle(10);
circle->calculateArea();
circle->test();

system("PAUSE");
return EXIT_SUCCESS;
} 

shape.h

#ifndef _SHAPE_CLASS
#define _SHAPE_CLASS

class Shape{
public:
virtual void showName();
virtual double calculateArea();
void test(){
     showName();
}
};

#endif

shape.cpp

#include "shape.h"
#include 

using namespace std;

void Shape::showName(){
cout << "Shape: I am a shape!" << endl;
}

double Shape::calculateArea(){
cout << "Shape: Dunno how to calc my area ..." << endl;
return 0.0;
} 

circle.h

#ifndef _CIRCLE_CLASS
#define _CIRCLE_CLASS

#include "shape.h"

class Circle : public Shape{
public:
Circle(double radius) : radius_(radius){}
virtual void showName();
virtual double calculateArea();
protected:
   double radius_;

};

#endif

circle.cpp

#include "circle.h"
#include 
#include 

using namespace std;

void Circle::showName(){
cout << "Circle: I am a circle!" << endl;
}

double Circle::calculateArea(){
cout << "Circle : My area = " << M_PI*radius_*radius_ << endl;
return M_PI*radius_*radius_;
}

C#
Program.cs

using System;
using System.Collections.Generic;
using System.Text;

namespace CSharpPolymorphism
{
class Program
{
   static void Main(string[] args)
   {
       Shape shape = new Shape();
       shape.showName();
       shape.calculateArea();

       Circle circle = new Circle(10.0);
       circle.showName();
       circle.calculateArea();
  
       Console.Read();
   }
}
}

Shape.cs

using System;
using System.Collections.Generic;
using System.Text;

namespace CSharpPolymorphism
{
class Shape
{
   public virtual void showName()
   {
       Console.WriteLine("Shape: I am a shape!");
   }

   public virtual double calculateArea()
   {
       Console.WriteLine("Shape: Dunno how to calc my area ...");
       return 0.0;
   }
}
}

Circle.cs

using System;
using System.Collections.Generic;
using System.Text;

namespace CSharpPolymorphism
{
class Circle : Shape
{
   protected double radius;

   public Circle(double radius)
   {
       this.radius = radius;
   }
   public override void showName()
   {
       Console.WriteLine("Circle: I am a circle!");
   }

   public override double calculateArea()
   {
       Console.WriteLine("Circle : My area = " +
           Math.PI * radius * radius);
       return Math.PI * radius * radius;
   }
}
}

Java
Main.java

public class Main {

   /**
     * @param args the command line arguments
     */
   public static void main(String[] args) {
       Shape shape = new Shape();
       shape.showName();
       shape.calculateArea();
      
       Circle circle = new Circle(10.0);
       circle.showName();
       circle.calculateArea();
      
   }
  
}

Shape.java

public class Shape {
  
   /** Creates a new instance of Shape */
   public Shape() {
   }
  
   public void showName(){
       System.out.println("Shape: I am a shape!");
   }
  
   public double calculateArea(){
       System.out.println("Shape: Dunno how to calc my area ...");
       return 0.0;
   }
}

Circle.java

public class Circle extends Shape{
  
   protected double radius;
   /** Creates a new instance of Circle */
   public Circle(double radius) {
       this.radius = radius;
   }

   public void showName() {
       System.out.println("Circle: I am a circle!");
   }

   public double calculateArea() {
       System.out.println("Circle : My area = " + Math.PI*radius*radius);
       return Math.PI*radius*radius;
   }
  
}

Taking advantage of duo core processor

I have heard for a while that running a multi-thread program on multi core processor is a lot faster than running it on single core one. So, I decided to conduct a mini-experiment to test whether this is true.

C# Console Application, .NET Framework 2.0

Program.cs

using System;
using System.Collections.Generic;
using System.Text;
using System.Threading;

namespace PerformanceTester
{
class Program
{
    private const int NUM = 5000000;

    static void Main(string[] args)
    {
        for (int i = 0; i < 3; i++)
        {
            DateTime start;
            TimeSpan span;

            start = DateTime.Now;
            SingleThreaded();
            span = DateTime.Now.Subtract(start);
            Console.WriteLine(
                String.Format("\tSingle Threaded : {0} ms",
                span.TotalMilliseconds));

            start = DateTime.Now;
            DoubleThreaded();
            span = DateTime.Now.Subtract(start);
            Console.WriteLine(
                String.Format("\tDouble Threaded : {0} ms",
                span.TotalMilliseconds));

        }
        Console.Read();
    
    }

    private static void SingleThreaded()
    {
        PrimeGenerator generator = new PrimeGenerator();
        List<int> results = new List<int>();
        generator.AddPrimes(results, 1, NUM);
    }

    private static void DoubleThreaded()
    {
        List<int> results = new List<int>();

        Thread t1 = new Thread(delegate()
        {
            PrimeGenerator generator =
                new PrimeGenerator();
            generator.AddPrimes(results,1,NUM/2);
        });

        Thread t2 = new Thread(delegate()
        {
            PrimeGenerator generator =
                new PrimeGenerator();
            generator.AddPrimes(results,NUM/2+1,NUM);
        });

        t1.Start(); t2.Start();
        t1.Join(); t2.Join();
    }
}
}

PrimeGenerator.cs

using System;
using System.Collections.Generic;
using System.Text;
using System.Threading;

namespace PerformanceTester
{
  class PrimeGenerator
  {
      private bool IsPrime(int n)
      {
          if (n <= 1)
              return false;
          else if (n <= 3)
              return true;
          else if (n % 2 == 0)
              return false;
          else
          {
              int bound = Convert.ToInt32(Math.Ceiling(Math.Sqrt(n)));
              for (int i = 3; i <= bound; i++)
              {
                  if (n % i == 0)
                      return false;
              }
              return true;
          }
      }

      public void AddPrimes(List<int> list,int lowerBound,int upperBound)
      {
          for (int number = lowerBound; number < upperBound; number++)
          {
              if(IsPrime(number))
                  lock (list)
                  {
                      list.Add(number);
                  }
          }
      }
  }
}

This program will search for all primes between 1 and 5000000 inclusive. It works in two mode, single threaded and double threaded. The search range is divided into two parts in double threaded mode, 1 - 2500000 and 2500001 - 5000000 (we can obviously see that the work load of the second range is bigger than the first one but since this is informal experiment so I did not care about this point :P). The program also record running times for each mode and print them on the screen.

Here are the results:

Running on my IBM R52 - Intel(R) Pentium(R) M 1.60 GHz
(Single core)

Single Threaded : 11687.5 ms
Double Threaded : 12875 ms
Single Threaded : 12812.5 ms
Double Threaded : 12953.125 ms
Single Threaded : 12000 ms
Double Threaded : 11703.125 ms

Running on my mom's IBM R60 - Intel(R) Core(TM)2 CPU 15500 @ 1.66GHz
(Double core)

Single Threaded : 9171.875 ms
Double Threaded : 5625 ms
Single Threaded : 9109.375 ms
Double Threaded : 5625 ms
Single Threaded : 9109.375 ms
Double Threaded : 5609.375 ms

For single core, the running time is practically the same for each mode. While for double core, double threaded mode gives noticeably better running time.

So, to take advantage of new duo core processors nowadays, considers building your program to support multi threaded mode.