Neil Birkbeck

Turns out I wasn’t very active updating the publications. It is now up to date (has things after 2008).

http://www.neilbirkbeck.com/wp/nb-pubs.php

…not only for this post, but also the cleaning that I just started on the old filing cabinet. It feels nice to get rid of old paper, like receipts & visa statements, from over 10 years ago. The best part is going through the auto expenses, and basically discarding the entire folder–this last year with only one shared vehicle has been great.

One of the most painful folders to go through is the computer receipts. Its hard to swallow how much was spent on computer things. Back when I was just starting out as undergrad, I was playing a lot of Quake 3, and I got caught up in the “trying to have the latest hardware” cycle. This was also at a time when I was working a lot during the summer and still living with my folks, so maybe it was okay to spent $500 on the latest graphics card, if only to get a few more FPS out of quake.

Just out of curiousity I am going to tabulate all of the major expenses during that time:

Surprisingly, I only found receipts for a few mice and keyboards; they probably weren’t kept (Keyboards: 3, Mice: 4).

It all started somewhere around 1999, when I had just started university the year before.  I remember upgrading our home computer for about $500, and was psyched that I could play DVDs on the TV with it.  At about this time was when we first started to use the internet.

1999 ($253)

Quake 3 Arena Boxing Day ‘99, $50
FaxModem $203

2000 ($3000!)

This was about the time when I really started to waste money upgrading and spending too much time playing quake.  I think there was a time when I was upgrading our old computer from 133MHZ processors to slightly faster ones that I could find on the edm.forsale newsgroup.   I was working two jobs over the summer and I had hurt myself skateboarding, so all of my efforts went into Q3.  I can’t believe how much was spent, and I’m sure that I bought a huge 19 inch monitor for over $300 during this time.  And these are only the ones I have receipts for.  Many other things were purchased from individuals (and a few sold).

In my defense, I was helping build computers for my G/F at the time, and also for my parents, and brother (I think).  The main problem is that I was caught up in the benchmarking scene.  Its impossible to keep up with it.  The other major cost associated with this was trying to overclock my Athlon.   I had penciled in some marks on the chip to unlock the clock multiplier, and when putting the heatsink back down, I partially crushed the casing.  A little later things weren’t working well (random blue screens), during quake, god forbid.  I had to take it into two places: one charged me for more expensive ram, and the other found out that it was just that one of the cards wasn’t seated all that well.  This chipped die went on to be a decent computer for years later.

Intel Pentium MMX-233 MHZ CPU $80
3DFX Voodoo3 2000 16MB $140
VooDoo3 300 16MB $115
13GB HDD $185
Thunderbird 800, $320
Asus A7V $250
Raid Controller $160
Tower $60
Samsung FDD $20
Power Surge $35
ASUS AGP V7700 GEFORE 2 GTS DELUXE 32MB $495
Gamepad: $55
Tower and 300 Watt PSU $80 + $45
Another diagonstic: $75
Diagnostic + 128 VCRAM: $295
CD writer: $339
Epson stylus: $250

2001 ($861)

Maybe I learnt my lesson from the previous year.  2001 didn’t seem so bad

Lexmark Printer: $246
HIS ATI Video Card $45
Speakers + SB Card $80 + $32
A7V133 Socket A, $188
MSI Starforce $145
Duron 750 $90
Duron Heatsink $35

2003 ($300)
ATI 9800 AGP128MB $300, April

2004 ($593):

Pyro video camera $80

Wireless router and card $183, 2004
Printer Ink and DVD writer: $330

2005 ($1024):
iPod Nano: $250
Samsung 17 inch monitor $387 * 2

2006 ($525):
LG Monitor $250,
160GB HD $90,
MSI 7600GS $185

Somewhere in between I bought Athlon 64 and kept that up until about 1.5 years ago.

It turns out that some of these things were actually good investments.  Obviously graphics cards and printers are not.  But the two monitors I bought in 2005 are still going strong.   Same with the surge protector: don’t have to worry about the current T-storm we are having.

In the end, I’m glad I no longer try to keep up on the latest hardware, but at the time I guess it was exciting.  It also seemed like things were changing faster back then.

Not too long ago, I was working on something where it was necessary to extract the correct locations of peaks in a 1D signal.  The 1D input signal comes from some noisy measurement process, so some local method (e.g., thresholding) may not always produce the best results.

In our case, the underlying generator of the signal came from a process with a strong prior model.  For simplicy, assume that the spacing between the peaks can be modeled as Gaussian with mean, mu, and standard deviation, sigma.  Also, assuming that the input signal is the probability of a peak (e.g., the signal is real valued, in [0, 1]), the problem can be formulated in a more global way.

For example, in a Bayes approach, the problem would be formulated as maximizing p(model | signal), where the model = {x_1, x_2, …, x_k} is the set of points where the peaks occur in the signal.  The MAP estimate is obtained by maximizing p(model | signal) ~= p(signal | model) p(model), or minimizing -log(p(signal | model)) – log(p(model)).  Assuming a simple Gaussian distribution between the spacing of the peaks, the prior, p(model), is easily defined as \sum_{i=2}^N exp(((x_i – x_(i-1)) – mean)^2/(2 sigma)^2).

For the negative log-likelihood term, we can use something as simple as -log(p(signal | model)) = \sum_{x} signal(x) * f(x; model) + (1 – signal(x)) * (1 – f(x; model)).  Where f(x; model) = 1 where for some j, x == x_j, and 0 otherwise.

On first encounter with this problem, it seemed like dynamic programming would be ideal to solve it.  In order to use Dynamic programming, we relax the unknowns, x_i (represent the ordered locations of our peaks) and allow them to take on any value in the input domain.  The dynamic programming solution is then straightforward.  In the first pass, the total cost matrix for all the peak locations is created.  For each variable x_i, we store for each possible input location, the total cost for that location and all previous variables.  In order to compute the total cost for variable x_{i+1}, each possible input location finds the best combination of x_i’s total cost, the likelihood, and the prior cost between x_i and x_{i+1}.

The only difference is that at each peak location, the likelihood for the region after that peak location is not considered (until later) and the peak location is penalized for appearing before x_{i-1} (ensures ordering).

Once the total cost matrix, C, has been computed (e.g., NxM matrix with N peak locations and an input signal of length M), the likelihood beyond x_i can be considered.   For each of the possible peak locations, we accumulate the likelihood beyond the candidate peak location  (e.g., C(i, j) = sum(neg_log_likelihood(S(j+1: M))).  If done this way, each row of the cost matrix now gives the total cost if we were to consider only i peaks in the input signal.  That is, we get the best locations of the peaks for all possible numbers of peaks.

In the following synthetic examples, the global dynamic programming method was used to extract the peaks in the input signal, as well as the number of  peaks present.  The global method used searched for up to 5 more peaks than were present in the ground truth.  For the top examples the input peaks had a mean of 14 and standard deviation of 2.  The dynamic programming method used the ground truth from the underlying model during its prediction.

Simple example, where a non global method would work	Another simple example, with more peaks, number automatically selected
A more difficult example with more noise (4 peaks)	A more difficult example with more noise (10 peaks)
A harder example, notice that the last peak is detected correctly, even though the input signal is almost homogeneous near it.	A harder example where it would be harder to select the ideal threshold.
The success of the global approach depends on the prior model providing some information in the presence of noise. With a small standard deviation, significant noise can be overcome (notice the high peak at around 70 in the input is not a true peak in the ground truth signal).	When the prior model has a large standard deviation, the global method can not as easily resolve ambiguities. In this case, the wrong number of peaks is selected and the peak near time 50 is missed.

The above tables were generated in octave (dyprog1D source code).

I was browsing google projects today, and I came across some things that I probably have seen before, but forgot.

• jogl: Java bindings for openGL.  There is some interoperability between java and this too (swing components).
• jake2: http://bytonic.de/html/jake2.html Java port of the quake2 engine
• http://pypy.org/
• Javascript math library: http://sylvester.jcoglan.com/
• Google’s Closure: http://code.google.com/closure/
  • I’m not really a javascript guy, so I don’t feel guilty for just learning about these things today.

Another boost feature that I just learnt about, that could come in pretty handy: http://www.boost.org/doc/libs/1_40_0/libs/conversion/lexical_cast.htm

I recently attended a talk by Robert Tibshirani, who mostly presented his work (and related developments) of the Lasso. The talk was very interesting, but I found some of his most recent work on spectral regularization for matrix completion particularly interesting. There are several problems in vision that suffer from unknown data, and this tool seemed like it could help out. I quickly prototyped some solutions using his/their approach and it does seem to have benefits in these applications, although I’m not sure of the impact.

I have written a draft document that details the problems that I was thinking about: spectral-reg-vision.pdf

And some quick and dirty matlab scripts that were used in the testing: spectreg

The polygon growing is coming along. Found this nice tool for polygon clipping: GPC. It is a C library that is all in one file. Nice and lightweight, efficient, and has a simple API (there are only a 6 or so functions, only two of which you need to use). And it does polygon union, difference, XOR, and something else I think. I’ve been using it to convery the meldshape (level set generated shapes) non-overlapping images (with spaces) into complete tilings of the plane:

Input (want to get rid of spaces)

Output (complete tiling, shapes do not overlap)

Maybe in the near future I will have the upload (it is a complement to JShape: the random shape generator). And also some details on how the GPC library was used to generate these.

Last year, at about this time, I went through an itch to implement various optic-flow algorithms. One that was brought to my attention by a classmate was the grid-powered non-linear registration from the medical community:

http://www.mendeley.com/research/grid-powered-nonlinear-image-registration-with-locally-adaptive-regularization/

Shortly after implementing the method, I was driven to write a GPU optimized version. First, because I wanted to use Cuda. After I got started, I realized it was just as easy to implement the idea using shaders alone. I tested out using gauss-siedel to solve the sparse system of equations on the GPU needed for the diffusion component of the algorithm (they actually use adaptive operator splitting and a fast tri-diagonal solver in the paper, I believe). I remember not being all that impressed by the speedup that I attained (somewhat less than 2 times for this solver including read back, maybe 4 times without reading back). I ended up using an explicit filtering approach for the diffusion.

I wanted to post the code (it has some internal dependencies for creating windows and initing shaders, if anyone is interested I can supply): gpu-gauss-0.0.tar.gz

I didn’t actually compare the timings to the CPU implementation, but here is an example input sequence (same image perspectively warped):

Below is a cross-faded animation of the warped gifs. I didn’t really tweak the parameters (there are a couple for # iterations), but one-way flow took about 0.9 seconds on a geforce 8800 (including loading the images and saving, etc). This was run using the command: ./warp /tmp/w0.png /tmp/w1.png --seq=0 --its=20 --upd_its=20 --glob_its=40. There are a couple of artifacts around the boundary, but for the most part it looks pretty accurate. I have a couple other implementations of optic flow to post sometime.

Recently tested out an idea for using a view-dependent Laplacian smoothed depth for rendering. Given a set of 3D points and a camera viewpoint, the objective is to generate a dense surface for rendering. Could either do triangulation in 3D, in the image, or some other interpolation (or surface contouring).

This was a quick test of partitioning the image into bins and using the z-values of the projected points as constraints on a linear system with the Laplacian as smoothness. The result is a view-dependent depth that looks pretty good.

Check out the videos below. The videos show screenshots of two alternatives used for view-dependent texturing in a predictive display setting. Basically, an operator controls a robot (which has a camera on it). There is some delay in the robots response to the operators commands (mostly due to the velocity and acceleration constraints on the real robot). The operator, however, is presented with real-time feedback of the expected position of the camera. This is done by using the most recent geometry and projective texture mapping it with the most recent image. The videos show the real robot view (from PTAM in the foreground) and also the predicted view (that uses the geometric proxy) in the background. Notice the lag in the foreground image. The smooth surface has the a wireframe overlay of the bins used to compute the surface. It works pretty good.

• smooth-surface
• Or an alternative: tet-surface

Currently, the constraints are obtained from the average depth, although it may be more appropriate to use the min depth for the constraints. A slightly more detailed document is available (although it is pretty coarse): lapproxy.pdf

Another improvement would be to introduce some constraints over time (this could ensure that the motion of the surface over time is slow).

Not much to say about this yet.  Trying to work on something for an artist.  This is a first attempt.  Starting from the same starting position, each of the other configurations have random stiffnesses, which means different images get generated.

Some movies:

trial1trial3trial4

trial2

Again, we were recently working on a project involving a robot and a colleague’s (David Lovi’s) free space carving to acquire a coarse seen model. The model is fine as a proxy for view-dependent texturing (e.g., lab-flythrough):

But to generate a figure it is nice to have a single texture map. Since the geometry is course, a simple averaging is out of the question:

After some minor updates to my initial implementation (to take into account the fact that all images were inside the model), the space-time texture map (idea anyhow) seems to work pretty good. Remember that this assigns a single image to each triangle, but it does so in a manner that tries to assign neighboring triangles values that agree with one another while ensuring that the triangle projects to a large area in the chosen image.

Of course the texture coordinates above are not the greatest. The texture was generated from some 60 keyframes. The vantage points below give you an idea of the quality of the texture:

Again, the model is coarse (obtained from key-points and carving), but space-time texture map idea works pretty good to get a single texture.

The data for the model was obtained with the prototype system (described in this video http://www.neilbirkbeck.com/wp/wp-content/uploads/2010/03/IROS_predisp.mp4)

We were recently working with the WAM robot and needed to generate trajectories from a haptic device. The WAM code-base had code for following a simple trapezoidal trajectory. It is straightforward to generate such a trajectory given
maximum velocity and acceleration constraints.

Trapezoid velocity profile

The WAM library routines allowed to issue more positional commands (using MoveWAM), but the previous trajectory would be halted and the new one started with an initial velocity of zero. The figure below illustrates what would happen:
Clearly the p(t) curve is not smooth at the time of the new interruption (v(t) is discontinuous); this is evident in the robot motion. A worse case occurs when the commands are issued more frequently, implying that the trajectory can never reach
full velocity.

Trapezoid interrupt

Instead of creating a new trajectory with zero velocity, especially when the subsequent commands are the same as the previous command, the trajectory should take into account the current velocity. So instead of the result above, the interruption should still
produce a curve more like that in the first figure. Regardless of where the interrupted commadn is received (or its location), the resulting positional trajectory should obey the constriants. For example:

The implementation is straightfoward. There are main two cases to handle. Like before, if the distance to travel is large, the trajectory will have a period owhere the velocity is at maximum velocity. The details of the implementation are in the attached document (trapezoid-writeup)

Results

The figures below illustrate what the curves look like (red always starts at zero velocity, and white utilize current velocity).

Sample trapezoid trajectory.

The bottom figure illustrates the non-smoothness of the trajectories that would be generated if the current velocity is ignored.

Video

trap.mov

See it in action here: IROS_predisp

Python Code

A quick python prototype was used to validate the first step. Click on the window at the y-location you want the curve to go to. Currently the implementation actually uses the velocity profile and needs to integrate (uses simple Euler method to do so). Alternatively, you could easily store the positional curve and just look up the position.

rob.py

I recently read the paper entitled A direct approach for efficiently tracking with 3D Morphable Models by Muoz et al (published in ICCV 2009). I was curious whether their technique for pre-computing some of the derivatives could extend to both multiple cameras and to a skinned mesh (as opposed to a set of basis deformations). I spent a couple days understanding, implementing, and trying to extend this idea. This blog and accompanying document is a summary of my results and relies heavily on the ideas in that paper. The pdf document, rigidtrack2 ,contains my thoughts (roughly). Most of them are concerns about speed, gradient equivalency, etc.

Here are some videos of the tracking (the left/top uses a an image-based Jacobian), and the right uses Jacobian computed in the texture space with factorization. The pose of the object in the middle is being inferred from the surrounding images. Notice that the bottom/right video has a mistrack.

Links to the other videos are here:

fact-one

fact-two

image-four

image-one

Those prefixed with “fact” use factorized; those prefixed with image use the non-factorized image Jacobian. The suffix is how many of the images are used.

The factorized Jacobian seems to perform worse, and is slightly slower, but this may be due to implementation error. It loses track in this example sequence (which has either four or one cameras), mostly due to the fast motion.

I have also uploaded the code: rigid-tracker-src.tar. It is kind of a mess, and won’t compile unless you have some of my other libraries. Check the TODO to see any limitations. But it may be useful if someone is considering implementing the same paper.

The blender sequences, .obj, and png files: RigidTrack2.tar

I have recently fallen for boost::serialization.  Super useful.  Beats making your own file format, and you get serialization of stl containers for free.  The newly added boost::property_tree also seems like it will come in handy.

The holidays are just about over.   This last weekend was pretty fun.  We went for a 13KM x-country ski (which, due to our lacking technique, just about killed us).  The only thing that kept me going through the last bit was the the thought of the ravioli we were going to hand-make afterwards.  It turned out pretty damn good.  The dough was a little thick on the first couple batches (evidenced by the fact that the recipe was supposed to make 150 ravioli and we only got like 48 out of it).  For future reference, we used the recipe from http://www.ravioliroller.com/recipes/basic.html.

And we went for a short shred today (at valley of all places).  This lasted all of 1.5 hrs, but was fun nonetheless.

Finally finished up the vertmat blog.  Check it http://www.neilbirkbeck.com/?p=1652.  Still have to fix up some things, and possibly rebuild the binaries.  I have to return the book that helped understand the derivation of the stress matrix, again for a personal note, it is the book cited by the IVM paper: Finite Element Modeling for Stress Analysis, by Robert Cook.  All that was needed from this was the understanding of the strains (and how they are used with the linear strain tetrahedron).  The strains are the partial derivatives of the displacements w.r.t x, y, and z (along with three mixed derivatives).  As the displacements are interpolated over the triangles, I derived these from the barycentric coordinates of a point in the triangle.