Australia and Computer Vision

Note: I have more than ever been busy with work and the loss of reach my blog suffered when Google Buzz ended has reduced a bit of the motivation I had earlier when updating it. I won't say I'm making a resolution for a come back this year but I will try to write earlier and write often.

The Three Sisters, a rock formation in the Blue Mountains in New South Wales, Australia.

I was recently lucky enough to attended a big conference in computer vision, the ICCV - International Conference in Computer Vision. It took place in Australia last December and it was refreshing. Australia is a great place to visit but more on that later. One thing that took me by surprise was that I and my collaborators were awarded the prestigious Marr Prize in computer vision. I'm very grateful about that. I won't go into details about our own work that led to this prize in this blog post but I will borrow an excerpt from Tomasz's vision blog to describe it:

"[...]. It is all about entry-level categories - the labels people will use to name an object - which were originally defined and studied by psychologists in the 1980s. In the ICCV paper, the authors study entry-level categories at a large scale and learn the first models for predicting entry-level categories for images. The authors learn mappings between concepts predicted by existing visual recognition systems and entry-level concepts that could be useful for improving human-focused applications such as natural language image description or retrieval. NOTE: If you haven't read Eleanor Rosch's seminal 1978 paper, The Principles of Categorization, do yourself a favor: grab a tall coffee, read it and prepare to be rocked. [...]"

I not only recommend following his blog but also to check out and fund his new venture on Kickstarter.

The conference was a big success and we saw some of the new trends in the field that are getting more established. I will briefly discuss two of those trends: 1) Using geometry for high level computer vision tasks like detection or total scene understanding. 2) Using neural networks and particularly deep architectures. These two separate trends share some history. Geometry was initially taken as the main tool for solving vision problems but time seemed to prove that, at least for object recognition, representing images with 2D templates and using clever machine learning was sufficient to recognize objects. This approach has practically solved the problem of detecting faces. Geometry was to an extent confined to a separate track of classic tasks like reconstruction from multiple images. But in this new trend there is a clear revival for geometry in recognition where people have realized that in order to move forward to make recognition more general we need to incorporate geometry back into the mix.

In the same light neural networks were at some point more or less thought as a general black-box for learning. You show the computer some images and some labels and the neural network learns how to label new images by adjusting weights and filters on the input representations. This weight and filter system has some analogy to how networks of neurons work together, hence the name. They were also used together with 2D templates to learn to detect things like digits or faces and they were successful. Unfortunately there was the problem of scaling to more general neural network architectures with more layers. This required adjusting an enormous amount of parameters that computers were just not able to handle at the time. Machine learning theorists also came up with very solid theory for other alternatives to neural networks like max-margin classifiers and kernels that had better theoretical grounds and comparable performance than the neural networks of the time. And soon people largely stopped using neural networks to attempt computer vision problems and even problems in other fields. This recent revival and interest in neural networks in computer vision is due to recent key successes in training deep neural network architectures that have shown superior performance on several important vision tasks. Today's computers combined with large amounts of data and clever new techniques have all made this possible.

Our paper on entry-level categories doesn't fall in any of the above two categories but instead insists on yet a new focus on vision which is that of finding clever representations of what we should be learning about our visual world. Solving computer vision is not just about translating pixel content into labels but rather about building a higher representation model of the visual world that we can eventually apply to specific instances of this visual world. We have advocated for some time that we can augment this visual world model using knowledge collected from text and studying how people describe images using natural language.

I will take the almost impossible task of using my last paragraph to highlight Australia as a destination. It is an awesome place! Being a huge island, the fauna of Australia is just so different than everywhere else that it feels the closest to a totally different planet. I can only imagine how was the first encounter of non-aborigins of the island with those animals. The kangaroos are like a portrayal of deers taken from a very creative sci-fi movie except they are real. The koalas also have no parallels. The wombats and tasmanian devils are also something to be set apart from the rest of the fauna. I also had a chance to visit Cairns and the The Great Reef Barrier and while this is an awesome view of the underwater fauna I have to say that I enjoyed the above ground fauna the most.

Starry Night Mosaic Art

I'm posting here a picture that I generated using so called mosaic art, which is a technique used by several artists and designers consisting of depicting an image using smaller units of content. The smaller units can usually be other images, for instance, remember the poster of the movie The Truman Show? There is software available to generate this type of images, here is one named Mazaika. Mosaic art has also been popularized to some extent by artists such as Chuck Close or Juan Osborne's amazing text mosaics. I wanted to do a simple experiment that incorporates an additional variable that I haven't seen in previous mosaics.

Coming from a computer vision perspective my motivation here is that most mosaics that tile images try to match only the color of the image for each specific location but they do not capture other characteristics like gradients (a sense of directionality) which is a common feature in most of today's computer vision systems. Take as inspiration the picture of the Starry Night by Vincent Van Gogh, made available by the Google Art Project at incredible resolutions. I'm including here a pretty high res picture if you click on it but feel free to explore the link above.

Click on the image for higher resolution.

For this kind of image, gradients are just as beautiful as colors and a good mosaic should be capturing both when tiling images. I used a database of 1 million pictures taken from Flickr to retrieve the closest matching image regarding both color and gradients for every tile in the composition. I also made sure to add some randomization so that nearby tiles don't get too similar images and only slightly modified the tonality of the resulting picture. I will try to update this post if I find a way to return even better matches regarding color and gradients or better tiling but I hope this mosaic conveys the idea of using gradients (a popular cue for many state of the art feature descriptors in computer vision) for creating mosaics.

Click on the image for higher resolution

Visual Attention and Visual Saliency

"Everybody knows what attention is ..."
-William James 1890

This quote is referenced in a research paper from the Visual Computing group at Microsoft Research Asia (MSRA), titled "Learning to Detect a Salient Object". I don't know exactly the context for that quote but it is interesting that somebody says this in 1890 when yet today we don't know many things about visual attention. Visual attention is particularly interesting in Computer Vision because in this field we want to teach computers how to recognize things in the visual world and it seems humans might be taking advantage of things like visual attention in ways computers still aren't.

To actually give some definition of visual attention I would say that it is the condition by which our vision focus in more or less degree on some things within the total amount of information that is perceived. Particularly in computer vision there are some research lines that are closely related to ideas in visual attention, one of them is visual saliency, which could cover among other things a) class-independent object detection or proto-object detection (although proto-objects as defined in the visual perception literature might not be directly usable in a practical application), b) detecting salient objects on an image (under the assumption that we humans do not consider all objects are equally visually important) or c) Detecting saliency maps that define regions that are important on an image without explicitly associating them with an object.

The paper from MSRA ("Learning to Detect a Salient Object" CVPR'07) detects a salient object under the assumption that we know a priori that there exists a salient object in the image. I believe this assumption holds for a large number of images on the web because that's just the way we think when we capture pictures, we usually focus on something. It is easy to imagine that not only Microsoft but also Google are already using some form of visual saliency to autocrop images from the web for display on search results or generating thumbnails. But beyond this obvious application there is room for using these kind of techniques to improve object detection itself or at least to avoid trying to detect objects on every possible location within an image.

Sample saliency maps for the top left image used as features in  the MSRA paper.
Those maps were generated using my own implementation of their method.

The MSRA paper also introduces the MSRA Salient Object Database, a large collection of images with manually annotated bounding boxes enclosing the salient object on each image. The only thing not included is source code, that's why in 2009 while I was starting graduate school I decided to implement their method on Matlab [link to source code]. And although the CRF formulation is not exactly the same, I get similar performance to the one reported in the original paper (See slides included at the end of this post). The paper has got some considerable attention since it was first published and so although I don't keep track of how many people are downloading my code, I see a lot of traffic coming from Google search. Also I didn't run many experiments beyond what is explained in the original paper but I found somebody using my code who did a more thorough evaluation. This was done by a student at the Computer Vision class at the University of Texas Austin http://vision.cs.utexas.edu/cv-fall2011/slides/larry-expt.pdf. As I had expected this method does better than Itti & Koch (previous much simpler approach) but only when it actually detects something, which is most likely to happen in the kind of images where we have a clear single salient object, the kind of images the method was trained on.

Links in this post:
MSRA: Learning to detect a salient object source code:
http://www.cs.stonybrook.edu/~vordonezroma/code.html
Saliency Experiments Slides from the University of Texas Austin:
http://vision.cs.utexas.edu/cv-fall2011/slides/larry-expt.pdf

Simple Audio Synthesizer in Java

This is about a program I wrote in 2005. The objective was to generate sounds that resemble the sounds of real musical instruments. This blog post includes an executable JAR file and the source code for this. If you computer is Java-ready you can start by trying it here right away [YASS]. (UI in English).

This is how the UI should look like (Except this one is the original UI in Spanish)

It uses a bottom-up approach to recreate the sounds of real musical instruments by starting from the most basic constructs - simple sinusoidal functions. This means that more complex wave functions are created by aggregating sinusoidal waves with different frequencies and modulating the amplitude of the resulting waves using envelope functions. The UI allows to modify the basic wave function by modifying the individual sinusoidal waves or choosing from a preset list of wave functions. It also allows for choosing from a preset list of envelope functions. Finally it allows to choose from a preset list of musical instruments. This latter option just chooses the appropriate wave functions and envelope functions that make the resulting sound resemble a musical instrument. This last part was done just by using my own judgement and not any machine learning (Disclaimer: I don't pride myself of having a sense of musical aptitude). And this is all this program can do.

One thing that is most likely wrong is the keyboard, I wouldn't trust the mapping of the tones in the keyboard to the actual tones, this is a quick fix though. I frankly don't remember where did I get the mapping for this keyboard. This document from the University of Tennessee explains how to make the mapping correctly: http://web.eecs.utk.edu/~qi/ece505/project/proj1.pdf.
Another thing that I definitely have to credit is Manfred Thole's demo on Fourier Synthesis, while I clearly took inspiration on the sinusoidal editor from his demo I totally borrowed his function to convert integers to the μ-law scale: http://www.thole.org/manfred/fourier/en_idx.html

Finally I was not sure if I should post the source code for two reasons: 1) Function definitions, variable names, etc are all in Spanish and I'm writing my blog in English. 2) I actually lost the original source code and had to decompile the class files inside the JAR file to get source code and recompile it again with the UI in English, thus additionally losing comments and therefore potentially not acknowledging some sources of inspiration and some wisdom for the future. Still I'm including here the source code in case somebody finds it useful despite of cons 1) and 2), one good thing is that it still compiles in the Java SDK 7 even after decompilation: [Yass-src.zip].

Colorado Springs and Kinect

I have again neglected my blog for sometime due to deadlines and other aside work. I just realized I never got myself some time to write about my visit to Colorado Springs for CVPR 2011 during the summer. Actually there is not much for me to say about Colorado Springs since I hardly visited any places beyond the hotel so I will just mainly refer about one particular paper presented in this conference.

CVPR 2011 might perhaps be remembered as the conference where the research paper Real-time Human Pose Recognition in Parts from Single Depth Images (The Kinect paper!) by Microsoft Research was presented. (Ok, this is obviously an overstatement, quality of research at this conference is really high) Microsoft Kinect is a product that has had a big impact that goes beyond gaming. This is a very iconic example of Computer Vision that works and is readily available to the world.

Wearing a cap and being Kinect captured

Kinect has inspired hackers (http://kinecthacks.net/), artists (http://artandcode.com/3d/) and general technology enthusiasts since its introduction some time ago. It has also inspired researchers to create new algorithms that can clean the data captured by the Kinect sensors and make the most out of it or just play with it (here http://acberg.com/kinect/ some kinect hacking in Matlab by Alex Berg, one of my vision professors in Stony Brook). The picture I included in this blog post was ironically captured in our fancy Motion Capture Lab using the inexpensive capturing device from Microsoft. People here have also been working on Kinect with applications to Music performances and Motion identification. (More links to be added later...). Update: Interactive Music using Kinect: http://tamaraberg.com/papers/kinect_music.pdf

Although I didn't stay for the whole week of the conference I also presented a paper in CVPR 2011 about automatically estimating photo-quality and user engagement for photographs titled: High Level Describable Attributes for Predicting Aesthetics and Interestingness. Our goal was to use Computer Vision to recognize what are the kind of photographs that users think are cool without explicitly having to ask them what is cool? (Note: Users might not even realize what are the individual things that make them judge something as cool or interesting). 

Time for Mobile!

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
Update 10/05/2011: Steve Jobs just passed away, my deep admiration for his work and legacy will always be alive. People like him have made working in Silicon Valley a dream for people like me.
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

Some years back there was a time when people thought it was time for mobile! but it wasn't. It was around 2002 when developers were being lured to creating wap applications for the new generation of more capable phones. Java had already gained popularity and it was finally serving its purpose of being a language designed to run on top of anything. J2ME applications were a hot topic, at least among developers. But I was always more attracted to web application development and so selectively chose not to go into the mobile arena. I never coded any J2ME or wap application or anything that runs on a cellphone even though most of my peers would "wow!" such developments. And of course this is my personal opinion and you should understand I'm biased on this topic but I know some people will agree and I have some good reasons product of my own experience to think that time for mobile is now and it wasn't quite ready before.

When I say time for mobile I mean time for developers to create applications and really start making profit and embracing powers that go beyond the typical desktop application. Technology has made a lot of progress of course. Now a smartphone can run stuff on the GPU (Graphics Processing Unit) that go beyond drawing things on the screen. You can take not only full advantage of the web but also other multimodal sources of information like GPS and information coming from various sensors: proximity, orientation, etc. But the more important changes are the not very technical ones, now you have a more clear model for distributing applications massively (Apple Appstore, Android market), and devices are more third party application centric than before. More importantly you have a more clear model for monetizing applications!, you can create the new big hit $1 app or you can go big with advertisements. You have already been listening for some time on the news about kids making $1 applications and going big and you might think I'm writing this way too late. I think this is partially true but while one-big-hit-wonders happened in the previous years, the success of those were in a lot of cases hard to predict. Today you can start a more principled entrepreneurial project and gain some reasonable success even if you don't happen to become a big hit.

The establishment of Social has powered the establishment of Mobile and also the other way around. Social networking applications bring people even closer when they incorporate mobile, for instance Foursquare lets you see whom of your friends is around you at a given time by using your mobile device location and the location of your friends (see my previous post mentioning Foursquare). You can engage users in a more personal level connection using mobile.

Finally, there are a lot of other things I would like to write about mobile, for instance Computer Vision for mobile since I work in Computer Vision and I spent the last summer working with images at the Multimedia Content Analysis team at Android. I gladly noticed how much people from everywhere inside Google especially from research teams were willing to contribute to Android and what cool applications are out there from third party developers taking advantage of Computer Vision both for Android and iPhone. One thing I will not write about is the controversy on which one is better or their legal problems on patents and the like. I really admire Steve Jobs and I think without his vision and the iPhone coming into the mobile scene things wouldn't have moved so fast, taking the idea of multi-touch to mainstream usage in a product for the first time was a big hit but the technological advances have been the sum of the knowledge of so many people and I think the world is a more colorful place with competition that fits the needs of several groups of users.

Learning Karate by Waxing Cars

I will introduce here an article by Peter Norvig that I recently read and involves a discussion about Artificial Intelligence, Statistical Models and Machine Learning, but before posting the link I will introduce the discussion with an example:

When I was a child I learned how to write proper Spanish by following what I will refer in this article as the karate-kid or Mr.-Miyagi approach. I present here two approaches to learn and improve your basic writing skills.
1. Take a class on grammatical and orthographic rules.
2. Read lots of grammatically and orthographically correct text, not bothering about rules.

By using the first approach you can get a sense of how to construct correct sentences early on, but the effects depend a lot on having rules hard-coded in your brain very heavily, practicing with those rules with lots of examples can certainly reinforce the rules to be learned.

The second approach does not involve learning rules at all but just reading lots of text data, let's say books. After reading lots of correctly structured sentences and words you can develop a sense of how a correctly structured sentence or word feels like without being conscious about rules. In other words for some cases you will be using rules almost without consciously thinking about them due to the amazing ability of our brains to find patterns. This second approach is the data-driven approach or as I prefer to call it, the karate-kid approach because I suspect this is the path Mr. Miyagi would have chosen if he had to mentor a pupil about how to write properly.

Mr. Miyagi asking his pupil to wax cars over and over again.

The field of Artificial Intelligence used to follow the first approach. If you want a smart computer, then hard code rules on it so that it can behave as desired. Hard-coding rules doesn't scale very well so you might want to learn the rules from data or adapt the rules over time but ultimately people realized that you might not really need to care about rules at all, as long as you just care about the system behaving as desired.  This is the topic of discussion in the article by Peter Norvig in response to Noam Chomsky's remarks where Chomsky apparently derided machine learning researchers. You can read it in the following link, I highly recommend it: http://norvig.com/chomsky.html

Mapping the world - from housingmaps to foursquare

This is the map generated using part of the controversial consolidated.db from my iPhone.

Yes, the above picture was generated using the pretty much talked consolidated.db file from my iPhone. I'm not planning to write a post about such controversy, a lot has already been said. I want to rather use this map to start talking about web mapping applications and applications that leverage the use of geo-data and two entrepreneur stories that have amazed me.

When I found about this iPhone-tracking-your-every-move controversy, as a good geek I tried to get the map of my recent movements and downloaded an application that some good developers had already put online. From the map it seems that I have yet left to explore Nassau County and the boroughs of New York, especially Brooklyn and Queens which are closer. I have mainly been visiting places in Manhattan and around Stony Brook in Suffolk County like: East Setauket, Smithtown, Selden, Centereach, Lake Grove and Port Jefferson.The consolidated.db file also successfully recorded my visit to Fire Island in the south shore of Long Island and another recent visit to Coney Island in the south of Brooklyn. Looking at your data on maps is a nice experience because even though you might have been to a lot of places, it is hard to have a picture of how much you have explored until you see your data in an actual picture! 

An interesting related note I found is that there's a group of researchers in the New York Times Company Research and Development Lab asking for people to donate their iPhone consolidated.db data for the benefit of all [see openpaths.cc]. More interesting to me than the applications on transportation, epidemiology or land use that they suggest is the fact that The New York Times Company has a full research lab. I like the idea that research is so important these days even for a media company best known for distributing one of the most popular newspapers.

Now I will talk about the first entrepreneurship story. Undoubtedly two mapping applications that changed things on the web were Google Maps and Google Earth, both cited as milestones in the history of web mapping compiled on the Wikipedia. They both started from the minds of very keen engineers and entrepreneurs but there's another story on top of that. They allowed people to start mapping anything without the effort of installing your own geographical information system. But most people might not know that this was not the case in the beginning of Google Maps where you didn't use to have a nice API.  One research engineer working in the field of Computer Graphics and trying to make computer generated images more realistic spent some of his research time on an aside project later known as housingmaps.com, where he merged the information from craigslist (housing advertisements) and Google Maps. This application didn't go unnoticed, it became so popular that people often believe this as one of the reasons for Google to release a full developer's API. The next year he was named one of the TR35 (Top innovators under 35) [link here] for creating this web application often regarded as the first maps mash-up. What I like about this story is the fact that his big idea came from an aside project and the fact that coding this application probably didn't take longer than a month.

Foursquare Badge rewarding
people for visiting three times
any place above 59th street in
New York City. 

The second story concerns another application that uses geo-data although it doesn't include maps itself: foursquare. A mobile application where you voluntarily reveal your location and moves through checking-in into different venues. It pulls your latitude-longitude coordinates from your mobile device so that you're one click away from shouting your location to the world or your friends. More recently you have the option to upload a picture about the places you visit. Chances to collect some fine-grained image dataset about places some day? [like the im2gps project]. Well, the story about foursquare is that it was developed by engineers who had previously worked at Google. But there are quite a few startups founded by former Google employees you might say. The interesting part is that these guys had already developed before joining Google another location based application called dodgeball, which was acquired by Google. Some time later they left Google and started again but this time they came up with this thing called foursquare.

My friends often ask me how to do stuff with the Google Maps API because I did an internship at Google in one of the Google Earth/Maps teams. Although I did indeed worked with one such team, my work was mostly concerned with server-side programming of image processing routines for aerial images. I in fact used the Google Maps API a bit for displaying results and also on my own time just for fun but I don't have vast experience with it and I know they have kept adding lots of features to it. I will end this by just wondering what else is left to do with maps and how many other useful linear information can be nicely mapped.

Minesweeper as an Introduction to Computer Science

The very first computer game that I remember playing is Minesweeper, in spanish Buscaminas (literally translates as Minefinder). It was probably 1997 during one day I was visiting the workplace of my father, I started exploring a computer with Windows 95. I think my father had loosely explained to me some of the basics about computers but I think it was mainly my experience with video games that made the transition smooth. I quickly navigated through the task bar looking for games and ended up clicking on the salient smiley face icon. I randomly clicked through the cells and ended up losing the game quickly and with disappointment. I had to wait some 3 years later until my family could finally acquire a personal computer for our house.

I liked minesweeper very much and I want to explain here how I embraced it in my education and what are the things I believe we can learn from such game that according to Wikipedia has been there since the early mainframes in the 60's. The first thing I liked about the game is that it is very self contained, it's more exciting if you figure out the game rules by yourself while trying it. You will quickly realize what are the meanings of the numbers when you start uncovering cells: The number of bombs around that cell. Then you will start realizing how to use this information and start finding patterns: The 1's in the corners, the 2's in the corners, several combinations of 2's and 3's and so on, those patterns that allow you to become faster and really master the game. Shortly after I started playing, my father and sister also liked the game and started playing it, often challenging ourselves in our computer.

After some time and with lots of spare time and a computer at home, I started exploring some basic programming. What I was actually most interested was in learning how to create webpages but at some point I found myself with programming some Javascript, mostly to open the infamous popup windows and creating some more stylish navigation menus. But I also started to wonder how to encode the rules of a game like minesweeper and thought maybe it would be a good exercise to try. I couldn't do it at the time and in my naive attempts without any guidance other than Yahoo Search and Altavista and the less known newcomer Google, I tried to learn the Pascal programming language to do the job but honestly I couldn't get very far on my own. I had to wait another 2 or 3 years until I was in my second year of college.

So I'm talking now about 2004, after an introduction to programming class and a data structures class under my belt. I was enrolled in the 'Object Oriented' programming class, a still hot topic at the time, at least in the local tech community back there. So I set my mind that I would use this class as an opportunity to implement minesweeper and play around with the rules of the game to create some variants of the basic game. The basic game requires an understanding of several things, there are two obvious things that you will gain from the experience:

1. Be good at manipulating arrays/matrices: Obvious! The game even looks like a matrix so this is the data structure you will need. You will have to traverse the matrix up and down, forward and backwards in every way possible. I implemented this in Java so I didn't need to think about dynamic allocation of arrays explicitly but if you want your game dimensions to be variable (beginner, medium, expert), then in a language like C you will want to go dynamic.

2. Be good at using recursion: This might not be too obvious but uncovering a cell with no number and no mine requires propagating a recursion call in several directions until you find a numbered cell. There's always a way to do it without recursion but recursion just comes naturally.

Beyond these two things you can learn about the power of random number generation when you're writing the routine to place the mines and also a basic convolution-like operation when you're assigning the numbers to the cells after the placement of the mines. Also if you're really into it you will notice things from the Windows Minesweeper like the fact that you never hit a bomb in your first move.

In the realm of Object Oriented programming itself which was the excuse for getting into this project, you can also learn to encapsulate your objects so well as to have the ability to create a new game by instantiating a Minesweeper class. Things like: new Minesweeper(), new Minesweeper('expert'), new Minesweeper(width, height, mineCount). Or even more, generalize your game to add the extra features in this way: SuperMinesweeper extends Minesweeper. Which effectively addresses the whole purpose of programming with objects in mind.

Minesweeper is not the only game that I get to program when I was on my first steps in the world of programming but now that I'm usually writing code for image processing and computer vision I get to remember the first times I was traversing matrices and performing convolutions and recursion calls over rows and columns. I'm including in this post a caption of the game that looks as close as it can get to the one distributed in older Windows versions. The code I wrote back then is still fully working but nowadays you can find lots of minesweeper implementations out there, even in Javascript which needs you to install nothing, you can try this one. Indeed you can find so many variants of it online and from so many places around the world. I, for one, thank all the programmers who wrote the early versions of minesweeper and also Microsoft's decision to include this nice game in his most popular software. This is a game that I believe has truly inspired many people even so far as to somebody proving that Minesweeper is NP-complete! How cool is that?

Podcast search - Large scale media retrieval

This is a follow-up post from my last tech post on Speech to Text using Java. I'm exploring here one idea I envisioned some time back (almost 4 years ago now) when I was a college student. This is the reason that pushed me to look for mature speech recognition technologies that I could use. By the way, this reminds me of some online lectures that I was listening the other day of Prof. Stephen Boyd (Stanford) on Convex Optimization where he was commenting that saying something is a "technology" might feel like derogatory to some people because this translates to using something as a black box without really understanding what is inside but he said he usually replies back by saying that most of us use TCP/IP without a deep understanding of what's going on inside to get a secure channel. In my case I was decided to use speech recognition roughly as a black box but ended up learning a bit of the underlying grounds anyways (language models, acoustic models, HMM's, etc).

My goal with my experiments with speech recognition technologies was to find a useful way to do video content retrieval using noisy automatically extracted transcriptions. Using this at the time I might have tried to beat Youtube on search (insert smiley face here), I even sketched the web search interface included in this post. But I was aware that making this at web-scale would require more computing power than whatever I could have available, especially at the time when I was working on this back in 2007 when Amazon EC2 was in its early stages, the Windows Azure Platform was non-existent and even Google App Engine was yet not released. I had to seriously narrow down my objective and make something that people who want media attention with a partially working prototype justify usually as "proof of concept" and in my case I would use this proof-of-concept as my way out of college.

At the time there was still a lot of buzz about podcasts on the web, which are the audio versions of blogs. So some companies were developing search solutions that could potentially look (or in this case listen) inside the contents of a large collection of audio documents. I'm including here a timeline of events related to podcast search and the use of speech recognition for large media search:

December 2004: Blinkx launches as the first audio search engine powered by speech-to-text technologies http://www2.prnewswire.com/cgi-bin/stories.pl?ACCT=LRTVN.story&STORY=/www/story/12-16-2004/0002636303&EDATE=THU+Dec+16+2004,+08:02+AM

April 2005: Podscope launches as the first audio search engine powered by speech-to-text technologies. (Hey! wasn't it Blinkx the first one?) http://en.wikipedia.org/wiki/Podscope

October 2005: Yahoo! Podcasts gets created although I haven't found if they used speech-to-text

http://docs.yahoo.com/docs/pr/release1266.html

January 2006: Podzinger launches featuring a US government funded speech recognizer

http://www.internetnews.com/infra/article.php/3576941/PodZinger-Launches-Audio-Search-Service.htm

July 2006: AOL Launches Podcast Search (powered by Podscope), this was the major internet company launching a service like this! I haven't found any information about when they broke the deal but AOL Podcast Search doesn't seem to be available anymore.

http://news.ebrandz.com/ask-a-aol/2005/336-aol-launches-podcast-search.html

http://web.resourceshelf.com/go/resourceblog/42962

October 2006: Microsoft uses some help from Blinkx technologies for their video search. http://en.wikipedia.org/wiki/Blinkx

June 2007: Plugdd starts as a podcast search solution using speech-to-text technologies. http://mashable.com/2007/06/29/pluggd-launches-audio-search-player-on-cnet/

October 2007: Yahoo! closes Yahoo! Podcasts

https://searchengineland.com/yahoo-podcasts-to-close-the-sorry-state-of-podcast-search-12288

July 2008: Google Launches a test version of their Speech Recognition based Video Retrieval system http://googleblog.blogspot.com/2008/07/in-their-own-words-political-videos.html

February 2009: TED adds captions and translated captions to its videos by using the power of the crowd http://blog.ted.com/2009/02/09/unveiling_teds/

November 2009: Google Launches automatic captions from youtube videos

http://googleblog.blogspot.com/2009/11/automatic-captions-in-youtube.html

This list is not exhaustive but I think it's enough to draw some conclusions. I included the fact that TED added captions generated by users in 2009 because I used some TED videos in my project to generate automatic transcripts so that video content from TED could be searched. I thought that since TED is all about interesting ideas it was a pity that you could not search based on contents. If I had put my idea/prototype online in 2007 it would have been useless by 2009 when it was no longer necessary to do automatic speech recognition when you already have perfect transcriptions in several languages for most TED videos. Another thing that I can see from 2007 up until now is that two big companies decided to shutdown their podcast search service (Yahoo and AOL). I was actually surprised that Google was not going into using speech recognition for audio search back then, they took their time and they have incorporated this into their already existing products (Youtube, Google Voice).  Podscope hasn't changed much since 2007 and Podzinger was rebranded twice (Everyzing, RAMP). Things move relatively slow in this area mostly because building automatic speech recognition software that is speaker independent and handles a large vocabulary is very expensive so only big companies or companies already owning rights over speech recognition software can compete. I think we yet have to see what's the final take on search based on audio contents, I think the best example today is the automatic caption generation on Youtube videos.

Speech to Text using Java

Is there out any utility, preferable command line that allows you to input an audio file and output a text file? Moreover, is there such a thing packaged as a library that developers can use? And yet again another technical requirement, is there something like it written on Java or another high level language? And as if it was not enough I want it for free. More than three years back I was looking for such a solution and I could not find something that works out of the box. If you try searching for something like this you will probably find the sphinx-4 project, a speech recognizer entirely written in Java. I spent a lot of time trying to understand the underlying basis of speech recognition and how it works, what are the roles of Language Models, Vocabularies, Acoustic Models, etc and not very few hours trying to make the whole thing work. I was successful in making it recognize isolated digits but what I wanted was general speech recognition that could deal with continuous speech, large vocabulary and complex grammar models. So I tried making it work for this scenario but I was unsuccessful, and for some of those models with larger vocabularies the system was very slow and I couldn't get much help with the documentation and available examples on the web. Without coming up with more excuses for my failed attempt I decided to take a different approach.

Surfing for other possible solutions I found some documentation for speech recognition engines from private companies that usually ship their products with a developer's API, big companies like IBM or Nuance. They would usually implement an interface known as SAPI (Speech Application Programming Interface) developed by Microsoft to provide speech recognition capabilities to Windows applications. In the same lines there is a JSAPI specification for the Java programming language. Microsoft not only developed the SAPI specification but also includes his own speech recognizer with some versions of the Windows operating system. So I downloaded the SAPI Software Development Kit and wrote a simple command line utility that reads a raw audio wav file and outputs a text file with the transcription of what was said in the audio file. Results were not great, especially because the recognition engine is not very speaker independent and some audio files that I tried had noise/music in the background.

The results of this hacking activity went beyond modifying one of their code examples to write this command line utility but I also wrote a JNI  (Java Native Interface) interface to use the recognition engine from Java, although I have to stress I did it more as a practicing exercise because I'm still limited to read only from a wav file. Of course this will only work on Windows but portability is something you will have to give up for this time if you want all those things that I mentioned at the beginning of this post. I'm including a link here with the command line utility with source code and the Java interface and one example of usage of the interface using Java.

Download: wav2text.zip

One limitation of those tools will also be that the wav file must be a PCM raw audio file with 22KHz frequency, 16 bit per sample and stereo sound. For this purpose I recommend using some nice command line utility to do the job: You can use SoX, an open source library and command line tool to change any of those parameters from the wav audio file. Also it would be great if you could input mp3 files or even video files. The problem with mp3 is that there are not so many solutions for conversion out of the box due to patents. You will have to download and compile LAME and integrate this encoder with SoX in order to get SoX to convert raw PCM wav files to mp3 encoded files. For video files the best solution is to use mplayer from the command line using mplayer -vo null -ao pcm:file=%FILE_PATH%. This will extract the audio from the video file.

Getting to hack with audio and video formats and speech recognition development was an interesting experience, this also exposed me to other higher level technologies like VoiceXML and later I had the chance to meet one of the developers of Firevox, a Firefox extension that focus on accessibility. Coincidentially a research project here at Stony Brook also does accesibility using voice technologies: HearSay.

This book  about the history of vocoders
is titled: "How to wreck a nice beach"
a phrase commonly used as example of
the difficulty of speech recognition,
because it sounds like: "How to recognize speech" 

Google New York

Google invited the Computer Science graduate student community at Stony Brook to visit their offices in New York last December. Most of the people were busy giving finals and wrapping up their Fall semester, still we managed to go there with a group of fellow graduate students. Weather was very cold but no snow yet at the time.

The tour was guided by both a Google software engineer and a recruiter. The company is moving from their Times Square location to two new buildings and although they only occupy a couple of floors on those buildings, the place still looks huge. From the outside the building we visited looks like any other building in Manhattan. This came in contrast to the Google-land looks of their main offices in California but once you're inside those buildings the feeling is the same, an open place full of fun and geek culture in every bit.

We attended a Tech Talk given by a Software Engineer and Ph.D. alumni of Stony Brook working on Google Local Search. He explained a lot of the challenges he has to deal with in his daily work and how they collect, interpret, present and more importantly search through geo data. Before the talk we played a trivia game where we could win precious Google merchandise. I managed to get away with the two items shown in the picture of this post: A Google mug and an Android plush doll. I got the green Android by completing the phrase of Edsger Dijkstra: "Computer Science is no more about computers than astronomy is about telescopes" and I won the mug by remembering the original name given to the Google search engine when it was first put online: Backrub.

After the talk and with some Google goodies in hand we had lunch with the rest of employees in the nice restaurants that have made this company famous for the free and good food. Beyond Google we didn't do much this day. We went to Washington Square Park with a group of friends and did some shopping nearby. Google New York seems like an awesome place to work although for me I came to realize that most of the work in my field of interest is happening in the west coast.

MapReduce -> GFS -> Bigtable

A yellow elephant, a perfect mascot
for anything geeky.

Some friend was recently interviewing for a full time position at Google. So we had this small conversation over email about some of the infrastructure that engineers have to master inside to build the magic that makes Google scale to humanity orders of magnitude. This is not a big secret, there is a lot information on the Internet by now and Google itself has published papers about these technologies. But I would like to share the things that I learned some time back during my stay at Google. I will try to explain what are MapReduce, GFS and Bigtable from the developer's perspective.

MapReduce: What do you usually do when you want to run your code over a large set of data in parallel? Naturally you would execute several instances of your program with different parts of your big set of data as input. Even better you could run those several instances of your program on different computers. There are several issues you have to take care of when you do this: Writing some extra code that splits the data and sends the appropriate pieces to each of your program instances, distributing your program itself to each computer and then collecting the data in a single place. And also you might want to think about some basic synchronization (counters) and fault tolerance. MapReduce takes care of most of those basic and more advanced things, you write your piece of code that will take data as input and you send your code and an initialization file to the MapReduce system that will be in charge of distributing your program and executing instances with the specified inputs. Why the name MapReduce? This is because the framework also addresses another issue. What is a general way of describing a distributed process that is so general that can be used to implement most kinds of distributed processing?  The answer is mapping and reducing. The processes that perform mapping are called mappers and the processes that perform reducing are called reducers. Mappers take an instance of the data as input and process it to generate some output. Reducers take the outputs of several mappers (or other reducers) as inputs and output a single output. It is interesting that by implementing our own mappers and reducers we can implement most processing functions that one might need. I will give two examples below:

Let's say you're in charge of calculating the average age of people on Facebook, your data is very big obviously and you will need to compute this average in a distributed way. In this case you would implement mappers that take a (date of birth) as input and output (key, (age, 1)), where key is a constant in this case. Your reducers would take an input of the form list of (age, count) and they would output a pair (key, (agesum, countsum)) that adds the ages and keeps the count of to how many people these age sum corresponds. At the end we will have a single output because the reducers will continue reducing until we have one output per key. So let's say you want to calculate the average age of people on Facebook by each country instead of average of all, then you would just need to use the country as the key and the reducers will receive a list of age and count only for the same key and will keep reducing until you get one output for every country.

Sometimes you don't need the reducers at all, let's say in the above example that you need to store a pre-calculated value of the age of the person using the East Asian age reckoning in which new borns are considered to have 1 year old at the time of birth and the age changes each Lunar Year. In this case the mappers take (date of birth) as input and output (East Asian age), and there is no need to use reducers, the process is purely mapping. You can watch how other algorithms can be implemented in MapReduce in the next video.
http://www.cloudera.com/videos/mapreduce_algorithms (They explain sorting)

GFS: There is one problem with the above approach that GFS solves. By using MapReduce we are now able to distribute our processing to hundreds of computers but imagine all those processes trying to read from the same physical location. This will slow down most hard drives and also processes will block while trying to read the data. So if you have a distributed processing system you will also need a distributed file system and that is GFS. A good MapReduce framework will not only use a distributed file system but will also try to assign data to each mapper based on the physical proximity of data.

Bigtable: Instead of reading/writing to files it would be better if you had some more structured way of storing your data, like a database. Bigtable is a database that runs on GFS. But Bigtable is not only a database that runs in GFS, it is also a different kind of database. Some differences are that in Bigtable you can have varying amount of columns for each row without any penalty in performance and you don't need to define columns when creating the tables. The original paper says about Bigtable: 'A Bigtable is a sparse, distributed, persistent multidimensional sorted map'. And I found this nice article explaining each of those properties in more detail http://jimbojw.com/wiki/index.php?title=Understanding_Hbase_and_BigTable.

Finally I will translate the proper title of this post
'Google MapReduce -> Google File System -> Google Bigtable'
to the opensource Apache implementation of these technologies
'Apache Hadoop -> Hadoop Distributed File System-> HBase'.

Texture Synthesis, Computer Graphics and Computer Vision

Choosing some problem to work on is a very difficult task, regardless of the area that you work on. Sometimes we choose problems based solely on our personal curiosity, other times due to funding commitments. This time I was trying to decide about a small project assignment using computer graphics based solely on personal curiosity. One insight I had some time back before starting graduate school was the importance of image processing on computer graphics, especially when it comes to rendering and synthesizing textures. I thought this problem was interesting for several reasons: It was a relatively simple but well defined problem, it required knowledge about image processing, graphics, data structures, statistics, visual perception and optimization. There was already a body of knowledge from where I could learn. And there have been a lot of successful applications and future works based on those methods. I can mention now image inpainting, non photo realistic rendering and some popular seam carving methods on image processing.

The problem of texture synthesis can be described as follows: Let's say we need to put a texture on a large floor for a video game, but we only have a texture image of a small size. How do we texturize the entire floor? One thing we can do is to repeat our small image over and over until the whole surface is covered. We will obtain easily noticeable boundaries, and even if we create special textures that match in the boundaries cylindrically we will still notice the same pattern repeating over and over at a fixed rate. The ideal solution would be to create a method that 'learns' the texture in order to create a larger one that can give you the same appearance locally and globally as the original texture.

I looked at several publications on this and invariably the use of image samples to synthesize textures was the one that had established the most profound impact in the area. The idea of these methods is to take small image patches from the image pattern that you want to reproduce and place them randomly in the output texture but taking care of merging the boundaries without noticeable effects. I can't really survey those methods in a blog post but I actually did a small survey on them in this technical report
http://www.cs.sunysb.edu/~vordonezroma/texturesynth.pdf

I chose to implement the method described in the SIGGRAPH 2001 paper named 'Image Quilting for Texture Synthesis and Transfer' by AA Efros (Berkeley) and WT Freeman (MERL).  Now 9 years after the paper was originally published and 1 year after I decided to take a look and implement this method, Prof. Efros was awarded the Significant New Researcher Award at this year SIGGRAPH 2010.   An excerpt of the award recognition reads:

'...Efros has published in a variety of areas in computer graphics
and computer vision, but his work can be broadly characterized
as employing data-driven approaches to solve problems that are
difficult to model using parametric methods. For example his work
in texture synthesis by example revolutionized an area in which
previous researchers had largely employed parametric approaches
with moderate success ...'

Which also summarizes what I had in mind before, this method and problem was one that was significant, has a proven track of applications derived from it, I can learn from and is definitely worth looking at. I created a video of my program synthesizing several textures. I include here the video and the slides that I presented in my class of Computer Graphics under the kind supervision of Prof. Hong Qin.

View more presentations from Vicente Ordonez.