Lane Kolbly's Blog

This is the end…

Hold your breath, and count to ten…

Feel the Earth move, and then… hear my heart burst again….

For this is the end.

Well, I had to pick some lyrics to accompany this post.

The rumors are true – I’m wrapping up High School in the next few weeks. More pertinent to this post, I’m wrapping up my ACP class. I’m supposed to do a reflection on it.

To be honest, when I signed up for the class I wasn’t sure what to expect. I didn’t even expect to end up in the class, but that’s what you get I guess. I know for a fact that what it became is not what I expected.

The question is, of course, what did it become? It became a nice hour and a half at the end of the day dedicated to programming whatever project I need to work on.

Speaking of projects, I come to announce Lyst, which will roll out on shelves one week from tomorrow. I’ve been using my ACP period to work on Lyst, to good advantage. Now I may actually get a project done.

Speaking of not getting projects done, I turned over the source code for Workflow and never heard back. That was my other major project.

And so I close, realizing that perhaps the ending has not yet been written.

I haven’t posted in a while, I know. But I’ve been buried under Lyst.

Speaking of which, if you want to help out (and get a spot in the credits, and a portion of the profits), then check out:

http://pillow.rscheme.org/lyst-help/

Thanks!

Lane

(P.S.: As for flying, there’s a significant chance I may solo this week. Details coming soon!)

They’re a wonderful thing, no?

It’s not that I have anything against them. They’re a wonderful invention (not that I’d know), but the advertising for them can get a little bit annoying…

Recently I got a text from a 512 number that said nothing but (to pseudo-quote) “you should go to friend-meet.com. I have pics on there.”

I happen to live in the 512 area code, so it could be someone I know. On a (hopefully) unrelated note, I’m going to prom this year. I haven’t checked to see if she actually has pics on there, or if it’s just coincidentally random advertising. I’m not over 18, so I’m not allowed to check… because that would be mis-representing myself using a computer. Which is illegal.

Anyway… Lyst! And HDR! (and airplanes, but I don’t have anything to say about that other than they’re awesome)

I was messing around with HDR some more, and found a pretty cool set of tools out there that does these things for you. Here’s a picture that was made using pfstools:

Bonus points if you can identify what the picture is of, and where it was taken. Yes, I’m aware it’s not the best test image for HDR, but it’s what I was playing with because I didn’t feel like pulling the other pictures off of my camera.

I used the reinhard02 algorithm. The cool thing is that it removed the yellow tint from the image – the wall in the background is allegedly white. It was halogen yellow in the source image. The sad thing is that reinhard only does tone mapping, so I still need to go through the effort of creating HDR imagery. Perhaps combining this with my Python HDR script could give some nice results.

(Quick side note about pictures: John McAfee, creator of the infamous McAfee virus software, was caught a few months ago in Brazil when the FBI found his location using the EXIF geolocation tags in a picture taken of him by a magazine reporter. Moral of the story: If you’re on the lam, don’t do interviews)

Speaking of HDR and such stuff, Lyst is coming along quite nicely. This past week (sorry for not posting earlier, by the way) I implemented a perspective matrix transform to map subslides onto slides. A picture is worth a thousand words:

Note that the image of the room is mapped onto the computer monitor – the monitor wasn’t actually showing that image when I took the picture. The new Lyst code makes it so that I can specify what four points make up the corners of the computer monitor. Then, I tell it to create a new “slide” and map it onto that area. This lets me implement all of the computer monitors in the game without any specialized code.

In other words, most of the Lyst engine is complete. However, the Lyst data still largely needs to be made.

For clarification: There are two Lyst projects. One is the Lyst game, which is a version of Myst made for the LASA High School (“LASA Myst”). The other is the Lyst engine, which will be the game engine that the Lyst game runs on (“Lane’s Myst”). Both are closed source, for the time being, but open for recommendations.

3d stereoscopic views have been cut from Lyst. I was unable to find a second projector, and I don’t think I have time even if I did have a second projector to develop the system enough to film and code everything before the end of the school year.

If you have recommendations/suggestions/ideas for the Lyst game, please Contact Me.

This post is part of a series I intend to write this weekend which fully explain most aspects of some of my bigger projects, so hopefully they make a little bit more sense than my normal posts.

The flip side is that they’ll be a lot more technical.

Introduction

I’m a member of one club at school: Robotics. Every year we compete in FIRST Robotics Competition, which is aimed at high schoolers building autonomous/teleoperated robots. This year the challenge is to throw frisbees into rectangular goals at each end of the playing field.

So we decided that we’d build a program that could use the camera feed from the robot to automatically aim the robot at the target. This is made easier by the fact that the targets are lines in retroreflective tape, and we have a high-power LED array pointing at the tape. After we monkeyed with the camera’s gain settings, we got a relatively clear image:

Which we have to convert to a couple of different variables, such as bounding box, angle from center, and distance from the target center line, which I’ll represent graphically as:

Robot Control System Architecture

As with most projects, there’s multiple different layers of architecture involved. The topmost is how this program fits into the rest of the robot control system.

The robot control system consists of an IP camera, mounted on the robot, a cRIO, which is a FPGA-based computing device, also mounted on the robot, both of which are connected to a wireless access point which we connect to with the drive station computer to control the robot.

My program sits on the drive station computer as a (C++) server daemon process separate from the rest of the drive station software. The daemon talks directly to the IP camera to fetch the imaging feed, and it presents a network API which the cRIO connects to in order to receive the processed imagery data.

Server Daemon Architecture

The next architecture layer is how the server daemon is internally laid out. Internally there are three threads, each dedicated to one of the main tasks. The three main tasks are:

• “networking”: This thread pulls the latest imagery data from the camera, and saves it to disk. This thread is freewheeling, pulling data as fast as is possible in order to keep the latest imagery on hand.
• “processing”: This thread processes the images gathered by the previous thread. When this thread is ready to process the next image, it locks on a mutex which is normally held when the networking thread is currently writing data to the file. When networking starts pulling the next image, it momentarily unlocks the mutex to allow processing to copy the file to it’s internal storage.
• “server”: This thread manages the server API. Clients connect to the sockets generated in this thread. Note that this thread can’t do the same mutex trick as networking, because it is not allowed to block, but it does do a similar trick by trying the mutex.

The Processing Pipeline

Now, the part you’ve all been waiting for. How we convert from the first image to the second image.

The first thing we do is condition the image. In this step we resize to a 640×480 image, convert to grayscale, apply a Gaussian blur, and then threshold the image.

The next step is to find the edges. This is done with the OpenCV Canny edge detector, which returns us an image with the edges highlighted. We then take this image and turn it into a “point cloud”: All of the pixels which are lit (i.e. are an edge) are added to a giant list of points which consists of the point cloud.

Then what we do is split this master point cloud into smaller point clouds, based on their relative groupings in the image. In the future this step and the one before it can be merged for performance optimization, but for now they remain two separate steps.

Actually, they remain three separate steps. The splitting of the master point cloud takes place in two steps: Creating new point clouds, and then merging clouds that are close together. Creating new point clouds is done by looping through every point, and determining if it is near one of the already defined point clouds. If it is, then the point is added to said point cloud. If not, then a new point cloud is created which contains that one point.

After merging the clouds nearby, we are left with a series of point clouds, which we apply the convex hull operator to. The convex hulling operation removes over 95% of the points we have to process in later steps. The points returned by this operation are rendered as small purple circles in the above image.

Now it’s just a matter of converting the point cloud into 2D quadrangles, followed closely by 3D rectangles. The first step is done by finding the four corners, which I implement by searching through the convex hull of the point cloud and finding the four vertices with angles closest to 90 degrees. These vertices are marked as big purple circles.

These four corners make a bounding box of the rectangle, which is marked with the green square.

These four points are also fed into the rectangle3D framework, which processes the points to form a best guess for the matching 3D rectangle.

Rectangle3D Solver

This solver is deceptively simple. One could do high level math to figure out the reverse affine transformation to figure out the best match.

Or one could do an “iterative solver”.

I first determine that the four known 2D points define lines extending from the camera to infinity through the 2D point, at some set plane distance. I used 1 as the backplane distance, but as long as the FOV is taken into account correctly these lines can be defined.

The next step was to define a function that found the “squareness” of some 3D rectangle. That is, how closely the angles four corners match 90 degrees (RMS).

Then we start with some arbitrary distances for guesses for the initial points of the rectangle. Note that a distance along one of the lines defines a point in three space, so four distances along four lines defines a quadrangle.

For each corner, we try moving it some small distance away from the camera, check to see if the solution becomes “more square”, then move it a small distance closer to the camera, and choose the better solution. Then we repeat.

I realize that this is not the best way to do it, but with properly tuned variables (i.e. how small is “small”), and a well-defined breakpoint, it exits within a short period of time.

Once we have four points which define a rectangle in three-space, it becomes trivial to do calculations such as center-line distance, etc.

And that is how I convert from the top image to the bottom image.

Possible Future Work

In the future, I would like to implement a little bit more user flexibility. Right now, most of everything is hard coded. I’d like to add support for multiple cameras, multiple different clients, each with it’s own configuration. Some will be looking for rectangles, some for triangles, some for circles, etc. I’m thinking that each camera pipeline can have it’s own fetch/processing threads, which feed to a single server thread handling the clients.

Likewise, I’d like to clean up the network API. Right now there’s a large schism between the official documentation and what is actually implemented. This is bad.

Source Code

This project ended up on my GitHub account:

https://github.com/lkolbly/FRCVision

No story today, but I think I have invented perhaps the greatest laptop cooling stand of all time:

…are the way of the future.

Everyone’s familiar with the almost-ubiquitous QR codes. They appear no matter where you go – cereal advertisements, fliers for prom, even terrorist communications:

As a side note, I would like to thank Kaywa for their free QR code generator. Without their continuing support I would have to use something else, or else (heaven forbid) generate my own QR codes.

Now, QR codes are cool and all, but they’re a little bit commonplace now. They used to be the hip thing. Now everyone who has a smartphone has a QR code reader. I was thinking the other day about my work with SSTV (Slow Scan TeleVision) – essentially, images transferred over sound waves.

Then I saw SpectroTyper, which is very cool oh-by-the-way. It essentially builds an audio file where the spectrograph displays some human readable text.

So I said to myself: I can do that.

And I wrote a little script that will convert an arbitrary QR code into an audio file. You give it data, it spits out a wave file. Here’s an example audio file:

qrcode

I’ll be the first to admit that it doesn’t sound like much. But before you scoff at me too much, pull it into Audacity and look at the spectrograph:

Does that look like something we all know? Scan it if you don’t believe me.

The backend script to generate that isn’t terribly complex. Essentially, it reads an image, and wherever the image is black it adds a cosine wave of the appropriate frequency to that time bucket. Then it normalizes everything and we’re finished.

Feel free to play around with the QR code generator – however, bear in mind that it’s generating each QR code audio bit from scratch on a Pentium 4. So when you submit a job I’ve found it’s usually taken about a minute or two, but jobs are processed linearly so don’t abuse it.

Also, I believe I promised to release the source code for the HDR. You can look at the code Here.

After some tuning, here’s some updated images of my lab:

Notice the much higher color quality. Below is another example where the final image has been equalized:

A little bit like a modern art piece…

And, for the image processing nerds out there, here’s an image I used to debug the assorted curve. Bonus points if you figure out what everything means on it.

At any rate, that’s all I’ve been able to do. Perhaps somebody more skilled/dedicated can do better?

In conjunction with the Lyst project, I’ve started work again on HDR photography. After all, it’s a game that suites itself to High Dynamic Range photography – the players want to be able to see all the details.

Standard images are taken at a single “exposure value”, which is a combination of shutter speed and f-number. Obviously, a very fast shutter speed (1/120th of a second) will make a very dark picture, whereas a very slow shutter speed (1 second) will make a much lighter picture. Usually in photography we try to find a happy middle that gives us the right amount of light in the picture. Here’s an example of three such pictures that I took of my lab:

Let’s look at the printer under my desk (in the bottom-center of the image, yes that’s a printer). In the center image, the printer is almost entirely obscured by the shadow the desk casts. In the image on the right, the medium image, the printer is visible but is still dark. However, the image on the left clearly shows the printer. If I wanted to take a picture of the printer, I would use the exposure value from the left image.

Now look at the two windows in the image. Obviously, they’re too bright in the left image. They’re also a little bit bright in the right-hand image. So we pick the center, darker image as the best picture for the windows – they’re not painfully bright like the other two images.

And, for a third comparison, look at the door and the flyer taped to it. The left-hand image is too bright, and washes out the flyer taped to the door. The center image is so dark that it’s difficult to read the flyer on a standard monitor. The remaining image is the happy middle for the flyer, and if I had set the focus to it, you could easily read it.

Normally, we would have to pick an exposure value to optimize for one of these areas. HDR is a technique for merging these three images into one image, which clearly shows all of the areas, none too bright and none too dark.

But how?

The conceptual approach is that we want to take the bright areas from the dark image (like the windows), the medium areas from the medium image (like the flyer), and the dark areas from the bright image (the printer), and merge these areas together. Image masks come to mind here – if we created a mask that selected for the areas we’ve identified above, in their respective images, then we could simply add the resulting images to form a single image that is contrast balanced.

The first step is, of course, to find the mask. For example, on the bright image, we eventually want a mask that allows dark areas through but not the bright areas. We could simply threshold, but we might have issues picking the right threshold value, so we run it through an equation that teases apart the bright areas of the image slightly so that it’s easier to find a good threshold value. The function we use happens to be a finely-tuned logistic function. The arguments are tweaked to affect how much of the image is pulled from the dark image, how much is from the bright image, and how much is from the medium image. Note that I actually don’t threshold the image – I simply apply this stretching function. Here’s the mask after the stretching function:

Dark areas are where the light image will show through, and light areas are where it will be blocked. Sorry about the aliasing – it was reduced with a nearest-neighbor algorithm.

The next steps are trivial: We apply the masks to the three images, then add them. The resulting image is our HDR result:

Not as bad as it could be. It dims the bright areas, brightens the dark areas, and deals with the middle areas.

I’m currently experimenting with equalizing the image, which increases the color saturation dramatically but also reverses some of the advantages of HDR.

At some point, I’ll release a script which can batch process a directory of files, and allow things like (understandable) controls for the user.

Also, stay tuned for my thoughts about HP Code Wars (yesterday! Yay!) and my new HP Envy:

… Microsoft doesn’t like it when robots setup their computers.

Introduction

While I may appear on the outside to be a cold, heartless programmer, on the inside I’m a normal person who celebrates Valentine’s day like anyone else. That is, by writing programs. (and people ask why I’m single…)

XKCD once did a version of Sierpinsky’s triangles, but using hearts: http://xkcd.com/543/. So I decided that I could write a program that could render these “triangles”, but for arbitrary shapes.

And, once I can do it for arbitrary shapes, I can “heartify” all of the letters of the comic sans alphabet, and have a webpage with a text input to let people create their own heartified strings, for their sweetheart’s name or whatever:

I’ll pick on Sally for now, since she is convenient.

Web Server

Okay, this really is just a CGI script which calls the “montage” program to stitch together the 26 precomputed letters to form a word. Then it saves the resulting image to a file, and serves the file.

Data Processing

It just now struck me that image processing has been a theme for me recently…

Regardless, the hearts are created by using an iterative loop, each time around adding another layer of hearts. Each loop has 4 major parts: sizing, maximizing, disqualifying, and rendering. People familiar with the FRC Vision 2013 architecture may notice some similarities, specifically in the maximizing/disqualifying steps mirroring the point clouds.

Sizing is, as it’s name implies, determining the sizes of hearts that can fit into the current image. This is done for every pixel which may contain a valid heart, and for every pixel it determines the largest possible heart which fits into the legal regions centered at that pixel. This part really is as inefficient as it sounds – I loop through every pixel, and then start with a size 0 heart and step up the size until the heart no longer fits.

There are a few optimizations present, e.g. circles are used as a first-pass approximation to hearts because the hearts equation is long and complex:

    theta = M_PI/2.0 - theta;
    r = (2.0 - 2.0 * sin(theta) + sin(theta) * sqrt(fabs(cos(theta))) / (sin(theta) + 1.4)) / 4.0;

Ergo, it is best to avoid computing this function where possible. Note that I have implemented a cache to accelerate this function through the use of lookups. The distance function leaves us with an image which looks approximately like:

In the above image, the white areas correspond to “illegal” areas where hearts cannot be, and the intensity of red corresponds to the largest heart which fits at the given pixel. Brighter indicates larger hearts can fit. Below is the distance image from the second iteration:

After the distances are computed, note that there are peaks and ridges of intensity. In order to fit the largest heart we can, we want to place hearts on these peaks and ridges. However, we cannot simply place a heart at every valley and peak – we would then run the risk of overlapping hearts. This is why we have the disqualifying step. All hearts are compared against each other, and overlaps are resolved by removing the smaller heart. Again, this is optimized by providing liberal caching and approximations.

Rendering is the simplest step. Wherever a heart is located, after the disqualification step, we simply draw a heart.

Then we repeat. Note how in the second distances image, there are black areas splotched onto the image. These correspond to the hearts which were placed onto the image in the first image.

Final result after 3 iterations:

Possible Future Changes

One thing that I’ve found makes this program exponentially faster is choosing smaller images. This is why each letter was computed individually, and not from a single large image containing all of the letters. In the future it would be nice to have the program automatically subdivide the image into smaller regions to process (or, alternatively, fix the algorithm so it’s faster on large images).

On a related note, I have done work on removing the need to recompute the distance map for the entire image every iteration. The theory is that we can determine how a given heart affects the distance map near it, so we adjust the distance map at render time instead of having to recompute it every iteration. However, I couldn’t get this code to work in time for Valentines, so it is commented out.

In order to make the algorithm more useful for other holidays, I think it would be nice to allow for different shapes and colors (not just red hearts). Also, people (you know who you are) complained about my use of Comic Sans, so maybe a font selector would be good.

Source Code

This project ended up on my GitHub account:
https://github.com/lkolbly/Valentine2013

Amazon sure did have a lot of screw ups this year, no?

But has anyone gotten the wrong New Year’s Resolution yet? I distinctly resolved for true love and happiness, but I seem to have gotten somebody’s resolution to lose weight. And this person must have been freakin’ massive. Who else would want to lose 25 pounds?

So, if anyone out there was meaning to lose 25 pounds, but instead got true love and happiness, if you could please let me know.

But only if you like Pina Coladas, and getting caught in the rain.

Regardless, let’s get to business. Another one of my projects is the FRC Vision C++ Platform. This project intends to become a simple way to move data from the AXIS camera on the robot into the LabView application on the robot, while at the same time processing it for shapes, etc. Incidentally, it’ll be running on a separate Windows computer, not on the robot, communicating via 802.11. Now is that efficiency or what?

But, check out the code: https://github.com/lkolbly/FRCVision

In other news, no news on Lyst.

And no news on the SillyBot.

But I got this really cool alarm clock/iPad dock thing! It had a remote, so I can play Pandora from a long way away.

So, this is my entry for one of the Kealing application essays. Please don’t copy me, as I could get into some trouble. Possibly.

There was a house here. I traced the doorstep where we found the marble statue with my foot. My foot swept aside several inches of sand, uncovering the original stone step. The carbon dating team back home had texted me  earlier, saying that the animal statue was sculpted using metal tools, like I had guessed, and that it was roughly five thousand years old.

Five thousand years. Long enough to hide everything but a metal ball, an animal sculpture, and a large stone sculpture of what appeared to be human. None of us had any idea what they meant. Who were these people? How did they make a living? What were their rituals? Why did they vanish?

“Benjamin! We must go before the tsara!” I turned to my Arabian guide, then looked at my wife packing the last bag into the jeep, twenty yards away. The tsara was a legendary sandstorm that occurred annually, and was said to wipe away everything in it’s path, changing the very layout of the sand dunes around us.

Then it hit me. I was teleported back five thousand years, to a small agricultural village. I stood in the center of a ring of mud huts, near the doorstep with the marble statue, facing the giant human statue. The town was apparently empty, except for a young girl, around fifteen I supposed, knelt in prayer at the giant human statue. Her dress was made of a light weaving of the local tall grass, her hair was in a bun, indicating that she had recently been working. Probably either weaving or some other home making. A young boy, similarly aged, ran over to the girl. His hair was cropped short, and he was wiping his face with a cloth he kept at his belt, indicating a hot work, probably baking or blacksmithing. I walked close enough to hear.

“The council has made their decision. We are to leave, and burn the town so the Animal God may have his land back.”

The girl broke down in tears, and the boy moved to comfort her. The girl managed to sob that “then it is all over. We cannot make it to the next town by the time the tsara is here.”

“Do not worry. It is all a part of Their plan.” There was a pause, and the boy continued “I made you this.” He produced from his robes the same one inch metal sphere I now held in my hand. Five thousand years later.

“Benjamin, Molly finished packing jeep. We go before tsara comes.” The Arabian guide was starting to get antsy.

I walked over to the jeep. Molly turned to me and smiled “Well? Think we’ll beat the tsara?”

I put my hand on Molly’s shoulder and gave a supportive smile “Don’t worry.” I paused for a split second “I brought this for you.”

She smiled “Oh, Benny. Get into the car before our friend has a heart attack.” She jumped over the welded back door of the jeep, and I climbed into the passenger seat to keep our guide awake for the 12 hour ride back to Laghouat, the nearest form of a civilization. Modern civilization, that is.