Hallo, ich bin auf der Suche nach einem guten Algorithmus um eine Grafik im sub-Pixel Bereich zu verschieben. Ich kenne zwar die Namen einiger Interpolationsverfahren habe aber keine Ahnung über deren Implementierung und deren Vor-/Nachteile. Ich benötige keine Skalierung und keine Rotation, nur ein Verschiebung in zwei Achsen. Ich habe gelesen das man z.B. für Lanczos-Interpolation unterschiedliche Koeffizienten für unterschiedliche Verschiebedistanzen benötigt um ein optimales Ergebnis zu erhalten. Im Prinzip reichen mir einige diskrete Verschiebedistanzen, z.B. 0,125px 0,25px 0,375px & 0,5px bzw. jeweils diese 4 Werte für jede Achse also insgesamt 16 Algorithmen. (Für negative Verschiebung kann man ja dann einen ganzen Pixel negativ schieben und dann die entsprechende positive Verschiebung Anwenden). Jemand eine Idee was man da am besten nimmt?
ich hab so etwas noch nie gemacht, werde aber in den nächsten Wochen etwas ähnliches entwickeln müssen für die Verschiebung in eine Achsrichtung. Ich hätte jetzt - ohne groß drüber nachzudenken auf lineare Interpolation gesetzt. Das müsste sich auch auf 2D-Verschiebungen anwenden lassen. Aber ob das das Maß der Dinge ist? ich bin ebenfalls auf Antworten gespannt!
Kannst versuchen, ein Upscaling durchzuführen, bis deine Subpixel ganze Pixel sind, dann verschieben und wieder runterskalieren. Ansonsten kannst du auch ganz normal destination-driven vorgehen: - 2.(leeres) Bild erzeugen - von Zielkoordinaten (ganze Zahlen) auf die Source-Positionen zurückrechnen - linear oder sonstwie zwischen den Source-Pixeln interpolieren. Du wirst bei beiden Verfahren ein leichtes tiefpassartiges Glätten im Ergebnisbild haben. Gerade harte Kanten werden halt stark geblurrt. Da kann man eigentlich nichts machen, da eine vorher 1 Pixel breite Kante wahrscheinlich auf 2 bis 3 Pixel breitgezogen wird. Wahrscheinlich: ausprobieren und schauen, was am besten taugt. Ich hatte teilweise schon mit Resamplen ohne Interpolation bessere Ergebnisse als mit Interpolation (ging darum, Albencover auf einen Sansa-MP3-Player zu bringen, der nur eine geringe Auflösung hat)
Eine schöne Möglichkeit ist auch, das Bild im Fourier-Raum mittels des Verschiebungstheorems ringförmig zu verschieben. Vorteil ist, dass dieser Vorgang nicht bandbreitenbeschränkt ist, heißt, keine Tiefpasswirkung. Beispiel in Python habe ich angehängt. Unerwünschte Randartefakte sind durch 1-Pixel breites Padding zu vermeiden.
auf http://www.paulinternet.nl/?page=bicubic habe ich C code für Bicubic Interpolation gefunden:
1 | double cubicInterpolate (double p[4], double x) { |
2 | return p[1] + 0.5 * x*(p[2] - p[0] + x*(2.0*p[0] - 5.0*p[1] + 4.0*p[2] - p[3] + x*(3.0*(p[1] - p[2]) + p[3] - p[0]))); |
3 | }
|
4 | |
5 | double bicubicInterpolate (double p[4][4], double x, double y) { |
6 | double arr[4]; |
7 | arr[0] = cubicInterpolate(p[0], y); |
8 | arr[1] = cubicInterpolate(p[1], y); |
9 | arr[2] = cubicInterpolate(p[2], y); |
10 | arr[3] = cubicInterpolate(p[3], y); |
11 | return cubicInterpolate(arr, x); |
12 | }
|
habe mir dann noch schnell ein Programm in Qt geschrieben zum testen:
1 | #include "QImage" |
2 | #include "math.h" |
3 | |
4 | #define GETPIXEL(x,y) ((double)(pic1->pixel((x),(y))&0xFF))
|
5 | #define TOQPIXEL(x) (((unsigned int)round(x))|(((unsigned int)round(x))<<8)|(((unsigned int)(x))<<16)|0xFF000000)
|
6 | |
7 | MainWindow::MainWindow(QWidget *parent) : |
8 | QMainWindow(parent), |
9 | ui(new Ui::MainWindow) |
10 | {
|
11 | ui->setupUi(this); |
12 | |
13 | QImage* pic1 = new QImage("/media/data/test/1.bmp"); //Ausgangsbild 160x160 schwarz-weiß |
14 | QImage* pic2 = new QImage(128,128,QImage::Format_ARGB32); |
15 | QImage* pic3 = new QImage(128,128,QImage::Format_ARGB32); |
16 | double temp[4][4]; |
17 | double out; |
18 | |
19 | for( int i=0; i<128; i++ ) |
20 | {
|
21 | for( int j=0; j<128; j++ ) |
22 | {
|
23 | pic2->setPixel(i,j, TOQPIXEL( GETPIXEL(i+16,j+16) ) ); |
24 | //daten in temporäres array kopieren
|
25 | for( int k=0; k<4; k++ ) |
26 | {
|
27 | for( int l=0; l<4; l++ ) |
28 | {
|
29 | temp[k][l] = GETPIXEL(i+k+14,j+l+14); |
30 | }
|
31 | }
|
32 | //interpolierten Werte berechnen & speichern
|
33 | out = bicubicInterpolate(temp,0.33,0.66); |
34 | out = (out>255.0) ? 255.0 : out; |
35 | out = (out<0.0) ? 0.0 : out; |
36 | pic3->setPixel(i,j, TOQPIXEL(out)); |
37 | }
|
38 | }
|
39 | pic2->save("/media/data/test/2.bmp"); |
40 | pic3->save("/media/data/test/3.bmp"); |
41 | }
|
Stimmt.... Fourier-Raum ist auch eine Idee... wie war das? Verschiebung im Zeitbereich ist Dämpfung bzw. Phasenverschiebung im Frequenzbereich oder so...
Hallo KlausPixel . Daß dir diese Interpolationsimplementierung das Pixel verschiebt, hast du nicht bemerkt ? Weiters musst du bei solchen Sachen auch immer noch einen Rahmen/Rand rumherum machen, sonst stimmt dir das Ergebnis auch nicht, wie der Weichzeichnereffekt dir warscheinlich nicht aufgefallen ist. Ob sich das Gamma auch ändert kann man so nicht beurteilen, da der Weichzeichnereffekt zu hoch ist.
ich bin auch an so einem thema dran, denke aber, dass es nicht gehen kann, den kontrast aufrecht zu erhalten. scharf begrenzte linien werden immer weich werden, wenn sie nicht mehr exakt auf dem pixel liegen. gutes thema dazu: Beitrag "Abtasttheorem angewendet auf Bildformate"
chris schrieb: > Daß dir diese Interpolationsimplementierung das Pixel verschiebt, hast > du > nicht bemerkt ? Die Frage verstehe ich nicht. Ich will doch eine Verschiebung haben. > Weiters musst du bei solchen Sachen auch immer noch > einen > Rahmen/Rand rumherum machen, sonst stimmt dir das Ergebnis auch nicht, Das stört für meinen Anwendungfall nicht, außerdem ist der Rand nur 2 Pixel breit. > wie der Weichzeichnereffekt dir warscheinlich nicht aufgefallen ist. Doch aber wie Bildverwursteler schon sagt kann man eben keine scharfe 1px breite Linie darstellen die genau zwischen 2 pixeln liegt. > Ob sich das Gamma auch ändert kann man so nicht beurteilen, da der > Weichzeichnereffekt zu hoch ist. Wenn ich heute Abend Zeit habe werde ich das mal untersuchen. Gegen eine C(++) Implementierung oder Library für die FFT Variante hätte ich nix einzuwenden, einen Versuch ist es Wert.
Ich sollte vielleicht noch erwähnen das diese Verschiebung lediglich dazu verwendet wird einige Parameter zu ermitteln (Korrelation) und das verschobene Bild an sich so nicht weiter verwendet wird. Die Performance ist deswegen auch nicht ganz unerheblich.
Wenn Du es auf subpixelgenaue Registrierung der Bilder abgesehen hast, wonach sich das gerade anhört, dann schaue Dir doch mal die VTK-Libraries an oder implementiere die FFT-basierte Kreuzkorrelation (z.B. nach http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.13.3263&rep=rep1&type=pdf)
__UNDEFINED__ schrieb: > Wenn Du es auf subpixelgenaue Registrierung der Bilder abgesehen > hast, > wonach sich das gerade anhört, dann schaue Dir doch mal die > VTK-Libraries an oder implementiere die FFT-basierte Kreuzkorrelation > (z.B. nach > http://citeseerx.ist.psu.edu/viewdoc/download?doi=...) Danke für den Link, das muss ich mir in einer ruhigen Minute mal ansehen. Allerdings werde ich jetzt erst einmal ein schnelles "Proof of Concept" machen mit dem was schon funktioniert und dann entscheiden ob es sich lohnt mehr Arbeit rein zu stecken. VTK sieht auch genial für Visualisierung aus.
KlausPixel schrieb: > einige Parameter zu ermitteln (Korrelation) und das > verschobene Bild an sich so nicht weiter verwendet wird. Und genau dann bekommt man das Problem der Verschiebeartefakte.
> Die Frage verstehe ich nicht. Ich will doch eine Verschiebung haben. > Ja, du willst eine "Subpixel" Verschiebung. Wenn da noch zusätzlich das Bild um Pixel verschoben wird, wegen dem Algorithmus, ist dies irrelevant ? Warscheinlich hattest du es aber nicht gemerkt. Du hast eine Verschiebung der Pixel, weil du keinen Rand machst und die Pixelverschiebung auch nicht beachtest. >> wie der Weichzeichnereffekt dir warscheinlich nicht aufgefallen ist. > Doch aber wie Bildverwursteler schon sagt kann man eben keine scharfe > 1px breite Linie darstellen die genau zwischen 2 pixeln liegt. > Eine 1px breite Linie zwischen 2 pixeln interessiert keinem. Eine 4px breite Linie welche nun zu einer verschwommenen 6 Pixel Linie wird ist aber blöd. Deshalb wird dies meisten ausmaskiert und entsprechend behandelt. >> Ob sich das Gamma auch ändert kann man so nicht beurteilen, da der >> Weichzeichnereffekt zu hoch ist. > Wenn ich heute Abend Zeit habe werde ich das mal untersuchen. > > Gegen eine C(++) Implementierung oder Library für die FFT Variante hätte > ich nix einzuwenden, einen Versuch ist es Wert. Wenn die Geschwindigkeit notwendig ist, nimm die lineare Interpolation. Ich glaube, du hast keinen Stuss was du machst. Was du derzeit machst: Du nimmst das Orginalbild 1.bmp, verschiebst es um je 16 pixel in X und Y Richtung und speicherst dies in 2.bmp . Dann machst du dasselbe , nimmst 1.bmp, verschiebst es um je 15 pixel in X und Y Richtung und dann machst du noch einen Weichzeichner drauf. Was hat dies mit Subpixel zu tun ? Was willst/brauchst du effektiv ?
> Ja, du willst eine "Subpixel" Verschiebung. Wenn da noch zusätzlich > das Bild um Pixel verschoben wird, wegen dem Algorithmus, ist dies > irrelevant ? Ja, solange man weiß das das so ist kann man es ja kompensieren. > Warscheinlich hattest du es aber nicht gemerkt. Kann man so sagen > Du hast eine Verschiebung der Pixel, weil du keinen Rand machst und die > Pixelverschiebung auch nicht beachtest. Ich habe 16 Pixel Rand in jede Richtung, der Bildbereich der zur Korrelation verwendet wird ist 128x128, im Speicher liegt aber ein 160x160 Ausschnitt. Wie man sich sicherlich denken kann Schiebe ich nämlich am Anfang auch mal um ganze Pixel. > Ich glaube, du hast keinen Stuss was du machst. Das mag sein, deswegen habe ich ja ein Thread hier auf gemacht aber der überheblich Tonfall den du hier an den Tag legst lässt mich dazu neigen alles zu ignorieren was du sagst. > Was du derzeit machst: > Du nimmst das Orginalbild 1.bmp, verschiebst es um je 16 pixel in X und > Y Richtung und speicherst dies in 2.bmp . > Dann machst du dasselbe , nimmst 1.bmp, verschiebst es um je 15 pixel in > X und Y Richtung und dann machst du noch einen Weichzeichner drauf. Das ist der oben erwähnte Rand, wie man sieht Speicher ich nämlich nur 128px statt 160px. Später überlappen sich dann die 160x160 Ausschnitte des Bildes, die 128x128 Ausschnitte aber nicht...
>> Was du derzeit machst: >> Du nimmst das Orginalbild 1.bmp, verschiebst es um je 16 pixel in X und >> Y Richtung und speicherst dies in 2.bmp . >> Dann machst du dasselbe , nimmst 1.bmp, verschiebst es um je 15 pixel in >> X und Y Richtung und dann machst du noch einen Weichzeichner drauf. > Das ist der oben erwähnte Rand, wie man sieht Speicher ich nämlich nur > 128px statt 160px. Später überlappen sich dann die 160x160 Ausschnitte > des Bildes, die 128x128 Ausschnitte aber nicht... Nochmals, derzeit verschiebst du ein Bild um 16 Pixel und 14 Pixel, bei den 14 Pixel machst du noch einen Weichzeichner drauf. Den Code BicubicInterpolate macht folgendes: Er Interpoliert 16 Pixel (4x4). Also wenn du ein Bild in Auflösung 2560 x 1440 Pixel hast und das Bild mit diesem Code Reduzierst, dann erhälst du ein korrekt reduziertes Bild mit einer Auflösung von 160 x 90 Pixel. Wenn du hingegen keine Reduzierung machst, dann macht dieser Code einen Weichzeichner, eigentlich eine Convulution. Ich könnte dir die Coeffizienten der Convulutionsmatrix nennen, was eigentlich gemacht wird, aber dies ist ja nicht Sinn der Sache. Was brauchst du effektiv ?? Im Anghang ein quick and dirty code in C für eine Ausführliche lineare Interpolation mit etlichen Debug Output für dich. Er generiert auch ein pgm File für dich. Im Anhang der Output von x=0.33 und y=0.22 Verschiebung, in Gimp Differenz und dann Grau addiert und automatisch Normalisiert, damit man es besser sieht. Dies ist einfachst lineare Interpolation. Wenn du genau darlegen kannst was du benötigst, dann kann ich dir auch weiterhelfen.
Ob man einen Interpolations-Algorithmus zum vergrößern, verkleinern, rotieren, verschieben oder perspektivischen projizieren verwendet ist doch nur eine Frage mit welchen Parametern man ihn aufruft. Ich habe mal schnell ein Programm geschrieben was diese Interpolation zum rotieren um 26,3° verwendet. Das Ergebnis ist (bis auf die Artefakte außerhalb des ursprünglichen Bildbereichs) bis auf das letzte Bit identisch mit dem was Gimp 2.8 beim rotieren von Ebenen liefert!!! So ganz dumm kann ich also nicht sein. Warum du der Meinung bis das dieser Algorithmus nur zum 16x verkleinern eines Bildes taugt ist mir schleierhaft.
1 | QImage* pq_ImageIN = new QImage("/media/data/test/1.bmp"); |
2 | QImage* pq_ImageOUT = new QImage(160,160,QImage::Format_ARGB32); |
3 | double alpha = 26.3; |
4 | for(int i=-80; i<80; i++) |
5 | {
|
6 | for(int j=-80; j<80; j++) |
7 | {
|
8 | double f64_cord_x = 80.0 + (j*sin(alpha*PI/180)) + (i*cos(alpha*PI/180)); |
9 | double f64_cord_y = 80.0 - (i*sin(alpha*PI/180)) + (j*cos(alpha*PI/180)); |
10 | double f64_px = getGlobal(pq_ImageIN, f64_cord_x , f64_cord_y ); |
11 | f64_px = ( f64_px > 255.5 ) ? 255.0 : f64_px; |
12 | f64_px = ( f64_px < 0.0 ) ? 0.0 : f64_px; |
13 | uint8 px = round(f64_px); |
14 | pq_ImageOUT->setPixel(i+80,j+80, 0xFF000000|px|(px<<8)|(px<<16) ); |
15 | }
|
16 | }
|
17 | pq_ImageOUT->save("/media/data/test/rot26p3.bmp"); |
mit:
1 | double getGlobal(QImage* pq_img, double f64_x, double f64_y) |
2 | {
|
3 | uint32 u32_x = (uint32)f64_x; |
4 | uint32 u32_y = (uint32)f64_y; |
5 | double f64_res_x = f64_x - (double)u32_x; |
6 | double f64_res_y = f64_y - (double)u32_y; |
7 | double temp[4][4]; |
8 | |
9 | for(int i=0; i<4; i++) |
10 | {
|
11 | for(int j=0; j<4; j++) |
12 | {
|
13 | temp[i][j] = pq_img->pixel( (u32_x-1+i), (u32_y-1+j) ) & 0xFF; |
14 | }
|
15 | }
|
16 | return bicubicInterpolate(temp,f64_res_x, f64_res_y); |
17 | }
|
KlausPixel schrieb: > Gimp 2.8 beim rotieren von Ebenen liefert!!! Auf GIMP als Referenz würde ich mich aber nicht verlassen. Rotiere mal aum 3 Grad nach links, 5 nach rechts und wieder 2 nach links und vergleiche das Ergebnis. :D
Gimp, habe es probiert, 16.3 Grad nach rechts gedreht, und zurückgedreht. Der Weichzeichner war evident, das Gamma ist gesunken, hier eine kleine Animation. Den Code den du verwendest ist nicht Cubic sondern Catmull-Rom. Es kommt darauf an, was du benötigst und für was. Ich weiss natürlich daß der Code auch für andere Sachen gut geht, aber ohne Nebeneffekte eben nur für eine 16x Reduction. Wenn dir die Nebeneffekte egal sind, dann ist es für mehr auch verwendbar. Nur gerade bei image recognition macht dieser Algorithmus Artifakte, welche dann die nächsten Stufen der Erkennung empfindlich stören.
Wie man solche Testbilder verwenden kann ist mir ein Rätsel. Ihr wollt das verschieben im Sub-Pixelbereich testen. Dazu bräuchte man eher Bilder mit klaren Linien oder anderen klaren Strukturen, um den Effekt gut sichtbar zu machen.
Da gibt es doch sicher normierte Testbilder, oder? Ich bräuchte etwas in der Art, um einen Vorschausklierer zu testen.
Nimm einfach den Siemensstern oder besser gleich eine sog. Zoneplate. Bei letzterer sieht man die Aliasingeffekte deutlicher. Hab mal einen Quick-Hack Code angehängt, der eine als 10000x6666er PNM produziert (Linux: gcc -lm zoneplate.c; ./a.out >zp.pnm). Schau das Ergebnis mal verkleinert mit einem beliebigen Imageviewer an ;)
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.