Bilder verkleinern

-Foo-

Hi,
ich brauchte eine Routine zum skalieren von Grafiken für mein Programm, und das ganze sollte natürlich schnell sein. Deswegen dachte ich: Du hörst immer: Divisionen und Fließkommarechnung ist langsam, also verzichtest du sogut wie möglich darauf.

Also hab ich mir ein bisschen Gedanken gemacht und dann hab ich auch ein bisschen programmiert. Meine Funktion kann nun Grafiken verkleinern (das reicht momentan erstmal) und benötigt dafür nur zwei Divisionen, diverse Bitverschiebungen und keine Fließkommazahlen.

Einziges Problem: Das ganze bringt es auf nicht mehr als etwa 15-20 Bilder, die von 640x480 auf 480x360 runterskaliert werden. Da ich das jedoch im Zusammenhang mit Video benutzen möchte, wären 30 Bilder pro Sekunde schon angebracht

Deswegen meine Frage: wie kann ich die Funktion beschleunigen?
Gruß, Olli

Meine Funktion:
die verwendeten eigenen Funktionen (image_create, image_get_row, etc) sollten selbsterklärend sein

li_image *image_get_scaled( li_image *source, int width, int height ) {
	if( source->width == width && source->height == height )
		return image_create_copy( source );

	FV_StartTimer( 0 );

	li_image *scaled_x = NULL, *scaled_y = NULL;

	if( source->width != width ) {
		scaled_x = image_create( width, source->height );

		if( width < source->width ) {
			int x, y, i;
			int *lookup_x = malloc( sizeof( int ) * source->width * 3 );
			int *row_output = malloc( sizeof( int ) * width * 4 );

			int factor = (width << 8) / source->width;
			for( x = 0; x < source->width; x++ ) {
				int dx = factor * x;
				int dxr = dx & 0xff;

				int weight_1 = li_min( 255 - dxr, factor );
				int weight_2 = factor - weight_1;

				lookup_x[ 3 * x ] = dx >> 8;
				lookup_x[ 3 * x + 1 ] = weight_1;
				lookup_x[ 3 * x + 2 ] = weight_2;
			}

			for( y = 0; y < source->height; y++ ) {
				li_color *row_source = image_get_row( source, y );
				li_color *row_scaled = image_get_row( scaled_x, y );
				memset( row_output, 0, sizeof( int ) * width * 4 );

				for( x = 0; x < source->width; x++ ) {
					for( i = 0; i < 4; i++ ) {
						int dx = lookup_x[ 3 * x ];
						row_output[ 4 * dx + i ] +=	(row_source[x].v[i] * lookup_x[ 3 * x + 1 ]);

						if( lookup_x[ 3 * x + 2 ] && dx + 1 < width )
							row_output[ 4 * (dx + 1) + i ] += (row_source[x].v[i] * lookup_x[ 3 * x + 2 ] );
					}
				}

				for( x = 0; x < width; x++ ) {
					for( i = 0; i < 4; i++ )
						(row_scaled + x)->v[i] = (row_output[ 4 * x + i ] >> 8) & 0xff;
				}

			}

			free( row_output );
			free( lookup_x );
		}
	}

	if( source->height != height ) {
		if( scaled_x ) source = scaled_x;

		scaled_y = image_create( source->width, height );

		if( height < source->height ) {
			int x, y, i;
			int *lookup_y = malloc( sizeof( int ) * source->height * 3 );
			int *col_output = malloc( sizeof( int ) * height * 4 );

			int factor = (height << 8) / source->height;
			for( y = 0; y < source->height; y++ ) {
				int dy = factor * y;
				int dyr = dy & 0xff;

				int weight_1 = li_min( 256 - dyr, 192 );
				int weight_2 = 192 - weight_1;

				lookup_y[ 3 * y ] = dy >> 8;
				lookup_y[ 3 * y + 1 ] = weight_1;
				lookup_y[ 3 * y + 2 ] = weight_2;
			}

			for( x = 0; x < source->width; x++ ) {
				memset( col_output, 0, sizeof( int ) * height * 4 );
				li_color *col_source = source->data + x;

				for( y = 0; y < source->height; y++ ) {
					for( i = 0; i < 4; i++ ) {
						int dy = lookup_y[ 3 * y];
						col_output[ 4 * dy + i ] +=
								col_source[ y * source->width ].v[i] * lookup_y[ 3 * y + 1 ];

						if( lookup_y[ 3 * y + 2 ] && dy + 1 < height ) {
							col_output[ 4 * (dy + 1) + i ] +=
									col_source[ y * source->width ].v[i] * lookup_y[ 3 * y + 2 ];
						}
					}
				}

				for( y = 0; y < height; y++ ) {
					for( i = 0; i < 4; i++ )
						(scaled_y->data + y * width + x)->v[i] =
							(unsigned char)(col_output[ 4 * y + i ] >> 8);
				}

			}

			free( col_output );
			free( lookup_y );
		}
	}

	if( scaled_y ) {
		if( scaled_x )
			image_destroy( scaled_x );

		FV_StopTimer( 0 );
		return scaled_y;
	}

	if( scaled_x && !scaled_y ) {
		FV_StopTimer( 0 );
		return scaled_x;
	}

	return NULL;
}

thordk

auf was für nen lahmen möhre arbeitest du denn da? ^^ soll die skalierung interpolieren oder reichts, wenn einfach überflüssige pixel rausgeschmissen werden?
und nen genereller tipp: für arbeiten auf den pixeln ist es häufig effizienter, wenn die pixeldaten in nem eindimensionalen array vorliegen, damit rumgerechnet wird und erst ganz zum schluss das ergebnis wieder in ein high level objekt transformiert wird.

-Foo-

Also ich dachte mir interpolieren ist schon schön, sonnst wär das bestimmt schneller, aber ich kann mir vorstellen, dass es dann irgendwann ziemlich kacke ausschaut.
Meine lahme Krücke ist ein Pentium 4 mit 3.06Ghz (das war der erste mit HT, soweit ich mich erinnere =)... gut bringt mir jetzt hier wenig... )
Naja das mit dem eindimensionalen Array kann ich ja nochmal drauf übertragen, vllt bringt das ja tatsächlich noch was, aber ich arbeite ja im Prinzip schon mit einem eindimensionalen Array, nur dass ich das nach jeder Zeile wieder zurück schreib statt am Ende... Dürfte im Prinzip doch nciht viel unterschied machen?
Gruß, Olli

thordk

hab grad mal ne variante zusammengeklebt, die mit unsigned chars auf eindimensional arrays arbeitet aber haufenweise float multiplikationen verwendet. reine skalierungen ohne sonstigen schnickschnack purzeln da ca. 125 pro sekunde raus. (für die interpolation hab ich ne simple 3x3 faltung verwendet)
glaub mit ner einfachen straight forward lösung ist man doch schneller ^^

da sieht man es mal wieder. es kommt auf den algorithmus an und nicht drauf ein paar "perfomancetricks" zu verwenden. google mal nach "faltung" und "separierbare filter".

thordk

hab das ding mal hier hingepackt http://nopaste.info/0c0318a76a.html
ewig kein reines c mehr gecodet, übernehm keine verantwortung für standard konformität
soll eher als beispiel gelten, ist eigentlich kein bisschen optimiert.