Median Filter und Optimierungsproblem

Hallo,
ich schreibe gerade für meine Webcam einen Medianfilter. (Nimmt alle Pixel in einem kleinen Umkreis um den Pixel XY, sortiert sie aufsteigend und nimmt dann den mittleren Wert und ersetzt XY dagegen.)
Ich hab ihn auch implementiert, allerdings lässt die Performance trotz Optimierung zu wünschen über ( etwa 1 Frame pro Sekunde bei 320x240 Pixeln (RGB, je ein unsigned char) )
Wie könnte man den noch weiter optimieren? (Am besten so aufs 10 fache *utopische Gedanken hab*)

#define UVC_MEDIAN_KERNEL_SIZE 5
void uvc_filter_median( struct s_uvc_connection *uvc, unsigned char *input, int length ) {
	static unsigned char *buffer = NULL;

	unsigned char pixel[3][ UVC_MEDIAN_KERNEL_SIZE * UVC_MEDIAN_KERNEL_SIZE ];
	unsigned char pixel_sorted[ UVC_MEDIAN_KERNEL_SIZE * UVC_MEDIAN_KERNEL_SIZE ];

	int x, y, dx, dy, a, b, count, i;

	if( !buffer ) {
		buffer = malloc( length );
	}

	if( buffer ) {
		for( y = 0; y < uvc->height - UVC_MEDIAN_KERNEL_SIZE; y++ ) {
			for( x = 0; x < uvc->width - UVC_MEDIAN_KERNEL_SIZE; x++ ) {

				if( x == 0 ) {
					for( a = 0; a < UVC_MEDIAN_KERNEL_SIZE; a++ ) {
						for( b = 0; b < UVC_MEDIAN_KERNEL_SIZE; b++ ) {
							dx = x + a;
							dy = y + b;
							for( i = 0; i < 3; i++ )
								pixel[i][a * UVC_MEDIAN_KERNEL_SIZE + b] = *( input + 3 * ( dy * uvc->width + dx ) + i);
						}
					}
				} else {
					a = ( (x - 1) % UVC_MEDIAN_KERNEL_SIZE);
					dx = x + UVC_MEDIAN_KERNEL_SIZE - 1;
					for( b = 0; b < UVC_MEDIAN_KERNEL_SIZE; b++ ) {
						dy = y + b;
						for( i = 0; i < 3; i++ )
							pixel[i][a * UVC_MEDIAN_KERNEL_SIZE + b] = *( input + 3 * ( dy * uvc->width + dx ) + i);
					}
				}

				count = UVC_MEDIAN_KERNEL_SIZE * UVC_MEDIAN_KERNEL_SIZE;
				for( i = 0; i < 3; i++ ) {
					memcpy( pixel_sorted, pixel[i], count );
					uvc_quicksort_uchar( pixel_sorted, 0, count );

					*( buffer + 3 * ( y * uvc->width + x ) + i) = pixel_sorted[ count / 2 ];
				}

			}
		}

		memcpy( input, buffer, length );
	}
}

void uvc_quicksort_uchar(unsigned char *a, int left, int right) {

	unsigned char pivot = a[ right ];
	int l = left;
	int r = right;
	unsigned char swap;
	if( left < right ) {	
		do {
			while (a[l] < pivot) l++;
			while (a[r] > pivot) r--;

			if (l <= r) {
				swap = a[l];
				a[l] = a[r];
				a[r] = swap;
				l++;
				r--;
			}
		} while (l <= r);

		uvc_quicksort_uchar(a, left, r);
		uvc_quicksort_uchar(a, l, right);
	}
}

xivVerge

Probiers mal damit. Das ist etwas besser als Quicksort, weil es abbricht, wenn der Median gefunden ist.

#define ELEM_SWAP(a,b) { register int t=(a);(a)=(b);(b)=t; }

int quickmedian(int arr[], int n) 
{
    int low, high;
    int median;
    int middle, ll, hh;

    low = 0 ; high = n-1 ; median = (low + high) >> 1;
    for ( ;; ) 
	{
        if ( high <= low )
            return arr[median];

        if ( high == low + 1 )
		{  
            if (arr[low] > arr[high])
                ELEM_SWAP(arr[low], arr[high]);
            return arr[median];
        }

		middle = (low + high) >> 1;
		if ( arr[middle] > arr[high] )    
			ELEM_SWAP(arr[middle], arr[high]);
		if ( arr[low] > arr[high] )       
			ELEM_SWAP(arr[low], arr[high]);
		if ( arr[middle] > arr[low] )     
			ELEM_SWAP(arr[middle], arr[low]);

		ELEM_SWAP(arr[middle], arr[low+1]);

		ll = low + 1;
		hh = high;
		for ( ;; ) 
		{
			do ll++; while ( arr[low] > arr[ll] );
			do hh--; while ( arr[hh]  > arr[low] );

			if ( hh < ll )
				break;

			ELEM_SWAP(arr[ll], arr[hh]);
		}

		ELEM_SWAP(arr[low], arr[hh]);

		if ( hh <= median )
			low = ll;
		if ( hh >= median )
			high = hh - 1;
    }
}

#undef ELEM_SWAP

du übergibst ein Array und die Größe des Arrays.
Is recht schnell.

Dann kannst du dir redundante Berechnungen sparen. z.B. count wird für jeden Pixel neu berechnet. Genauso die Position im Pixel-Array ( Pixel[i][...] ). Da einfach mal ne Laufvariable mit in die b-Schleife packen. usw.

Verge

Hey, die quickmedian Funktion erhöht die Geschwindigkeit bereits auf das 3fache
Von 2 auf 6fps *strahl*, vielen Dank.

Der Flaschenhals liegt eh in der Sortier/quickmedian funktion. Denn wenn ich diese nicht aufrufe, dann habe ich volle fps Zahl.
Gruß, Olli

ten

Only-Olli schrieb:

Der Flaschenhals liegt eh in der Sortier/quickmedian funktion. Denn wenn ich diese nicht aufrufe, dann habe ich volle fps Zahl.
Gruß, Olli

nimm doch einfach den mittelwert, dann brauchst nix zu sortieren.
vielleicht reicht das schon...

c.rackwitz

ten schrieb:

nimm doch einfach den mittelwert, dann brauchst nix zu sortieren.

median und average sind erstmal verschiedene sachen. dann hat median ne ganz andere bedeutung als average. "average" reicht vielleicht *nicht* mal so. der OP wird sich doch kaum grundlos die muehe machen.

ten

c.rackwitz schrieb:

dann hat median ne ganz andere bedeutung als average.

ist doch beides zum rauschen wegfiltern, oder?

c.rackwitz schrieb:

"average" reicht vielleicht *nicht* mal so. der OP wird sich doch kaum grundlos die muehe machen.

wer weiss. vielleicht reicht ein mean filter mit grösseren blöcken in seinem fall.
muss man immer abwägen, geschwindigkeit oder schlechterer filteralgo.
natürlich gibt's noch andere tricks, wie assembler benutzen oder 'nen coprozessor...

btw: vielleicht hilft das: http://ndevilla.free.fr/median/median.pdf

Hi,
einen Mean-Filter habe ich bereits implementiert, jetzt wollte ich eben den Median-Filter einbauen.
Das ganze verfolgt keinen wirklich wichtigen zweck, es macht halt einfach nur das Bild meiner Webcam schöner (Der Mean-Filter ist mir zu unscharf ^^)
Vielen Dank für die Hilfe und auch die letzte PDF,
Gruß, Olli

hellihjb

du berechnest den median fuer den umkreis (in deinem beispiel 10x10 pixel) jedes pixels komplett.
in dem moment wo du den naechsten pixel bearbeitest, kannst du einen grossen teil dieser berechnung wiederverwerten, denn es kommen nur 10 neue pixel dazu, 10 fallen raus, 90 bleiben erhalten - der aufwand reduziert sich also auf 10%.
(edit: nagut, so steht's auch schon im pdf...)

weitere kleinigkeiten:

for( x = 0; x < uvc->width - UVC_MEDIAN_KERNEL_SIZE; x++ )
{
  if( x == 0 )
    // ...
  else
    // ...
}

sowas ist bloedsinn. erledige x=0 zuerst und dann die schleife.

for( x = 0; x < ...; x++ )
  a = ( (x - 1) % UVC_MEDIAN_KERNEL_SIZE);

modulo ist division und langsam.
du weisst dass "a" nach jeweils "UVC_MEDIAN_KERNEL_SIZE" pixeln auf 0 gesetzt wird.
unterteile deine schleife in stuecke der lanege "UVC_MEDIAN_KERNEL_SIZE" und resette "a" manuell.

hellihjb schrieb:

du berechnest den median fuer den umkreis (in deinem beispiel 10x10 pixel) jedes pixels komplett.
in dem moment wo du den naechsten pixel bearbeitest, kannst du einen grossen teil dieser berechnung wiederverwerten, denn es kommen nur 10 neue pixel dazu, 10 fallen raus, 90 bleiben erhalten - der aufwand reduziert sich also auf 10%.
(edit: nagut, so steht's auch schon im pdf...)

weitere kleinigkeiten:
for( x = 0; x < uvc->width - UVC_MEDIAN_KERNEL_SIZE; x++ )
{
  if( x == 0 )
    // ...
  else
    // ...
}

aber genau mit dem stück quelltext, das du zitiert hast, unterscheide ich ja, ob es der erste pixel in einer reihe ist, oder nicht, und entscheide dann ob ich den kompletten (übrigens nur 5x5 px großen umkreis) berechne, oder nur die nächsten 5pixel