A week of scripting

Before I launch into today’s rendition of “How I Spent A Week Doing Something Essential To My Research That Someone In Industry Could Have Done In 5 Minutes”, I wanted to remark on how, lately, this post has been seeing a lot of traffic. It was interesting re-reading it and all the comments that followed. It was also evident that mcoville and I were talking past one another. Though my views have not changed, my desire to enter into such “discussions” most certainly has 😛

Particle Swarm Optimization

Does anyone know anything about mathematical optimization? Sparing folks from gory details, it’s basically the super-complicated analog to “use calculus to find the maximum value of f(x)“. Remember that from high school / college? Given a function, you needed to take its derivative, set it equal to 0, and solve for x, which should give you either the maximum or minimum of the function.

Optimization is like that. Except instead of f(x), we have something like f(x,y,z…,a,b,c,d,e,f,g,h) and we can’t actually take its derivative. Oh, and we usually don’t even have an explicit equation for f. But we still want to know: what is the largest or smallest value (or set of values) that it takes? One such method to arrive at a close answer is particle swarm optimization (PSO).

The search space is under attack!

Let me just say: every time I hear about PSO, I immediately think ZERG SWARM. And to be perfectly frank, it’s kind of like that, so I’m just going to run with that analogy.

As I’m a TA this semester, and my fellow TA was busy writing a paper and studying for an exam, I was in charge of running the lab this past Friday. And the lab was on PSO. Which was curious because I’d never once used or even studied PSO before.

I set out to figure out how the f PSO even worked. Turns out, it’s not all that complicated (one of the advantages of using PSO over other optimization methods): you have a bunch of particles (zerg) that “swarm” over your search space. Obviously the more particles/zerg you use, the better your results will be, but the more intensive your calculations become. The particles/zerg have a certain degree of randomness: they will converge upon areas of the space that are “better” (analogy: we found a protoss expansion!) but still allow for some random movement in case there’s an even “better” area just around the corner (analogy: holy crap, the protoss’ main base!)

In fact, PSO draws its ultimate inspiration from watching flocks of birds. Check this out:


That’s pretty much PSO in action. The nitty-gritty is that you have particles with position, velocity, and a certain amount of independence (“drunkenness”, I call it) and social cognition (“sheepness”, I call it), all of which work together to determine where a single particle will move to reveal properties of the area it’s searching. If you do it right, PSO can reveal the maximum/minimum you’re looking for in a fraction of the time it would take to do an exhaustive search.

If you’re at all interested, I posted the Python module I wrote for the occasion on github. “lab5.py” is the one you’ll have to fill in; “answer.py” contains the completed assignment. The PDF instructions tell you everything you’ll need to know. NOTE: You will need NumPy and Matplotlib installed in order to run this example.

Needless to say, I learned a lot about PSO, and optimization in general. Like how PSO really isn’t ideal for revealing mystery images, but it sure makes for a fun, gimmicky introduction to the overall idea.

HTML5 Particles

I know this seems like a jarring segue, but the PSO implementation inspired me to do a little exercise in HTML5 canvas work to prime myself for the real HTML5 canvas work I needed to do for my research: figure out how to add, remove, and resize semi-transparent boxes on an actively-playing video in the browser, and then save the coordinates of these boxes in a database.

So, I created a particle simulation in which each particle has a certain gravitational attraction to all the other particles in the simulation. Seems straightforward enough, right? Eventually you should get a little ball of swarming particles, right?

WRONG!

Well, that was the initial implementation. But I wanted to spice things up a bit: wouldn’t it be cool, thought I, if there was some critical mass threshold at which the particles would suddenly explode outward? Sort of like what happens just before and during a supernova: matter is compressed and compressed and compressed, and eventually the repulsive forces overwhelm the gravitational ones, and everything goes KABOOM!

Turns out, this was pretty tricky to code up. It was particularly tricky to code up efficiently. The original task of simulating n particles requires O(n2) computations, as you need to compute the pairwise distance between particles to determine how the gravity from each particle affects the trajectories of all the others. Through a lot of thinking and whiteboard-ing, I settled on a simulation that was O(n2 + n).

Here is the code I posted in my github repository. Feel free to check it out, fork it, tweak it, maybe make it a bit more efficient, though I don’t think you can optimize it much further than that. Also, if you don’t really care about the code and just want to see the simulation in action, I created a public Dropbox link for that: it’s rather mesmerizing. I do eventually want to put in HTML buttons and switches so you can actively modulate things like number of particles, gravitational attraction, and the “critical” quantities required for an explosion to happen.

I also wanted to add some seizure-inducing features like having each individual particle flicker its color randomly and independently from all the other particles, but I figure I’ll wait on that one for the moment.

Annnnnnnnd Research

Which leads me, inexorably, to my research: trying to get an HTML5 canvas into Drupal. While this has, to a very limited extent, already been done before, my canvas requires quite a bit more functionality. I need to be able to play a video in a web browser, and as the video is playing, allow users to draw boxes around regions of interest in the video, effectively annotating the videos so I know which regions to pay attention to when I analyze the video as part of my research.

[Not?] Surprisingly, this is rather difficult to accomplish. First, a whole framework needs to built around an HTML5 canvas for painting the frames of the video and the boxes (in that very order!). Then, one needs to add more JavaScript for both adding and removing boxes: the user may want to highlight four distinct areas of interest on the video, but then decide Box 3 is superfluous and remove it. Finally, the user needs to be able to save this annotated video in such a way that I can retrieve the coordinates of the boxes later.

And that doesn’t even touch on the incredibly nuanced and noisome issue of transcoding the video into the correct format to use in an HTML5 canvas. Holy crap is that annoying.

So anyway. As of today, I have the proof-of-concept up and running in a standalone script, which you can check out on github. The next step–which, arguably, may be even harder–is to convert that proof of concept into a viable Drupal module. Not exactly sure how that’s going to pan out yet.

Return of the Intrepid Traveler

All this is kind of in a rush to be completed by the end of this week, when I depart for eight long days to the country of Morocco! Yes folks, I am going to visit my sister for the entirety of spring break. I’ll be off the grid in the purest sense; I’m hoping to maintain occasional contact with the outside world but only in response to the most pressing matters…mainly that of maintaining contact with The Lady 🙂 I’m looking at which passwords I can reset for my temporary overseas stay, and then reset again upon my return home. I would also like to maintain one ready SSH server for a SOCKS-proxy hookup as a way to maintain some semblance of privacy. But I’ll need to make sure that server doesn’t have anything sensitive on it. What an ordeal!

But yes, this is likely my final update here before I land on my fourth continent. I hope everyone has a lovely next few weeks, and a very happy St Patrick’s Day!

I just found this incredibly amusing. Probably because I relate to the awkward penguin.

Advertisements

About Shannon Quinn

Oh hai!
This entry was posted in Academics, Graduate School, lolcat, Mathematics, Programming, The Lady, Travel and tagged , , , , , , , , , , , , , , , , , , , , , , , , , . Bookmark the permalink.

One Response to A week of scripting

  1. eksith says:

    We had to use annotated video on a project a long time ago and we managed to do it by placing a layer over the playing video and every time the user clicked on it, it would pause the video allowing the user to draw/move a box of arbritary size. Then the video can be played again, until the user pauses it to remove the box or add more boxes on that layer.

    The boxes would get recorded on a timeline of sorts (a bit like a seismograph tracking click/drag/move events, but basically a multidimensional array with width, height, x,y, text and color) that will be played on top of the video. We used to joke that it’s like a silent movie with the picture playing by itself while the player piano goes on its own to match the action.

    Originally this was done with some C++ mess, but then it was moved in its entirety to Shockwave (yuck, remember those?) and the browser until finally, it was separated to a plain Flash swf and an XML file with timestamp, x,y coords, colors etc… of the boxes separately.

    I imagine you can do something very similar by pushing mouse actions to an array along with the video timecode and overlaying them on playback. The nice thing about HTML5 is that you don’t need separate browser technologies to do this anymore.

    Also, I found explorer canvas handy when trying to manhandle IE into doing canvas work… that it technically was supposed to be doing by default now anyway (AARRGH MS!!).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s