Downloading photos from flickr

I thought this might be helpful for people who want to download flickr images using api and can save them some time:

1. Get an authentication key from flickr: http://www.flickr.com/services/api/misc.api_keys.html
2. Install flickrapi: http://pypi.python.org/pypi/flickrapi 
1. The easiest way to do this is using pip: 
• sudo port install py32-pip(mac only, sudo apt-get install pip for linux?)
• pip-3.2 install flickrapi ( depending on your pip version change the command.
3. Run the attached python script with three command line arguments:
1. Search query to retrieve photos of
2. Number of photos
3. Output directory to save to ( The sub-directory structure is similar to flickr's internal directory structure, You can modify the FlickrPhoto class to modify this behavior).
4. This script uses the tag based search query. The code also has a way to use the search query instead of tag based query(commented out). All special arguments explained in the link for more information: http://www.flickr.com/services/api/flickr.photos.search.html

I copied/modified this code from a friend who in turn copied/modified it from an existing api tutorial. You do not have to cite either of us! :-)

NOTE: THIS CODE WILL NOT WORK UNTIL YOU FILL THE TWO KEYS INSIDE THE CODE. (LINE 47 and 48)

Code: http://dl.dropbox.com/u/14073242/Blog/techtidings/flickr/DownloadTask.py

OSAP - Optimal Seating Arrangement Problem

Recently, I went with bunch of folks from my lab to Ormsby's. We were seated in a pretty big table(rectangular) that could host 16 people, we were 12. Each one of us sat arbitrarily(of course fighting for places with eye catching views(girls!)). We started chatting. I talked for a while with people sitting beside me. Then, I tried to talk to people on the opposite side and other folks. There was so much noise that it was very difficult to have any conversation. After shouting at the top of my voice for a while I got tired and just enjoyed my dinner. For the rest of the time I was thinking of this problem and tried to formalize it in my mind. I tried searching for the problem on Google but could not find anything. So, I named it Optimal Seating Arrangement Problem(OSAP). Below I provide the formal description. Anyone wants to propose an algorithm?

OSAP -  Optimal Seating Arrangement Problem

Problem Statement: Design an algorithm to find an optimal seating arrangement for a group of friends of size n on a round table. Each person in the group has a preference for every other person. The preference values lie between 0 and 1. Also, the sum of the preference values for a person's friends should equal to 1. The optimal arrangement is the arrangement with the highest score where the score of an arrangement is calculated by adding the score of individual person and the score of an individual person is sum of the preference values of his neighbors. A neighbor of a person is someone sitting either to the immediate left or immediate right of the person.

Input: n followed by n X n matrix. Row i contains the preference values of person i for every other person in the group.

Example Inputs:
Input: 3
0 0.1 0.9
0.5 0 0.5
0.6 0.4 0

Output:
1 2 3 or 2 3 1 or 3 2 1or 1 3 2 or 2 1 3 or 3 1 2 ( All of them will have equal score in case of n = 3 )

Input: 4
0 0 0.1 0.9
0 0 0.1 0.9
0.5 0.5 0 0
0.9 0.1 0 0

Output:

3 1 4 2 or any permutation ( 1 4 2 3, 4 2 3 1, 2 3 1 4 )

What is the complexity of the optimal algorithm?

Joint(Cross) Bilateral Filter

I have been meaning to write about this for a while but due to two conference deadlines I did not get time. Anyway it is one of the most interesting things I read and implemented recently which helped immensely in my project. Joint bilateral filter is also referred to as Cross bilateral filter. Both mean the same. Without any further ado let me motivate its necessity and then provide some explanation with results. I will make the matlab, c++ and java code available on my website very soon.

A basic course in image processing will teach you about low pass filtering. In layman's language smoothing. An image is fundamentally composed of two types of frequency components, low and high. Low frequency components signify smooth and constant regions where as high frequency components signify edges and corners. So, a low pass filter passes low frequency components untouched but smoothes the high frequency components. Typically smoothing is a process of convolving a kernel with the image at each pixel location. It is used to reduce noise. The typical kernel is a uniform or a Gaussian kernel. These kernels work very well in general but have issues near edges/boundaries. They induce artifacts because the resulting value after smoothing at the boundary pixel comes from two different regions. The edges are not preserved. Bilateral filter is a technique that can be used to perform edge preserving smoothing. There are variants to this namely anisotropic diffusion. I will not go into details of that in this post. So, in short bilateral filter modifies the kernel based on the local content so that edges are preserved.

Taking it a step further imagine you have two sources and you want to smooth one source based on the similarity of the other source. A typical example is if you have color image and depth image and you want to smooth the color image such that color does not bleed across depth boundaries. That is when you use the joint/cross bilateral filter. Here, the kernel is a combination of weights based on the color similarity and depth similarity. Thus the filter will only smooth values with similar color and depth and keep the rest untouched. This is a simple but elegant solution that has tremendous applications. The application I am interested in and where I used this in my research is to smooth the color image as a preprocessing step to perform over-segmentation.

Below I share three images, the input image, result obtained by smoothing the color image using a Gaussian filter alone and result obtained by using the joint bilateral filter. You can clearly see that the edges are preserved but the rest of the content is smoothed out. Keep in mind that along with the color image I have the corresponding(registered) depth data. Without an additional source of information you can only apply bilateral filter, not cross bilateral filter.

I will discuss about the two papers that are relevant to this in my JiffyPaper blog.

Synchronizing(Syncing) Bookmarks, Passwords and even Open Tabs

I am amazed at the extensions and utilities available for browsers these days :-)

I work on three different machines on a given day: My Desktop, Lab laptop and home laptop. One of the many features I wanted was to be able to synchronize my browsers across these machines. They use different operating systems and I end up using either chrome, firefox and sometimes internet explorer. Firstly, I love Chrome because it syncs to my google account which has many uses but the main one being synchronizing bookmarks and extensions across machines.

Then, I added Lastpass another extension that is a password manager. I dont remember passwords to most of the websites as they are automatically generated using Lastpass! Its an amazing tool that will save you a lot of time.

Finally, I found Xmarks another extension that takes synchronization a step further. It synchronizes open tabs across machines! How cool is that? In the lab I can now open tabs that are open on my laptop at home. Its made the entire process of moving across machines so much easier.

I strongly suggest anyone who is looking to deal with synchronizing your work on the browsers across machines to use the following combination: Chrome browser + Synchronize with Google account + Lastpass + Xmarks

!!!The combination is uncanny!!!

Opencv knnSearch example

After searching through the web and going through the FLANN api I could not find a decent example that showcases the K nearest neighbor search capability. I found that OpenCV also has a wrapper written around flann so checked if there exists a simple example. To my dismay I could not find one. So, I spent couple of hours and put together the following code. Hope someone looking to use flann with opencv will find this example useful!

The example generates data randomly centered around a mean and a variance of arbitrary dimensions(provided by user, default is 1) and generates query data with similar properties and invokes the single query and batch knnSearch function calls and prints out. Just to let you know its not a class, its just a simple example to help people use knnSearch function in openCV. Enjoy!

code: cvKnn.cpp
Command to compile the code: g++ cvKnn.cpp -L /usr/lib -lopencv_core -lopencv_flann -o cvKnn

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 ).

Demoasicing:

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.

Normal:

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.

grgrg

bgBgb

grgrg

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..

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 :-)

Problem with libGL.so 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 ( libGL.so ) I ran into compile errors similar to:

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

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

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

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

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

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

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

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

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.

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{
public:
        void foo(int i) {
                // do something with i 
        }
};


template class derived:public base{
        int bar() {
                foo();
        }
};

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.

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 

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

gitk on MAC

I had trouble getting gitk to work on my mac. It did not do anything and did not throw an error as well. After reading through some forums I found that the PATH variable is the culprit. In my .profile ( or in .bashrc), wherever you set PATH variable I had set it the following way:

export PATH=/opt/local/bin:/opt/local/sbin:$PATH

I modified it to the following:


export PATH=$PATH:/opt/local/bin:/opt/local/sbin

and everything works fine now. Hopefully someone with similar issues will land up on this page.

Debian changing root password

Follow these instructions to boot into single user mode and change the password of root on Debian.

1) When GRUB loads press 'e'
2) Find the line with initrd and goto the end and add init=/bin/sh
3) Press Ctrl + x to boot
4) You will get a prompt with #
5) You need to remount the root filesystem in read write mode by using the command mount -o remount rw /
6) use the command passwd to set the new password.

Done!

Statistics is FUN!

This summer I am taking a basic statistics course and auditing an advanced one. If the basic one is increasing my knowledge and giving me the confidence the advanced one is killing me!(in a very very good way!) After a very long time have I have had to spend nights understanding things from various textbooks and the joy in doing it is awesome! I am writing this post to share few thoughts and resources related to the topic.

1) In the past many of my friends have asked me for soft copies of ebooks. I download most of them from the following site: http://library.nu
I found almost 90% of the textbooks & novels I searched for from this website. I am using the following four statistics books to keep myself busy! Each book uses a different notation which gets to me more often than not but as of now the patience is paying off.
a) Probability & Statistics by Athanasios Paupoulis
b) Probability & Statistics in Engineering by Hines et. al.
c) Theory and problems of probability & statistics by Schaum series
d) All of statistics by Weisserman

2) I hate calculating expecation, covariance and correlation and all that crap for discrete distributions. Firstly, the calculations are cumbersome and secondly I hate Algebra! So, I put together the following script that calculates these. Just update the pdf and x, y vectors and you will get all the answers you need.

pdf=[11/50, 4/50, 2/50, 1/50, 1/50, 1/50;

8/50, 3/50, 2/50, 1/50, 1/50, 0;

4/50, 3/50, 2/50, 1/50, 0, 0;

3/50, 1/50, 0, 0, 0, 0;

1/50, 0, 0, 0, 0, 0;]

x = [0:5]

y = [0:4]

fx = sum(pdf)

fy = sum(pdf,2)'

ex = sum(x.*fx)

ex2 = sum(x.*x.*fx)

varx = ex2 - ex*ex

ey = sum(y.*fy)

ey2 = sum(y.*y.*fy)

vary = ey2 - ey*ey

[xgrid ygrid] = meshgrid(x,y)

exy = sum(sum(xgrid.*ygrid.*pdf))

covxy = exy - ex*ey

corr = covxy/(sqrt(varx)*sqrt(vary))

3) Proofs have always intrigued me. Although there is lot of fun in using a formula to get the answer and feel satisfied, I always found real satisfaction in deriving the formula. Being a computer science major has deprived me of such opportunities. But thanks to the stats course I get to sit and prove stuff again :-)
I am sharing two of the proofs for which I did not find straightforward solutions online. I hope it helps others who are trying to understand the proofs.

Probability Distributions

I am playing around with various discrete and continuous distributions for a statistics course assignment. So, I thought of spending few extra minutes and make a matlab script that would plot all of these. Below is the simple matlab script that plots Uniform, Exponential, Normal distributions. The Normal distribution can be generated using inverse transform, box-muller method and the most famous theorem in statistics: The Central Limit theorem.

I want to extend the script to take various parameters and plot more distributions like weibull, poisson etc. but I dont have time right now!

Code:

%% Uniform distribution using 100 instances

u1 = rand(1,100);

%% Uniform distribution using 1000 instances

u2 = rand(1,1000);

%% Exponential distribution using 100 instances

e1 = -log(u1);

%% Exponential distribution using 1000 instances

e2 = -log(u2);

%% Normal distribution using inverse transform method

n1 = norminv(u2,0,1);

%% Normal distribution using box-muller method

n2 = sqrt(-2*log(rand(1,1000))).*cos(2*pi*rand(1,1000));

%% PLOT1 ( Uniform, Exponential, Normal distributions )

figure(1),subplot(3,2,1),hist(u1,10),title('Uniform using 100 instances');

figure(1),subplot(3,2,2),hist(u2,10),title('Uniform using 1000 instances');

figure(1),subplot(3,2,3),hist(e1,10),title('Exponential using 100 instances');

figure(1),subplot(3,2,4),hist(e2,10),title('Exponential using 1000 instances');

figure(1),subplot(3,2,5),hist(n1,10),title('Normal using inverse transform method');

figure(1),subplot(3,2,6),hist(n2,10),title('Normal using Box-Muller method');

%% Triangular distribution

t1 = rand(1,1000);

t2 = rand(1,1000);

t3 = t1 + t2;

%% Central Limit Theorem

n = 12;

for i = 1:n

    t(i,:) = rand(1,1000);

end

n3 = sum(t);

%% PLOT2 ( Trinagular and Normal distributions )

figure(2),subplot(1,2,1),hist(t3),title('Traingular distribution');

figure(2),subplot(1,2,2),hist(n3),title('Normal using central limit theorem');

%% Save to eps files

figure(1),print('-deps','1.eps');

figure(2),print('-deps','2.eps');

Easiest & Fastest way to save Kinect depth and image data

After searching a lot to quickly get range and intensity data I thought of documenting the best way so that other people save their precious time! 

I ended up using Mobile Robotics Programming Toolkit(MRPT). Please goto this page for installation instructions: http://www.mrpt.org/Kinect_and_MRPT

I used the option of "installation from the repositories" instead of compiling from source. Its fast and easy this way.

Once that is done,

Download the code from here: Code

Download the cmake file from here: CMakeFile

Commands:

cmake .

make

sudo ./kinect_view

Cannot find the library `/usr/lib/libgdk_pixbuf-2.0.la`

I got this error while compiling Peekabot from source. If you get this error for the same reason or for any other reason: Installing pixbuf from source package is the workaround for now.

apt-get source libgdk-pixbuf2.0-0

cd gdk-pixbuf-2.22.0/

./configure --prefix=/usr

make

make install

If you install from the repos you get the shared library but not the static which peekabot seems to require!! 

Good luck!

Theory cheat sheet

For the theory course(CS6505- Computability, Algorithms, and Complexity) at Gatech I along with couple of my friends prepared a cheat sheet covering the topics of NFA, Turning Machines, Turing Reducibility, Data structures( Fibonacci Heaps ), Algorithms ( Dynamic programming, Divide and Conquer, Matching algorithms etc. I am sharing the .tex and pdf file in case its useful for someone. Please feel free to download and modify for your use.

 TEX & PDF

.glc to .avi conversion script

Thanks to Jon Rogers for this script!


#!/bin/bash
FILES="*.glc"
for f in $FILES
do
 echo "Processing $f file..."
 # take action on each file. $f store current file name
 glc-play $f -y 1 -o - | mencoder -demuxer y4m - -ovc lavc -lavcopts vcodec=mpeg4 -o ${f%.*}.avi
 # This previous line takes in the glc file at $f and changes the extension to .avi for saving it as mpeg4
done

Combining two laser scans into one coordinate system

For my current Boeing project I have to use two laser scanners to get 360 degree fov. I need to extract walls from the room and localize based on the walls. I decided to combine the laser scans from both lasers into one coordiante system and then extract walls. I wrote few matlab scripts to combine the scans and extract lines etc. After being satisfied with the results I moved to implement the same in C++ specifically in ROS. When I reimplemented I got very weird results when I combined both laser scans into one coordinate system.

After debugging for almost a day and taking help from a friend I found the BUG! I wish it was a programming bug, sadly it was a mistake in my understanding. I tried to put as much as possible in the image below. Once we knew the problem the formulas were elementary math but realizing that we needed to do this took time. I partially blame my matlab implementation which was also wrong but the error was never noticeable in the plots! At the end of the day though, things are looking great and I am glad one bridge is crossed :-)

After implementing it, the program started crashing arbitrarily giving segmentation fault! And that lead us to another "double precision" issue!! The calculation involves taking inverse sin by using asin. asin gives a HUGE number for any input greater than 1. In case of asin(a/b) for a=b due to double precision problems the function returned a crappy number. So, I had to make a minor modification so that a is always less than b :-) A productive day involving lot of debugging and learning!