Saturday, October 28, 2006

Algorithm: JPEG and related

I've been researching image compression on and off for a while. I see the methods that make up JPEG forming a core standard that most modern image and video compression is based on.

I've been wanting to make a JPEG compressor in a dsPIC for a while now. What do you do when you only have 16K to 30K of RAM? You look at what you're doing!

JPEG takes a YCbCr image and compresses each channel separately. A block of 8x8 values is put through a discrete cosine transform (DCT) which, like the FFT, provides a frequency value. Next, there is a zig-zag pattern defined by JPEG that takes this 8x8 block and rearranges it into a linear 64 byte block. So far, if the DCT result is kept in a floating-point format, no data has been lost. Next up is quantization. Either a fixed multiplier sequence (simple) or one calculated from the overall image (complex) is used to scale the image data, losing resolution. After that, any data below a certain threshold is set to zero, which starts the compression. The final step is what's called Hufmann coding. It uses either a set or calculated table to assign a unique binary symbol (say 01 is one symble, and 011 is another symbol) to replace a part of data. The theory is that a symbol's length is inversely related to how often it shows up. Ideally the table should be generated beforehand from statistics, although on the fly table generation gets close. Both the Hufmann table and the quantization table need to be passed to the reader so that it may be effectively decoded.

It's a lot of information, but there are better and more in depth discussions on the net.

I have a camera that does VGA images. Standard output is 4:2:2 (I think that's the format). For every pixel, it puts out a greyscale 8 bit value and either a red or a blue 8 bit value.
So, I don't have to do any conversion. I can decimate the red and blue channels to bring it down to a 4:1:1 depth (4 greyscale per 1 of the color channels). To correctly capture this data, I need 8 lines stored in RAM. As a raw data count, that would be 10,240 bytes. After decimation that's 7,680 bytes. Might be a bit tight in there...

dsPICs have DMA, which makes it easy to get the data into buffers without CPU capture intervention. Since the 8x8 DCT is so common in image compression, people have been trying all SORTS of ways to get it fast and simple A single 8x8 DCT can be broken down into 16 1x8 DCTs. You run a DCT on each row, then one on each column. My plan is to run the DCT in place in the buffer on each row and put the results into a new buffer outside of DMA control. I can also sort the rows out to isolate the various channels at the same time. Once 8 rows have been read in for any channel buffer, the 1D column DCT can be run.

there are 40MHz TI DSPs that have DCT hardware for image processing, allowing them to do the rest of the compression in software. TI DSPs are great. I just don't want to fork over several grand for a compiler.

After that, I can immediately start making decisions. I don't necessarily need a full JPEG compatible image as long as I have a reader on the other end that can decode what I encode. One way suggested in a technical paper (find reference) is that the encoding stops at quantization and truncating the data. This is nearly as effective in compression as the Huffman table (both size and quality) and greatly reduces the additional workload required. High frequency information suffers greatly, however. I'm considering this method. given the extremely rapid data transfer that must be done for an embedded camera. I'd like to get a VGA or QVGA video compressed down small enough to stream over an RF link, but I believe that may be impossible given the horsepower I want to attempt it with. Time for a 200MHz ARM32?

Tools: CAD for the home user

I've recently started looking for good, no cost CAD software to work on my solids designs. I wanted to find something that's anyone can get and use continuously, so no expensive packages or time limited demos.

My original hunt lead me to open source. From there, I ran into the following software. I'm still just touching on these right now, so I might be missing the big picture.


BRL-CAD is an open source implementation of the Army Ballistics Research Laboratory solid modeling package. They use it to do simulations of various combat scenarios. Its results look pretty, but the Windows package I looked at shows that this is going to be a command line driven uphill battle. It's essentially a collection of very powerful software bits that can read and work on the same data set.


Another CAD package, although this is not based on a US DoD project. Seems similar in capability to BRL-CAD, and also may be command line based. What got me interested in looking at this one is that it has close ties to various finite element analysis software packages.


Ah, an old open source 3D modelling standby. While you can do solid CAD style modelling with it, and it has a much better UI for diving into it than the prior two, it doesn't appear to do solid modeling, which may cause issues if you want to post-process the component.

Now, there's also a few "freebie" packages I'm investigating. As they're based on commercial packages for Windows, they tend to be at least easier to dive into within a few minutes. I'll have to see how everything stacks up in the long run.

Solidedge 2D V19

Basically the 2D component of SolidEdge, this is a really REALLY nice free 2D CAD package. It's not AutoCAD, but it reminds me of the fast and simple CAD package I learned on back in high school. It's also nice that it can open and edit all AutoCAD files, and can export into AutoCAD and MicroStation formats, so it's not locking you into its format.

Alibre Design Express

I'm just going through the initial tutorial for this one. If it's up there in capability with SolidWorks and SolidEdge, this one's a keeper. They've removed the ability to work with sheet metal forms and the ability to generate bill of materials (these are usually addons in other programs anyway). However, it looks like it's all there, I'll give it a try and I'll have to follow up on this at some point in the future.

Monday, October 23, 2006

The Fourth Combat Form: Nerf

As this blog's rolled on, I've talked a bit about three different combat teamplay concepts. MilesTAG (beefed up laser tag), paintball, and Airsoft. Well, to round out this, let's take a look at another obscure teamplay game, Nerf.

Most people (read kids, teenagers) get a few Nerf guns and play a few "shoot em" games with friends. A few go and modify their stock nerf guns to remove some of the safety limitations. A few others go and make their own cheap, custom rounds. Even fewer go and build their own guns, usually low shot PVC contraptions that, while ergonomic and effective (although sometimes really neither), they make a bullpup pneumatic potato launcher look sleek and sexy.

And then... there's a guy who goes by the pseudonym Boltsniper. I believe he's graduated with a mechanical engineering degree, like me. Unlike me, he exercises his 2nd amendment rights. He also uses that knowledge gained to make semi-automatic full custom Nerf designs that work.

I don't want to copy him, but I will learn from him. I still want to make that airsoft/paintball OICW. For that, I need to understand how shell load and eject systems work. Well, at least the loading system, as I've been contemplating a caseless design.

So, today's objectives?

Part 1: Figure out a caseless Nerf gun system that has a working magazine system and runs on 3/8" nano Stefan darts. 9.5mm caliber if true diameter.

Part 2: Take the magazine system and integrate it with an airsoft style motor driven plunger system. This will allow select fire and full auto to be implemented. I have no objection to Boltsniper's pump system at all. It's quite the marvel in terms of system understanding and parts availability. I just want to see if an airsoft style reciprocating assault rifle will work.

Project 2 will be scaling this up to 25mm for range tests and practicality testing on dummy airsoft airburst rounds.

And no, I haven't given up on MilesTAG2020. Frankly, the various systems all kinda melded together. My ultimate objective is a series of modules that connect together and can be used for various game types. MILES is just the "ultimate" use, as it will integrate the actual shot detection, scoring, and shooting into the module network. The problem is, like the real MILES, you can't simulate indirect fire or area effect attacks effectively. While not a big deal for a game system, the US Army's troops are not ready for the realities of full combat that includes shrapnel clouds. That realization was not mine originally, but belonged to some article I read. I fully agree with it, however.

Saturday, October 21, 2006

Near field active target tracking

Life got me. Busy summer, who knows if it's over yet...

I ran across a website a while ago about using a laser and photodiode to track a target in 3D.

Now, they use a pair of galvanometers to control the laser. Nifty. You can build some yourself actually. It's mostly a magnet, glued to a shaft on bearings, over a magnetic coil. One end has a first surface mirror, the other has a feedback mechanism.

One issue with building galvanometers yourself is that you probably won't get anywhere NEAR the frequency response of a pro set. I know of a pro set for laser shows that runs $700 or so. That's less than half what most places would charge.

So, do we have alternatives? I believe yes. At the loss of flexibility and speed, we can probably use two standard RC servos for X-Y positioning. The high speed circle drawing could be replaced by a small motor with an off-kilter mirror. Now, to adjust circle size, either a small push rod to another servo-esque setup (worm gear?) or a different focusing mirror arrangement, I'll have to see what's pratical. A stripped laser pen diode should work fine for the source, and I can get a decently matched photodiode from Digikey et-al. Optics, motors, and other oddball stuff actually should be available locally for me at American Science and Surplus. Even the parts for a first run galvanometer if I so chose that route.

While the demonstrations they do are good, they have limitations. Power output and circle size is based upon relfected light from the target, and it's assumed to be roughly spherical. Makes adapting it to track other objects difficult. Not impossible. I'm more worried about tracking, say, my pasty white finger and then having one of my darker compatriots try it and the system thinking he's a meter farther back than he is. Time will tell. Maybe a slightly off-axis reciever running a 2D PSD (position sensitive device) would allow for rough triangulation and automatic tuning.