kurse:ef05a-2021:kurven:bezier-interpolation [https://fginfo.ksbg.ch Fachgruppe Informatik der KSBG]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Interpolation mittels Bezierkurven ======
Das (ambitionierte) Ziel ist die Buchstabenerkennung auf einer Smartwatch. 

===== Trainingsdaten =====

Dazu liegen bereits erste Input-Daten vor:
https://tech-lab.ch/twatch/drawing/test.txt

Das Format ist wie folgt:
<code txt>
ID letter
ms x y
...
ms -1 -1
ms x y
...
ms -1 -1
ID letter
...
</code>
Wobei 
  * ID ist eine 12-stellige Hexadezimalzahl ist. Damit kann z.B. spezifisch für eine Person trainiert werden.
  * letter ist ein Zeichen (zur Zeit A-Za-z0-9).
  * ms ist die Zeit in Millisekunden seit Beginn des Zeichnens
  * x y sind die Pixelkoordinaten (auf einen 240x240 Pixel grossen Bildschirm).
  * sind die Koordinaten -1 wurde der Finger abgesetzt. Entweder ist das Symbol fertig, oder es folgt ein weiterer Strich


====== Geeignete Datenstruktur ======
  * Wir haben mehrere Buchstaben (zur Zeit A-Za-z0-9).
  * Jeder Buchstaben kann von verschiedenen Personen gezeichnet worden sein.
  * Zu jedem Buchstaben liegt z.T. mehrere "Zeichnungen" vor, d.h. die Information, wie er gezeichnet wurde.
  * Eine Zeichnung besteht aus z.T. mehreren Strichen.
  * Ein Strich besteht aus mehreren Zeit/x/y Koordinaten

Später werden aus jeder Zeichnung Daten (Fingerprint) errechnet, mit deren Hilfe dann die Ähnlichkeit mit einer zu bestimmenden Zeichnung errechnet werden kann.

Aus mehreren Zeichnungen eines Buchstabens soll dann auch ein "mittlerer Fingerprint" errechnet werden. Das beschleunigt das Abgleichen.

===== Frage: Arrays und Funktionen oder Klasse(n)? =====
Vorteile von Klassen: 
  * Einfach erweiterbar
  * Einlesen/Manipulation der Daten kann in der jeweiligen Klasse erfolgen.
  * Übersichtlichkeit im Code dank mehreren Dateien (jede Klasse in eine Datei).
Nachteile von Klassen:
  * Boilerplate-Code (Viel Code, damit die Klasse erst mal als solche funktioniert).
  * Gefahr vom "Yak-Shaving", d.h. vermeintlich nützliche Dinge implementieren, einfach weil es elegant ist, und vielleicht einmal praktisch sein könnte (z.B. könnte die Differenz zweier Zeichnungen gleich die Ähnlichkeit liefern, oder die Daten werden direkt via http eingelesen).



==== Auslesen und Anzeigen der Daten ====
Schreiben Sie ein Python-Programm, das die Daten einliest und Buchstaben auf dem Bildschirm darstellt.

==== Mögliche Ähnlichkeitsmasse ====
Überlegen Sie sich, wie die Ähnlichkeit zweiter Buchstaben gemessen werden könnte. Formulieren Sie dazu einen präzisen Algorithmus (d.h. wie genau was gerechnet werden soll).
  * Ihre Ideen möchte ich haben...

==== Warum Interpolation? ====
Ein mögliches Ähnlichkeitsmass besteht darin, die vom Benutzer gezeichnete Kurve in Fourier-Koeffizienten zu zerlegen und diese Koeffizienten zu vergleichen. Weil die Kurve nicht geschlossen ist und aus mehreren Stücken bestehen kann, muss die Kurve vor der Transformation zuerst vervollständigt werden. Um hochfrequentes Rauschen zu minimieren, sollen die fehlenden Stücke "möglichst schön" eingefügt werden. Kubische Bezier-Kurven erscheinen hier als brauchbare und einfach umzusetzende Methode.


===== Code zum Einlesen in einfache Datenstruktur =====
<code python>
#!/usr/bin/env python
# -*- coding: utf-8 -*-

from gpanel import *

makeGPanel(Size(800,800))  # Fenster oeffnen
window(0, 240, 240, 0)     # Koordinatensystem


alles = {}  # Neuer dictionary, keys sind Buchstaben
# Eintrag ist ein dictionary, keys sind ids(person)
# Eintrag ist ein Array, Einträge sind Zeichnungen
# Zeichnung ist ein Array, Einträge sind Striche
# Strich ist ein Array, Eintrag ist ein Array von 3 Einträgen ms,x,y
#
# alles['Q']['2c24fac40a24'][0][1][2] liefert [50,20,130]


with open("test.txt") as datei:
    while True:
        line = datei.readline()
        if not line:  # Datei Ende?
            break
        line = line.rstrip()
        items = line.split()  # Liste mit Strings
        
        if len(items)==2:  # Kopfzeile
            person = items[0]
            buchstabe = items[1]
            if not buchstabe in alles:  # Neuer Buchstabe, Eintrag ist ein leerer Dictionary
                alles[buchstabe] = {}
            if not person in alles[buchstabe]: # Neue Person, Eintrag ist ein leeres Array
                alles[buchstabe][person] = []  # Platz für Zeichnungen
            zeichnung = []  # Platz für Striche
            alles[buchstabe][person].append(zeichnung)
            strich = []  # Platz für Koordinaten
        else:  # "Normale Zeile"
            koordinaten = [int(s) for s in items]  # Umwandlung in Zahlen
            if koordinaten[1]==-1: # Strich fertig
                zeichnung.append(strich)
                strich = []  # Neuer Platz für Koordinaten
            else:
                strich.append(koordinaten)
                

for buchstabe,personen in alles.items():
    for person, zeichnungen in personen.items():
        print("Buchstabe %s, Person %s" % (buchstabe, person))
        for zeichnung in zeichnungen:
            clear()
            for strich in zeichnung:
                move(strich[0][1], strich[0][2])
                for txy in strich:
                    lineto(txy[1], txy[2])
                    delay(20)        
        
    

</code>