Yeah, this time I will introduce about character segmentation in details[Code] from the previous entry.
First of all,you should load this tester image for workshop.

image.jpg (11.77 kb)

OK, this workshop works on Python language with Python Image Library. http://www.pythonware.com/products/pil/index.htm

There are 5 parts in this workshop.
1. Preprocessing -> prepare image before do the main process.
2. Find histograms in both directions -> to be used in step 3.
3. Find pair of concave up and down points -> to find segmentation points.
4. Segmentation.
5. Show Results.

Recall from the previous entry.
In Preprocessing, we need to load the image in grayscale image. Next, clean the image. Then, convert to a binary image.

# load and convert image to a grayscale image.
im = Image.open('image.jpg').convert("L") 
(width, height) = im.size
# use median filter size 11x11 to clean image
mim = im.filter(ImageFilter.MedianFilter(11))
# extract foreground from background by using threshold value.
# using threshold = 8, then use median filter to clean image again.
cim = mim.point(lambda i: i*8,"F").convert("1").filter(ImageFilter.MedianFilter(11))

We will get the result like this. [Use cim.show() to show an image]

Next, we have to find histograms in horizontal and vertical lines.

#main process part
# load image to 2d
pix = cim.load()

#find histograms in both directions
hhist = []
s = 0
for h in range(height):
    for  w in range(width):
        if(pix[w,h]==0):
            s+=1
    hhist.append(s)
    s = 0
    
vhist = []
s = 0
for w in range(width):
    for  h in range(height):
        if(pix[w,h]==0):
            s+=1
    vhist.append(s)
    s = 0

Then, we have to find cutting point from the image by seeing from histogram value that goes up from 0 to upper and goes down from more than 0 to 0.

#find pair of concave up and down points
hup = []        #keep concave up index [horizontal]
hdown = []      #keep concave down index [horizontal]
s = len(hhist)
for x in range(1,s):
    if(hhist[x-1]>0 and hhist[x]==0):
        hdown.append(x-1)
    if(hhist[x-1]==0 and hhist[x]>0):
        hup.append(x)

vup = []        #keep concave up index [vertical]
vdown = []      #keep concave down index [vertical]
s = len(vhist)
for x in range(1,s):
    if(vhist[x-1]>0 and vhist[x]==0):
        vdown.append(x-1)
    if(vhist[x-1]==0 and vhist[x]>0):
        vup.append(x)

Finally, we will segment an image and then show the result of all characters. We have to create a box for crop an image (left,upper,right,lower) that upper and lower will use values from hup and hdown respectively.

#segmentation
# we know that we have only 1 line so, hup and hdown are not change.
# if we want to show all segmented images, it will change in vup and vdown indexes.

for i in range(len(vup)):
    box = (vup[i],hup[0],vdown[i],hdown[0])
    seg = cim.crop(box)

#show result
    seg.show()

Now, we will know about the concept of image segmentation that is not hard for implement. It may expand your thought to develop a more complicated segmentation ^^.

Today, I will talk about how to segment character from the image by using MATLAB. At this time, I will show about the concept and the result first, next time I will show the code to implement this. In this entry, I will create automate segmentation step by step. 1. Read the grayscale image.

                               

 

2. Clean the image by using median filter: http://en.wikipedia.org/wiki/Median_filter There are a lot of method to reduce noise from the image but in this picture I found that median filter is the best way to reduce the noise from the image.

3. Now, we can extract foreground image from the background.

 

4. We will see that there are noise stay in the image so, we have to clean the image again by using median filter.

 

5. Find the projection in the vertical and horizontal to see the space between each character which we have to use this to separate each character.

 

Horizontal Histogram

 

Vertical Histogram

6. We have to match the boundary of each character by concave down and concave up of the histogram. [In horizontal, we have only 1 pair because we have only 1 line of characters.]

7. Finally, we cut the selected zone from the image to display a character.

 

8. Do these for all characters.

 

So, we will know the basic steps to segment the characters and the next time I will show and explain about the code to implement it. Hope this will guide you an idea.

 

 

Today, the RIA[Rich Internet Application] competition rate is vary high among various company such as Flex from Adobe, JavaFx from Sun Microsystems.

For the Microsoft, there is a tool for create Microsoft Silverlight in Eclipse allow you can create Silverlight UI to connect the webservice.

You can download at the site http://www.eclipse4sl.org/

Let's go, enjoy with it!!!.

Today, I will show well-known sorting algorithm that is called Quick Sort.

Normally, On adverage, it uses Θ(nlogn) when compare to n items that usually better than other Θ(nlogn) algorithm but it's not stable.

Quicksort, like merge sort, is based on the divide and conquer paradigm.

Divide: Patition array into two arrays from A[p..r] into A[p..q-1] and A[q+1..r]

Conquer: Sort the two sub arrays in the recursive quick sort.

Combine: Sub arrays are sorted in place, so, no need to combine them.

 

In this algorothm, there are 4 regions to maintain subarray in the partition zone.

pivot || value < pivot || value > pivot || unrestricted         [From left to right of subarray]

and it use pivot to compare the appropriate place to swap the pivot from the both side left and right.

For example: 3,2,6,5
pivot = 3 [index 0]

From the left : Find the first place that value is greater than pivot
left index = 1
3 > 2 move index by one
3 < 6 stop loop
-> left index = 2

From the right : Find the first plae that value is smaller than pivot
right index = 3
3 < 5 move index by minus one
3 < 6 move index by minus one
3 > 2 stop loop
-> right index = 1

You can see that if we sort in ascending order, we should swap pivot with the position of 1 in the array. Then it get 2,3,6,5.
Next, it go to recursion procedure of quicksort. From index 0-1, 2-3.
and do this again until thay can't be partitioned.

using System;

namespace Sorting
{  
    class Sort
    {
        //swap in place
        private static void Swap<T>(T[] arr, int m, int n)
     {
      T temp = arr[m];
      arr[m] = arr[n];
      arr[n] = temp;
     }

        //normal quick sort
        public static void QuickSort<T>(T[] arr) where T : IComparable
     {
      QuickSort(arr, 0, arr.Length-1);
     }
 
     //recursive quick sort
        public static void QuickSort<T>(T[] arr, int start, int end) where T : IComparable
        {
            //based case
            if (end <= start)
                return;

     //---------------- Partition ---------------------------
            T pivot = arr[start]; //pivot
            int i = start;  //starting index
            int j = end + 1; //ending index

            while (i<j)
            {
                //searching for data that is less than pivot
                while (i < end && arr[++i].CompareTo(pivot) < 0) ;

                //searching for data that is greater than pivot
                while (j > start && arr[--j].CompareTo(pivot) > 0) ;

                //exchange data at i and j only if i < j
                if (i < j)
                    Swap(arr, i, j);
            }
            //restore pivot
            arr[start] = arr[j];
            arr[j] = pivot;
     //-----------------------------------------------------

            QuickSort(arr, start, j - 1);//sort left side
            QuickSort(arr, j + 1, end); //sort right side
        }
        static void Main(string[] args)
        {
            int[] a = {5,1,2,4,6,8,100,56,23,55,75,34,84,76,97,56 };
            QuickSort<int>(a);
            foreach (int x in a)
            {
                Console.WriteLine(x);
            }
            Console.ReadLine();
        }
    }
}