2
$\begingroup$

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.

enter image description here

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

Second image - signal acquired:

enter image description here

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!

$\endgroup$
  • $\begingroup$ Hi Deval, the problem you are stating seems very crude. please refine it a bit(maybe what kind of images/features). $\endgroup$ – arpit jain Apr 29 '16 at 4:43
  • $\begingroup$ Hi Arpit, thanks for the suggestion. Added an image of the two signals for the reference. $\endgroup$ – Deval Mehta Apr 30 '16 at 9:43
  • 1
    $\begingroup$ Could you not just export the figures e.g. as PNG and use them here? it's really not that handy to have a screenshot that contains a lot of unrelated GUI. Also, please structure your question more clearly – add paragraphs, highlight core questions, use enumerations $\endgroup$ – Marcus Müller Apr 30 '16 at 20:25
  • $\begingroup$ @MarcusMüller: Clarified the question. Hope now it is clear! $\endgroup$ – Deval Mehta May 4 '16 at 4:53
1
$\begingroup$

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');

enter image description here

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');

enter image description here

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

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

enter image description here

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!

$\endgroup$
  • $\begingroup$ The idea that you have provided is interesting. I have tried for the initial mean window that you have described in the answer. However, this particular window size and variation does not seem to work. As you said, I need to search for some other parameter and a different window function which will be suitable for my problem. Only testing will tell if the different window functions that I try will be able to solve the problem. If you do have anything else in mind, please suggest. $\endgroup$ – Deval Mehta May 12 '16 at 7:25
  • $\begingroup$ @DevalMehta: Have you tried interpolation? $\endgroup$ – Amal Mar 21 '17 at 18:24
  • $\begingroup$ The idea of sliding window and extracting a feature (such as mean, median, variance, etc.) could not work. It also had the same issue as other ideas - the feature that got extracted changed a lot because of the missing data. By interpolation, I am not clear what do you suggest? Interpolate the points in the missing samples signal to predict the samples already missed? $\endgroup$ – Deval Mehta Mar 23 '17 at 1:09
  • $\begingroup$ Yes. Take a look at: mathworks.com/help/signal/examples/… $\endgroup$ – Amal Mar 23 '17 at 14:32
0
$\begingroup$

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).

enter image description here


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)
$\endgroup$
  • $\begingroup$ Peter.K, thanks for the idea, but it doesn't seem to work. The problem is when there are no missing points, it works decent enough. However, when there are missing points, the highest inner product / dot product of the signal with each of the 5000 entries in the database is a wrong one. i.e. some other entry is depicted to be corresponding to the acquired signal which is false. The true corresponding entry gives a small inner product. $\endgroup$ – Deval Mehta May 6 '16 at 5:25
  • $\begingroup$ Odd. That's not what running the R code shows me. Can you confirm that there will be a maximum of 15 and minimum of 12 entries? In the case of missing entries, are there also extra entries? $\endgroup$ – Peter K. May 6 '16 at 10:16
  • $\begingroup$ @ Peter. K, The number of non-zeroes in a particular entry of the database varies from 5 to 50. And the number of non-zeroes in the acquired signal also varies. The above was just an example of one of the entries of the database containing 15 non-zeroes and the acquired signal containing 12 non-zeroes. That is why the inner product creates a problem. 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. $\endgroup$ – Deval Mehta May 9 '16 at 1:39
  • $\begingroup$ @DevalMehta : Thanks for the update. Yes, that would create a problem having such a large variation. I had assumed your example in the question was more indicative of the problem. $\endgroup$ – Peter K. May 9 '16 at 11:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.