Skip to content

perpendicular parallel parking

Thursday, January 22, 2009

Puzzle

It is a fun (and rarely appreciated) moment when basic math and engineering can help one solve a non-technical problem.  Recently, I witnessed such an occasion where a non-standard solution was the only one that would work.  Warning: This is a geeky post, but hopefully entertaining nonetheless.

Here’s a visualization of the problem…

Namely, car 1 and car 2 were parked on a curb and car 3 (a police car) was double-parked, but at a position such that our car could not easily be parked in the desired spot.  Yes, four-wheel steering and its interesting fuzzy-logic research is now available on some  trucks and I am aware of other cars that have even used it for parallel parking, but it was not available on the car I was in.  Other alternatives like this creative parking solution also were not on hand.

Crash Scenarios

If you think about traditional ways of getting into the spot, you will inevitably have collisions because the dimensions of the various cars are just out of the range compared to what’s needed, as animated below.  Drawn as close to scale as presentation software allows, a mulit-point turn and park was also infeasible because of curb proximity.

Solution

The solution? As the title indicates, it was to approach the problem from a different angle.  In this case, that angle was perpendicular and then a multi-turn technique was applied.  As part of the entertainment promised, below is a coarse animation of the process.

Of course, this weird problem may be solved by four-wheel turning quite easily because then the car has an augmented set of physical movements.  It is also fun, but much less feasible, to imagine these weird techniques being applied to more competitive parallel parking records.

Yay for Mili and Eric.

Update: Yes, the car in question was a bit smaller than the others because it was a VW Bug.  There’s no reason that a larger vehicle couldn’t pull off the same physics feat, but I wanted to draw the operation to scale for more dramatic effect. Thanks for the gotcha, Carl!

Filed in Freeform, waste of time | Comments (3)

normalize flash playback speed using ffmpeg

Thursday, January 8, 2009

Video is a great way to demo a new system or option.  As a world, we’re moving to the availability of high-speed connections just about everywhere, but we’re not there yet.  That means that you probably want to crunch down a 30M high-quality video you just generated into something more tolerable, like 5-7M.  I’ve found that generating flash files (hey, it works for youtube, google, etc) and posting them with something like swfobject with ffmpeg is really a simple and great way to go.

First stab at ffmpeg

Check the documentation for a true reference of all ffmpeg options, but with this simple command string, I am able to crush down a 30M, 7 minute presentation to under 5M.  As you can see, the frame rate is only 2fps and the bitrate is quite low, but when the two come together, you end up with a tiny file.

ffmpeg -i talk-MIR08-trim.mov -b 100000 -r 2 talk-MIR08-trim.swf

Maintaining playback speed

One problem I’ve noticed though is that if your video doesn’t contain any audio, when you use the frame rate option, the flash player will try to take your new video and play it back at a normal rate.  For example, if you set the rate at 2fps, flash is probably going to play it back at 30fps.  The net result? You get a fun 15x playback rate.  It’s great if you meant to make your presentation at light-speed, but usually that’s not the desired effect?

Fortunately, there is a simple solution for this somewhat perplexing problem.  I scoured the flash and swfobject documentation pages for some extra parameter that could save the day, but alas there was none.  Instead, let’s think about what’s typically in a video, or more generally a multimedia document?  Both audio and video, right?  There’s the solution.

If you don’t have it, go fetch the great open-source audio application Audacity, after all, you never know when cool little tricks like this may come in handy.  With Audacity, open a new document and “Generate -> Silence…”.  Compute what the true runtime of your video should be and generate that much silence.  Next, save the file to WAV or MP3 format next to your video file.

Finding video length

Finding video length

Audacity Generate menu

Audacity Silence specification

Multiplex audio silence and video

Now, let’s jump back to ffmpeg and just add a few more arguments.  Since the audio content is silence, we can really squeeze down the number of bits required by the MPEG1-Layer 3 codec.  I found that keeping the audio clip as mono, 11.025kHz sample rate and only 48kB was about as small as it could go.  What does that look like on the command line…?

ffmpeg -i talk-MIR08-trim.mov -i silence.wav -b 100000 -r 2 -ar 11025 -ab 48000 talk-MIR08-trim.swf

Tada!  Your new file is now much smaller at a low-framerate and it preserves the normal playback speed.  Good luck and happy movie making.

Filed in code, Freeform | Comments (0)

zenphoto movie and ffmpeg tricks

Saturday, January 3, 2009

Discussion

Recently, I switched from gallery2 to zenphoto for a few reasons, which are of course biased by my experience with these packages.

  • The development tends towards straight-forward and simple approaches; this tends to break apart more as legacy things are carried forward, which I feel might be the problem with gallery
  • Nice set of ajax editing options; it was really hard for friends and family to understand how to edit captions and titles, the ajaxy part of zen took care of that
  • Easy to dump files into repository; instead of indexing everything via web interface, you can just upload files quite easily… this may also be the case for gallery, but it seemed that it had trouble if you move things around too much
  • Plug-in architecture; mentioned in point 1, it’s important to set a low barrier for plugins.  While zenphoto doesn’t have too many now, I inspected some of the existing ones and the structure and hooks seems to make sense to me without a lot of API spec reading.

All of this praise aside, I still found a few errors here and there, so this post is meant to record them both for others and myself, just in case I have to install from scratch in the future.

Fixing tab hiding error

The most aesthetically pleasing theme in the default set to me was ‘stopdesign’, so I set it as my default.  However, when hovering over different images (or even movies, which was more troublesome) the virtual tab to advance to the next or previous image was far too large.  In some cases, this prevented the shuttling of position in movies, in others, it was just weird because the image dimension was smaller than the hover-over hotspot.  These are some screenshots of firebug and what it looked like on a movie page.

Fortunately, it’s a simple change documented in these steps…

  1. Find the file… zen/themes/stopdesign/image.php
  2. Find the line… <strong style=”width:190px; height:300px;”>
  3. Change it to… <strong style=”width:190px; height:100px;”>

Once you do this, just the asthetic location of the hover-over tab (or the height of the floating ‘strong’ DOM) style changes, so you run no chances of actually breaking code.

Preventing direct access of ‘albums’ directory

One design flaw (or perhaps hosting flaw) was that users could directly access  the photos in my library without going through the zenphoto interface.  In the end this may be desirable, but I have some intelligent and well-meaning friends that may opt to scrape my site for photos, which generally isn’t what anyone wants.

Here, the change is made by creating an ‘.htaccess’ file in the albums directory of your zenphoto installation.  I chose these file extensions because they were common extensions of my media, so you can add or delete extensions as you see fit.

<Files ~ "\.(avi|GIF|JPE?G|MPG|mpg|AVI|PNG|gif|jpe?g|png)$">
        Order Deny,Allow
        Deny from all
</Files>
Options -Indexes

After adding the ‘.htaccess’ file to your album directory, anyone who tries to directly scrape will get a 403 (permission denied) message, which is generally handled correctly by zenphoto’s scripts in parent directories.

Generating thumbnails and flv videos

An appealing aspect of zenphoto is the ability to include FLV files in place and have them auto-indexed and show up in a browse mode just as regular photos.  However, to get a good thumbnail and FLV format data from different formats, you may have to transcode the original file.

First, a straight-forward command to generate FLV files in a fixed size and bitrate for zenphoto and the web.  The touch command will copy the timestamp from your movie to the generated FLV.  Although this may not be perfect, at least it will help zenphoto to better organize your new movie by date, which is the default mode.

nice ffmpeg -i $1 -s 320x240 -r 15 -b 250000 -ar 22050 -ab 48000 -y $1.flv
touch -r $1 $1.flv

Next, a quick command to also generate a JPG thumbnail from the start of the video.  Without this, your video will show up as a generic movie icon, which can make browsing them confusing.  Solution? Simply direct ffmpeg to generate a single frame from the top of the video.  Again, the second line grabs the timestamp from the original video.

nice ffmpeg -i $1 -vframes 1 -f image2 $1.jpg
touch -r $1 $1.jpg

Finding new files for indexing

Okay, so now you are happily generating videos with watermarks and thumbnails to browse.  If you’re like me you’re thinking, “how can I do this in a batch mode for a lot of videos that I just uploaded?”.  Fortunately, that answer is pretty simple, too, and just uses a bunch of standard GNU tools to accomplish the task.

  • First, combine the four lines above into a single script file. In these examples we call it ‘avilist.sh’.
  • Next execute a find command that searches for all of the raw movie formats that you’re interested in generating videos for.  The line below is how I do it on my host where the result is saved into a list of ‘new’ movies.
find zen.zavesky.org/albums/ -type f | grep -i -e '\(mpg\|AVI\)' | grep -iv jpg  | grep -iv flv | sort > avilist.new.txt
  • Next, diff the new and old list of movies to find out what really needs to be processed by your ffmpeg script.
diff avilist.new.txt avilist.txt  | grep -e '^<' | sed -e 's/^< //g' | grep -v -e '\/extra\/' > avilist.todo.txt
  • Finally, execute your ffmpeg processing script for each line of the new file.  Step back, watch the magic and run at will for new video.
cat avilist.todo.txt | xargs -i ./avilist.sh {}

Edit: While zenphoto will reorder your newly generated videos according there timestamp (the timestamp of the original movie file), there may be some differences between the file date and the EXIF date in your pictures.  For example, if you took a picture and captured movies at 10am and uploaded the data at 11am, don’t be surprised if all of the movies get stamped with the 11am time.  It’s an easy fix inside of the metadata editor of zenphoto, but it got me a couple of times.

Watermarking videos

Video watermarks can be applied when transcoding a movie with a nice hook provided for ffmpeg.  This documentation page describes the hook quite well and even gives a demonstration file.  Following this example and using the bump map generator in GIMP (as suggested), I was able to recreate the same effect very easily, as demonstrated by the image below.

From the example commands above, a quick modification to the transcode line shows how to use a watermark.

nice ffmpeg -i $1 -s 320x240 -r 15 -b 250000 -ar 22050 -ab 48000 -vhook '/usr/lib/vhook/watermark.so -f zen.zavesky.org/zp-core/watermarks/copyright-video-bump.png' -y $1.flv

These watermarks are stamped into the generated FLV with whatever image you provide on every frame.  Sure, this may be covering up the image a little bit and/or a little paranoid about people borrowing content without your permission, but it was a cool feature that you can turn on for your images so why not do it for videos as well?

Watermark example in bottom right

Watermark example in bottom right

Filed in code, Freeform | Comments (0)

fast top-k similarity computation in matlab

Saturday, December 27, 2008

When pre-computing a similarity matrix, there there is a large cost in both time and memory for computing pairwise similarity between every sample, O(N^2).  There are two main ways to slightly reduce the cost of either one of these demands…

  • Approximate Hashing: Hashing projects a set of features into a lower dimensional representation while simultaneously spreading out the samples.   Hash strategies can chosen to either find exact copies, as is common for traditional algorithms like MD5 and SHA1, or for approximate nearest-neighbor indexing, like LSH.  These algorithms provide effecient approximations (see Voronoi diagram below), but the query is issued at query time making similarity score aggregation across many samples much slower (i.e. finding a list of images similar to a set of other images can be slow).
    Approximate Voronoi diagram of a set of points. Notice the blended colors in the fuzzy boundary of the Voronoi cells. (from wikipedia, http://en.wikipedia.org/wiki/Voronoi_diagram)

    Approximate Voronoi diagram of a set of points. Notice the blended colors in the fuzzy boundary of the Voronoi cells. (http://en.wikipedia.org/wiki/Voronoi_diagram)
  • Precomputed Tables: Precomputing pair-wise similarity in some distance metric (usually L2 or simple Euclidean) is a simple way to have fast similarity look-up with some cost for additional storage of the look-up table.  While this method requires a lot of resources to save the pair-wise distances, it is only limited by the speed of your database lookup process.

In most work, resources are easier to acquire than additional processing power, so I currently prefer to use precomputed tables.  If you look closely at most search applications like whether the user really cares what the 1000000th most similar items is to the query it’s probable that they don’t.  This is the case for applications that are trying to find the closest resturant to a geographic location (using GPS to search the yellow pages) as well as most image-based search operations.  Thus, it’s likely that when computing this table, a full depth (i.e. compare every image to every other image) analysis is not necessary at query time.

Motivated by the discussion above, top-K indexing takes advantage of the fact that only the top-K (or best K results).  However, we must also be mindful of the fact that not all similarity computations may be able to be stored in memory at once.  For example, if you have 20 million items, it may not be resource efficient to store an entire set of 20 million x 20 million result in memory while you search for the top-K items.  The solution?  Break apart the large N x N matrix (here 20 million) into small chunks which can be more easily analyzed (step 1).  After similarity computation, save the sparse top-K matrix (step 2) from both the combined last matrix chunk and everything you’ve seen before (step 3).  In the image below, I illustrated the matrix in step 2 as how I save it on disk: two separate and simple lists containing the score and index of the new top-K.

Sparse top-K similarity matrix.

Sparse top-K similarity matrix.

Sure, this method is has a slight increase in time complexity because you’re constant sorting and storing new results for the top-K process, but overall it should run much faster because of the reduced memory requirements.

Also attached is an example matlab script that contains code to each of the steps defined above.  Hopefully this will help solve at least one part of the problem when indexing pair-wise similarity of a very large dataset.

Example source code: topk.tar.gz

Filed in code | Comments (0)

regular expression PHP example for non-programmers

Wednesday, December 17, 2008

When asked to help a friend make an easy way to parse a web page, I suggested using regular expressions. PHP is currently my language of choice, so in a few minutes I hacked together a well-documented (in my opinion) php script that will pull apart a table in an otherwise very messy web page.  I made a trivial attempt to obscure the source of this data, which is public domain, but included are the originally downloaded web page, the extraction script, and the output in either CSV form or another plain HTML page.

The assumption for using this script is that you can download the target page yourself (either through a crawler like curl or wget) or by the “Save as” link in your browser.  If not, solve that problem first and then come back for the script.

Helpful links (thanks Eric L.) for learning regular expressions yourself (not a comprehensive list)…

Download: Regular Expression Example

Filed in code | Comments (0)