Signal Matching

At its core, the problem of classifying temporal signals lay in finding segments of temporal signals that recur. These segments could then be used to construct grammars or build classifiers in some way. In other words, the core of the problem is developing an intuition of what makes two temporal signals similar and what makes them different.

Hence, if temporal signals could be ``matched'' against one another in some way to work out parts of the signal that were similar, this could be used in some way for classification purposes.

How can one compare whole signals with one another while looking for patterns? For the moment, let us consider a single channel of data. Two such channels can be compared by creating a 2D image. Each pixel of the 2D image represents the difference between signals at that timepoint. In other words, let $x[t]$ and $y[t]$ be two signals that we are trying to compare. Let $l_x$ and $l_y$ be the length of each of the two. Then for each pixel $a_{ij}$ of the image, let its intensity be determined by $\vert x[i]-y[j]\vert$. This will result in an image - which we will term the signal match image - or SMI for short.

This image is useful for a number of purposes; for instance we could use it to implement a dynamic time warping algorithm by looking at which path from the top right to the bottom left accumulates the least ``black''; in other words, accumulates the least distance. But it is also useful in other ways. Anything that has low difference along a top right to lower left diagonal indicates similarity.

Figure 7.2: The SMI of the z channel of one instance of building with itself.

Figure 7.2 shows what happens when an SMI is created for a signal with itself. In this particular case, it is they z value from the Auslan sign building. In this case, black is used to represent the largest observed difference, and white is used for zero difference. Along the diagonal the signal is of course white, since the difference between the signal and itself is zero.

Figure 7.3 shows an instance of building as against an instance of make. As can be seen, the instances are quite similar, and hence indicates that perhaps the z value is not a good feature to look at for telling signs like building and make apart.

Figure 7.3: The SMI of the z channel of an instance of building and an instance of make.

At the same time as this work was being looked at, many people in the image processing world were encountering mathematical morphology, a means of image processing ideally suited to the purposes of extracting lines from such images. One way to thing of mathematical morphology is to think of each intensity point as a height, where in our case, white corresponds areas of low altitude and black to high. By modelling the flow of water in such a situation, it is easy to work out what the ``valleys'' are; and hence the parts of each signal that are common.

One approach to classification is to to extract typical sub-events corresponding to near-diagonal near-white lines, and then use these labelled sub-events to develop a grammar for each class.