A colleague recently presented a paper at the MICS 2011 Conference in Duluth, MN. Since I was the first to google the knapsack problem for him (among other minor things), I became second author!

Apparently, owning a laser cutter opens a whole new world insofar as building things is concerned. I just couldn’t resist the allure!

I purchased a 40W engraver/cutter from Full Spectrum Engineering during spring break (Mar 11-18). It finally arrived on the 6th of April. I stayed up until the wee hours of the morning configuring, aligning, and getting a few test cuts done:

I do not regret opting out of the Windows-only USB printer interface for the machine, I’ve gotten great results using only the parallel port, EMC2, and Inkscape. Configuration files for the 40W FSE Laser under EMC2.

The only hiccup so far is the manual massaging of the gcode that the gcodetools Inkscape extension spits out, but that should be easy to remedy. A sample massaged gcode file.

Last summer I slapped together a workbench project into an enclosure and gave it to a friend, he liked how it sounded. Eventually it broke down, so I offered to design a PCB to replace the circuitry.

The Overdrive circuit, next to the replacee:

Design files: PCB, Silk

A friend needed help hooking up his PS3 USB DDR pad to his PS3 while it was emulating a PS2 game.

The original pad used a USB connection, but was not a ‘Sony blessed’ interface. The first step was to acquire a PS3 controller to sacrifice. We removed the plastic shell and plastic interface board, then I cooked up the following PCB to interface with it:

Design files: PCB, Silkscreen

Next, we cracked the USB Pad, removed some extraneous plastic and circuitry, and attached our “controller-within-a-controller”:

I wasn’t entirely satisfied with my previous attempt at HTTP/POST gzip-compression, so I wrote a more elegant solution (no XMLRPC libraries this time).

A function to perform gzip-compression on a string:

// see zlib's compress.c:compress() function for the original of this
// modified function
//
// dest      : destination buffer, malloc'd already
// destLen   : size of the malloc'd buffer
// source    : the uncompressed text
// sourceLen : the size of the uncompressed text
//
// this function returns an error code from the zlib library.
// upon return, dest contains the compressed output, and destLen
// contains the size of dest.
int string_gzip (char *dest, unsigned long *destLen, char *source, unsigned long sourceLen)
{
  char *header;

  sprintf(dest, "%c%c%c%c%c%c%c%c%c%c", gz_magic[0], gz_magic[1],
          Z_DEFLATED, 0       , 0,0,0,0      , 0        , OS_CODE);
        //          , flags   , time         , xflags   ,        );

  header = dest;
  dest = &dest[10]; // skip ahead of the header
  *destLen -= 10; // update our available length

  z_stream stream;
  int err;

  stream.next_in = source;
  stream.avail_in = sourceLen;
  #ifdef MAXSEG_64K
    /* Check for source > 64K on 16-bit machine: */
    if (stream.avail_in != sourceLen)
      return Z_BUF_ERROR;
  #endif
  stream.next_out = dest;
  stream.avail_out = *destLen;
  if (stream.avail_out != *destLen)
    return Z_BUF_ERROR;

  stream.zalloc = Z_NULL;
  stream.zfree = Z_NULL;
  stream.opaque = Z_NULL;

  // instructs zlib not to write a zlib header
  err = deflateInit2( &stream, Z_DEFAULT_COMPRESSION, Z_DEFLATED,
                      -MAX_WBITS, DEF_MEM_LEVEL, Z_DEFAULT_STRATEGY );
  if (err != Z_OK)
    return err;

  err = deflate(&stream, Z_FINISH); // Z_FINISH or Z_NO_FLUSH if we have
                                    // more input still (we don't)
  if (err != Z_STREAM_END) {
      deflateEnd(&stream);
      return err == Z_OK ? Z_BUF_ERROR : err;
  }
  *destLen = stream.total_out;

  err = deflateEnd(&stream);

  dest = header; // put the header back on
  *destLen += 10; // update length of our data block

  return err;
}

Using this function to make a gzip-compressed HTTP/POST using libcURL:

   char *data = readXMLInput();
   unsigned long dataLength = strlen(data);
   unsigned long compressedDataLength = dataLength*1.1 + 22; // see zlib's compress.c
   char *compressedData = calloc(compressedDataLength,1);
   string_gzip(compressedData, &compressedDataLength, (char*)data, dataLength);

    curl =  curl_easy_init();
    struct curl_slist *header_list=NULL;

    curl_easy_setopt(curl, CURLOPT_URL, "www.example.com/xmlrpc.php");
    // set the "Accept-Encoding: " header
    curl_easy_setopt(curl, CURLOPT_ENCODING, "gzip");
    // set the "Content-Encoding: ", "Content-Length: ", "Content-Type: " headers
    header_list = curl_slist_append(header_list, "Content-Encoding: gzip");
    header_list = curl_slist_append(header_list, "Content-Type: text/xml");
    sprintf(contentLengthBuf, "Content-Length: %d", compressedDataLength);
    header_list = curl_slist_append(header_list, contentLengthBuf);
    curl_easy_setopt(curl, CURLOPT_HTTPHEADER, header_list);

    // Now specify the POST data
    curl_easy_setopt(curl, CURLOPT_POSTFIELDS, compressedData);
    curl_easy_setopt(curl, CURLOPT_POSTFIELDSIZE, compressedDataLength);

    // Perform request
    res = curl_easy_perform(curl);
    curl_slist_free_all(header_list);
    curl_easy_cleanup(curl);
    free(compressedData);

Above is the source code for a simple* extension of ulxmlrpcpp that allows Gzip compression of XML-RPC.

The simplest* method to perform a Remote Procedure Call (RPC) from one language to another is XML-RPC.

The XML-RPC specification is dead simple; using XML, construct a procedure call, with the parameters of the call as children. Then, send this XML document using HTTP/POST to the resource server, where the request is processed and an XML response is sent back containing the procedure’s result.

The problem I’m concerned with: using a Java Server (JavaMOO), construct an XML-RPC server that can communicate with a client written in C/C++, and do so efficiently enough to run a real-time virtual world.

This hardly seems like anything to right home about; in fact, I had no problem finding Java and C++ implementations of XML-RPC, and was performing RPCs within the hour.

The drama came when I considered efficiency, and hence compression. The XML-RPC specification is unclear/denies the use of any sort of compression on the XML document, which is a shame. Gzip compression is available as a vendor extension for the Java implementation I was using (Apache’s ws-xmlrpc). I found no such capabilities in any C/C++ implementations, so I wrote one up.

*: Nothing is ever simple.

I’ve been tasked with some basic research.

Now that we have two versions of JavaMOO (backstory), it’d be nice to know if one is more capable than the other.

javamoo-legacy has the benefit of the doubt; we know it works in practice, and we have many usage tests backing up the majority of its functionality. JavaMOO has the benefit of a professional project; with plugins, post-build-time configuration; all the trappings of a polished product.

Here’s a plan of action:

• Familiarize with JavaMOO, compile
• Write a client that communicates with both servers (RMI)
• Perform some simple tasks like object creation, database queries, etc.
• Draw conclusions, reformulate & reiterate experiment

Nothing too exciting here. A C++/Ogre/Blender effort; controls are w,a,s,d for movement, ‘b’ to drop a box, and ‘r’ to load the auxiliary map texture.

I’ve been hired by WoWiWe Instruction Co.

The job description:

Using the existing JavaMOO server, build a “World Development Tool” to aide content experts (grad students) in the rapid development of educational games.

The project must be delivered before December 31st, 2010; when my employment terminates. This sort of a finite-length employment makes a lot of sense to me; it allows me to plan for the future (graduate school) while building my job experience. Much like an internship, but better paying.

A friends’ birthday’s coming up, and two of us have gotten together to give him a great present.

A guitar’s the gift, but we can’t just give the birthday boy a used guitar! We decided to put a speaker into the body of the guitar, but in testing (before drilling) we found that the bass strings overtook the treble. We had two choices: a simple equalizer, or two speakers.

After we chose to use two speakers, we tried a few things to get the desired effect. The simplest approach, the approach used in mass-produced dual-speaker systems (think plastic boombox), is to use a filtering capacitor for the bass speaker, and feed the plain signal into the treble speaker.

This approach was dismissed for two reasons:

• We needed to decrease the volume of the bass in both speakers
• We were halfway towards an op-amp buffered equalizer circuit already, as we needed to amplify the guitar to drive the speakers

Our second point became moot in the end, as we ended up using three op-amps to make the 1x buffer/ 2x equalizer, and an additional two op-amps to drive the speakers themselves. We could have used the fourth op-amp as an adder, and fed the output to one speaker. However, the clarity would have suffered so we went ahead with a two speaker design.

Sometimes the best way to test a piece of software is to throw a bunch of kids at it.

Some background: I didn’t really graduate. I was missing one class, Database studies. Dr. Brian Slator was kind enough to offer me a few alternatives in order to graduate on time, and I chose to work on the development of a graduate’s project from x years ago. The graduate, Ben Dischinger, completed his Master’s Defense and delivered a newer version of his software, JavaMOO, earlier this year.

At the time, and still, our development was in the older version of JavaMOO (denote javamoo-legacy). JavaMOO is a server architecture that allows clients to connect via Java’s Remote Method Invocation (RMI) interface to a database (Derby, MySQL) on the server. JavaMOO is intended for the development of educational games, and Dr. Slator has one such (simple) game with a few hard-to-track bugs abound.

Since the server is threaded to allow higher user-throughput, a database concurrency error was suspected to be the cause, hence the credit substitute for the Database requirement for graduation. I brought myself up-to-speed throughout last semester, and had cracked a few unrelated bugs while testing out the system.

At semester end, Dr. Slator had offered extra credit to one of his classes for volunteers to come into the lab and stress-test the server, to check our progress and help reveal any new bugs. We’d made steady progress as usual since the semester end, and yesterday we had another round of testing. Dr. Slator had an opportunity to give a group of high-school-age students a one-hour demonstration of our lab’s work, and we jumped on the opportunity to show off, and test, our educational game.

The kids did a great job, they managed to crash all three of our servers.

Dan‘s gone! He left the 18th of last month, but not before dropping off a present:

A “D&M 4 Machining Center,” an educational model. This last week I’ve been cleaning the mill, and imagine my surprise when I pop the back to find this:

Although the front controls and computer control port were toasted, the power supply was functioning, and after sending a 5V probe into the logic input of one of the motor controllers, we find that the Mill is, in fact, in operating condition! It’s now “feasible” to attempt some repair:

• New controls:

• New circuit board to translate the controls to 5V logic (using 555 timers, two per axis, each pair allows two duty cycles per axis):

On an up-note, while researching the ICs on the motor controller boards, I found that they have a boolean state for half- or full-stepping (!). The makers of the controller boards even put a small rocker switch on-board to toggle the stepping-mode:

@ 10:00 May 15th 2010,

I confer upon you the title “Bachelor of Arts.”

This means I have time to work on my own projects now, right?

So, you want to take two images, slightly offset in space from one another, and combine them into a larger image.

This is an old problem, and seems “solved” if you consider the Photoshop plugins, etc. to produce such panoramas. Most don’t realize that these tools are less than perfect, for instance the final product can be greatly improved by removing the lens distortion from each image before attempting to perform a panoramic merge.

But we don’t want to make a panorama with our images, we just want to do all the steps (correctly) up to the point where we’d try and combine them, i.e. perform translations/rotations/scaling to make the images lie on the same plane, so that each image’s only difference is being offset in that plane (only x and y offset, no z offset, no rotations in space, etc. )

Consider a model of the Large Camera Array Dan and I have been using. Our intention is to have the cameras lined up so that each of the camera’s sensors lie in the same plane, so that the only information being added by each adjacent camera is an image x units to the left. This is impractical in reality: each camera is slightly offset from the others, some even have tilted lenses causing them to look slightly down, etc. as we’ve observed in the data we’ve collected.

In order to find the transformations that will rotate/scale/translate the images so that they all lie in the same plane, we must make a set of assumptions about our problem to have any hope of implementing a solution. (The alternative being trying all such rotations in all three axis of freedom, etc. until the images are planar, an algorithm that would take prohibitively long [years] to complete.)

We can assume that all such rotations take place from (have origin at) the center of the image, since our images were taken with a camera and lens system. We can also assume the maximum displacements in the x,y,z plane, based on measurements of our physical system. We can additionally put maximum bounds on our rotations, but we may not want to in order to allow for flexibility in camera orientations (say landscape, portrait mixes).

The goal all of this is working toward is to be able to calibrate an array of cameras, or a collection of images from one camera, moved through space between shots, so as to put there output on the same plane. In the case of an array of cameras, this calibration need only be computed once (or every once in awhile) in order to better fit the model of being perfectly planar.

If such an algorithm is successful, it would enable a hastily constructed or ad-hoc array to provide useful Light Field representations, and improve the output for constructed arrays as well.

Currently, our lfmanip only concerns itself with translations in the image’s x,y planes (not the real-world x,y plane, mind you). If we knew the rotations and scaling between each image, we could line up our images in a much better way.

To tackle this problem, I’ve decided to attempt to reduce each image to a line representation, a vector image. Given each image as a set of lines, it will be remarkably easier to compare two sets of lines and try and decide which set of transformations will make them most similar.

I’ll be graduating with my Bachelor’s of Arts in Mathematics/Computer Science this spring, so  I’ve decided to tackle the problem of mathematically describing the “optimal” way to prepare an image for edge-detection for my capstone research project. The hope is that working with the nit-picky parts of this process I’ll be able to extract a set of lines from a given image, particularly those lines that will be most helpful in deciding how an image has been transformed with respect to rotation/scaling/translation of a previous image.

It’s likely such a best approach does not exist or is computationally infeasible. Whatever the case I’m optimistic that by slowly adding in more assumptions about the problem I’ll be able narrow the search space to the point where an algorithm can be written to do the heavy lifting.

There were some issues when using images in portrait mode, and I’ve upped the maximum number of allowed images to 500.

I’m still cranking away on the correction of rotations and almost-perfect matching. It turns out almost-perfect matching is just a matter of rewriting the way lfmanip stores/compares the already collected feature points, but the rotation issues have turned into an ugly monster.

I’ve enlisted the help of a mathematics professor to help with the rotation issues, and he assures me that it will not be a trivial problem to solve.

Dan and I tried to build a cheap book scanner. Enjoy the Cardboard Book Scanner.

This is an updated version of lftextures. lfmanip makes use of the OpenCV libraries and the SURF algorithm to generate feature points, which are then used to match features between images, allowing us to automatically align the images in the application, rather than requiring the user to do so before hand.

This application also saves the resulting offsets into a file “offsets.txt” in the image directory, and will automatically load the offsets from this file if it is found. (Therefore subsequent viewings do not require the alignment procedure.)

Currently the code isn’t very fancy; it must match the same feature in all images or else it’ll fail. It’s also a bit slow, it takes approx. 4-12 seconds per image to calculate all of the SURF points. I haven’t polished the code base as well, so if a segmentation fault or crash happens be sure to e-mail me with a short description of what happened.

To use other datasets with this program, just drag and drop a folder containing your data onto lfmanip.exe and it’ll load those images; otherwise it will use the hard-coded “lf/” directory.

In the first view, use the drawn arrows to page through the images, and look for a suitable feature. In the provided dataset, the tower on the top of the image looks suitable. Drag a selection box around the feature you think will work, at this point lfmanip should freeze. Watch the command window for output.

If lfmanip finds the same feature in all images, it’ll write it’s findings to “offset.txt” in your image directory and switch to viewing mode. If it does not, it’ll draw red dots where every feature was found.

At any point, (except when processing a selection) you may hit the ‘S’ key to switch between the two viewing modes.

Otherwise, the controls are on-screen and are the same as lftextures‘.

Coming soon:

• The ability to match almost-perfect features
• Automatic image rotation for wobbly pictures

This is a PSA for anyone who’d ever want to load jpegs into an OpenGL program (in c)…

Loading textures into OpenGL is a pain. The API expects the image information to be presented to it in binary form, of which the user may choose from:

• {Luminance | Red | Green | Blue} for single valued streams
• {RA | RG | GA | etc.} for double valued streams
• {RGB | RGA | etc.} for triple valued streams
• {RGBA} for quad valued streams

(Full listing @http://www.opengl.org/sdk/docs/man/xhtml/glTexImage2D.xml)

The first pain a user faces is getting a binary stream loaded. While the rest of OpenGL is calling blackbox functions, the user must write a file opening routine:

FILE *image = fopen("texture.raw", "rb");
//must be a power of two in both dimensions
int height = 512;
int width = 512;
GLuint texture;
glGenTextures(1, texture);
glBindTexture(GL_TEXTURE_2D, texture);
glTexImage2D(GL_TEXTURE_2D, 0, 3, width, height, 0, GL_RGB, GL_UNSIGNED_BYTE, image);


But then its not always so obvious how to convert a given image into a raw format, how to skip past the header if it’s an almost raw format, etc.

Most users want to use a common format that’s easy to work with. Since lftextures uses digital still cameras as it’s input, loading the jpegs directly seemed like a fantastic idea.

Fantastic until you see the code:

FILE *fd;
unsigned char *image;
int width, height, depth;
fd = fopen("texture.jpg", "rb");
struct jpeg_decompress_struct cinfo;
struct jpeg_error_mgr jerr;
JSAMPROW row_pointer[1];
unsigned long location = 0;
cinfo.err = jpeg_std_error(&jerr);
jpeg_create_decompress(&cinfo);
jpeg_stdio_src(&cinfo, fd);
jpeg_read_header(&cinfo, 0);
cinfo.scale_num = 1;
cinfo.scale_denom = SCALE;
jpeg_start_decompress(&cinfo);
width = cinfo.output_width;
height = cinfo.output_height;
depth = cinfo.num_components; //should always be 3
image = (unsigned char *) malloc(width * height * depth);
row_pointer[0] = (unsigned char *) malloc(width * depth);
/* read one scan line at a time */
while( cinfo.output_scanline < cinfo.output_height )
{
jpeg_read_scanlines( &cinfo, row_pointer, 1 );
for( i=0; i< (width * depth); i++)
image[location++] = row_pointer[0][i];
}
fclose(fd);
jpeg_finish_decompress(&cinfo);
jpeg_destroy_decompress(&cinfo);


Then you’ll want to load this into a texture; the code is the same as above except we’ll use the GL_TEXTURE_RECTANGLE_ARB extension to allow for any sized image:

GLuint texture;
glGenTextures(1, texture);
glBindTexture(GL_TEXTURE_RECTANGLE_ARB, texture);
glTexImage2D(GL_TEXTURE_RECTANGLE_ARB, 0, depth, width, height, 0, GL_RGB, GL_UNSIGNED_BYTE, image);

Last and most importantly; to use the libjpeg library you need to include it:
#include <jpeglib.h>
and compile like so:
gcc -ljpeg this.c

Other examples:
http://www.cim.mcgill.ca/~junaed/libjpeg.php
http://www.jpegcameras.com/libjpeg/example.c%3frev=1.4

libjpeg specification:

http://www.jpegcameras.com/libjpeg/libjpeg.html

Prologue: The Need
Dan Reetz thought to himself, “I have this great idea for a large camera, but I need to have the tools to use the camera before I build it.” Dan had been collecting the cameras and other parts for awhile before I’d met him. Once he told me about his idea, we decided that the project was within reach and went for it.

Our plan was to design a program that could display the additional information captured in such a fashion; and to do so we needed some data. So we built a “slide-type” camera, and made a set of overlapping images of a few different scenes for an initial dataset.

Step 1: The Method
At the workstation, Photoshop is fired up. Dan’s intuition is to pick the object we want to focus, align all images so that feature is centered in each image, and then take the mean of all the images. Success! We’ve refocused the scene! We also experimented with the mode, median, etc. and found the mean and median to look the best.

Step 2: Emulation
My task now was to perform the same tasks in a manner that was repeatable on any suitable dataset.

First our requirements:

• We need to display 12 or so images at once
• We need the user to have interactive control

These lead me to choose a graphical language of some sort. I decided to use OpenGL (used in 3D games and applications) and the GLUT toolkit (OpenGL extensions for keyboard, mouse, window, etc. control). I chose them for two reasons: cross-compatibility, and familiarity.

Using OpenGL allowed me to take advantage of the blending modes and the ability to set the transparency of an object to perform the “mean” of the images without an intermediate processing step.

A problem was therefore introduced: I would want to make big rectangles and display (texture) the images on them for speed and efficiency reasons, but OpenGL expects texture dimensions to be in powers of two, meaning we couldn’t use any input image we wanted without preprocessing them first. (I actually built an initial attempt that sampled the image and made thousands of little “pixel” rectangles, but this method was very slow and memory intensive, i.e. over 2GB of RAM)

Of course, others wanted to texture arbitrary images as well, and the problem had been solved quite a long time ago when graphics cards began to support the GL_TEXTURE_RECTANGLE_ARB extension; this allows textures to be any dimension, among other things.

At this point:

• We could perform our target procedure
• We had reduced the CPU and memory footprint

All that remained was to implement the steps to calculate the refocused scene. By a stroke of luck our initial attempt worked very well; at first we didn’t realize that it’s success was due to the careful manner in which we had taken the pictures.

Step 3: Fire-fighting
We now had a working program, but it wouldn’t perform correctly on some of our data, confusing and frustrating us.

It didn’t take us long to root out the problem; once we had the data open in a viewer we noticed that some datasets were aligned very well while others were not. We quickly did a manual alignment in Photoshop on one of the problem datasets et voilà!

Epilogue: Onward
The core of the application hasn’t changed since. It is a major pain to manually align each dataset however, I’ve begun work on a rewrite that aligns the images in the program, instead of relying on the user to do so before hand.

Now that we’d completed our tool, we could see what our plenoptic camera was seeing. We now had a flurry of questions to answer:

• Why is the plane of focus so shallow? (1-2 cm!?)
• Can we retain sharpness on the edges of our output?
• How can we improve the resolution of our compositions?
• What other sorts of operations can we perform?

And additionally:

• How many of our limitations are caused by our software?
• Are some of our problems caused by our hardware?

So we march on.

Dan and I have just put the finishing touches on two new Instructables:

First, a primer on Computational Photography: Computational Photography Primer
Second, a quick tutorial on using a single camera to make a refocusable image: Using one Camera to Make Refocusable Pictures

Edit: Newer versions of this application still use the hard-coded “lf” directory, but only if no other directory is given. To use a different directory, just drag and drop the folder of pictures onto the “lfmanip.exe” icon.

I’ve gotten a lot of e-mails asking how to put your own data into lftexures, or how to the put the other available data in.

The version I released uses a hard-coded directory, “lf”. Just replace all the pictures inside the ‘lf’ directory with your own data and the program will automatically load them all, in alphabetical order (maximum of 22 images).

Here we have available some binaries of our simple light field viewer, lftextures. When Dan and I first tried to capture a light field, trying to manipulate the data was a real pain. How were we to know if our data was any good if we didn’t have a simple test to show we had captured the scene? We decided to implement the easiest operation, digital refocusing. Here’s the product:

The controls are simple, use the mouse wheel or Home/End keys to scroll through the scene; the application refocuses as you scroll.

Scroll up = move to background, Scroll down = move to foreground.

• Mouse wheel, or Home/End keys: Scroll through scene
• Click and drag mouse: Rotate the viewing plane
• Arrow keys: Move the viewing plane
• Page Up/ Page Down: Zoom in/out from the viewing plane
• R: Reset the viewing pane
• P: Print the screen (files are dropped in the directory lftextures is in, i.e. the working directory)
• O: Turn off/on the on-screen display (The text in the main window)
• X: Speed up/down the rate of scrolling
• L: Brighten/Darken the scene
• M: Switch render modes

And finally,a few macros (for making movies)

• I: Print screen and Scroll up once
• U: Print screen and Scroll down once
• Y: Print screen and rotate away
• T: Print screen and rotate towards

Once you’re satisfied scrolling through the scene, try hitting “M” until the on-screen display says “M: 2, 3D” then click and drag the scene back and forth: