Saturday, 21 December 2013

The legacy of Jean Baptiste Joseph Fourier

Vladimir Nabokov, a Russian novelist once said:
"The breaking of a wave cannot explain the whole sea"

I tend to disagree and today I'm gonna try and convince you that Vladimir couldn't be any further from the truth. To prove my point I would like to call the Ghost of Jean Baptiste Joseph Fourier into the witness box.

ME: Tell us Joseph, do you agree with Vladimir?

JOSEPH: Well...I think our friend's remark might explain a lot of philosophical questions as it is indeed true that in order to get the complete picture it is simply not enough to understand a few bits and pieces of it. To be called the master of one's creation, a person has to understand all the pieces of the puzzle and how they fit together.

ME: Did Vladimir pay you for saying all this?

JOSEPH: Oh no, no! I was just getting to the point that while his words have great value in the world of Philosophy, it stands no chance in the ruthless world of mathematics. Through more than 200 years of study, initiated by my work on 'Fourier Series', it has been rigorously proved that periodic signals can be expressed as a sum of very simple oscillating functions, namely sines and cosines (or complex exponential) each oscillating at an integer multiple of the fundamental frequency.

ME: Did you copy that line from Wikipedia or something? Anyways, continue.

JOSEPH: If you have a continuous time periodic function $f(x)$ (satisfying some criteria for convergence, of course) with period 2L, then it can be written as a linear combination or a weighted sum of complex exponential functions as follows

f(x)=\sum_{n=-\infty}^{\infty}A_n e^{\frac{\iota 2 \pi n x}{2 L}} \\
where \: A_n = \frac{1}{2L} \int_{-L}^{L}f(x)e^{\frac{\iota 2 \pi n x}{2 L}} dx

ME: Dude, you're talking French.

JOSEPH: Let me explain with the help of an example. Consider a square wave with unit amplitude and a period of 2 seconds. A quick calculation shows that the Fourier Series expansion of this particular signal is given by

f(x)=\sum_{n=1}^{\infty} \frac{2}{\pi n}(1-(-1)^n) sin({\frac{ \pi n x}{ L}})

ME: Yeah...right, that would've been a very quick calculation :p

JOSEPH: You can take a look at both my code and calculations if you are inquisitive enough. Click here, c'mon now don't be shy!

ME: Alright I got the calculation but what's the meaning of all this.

JOSEPH: I'm glad you asked that. What the above equation says, is that if you know the Fourier coefficients, not one or two, but all of them then you know the signal completely and it is possible to reconstruct the signal from them.

ME: But doesn't that justify Vladimir's statement then....the need to know all the pieces of the puzzle....all the waves in the sea :-(

JOSEPH: Not quite :-). Look at the image below where I've taken the sum of the first few terms in the Fourier expansion. I want you to notice that as the number of terms are increased from 10 to 1000 the quality of the reconstructed signal increases greatly and I can bet on the Eiffel Tower that with just a 1000 coefficients you won't be able to distinguish between a true square wave and a reconstructed one with just your naked eye.

ME: Ok...that kinda makes sense. But why is there an overshoot at the point of discontinuity.

JOSEPH: Ahem....I was.....umm....I was trying to avoid this discussion but now that you have asked, it is because of something called the Gibbs phenomenon. It happens whenever you try to take the partial sum of the Fourier series of a piecewise continuous signal. Don't give me that look....it is not my mistake. I bet if the computers you've made had infinite precision and were capable of adding the infinitely many terms in the series then the results would have been perfect.

ME: Alright Joseph, but you know there is a fundamental problem. Many signals in nature are continuous time but we must use digital computers to process them, so what use is all that you've told us.

JOSEPH: I think I must leave now for the gates of heavens are closing. Some bloke called Einstein is going to deliver a lecture on some hypothetical theory of Relativity. But two of my proponents Prof. Alan. V. Oppenhiem (MIT) and Prof. Ronald. W. Schafer (Hewlett Packard) have written a book on Digital Signal Processing which addresses this issue in great details.

ME: Your Honor, my witness has given enough evidence to suggest that, breaking a signal into its component harmonics often gives valuable insight about the signal itself. Even today, in applications like speech recognition and image compression Fourier Coefficients are used to encode the signals. With this note I rest my case.

In my next blog, I will skip a few steps i.e. the subtle relationship between Fourier Series, Discrete Time Fourier Transform and Discrete Fourier Transform and really get into how breaking a signal into component frequencies finds use in noise filtering. I know I promised to do it in this blog itself but some foundation had to be established. Anyways its my blog and I can change my mind whenever I want :p.

Despite all my efforts to be accurate and technically correct, some mistakes might have crept in. Please feel free to point them out in the comments bellow.

Thursday, 19 December 2013

The Philosophy and Science of Signals

Our lives as humans are meaningful because we are constantly interacting with our environment. Ladies and gentlemen we are in dynamic equilibrium with the states of the universe which is sustained only by an influx of information from sensory receptors in our body and our capability to rationalize and respond to this stimulus, sending fresh waves of change rippling through time and space. Scientists have studied these waves of information and change over a few centuries trying to understand and manipulate them. Today we all know these waves of change as “Signals”.

The range of studies conducted on Signals are diverse. Steve Wozniak might be interested in variations of voltage and current with time in the Apple motherboard. Steve Jobs on the other hand would probably be more interested in the ‘time-series’ of stock prices of Apple which are yet another type of discrete-time signals. Siri is obsessed with speech signals i.e. the variation of voice amplitude over time. And I am a fan of motion pictures which are variations in pixel intensities over both time and space (since any snapshot at a given time is an image which can be looked at as variation of pixel values over the span of the display screen).

Interestingly computers can be taught to analyse signals to extract the required information and this is a common theme that runs along all problems studied under the broad domain of Signal Processing. Just like food processing is important to convert raw food into edible form before it can be cooked, Signal Processing is important to reduce complex signals into rudimentary forms which can be consumed by the limited intelligence and rationale that computers possess.

For example, say a satellite picture of region around the Pantheon in Rome (a top view) is to be used to automatically register the total built up area i.e. the floor area occupied by all the buildings in the image. A possible way to tackle the problem is to write a computer program to detect the edges in the image and assuming that the edges corresponding to the view of the rooftops of the building would form closed loops, the program could simply count the number of pixels completely enclosed by loops. In this problem the method of detecting an edge is studied under Image Processing which forms a part of the algorithm for the task of inferring the built up area which is of interest to a researcher in Computer Vision.

 Smoothing the image while preserving edge information using Perona-Malik Diffusion

 Edge Detection applied to the diffused image using Canny Edge Detection Algorithm
This doesn't look simple and it isn't :p (I love this tongue-sticking-out smiley). Edge detection is done in 2 steps because if Canny edge detection is used on the original image directly then a lot of unnecessary edges are captured which may make the task even more difficult. Thus the image is first smoothed out using a sophisticated algorithm known as Anisotropic Diffusion developed by and named after Pietro Perona (Professor and Computer Vision Researcher at Caltech) and Jitendra Malik (Professor and Computer Vision Researcher at UC, Berkeley). Further as can be seen from the edges detected, our assumption about the loops being closed doesn't hold in many places and it is the job of a Computer Vision researcher to either work his way around this problem or improve the algorithm for edge detection or both.

This example clearly elucidates the dependence of Computer Vision on Signal Processing, especially Image Processing. There are other challenges involved too. For instance, the process of image acquisition by the satellite and transmission to the base station on the ground adds some noise which are random variations that corrupt the original signal. Noise is the manifestation of the imperfect world we live in. Noise removal is a pre-processing step in many applications including the one in question. All is well and good while there is sunshine and a clear sky, but what if clouds come in between the Pantheon and the satellite? That would be hilarious wouldn't it :p ?

Fortunately, Signal Processing deals with techniques that can filter out these unwanted additions to our good old signal like noise and cloud cover (yes! you can look through the clouds) and hence these methods are aptly called Filtering techniques. They come in varying degrees of complexity and applicability.

If you are as excited as I am, then watch out for my next post where we will explore a fundamental concept in Signal Processing and see how it can help us in noise removal in simple 1-D signals.

Guys and girls, please feel free to leave behind a comment. Older people, who don't think they fit into the category of guys and girls, need not refrain from doing so either :-) .

Code for Anisotropic Diffusion and Canny Edge Detection in Matlab

Monday, 16 December 2013

Initializing()

To begin with, the title of this post makes sense if you have ever written a computer program :p.
This is my first ever blog post so do try and be kind, but that's definitely not a prerequisite for following my blog.

The reasons why I have started this blog are as follows:
1. I am about to enter the final semester of my undergraduate education in Electrical Engineering and I am waiting for the results of my PhD applications. So, I have some free time that I would like to fill up with an interlude.
2. I am really fascinated by certain inter-disciplinary topics such as Computer Vision, Machine Learning and Image Processing (Computer Science and Electrical Engineering being the disciplines in question) and I wanted to share my thoughts with the world as I explore.

This blog might be useful for people who stumbled upon the idea that computers might someday take over our world (thanks to Hollywood which seems to be thoroughly excited by the idea and prospects of endless profits the idea might fetch at the Box Office) and would like to know exactly how human researchers have been facilitating it.

But on a more serious note, this century might see a remarkable change in how computers interpret this world of humans and make logical inferences from it. It might be worthwhile to participate if not lead the revolution. So, together let us embark on a journey into how Artificial Intelligence plays a role in our lives today and fathom how this might change in a couple of decades.