EDN logo


Columnist: July 4, 1996

Fuzzy templates—with a twist

David Brubaker,
contributing editor


Every so often, I get caught off guard. Actually, it happens all the time in general living, but it also happens occasionally in engineering. Here's an example. I present it because it shows how fuzziness can be incorporated in a system without rules, but be prepared for a twist at the end that, I admit, I did not expect.

About two years ago, I helped develop a system to classify acoustic time-series "signatures." Figure 1 shows plots of the eight possible signatures—acoustic "whistles" or "chirps," with the names of classical-music composers as code names. The vertical axis of each plot is frequency, which ranges from 1 to 100 kHz (note the log scale). The horizontal axis is time, in milliseconds. There are distinct and detectable start and stop times for each chirp, and no chirp lasts longer than 75 msec.

A different type of emitter generated each signature type. Upon receiving an unknown chirp, the system was required to classify the chirp into one of the eight emitter types. Not belonging to any of the eight designated types was also an acceptable outcome. Filters eliminated most noise prior to the classifier. However, based on emitter power and configuration, and specifics of the transmission medium, the classifier needed to accurately identify signatures with as much as 25% scaling in both frequency and chirp duration. Finally, future versions of the classification method would need to identify as many as 30 signal types.

Initially ignoring the need to handle scaled signatures and because of the relative simplicity and small number of signature types, a simple template-matching scheme seemed appropriate. Traditionally, the principal problem with templates is that they are "brittle"; the transition from a perfect match to a complete mismatch tends to be rapid. I hoped adding fuzziness to the templates would greatly reduce or eliminate this brittleness.

Figure 2 shows a template for the signal type Chopin. It consists of six semifuzzy regions in the time-frequency input space. Each region is semifuzzy because it has fuzzy boundaries only for frequency; time boundaries are crisp.

Signature characteristics determine the placement of time and the frequency boundaries of each region. Selecting the number of regions in the template for each signal type involves a trade-off between the processing time and the ability of the template to accurately discriminate between different, but similar-looking, signature types. In general, you need more regions where the signature changes rapidly (where the magnitude of its slope is great), and you need fewer regions where it does not change rapidly (where the magnitude of its slope is small). Figure 3 shows the membership functions, as functions of (log) frequency, that define regions a and c in the Chopin template.

During operation, an incoming signature is sampled every millisecond. The sample value is applied to all active templates—to the fuzzy region within each template that corresponds to the time of the specific example. For example, when applied to Chopin's template, all samples occurring at time 0<t<=14 msec are applied to membership function a, all samples occurring at time 14 msec<t<=22 msec are applied to membership function b, and so forth.

How well each sampled frequency value fits into the respective template region determines the degree of match, µ. When the frequency sample is a full member of the template region, µ=1. When it is not a full member of the region, µ=0. Between these two values, 0<µ<1, and µ is an indication of how removed the actual value is from the required value.

Combining individual degrees of matching generates a measure of how well an actual signal matches a template. As a combining operator, the fuzzy AND operator is attractive be-cause it may ease implementation but is inappropriate because it drives the result irretrievably to zero for any single time a zero match occurs. A running average is more appropriate. For each µi, the running average, ¯µ1, for all µ through µi is:

¯µ1=[(i-1)¯µi-11]/i

Now for the twist. I wanted to see how much using fuzzy boundaries on the regions improved classifier operation, so I created a crisp-boundaried template for Chopin-type signatures and applied a signal that had a 20% longer-than-normal duration to both fuzzy and crisp templates. Figure 4 shows the results.

Fuzzy and crisp templates performed nearly identically. This result came as a complete surprise to me: I had expected the "softness" associated with the fuzzy boundaries to allow its overall degree of match, µ1, to degrade far less rapidly. I ran the same comparison with other signal types and other templates, always with very nearly the same results.

A little thought provided the reason. Although we were using fuzziness, we were not using fuzzy logic, because we did not use a logic-based operator to combine the degrees of match. The running average, by providing smoothing on the bilevel logic measures, added the same improvement usually gained by moving to fuzzy logic. For this application, fuzziness was not needed for a successful system.

Did we, therefore, step back to a crisp implementation? No, we didn't. The actual matching mechanism was only part of the classifier system. In addition, two feedback loops were added to account for the anticipated 25% scaling in frequency and duration. Both loops had individual values of µ as inputs, not the running average, and we opted to work with proportional, rather than bang-bang, loops. The fuzzy templates remained.

To close, I have a brief administrative matter. I still promise to respond to each reader who writes to me. Most of you write via e-mail, and I respond accordingly. Occasionally, a reader's server bounces back my response as addressed to an "unknown user." This has been the case for several of you. To those who are still waiting for a response, please send me a viable address, and, to all who write, please include your postal address as well. Then, if e-mail fails, I have something to fall back on.


| EDN Access | feedback | subscribe to EDN! |
| design features | out in front | design ideas | columnist | departments | products|


Copyright © 1996 EDN Magazine. EDN is a registered trademark of Reed Properties Inc., used under license.