30 Dec 2007

I wanted to try making one of those movie montage things I wrote about earlier into a nice poster that could be hung on a wall. Now, I prefer a Spartan environment whenever possible, so I really did not want to have my own poster. No decorations for me, please. I just wanted to make one. My solution? Make one for my sister, who has lots of junk and would enjoy having one. Her favorite movie is Pirates of the Caribbean, so I used this movie, which she conveniently already had on DVD.

As before, I used mplayer to rip all of the frames I needed. To get a poster-quality version I would need better resolution. To do this, I changed the frame output image size to 160x90 (100 times bigger than before).

[...] framestep=30,scale=160:90 [...]

Next, I used my own montage script to put these frames together. My script took about 2 minutes to put together one of these larger montages. Finally, I used the GIMP to add a black border and simple title at the top. Since I don't have any more than 512MB of memory on my computers, I actually had to scale the image down to 1/4 of its original size to do this. Before scaling, the GIMP was spending hours just adding the border because it was thrashing the hard drive. It needed about 2G of memory and it was using the hard drive to get it.

I took my giant image to FedEx Kinko's where they printed it to a 2'x2' poster for 30 bucks. Here are the results, taken using my sister's crappy Kodak camera (never buy Kodak digital cameras, as they all suck!). To help see what is going on, I provided a glare version and a non-glare version. Each shows different details.

Here is the normal version from before for comparison.

26 Dec 2007

I had written a previous post called Movie DNA where I described a simple way of distilling an entire movie down to a single frame. It involved the use of two tools, with no intermediate code or software in the middle to glue things together.

The first tool, mplayer was used to dump all of the frames we needed. This took about the running length of the movie to do, which wasn't so bad. There may be a way to speed this up by giving mplayer some extra hints. I have not yet figured this part out.

The real time cost was in ImageMagick's montage tool, which made the final montage out of the images. This took between 6 and 10 hours to do this, depending on the length of the movie. The process seemed to be non-linear for some reason, with long movies taking unproportionally longer to process (One could always dig around the montage source to find out why). I knew there had to be a way that this could be improved!

Well, I wrote a Perl script last night, dubbed gdmontage to speed up the montage process. It was even faster than I thought it would be, taking only 12 seconds on the same machine as before. It uses the GD Graphics Library via Perl's GD module, which you would need to install to use this. It also uses the Term::ProgressBar, if it's available, to provide a progress bar and ETA.

Like the original montage program, the script recognizes file globs, so you can provide the files through a glob in order to avoid the limits on command line arguments.

$ ./gdmontage.pl "frames/*"

It is a bit unfair to call my code a "faster montage" because it only covers a tiny subset of the original montage. It makes some big assumptions in order to be faster; specifically, it assumes that every image is the same size. The original montage must look at every image before it even starts in order to determine the dimensions and placement of the final image.

It is also geared towards the Cinema Redux thing, doing only 60 images per row. This can be changed internally (no command line arguments for this) by adjusting the parameters at the top of the script. The script could probably be easily expanded to include most of the features of ImageMagick's montage, but I am sure this Perl script would be much faster when it comes to creating large montage's. (Why is montage so slow?)

Anyway, you can get the script here: gdmontage.pl (GPLv3)

19 Dec 2007

Original image courtesy NASA.

While studying for my digital image processing final exam yesterday, I came back across unsharp masking. When I first saw this, I thought it was really neat. This time around, I took the hands-on approach and tried it myself in Octave. It has been used by the publishing and printing industry for years.

Unsharp masking is a method of sharpening an image. The idea is this,

1. Blur the original image.
2. Subtract the blurred image from the original, creating a mask.
3. Add the mask to the original image.

Here is an example using a 1-dimensional signal. I blurred the signal with a 1x5 averaging filter -- [1 1 1 1 1] * 1/5. Then I subtracted the blurred signal from the original to create a mask. Finally, I added the unsharp mask to the original signal. For images, we do this in 2-dimensions, as an image is simply a 2-dimensional signal.

When it comes to image processing, we can create the mask in one easy step! This is done by performing a 2-dimensional convolution with a Laplacian kernel. It does steps 1 and 2 at the same time. This is the Laplacian I used in the example at the beginning,

So, to do it in Octave, this is all you need,

octave> i = imread("moon.png");
octave> m = conv2(i, [0 -1 0; -1 4 -1; 0 -1 0], "same");
octave> imwrite("moon-sharp.png", i + 2 * uint8(m))

i is the image and m is the mask. The mask created in step 2 looks like this,

You could take the above Octave code and drop it into a little she-bang script to create a simple image sharpening program. I leave this as an exercise for the reader.

14 Dec 2007

Download: hashtab.tar.gz (3.9KB)

I needed a hash table written in C for a project I was working on and I didn't like any the free hash table code that was out there. Plus, I have NIH syndrome and I really wanted to write my own for fun. My goal was to make it extremely generic, so that it would work with any data of any size. A small front end could be placed on top to make it work cleanly for strings (no need to pass the length of the data).

It uses open hashing, with linked lists to store the data. The only penalty from collisions is a slightly slower lookup. This also is what alows the variable entry sizes. I could definitely fix up a few things to make it more efficient. The default hash function uses modulus, which is quite expensive.

It works just fine with all my tests so far, so it suits my needs for the project. The code includes a demo of the hash table (main.c). If you want to read about some better hashing functions and use one with this hash table, take a look at A Hash Function for Hash Table Lookup.

11 Dec 2007

Brendan Dawes has this interesting idea he calls Cinema Redux. A entire film is distilled down to a single image. You take one frame from each second of the movie, shrink that frame down to 8x6 pixels, then line them up in a montage with 60 frames per row. Each row then represents one minute of film. There are 8 examples on his website.

I was interested in trying this for myself, but I couldn't find any of his code, which he had written in Java, to do it myself. Then it hit me: I really don't need to write anything to do this! Here is how you can make your own using only two tools: mplayer and ImageMagick.

Originally I thought that I may need to write a small Perl script to glue these two things together, but found, after digging though man pages, that this was completely unnecessary. There are two steps involved and each tool does one step: grab all of the frames, and second, make a montage out of those frames. Grabbing the frames is one call to mplayer,

mplayer -vo jpeg:outdir=frames -ao dummy -vf framestep=30,scale=8:6 \
        video_file

What we are doing here is dumping every 30th frame (assuming 30 frames-per-second) into a directory named frames. These images will be named by consecutive 8-digit numbers. These frames are also resized down to 8x6 pixels. If you are converting a video with a different aspect ratio, such as a wide-screen movie without letter-boxing, you will need to adjust this. A wide-screen film would be 16x9.

Next, we glue these frames together with ImageMagick,

montage -geometry +0+0 -background black -tile 60x "frames/*jpg" \
        montage.jpg

This will create the montage in the file montage.jpg . There is something important to note here. See how the file glob is quoted so that the shell will not expand it? Thats because listing 7000 frames pushes the limits of the system in passing command line arguments. ImageMagick knows about file globs and will do this internally.

And that's it! I put these together into a handy shell script that will also remove the frames after the montage has been successfully created. The process takes between 6 and 12 hours, depending on the length of the movie. It takes the movie running time to produce all the frames file, then it spends the rest of the time creating the montage, which is disappointingly slow. (Maybe I could write a Perl script that does it faster?) The script will create a montage out of just about any video you throw at it, thanks to mplayer. Example usage for DVDs,

$ ./cinrdx.sh dvd://

I did it on three movies so far: Gladiator, Tron, and The Matrix. I did it to Tron and The Matrix because I wanted to see if these movies have a dominant color scheme.

Gladiator

Tron

The Matrix

To inspect the coloring of these films, I took a hue histogram. Tron is very obvious: lots of blues and cyans dominate,

I was expecting to see a lot of green show up in The Matrix, but was a little bit disappointed,

To get these histograms, I loaded the images into GNU Octave, converted it to HSV so that the red channel is really the hue channel. Then I had the GIMP make the histograms by providing the histogram of the "red" (read hue) channel. I dropped an HSV color bar below with some image editing.

octave> m = imread("movie.jpg");
octave> [x map] = rgb2ind(m);
octave> map = rgb2hsv(map);
octave> imwrite("movie-hsv.jpg", x, map);

See if you can find some really interesting things to do with this.

05 Dec 2007

Notice: This software is not affiliated with the South Park Zone nor South Park. In fact, this bypasses all of the South Park Zone's advertising, so they may not like it. I have do not have anyone's approval, nor do I know about any of the legal implications of this tool. Use at your own risk.

Get the program: spd.pl (3.8KB) GPLv3
Requires Perl and GNU wget

This was an afternoon project the other day. I found out about a website called the South Park Zone. This website has information on where to fetch South Park episodes from different hosts, such as MySpace and YouTube. These videos are stored in the Flash video format. You see, I don't have the proprietary Flash software installed and the free versions aren't quite ready for use yet. I use other means of watching videos on sites like YouTube. This means that I normally have to either use a tool to find the .flv file or search through the site's HTML code manually.

In this case, I couldn't find an existing tool that could grab the videos pointed to by the South Park Zone. I was able to find it manually, but trying to watch several videos takes a bit of digging. Anyway, if I really want to become a hacker sometime (I feel I am not yet worthy of this name), what do I do? Well, I write a program to do it for me!

I stretched my Perl legs a bit and wrote a script that will grab the video location from the South Park Zone and download the video. The only thing you need other than Perl is GNU wget. This is the program that does all the hard work. My Perl script just scans the HTML and XML for the data.

Here is an example session,

$ spd 807
Getting mirror number ... 
Getting episode URL ...
Downloading episode: The Jeffersons (125)
--20:21:21--  http://content.movies.myspace.com/0008289/24/25/828935242.flv
           => `South Park - 0807 The Jeffersons.flv'
Resolving content.movies.myspace.com... 204.16.34.216
Connecting to content.movies.myspace.com|204.16.34.216|:80... connected.
HTTP request sent, awaiting response... 200 OK
Length: 43,350,604 (41M) [application/octet-stream]

100%[====================================>] 43,350,604   890.43K/s    ETA 00:00

20:22:14 (823.14 KB/s) - `South Park - 0807 The Jeffersons.flv' saved [43350604/43350604]

The program accepts episode numbers, episode ranges, and search terms. For example, assuming you have installed the program and removed the .pl extension, this will download season 2, episode 3 and season 10, episode 10,

$ spd 203 1010

You can also provide a range of episodes with a dash,

$ spd 405-410

With that command, season 4, episodes 5 through 10 will be fetched. The range will not work across seasons! This is because I didn't see a convenient way to find out how many episodes were in each season. Right now the tool should be fine until season 100 (3 digit seasons) or South Park Zone goes away. It knows nothing about South Park: it only fetches the data on request.

And finally, one of the coolest parts, it will do searches for you too. Right now, it just grabs the first search result, but this seems to work pretty well. For example, this grabs the famous Make Love, Not Warcraft episode,

$ spd warcraft

I have used it a bit myself, but there may still be bugs. It also assumes that all of these videos are .flv files, but the South Park Zone is prepared for these things to be in any format. If its popular enough, perhaps I will turn it into a "project" and version it. It could also use a better front end for parsing option flags. Perhaps a quiet -q flag,

$ spd -q 506-510 708 710