Mustererkennung auf Mikrocontroller

[Frank B. (frank501)]

Hallo, zusammen,

ich habe in einem Array aus Bytes die Abfolge mehrerer Eingangssignale 
gespeichert. Jedes Bit entspricht einem Eingang an meinem Controller und 
bei jedem Wechsel eines Einganges wird das Array um eine Position weiter 
geschoben und die neue Bitfolge an erste Stelle geschrieben.


Das sieht dann im Idealfall so aus:
X-Achse: Position des Arrays, Y-Achse: die einzelnen bit. .=low x=high)

bit

b0 ....................
b1 .X..................
b2 ...x................
b3 .....x..............
b4 .......x............
b5 ....................
b6 ....................
b7 ....................

t  01234567891111111111
             0123456789

Dieses Muster möchte ich erkennen. Hier muss ich ja einfach nur die 
ersten acht Positionen des Arrays nach den entsprechende Bitmustern 
durchsuchen, um zu wissen, daß die Eingänge in der entsprechenden 
Reihenfolge ihre Zustände gewechselt haben.

Leider kommen die Signale nicht in der idealen Reihenfolge, sondern 
können sich zum Beispiel überschneiden oder die Pause dazwischen kann 
ausfallen.
Beispiel:

bit

b0 ....................
b1 .X.........x........
b2 ..x........xx.......
b3 ....x.......x.......
b4 .....x......xx......
b5 ....................
b6 ....................
b7 ....................

t  01234567891111111111
             0123456789

Das kann jedes mal anders aussehen und es geht mir auch nicht nur um 
dieses Muster, sondern auch um andere Muster, die vorliegen können. Zum 
Beispiel sowas:

bit

b0 ................................
b1 .x.x.................x.......x..
b2 ..x.x..................x...x....
b3 ..........x..............x......
b4 .........x.x....................
b5 ........x...x...................
b6 ................................
b7 ................................

t  01234567891111111111222222222233
             0123456789012345678901

Auch diese Muster werden nur selten so wie dargestellt auftreten, 
sondern immer etwas unsauber sein.

Da ich mit Mustererkennung überhaupt keine Erfahrung habe, frage ich 
hier einfach mal ganz blauäugig, ob es irgendwie möglich ist, solche 
Muster mit einfachen Mitteln zu erkennen, auch wenn sie nur in 
Grundzügen etwas mit dem gesuchten Muster gemeinsam haben?

Frank

[c-hater (Gast)]

Frank B. schrieb:

> Da ich mit Mustererkennung überhaupt keine Erfahrung habe, frage ich
> hier einfach mal ganz blauäugig, ob es irgendwie möglich ist, solche
> Muster mit einfachen Mitteln zu erkennen, auch wenn sie nur in
> Grundzügen etwas mit dem gesuchten Muster gemeinsam haben?

Nein. Mit "einfachen Mitteln" geht das nicht. Mit geeigneten Mitteln 
hingegen schon. Im Rahmen der prinzipiellen Möglickeiten "unscharfer" 
Entscheidungen. Also nie mit 100%iger Sicherheit.

[Frank B. (frank501)]

Ein eindeutiges Ergebnis erwarte ich gar nicht, sondern eher eines mit 
einer gewissen Wahrscheinlichkeit. Die "Schaltschwelle" ab der ein 
Muster als erkannt gilt, lässt sich ja festlegen.
Die Frage ist: Was sind denn geeignete Mittel?

[Hermann Kokoschka (Gast)]

Aus Deiner Frage geht m.E. absolut nicht hervor WAS GENAU Du denn nun 
erkennen willst.

Frank B. schrieb:
> Das kann jedes mal anders aussehen...
ALSO kann im Array praktisch ein beliebiges Muster stehen.

OK, WAS GENAU möchtest Du erkennen?

[Mustermann (Gast)]

Hermann Kokoschka schrieb:
> Aus Deiner Frage geht m.E. absolut nicht hervor WAS GENAU Du denn
> nun erkennen willst.
> Frank B. schrieb:
>
>> Das kann jedes mal anders aussehen...
>
> ALSO kann im Array praktisch ein beliebiges Muster stehen.
> OK, WAS GENAU möchtest Du erkennen?
Das frage ich mich auch. Wenn eine Position erkannt ist (x), ist dann 
für den Wert entweder ein x drüber oder drunter erlaubt, oder gar 
nichts, oder das original x plus drüber oder drunter? Dann wäre das doch 
einfach zu entscheiden.
Aber zunächst muss mal geklärt werden, was erlaubt ist und was nicht. 
Und wann ein Muster als beendet angesehen wird.

[J. V. (janvi)]

Da empfehle ich dir mal eine Vorlesung in Bildverarbeitung. Die 
Morphologie ist ein riesiges Gebiet. Die Operationen heissen z. Bsp. 
blow und shrink. Vielleicht zeigt Google was an ? Ansonsten könntest du 
auch mal eine Kreuzkorrelation ausprobieren. Geht aber ziemlich auf die 
Rechenzeit. Ich habe das mal mit Excel ausprobiert und festgestellt, daß 
auch Excel einen Wartebalken zur Fortschrittsanzeige hat. Letzendlich 
habe ich das mit Matlab in einer Zeile programmiert. Die Korrelation 
kann man über fft machen und das geht dann "einfach". Der Versuch das in 
ein FPGA zu kriegen hat aber wegen der Auflösung und Resourcen 
gescheitert.

[J. V. (janvi)]

Hier kommt ein Google Treffer:

https://books.google.de/books?id=RNLQBgAAQBAJ&pg=PA303&lpg=PA303&dq=morphologie+blow+shrink&source=bl&ots=NcBxaTHvOn&sig=ACfU3U3dbquAydXzRpBd_kal9RwLUfoRFA&hl=de&sa=X&ved=2ahUKEwjowYKNobD4AhXCSfEDHacSBxIQ6AF6BAgVEAM#v=onepage&q=morphologie%20blow%20shrink&f=false

Das ist mit 1977 zwar schon ziemlich alt und als Anwendung in der 
Medizin. Das was ein Siemens PR330 damals konnte kann ein uC heute auch. 
Es sind auch Verweise auf weitere Literatur und Ausführungen zu den 
Verwendeten (Laplace) Filtern.

[ert (Gast)]

Das macht man heute ganz einfach mit machine learning. Mit Tensorflow 
Lite gibt es inzwischen auch eine inferenzengine für Mikrocontroller. 
Musst Dich halt einlesen.

https://www.tensorflow.org/lite

[J. V. (janvi)]

TensorFlow muß nicht unbedingt besser sein und auch nicht auf einem uC 
laufen. Hier noch ein Link:
https://www.yumpu.com/de/document/read/21290160/materialien-zur-bildverarbeitung-prof-dr-hardy-pundt-

[Frank B. (frank501)]

Hermann Kokoschka schrieb:
> OK, WAS GENAU möchtest Du erkennen?

Ich möchte wissen, ob das gesuchte Muster im Array vorkommt, je näher 
das im Array stehende Muster dem "Original" nahekommt, desto 
wahrscheinlicher ist es, daß es das gesuchte Muster ist.



Mustermann schrieb:
> Das frage ich mich auch. Wenn eine Position erkannt ist (x), ist dann
> für den Wert entweder ein x drüber oder drunter erlaubt, oder gar
> nichts, oder das original x plus drüber oder drunter? Dann wäre das doch
> einfach zu entscheiden.
> Aber zunächst muss mal geklärt werden, was erlaubt ist und was nicht.
> Und wann ein Muster als beendet angesehen wird.

erlaubt oder nicht, sehe ich nicht als die entscheidende frage. Die 
größtmögliche Annäherung an genau das gesuchte, soll auch eine 
größtmögliche Wahrscheinlichkeit (>95%) ergeben, je größer die 
Abweichungen, desto geringer die Wahrscheinlichkeit, daß es das Muster 
ist. Ob da zusätzliche x sind oder welche fehlen, ist dabei egal. Nur 
soll auch ein komplett mit x-en gefülltes Array nicht auch eine hohe 
Wahrscheinlichkeit bedeuten.



Wie erkennt zum Beispiel ein Smartphone ein wischen über den Bildschirm? 
Das läuft ja, ganz grob gesehen, aufs gleiche hinaus, nur daß ich nur 8 
"Bildpunkte" habe und das nur eindimensional, also nur hoch, runter und 
"wackeln" erkennen kann.

[Ein Kommentar (Gast)]

Dazu findet sich einiges unter dem Stichwort: Levenshtein-Distanz

Der Algorithmus stammt aus einer Zeit, als ein Großrechner weniger 
Rechenleistung als ein MC hatte.

[Harry L. (mysth)]

Damit geht sowas:
https://www.st.com/en/embedded-software/x-cube-ai.html

[Jobst M. (jobstens-de)]

Was ist mit neuronalen Netzen?

Frank B. schrieb:
> Wie erkennt zum Beispiel ein Smartphone ein wischen über den Bildschirm?

Das ist eine Bewegung und muss nicht erkannt werden. Sie ist eindeutig.
Man hat exakt eine Position (oder zwei, z.B. bei zoom) und kann die 
Koordinaten problemlos verfolgen.

Gruß
Jobst

[Egon D. (Gast)]

Frank B. schrieb:

> Hermann Kokoschka schrieb:
>> OK, WAS GENAU möchtest Du erkennen?
>
> Ich möchte wissen, ob das gesuchte Muster im Array
> vorkommt,

Das ist, glaube ich, verstanden worden.


> je näher das im Array stehende Muster dem "Original"
> nahekommt, desto wahrscheinlicher ist es, daß es das
> gesuchte Muster ist.

Schön.
Und wie sieht das "Original" in Reinform aus?
Welche Unterschiede sind zulässig?


>> Aber zunächst muss mal geklärt werden, was erlaubt
>> ist und was nicht. Und wann ein Muster als beendet
>> angesehen wird.
>
> erlaubt oder nicht, sehe ich nicht als die entscheidende
> frage.

Aber wir.


> Die größtmögliche Annäherung an genau das gesuchte,

Herrgott.
Und WAS IST "das Gesuchte"?

(Jetzt antworte aber BITTE nicht mit einer Nullaussage
der Art: "Das Gesuchte ist das, was ich suche." Wir
sind nämlich nicht komplett bescheuert -- auch wenn es
manchmal so aussieht.)


> soll auch eine größtmögliche Wahrscheinlichkeit (>95%)
> ergeben, je größer die Abweichungen, desto geringer
> die Wahrscheinlichkeit, daß es das Muster ist.

Ja... soweit ist das selbsterklärend.


> Ob da zusätzliche x sind oder welche fehlen, ist dabei
> egal.

NEIN!
Der Unterschied zwischen einem "F" und einem "x" ist auch
nur der, dass da einerseits ein paar Pixel zusätzlich sind
und außerdem ein paar andere Pixel fehlen.

Man kann aus gestörten Daten die wesentlichen Informationen
gewinnen, das ist möglich -- man kann aber bis jetzt noch
keine Gedanken lesen. Das ist nicht möglich.

So lange Du keine Liste von Beispielen lieferst, welche
Muster dem Original sehr ähnlich sind, welche dem Original
halbwegs ähnlich sind, und welche ganz unähnlich sind,
so lange kann niemand über eine zielführenden Algorithmus
nachdenken.

Im Moment ist Deine Frage auf dem Niveau "Woran erkenne ich
Gott, wenn ich ihm begegne?", und meine Antwort darauf ist:
"Keine Ahnung. Für mich gibt es keinen Gott."

[Ein Kommentar (Gast)]

> so lange kann niemand über eine zielführenden Algorithmus
> nachdenken.

Gibt doch nur 2 Algorithmen.

Der Levenshtein Ansatz. Du berechnest, für jedes Muster die Anzahl von 
Bits, die du einfügen/löschen/ändern musst. Legst die Kosten für 
einfügen und ändern fest. Und nimmst das Muster mit den geringsten 
Kosten.

Und wenn du die Trennung zwischen den Paketen nicht kennst, kombinierst 
du es mit dem sliding window Algorithmus. Nimmst Muster und 
Startposition mit den geringsten Kosten.

Oder du fütterst eine KI mit unzähligen Mustern, die du per Hand 
klassifizierst. Und ein Framework, von dem die Entwickler behaupten, es 
würde das passendste Trainingsmuster auswählen.

Hast du irgend eine Idee für einen weiteren Algorithmus?

[Andreas M. (amesser)]

Ich würde das mit einem mehrschichtigen Perzeptron-Netzwerk versuchen. 
Das es nur wenige Binäre Eingänge gibt kommt man mit einer handvoll 
Neuronen und ohne Multiplikation aus. Die Gewichte müsste man händisch 
festlegen. Ein neuron besteht hier im wesentlichen aus einem Integrator, 
einem Schwellwertschalter und einer Totzeit. Der Integrator kann nicht 
kleiner als 0 werden. Mal so als Startpunkt für das allererste Muster:

struct state {
  int accu[2]; /* <0 -> neuron in totzeit */
  int fire[2];
};

struct state last_state;

#define TOTZEIT 127

void cycle()
{
  struct state new_state = last_state;

  /* neuron 0 signal konditionierung b1 */
  if (new_state.accu[0] < 0) ++new_state.accu[0];
  else 
  {
    new_state.accu[0] = new_state.accu[0] - 1;
    if (b1) new_state.accu[0] = new_state.accu[0] + 64;

    new_state.accu[0] = max(0, new_state.accu[02]);
  }

  /* neuron 1 signal konditionierung b2 */
  if (new_state.accu[1] < 0) ++new_state.accu[1];
  else 
  {
    new_state.accu[1] = new_state.accu[1] - 1;
    if (b2) new_state.accu[1] = new_state.accu[1] + 64;

    new_state.accu[1] = max(0, new_state.accu[1]);
  }

  /* neuron 2 */
  if (new_state.accu[2] < 0) ++new_state.accu[2];
  else 
  {
    new_state.accu[2] = new_state.accu[2] - 1;

    /* Verbindung Neuron 0 -> Neuron 2, Gewicht muss kleiner als Totzeit,
     * Sonst kann Neuron 0 alleine Neuron 2 auslösen */
    if(last_state.fire[0])
      new_state.accu[2] = new_state.accu[2] + 40;

    /* Verbindung Neuron 1 -> Neuron 2, Gewicht muss kleiner als Totzeit,
     * Sonst kann Neuron 1 alleine Neuron 2 auslösen */
    if(last_state.fire[1])
      new_state.accu[2] = new_state.accu[2] + 32;

    new_state.accu[2] = max(0, new_state.accu[2]);
  }  
  
  if (new_state.accu[0] >= 64) 
  { 
    new_state.accu[0] = -TOTZEIT; 
    new_state.fire[0] = 1;
  }
  else
  {
    new_state.fire[0] = 0;
  }

  if (new_state.accu[1] >= 64) 
  { 
    new_state.accu[1] = -TOTZEIT; 
    new_state.fire[1] = 1;
  }
  else
  {
    new_state.fire[1] = 0;
  }

  if (new_state.accu[2] >= 64) 
  { 
    new_state.accu[2] = -TOTZEIT; 
    new_state.fire[2] = 1;
  }
  else
  {
    new_state.fire[2] = 0;
  }
    
  last_state = new_state;

  if(new_state.fire[2])
     ... /* sequenz b1->b2 erkannt */
}

Durch die entsprechende Wahl der Gewichte der Neuronen zueinander kann 
man die Akzeptanzfenster für die Signale festlegen. Wenn man bei Neuron 
2 die Summe der Gewichte (40+32) Größer als 64 wählt, dann wird 
Zeitverschiebungen symetrisch um Mittelpunkt akzeptiert. will man, das 
b2 immer gleichzeitig oder nach b1 auftreten muss, dann muss man noch 
eine verbindung von neuron 0 nach neuron 1 einbauen und die Gewichte 
entsprechen setzen.

Man kann auch die Verbindungen zwischen den Neuronen ein zeitliches 
Abklingverhalten anmodelieren indem man fire wie einen Zähler behandelt 
und mit einem Wert > 1 setzt und dann langsam runterzählt. So kann man 
die zeitliche Symmetrie verschieben.

Ich hoffe mein Kauderwelsch war verständlich.

[Erich (Gast)]

Deine hochgeheime Mustersuche ist nicht allgemein beantwortbar.

I.d.R. sollten eine Muster, z.B. ein Barcode; ein QR- oder 
DataMatrix-Code, auch GANZ EXAKT erkannt werden und nicht nur 
näherungsweise.

Gruss

[Egon D. (Gast)]

Ein Kommentar schrieb:

> Gibt doch nur 2 Algorithmen.

Ich bin etwas überrascht. Warum muss man dann jahrelang
Informatik studieren, wenn es ohnehin nur zwei Algorithmen
gibt...?


> Der Levenshtein Ansatz.

Das Ähnlichkeitsmaß müsste nicht die Levenshtein-Distanz
sein; der (gewichtete) euklidische Abstand wäre auch
ein Kandidat.
Dazu müssten allerdings erstmal das oder die "Originale"
bekannt sein, zu denen die Distanz berechnet werden
kann...


> Hast du irgend eine Idee für einen weiteren Algorithmus?

Naja, einen endlichen Automaten zum Beispiel. Die Anzahl
der Zustände und die Überführungsfunktion muss man so
pimpen, dass bei zulässigen Abfolgen "1" und bei unzulässigen
"0" geliefert wird.

Wenn es nur auf die (fast) periodische Abfolge der
Belegungen ankommt, kann man sicher auch etwas
selbstlernendes basteln...

[Egon D. (Gast)]

Erich schrieb:

> I.d.R. sollten eine Muster [...] GANZ EXAKT erkannt
> werden und nicht nur näherungsweise.

Quark.

Die NUTZDATEN ("payload") sollen exakt rekonstruiert
werden -- aber da das Muster Redundanz enthält, genügt
es in der Regel, das MUSTER nur teilweise zu erkennen.

Wäre ja schlimm, wenn's anders wäre...

[Peter D. (peda)]

Es wäre mal interessant, was die eigentliche Aufgabe ist.
In der Regel wird es extrem kompliziert, wenn man alle Vorinformationen 
verheimlicht und die Aufgabe allgemein formuliert.
Besser geht man den umgekehrten Weg, d.h. erstmal die spezielle Aufgabe 
lösen und später die gefundene Lösung verallgemeinern, soweit möglich.

[Jobst M. (jobstens-de)]

Ich habe ja die Befürchtung, dass er den maximal dämlichsten Ansatz für 
ein Problem gefunden hat und für diesen von uns nun eine Lösung haben 
will.
Ich denke, er möchte eigentlich die Bewegung eines einzigen Bits an 8 
Eingängen verfolgen und auswerten. Die Muster passen dazu. Die Aussage 
mit dem wischen auch.

Es gehört schon etwas dazu, zu glauben, dass das beschriebene Problem 
einfacher zu lösen wäre ...

Gruß
Jobst

[Jester (Gast)]

Peter D. schrieb:
> Es wäre mal interessant, was die eigentliche Aufgabe ist.

Das ist maximal geheim (klassifiziert als STRENG GEHEIM). Auf diese 
Frage wirst du daher eine Antwort nie nicht bekommen.

> In der Regel wird es extrem kompliziert, wenn man alle Vorinformationen
> verheimlicht und die Aufgabe allgemein formuliert.

In der Regel wird es maximal kompliziert, wenn man sich in eine 
Lösungsrichtung verrannt hat, dann nicht weiter kommt und die helfenden 
Hände im Regen stehen lässt...

[Jens R. (tmaniac)]

Ein relativ einfacher Ansatz wäre doch tatsächlich mit unterschiedlich 
scharfen Filtern zu arbeiten.

Der schärfste Filter wäre dein gewünschtes Muster. Wenn das mit dem 
Eingangssignal bitweise ver-und-ed wird, weißt du die Anzahl der 
notwendigen Bits.

Erster Schritt wäre diese Anzahl mit der gewünschten Anzahl zu 
vergleichen.
Jeweniger das Muster übereinstimmt, desto kleiner wird die Anzahl 
automatisch.

Wenn man mit zwei oder drei "verschobenen" oder "vergrößerten"(ein 
Wunschbit hat im Filter 2 oder 3 Bit) Filtern prüft, kann man immer über 
die Anzahl der getroffenen Bits auch Rückschlüsse ziehen.


FuzzyLogic kommt halt so langsam aus der Mode 😉

[Hermann Kokoschka (Gast)]

Leute, spart Euch den Ideen-Aufwand.
Der TO ist seit Tagen längst raus...

[Stefan F. (Gast)]

Hermann Kokoschka schrieb:
> Der TO ist seit Tagen längst raus...

Ohne Bescheid zu sagen. Ich finde das sehr respektlos. Den Namen solltet 
ihr euch merken, damit er euch nicht erneut verarscht.

[Moko (Gast)]

Der TO macht jetzt hier weiter
https://forum.arduino.cc/t/unscharfe-mustererkennung/1003922

[Hermann Kokoschka (Gast)]

Moko schrieb:
> Der TO macht jetzt hier weiter
> https://forum.arduino.cc/t/unscharfe-mustererkennung/1003922

Und DORT ist er (wie durch ein Wunder) plötzlich in der Lage, das 
Grundproblem/Projekt zu beschreiben.

DIE EHRE wurde diesem Forum leider nicht zuteil.

P.S.:
Cool finde ich, dass dies DORT bemerkt wurde,
manchmal erfreut mich sowas wie "Vernetzung"...