6
$\begingroup$

I want to segment a signal in an unsupervised manner.
The data is a 1D signal which has different segments which I want to be able to segment automatically for farther processing.

I am looking for a fast and efficient algorithm.

The motivation is get more information on the subject in order to evaluate approaches. So it might be like a general question on how it is done and what are some approaches to do so.

Simple example:

The blue line is a 1D signal plotted against time (x-axis). The algorithm should output the x-values of the two vertical red lines, essentially segmenting the 1D signal.

To make the problem a little easier, it is okay to assume the number of segments are known beforehand (similar to k-means clustering where the number of clusters is an input to the algorithm).

enter image description here

$\endgroup$
5
  • 1
    $\begingroup$ Do you have an example of the signals? $\endgroup$
    – Royi
    Jul 3, 2021 at 14:51
  • 1
    $\begingroup$ Hi Thomas! Nice having you here. However, the amount of info you'd have showed here says "it's always one segment spanning the whole signal" just as much as "there's as many segments in the signal as there are samples". Or, really, any other segmentation. There must be some way a sensible segment is characterized. $\endgroup$ Jul 3, 2021 at 16:14
  • $\begingroup$ The question lacks focus, and as it stands is just a Rorschach blot for the helpful. Please edit your question: Why are you segmenting the signal? What do you want it segmented into? Why do you think that "segmentation in an unsupervised manner" (presumably segmentation using an unsupervised learning algorithm) will work? What do you want to achieve here? $\endgroup$
    – TimWescott
    Jul 3, 2021 at 17:02
  • $\begingroup$ You still need some metric that measures the quality of the segmentation. That would drive any unsupervised learning algorithm. $\endgroup$
    – IanJ
    Jul 3, 2021 at 20:43
  • $\begingroup$ I am trying to write something on this interesting question before it is closed. $\endgroup$
    – Royi
    Jul 4, 2021 at 14:36

2 Answers 2

5
$\begingroup$

This is an interesting question.
For answering it I will assume a time sampled signal.

The way I see it, it something like Image Segmentation where indeed we have many methods which require little or no explicit assumptions.

So, the first things comes to mind it to cluster data by its value. Yet there won't be any significance to the time axis which is probably important. Namely if we have data and cluster it by its values then we can have the same data sampled at different times (Shuffle the samples) and have the same result.
This brings the intuition we need to use the time somehow. One way I found very efficient yet simple to do so is similar to the concept of Super Pixel.
Namely we cluster with one of the coordinates of the clustering data being the time.
The challenge then is to create the proper metric to weigh values vs. time indices.

But even this simple yet effective method, something is missing. On time data the connection is form one sample to another while Super Pixel is from many to one (The center).
So the next step could be something like Spectral Clustering / Graph Based Clustering where we take into account the chain like connection between samples.

$\endgroup$
7
  • 1
    $\begingroup$ This does not provide an answer to the question. To critique or request clarification from an author, leave a comment below their post. - From Review $\endgroup$
    – MBaz
    Jul 4, 2021 at 15:26
  • 2
    $\begingroup$ Rather than trying to subvert the intention of the site, why don't you suggest to the poster how they may improve their question so that it doesn't get closed? Questions get reopened all the time -- after they are brought up to the standards of the group. $\endgroup$
    – TimWescott
    Jul 5, 2021 at 4:02
  • 2
    $\begingroup$ @TimWescott, Maybe because I find the question interesting as it is? If I get, the OP wants people to explain different methods of signal segmentation. I have and idea from Image Processing world which I can think might work nicely. The intention of this site is sharing knowledge by questions and answers. Not trying to teach people how to ask. What's not to understand from the question? It leaves the way to measure the success and the method open. So give something reasonable, explain when it will work and when not and add valuable information. $\endgroup$
    – Royi
    Jul 5, 2021 at 5:09
  • 2
    $\begingroup$ This question isn't much poorer than many others which are answered without closure. If someone's willing to answer, it's added knowledge. $\endgroup$ Jul 5, 2021 at 16:25
  • 1
    $\begingroup$ @PeterK., I'm working on it. $\endgroup$
    – Royi
    Jul 7, 2021 at 16:42
2
$\begingroup$

Royi's answer is a good starting point. However, my first thoughts were the problem is more related to Video-scene segmentation (or more generally Time-series segmentation) rather than Image segmentation.

With a bit of searching I found SO: Time Series Segmentation using Python related question, and a Python library called ruptures. Here's how to detect the three segments in the example in the question using ruptures:

from matplotlib import pyplot as plt
import ruptures as rpt  
import numpy as np

add_noise = lambda arr: arr+np.random.normal(size=len(arr))
pieces = [add_noise([20]*100), add_noise([10]*50), add_noise([-10]*10)]
signal = np.concatenate(pieces)
bkps = np.cumsum([len(ps) for ps in pieces])

algo = rpt.Dynp(model="l2").fit(signal)
result = algo.predict(n_bkps=len(bkps)-1)
rpt.display(signal, bkps, result)
plt.show()

enter image description here

$\endgroup$

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.