Brett Walenz

I’m not sure why this gave me such trouble, but to build properly under Linux I couldn’t find the correct build order (with all the split out libraries now), so here’s what I used:

-lavformat -lavcodec -lavdevice -lavfilter -lavutil -lz -lm -lswscale -lSDL

Here’s hoping! 

This week is the last week of the Stanford Machine Learning course (ml-class.org), so here is my basic review of the course. Overall, the quality is quite good. The lectures are easily the most valuable part, as Andrew Ng is very organized and provides insightful explanations over the approaches and algorithms.

The homework problems use Octave, a mostly clone version of Matlab (including down to language spec), so it’s pretty easy to pick up for most math-inclined people.

The homework assignments themselves were mildly… disappointing? I’m not sure that’s the right word, but I feel they were really lacking in improving understanding of the primary concept at hand. At the start of the course, the homework assignments are concerned with implementing cost functions for linear regression and neural networks. At the end of the course, the homework assignments are concerned with implementing cost functions for k-means clustering – so it gets fairly repetitive, and doesn’t really make you aware of the steps involved with the different algorithms. Most of the supporting code that goes into the algorithms is written for you by the course team. Let’s take a look at what I mean.

In the following example, the course walks you through a collaborative filtering example to recommend movies that you might enjoy based on previous ratings. There are a number of steps that go into it:

1. Load the data
2. Normalize the ratings
3. Set initial values for X and Theta
4. Create a cost function
5. Find values of Theta that minimize the cost function
6. Use X and Theta to produce a prediction

In this assignment, the only step you do is 4. Creating a cost function, so you don’t really get a sense of what is going on unless you step through the code yourself, and it generally moves fast enough that I’m guessing most people don’t. And, for the most part, that’s my only criticism. The course does talk about, from week to week, mean normalization, regularization, etc., but you never really ‘connect the dots’ in an assignment. It’s always:

• Fill out formula
• Run magic program
• Did formula look right? If so, submit.
• If not, look at formula again.

Gripe aside, again, I really enjoyed the class. The lectures really are outstanding. And he pays a lot of attention at the start to talk about regression (linear and logistic), and neural networks – while explaining them in a clear and concise manner, avoiding a lot of ugly statistics that most people get lost in. Actually, that’s another nice part. He does a really good job of mixing data mining terms and statistics terms so that you understand there are multiple ways to describe something. That way if you go someplace else to read about it, you won’t be lost(weights vs. parameters, fitting vs. learning).

The other topics covered are SVM’s, K-means clustering, anomaly detection, and practical applications of machine learning, as well as some large scale discussions.

So I’d recommend it, with one caveat – make sure you don’t fall into the trap of “make formula go”, and understand the underlying connecting parts.

After installing OpenCV 2.2 and FFMpeg 7.1 on Ubuntu 11.04, I wasn’t able to run FFMpeg because of linker issues. Turns out the problem was my system wasn’t aware of /usr/local/lib which is where the built libraries got placed. So I ended up getting errors like:

ffmpeg: relocation error: /usr/local/lib/libavfilter.so.1: symbol av_expr_free, version LIBAVUTIL_50 not defined in file libavutil.so.50 with link time reference

You can do something fairly easy which might fix it:

$ export LD_LIBRARY_PATH=/usr/local/lib

Or you can do this:

There’s a file in /etc called ld.so.conf. This contains a path to a directory which contains all the ld conf files. In that directory there should be one called libc.conf. Put the line /usr/local/lib in there (or if it already is), then run:

$ sudo ldconfig -v

This reloads the ld cache. If the file IS NOT there, then you can create one called /etc/ld.so.conf.d/ffmpeg.conf and add the line, then rerun sudo ldconfig -v. This should point ffmpeg to the proper files.

This is a fairly specific entry – but there’s a lot of tidbits scattered about here and there that I had to get through to make this work.

The basic gist is this: I needed to play back video from a file (or stream) in a toy application I was writing for a project. I’ve been encoding stuff using x264 and ffmpeg, so I figured anything that took advantage of the same libraries would be a big help, and OpenCV has a lot of other useful algorithms.

So first, install OpenCV, Python, and wxPython. This writing works with OpenCV 2.2, Python 2.7, and wxPython 2.8. On Ubuntu 11.04.

For installing these things on Ubuntu 11.04, you can follow the guide.

So now it’s pretty straightforward. The process is:

1. Load the file through OpenCV.
2. Create a timer using wx that simulate the FPS of the video.
3. On each tick, grab the next frame from OpenCV, and display it
on the panel.

The entire code is located on my bitbucket repository, under player.py.

The only tricky bit is when you try to switch between OpenCV’s frame and a wx Bitmap:

def createBitmap(self, frame):
        # Convert the color to the space wx works in. 
        cv.CvtColor(frame, frame, cv.CV_BGR2RGB)
            
        Img = wx.EmptyImage(frame.width, frame.height)
        # Unsure why this works, assuming frame.tostring() places it in a well-known format
        Img.SetData(frame.tostring())
        
        return wx.BitmapFromImage(Img)

Also I found the wxPython documentation fairly out of date, and the OpenCV Python interface has changed a lot, so be wary of reading things that don’t tell you what version it’s for.

This is mostly just a reference post for me to assemble thoughts on what I’ve read about video encoding over the past couple of days. It might not make much sense.

First, a good starting point is the book H.264 – Advanced Video Compression Standard by Iain E. Richardson. It’s where I’ve picked up most of the relevant information. The concepts and technologies are pretty involved with a lot of terminology, so the book was helpful in that regard. But if you read Chapter 3, Video Coding Concepts, it’s a lot easier to understand H.264 and V8.

So how does a video stream go from raw to compressed? It’s actually a fairly interesting process. In most cases, it goes something like this (although implementations/specs may vary):

1. An input video frame, F, is processed in macroblocks, usually 16 x 16 pixel area of the frame.

2. A motion estimation function finds a 16 x 16 pixel region in the reference frame (usually the previous frame encoded) that most closely matches the current macroblock. The offset between the previous frame’s position and current is calculated – this information helps the compression algorithm in the next step and enables compression to continue in the cases where the camera is panning. This offset is called the motion vector.

3. Using the motion vector, a prediction is generated which basically states what the current frame might look like based on the previous frame and motion vector.

4. The prediction is subtracted from the current macroblock and produces a residual macroblock. This residual macroblock represents the regions that have changed since the previous frame, taking into account motion of the camera itself. Therefore, we’ve now reduced transmission of an entire frames data into only the residual data required to represent change.

5. Now, the residual macroblock undergoes a transformation to reduce the information contents further. This transformation is typically in the form of a Discrete Cosine Transformation, which basically takes a macroblock and translates the values into coefficients of a matrix. This lets the algorithm chop off some of the coefficients since we can fairly closely reconstruct the matrix from a majority of the coefficients. Remember, we are working with small pixel regions so being “close enough” is a good trade-off.

6. The coefficients are quantized. Quantization means the removal (or indexing) of unnecessary or repetitive data. In some cases, this can mean a lookup table that is shared by the encoder or decoder for common coefficient sequences.

7. These quantized coefficients are reordered. Since it’s likely that there are a large number of zero-valued coefficients, special encoding is used to compress these blocks and only represent the non-zero coefficients, called run-level encoding.

8. The coefficients, motion vector and all other header information required for the decoder to recreate the original frames is entropy encoded to create a bitstream. Examples of entropy encoding are Huffman codes or arithmetic coding techniques.

A reverse process is used by the decoder to reproduce the frame/macroblock.

So you want to use Eclipse, Maven, and not have to duplicate Checkstyle, PMD, Findbugs, and all that jazz? Good luck. It’s *almost* black magic. Random eclipse update sites. Random projects. Clean, Install, hope it runs. So without further adieu, here is the list I use to reliably get my workspace up and running.

First, a note on plugins. There are three required plugins that most people get confused about.

1. m2eclipse – provides base maven-eclipse integration
2. m2eclipse-extras – provides integration for web tools platform
3. m2eclipse-extensions – provides integration for checkstyle

@Ajax.ActionLink giving you a brand new page? Wiping away your existing page, when all you wanted to do was update a div?

You probably just forgot javascript, or you have them included in the wrong order.

Try this in your script definition:

This post is mostly link spam for my future reference. It could also be called “Things you should know if you are just entering the .NET world”. I’ve just started playing around with things, and it’s at least interesting so far. I wanted to build a simple web application, so I ran through the MvcMusicStore tutorial and was able to following along pretty easily.

.NET and Java EE share a lot in common, unfortunately it’s enough that when something doesn’t work things get really confusing. Not only that, but my common resort of “Consult Google” doesn’t work as well for API documentation. So with that said, here’s the links to the API docs! Never lose these…

http://msdn.microsoft.com/en-us/library

Secondly, I found the documentation for the MVC Model Binding to be very… shortcoming. Maybe I’m just missing it. But this link helped tie things together for me:

http://marcomagdy.com/2009/09/03/asp-net-mvc-model-binding-form-inputs-to-action-parameters/

Lastly, this post was a great help on how to nest a collections and add new items to a collection from a form:

http://jarrettmeyer.com/post/2995732471/nested-collection-models-in-asp-net-mvc-3

Although things didn’t work out properly, I had to do:


@foreach (var item in Model.Exercises)
{
@Html.EditorFor(model => item, "Exercise")
}


Instead of:

@Html.EditorFor(model => model.Exercises)


No clue why.

Just a short note on what I’ve been working on lately. First, I put the public version of my master’s thesis up on https://bitbucket.org/bwalenz/sequencer-thesis. You can browse all the minute details of web crawling with Nutch, parsing documents using OpenNLP, and writing results to a database. I used GWT for visualization purposes, and had to a bunch of wiring to transfer entities (as in named entities from text) from the database to the user interface.

Some good examples are:

Extracting code from text using OpenNLP and a specialized news article extraction algorithm:

EntityExtractor

Executing a Nutch crawl from a Windows machine using Cygwin:

NutchProcess

On the flip side, here’s some code sending these extracted entities to GWT’s client javascript code. Uncommented (here there be dragons):

AreaChartServlet

On a completely unrelated note, I’ve included a JavaScript implementation of the GEM graph layout algorithm at: https://bitbucket.org/bwalenz/algorithms. If I get more time I’ll type up the explanation, it’s pretty neat.

An interval tree is a data structure for efficiently searching intervals. Surprise! An interval can be a continuous line segment, a time frame, etc. It is generally augmented with a secondary structure in each interval node to allow for windowing queries. A good example is quickly finding a rectangular region in a GIS application. I couldn’t find a really straightforward explanation of the algorithm. The Wikipedia entry, while correct, was not well-explained from an implementation point of view. Most of this information comes from the great book Computational Geometry by Berg et. al.

There are different types of interval trees. The CLRS Introduction to Algorithms book uses a red-black tree as the starting point and outlines construction and querying for intervals. The approach outlined below is a centered interval tree, which uses a binary search tree where each subtree is also a centered interval tree. The value of each subtree is the median (left or right) endpoint of the intervals in the subtree.

An interval, at it’s barest, has a left and right endpoint. That’s it. Let’s look at how we’d construct an interval tree given a set of intervals. I’ll use pseudo-Java since I think it’s the friendliest to read.

CenteredIntervalTree constructIntervalTree(Set<Interval> intervals) {
    if intervals.isEmpty()
       return leaf;
    Compute xMid = Median of interval endpoints
    Compute iMid = the set of all intervals
                   where the left endpoint is <= xMid
                   and the right endpoint is >= xMid
    Compute iMidLeft = a copy of the set iMid sorted by left endpoint
    Compute iMidRight = a copy of the set iMid sorted by right endpoint
    Store xMid, iMidLeft, and iMidRight at the current node.
    Compute iLeft = a set of all intervals where the RIGHT endpoint is < xMid
    Compute iRight = a set of all intervals where the LEFT endpoint is > xMid
    leftSubTree = constructIntervalTree(iLeft)
    rightSubTree = constructIntervalTree(iRight)
    return currentTree;
}

The construction algorithms creates a roughly-balanced search tree by taking the median of the (right) endpoints and setting that as the root of the current tree. The data stored at each node is the set of intervals that contain that endpoint. To see how this construction algorithm works, assume we have the following set of intervals: {(1, 10), (17, 29), (31, 38), (30, 40), (15, 24)}. The resulting interval tree will appear as in the image below. The running time for the construction algorithm is O(n log n). For the proof, see Lemma 10.3 in Computation Geometry.

So how do we query this? The answer should be obvious when looking at the image. The only trick is when you wish to query for all intervals intersecting another interval.

To query for a given point (say, to find all intervals containing the value 35 in the example), the following algorithm can be used:

Set<Interval> queryIntervalTree(tree, value) {
   if (tree does not have children)
      return currentSet;
   if (value < xMid) {
      for (Interval interval : iMidLeft) {
         if (interval.contains(value))
            currentSet.add(interval);
         else
            break; //sorted so that nothing past this will contain value
      }
      currentSet.addAll(queryIntervalTree(tree.leftSubTree, value));
   } else {
       /* Repeat iteration from above but with iMidRight instead of iMidLeft;
      currentSet.addAll(queryIntervalTree(tree.rightSubTree, value));
   }
}

The query time is a very fast O(log n + k), where k is the number of intervals that are stored at a node. But what if we wanted to search for an interval? This is fairly easy, but can be difficult to express: We want to start at the left endpoint, and grab all intervals until we reach the right endpoint intersection. From an implementation perspective, it can be hard to do this correctly. You can’t just call queryIntervalTree for the left and right endpoint values, you might miss intervals that are completely enclosed by the passed in interval. So, when implementing, it might be smart to replace some of the recursion with iteration, or at least keep track of the parent nodes for a centered interval tree. This will make walking the tree much easier.