Re: [Schrodinger-devel] Possible optimisation for to find the median value

[<yan...@fr...>]

> > > Sorting neighboring pixel values is a particularly dumb method of
> > > doing a CWM filter (when all you want is the median), so fixing the
> > > dumb method of sorting is not really going to make the code good.
> > > The correct way to do CWM is roughly min(max(center,min(neighbors),
> > > max(neighbors)), at least for weight=4.  (IIRC, this is from memory)
>
> If this is only for to find the median, this code seem to produce a good
> approximation of the true median for a 3x3 patch (in fact, this seem to
> return
> the true median value the majority of time)
>
> inline int median3(int a, int b, int c)
> {
> 	if ( a <= b )
> 	{
> 		if ( b <= c )
> 			return b;
> 		if ( c <= a )
> 			return a;
> 		return c;
> 	}
>
> 	// a > b
> 	if ( a <= c )
> 		return a;
> 	if ( b <= c )
> 		return c;
> 	return b;
> }
>
>
> void fast_median3x3(int *d)
> {
>
> 	int m1, m2 ,m3, m4;
>
> 	m1 = median3(d[0], d[1], d[2]);
> 	m2 = median3(d[3], d[4], d[5]);
> 	m3 = median3(d[6], d[7], d[8]);
>
> 	return median3(m1,m2,m3);
> }
>
> Note that the median3() func is coded very ugly and can certainly to be coded
> for to be very more speed
> (it only return the median from 3 values)
>
> On other side, I have found something that produce one approximation of
> the median for patchs biggers than 3x3, but the value returned can be very
> far
> from the true median value :(
> (n=9 for 3x3 patchs and n have always to be >= 3)
>
>
> int approx_median(int *d , int n)
> {
>
> 	int i, v, imin=255, imax=-255, sum = 0;
>
> 	for (i= 0; i < n; i++ )
> 	{
> 		v = d[i];
>
> 		if (v < imin )
> 		{
> 			imin = v;
> 		}
> 		else
> 		if ( v > imax )
> 		{
> 			imax = v;
> 		}
> 		sum += v;
> 	}
>
> 	return (sum - imin - imax)/(n-2);
>  }
>
> In fact, this compute the mean but without the minimum and maximum extrems
> values
> (this can for example to be used for to filter pictures with a little
> impulsed
> white noise)

Note too that with a very simple inversion of the j loop, we have already a very
big reduction on the number of bubbles swaps (about 50%)

int BubbleSort_ext(int *data, int n)
{
        int i, j, tmp, nswaps = 0;

        for (i = 0 ; i < n ; i++)
        {
                /* for( j = i + 1 ; j < n ; j++) */
		for( j = n - 1 ; j > i ; j--)
		{
        		if( data[i] > data[j] )
        		{
        			nswaps++;
        			tmp     = data[i];
        			data[i] = data[j];
        			data[j] = tmp;
			}
                }
        }

        return nswaps;
}


Unsorted (16 values) : 206 188 63 212 135 171 238 21 224 153 234 208 16 67 84
109


Original Bubble Sort :  (70 swaps)
BubbleSorted v0 (16 values) : 16 21 63 67 84 109 135 153 171 188 206 208 212 224
234 238


Modified Bubble Sort :  (30 swaps)
BubbleSorted v1 (16 values) : 16 21 63 67 84 109 135 153 171 188 206 208 212 224
234 238


@+
Yannoo