Lauflängencodierung - einfach erklärt
Informatik und Mathematik by Dr. Gebhardt
https://www.youtube.com/watch?v=EFsnoRGQ-xM

Transkript (automatisch erstellt)

0:00 hallo zusammen in diesem Video lernen wir wie man schwarz-weiß Bilder effizient im Computer speichern kann hier seht ihr ein schwarz-weiß Bild es
0:09 es wurde in das Bild ganz ganz stark rangezoomt so dass wir die einzelnen Pixel also Bildpunkte sehen können hier weiße Pixel und die schwarzen Pixel sind
0:19 schraffiert hier dargestellt wenn man ein solches Bild speichern möchte geht man so vor dass man einfach jeden einzelnen Bildpunkt
0:28 speichert für einen weißen Bildpunkt für ein weißes Pixel nehme ich eine 0 und für einen schwarzes eine 1 wenn wir also dieses Bild speichern wollen müssen wir
0:38 zählen wie viel Bildpunkte hatte das Bild das sind entsprechend wir zählen mal wie breit es ist es ist se Pixel breit vier Pixel hoch 6 x 4 wir
0:47 bräuchten also 24 Bit um dieses Bild zu speichern genauer gesagt speichern wir aber mit den 24 Bit erstmal nur die Nutzdaten des
0:58 Bildes was man auch ich noch merken muss sind sogenannte Metadaten die man auch braucht um das ursprüngliche Bild wieder rekonstruieren zu können und zwar
1:08 müssten wir uns hier noch merken wie breit das Bild ist denn wenn wir einfach nur eine Folge von Nullen und Einsen haben wissen wir am Ende nicht wie wir
1:16 die anordnen müssen wann machen wir den Umbruch zur nächsten Zeile das heißt wir müssten uns in diesem Fall noch merken dass das Bild eine Breite von SE Pixeln
1:27 hat und jetzt könnte man fest legen man nimmt z.B immer so und so viel bit um sich die Breite zu merken das kann aber je nach Anwendung variieren manchmal
1:36 nimmt man vielleicht immer 10 Bit um sich das zu merken manchmal vielleicht 12 weil das nicht eindeutig dann festgelegt ist schreiben wir einfach mal
1:44 hin wir brauchen 24 Bit für die Nutzdaten plus den Speicherbedarf den die Metadaten noch ausmachen die Metadaten müssen wir uns
1:54 aber bei jeder möglichen Speicherverfahren Werken deswegen reicht das auch auch wenn wir das entsprechend hier so
2:02 angeben als nächstes wollen wir uns überlegen wie man Speicherplatz einsparen kann und zwar mit einer verlustfreien kompressionsmethode wir
2:11 wollen also in der Lage sein das ursprüngliche Bild mit selber Qualität wiederherzustellen ein mögliches Verfahren hierzu ist die
2:22 lauflängencodierung oder die sogenannte nbit lauflängencodierung diese beiden Verfahren schauen wir uns jetzt nacheinander an beginnen wir mit dem
2:30 ersten die Idee der laufläencodierung besteht darin dass in einem Bild sehr häufig Pixel der gleichen Farbe mehrmals nacheinander
2:40 Auftreten und die Idee ist einfach dass wir uns nicht jeden einzelnen Pixel merken sondern wir merken uns wie oft kommt ein Pixel vor wir legen fest wir
2:52 fangen damit an dass wir angeben wie viele weiße Pixel hat das Bild und dann kommen immer abwechselnd wie viel schwarze dann wieder wie viel weiße wie
3:02 viel schwarze und so weiter ich notiere erm die Ideen also wir starten mit den weißen Pixeln und wir merken uns die Anzahl der gleichen
3:15 Pixel das machen wir jetzt für obiges Bild dann wird gleich sehr viel klarer wie ich das meine dieses Bild hier beginnt mit vier
3:26 weißen Pixeln wir notieren uns also eine dann kommt ein schwarzer Pixel das Notieren wir auch danach kommen vier weiße wir machen einfach in der nächsten
3:39 Zeile weiter es kommen drei schwarze und jetzt kommen noch mal eine ganze Reihe weiß wir Zen durch das sind 6 + 6 also 12 weiße
3:52 insgesamt und so merken wir uns das jetzt einfach wir merken uns unser Bild beginnt vier weiße Pixel ein schwarzer vier weiße drei schwarzer 12 weiße und
4:03 auf die Weise könnte man das Bild wieder hererstellen natürlich können wir diese Zahlen so nicht im Computer speichern sondern müssen sie erst binär codieren
4:11 bei der allgemeinen lauflcodierung geht man dann so vor man sucht sich die größte Zahl raus das ist die 12 und überlegt sich wie viel bit brauche ich
4:19 um eine 12 abzuspeichern da brauchen wir vier Bit für denn mit dre bit könnte ich maximal eine sieben
4:28 speichern aber mit 4 ist die 12 kein Problem und das sieht dann wie folgt aus 100 8 + 4
4:36 12 und jetzt müssen wir alle anderen zeihen auch mit 4er bit codieren damit man später das Bild wieder rekonstruieren kann und weiß wo hört die
4:46 eine pixelfarbe auf und wo geht die Nächste los deswegen können wir nicht einfach sagen wir machen mal mal 4 Bit mal 3 bit das würde keinen Sinn ergeben
4:54 dann könnten wir das Bild nicht wiederherstellen also müssen wir alles mit vier bit angeben die drei mit vier B die vi ist ja 10 müssen wir auch eine
5:04 Null auffüllen damit wir auch ein Vierer Block haben bei der 1 machen wir das genauso und noch mal bei der vier wir brauchten also für jede Länge 4
5:17 Bit und wir haben insgesamt 1 2 3 4 5 Längen 5 x 4 sind wir bei 20 bit die rein Nutzdaten die wir hier speichern sind also 20 bit aber es
5:34 kommen auch noch die Metadaten hinzu und zwar müssen wir uns hier auch natürlich die Breite des Bildes merken wir müssen uns aber auch merken wie viel
5:45 bit haben wir genommen um so eine Lauflänge zu codieren also die Anzahl der gleichen Pixel und da haben wir ja jetzt jeweils
5:55 vier bit verwendet wegen der 12 wie wir uns eben überlegt haben we das müssten wir uns auch speichern wir müssten un speichern wir haben 4er bit verwendet um
6:05 die Länge anzugeben und wir müssten uns die Breite speichern die ist sech Pixel breit das breite speichern müssen wir aber immer machen wie wir eben schon
6:15 festgestellt haben das haben wir auch bei der grundcodierung gemacht dass was hier hinzu kommmt das neue ist dass man sich noch merken muss wie viel Bild hat
6:23 man für die Länge genommen und wenn man sich die Länge noch auch noch speichern muss dann merkt man schon wir haben ja sowieso nur 4er
6:30 bit gespart wenn wir 20 und 24 vergleichen 4 Bit hätten wir zwar gespart aber wir müssen uns noch die Länge merken das heißt im
6:39 Endeffekt kommt so plus- n0 raus wir haben eigentlich jetzt nicht besonders viel gespart und deswegen ist ein bisschen intelligenter die sogenannte
6:48 nbit lauflängencodierung hier legt man im Vorhinein fest wie viele bit man zum Codieren der Lauflänge benutzt z.B sagt
6:57 man man nimmt die sogenannte dreibit lauflängencodierung dann würde man immer drei bit nehmen um die Länge zu codieren was wir da drüben gemacht haben
7:07 wäre so gesehen die vierbit Lauf dencodierung gewesen weil wir immer vierbit hatten nur weil es variabel war mussten wir uns das merken wenn wir das
7:14 von vorne rein festlegen wie vi bit wir nehmen brauchen wir uns die Anzahl der bit nicht noch mal merken dann ist ja klar wir haben immer drei bit genommen
7:21 und so machen wir das jetzt mal für das obige Bild der Anfang ist genauso wie zur normalen lauflcodierung jetzt zT einfach durch wie kommen die einzelnen
7:30 Pixel vor wir haben vier weiße dann kommt ein schwarzer vier weiße drei schwarze 12 weiße also genau wie eben auch und jetzt codieren wir jede Länge
7:40 mit 3 bit die vier wird also dargestellt als 10 die 1 codieren wir dann mit 01 dann kommt wieder eine
7:53 4 für die 3 haben wir 0 1 1 und bei der 12 haben wir ein Problem mit 3 bit können wir keine 12 darstellen denn wenn wir alle bit ausschöpfen das mache ich
8:04 jetzt mal wir nehmen alle dre bit dann haben wir aber erst eine 7 dargestellt weil 4 + 2 + 1 das ist 7 wir müssen aber auf 12 kommen und da ist die Idee dass
8:16 man sich jetzt einfach merkt wir haben sieben weiße und dann kommen erstmal keine schwarzen wir codieren also eine Null keine
8:26 schwarzen und dann kommt ja wieder der Block für die weißen und dann müssen noch fünf weiße kommen wir haben also die 12 zerlegt in 7 + 5 und haben uns
8:36 gemerkt dass dazwischen keine schwarzen Pixel kommen wie viel bit haben wir jetzt hier gebraucht wir zählen wieder durch wir
8:46 haben 1 2 3 4 5 6 7 x 3 also 21 bit als Nutzdaten und die Metadaten sind wieder die Breite des Bildes und und die Anzahl der bit die wir für die Länge verwendet
9:02 haben brauchen wir nicht speichern weil wir von vorne rein festgelegt haben wir nehmen die dreibit Lauflängen Codierung und das heißt wenn wir das
9:10 jetzt mit dem ur mit der ursprünglichen nicht komprimierten Codierung vergleichen dann können wir sicher sagen wir haben 3 bit gespart es war also
9:19 schon eine Ersparnis sichtbar dann hoffe ich habt ihr das Prinzip verstanden schaut euch noch mal
9:26 ganz in Ruhe an wenn ihr Fragen habt stellt die gerne wie immer freue ich mich über einen Daumen nach oben und natürlich ein Abo
9:34 dann bis zum nächsten Video