The Most Simple Introduction to Artificial Neural Networks

Taken from http://en.wikipedia.org/wiki/Artificial_neural_network

I would like to share you a good stuff on learning the basic of Artificial Neural Networks.

Artificial Neural Networks (ANNs), often refer to as Neural Networks, is one of the most well-known tool in Machine Learning. There are many websites available which provide basic theory of Neural Networks so I will not cover them here.

The hard part about ANNs is the Mathematics involed, how to implement them, and apply them to good use. There are many articles in CodeProject.com that try to present the ANNs in a simple, reusable ways. But, in my personal opinion, they are all hard to understand and reuse. I had read some of these articles once and I found that most of the content are too advanced. I just need to know a very basic part of ANNs and put them into good use, in short time.

I also have to admit that, sometimes, Object-oriented and Reusability are what make the code more harder to understand than it should be. I just need a "top-to-bottom" code in single method that explains what is going on. Distributing the data and logic in OO style is just not suitable for the purpose of learning algorithm.

Then, I came across this page: Implementing a Neural Network in C. This page explains very briefly everything you need to know and implementing an ANNs. And, most of all, the code is in non-object-oriented C language! That makes it is easy to learn and understand. I then followed the article with Java and everything was fine. I could adapt it to my homework problem at the university and got quite good result.

Finally, I really recommend this page to everyone who need to get started with ANNs, quick :)

Simple Tic-Tac-Toe AI in JavaScript

Click here to see the Tic-Tac-Toe game in action! (open in new window)

Last year, I was challenged by the thread at Thaiadmin to implement a two-player OX (or Tic-Tac-Toe, XO, what you may call) game. I had done this kind of program in VB6 before, so I decided to implement the one-player JavaScript version.

The hardest part of of this project is debugging the JavaScript. I had to write the value of each variable and things done in each step to the screen (as you see in the bottom of the figure above) to diagnose the problems. I was so embarrassed that I did not know any of the great web developer's tools such as FireBug.

The ideas behind the decisions making part (or the AI) are to search every possible moves and take the best one. In each move, We assumed that the opponent chose his best move and we chose our best move. This method is "Minimax" method. As described in Wikipedia:

Minimax (sometimes minmax) is a method in decision theory for minimizing the maximum possible loss. Alternatively, it can be thought of as maximizing the minimum gain (maximin). It started from two player zero-sum game theory, covering both the cases where players take alternate moves and those where they make simultaneous moves. It has also been extended to more complex games and to general decision making in the presence of uncertainty.

The Minimax method can be applied to many other board games too. But in some complex games such as Chess, there was so many game states that you cannot search into them entirely (it would take many many years on an ordinary computer). So some heuristic must be used to approximately determine value of each state and the search must be limited at a fixed level (deeper level of search makes the AI cleverer).

In my case, there was not too many game states so I can search on them entirely. You can test my game here - http://m3rlinez.googlepages.com/oxai.htm. Choose View->Source to view the JavaScript source code.

Fast nth Fibonacci number calculation

I am now preparing myself for Dynamic Programming quiz this Wednesday. One classic example of DP is the calculation of nth Fibonacci.

The straight-forward way is to convert the recurrence relation, Fn = Fn-1 + Fn-2, F0=0, F1=1, to a recursive function. However, the problem overlapping makes this solution poor in performance. A betterway is to calculate value of Fk from 2 to n in a bottom-up style. The asymptotic running time of this DP method is O(n).

   private static int FibN(int n)
   {
       if (n <= 1)
           return n;

       int a = 0, b = 1, c = 1;
       for(int i = 2 ; i <= n ; i++)
       {
           c = a + b;
           a = b;
           b = c;
       }

       return c;
   }

My instructor, Aj.Somchai, wrote in one of his book, "การออกแบบและวิเคราะห์อัลกอริทึม (Design & Analysis of Algorithms)", the challenge of finding a method that calculate Fn in less than O(n) time. After thinking for a while, I fired up my browser and search :)

This page described a method of calculating Fn in O(log n) time using a property of special case of matrix multiplication. The following is my implementation of this O(log n) method and O(n) method in C#.

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

namespace FastFibo
{
   class Program
   {
       private static int[] G = new int[] { 1, 1, 1, 0 };

       /// <summary>
       /// Get [[1,1][1,0]]^n matrix.
       /// </summary>
       /// <param name="n">n</param>
       /// <returns>[[1,1][1,0]]^n</returns>
       private static int[] GetFiboMatrix(int n)
       {
           if (n == 1)
               return G;
           int[] c = GetFiboMatrix(n / 2);
           c = MatrixMul(c,c);
           if (n % 2 == 1)
               c = MatrixMul(c, G);
           return c;
       }

       private static int[] MatrixMul(int[] a, int[] b)
       {
           if (a.Length != 4 || b.Length != 4)
               throw new Exception("Invalid matrix size");

           int[] res = new int[4];
           res[0] = a[0] * b[0] + a[1] * b[2];
           res[1] = a[0] * b[1] + a[1] * b[3];
           res[2] = a[2] * b[0] + a[3] * b[2];
           res[3] = a[2] * b[1] + a[3] * b[3];
           return res;
       }

       private static int FibLogN(int n)
       {
           if (n <= 1)
               return n;

           return GetFiboMatrix(n)[1];
       }

       private static int FibN(int n)
       {
           if (n <= 1)
               return n;

           int a = 0, b = 1, c = 1;
           for(int i = 2 ; i <= n ; i++)
           {
               c = a + b;
               a = b;
               b = c;
           }

           return c;
       }


       static void Main(string[] args)
       {
           for (int i = 1; i <= 46; i++)
               Console.WriteLine("{0,4} FibN = {1,10} FibLogN = {2,10}",
                   i, FibN(i), FibLogN(i));
       }
   }
}

The normal 4-byte integer can only contain values in range [-2^31,2^31-1] and we can only get actual nth Fibonacci number up to n = 46. The difference of running time between O(n) and O(log n) for n under 47 can hardly be noticed.

This, however, can be apply to some Computer Olympiad problems such as "Find the last digit of nth Fibonacci number" :) You can also make this faster by convert it to non-recursion version.

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.