3x3 Pixelmatrix aus Bild extrahieren

[Yann B. (yann)]

Hallo,

Ich habe ein BMP Bild (784 Pixel), das ich mit einem Sobel-Filter 
verabeiten möchte. Dazu möchte ich mein ganzes Bild durchlaufen und 
immer eine 3x3 Pixelmatrix extrahieren und den  Sobel-Mask darauf 
anwenden, um das neue Pixel zu berechnen (siehe Anhang1). Den 
Sobel-Filter habe ich schon implementiert aber mir ist schwer, diese 3x3 
Pixelmatrix aus dem 28x28 Bild zu erzeugen. Die Pixeldaten des 
Input-Bildes sind in einem 1kx8 Bit Simple Dual-Port RAM nacheinander 
(von Adresse 0 bis 783) gespeichert.

Hat jemand vielleich eine Idee, wie ich diese 3x3 Pixelmatrix erzeugen 
kann?

Vielen Dank!

[c-hater (Gast)]

Yann B. schrieb:

> Hat jemand vielleich eine Idee, wie ich diese 3x3 Pixelmatrix erzeugen
> kann?

Du machst es so, wie alle anderen Programmierer auch: Du lernst einfach 
Programmieren...

[Yann B. (yann)]

c-hater schrieb:
> Du machst es so, wie alle anderen Programmierer auch: Du lernst einfach
> Programmieren...

Das Problem hier ist nicht "Programmieren". Es geht um einen optimierten 
Entwurf (kleine Latenz und wenig Ressourcen). Ich wollte beispielsweise 
28 weiteren Buffer erstellen, um 28 Pixel in jedem zu speichern. Dann 
könnte ich parallel und pro Taktzyklus immer 3 Pixel daraus lesen, und 
nach 3 Taktzyklen hätte ich meine 9 Pixel für meine Matrix. Aber 28 
Buffer finde ich viel als Ressourcen.

[Yann B. (yann)]

Übrigens, im Anhang 1 ist das Input-Bild nur ein Beispiel, es hat kein 
784 Pixel.

Außerdem, habe ich festgestellt, dass ich im falschen Forum Thread 
gepostet habe. Weiß jmd vielleicht, ich den Thread zum Forum "FPGA, VHDL 
..." verschieben kann? Oder kann nur Admin sowas machen?

[Alex G. (dragongamer)]

Verstehe nicht was du mit 28 weiteren Buffern meinst. Du brauchst nur 
den Buffer für das Output Bild und ein paar Lokale Variablen fürs 
Anwenden des Filters.
Du kennst ja sicherlich den Modulo Operator. Damit kannst du die Pixel 
extrahieren indem du 9 Formeln formulierst - eine für jeden Pixel.
Diese Formel wird die Variable N enthalten, welche das momentan gesuchte 
Out-put Feld angibt (also von 0 bis 27).

Die Formel für das Pixel oben Links in einem Feld sollte bei N = 0, 0 
ergeben. Bei N = 1, 3 und bei N = 4, 24, weil das die nächste Zeile an 
Feldern ist.

Btw. wahrscheinlich macht es viel Sinn den Speicher für die Felder auf 
eine ganze Anzahl von 3x3 Feldern aufzurunden, damit du keine 
Sonderfälle in den Formeln beachten musst.

EDIT: Übrigens, nur die erste Formel für die Ecke oben Links erfordert 
etwas Überlegung. wen diese z.B. X ergibt,
dann sind die neun pixel:

X
X+1
X+2
X+W
X+W+1
X+W+2
X+2*W
X+2*W+1
X+2*W+2

Wobei W die Anzahl Pixel auf einer Horizontale sind.



EDIT 2: Oh, du willst das in VHDL machen?

[Egon D. (Gast)]

Yann B. schrieb:

> Das Problem hier ist nicht "Programmieren". Es geht
> um einen optimierten Entwurf (kleine Latenz und wenig
> Ressourcen).

Naja, Du musst Dich schon entscheiden: ENTWEDER kleine
Latenz ODER wenig Ressourcen. :)


> Ich wollte beispielsweise 28 weiteren Buffer erstellen,
> um 28 Pixel in jedem zu speichern.

Du drückst Dich etwas sonderbar aus. Aber -- ja, Bilddaten
werden i.d.R. zeilenweise organisiert und bearbeitet.

Wenn Du das Bild nicht nur erzeugen und sofort ausgeben,
sondern intern speichern willst, brauchst Du mindestens
Pufferspeicher für zwei (!) komplette Zeilen.


> Dann könnte ich parallel und pro Taktzyklus immer 3 Pixel
> daraus lesen,

Schau Dir den Operator genau an: Sechs Pixel genügen -- wenn
der Koeffizient "Null" ist, ist nix zu tun.
Die Differenzen in allen Operatorzeilen kann man in Hardware
gleichzeitig berechnen.

> und nach 3 Taktzyklen hätte ich meine 9 Pixel für meine
> Matrix. Aber 28 Buffer finde ich viel als Ressourcen.

Wenn Du das Bild noch speichern willst, brauchst Du sogar
2x28 = 56. Wenn Du es nur erzeugen und ausgeben willst,
brauchst Du nix.

[Rolf M. (rmagnus)]

Hier denkt glaub ich jeder, dass es um die Implementation auf einem µC 
in z.B. C geht, aber das hier lässt anderes vermuten:

Yann B. schrieb:
> Weiß jmd vielleicht, ich den Thread zum Forum "FPGA, VHDL ..." verschieben
> kann? Oder kann nur Admin sowas machen?

Um die Frage zu beantworten: Ja, das kann nur der Admin bzw. Moderator.

[Yann B. (yann)]

Alex G. schrieb:
> Verstehe nicht was du mit 28 weiteren Buffern meinst.

Damit meine ich, jeder Buffer, um 28 Pixel (also jede Zeile im 
originalen Format des Bildes (28x28)) zu speichern.

> Du brauchst nur den Buffer für das Output Bild

Das ist auch schon geplant.

> und ein paar Lokale Variablen fürs Anwenden des Filters.

Der Filter habe ich schon implementiert. Ich muss ihm nur die Pixeldaten 
liefern.

Alex G. schrieb:
> Die Formel für das Pixel oben Links in einem Feld sollte bei N = 0, 0
> ergeben. Bei N = 1, 3 und bei N = 4, 24, weil das die nächste Zeile an
> Feldern ist.

Wie kriegst du bei N = 1, 3 und bei N=4, 24?

Alex G. schrieb:
> Btw. wahrscheinlich macht es viel Sinn den Speicher für die Felder auf
> eine ganze Anzahl von 3x3 Feldern aufzurunden

Was meinst du konkreter?

Alex G. schrieb:
> EDIT 2: Oh, du willst das in VHDL machen?

Ja.

[Yann B. (yann)]

Egon D. schrieb:
> Wenn Du das Bild nicht nur erzeugen und sofort ausgeben,
> sondern intern speichern willst, brauchst Du mindestens
> Pufferspeicher für zwei (!) komplette Zeilen.
Von welchem Bild redest du? Input-Bild oder Pixelmatrix?  Aus dem 
Input-Bild möchte ich die benötigten Pixel (Pixelmatrix) erzeugen, den 
Mask anwenden und das berechnetete Pixel in einen RAM wieder speichern.

Egon D. schrieb:
> Schau Dir den Operator genau an: Sechs Pixel genügen -- wenn
> der Koeffizient "Null" ist, ist nix zu tun.

Das stimmt.

[Yann B. (yann)]

Rolf M. schrieb:
> Hier denkt glaub ich jeder, dass es um die Implementation auf einem µC
> in z.B. C geht, aber das hier lässt anderes vermuten:

Sorry, ich kann den Thread leider nicht mehr bearbeiten. Sonst hätte ich 
schon längst noch erwähnt, dass ich es in VHDL realisieren möchte.

[Yann B. (yann)]

Keine Reaktion??

[Egon D. (Gast)]

Yann B. schrieb:

> Keine Reaktion??

Da ich Deine Frage nicht verstehe, kann ich auch keine
zielführende Antwort geben.

Was willst Du an der 3x3-Matrix "erzeugen"?

Auf einer sequenziellen Maschine verwendet man Pointer,
um den jeweil benötigten Ausschnitt aus dem Input-Bild
zu adressieren.
Im FPGA wird es sicherlich auf Addresszähler hinauslaufen,
aber davon habe ich keine Ahnung.

[Alex G. (dragongamer)]

Yann B. schrieb:
> Alex G. schrieb:
>> Die Formel für das Pixel oben Links in einem Feld sollte bei N = 0, 0
>> ergeben. Bei N = 1, 3 und bei N = 4, 24, weil das die nächste Zeile an
>> Feldern ist.
>
> Wie kriegst du bei N = 1, 3 und bei N=4, 24?
Habe jetzt nicht die Lust diese Formel zusammen zusetzten. Etwas musst 
du auch machen ;)
Wieso diese Zahlen aus der Formel kommen sollen ist dir schon klar, 
oder?
Das ist der Index der jeweils linken oberen Ecke von jedem 3x3 Feld wenn 
alle Einzelfelder in einem linearen Array sind.

Allerdings war das nur meine Annahme dass dein Bild als lineares Array 
vorliegt. Habe leider keine Ahnung von VHDL.


>> eine ganze Anzahl von 3x3 Feldern aufzurunden
>
> Was meinst du konkreter?
Glaube das nennt sich auch padding. Im Konreten Fall wo du ein 8x8 Bild 
hast, solltest du überlegen was aus den Feldern am Rand passieren soll, 
denn dort fehlen dir ja umliegende Werte. Es macht darum Sinn in einem 
vorbereitenden Schritt, eine Reihe sowie eine Spalte hinzuzufügen.
Denn es wird einfacher (und u.U. schneller) sein, mit einem 9x9 array zu 
arbeiten weil die 3x3 Felder da exakt rein passen.

[Egon D. (Gast)]

Alex G. schrieb:

> Allerdings war das nur meine Annahme dass dein Bild
> als lineares Array vorliegt.

Das wird so sein, da er schreibt, das Bild liege sequenziell
in einem Dual-Port-RAM vor.


>>> eine ganze Anzahl von 3x3 Feldern aufzurunden
>>
>> Was meinst du konkreter?
>
> Glaube das nennt sich auch padding. Im Konreten Fall wo
> du ein 8x8 Bild hast, solltest du überlegen was aus den
> Feldern am Rand passieren soll, denn dort fehlen dir
> ja umliegende Werte. Es macht darum Sinn in einem
> vorbereitenden Schritt, eine Reihe sowie eine Spalte
> hinzuzufügen. Denn es wird einfacher (und u.U. schneller)
> sein, mit einem 9x9 array zu arbeiten weil die 3x3 Felder
> da exakt rein passen.

Ich glaube, Du sitzt einem Denkfehler auf: Der Operator
muss auf JEDES Pixel (mit seinen 8 Nachbarn) angewendet
werden, nicht blockweise.
(Anders formuliert: Die "Anwendungsbereiche" überlappen
sich.)

Trotzdem hast Du Recht: Man muss das Ursprungsbild erstmal
erweitern, weil ja Pixel am linken Rand keinen linken
Nachbarn haben können, was aber für den Operator notwendig
ist.

[Yann B. (yann)]

Also, ich möchte noch einmal erwähnen, dass ich im falschem Forum 
unbewusst gepostet habe, und wollte gern switchen aber es kann nur der 
Admin das machen, soviel ich weiss.

Egon D. schrieb:
> Was willst Du an der 3x3-Matrix "erzeugen"?

Also, wie ich oben schon gesagt habe, möchte den Sobel-Mask auf meinem 
Input-Bild anwenden. Dazu möchte ich das ganze Bild durchlaufen und eine 
3x3 Pixelmatrix erzeugen, um den Mask darauf anzuwenden.

[Egon D. (Gast)]

Yann B. schrieb:

> Egon D. schrieb:
>> Was willst Du an der 3x3-Matrix "erzeugen"?
>
> Also, wie ich oben schon gesagt habe, möchte den
> Sobel-Mask auf meinem Input-Bild anwenden.

Das habe ich verstanden.


> Dazu möchte ich das ganze Bild durchlaufen

Das habe ich auch verstanden.


> und eine 3x3 Pixelmatrix erzeugen,

Das verstehe ich nicht. Was willst Du da "erzeugen"?

Du musst die Pixel aus dem Input-Bild lesen und mit
den korrespondierenden Koeffizienten aus der Filtermatrix
multiplizieren.

Wie das geht, hat Alex erklärt.

Wenn Du andere Antworten möchtest, solltest Du Deine
Frage anders formulieren, damit Dein Problem verständlich
wird.

[Yann B. (yann)]

Alex G. schrieb:
> Habe jetzt nicht die Lust diese Formel zusammen zusetzten. Etwas musst
> du auch machen ;)
> Wieso diese Zahlen aus der Formel kommen sollen ist dir schon klar,
> oder?

Leider immer noch nicht.

Alex G. schrieb:
> Das ist der Index der jeweils linken oberen Ecke von jedem 3x3 Feld wenn
> alle Einzelfelder in einem linearen Array sind.

Wie Egon schon gesagt hat, wird der Sobel-Mask auf alle Pixel des Bildes 
angewendet, angefangen vom ersten Pixel oben links.

[Yann B. (yann)]

Egon D. schrieb:
> Das verstehe ich nicht. Was willst Du da "erzeugen"?

Sorry, wenn der Term "erzeugen" dich verwirrt. Ich brauche einfach 9 
Pixel für meine Masken (Horizontal und vertikal).

Egon D. schrieb:
> Du musst die Pixel aus dem Input-Bild lesen und mit
> den korrespondierenden Koeffizienten aus der Filtermatrix
> multiplizieren.

Das hier (*) ist das Symbol für die Faltung. Ich mache also für jeden 
3x3 Block die Faltung mit den Masken, was das Ausgang-Pixel ergibt.

[Daniel A. (daniel-a)]

Sobel ist ein Separabler Filter, damit könnte man also eventuell etwas 
einsparen: https://de.wikipedia.org/wiki/Separierbarkeit

[Egon D. (Gast)]

Daniel A. schrieb:

> Sobel ist ein Separabler Filter, damit könnte man
> also eventuell etwas einsparen: [...]

Natürlich.

Außerdem sind die Zeilen des Filters linear voneinander
abhängig; es genügt also, EINE Zeile zu berechnen. Das
läuft also auf y[n] := x[n+1] - x[n-1] hinaus.

Die von Eins verschiedenen Koeffizenten realisiert
man durch passend verschobene Verdrahtung.

Man braucht einen FIFO, der etwas mehr als zwei Zeilen
fasst, sowie ein paar Adder.