Features of a non-periodic signal for comparison

Question

I am looking for comparing a signal (256 / 512 point discrete | non-periodic ) (obtained after extracting some features from the captured image) with a database of around 5000 signals (256 /512 point discrete | non-periodic)(constructed with the same features as the one in the image). The features are angles and distances from an image captured. The signal is constructed by taking angular value on the x-axis and the corresponding radial distance on the y-axis (amplitude). See the two images.

This image has 15 non-zero points and can be considered as one of the 5000 entries in the database.

Second image - signal acquired:

This image is that of the signal acquired and as can be seen it has 12 non-zero points in the signal. This is actually the corresponding signal of the first image but with some missing points and some variations in the amplitude.

The above is just a example of one of the entries of the database containing 15 non-zeroes and the acquired signal containing 12 non-zeroes. There can be many entries in the database containing the same number of non-zeroes, but the positioning of the non-zeroes will, of course, be different. The number of non-zeroes in a particular entry of the database varies from 5 to 50.

Now consider this as a signal to be compared.

There are two bottlenecks - Firstly, the acquired signal contains missing points from its corresponding signal in the database. The missing points can be very high sometimes. This can be viewed as the correlation between two signals can drop from 1 to 0.5 sometimes. Still I can apply correlation and look for the correct signal match.

But, here comes the second bottleneck and that is I do not want to correlate the acquired signal with each and every entry of the database (because it takes a huge amount of time). Instead, I want to shortlist some entries first based on some feature that can be calculated from the signal. This feature can be mean, variance, standard deviation, 3 dB bandwidth, etc. However, this feature must be something that does not vary much in the case that some points are missed as I stated earlier. I also thought of applying FFT on the signal and using some feature such as mean of the absolute value, phase information, etc.

Eventually, I have tried mean, variance, std, power bandwidth, mean of the absolute value of FFT. However, the change is quite drastic and I cannot shortlist to a small number (by small number I mean around 1000). At the same time, as I mentioned earlier, the correlation also drops quite drastically in some cases thus failing to find a match. Do you have any suggestions on how to go about for this problem of comparison when the acquired signal has missing points from the corresponding database signal? Any idea is appreciated! Thanks!

Answer 1

It is just an idea but how about a mean of the terms in a sliding window.

x = zeros(1,250);
c = randi(50,1,15);
x(c) = randi(500,1,15);
y = x;
d = randi(15,1,3);
y(c(d)) = 0;

figure;
stem(x,'LineWidth',1); hold on; stem(y,'LineWidth',1);
legend('Original Signal','Signal with Missing Samples');

N = 5;
L = numel(x)/N;
[m, m1] = deal(zeros(1,L));

for i = 1:L
    mx(1,i) = mean(x((i-1)*N+1:i*N));
    my(1,i) = mean(y((i-1)*N+1:i*N));
end

figure;
stem(mx,'LineWidth',1); hold on; stem(my,'LineWidth',1);
legend('Mean of x', 'Mean of y');

As you can see the plots are very similar now. You can also check their cross-correlation:

figure;
stem(xcorr(mx,my),'LineWidth',2);

These are of course just ideas to get you started. Now you can play with the window size and instead of doing $1:N$, $N+1:2N$ you can try $1:N$, $2:N+1$ , etc. and replace mean with other statistical parameters to see which one works the best for you.

Hope it helps!

Answer 2

What's wrong with just taking the inner product?

Below is an attempt to generate a database like what you suggest: 5000 signals with 256 coefficients in them, most of which are zero.

In this case, I've set every even numbered signal to be the same as the odd prior odd numbered signal, with just some missing coefficients selected randomly.

The $\color{green}{\bf green}$ circle on the left shows the value of the inner product for the first signal with itself; the $\color{red}{\bf red}$ circle shows the value of the inner product of the first signal with the second (which should be the same, with missing entries).

Running that code takes about 0.298 seconds on a 2010 MacBook Pro (yes, I know, I need a new one).

---

R Code Below

#30451

signalLength <- 256
numberOfSignals <- 5000

database <- array(0,c(signalLength,numberOfSignals))

for (signal in seq(1,numberOfSignals-1,2))
{
  ix <- sample(signalLength,runif(1,min = 10, max = 15))
  database[ix,signal] <- runif(length(ix),min = 400, max = 600)
  ix2 <- sample(ix,10)
  database[ix2,signal+1] <- database[ix2,signal]
}

plot(colSums(database[,1]*database))
points(1,database[,1] %*% database[,1], col="green", lwd=5)
points(1,database[,2] %*% database[,2], col="red", lwd=5)