Thursday, January 19, 2012

Demosaicing: Normal, edge aware and edge weighted!

Bayer pattern is a common term you will come across while working with a digital camera. Wikipedia does a great job at explaining the Bayer pattern: wiki

Bayer Pattern:
The most straightforward explanation is you have a CCD with three types of photo sensors(red, green and blue). Green are sensitive to luminance and red and blue are sensitive to chrominance(color). Apparently, human eyes are more sensitive to luminance so in a typical CCD you will have twice as many green sensors as the red and blue ones. These photo sensors are arranged in a specific pattern(RGBG, GRBG, RGGB). The raw output(also referred to bayer pattern image) will record only one of the three colors at each photo sensor. Each photo sensor has a corresponding pixel in the image. From the bayer pattern we only have the raw value at each pixel but we want to know the true color(r,g,b). This process of computing the color at each pixel is called demosaicing(or debayering?). A typical arrangement of photo sensors is shown in the image below ( linked from Wikipedia ).

There are number of methods out there that do demosaicing and a survey of all the techniques is out of scope of this post. I myself implemented three techniques which are intuitive, computationally less expensive and work reasonably well.

This is the first thought that will come to anybody's mind:
For each pixel do bilinear interpolation. So depending on where you are in the pattern the bilinear interpolation will vary. For example in the above image if you are on the green with two reds on top and bottom, you will just take the average of the red value. But, if you are on the blue you will take average of all four neighboring reds etc. This approach works reasonably well but artifacts (aliasing, zippering, purple fringing etc.) show up on the edges. These are quite noticable.

Edge Aware:
Since most of the artifacts are on/near the edges, instead of blindly doing bilinear interpolation you do edge aware interpolation. For example below if you are trying to find the green value at position B, you will only take the average of the green values with smaller gradient. i.e. first you compute the difference of horizontal green values and vertical green values and pick the option with lower difference and take the average of those two green values. This change makes the demosaicing much better.


Edge Aware Weighted:
Taking it a step further instead of blindly discarding the two green values with higher gradient we take a weigh the horizontal and vertical ones according to the gradient values. Lets define the following:

HDiff = LeftGreen - RightGreen
HSum = LeftGreen + RightGreen
VDiff = TopGreen - BottomGreen
VSum = TopGreen + BottomGreen

Final = 0.5 * (VSum * HDiff + HSum*VDiff ) /  (HDiff + VDiff)

I will leave it to your intuition why 0.5 is needed :-) This small extension is less prone to noise and also keeps strong edges intact.

This drastically improves results. There might be even more fancier ways but for now I fixed my issue so I will research further in future! For comparison purposes I am including the sample images after using the normal(left) and edge aware weighted(right) . Observe across the edges on the chair, board and any other place. You can judge the difference yourself..

Monday, January 16, 2012

Ubuntu 11.10 check battery status hang

I was facing this issue and had no clue how to resolve it. After playing around with grub and various lightdm settings and reading bunch of forums related to the problem I could not resolve it.

I thought it was a longshot but just tried to reinstall the nvidia-drivers and Voilla!! So, for people who faced similar issue, make sure you have the Nvidia driver in one of the folders and boot into text mode(check ubuntu forums on how to modify grub to boot into text mode ) and then reinstall the drivers.
Hope this solves your problem :-)

Saturday, January 14, 2012

Problem with on 64-bit Ubuntu

I have an Nvidia card and as expected I installed Nvidia drivers for my ubuntu. But, whenever I compiled programs that used OpenGL ( ) I ran into compile errors similar to:

No rule to make target `/usr/lib/x86_64-linux-gnu/'

I was sure there was some problem with my file so I ended up looking at it properties and found out that it was a broken link pointing to 'mesa/' which in turn was pointing to '' which never existed.

bpaluri3@bpaluri3:~/libfreenect/build$ ls -l /usr/lib/x86_64-linux-gnu/ 
lrwxrwxrwx 1 root root 13 2011-08-10 04:20 /usr/lib/x86_64-linux-gnu/ -> mesa/

bpaluri3@bpaluri3:~/libfreenect/build$ ls -l /usr/lib/x86_64-linux-gnu/mesa/ 
lrwxrwxrwx 1 root root 10 2011-08-10 04:20 /usr/lib/x86_64-linux-gnu/mesa/ ->

Then I verified the in my /usr/lib directory and found out that it pointed to which is the file provided by the nvidia driver.

bpaluri3@bpaluri3:~/libfreenect/build$ ls -l /usr/lib/ 
lrwxrwxrwx 1 root root 15 2012-01-09 13:53 /usr/lib/ ->

I just overwrote the symbolic link in `/usr/lib/x86_64-linux-gnu/' with the nvidia openGL library i.e. `/usr/lib/' ( I had to delete the old symbolic link before I do this ).

bpaluri3@bpaluri3:~/libfreenect/build$ sudo rm /usr/lib/x86_64-linux-gnu/ 
bpaluri3@bpaluri3:~/libfreenect/build$ sudo ln -s /usr/lib/ /usr/lib/x86_64-linux-gnu/ 

The final two statements are the fixes for the libGL error and I hope anyone who runs into a similar issue will find this information useful.

Wednesday, January 11, 2012

C++: Accessing members of Templated base classes

I spent a considerable time debugging the following error after compiling the c++ code I am writing:

there are no arguments to <function> that depend on a template parameter, so a declaration of <function> must be available

To make the matters simple and to explain what is happening, lets use the following example. I have a base class which is templated, and a derived class that invokes a function from the base class but the function is not "dependent" ( dependent here means the function depends on the type of the template paramter ). In this case foo is not dependent on the template parameter T. The derived class has a function that invokes foo, this call is also not dependent on the template parameter ( there are no arguments that depend on T ).

template class base{
        void foo(int i) {
                // do something with i 

template class derived:public base{
        int bar() {

Again, the call to foo() is not dependent on template arguments (there are no arguments that depend on the type T). This will work only if a global declaration of foo is available, since the one in the base class is not visible until instantiation time, you will get the following compiler error message:

: In member function ‘int derived::bar()’:
error: there are no arguments to ‘foo’ that depend on a template parameter, so a declaration of ‘foo’ must be available
error: (if you use ‘-fpermissive’, G++ will accept your code, but allowing the use of an undeclared name is deprecated)

To solve the problem we have to either use this->foo() or base::foo(). 
You can also compile with -fpermissive flag which allows the compiler to relax the diagnostics for nonconformant code errors to warnings. Its not a good idea though ( for various reasons that I understand but dont have time to explain for now! :-)

In conclusion, Name lookup is a bit tricky because of the two stage approach by the GCC compiler ( apparently since version 3.4 ). The distinction between lookup of dependent and non-dependent names is called two-stage (or dependent) name lookup. Hope this helps someone who get simliar errors.

Friday, January 6, 2012

Windows XP, 7 install cds hangup

I ran into a problem of corrupted partition table when I deleted one of the logical drives on my laptop. I tried to install windows XP and Windows 7 but both cds just froze in the initial setup itself. Having had no clue I tried searching around and found a solution hidden in midst of lot of information. Here is a thing you could do although this will screw up the partition table and in my case I was okay reinstalling stuff without worrying about the data. If that is not the case with you have to find a better way.

I had linux partitions and I just inserted the Linux live cd and formatted the MBR with the following command and voila! 
dd if=/dev/zero of=/dev/sda bs=512 count=1 

Tuesday, January 3, 2012

Clustering - Silhouette, K-means & K-medoids

One of my friend sent out an email asking for suggestion on an algorithm to cluster data given a similarity matrix. And that led to a discussion and another friend forwarded a link to k-medoids algorithm and suggested using it instead of k-means because its more robust to noise etc. But I was still wondering how to find the right k and even if I find the right k is k-medoids better than k-means. I was going to leave it to my friend to figure it out but was too impatient to wait that long.

So, I decided to investigate more and kept reading the wikipedia pages and research papers pertitnent to the topic. Instead of just reading this time I wanted to challenge myself. So, I kept a But, instead of just reading it I wanted to challenge myself. So, I set a 5 hour deadline, to understand, formalize, implement, test, create a video, upload and finally write this blog post on it. I started a timer and boy I was in for a surprise... It took me 6 hours to get everything done :(

There are three advantages I found in doing this.
1) I learnt about the two methods and related work in a quick time, good enough to implement them and know their limitations.
2) A timer countdown helps you focus and ignore everything else instead of just saying I will do this today!
3) Most important, I wanted to see how fast I could transition from basic knowledge to the point of having a running code and beautiful outputs with a good report and finally a blog entry that will stay forever(or till blogspot's existence)

I started on a whiteboard with todo list(image below) and time estimates and within 4 hours got the code working after which I had to spend time on making the video, writing the report, uploading, creating the blog entry etc..

The youtube video of the final output

Report: pdf
Matlab code: code