As a lifetime fan, I was unbelievably excited to hear of the release of a Chick Corea songbook. And then I listened. It only took me a moment before a sinking feeling set in, as I realized that ManTran, one of the best-blending and most in-tune vocal ensembles in recorded-music history, has succumbed to the scourge of modern recording known as “Auto-Tune”. Yes, Manhattan Transfer fans, welcome to the world GLEE and Cher. It’s all over the place on group harmonies, and even rears its ugly head on a few of the solo vocals.

I mean, really. Why ON EARTH would this production choice be made? It takes what are otherwise very hip and adventuresome arrangements, and makes them roboticized, metallic, cold, and inhuman.

It seems to me that it’s one thing to allege that a weekly TV musical is using Auto-Tune, but quite another to level the accusation at four vocal jazz icons.

I am by no means anything approaching an expert on this topic—just an interested fan. But the engineer in me was curious: Is it actually possible to detect the use of Auto-Tune?

First, I did a little background research. Auto-Tune is a tool that can be used to correct the pitch of recorded singing. Evidently it can be used in a subtle or blatant manner; Andy Hildebrand, the inventor of Auto-Tune, says:

At one extreme, Auto-Tune can be used very gently to nudge a note more accurately into tune. In these applications, it is impossible for skilled producers, musicians, or algorithms to determine that Auto-Tune has been used. On the other hand, when used as an effect, such as in hip-hop, Auto-Tune usage is obvious to all. Everything in between is subject to an individual’s unique listening skills.

This raises the question: Assuming that the Manhattan Transfer is attempting to use Auto-Tune in a subtle manner, how can Grobengieser detect its use? (In a follow-up comment to his review, he claims he is “a trained musician with years of experience dealing with vocal group intonation.”) Frankly, I didn’t believe he could detect it, so I decided to try to learn more.

According to one site:

The most important parameter is the retune speed – the time it takes Auto-Tune to glide the note to its perfect pitch. For maximum realism, the retune speed must be set to a value close to the retune speed of the singer’s natural voice. . . . But Auto-Tune’s retune speed can be set to any value right down to zero, which means that notes instantly jump to the exact pitch. This effect is decidedly un-natural. If the singer glides smoothly from one note to another, Auto-Tune will suddenly jump from one note to the next when the mid-point between them is reached.

I believe you can hear the un-natural Auto-Tune effect with a zero retune speed in this Cher song, which according to various web sources also seems to be the first use of Auto-Tune as a sound effect (in 1998).

But let’s assume that the Manhattan Transfer is trying to hide the use of Auto-Tune, in which case their recording engineer would presumably use a retune speed that approximates a “natural” value.

Hildebrand’s original patent for Auto-Tune, also from 1998, has a relatively clear explanation of his invention and how it works. (In my experience, the technical clarity is unusual for a patent!) If you’re interested, I recommend the discussion from the middle of column 3 to the middle of column 6.

I wondered if possibly we could detect Auto-Tune because the notes would be too perfect. The song “500 Miles High” begins with an a capella intro in which it is easy to isolate the first note sung by Janis Siegel. I brought this song into Audacity and zoomed in to the first one second of the left channel, and then selected Analyze > Plot Spectrum.

This is a reasonably crude method, but if you can use it at a point in the music where you can isolate a single voice, it can show some interesting information. Above, if I’m remembering my music theory class correctly, you can see that Siegel is singing an “A”. You can see the fundamental in the first peak, which is highlighted with the thin vertical line in the screenshot above. To the right are all the harmonics.

As you can see, the plot shows that Siegel didn’t hit a perfect “A”—that would have been at 220 Hz. Instead, she’s at 216 Hz, which would be noticeably flat. I am definitely no expert, but I’m thinking that if you’re going to use Auto-Tune, why not get the note correct?

There is a similar intro to the Manhattan Transfer song “Gentleman With a Family” from 1991’s The Offbeat of Avenues. I picked this song because it starts out similarly to “500 Miles,” and also because 1991 puts it well before Auto-Tune would have been in use. In this case, the intro isn’t a capella, so there is some instrumentation playing and thus it’s a little harder to isolate just the singer’s voice. However, selecting the left channel from 20.5 to 21.5 seconds in this song yields the following frequency analysis:

I am pretty certain that the highlight is again on the fundamental of Siegel’s voice—she is hitting a C at 262 Hz. (I believe the peaks to the left are lower tones from the instruments.) Here, before the days of Auto-Tune, she’s dead-on. Of course, she was also 19 years younger!

There are many more sophisticated methods of analysis that suggest themselves. It would be interesting to plot the frequencies over time—perhaps a voice held on a long note without any variation would be a likely indicator of the use of Auto-Tune. If we could isolate each singer onto a separate voice track, it would even be possible to run the pitch detection portion of the Auto-Tune algorithm; if this indicated that tuning was necessary, it would probably be a good clue that Auto-Tune wasn’t used in the studio. My colleague Kevin Gross suggested looking at the vibrato and timbre, because vibrato is removed altogether by Auto-Tune (and then artificial vibrato is usually added back in, according to the patent), and timbre would be changed when samples are added or dropped as part of the tuning process.

Obviously, I can’t really conclude anything from what I’ve done so far. In his Amazon review, Grobengieser doesn’t specify where he thinks he hears Auto-Tune on The Chick Corea Songbook; possibly he’s not talking about the intro to “500 Miles”. Or possibly my analysis tools are not sophisticated enough to detect the use of Auto-Tune. Or possibly if you are an audio engineer trying to sneak a little Auto-Tune into a jazz recording, you are smart enough not to correct to the exact pitch. I have no idea. To my ears the Transfer occasionally sounds just a little off-key on this album, which I ascribe to their age (but it also argues against the use of Auto-Tune). Again, though, I’m no expert.

I’d welcome your thoughts in the comments!

Howdy Pierce is a managing partner of Cardinal Peak with a technical background in multimedia systems, software engineering and operating systems.

Among the list of software patents that Oracle has decided to sue Google with are two that I’m fairly certain that I wrote prior art for. This was in 1983 or 1984, while I was a high school student. This work was published in a book by the University of Oklahoma press, and I believe I still have a copy somewhere.

It seems that the bar for patents is not very high if patents are granted for something a high school student could come up with a decade earlier!

In ’83 or ’84, I wrote a hybrid interpreter/compiler for a Forth-like language.

I had read the book Threaded Interpretive Languages: Their Design and Implementation and decided to write such a language for my TRS-80 model 1. I gave it the snappy name, TIL16U, which stood for Threaded Interpretive Language, 16 bit unsigned ints. The only numeric datatype was the 16-bit unsigned integer, which also nicely represents a pointer datatype on the Z-80 processor.

I took a slightly different approach to writing the language than the book described. Initially I wrote a simple single-pass compiler from the source language to a simple bytecode in TRS-80 Level II BASIC.

Once I could generate bytecode from ASCII source, I wrote an interpreter for it in Z-80 assembly. The interpreter for such a simple stack based language is very small, and it was dwarfed by the inclusion of a text editor (incorporated from an article in 80 Microcomputing with a source listing) and cassette I/O routines to load/save my programs off to tape. I used the initial compiler written in BASIC to compile the runtime library for my interpreter.

My library data structure consisted of a routine name stored as an ASCII string, a length, a flag to indicate whether a given routine was implemented in Z-80 machine code or in bytecode, and then the routine body. While interpreting, the TIL16U interpreter would look at the bytecode for a call routine, and following this would be a routine name. The interpreter would look up the routine name in the library, and either jump to it directly (if it was in machine code), or continue interpreting at the start of the routine (if it was in bytecode).

At the time, I was very interested in writing videogames—my parents wouldn’t allow me to have an Atari 2600—and the 1.77 Mhz processor on the TRS-80 was not particularly powerful. So the lookup step bothered me performance-wise. I knew I could implement a symbol table and a second pass in the compiler to patch in the addresses of routines, but this made the language less dynamic. I wanted to be able to type in code interactively and have it work, and it was also a hassle to store addresses in the code because whenever I built a new version of the interpreter or the runtime library they might have to change.

So I hit upon the expedient of making the interpreter selectively compile bits of the running program to machine code as it went and overwriting the bytecode with machine code that could be directly jumped to, and pushing the address of the interpreter on the stack so that when a Z-80 RET instruction executed, the interpreter continued executing. I thought it was cool that the more you ran a program, the faster it would go.

In particular, the bytecode to invoke a library routine could be replaced by a three-byte Z-80 CALL instruction (a one byte opcode plus two bytes of address).

So when the interpreter found such a bytecode sequence, rather than execute it, it would look up the symbol address, overwrite it with the machine instruction, PUSH the return address of the interpreter on the stack and then jump to it. In the future, the interpreter would look at the opcode byte and know just to jump directly to the code sequence. (As an aside, it is interesting how much of the Z-80 instruction set is still burned into my brain. I can still remember an unconditional jump, or JP, is 0xC3, and the RET instruction is 0xC9, thanks to writing this code.)

I believe the symbolic routine name to numeric address is the mechanism described in one of the patents in the Oracle lawsuit, granted in 1992, and last updated on April 29, 2003.

Additionally, this patent, also referenced in the lawsuit, covers overwriting virtual machine instructions with native code and executing those instead of the bytecode. This patent was originally filed in 1997, and was last updated in 2005.

I’m not claiming that I have perfect prior art for these two patents—I haven’t even studied them very closely—but I believe the techniques I used are at least highly similar to what is patented. Only a patent court can decide if something infringes, anyway.

I’d like to claim this was entirely because of my brilliance, but I think it is more likely that the US Patent Office has been granting software patents that are so obvious that a reasonably bright teenager with a computer can come up with them.

To finish the story, the most successful application of TIL16U did actually turn out to be video games. My parents bought me a ChromaTRS color video board for my TRS-80 (“with 15 vivid colors!”), and I wrote several games for it, one of which I remember was a parachute jump game, where you jumped out of a plane and tried to land on a target. The plane speed and wind speed would vary, so you had to judge how the windsock was looking to get the high score.

Ben Mesander has more than 18 years of experience—not counting high school!—leading software development teams and implementing software. His strengths include Linux, C, C++, numerical methods, control systems and digital signal processing. His experience includes embedded software, scientific software and enterprise software development environments.

There are several approaches possible for real-time networking under Linux, including RTAI with the RTnet hard real-time network stack.

However, the customer was already using Red Hat Linux servers to perform the signal processing, so we decided to try the less intrusive Red Hat MRG kernel to see if it could be modified to incorporate the desired networking protocol. MRG incorporates many kernel patches to improve real-time performance and lower latency.

Since the timing requirements were so tight, I decided that only an in-kernel implementation was likely to succeed. If the code had to switch between kernel mode and user mode, this would require additional overhead, interactions with the Linux scheduler, and moving the data between the kernel and user address spaces.

I started development by building two server-class Linux machines running Red Hat Linux with the MRG kernel, connected back-to-back with a GbE cable. Then I wrote a user-mode test program to send an Ethernet packet of the appropriate type via a raw socket. I now had a way to send a packet from one machine to another. I set up Wireshark to monitor the traffic between the two machines

Initially, I attempted to modify the device-independent portion of the Ethernet stack within the Linux kernel to detect the incoming packet and respond to it. Unfortunately, I had to discard this approach when I found it could not meet the customer’s latency requirement.

So I experimented with modifying the Ethernet drivers for various GbE PCIe Ethernet cards in the MRG kernel. The basic approach I took was to invoke the outgoing packet interrupt service routine from the incoming packet interrupt service routine. The driver has to be in just the right state for this to work correctly, so it required some study of the driver source code. Fortunately most Linux Ethernet drivers share some common framework, so it did not require a complete re-engineering effort to try different cards, but there are definitely some differences.

I initially started with a Realtek card and driver, and had some success. I installed the kernel driver on both machines, so that once I sent a single packet from one machine to another via my user-space program, the two machines would continuously exchange Ethernet frames with each other at the maximum speed achievable.

This made measurement challenging because my modifications to the driver were at a low enough level that the outgoing packets did not go through the device-independent Ethernet stack in Linux, and thus were not captured by Wireshark; and additionally, Wireshark was too slow to keep up and often dropped packets. I was, however, able to use tcpdump to capture packet headers to a file and then look at them later with Wireshark to make measurements. The latency could be estimated by looking at the inter-packet timing from packets sent by the other machine and dividing by two. Using tcpdump mostly got rid of most of the packet losses, but it would still sometimes drop some. I resorted to putting a serial number in each packet which I could then examine to determine if I had lost a packet or not.

I also tried inserting a GbE switch between the two machines and monitoring packets from a third machine. However, I found the switch introduced 20 μsec of additional latency on average, and greatly increased the deviation of the measurements. And still, sometimes packets were lost. So I discarded this approach and used tcpdump running on one of the machines being tested.

I was unable to reliably meet the 74.4 μsec spec under load with the Realtek card, so the next card I tried was an Intel GbE card. This card used the Intel e1000e driver, which is supported directly by Intel rather than the reverse-engineered driver the Realtek card used. Unfortunately I was unable to find a card supported by the version of the e1000e driver contained in the MRG kernel, so I downloaded the latest Intel driver. This driver was significantly more complex than the MRG version of the driver, and I made some measurements.

Finally, I modified the Broadcom bnx2 driver in the MRG kernel. This driver is directly supported by Broadcom. I was able to use the MRG kernel driver with my card, and so I made appropriate modifications.

I found this card, like the Intel card, was also able to keep up with the desired data rate. The Broadcom card ended up having slightly lower latency measurements than the Intel card. I suspect this is due to the MRG kernel driver for bnx2 having less locking overhead and shorter code paths than the stock Intel e1000e driver.

In the end, with the Broadcom bnx2 driver with my modifications, we achieved an average latency measurement of 58 μsec, which was comfortably under the 74.4 μsec requirement. Additionally, we tested continuously over a several day period, monitoring for missing packet serial numbers, and none were detected.

The customer’s initial protocol required sending several smaller packets in either direction, but ultimately an additional speedup could have been realized by using jumbo frames. RTAI/RTnet could also have been used, but I do not think it would have been significantly faster, although it may have reduced the variability of the latency.

Ben Mesander has more than 18 years of experience leading software development teams and implementing software. His strengths include Linux, C, C++, numerical methods, control systems and digital signal processing. His experience includes embedded software, scientific software and enterprise software development environments.

Using four studies, Kortum, along with co-author Marc Sullivan of AT&T Labs, showed 100 study participants 180 movie clips encoded at nine different levels, from 550 kilobits per second up to DVD quality. Participants viewed the two-minute clips and then were asked about the video quality of the clips and desirability of the movie content.

Kortum found a strong correlation between the desirability of movie content and subjective ratings of video quality.

(The original paper seems to be here, beyond a pay wall.)

Makes me wonder about the classic test footage with the calendar and the model train!

Recently, it occurred to me that since Flickr allows short movies (up to 1:30 long), maybe I could create a single-frame movie with the still picture as the frame and the audio as the sound track. Then the Flickr movie player would serve as the control for the audio, and the audio and the video would stay associated with each other.

I decided to try to use ffmpeg to create the movie, since it seems to be able to do almost anything with video and audio. The command line for ffmpeg is a bit obscure, so this blog post documents about two hours of my time spent getting it to work.

My camera produces 3648×2736 JPEG images, and the audio files are 8 kHz sample rate, mono, 8 bit unsigned PCM samples in WAV file format. I decided my goal would be to create a motion JPEG (MJPEG) encoded AVI file with maximum quality.

I started by searching the web to see if anyone had done this before. By studying those examples and experimenting, I came up with the following ffmpeg command line:

ffmpeg.exe -loop_input -shortest -f image2 -r 0.25 -i P910033.jpg -i P910033.wav -vcodec mjpeg -qscale 1 -t 4 foo.avi

Most of my attempts caused ffmpeg to hang. But eventually, I got the error message below:

Duration: 00:00:04.00, start: 0.000000, bitrate: N/A

Stream #0.0: Video: mjpeg, yuvj422p, 3648x2736, 0.25 tbr, 0.25 tbn, 0.25 tbc

[wav @ 01a80050]Estimating duration from bitrate, this may be inaccurate

Input #1, wav, from 'P6060033.wav':

Duration: 00:00:04.02, bitrate: 64 kb/s

Stream #1.0: Audio: pcm_u8, 8000 Hz, 1 channels, u8, 64 kb/s

[mp2 @ 01ac6310]Sampling rate 8000 is not allowed in mp2

Output #0, avi, to 'foo.avi':

Stream #0.0: Video: mjpeg, yuvj422p, 3648x2736, q=2-31, 200 kb/s, 90k tbn, 0

.25 tbc

Stream #0.1: Audio: mp2, 8000 Hz, 1 channels, s16, 64 kb/s

Stream mapping:

Stream #0.0 -> #0.0

Stream #1.0 -> #0.1

Error while opening encoder for output stream #0.1 - maybe incorrect parameters such as bit_rate, rate, width or height

At last I understood the problem: ffmpeg needs the audio sampled at some rate other than 8 kHz. So I decided to use Audacity, another open source application, to upsample the sound. However, now Audacity was unhappy with this audio format.

So I used Project->Import Raw Data, and selected my WAV file. I set up the import with the following parameters:

I knew this would work, because the WAV file format consists of a header, followed by PCM data, in this case 8 kHz unsigned samples. So the result in the audio editor would be an audio file with the WAV header as a noisy sound at the start, followed by the data I wanted. The selected (darker) portion of the WAV file below is the header. I used Edit->Cut to remove it.

Finally, I tried to save the audio at a different sample rate. The audio file has a pulldown menu that lets you change the sample rate, but it doesn’t do what I wanted—what it does is play the audio file back at a different rate with aliasing.

Instead, after consulting the Audacity documentation, I discovered you use the menu in at the lower left corner of the main Audacity window to set the sample rate.

Change this to 48000, and choose File->Export as WAV to save at the new sample rate. I re-ran ffmpeg, and the resulting AVI file would play in QuickTime and VLC player (although VLC crashes afterwards), but it would not work in Windows Media Player (audio played, no video), divx, realplayer, or Flickr. So, I decided to try encoding to mp4 instead with the following command:

ffmpeg.exe -loop_input -shortest -f image2 -r 0.25 -i P910033.jpg -i P910033.wav bar.mp4

The resulting mp4 file plays in all the media players (although, again, VLC crashes after playing it), and Flickr can read it successfully as well. Here is what it looks like on Flickr:

Using size as a proxy for quality, however, the encoded video is much smaller than the input JPEG file. Can someone suggest additional flags to ffmpeg to improve the encoding quality?

Ben Mesander has more than 18 years of experience leading software development teams and implementing software. His strengths include Linux, C, C++, numerical methods, control systems and digital signal processing. His experience includes embedded software, scientific software and enterprise software development environments.

The Orton effect was originally achieved by taking two photos: a well-focused image that was overexposed by two stops, and an out-of-focus image of the same scene that was overexposed by one stop. These were then printed as slides and sandwiched together to produce the final image.

With digital photography, one way to achieve this effect is to shoot a single raw image of a scene. The raw image can be developed to two JPEGs, one at +1 EV (Exposure Value), and the other at +2. My script blurs the +1 EV image with a two dimensional Gaussian filter with a standard deviation of 40 pixels, loads the second +2 EV image, sharpens it with an unsharp mask, and then overlays the two images. There are a variety of ways the images can be overlaid, but I prefer to multiply them, which enhances the color saturation in light areas. This is done by the Gimp by calculating (blur layer × sharp layer) / 255, which results in the image darkening, and an increase in color saturation.

Original

Orton

My Gimp script to do this is available on the Gimp plugin registry.

The soft focus of the colors and the sharpness of the image got me thinking: Is the Orton effect really equivalent to heavily subsampling the chroma channels of the image, and sharpening the luma channel? JPEG and MPEG compression both make use of the fact that the human eye is not as sensitive to chroma (color) as it is to brightness (luma). Typically, both still and video compression uses 4:2:0 chroma subsampling to reduce the number of bits used to represent color information in compressed images without a perceptible quality difference to the human visual system.

I decided to test my theory. It turns out the Gimp has the ability to decompose an image into its YCbCr luma and chroma components used in the JPEG and MPEG compression process.

Original

Y

Cb

Cr

Once I had the image split into its separate components, the Gimp allowed me to apply my Gaussian filter to just the Cb and Cr components, and then regenerate a new color image from the components.

A Gaussian filter applied to just the chroma planes

The same picture using the Orton effect plugin above

Unfortunately, as you can see, the image is nothing like the image that underwent Orton processing—my intuition was wrong. However, it is interesting to see just how much one can low-pass filter an image without a huge impact on the image. I increased the standard deviation of my Gaussian filter from 40 pixels to 100 with the following result—the image is still recognizable and doesn’t look too bad, although the color bleeds outside the lines. It’s interesting to note that the resulting JPEG is also smaller because the low-pass filtered chroma information is easier to compress.

A 100-pixel Gaussian filter applied to the chroma planes

Additionally, it is interesting to see what happens if we decompose our squid into RGB components instead of YCbCr and filter two of them with a 100-point deviation Gaussian filter.

A 100-pixel Gaussian filter applied to two of the three RGB planes

Yuck. We can clearly see the advantage of chroma subsampling here over RGB subsampling.

First, we need a simple model of a lens. Consider the diagram below:

In this picture, the long horizontal line that passes through the center of the lens is called the lens axis. The lens has the property that rays that pass through the center of the lens are undeviated. Therefore, the ray from the top of the tree, at a distance l to the left of the lens, passes straight through the center of the lens. (The tree has a height of h.) The lens also has the property that rays that arrive perpendicular to the lens are refracted to pass through the focal point of the lens. The focal point lies on the lens axis and is a distance f from the center of the lens. The intersection of these two rays shows where the image of the tree will be formed. You can see that the image of the tree is upside down, and has a new height h’. The image is formed a distance d to the right of the focal point.

By using similar triangles we see first that

Using a different pair of similar triangles we also see that

Solving the first equation above for h’, substituting the result into the second equation and simplifying, we derive the following relationship:

This is the fundamental equation of a simple lens. It shows that as the object gets further and further from the lens, i.e. as l increases, the distance of the image of the object from the focal plane decreases, i.e. d gets smaller. We can assume that the camera’s image sensor is located at a distance f from the lens, is perpendicular to the lens axis, and that all objects more than a certain distance away from the lens will be in focus. In other words, the image of all sufficiently distant objects will appear on the focal plane where the image sensor is located.

In the case of 3D video, two cameras are used to acquire a sequence of stereopair images, one from the left camera and one from the right. Different stereo geometries are possible, but the most common one is to place the two cameras horizontally apart from each other by a distance i, and to keep their focal planes coplanar. The diagram below illustrates this configuration:

The horizontal line at the bottom is the focal plane; it is clear from the diagram that the focal planes are coplanar. The lenses are a distance f from the focal plane and are separated by a distance of i from each other. We assume that a small object (or a point on a larger object) is located a distance l from the lens plane and a distance m to the right of the axis of the right lens. We want to know where the image of that object appears in the left and the right camera. In particular, we want to know if we overlaid the left image on top of the right image, how far apart would the images appear? Mathematically, we want to know the disparity, which we define to be

where s1 and s2 are the distances from the image point to the intersection of the lens axis with the focal plane for the left and the right cameras respectively. Note that we are assuming that the object being imaged is far enough away that its image forms on the focal plane.

Using our favorite trick of similar triangles we have the following two equations:

and

Solving the first equation for s1, the second equation for s2, taking the difference and simplifying yields

Although this expression was derived for an object to the right of the axis of the right camera, it is easy to show in a similar manner that it is also true for an object between the axes of the two cameras as well as for an object to the left of the axis of the left camera.

So what does this equation tell us? First, it says that for this particular camera geometry, the disparity is only a function of the separation between the two cameras, i, and the distance of the object from the lens plane, l. Second the equation tells us that the disparity increases as we increase the separation between the cameras. Finally, it tells us that the disparity decreases as the object gets further away from the cameras, approaching zero for objects an infinite distance away. (You can see this when you watch 3D content without wearing the special 3D glasses: The “distant” objects can be seen by the naked eye, whereas the near objects appear blurry to the naked eye, because the value of ρ is greater.)

It should be clear from this equation that if a stereopair is available, and corresponding points can be found in the left and right pictures, that the disparity between those points can be measured, and the distance to the point can be computed.

Mike Perkins, Ph.D., is a managing partner of Cardinal Peak and an expert in algorithm development for video and signal processing applications.

You can’t escape the fact that it takes money to create a low cost product. It is estimated that the first version of the iPhone had COGS (cost-of-goods-sold) of around $200. That is very impressive given all of the included features. However, it is also estimated that Apple spent around $150M over 30 months to design the iPhone. In addition to that direct investment, Apple was also able to entice their component vendors to spend huge amounts of money to design custom ICs for the device.

Our clients typically do not have that kind of money to invest in a new product. (Although please give us a call if you do!) And even if they did, it often doesn’t make business sense to invest a lot of money in upfront engineering in order to reduce COGS, unless you have high volumes. So it’s more typical that we are performing a balancing act between the budget available for engineering, and meeting the target COGS that is necessary for a successful product.

Here are some guidelines that we use to keep development costs low and still create cost-competitive products.

• Start with solid requirements definition.

The most successful design projects start with clear product requirements. Starting a project with known requirements (and not changing them during the product design phase) is the best way to minimize development costs. Of course, most projects aren’t so lucky as to have perfectly defined requirements. It usually takes the management team some time to balance the requirements, development cost targets, product cost targets, and project time-lines. Still, the more quickly you can define what the product has to do, the less the engineering team will thrash—and thrashing costs money.

• Keep the schedule short.

This is pretty obvious, but the longer a project takes, the more it costs. We’re big believers in rapidly getting a solid, but perhaps less-fully-featured, product to market. In addition to keeping development costs low, this strategy also allows you to quickly gain feedback from the market and focus investment for an enhancement release on the most important areas.

• Hire an experienced design team.

An experienced design team will put together a more accurate project schedule and budget, is more likely to meet the project deadlines, and is better prepared to overcome the inevitable hurdles along the way.

• Explore the trade-offs between custom hardware design and using off-the-shelf components.

For low to mid-volume products, using off-the-shelf subsystems and components can be a very tempting way to reduce development costs. However, off-the-shelf subsystems (such as single board computers, power supplies, cases, etc) can be quite a bit more expensive than custom designed hardware. It is worth a thorough investigation of what solutions might exist to reduce your design effort yet still meet the product cost targets. Small hardware vendors may be willing to modify their products to fit your application and costs, and may not charge NRE to do this. As with all vendors, negotiating goes a long way towards minimizing your costs.

• Put together a hardware prototype early in the project.

In most product development projects, the software effort is larger than the hardware effort. As such, we structure projects to give the software engineers as much time as possible to work on the target hardware. This maximizes the time available for low level hardware and software bugs to be found and resolved.

• Start with reference designs and evaluation boards where possible.

Most semiconductor products have reference designs and evaluation boards available to give you a head start. For a low-volume product, these designs can be especially helpful to minimize development time.

• Use the vendor Field Application Engineers

IC vendors usually have FAEs that will help integrate their products into your design. FAEs are usually willing to do schematic reviews, help with software drivers, and even help debug parts of the system if necessary. These folks increase the chance of a successful first revision design and can reduce the development time of a product.

• Use open source software where possible.

We are big advocates of open source software here at Cardinal Peak. There is huge opportunity for reducing the development time and costs in a project by using open source modules. However, it is not easy to properly integrate open source software (especially real-time or embedded modules) into a complex product. To properly take advantage of the open-source benefits, a team that has experience with this is imperative.

Mike Deeds is an expert in embedded systems hardware and software engineering, including FPGA design and computer architecture.

Most of the demos I saw were nothing more than “here, put on these glasses”…in other words, “me too” type demos. (Although after seeing all this 3D interest I did wonder if Philips regretted terminating their auto stereographic display effort last year!).

Nevertheless, I did see two problems addressed that I found technically interesting. First, real-time 2D to 3D conversion (see here and here), and second, automatic 3D quality monitoring.

I worked a lot on the problem of compressing stereopairs as part of my Ph.D. research, and I also spent time thinking about 3D video quality assessment. However, I had never considered the problem of real-time 2D to 3D conversion, so the show got me thinking. It’s a pretty tricky problem!

Converting a 2D video stream to 3D can be partitioned into two fundamental steps. First, creating a depth map for each video image, and second, using the depth map to construct a second viewpoint. Although both steps are challenging, the first step feels substantially harder to me.

With regards to the first step, a sequence of 2D video images must be analyzed to extract a depth map. Several special cases are worth discussing, but I’ll only mention two. First, consider the case where the camera is stationary and a 3D object moves through the field of view. The closer points on that object will have frame-to-frame pixel displacements that are larger than those for object points that are further away. Therefore, one useful approach for deriving information for a depth map would be the following: a) segment the image into two regions: moving and stationary; b) segment the moving areas into distinct objects using various clues such as color and proximity; c) find distinct matching points on the moving objects in two different frames; d) determine depths for those matching points based on the measured point displacements; e) interpolate the depth map for non-matched moving object points.

As a second special case, consider the situation where nothing is moving in the video sequence for many frames in a row. In this case, occlusion becomes a major depth cue. If one object is in front of another, then it will occlude the background object, and it must be closer. If an image can be segmented into objects, and an occlusion map can be deduced, then different depths can be assigned to different objects based on where they lie in the occlusion map. Other clues that may be algorithmically exploitable could stem from perspective considerations applied to the edges of identified objects.

Many powerful depth clues will be hard to take advantage of algorithmically—although humans can exploit them easily—because they involve recognizing objects. For example, we can easily recognize two humans in a picture, and determine whether or not they are adults or children. We know that if two adult males appear in the picture, and one appears substantially taller than the other (and isn’t holding a basketball), then the shorter one is further away. I suspect that taking advantage of this sort of knowledge is beyond the capability of today’s real-time (and non real-time!) processing. Nevertheless, I was amazed at how well the systems I saw at the show appeared to work.

With regards to the second step, given an image and a depth map, a second view can be created from the first by displacing each pixel of the original image with a disparity value corresponding to its depth. In practice it won’t be that easy. Why? Because after displacing pixels with their appropriate disparities, gaps will appear in the new image. These gaps result from image detail that is visible in one image but not in the other, so the gaps will need to be interpolated or otherwise synthesized in some reasonable way.

With regards to 3D video quality assessment, I just want to interject a note of caution. I was encouraged to see that several vendors have made progress in developing systems that automatically approximate the “mean opinion scores” that subjective human evaluation tests would assign to various image sequences. However, when dealing with 3D video, the sum is greater than the parts. If the algorithmic approach implemented is to naively apply 2D image quality assessment to the left and right pictures independently, and then average the scores together, the result is likely to not correspond at all to a human’s subjective viewing experience. For those of you who wear glasses, like me, you can experience this directly if one of your eyes is better than the other. Take off our glasses, look at the world around you, and you will see it with the resolution of your better eye; but you will still have stereoscopic vision. This effect will ultimately need to be taken into account in automatic systems that purport to algorithmically assess the quality of a 3D image sequence.

Although I did this with the iPad, the technique below is not specific to it; you could use the approach below to capture network traffic to any Wi-Fi-enabled mobile device, like an iPod Touch or a Palm Pre.

An easy way to do this is to configure a computer to serve as a bridge between an Ethernet network and an ad-hoc Wi-Fi network. Then, by running Wireshark or another network sniffer on the computer, you can capture the packets as they flow through to the mobile device on Wi-Fi.

My computer is a MacBook Pro running OS/X 10.6 “Snow Leopard”, but the same concept should work on Windows or on earlier OS/X versions, although the dialogs might look a little different. There are three steps:

• Configure the computer to act as a Wi-Fi Bridge
• Connect the iPad to the computer’s ad-hoc Wi-Fi network
• Capture the packets

Step 1: Configure OS/X as a Wi-Fi Bridge

First, we need to configure OS/X as a Wi-Fi bridge. To do this, select “Create Network…” from the Airport drop-down menu. This dialog appears:

Type a network name, and, if you like, assign a password. I assigned a password just so I could ensure that only one device was connecting to my bridged Mac. We are nerds here at Cardinal Peak, so we tend to have a lot of devices floating around our office!

At this point, the iPad would be able to connect to the computer, but the computer is not yet configured to bridge the packets from the 802.11 network onto the Ethernet network. To configure bridging on OS/X, you need to turn on what Apple calls “Internet Sharing”. Go to System Preferences and select the “Sharing” option. Turn on Internet Sharing, and set it up to “Share your connection from” “Ethernet”, “To computers using” “AirPort”:

Step 2: Connect the iPad to the ad-hoc Wi-Fi network

Next, you’ll need to configure the iPad to connect to the ad-hoc Wi-Fi network you just created. This is pretty easy: Go to Settings, and then Wi-Fi. You should see your new ad-hoc network in the list—in my case, I’m looking for “HowdysNetwork”:

Just tap on the ad-hoc network. If you elected to use a password, you’ll be prompted for it.

You can confirm your iPad’s network configuration by tapping the right arrow next to the network name:

Good—we have an IP address, but more importantly we have reasonable entries for Router and DNS server, as well.

Next, you should test out your bridged network connection by bringing up Safari on the iPad and proving you can visit a web site.

Step 3: Capture the Packets

The final step is to start up Wireshark on your computer and attach to the Wi-Fi interface. You normally need to start Wireshark as the super-user in order to have enough rights to capture traffic. There’s probably a cool way to do this graphically, but being an old-school Unix guy, I always bring up a Terminal window and type sudo wireshark &.

We want to capture packets on the Wi-Fi interface, which on my Mac is device en1. Click the leftmost button on the Wireshark toolbar, and then click “Start” next to device en1:

Now you should be all set—do something on your iPad to cause network traffic, and confirm that you see it showing up in the Wireshark window!