Supporting the Pavilion Lake Research Project

I am in the middle of a two week-long field work in Pavilion Lake, British Columbia, Canada. This is my first official "NASA" field test trip in a remote site and I am very excited to be here with the xGDS team from Intelligent Robotics Group (Tamar and Dave) to make sure our software helps the scientists operate smoothly as they collect and analyze data about microbialites.

Pavilion Lake, BC, Canada

Microbialites are rocks that are formed by bacteria. They are most often found in very harsh environments and are often many million or even billion years old. The ones in Pavilion Lake are especially of interest to the scientific community because they grow in fresh water that also support other living species. From what I understand, studying these microbialites provides an understanding of really ancient microbialites that were formed billions of years ago on Earth, and it may provide clues to origin of life on Earth and ultimately clues to life on other planets.

A better / more accurate understanding of microbialites can be found here: pavilionlake.com ;)

Microbialite sample

The software my team and I wrote is called Exploration Ground Data Systems (xGDS). It's a pretty amazing tool that helps scientists plan their flights, take time stamped notes, view and analyze video data, images, and basically whatever data they collected out in the field. They use it to plan, execute, and review the entire research project.

Allyson, a scientist, uses xGDS to take timestamped notes while viewing video and noting the location of the ROV via xGDS tracking system.

There are many things I really enjoyed and learned from Pavilion Lake Research Project, and one of them was observing how effectively this tightly-knit group of scientists and engineers were led by Darlene and her team. We operated on a tight, busy schedule that began with a 7am meeting, then a morning flight with divers in the lake with xGDS supporting, then lunch, then an afternoon flight with divers and xGDS support, then dinner, then evening debrief at 8pm (after which  our team would go back to the trailer to code some more). The days were busy and hectic, and I am slightly woozy from lack of sleep my eye and hand are swollen from the mosquito bites. But it was so exciting!! And I learned so much about team work and productive work schedule from her team.

Science team meeting at the end of the day.

In the previous years, the underwater data was collected using a manned-underwater vehicle (basically a submarine). During this year's test, however, we used underwater ROVs' (remotely operated vehicles) with cameras to collect footages and sensor data underwater. There are three ROVs' and you can see one below (his name is Seamor).

Seamor is a remotely operated vehicle (ROV) that goes underwater to collect various data including video and sensor data.

Sometimes the weather in Pavilion Lake would  be freezing and windy. But the next day, the weather would flip and we would get nice sunny weather like you see below!

Enjoying the sun after days of rain and cold wind.

So checkout pavilionlake.com for information regarding Pavilion Lake Research Project. It's been a great fun so far, sprinkled with lot of laughter, jokes, and lots and lots of adventure coding :) And I am super excited for this network of scientists I now know. They are the greatest, funnest bunch :)

Surface Telerobotics Mission with Astronaut Luca Parmitano

Surface Telerobotics Mission, Session 2, took place on July 26th. Astronaut, Luca Parmitano, controlled our K10 Rover on Earth from the International Space Station. You can see the software we built to control the rover in the below pictures :)

There were lot of media present on the day of the session for coverage, including WIRED, Space.com, etc.

• WIRED: http://www.wired.com/wiredscience/2013/07/nasa-ames-telerobotics/?pid=8511

• Space.com: http://www.space.com/22160-space-station-astronaut-drives-rover.html

• Global News: http://globalnews.ca/news/752773/astronauts-control-rover-from-space/

Surface Telerobotics Mission

So much happened since my last post. I marked my 1 year work-anniversary at NASA on May 28th, 2012. I produced three short films, two of which is related to NASA. One of those videos was shown to the astronaut in the International Space Station, as part of training for our mission: http://youtu.be/Gp_Jj3kzdiM

On June 17th 2012, we got to interface with the astronaut on board the ISS as part of our Surface Telerobotics Project. The day started at the crack of down (5am!). There were thankfully no major hiccups and we were able to successfully have the astronaut in space control the K10 rover on Earth! The astronaut who controlled our rover was Chris Cassidy. He's a Navy SEAL, an astronaut, and an engineer from MIT, which officially makes him one of the coolest astronauts ever :) When the session ended, he had only good things to say about the GUI and complimented us on intuitiveness of the controls and the smoothness of the operation. And this of course, made the day for all of us who worked on the project.

Here are high-res pictures sent from the ISS of the astronaut in ISS using our UI to control our rover on the ground:

Image Courtesy of Intelligent Robotics Group at NASA Ames Research Center

Image Courtesy of Intelligent Robotics Group at NASA Ames Research Center

Image Courtesy of Intelligent Robotics Group at NASA Ames Research Center

Picking up the brush again...

It's been about four years since I've drawn/painted anything. I think I couldn't justify the act of drawing/painting - I mean, I wasn't going to become an artist. My profession is clearly in computer science and everything else seemed like such a waste of time. Recently though, I met someone who convinced me to pick up the brush again and get back to painting. I watched Casino Royale with him and the image of Vesper Lynd stayed with me. It sort of shocked me that a Bond Girl can be witty, brainy, and vulnerable (as well as beautiful - I think you have to be if you are a Bond Girl). Anyway, Here are the paintings:

Scene Graph, Weak References and other Java Stuff.

Thanks to VERVE, a robot simulation platform running on eclipse, my knowledge of Java is increasing daily. Currently I am going through the VERVE code that deals with importing and parsing KML overlays (Google Earth File Format), and in the process I encountered the concept Scene Graph, which is how Ardor3D (the graphics library we use for VERVE) is structured.

Scene graph is a directed acyclic graph (DAG) arranged in a tree structure that is composed of nodes. The objects are stored in the leaf nodes of the tree and the non-leaf (group) nodes are there to group the leaf nodes together.The nodes in the VERVE scene graph are referred using weak references.

Weak References are references to objects that don't interfere with garbage collection. Normally, the objects are referenced using strong references:

StringBuffer buffer = new StringBuffer();

But in some cases, strong references causes memory leaks since it forces an object to remain in memory if it is reachable via chain of strong references.

Weak references don't force the object to remain in memory. They are created like this:

WeakReference<Widget> weakWidget = new WeakReference<Widget>(widget);

Sometimes garbage collector might throw out the weak referenced object before you ask for the object. And when you do ask, you might get back "null". To prevent this, you can use a weak hashmap, which has keys that are referred to with weak references. Weak Hashmap automatically removes the entry if key becomes no longer reachable.

Factory Method (and other Design Patterns)

While talking about a method inside Verve (3D simulator for robotic control), my teammate said that it was similar to a "Factory". At first, I thought he was making an analogy between an actual factory and the method. But it turned out that he was referring to a pattern called "Factory Method", which was of course outlined in the seminal book "Design Patterns" by Gamma et.al that I conveniently forgot to read after impulsively buying it from Amazon.

Factory Method is a design pattern in object oriented program that allows an instantiation of an object in the subclass instead of the superclass. The superclass would be an interface that outlines the objects that need to be implemented. It is the job of a subclass that implements the interface to instantiate these objects outlined in the interface.

Here's an example. Say you have a Shape super class. Inside the Shape's constructor, it calls a "makeShape" function, which is supposed to instantiate and return a Shape. But the program won't know which shape to make (in another words, "instantiate") because the type of shape is defined in the subclasses. So the job of instantiation is passed to the subclasses of Shape super class, such as Circle. Circle Subclass would implement the "makeShape" method that instantiates the shape and returns it.

There is another pattern that is similar to Factory Method but does not instantiate each time but rather passes back the same object that was instantiated once for that class. It's called a "Singleton".

Geometry Clipmaps

I am currently reading a paper called "Geometry Ciipmaps: Terrain Rendering Using Nested Grids" by Frank Losasso and Hughes Hoppe, for my next project in IRG for terrain-rendering related project.

What is a Geometry Clipmap: 

It caches the terrain in a set of nested regular grids (which are filtered version of the terrain at power of two resolutions) centered about the viewer and it's incrementally updated with new data as the viewer moves.

What is the difference between Mipmaps / Texture Clipmaps / Geometry Clipmaps ? 

A mipmap is a pyramid of images of the same scene. The set of images goes from fine to coarse, where the highest mipmap level consists of just one pixel. Mipmap level rendered at a pixel is a function of screen space parametric derivatives, which depend on view parameters and not on the content of the image.

A texture clipmap caches a view dependent subset of a mipmap pyramid.  The visible subset of the lower mip levels is limited by the resolution of the display. So it's not necessary to keep the entire texture in memory. So you "clip" the mipmap to only the region needed to render the scene. Texture clipmaps compute LOD (level of detail) per-pixel based on screen space projected geometry.

With terrains, geometry for screen space does not exist until the level of detail is selected. But texture clipmaps compute LOD per-pixel based on existing geometry. See the problem?

So geometry clipmaps selects the LOD in world space based on viewer distance. It does this by using set of rectangular regions about the view point and uses transition regions to blend between LOD levels.

Refinement Hierarchy

Geometry clipmap's refinement hierarchy is based on viewer centric grids but ignores local surface geometry.

Overview of Geometry Clipmap

Consists of m levels of terrain pyramid. Each level contains n x n array of vertices, stored as vertex buffer in video memory. Each vertex contains (x,y,z,z_c) coordinates, where z_c indicates height value at (x,y) in the next coarser level (for transition morphing).

Texture

Each clipmap level contains associated texture image(s), which are stored as 8-bit per channel normal map for surface shading (more efficient than storing per-vertex normals. The normal map is computed from the geometry whenever the clipmap is updated.

Per-frame Algorithm

• determine the desired active regions (extent we wish to render)

• update the geometry clipmap

• crop the active regions to the clip regions (world extent of nxn grid of data stored at that level), and render.

Computing Desired Active Regions

Approximate screen-space triangle size s in pixels is given by

eq1

W is the window size

phi is the filed of view

If W = 640 pixels, phi = 90 degrees, we obtain good results with clipmap size n=255.

Normal maps are stored at twice the resolution, which ives 1.5 pixels per texture sample.

Geometry Clipmap Update

Instead of copying over the old data when shifting a level, we fill the newly exposed L-shaped region (since the texture look up wraps around using mod operations on x and y). The new data comes from either decompressing the terrain (for coarser levels), or synthesizing (for finer levels). The finer level texture is synthesized from the coarser one using interpolatory subdivision scheme.

Constraints on the clipmap regions

• clip regions are nested fro coarse-to-fine geometry prediction. Prediction requires maintaining one grid unit on all sides.

• rendered data (active region) is subset of data present in clipmap (clip region).

• perimeter of active region must lie on even vertices for watertight boundary with coarser level.

• render region (active region) must be at least two grid units wide to allow a continuous transition between levels).

Rendering the Geometry Clipmap

//crop the active regions

for each level l = 1:m in coarse-to-fine order:

  Crop active_region(l) to clip_region(l)

  Crop active_region(l) to active_region(l-1)

//Render all levels

for each level l=1:m in fine-to-coarse order:

  Render_region(l) = active_region(l) - active_region(l+1)

  Render render_region(l)

Transition Regions for Visual Continuity

In order to render regions at different levels of detail, the geometry near the boundary is morphed for each render region s.t. it transitions to geom of coarser level.

Morphed elevation (z'):

eq2

where blend parameter alpha is computed as alpha = max(alpha_x, alpha_y).

eq3

v'_x denotes continuous coordinates of the viewpoint in the grid of clip region.

x_min and x_max are the integer extents of the active_region(l).

Texture Mapping

Each clipmap level stores texture images for use in rasterization (i.e. a normal map). Mipmapping is disabled but LOD is performed on the texture using the same spatial transition regions applied to the geometry. So texture LOD is based on viewer distance rather than on screen-space derivatives (which is how hardware mipmapping works).

View-Frustrum Culling

pic2

For each level of clipmap, maintain z_min, z_max bounds for the local terrain. Each render region is partitioned into four rectangular regions (see Figure 6). Each rectangular region is extruded by zmin and zmax (the terrain bounds) to form a axis-aligned bounding box. The bounding boxes are intersected with the four-sided viewing frustum and the resulting convex set is projected onto an XY plane. The axis aligned rectangle bounding this set is used to crop the given rectangular region.

Terrain Compression

Create a terrain pyramid by downsampling from fine terrain to coarse terrain using a linear filter. Then reconstruct the levels in coarse-to-fine order using interpolatory subdivision from next coarser level  + residual.

Terrain Synthesis

Fractal noise displacement is done by adding uncorrelated Gaussian noise to the upsampled coarser terrain. The Gaussian noise values are precomputed and stored in a look up table for efficiency.

Here are some good references:

A good follow up paper: http://research.microsoft.com/en-us/um/people/hoppe/gpugcm.pdf

Awesome website on terrain rendering: www.vterrain.org

SIGGRAPH 2012 Recap

SIGGRAPH [Sig-Graph]

Definition: Name of the annual conference on computer graphics (CG) convened by the ACMSIGGRAPH organization. Dozens of research papers are presented each year, and SIGGRAPH is widely considered the most prestigious forum for the publication of computer graphics research.

Our paper, Updated Sparse Cholesky Factors for Co-Rotational Elastodynamic, was presented at SIGGRAPH. Here's a picture of me and Florian (first author) doing a silly 40-sec advertisement of our session during Tech Papers Fast Forward.

SIGGRAPH ends up being a big re-union of friends since graphics industry/academia is so tightly knit. The left half of us met at PIXAR during the Summer Internship. Lot of us ended up in the visual effects studios including Pixar, Weta, and Bungie and we started our new jobs within few months of each other. The right half are my friends from Berkeley Graphics Lab. Everyone loves technology, art, and being a nerd. I loved spending time with these like-minded people. 

Curiosity landed on Mars succesfully on the first day of SIGGRAPH. There was a viewing session set up at the Geek Bar in Los Angeles Convention Center. A fair amount of people came, including my family who snuck in to the geek bar to watch the landing with me. I believe my mom cried during the landing. It was so emotional and I felt so proud to be an engineer.

And I got some quality time with my family and my parents' not-so-small-anymore pug. It looks just like Frank the Pug from Men in Black. This pug changed our family dynamic from a grouchy family to a loving family. It loves everyone it meets. Here's me pinching its velvet-pin-cushion cheeks.

One of the best things about SIGGRAPH is the screening of selection from the SIGGRAPH Animation Festival. I got to watch Disney's new short Paperman, which is screened in front of Wreak it Ralph. The style of it was an interesting blend of 2D and 3D framed in photographic black-and-white. I watched it three times, and during the third one I teared up a bit. It moved me in the best way. Definitely a dreamer and romantic's pick of the evening.

I also loved the style of Twinings commercial called "Gets You Back To You". My favorite part is when her feet plunges in to the shallow ocean. Makes me want to walk along the shores of Seal Beach before I head back to Silicon Valley.

During downtime, I wandered into the SIGGRAPH Bookstore. It's awesome because someone already did the work for you in selecting the books in your interest range. I ended up buying bunch of them:

C++ Coding Standards: 101 Rules, Guidelines, and Best Practices

Herb Sutter, Andrei Alexandrescu

I heard of this book through an amazing coder I programmed with at Berkeley. He was a C++ guru and when I asked him how he picked up C++ (Berkeley doesn't teach it to you) he mentioned that he read a red C++ book over Summer. I assume it's this one since it's one of the more well known red-books on C++.

The DSLR Filmmaker's Handbook: Real-World Production Techniques

Barry Andersson, Janie L. Geyen

I am considering purchasing a DSLR and shooting videos in my spare time (weekends tend to be open). Reading a book about production usually doesn't help with the process unless you absolutely have no clue as to where to start. Well, I have zero knowledge and any starting point will probably help.

An Interdisciplinary Introduction to Image Processing: Pixels, Numbers, and Programs

Steven L. Tanimoto

Can't wait to read this book. It looks at image processing from creative and artistic as well as technical point of view. 

3D Engine Design for Virtual Globes

by Patrick Cozzi

My friend Josh bought this book. I picked it up again at the store and read couple pages and realized that it's directly related to projects done by my team at NASA. It covers terrain reconstruction among other topics. I can't wait to read this one and hopefully implement it for planetary bodies. 

More detailed blog on technical talks at SIGGRAPH will be coming soon, including the ones on Mobile GPUs. So stay tuned...

Destination Innovations features IRG!

Cool video illustrating different Human-Robot Interaction Projects currently in development at Intelligent Robotics Group (where I work :D ).

Brushing up on Linear Algebra

Hermitian Matrix

Square matrix with complex entries that is equal to its own conjugate transpose.

i.e. [3 2+i; 2-i 1]

Positive Definite Matrix

A n x n real matrix M is positive definite if z'Mz > 0 for all non-zero vector z with real # entries.

z*Mz > 0 (for complex or Hermitian Matrix M)

example:

[z_0 z_1] [1 0; 0 1] [z_0; z_1]  = z_0^2 z_1^2

Therefore, [1 0; 0 1] is positive definite

Eigenvalues

Non-zero vectors that remain parallel to the original vector no matter what matrix (read: transformation) is applied to them.

Av = lamba *v, where lambda is the eigen value of A corresponding to v.

Cholesky Decomposition

Decomposition of a Hermitian, positive-definite matrix into product of lower triangular matrix and its conjugate transpose (take the transpose then negate imaginary parts but not real part). Analogous to taking a square root of a number.

A = LL*, where L is a lower triangular matrix with positive diagonal entries.

As an Outsider Looking In.

It’s beautiful and tragic to stand against the wall, hearing your friends talk about the most vulnerable stories of their life, their suffering, and their private sorrows. It’s beautiful because it enables you to love that person for sharing a part of themselves so freely. It’s tragic because you are the outsider looking in, wanting the change to happen now so you can obliterate the cause of suffering. But we all know that this is wishful thinking for now.

The stories were about living in the United States as an undocumented student. By now, I feel familiar with these stories and half expected myself to feel a bit blasé. But these stories are somehow endowed with new meaning from each retelling. They present new revelations about life and about your friends. You marvel at the things you didn’t know even after knowing your friends for more than two years.

Stories were read aloud as part of the reception for a new website launch, www.thingsillneversay.com.  The purpose of the website is to share the personal stories of immigration, especially from the undocumented students, with the wider audience. Many of the stories on the website are from peers who attended the same summer writing workshop I attended. We gathered in San Francisco and critiqued each other’s stories about our lives as immigrants.

It was a bond forged in sharing the most intimate part of our lives. The darkest periods that we vowed never to think of again and tucked safely underneath our consciousness. I remember how difficult and frustrating it was to bring them to surface again. But we agreed tonight that the experience of writing and reading them aloud healed us in many ways. The broken immigration system in the United States had scarred us in ways that we were not aware of until we reflected and shared. We healed through opening up and acknowledging that there is a community of us who went through the same trials.

The stories are usually about parting with loved ones. Grandfathers and grandmothers whom we left behind, knowing we’ll never see them again. It’s about the everyday objects from our previous lives that seem so precious in our memory now. The sibling who’s left behind without visitation rights. About wanting to apply for scholarships that demand social security numbers. The feeling of being considered an unwanted outsider even when we are not.

My friends ask me what I’m up to these days. I fumble through my answer, feeling tremendous guilt by the fact that I have a job at NASA when my friends are barred from working anywhere. Our only difference is the nine-digit number that grants a work authorization. We all find it silly and confusing that these nine digits can hold so much power. I feel as if I am looking in from the world of opportunity, only nine-digits away from the world that stops dreams midway through their fruition. I’m looking forward to the day when this separation no longer exist; a land where all of us live free of anxiety and fear, a land where everyone is truly equal.

Writing Efficient Code for OpenCL Applications

This is the part 2 of the OpenCL Webinar Series put out by Intel. There were some good information about optimization in general but lot of the information focused on how to optimize OpenCL running on 3rd Gen Intel Core Processor. I jot down some optimization notes that are applicable to all processors.

Avoid Invariant in OpenCL Kernel

Anything that's independent from kernel execution (invariants, constants), move it to the host.

Bad:

__kernel void test1 (__global int* data, int2 size, int base) {

       int offset = size.y * base + size.x;

      float offsetF = (float)offset;

       ... 

}

Good:

__kernel void test1 (__global int* data, int offset, float offset) { 

     ... 

}

Avoid initialization in Kernel

Move one time initialization to the host or in a different kernel.

Bad: __kernel void something (__global int* data) {         size_t tid = get_global_id(0)         if (0== tid) {                 //Do Something         }        barrier(CLK_GLOBAL_MEM_FENCE) }

Use the Built in Functions

i.e. dot, hypot, clamp, etc.

Trade Accuracy vs Speed

If the output is correct, look at the performance and use "mad" or "native_sin"

Get rid of edge conditions

Bad:

__kernel void myKernel(__global int* data, int maxR, int maxC){

       int row = get_global_id(0);

       int col = get_global_id(1); 

       if (row > maxRow){

                 ... 

       } 

       else if (col > maxCol) { 

                 ...

       } 

       else{

                 ...         

       } 

}

Use the ND Range (work within a smaller range. Just avoid the conditionals...)

Use the padded buffers...

Get rid of edge conditions in general

Use logical ops instead of comparison/conditions.

Reduce number of registers to increase parallelism

Avoid Byte/Short Load and Stores

Use load and store in a greater chunk.

i.e. uchar -> uint4

Don't use too many barriers in kernel

You are asking everything to wait until the work items are done.

If the work item doesn't run, the code may hang.

Use the vector types (float8, double4, int4, etc) for better performance on the CPU

Preferred work group size for kernels is 64 or 128 work items.

-Workgroup size multiple of 8

-Query

CL_KERNEL_PREFERRED_WORK_GROUP_SIZE_MULTIPLE parameter by calling to clGetKernelWorkgroupInfo.

-Match number of workgroups to logical cores.

Buffer Object vs. Image Objects

CPU Device:

- Avoid using Image Object and use Buffer object instead.

Brushing up on Probabilities, Localization, and Gaussian

Gaussian: It is a bell curve characterized by mean and variance. It's is unimodal and symmetric. The area under the Gaussian adds up to 1.

Variance: measure of uncertainty. Large covariance = more spread = more uncertain.

Bayes Rule

Localization:

Involves "move" (motion) step and "sense" (measurement) step.

Motion (move) : First the robot moves. We use convolution to get the probability that robot moved to the current grid location. We use Bayes Rule (given previous location, find probability of being in this current grid location).

Measurement (sense) : Then robot senses the environment. We use products to get the probability that the sensor measurement is correct. Measurement applies theorem of total probability (sum of:  probability that sensor measurement is correct given it's a hit, prob that sensor is correct given it's a miss).

*Side note: for grid based localization method (histogram method), the memory increases exponentially with number of state variables (x,y,z, theta,row, pitch, yaw, etc) 

Moonrise Kingdom

My roommate, Nicole, invited me to the showing of Moonrise Kingdom as part of her birthday celebration. I had seen the trailer and gathered that it's a film about two kids in New England who decide to runaway together. The film takes place in the sixties. I would have dismissed the movie if it wasn't for the cast and the pretty movie trailer (and the 94% rotten tomatoes rating also helped). I swept aside my Asian guilt (I thought about spending this evening coding) and joined her and her friends for the movie showing.

Moonrise Kingdom, whose title sounds like a Chinese martial arts movie, is so pretty. It's like candy to your eyes and ears. It's so pretty that I wanted to take frames out of it and post it around my room. Every scene is like a vintage polaroid photo. An advertisement from the 60s. It's as if Wes Anderson shot the movie through Instagram.

The plot is simple and yet each moment is full of innocence, wonderment, and adventure. And Wes Anderson  portrays children as complete human being with full mental faculty and emotional complexity! But frankly all that stands out in my memory is the color palette. The sepia and pink hues, the golden fields, washed out blues, red and green standing out against the desaturated background. There is such a decisive and consistent look throughout the film.

I guess one thing that slightly bothered me was the visual imagery of the night time scene. The rain is pouring and it's the evening. And either the director or the post-production crew decided to blue-filter the sh#$ out of it. So everyone's faces look blue. Like ghosts. I didn't particularly like the look but maybe it was the look they were going for.

I appreciated that the film didn't water down childhood. I find that childhood portrayed through Hollywood is either idealistic, fantastical, really sad and dreary, or some other end of the spectrum. The subtlety and complexity is usually entirely missing. Wes Anderson deals with it very delicately, being careful not to shift to the extremes I mentioned. And the acting from these kids is amazing. I loved the gaze of the main character (the girl). It's always distant and full of meaning, and we can never really guess all that goes inside her head.

Overall, I loved it. Two hours well spent and coding could wait.

Intel SDK for OpenCL Applications Webinar Series 2012

Intel hosted a webinar on running OpenCL on Intel Core processor. The webinar I attended this morning (9am, July 11th), is first part of the three-part webinars on this topic. It was well organized and educational and I think the next seminar will be even more useful (since it deals with programming using OpenCL. I took notes during the webinar to get you up to speed in case you want to attend the next two seminars.

* July 18-Writing Efficient Code for OpenCL Applications<http://link.software-dispatch.intel.com/u.d?V4GtisPHZ8Stq7_bNj1hJ=3231> * July 25-Creating and Optimizing OpenCL Applications<http://link.software-dispatch.intel.com/u.d?K4GtisPHZ8Stq7_bNj1hS=3241> 

OpenCL: Allows us to swap out loops with kernels for parallel processing.Introduction: Intel’s 3rd Generation Core Processor.

• Inter-operability between CPUs and HD Graphics.
• Device 1: maps to four cores of intel processor (CPUs)
• Device 2: Intel HD Graphics.
• Allows access to all compute units available within system (unified compute model - CPU and HD Graphics)
• Good for multiple socket cpu - if you want to divide the openCL code with underlying memory architecture.
• Supported on Window7 and Linux.

General Electric’s use of OpenCL

• GE uses OpenCL for image reconstruction for medical imaging (O(n^3) - O(n^4))
• Need unified programming model for CPUs and GPUs
• OpenCL is most flexible (across all CPU and GPUs) - good candidate for unified programming language.
• Functional Portability: take OpenCL application and run it on multiple hardware platforms and expect it to produce correct results.
• Performance Portability: functional Portability + Deliver performance close to entitlement performance (10-20%)
• Partial Portability: functional Portability + only host code tuning is required.
• Benefits of OpenCL:
  • C like language - low learning curve
  • easy abstraction of host code (developers focus on kernel only)
  • easy platform abstraction (don’t need to decide platform right away.)
  • development resource versatility (suitable for mult. platforms)
• Uses combination of buffers (image buffers and their customized ones). Image buffers allow them to use unique part of GPU.
• Awesome chart that compares various programming models:

Intel OpenCL SDK: interoperable with Intel Media SDK with no copy overhead on Intel HD Graphics.Intel Media SDK: hardware accelerated video encode/decode and predefined set of pre-processing filtersThank you UC Berkeley Visual Computing Center for letting me know about this webinar series!

Caramel

Ever since I heard about this movie, a foreign film from Lebanon that takes place in Beirut and written, acted, and directed by Nadine Labaki (a female director to boot), I wanted to see it but kept pushing it off. It came up again on my Netflix watch list so I finally decided to watch it tonight.

And it whirled me into its world: a small beauty salon in Beirut where people come to share their personal drama, joy, worries, and hopes. It's a pastiche of different stories that involve women who work in the beauty salon and their frequent customers.

And you will never guess what the caramel is used for. Hint: it's not for eating.

There are many poignant moments in the movie and what I appreciated the most was the honesty in which these poignant stories are shared. Unlike in Hollywood movies, where the story takes expected turns to satisfy the audience, Caramel has moments of disappointment, disillusionment, but ultimately hope. The beauty of life shown through its most mundane, every day moments. I loved it.

I was reminded of a quote from Gogol's Dead Souls, which strangely fits this movie:

And for a long time yet, led by some wondrous power, I am fated to journey hand in hand with my strange heroes and to survey the surging immensity of life, to survey it through the laughter that all can see and through the tears unseen and unknown by anyone.

AI Course on Udacity

I've been taking an artificial intelligence course on Udacity (http://www.udacity.com/courses), an online course taught by Sebastian Thrun. The course is called "Programming a Robotic Car". One of my co-workers pointed out that the course covers exactly what I need to learn - probabilities, Kalman Filter, Particle Filter, and SLAM. I will be blogging about my progress with the course and the insights I picked up from it.

Unlike OpenCourseWare from MIT and other webcasts offered, Udacity is much more interactive. I didn't find myself bored or distracted (though I'm taking a break right now to write this blog) because it has short quizzes (they are easy and very short) to recap the concepts covered in the video. The videos also focus on insight and doesn't dwell on the mathematical formulation of the problem unless it's absolutely necessary. And as a visual learner, I find Sebastian Thrun's drawings very helpful in understanding the concept.

I wish every web classes offered online were as good as these. I hope you find them useful.

Understanding FastSLAM

The SLAM I’m talking about has nothing to do with poetry or basketball. I’m “investigating” (read “learning on the fly") the SLAM algorithm (Simultaneous Localization and Mapping). One of my co-workers forwarded me two papers that I should read (http://tinyurl.com/6vfvuxg), both of which are co-authored by Sebastian Thrun of Google X (clearly I am very excited to point this out). I think it’s pretty awesome that reading research papers is part of my job.

To understand FastSLAM (version of SLAM in the papers), I needed to understand particle filter and Kalman Filter. Here are one sentence summaries based on wikipedia articles:

particle filter: Uses differently weighted samples of distribution to determine probability of an ‘event happening’ (some hidden parameter) at a specific time given all observations up to that time.

*note to self: similar to importance sampling: particle filter is more flexible for dynamic models that are non-linear.

Kalman Filter: Takes in a noisy input and using various  measurements (from sensor, ctrl input, things known from physics), recursively updates the estimates (they call it system’s state) to be more accurate. example: A truck has a GPS that estimates the position within few meters.  Estimate is noisy but we can take into account the speed and direction over time (via wheel revolution and angle of steering wheel) to update the estimated position to be more accurate.

*note to self: Kalman Filter assumes linearity in dynamics and in noise.

In terms of flexibility, it can be described this way (from least flexible to most):

Kalman Filter < Exteneded

Kalman Filter < Particle Filter

FastSLAM is a Bayesian formulation. It essentially boils down to this:

The particle filter is used to estimate the path of the robot (it’s given by the posterior probability p(s_t | z_t, u_t, n_t)). First, construct a temporary set of particles from robot’s previous position and the control input. Then sample from this set with probability of importance factor (particle’s weight). Finding weight of each particle is quite involved. I’ll let you refer to the actual papers for the derivation.

After we have path estimates, we can solve for landmark location estimates (the right side of the equation). Through series of equalities, authors arrive at:

FastSLAM updates the above equation using the Kalman Filter.

The main advantages of FastSLAM are that it runs at O(M log K) instead of O(MK), where M is number of particles, K is number of landmarks. I've had trouble understanding this part but here it goes: each particle contains the estimates of K landmarks (and each estimate is a Gaussian). Resampling particles requires copying the data inside the particle (K Gaussians if we have K landmarks). Instead of copying over all K landmark location estimates, FastSLAM does a partial copy for only Gaussians that need to be updated. Also the conditional independence between landmark location and robot location allows for easy setup for parallel computing.

Stay tuned for breakdown of FastSLAM2.0 ...