In this lab I implemented several video processing algorithms in C with in-line assembly, making use of the MMX SIMD instructions of the later Pentiums. I also implemented these algorithms in straight C and compared them for speed.
(a-b) +
(b-a) = |a-b|. That means that with two subtractions and
an add we can compute 8 pixels.
For this algorithm it computes an approximation of the magnitude
of the gradient at each point and displays that. In flat places
the gradient is almost zero so it shows black, while on edges
the gradient is larger so it gives values closer to white. The
value for each pixel is calculated as |a-b|+|c-d|,
where a and b are the pixels
immediately to the left and right, while c and
d are the ones above and below. This is a nice
algorithm because we can just repeat the steps of background
subtraction twice and add the results.
For ghosting we blend the current view of the world with the
world as it was a certain number of frames ago. Frames are put
into a history buffer as they are captured, and the output for
each pixel is half its current value plus half its past value.
This should just be two steps, a bitshift and an add, repeated once
for each pixel in the current image and once for each pixel in
the historic image. It is made a little complicated, however, by
the MMX shifting operation being unable to work on packed bytes,
just words, double words, and quad words. I had to do a bitwise
and to clear the appropriate bits, which is a bit of an
ugly kludge. It is still a fast algorithm, just not as elagant
as it should be.
This algorithm goes through a history and turns any pixels that changed over the time period black, showing what parts of the picture are in motion. This algorithm was going to be part of the background generator, but I re-did the algorithm so it was no longer needed.
Here I take two frames and for each pixel where the variance is less than a threshold I update the output. This keeps moving things from showing up while consistent things remain. If something is consistent long enough, it too will show up. I implemented this in both C and assembly, but there are problems with the assembly.
Now we can combine background generation and ghosting to let people show up in a scene as transparent. Any movement in front of the camera shows up as only half there, while anything that stays still long enough becomes solid.
| Algorithm | C time (fps) | MMX time (fps) |
|---|---|---|
| Through | 15.22222 | n/a |
| Delay | 14.91892 | n/a |
| Ghosting | 14.94444 | 15.13333 |
| Edge detection | 14.73684 | 14.96607 |
| Background Subtraction | 14.98876 | 14.87273 |
| Background Generation | 15.02326 | n/a |
| TransCloak | 14.80000 | n/a |
These results are somewhat surprising, as because MMX allows
us to do operations eight pixels at a time, we would expect it
to be faster, but in many cases the plain C was faster. These
results don't seem very trustworthy, however, as
TransCloak which combines two Ghostings and a
Background Generation is faster than both of them. And
Through is the slowest of all, even though it is doing
something that all of the others do as well. This makes me
suspect that the limiting factor is not the speed of the
algorithm but the framerate of the camera and that this
framerate is inconsistent.