4
$\begingroup$

As a novice to digital signal processing I have a scenario that probably seems trivial but I dont know the answer to. I want to detect when a signal changes but ignore noise.

255 255 255 255 255 210 180 170 140 130 130 130 130 130 130

In the above signal there is a constant 255 value then it changes to a constant 130 value (with some noise in between). Is there a signal processing technique that can detect this, ie, it ignores noise and just detects the constant signal? Note the noise can persist for a while but we will always eventually get back to some constant signal value.

Context: I am learning computer vision as a hobby. My example signal represents grayscale intensity values (0-255). I want to detect the mode change, ie, detect when the most common value being seen changes whilst ignoring noise. I am aware of image gradients and gradient magnitudes identify areas of rapid signal change. However my signals wont always have a rapid change, they will always however have constant signal values between the change/noise. But this noise could be short or very long. Also the difference between the constant values could be very small or very larges. So it could go from constant value 255->240 or 255->0.

$\endgroup$
  • $\begingroup$ do you need to detect a constant value that presently has noise added to it? what if your virtually constant 130 had a few values of 129 and 131 sprinkled in there? maybe you need a median filter. $\endgroup$ – robert bristow-johnson Sep 11 '18 at 19:01
  • $\begingroup$ maybe, to deal with the 129 and 131 crapping up the constant value of 130, you need a "dead-zone" in there. $\endgroup$ – robert bristow-johnson Oct 11 '18 at 23:02
  • $\begingroup$ Sorry but your data does not represent noise but transients, and they are completely other things... $\endgroup$ – Fat32 Oct 12 '18 at 21:23
3
+500
$\begingroup$

As @AlexR mentioned, the digital 1st order derivative is the most straight forward and probably the most trivial solution to the problem, depending on what your signal looks like and the rate of changes involved between samples. The derivative can then be processed in a sliding window to find where it transitions and where it settles (derivative of constant will be close to zero). With these techniques you can reliably detect constants ONLY if the derivative of the signal is greater than the noise amplitude before the signal settles to its constant value. If the rate of change of the signal is slow (i.e. the sample to sample transitions are on the order of magnitude of your noise) then it will be difficult to detect the constant signal from this method. I scale the signals below to be on the same order of magnitude and also take the absolute value of the derivative.

enter image description here

close all
clear all
%signal
x = [ones(1,5)*255 253 251 ones(1,6)*240 240 230 220 200 193 187 180 170 164 140 130 130 120 110 80 ones(1,10)*70 80 95 112 125 137 140 170 180];

%repeat signal
y = repmat(x, [1 5]);

%max value 2^8
MAX = 255;

%noise amplitude
Namp = 5;

%add noise to signal
y = y+randi(Namp,1,length(y));

%1st order derivative 
c = diff(y,1);

%plots
figure
stem(abs((c)/MAX),'color','b')
hold on
plot(y/max(y))
line([1,length(y)],[0,0],'color','r','linewidth',2)
line([1,length(y)],[Namp/MAX,Namp/MAX],'color','r','linewidth',2)
ww = 4
reg = zeros(1,ww)
for i = 1:length(c)-1
  reg = [reg(2:end) abs(c(i)/MAX)];
  if(reg(1) >Namp/256 & sum(reg<Namp/256)>= 3 )
      line([i-ww+2, i-ww+2],[0 1],'color','g','linewidth',2)
  end
end
title({'Red: Signal', 'Blue: Derivative', 'Green: start of constant signal'})
hold off

The signals generated from the derivative algorithm can be used to make a clean piecewise continuous function as seen below. The delay of which, will be a function of your window size-1 sample. enter image description here enter image description here Updated code:

close all
clear all
%signal
x = [ones(1,20)*255 253 251 ones(1,4)*240 255 255 255 255 ones(1,5)*240 240 230 220 200 193 200 220 ones(1,10)*230 210 190 187 180 170 164 140 130 130 120 110 80 ones(1,10)*70 80 95 112 125 137 140 170 180];
%x = [ones(1,5)*130 ones(1,10)*255 ones(1,10)*20];
%repeat signal
y = repmat(x, [1 5]);

%max value 2^8
MAX = 256;

%noise amplitude
Namp =5;

%add noise to signal
y = y+randi(Namp,1,length(y));

%1st order derivative 
c = diff(y,1);
c2 = diff(y,4); 

hold off
%plots
figure
stem(abs((c)/MAX),'color','b')
plot(abs(c2)/MAX,'color','r')
hold on
plot(y/max(y))
line([1,length(y)],[0,0],'color','r','linewidth',2)
line([1,length(y)],[Namp/MAX,Namp/MAX],'color','r','linewidth',2)

ww = 4;
reg = zeros(1,ww);
filtered = []
piecewise =y(1); 
for i = 1:length(c)-1
  reg = [reg(2:end) abs(c(i)/MAX)];

  %if we detect a transition to 0 derivative 
  if(reg(1) >Namp/256 & sum(reg<Namp/256)>= 3 )

      line([i-ww+2, i-ww+2],[0 1],'color','g','linewidth',2)
      piecewise = y(i);
  end
  %if we detect a transition out of 0 derivative 
  if( sum(reg<Namp/256)>= 3 & reg(end) >Namp/256 )
      line([i, i],[0 1],'color','y','linewidth',2)    
      %piecewise = y(i)
  end

  filtered = [filtered piecewise];

end
title({'Red: Signal', 'Stem Plot: Derivative', 'Green: start of constant signal', 'Yellow: end of constant signal'})
hold off

figure
plot(filtered(3:end))
hold on
plot(y)
title({'Red: Signal', 'Blue: Cleaned Signal'})

If we take $x[n]$ to be the input and L to be the window length. First we take the 1st order digital derivative of $x[n]$ to get $\hat{x}[n]$

$$\hat{x}[n] = x[n+1]-x[n]$$

and then we examine $\hat{x}[n]$ in an L length window, noting that when the oldest sample in the window is large (signal is transitioning) and the rest of the samples in the window have settled close to zero (signal is constant) we are at an area of interest (we have found a constant signal after a transition). The longer the window L, the more samples you are considering after the transition before you trigger your algorithm. That is, if you know the signal will settle to a constant for a long period of samples, then choose a big L. If you want the output to transition quickly though, choose a smaller L. We know the smallest transition is zero but will be on the order of $N_{amp}$, the amplitude of the noise. If we scale everthing to the maximum amplitude the signal can be, $A_{max}$, then the newest L-1 samples are on the order of $\frac{N_{amp}}{A_{max}}$ and the oldest sample $x[n-L]$ is some value above that by $\epsilon$

enter image description here

We need to capture this mathematically to say: when the first $L-1$ samples are less than or equal to the noise amplitude and the sample L before is larger than the noise amplitude we have gone from a transition to a constant and the output should be the sample at this instance. Intuitively it seems that:

$$\frac{1}{(L-1)} \sum_{i=0}^{L-1}\frac{|\hat{x}[n]|}{A_{max}} \leq \frac{N_{amp}}{A_{max}}$$

should capture some essence of part of this, but doesn't quite capture that ALL samples in this $L-1$ window should be less than or equal to the noise amplitude.

it's tricky to capture this if-else statement mathematically. One way to get close to a single equation is to say the areas of interest (green lines in my plot) occur when

$$r[n] = \frac{\hat{x}[n-L]}{\frac{1}{(L-1)} \sum_{i=0}^{L-1}|\hat{x}[n]|} > 1 + \frac{\epsilon}{N_{amp}}$$

since the division above expresses:

$$\frac{\frac{N_{amp}+\epsilon}{A_{max}}}{\frac{N_{amp}}{A_{max}}}$$

This works ok, for example if you say you are only interested in $\epsilon$ greater than 5x your noise amplitude, then you get close, but it misses some transitions. It also seems to behave oddly when the window increases.

enter image description here

That is to say

$$y[n] = \left\{ \begin{array}{ll} x[n], \quad & r[n] > 1 + \frac{\epsilon}{N_{amp}} \\ y[n-1], \quad & otherwise \\ \end{array} \right. $$

code to reflect this math:

    close all
clear all
%signal
xx = [ones(1,50)*255 253 251 ones(1,50)*240 ones(1,4)*255 ones(1,10)*240 240 230 220 200 193 200 220 ones(1,20)*230 210 190 187 180 170 164 140 130 120 110 80 ones(1,25)*70 ones(1,2)*256 ones(1,25)*70 80 95 112 125 137 140 170 180];
%x = [ones(1,5)*130 ones(1,10)*255 ones(1,10)*20];
%repeat signal
x = repmat(xx, [1 5]);

%max value 2^8
MAX = 256;

%noise amplitude
Namp =5;

%add noise to signal
x = x+randi(Namp,1,length(x));

%1st order derivative 
xhat = diff(x,1);

L = 5;
reg = zeros(1,L);
filtered = [];
y = [];
y(1:L) =x(1:L)

for n = L+1:length(xhat)-1
  LminusOneSum = 0; 
  for i= 1:L-1
    LminusOneSum = LminusOneSum + abs(xhat(n-i))/MAX;
  end
  r(n) =  abs((xhat(n-L))/MAX)/(LminusOneSum*(1/(L)));

  if(r(n) > (1+6))
      line([n-L+2, n-L+2],[0 1],'color','g','linewidth',2)
      y(n) = x(n);
  else
      y(n) = y(n-1);
  end


end
title({'Red: Signal', 'Stem Plot: Derivative', 'Green: start of constant signal', 'Yellow: end of constant signal'})
hold off

figure
plot(y(L:end))
hold on
plot(x)
%plot(r)
title({'Red: Signal', 'Blue: Cleaned Signal'})
$\endgroup$
  • $\begingroup$ now, can you bring this out a little more with plots of the signal going in and the signal held piecewise constant plotted together? $\endgroup$ – robert bristow-johnson Oct 12 '18 at 18:12
  • $\begingroup$ not sure I completely understand what you mean - do you mean no noise piecewise constant? $\endgroup$ – spet Oct 12 '18 at 18:23
  • 1
    $\begingroup$ Don't know if my updates address your question or not...Let me know. $\endgroup$ – spet Oct 12 '18 at 18:54
  • 1
    $\begingroup$ haha oh god, let me think about $f(x[n])$...fixed the initial condition problem though. $\endgroup$ – spet Oct 12 '18 at 21:51
  • 1
    $\begingroup$ yeah, should have been diving by a $(L-1)$. Didn't quite get to an exact solution, but updated with some thoughts. $\endgroup$ – spet Oct 16 '18 at 19:52
2
$\begingroup$

Another solution that is fairly simple would be to take a digital derivative of your current value, and once that value equals 0 you can compare the signal's current value with the last saved signal value. If it is not the same then you'd save the new signal value and it would trigger what ever behavior you'd want to occur.

$\endgroup$
2
$\begingroup$

In a more generic framework, you are looking for piece-wise regular signals in noise, with very small or very high steps. Moreover, such signals often are not band-limited, so they suffer from aliasing. Here:

  • Your regularity is "constant" but they could be polynomial in general, and related to approximation or modeling
  • Noise is no specified,
  • Unknown jump locations relate to sampling or detection theory,
  • Small or large jumps can add constrains to the problem, related to total variation.

Several other denominations can be searched for, like Piecewise constant Segmentation, Change point detection, etc.

This combines several signal processing topics: assessing regularity, harnessing noise, detecting steps. As far as I know, their combination has no generic solution, and remains an open problem. A few pointers though, to help refine:

$\endgroup$
  • $\begingroup$ These are some helpful resources. Many thanks for sharing them :) $\endgroup$ – Maxtron Oct 13 '18 at 3:01
0
$\begingroup$

The simplest way probably is to look for N consecutive equal values, where you need to choose N according to the nature of the noise. This, however, will results in a delay of N frame.

$\endgroup$
  • 1
    $\begingroup$ you'll need some delay anyway. you can't say "constant value" without time being a component in that measurement. $\endgroup$ – robert bristow-johnson Sep 11 '18 at 19:03
0
$\begingroup$

In your example,

255 255 255 255 255 210 180 170 140 130 130 130 130 130 130

it seems that there is no noise but just the transition between the jump. That is, if noise does exist, there will be fluctuation along all the signal, but the constants ('255' and '130') are quite clean indeed. The transition is due to the fact that, since the ideal sharp jump means infinite spectrum range while practical systems generally have finite frequency respond band, the ideal jump will be smoothed by the system. Then, your problem becomes how to judge the beginning of the jump from the transition. Also, for practical signals, there will be noise indeed.

$\endgroup$
  • $\begingroup$ i'm having some issues with the answer that i was about to award bounty to. i want it to deal with small noise, like ±1 during the constant periods. $\endgroup$ – robert bristow-johnson Oct 16 '18 at 18:46

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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