Category : C Source Code
Archive   : GRAFGEM1.ZIP
Filename : MEDIAN.C

/*
Median Finding on a 3-by-3 Grid
by Alan Paeth
from "Graphics Gems", Academic Press, 1990
*/

#define s2(a,b) {register int t; if ((t=b-a)<0) {a+=t; b-=t;}}
#define mn3(a,b,c) s2(a,b); s2(a,c);
#define mx3(a,b,c) s2(b,c); s2(a,c);
#define mnmx3(a,b,c) mx3(a,b,c); s2(a,b);
#define mnmx4(a,b,c,d) s2(a,b); s2(c,d); s2(a,c); s2(b,d);
#define mnmx5(a,b,c,d,e) s2(a,b); s2(c,d); mn3(a,c,e); mx3(b,d,e);
#define mnmx6(a,b,c,d,e,f) s2(a,d); s2(b,e); s2(c,f);\
mn3(a,b,c); mx3(d,e,f);
med3x3(b1, b2, b3)
int *b1, *b2, *b3;
/*
* Find median on a 3x3 input box of integers.
* b1, b2, b3 are pointers to the left-hand edge of three
* parallel scan-lines to form a 3x3 spatial median.
* Rewriting b2 and b3 as b1 yields code which forms median
* on input presented as a linear array of nine elements.
*/
{
register int r1, r2, r3, r4, r5, r6;
r1 = *b1++; r2 = *b1++; r3 = *b1++;
r4 = *b2++; r5 = *b2++; r6 = *b2++;
mnmx6(r1, r2, r3, r4, r5, r6);
r1 = *b3++;
mnmx5(r1, r2, r3, r4, r5);
r1 = *b3++;
mnmx4(r1, r2, r3, r4);
r1 = *b3++;
mnmx3(r1, r2, r3);
return(r2);
}


/* t2(i,j) transposes elements in A[] such that A[i] <= A[j] */

#define t2(i, j) s2(A[i-1], A[j-1])


int median25(A)
int A[25];
{
/*
* median25(A) partitions the array A[0..24] such that element
* A[12] is the median and subarrays A[0..11] and A[13..24]
* are partitions containing elements of smaller and larger
* value (rank), respectively.
*
* The exchange table lists element indices on the range 1..25,
* this accounts for the "-1" offsets in the macro t2 and in
* the final return value used to adjust subscripts to C-code
* conventions (array indices begin at zero).
*/
t2( 1, 2); t2( 4, 5); t2( 3, 5); t2( 3, 4); t2( 7, 8);
t2( 6, 8); t2( 6, 7); t2(10,11); t2( 9,11); t2( 9,10);
t2(13,14); t2(12,14); t2(12,13); t2(16,17); t2(15,17);
t2(15,16); t2(19,20); t2(18,20); t2(18,19); t2(22,23);
t2(21,23); t2(21,22); t2(24,25); t2( 3, 6); t2( 4, 7);
t2( 1, 7); t2( 1, 4); t2( 5, 8); t2( 2, 8); t2( 2, 5);
t2(12,15); t2( 9,15); t2( 9,12); t2(13,16); t2(10,16);
t2(10,13); t2(14,17); t2(11,17); t2(11,14); t2(21,24);
t2(18,24); t2(18,21); t2(22,25); t2(19,25); t2(19,22);
t2(20,23); t2( 9,18); t2(10,19); t2( 1,19); t2( 1,10);
t2(11,20); t2( 2,20); t2( 2,11); t2(12,21); t2( 3,21);
t2( 3,12); t2(13,22); t2( 4,22); t2( 4,13); t2(14,23);
t2( 5,23); t2( 5,14); t2(15,24); t2( 6,24); t2( 6,15);
t2(16,25); t2( 7,25); t2( 7,16); t2( 8,17); t2( 8,20);
t2(14,22); t2(16,24); t2( 8,14); t2( 8,16); t2( 2,10);
t2( 4,12); t2( 6,18); t2(12,18); t2(10,18); t2( 5,11);
t2( 7,13); t2( 8,15); t2( 5, 7); t2( 5, 8); t2(13,15);
t2(11,15); t2( 7, 8); t2(11,13); t2( 7,11); t2( 7,18);
t2(13,18); t2( 8,18); t2( 8,11); t2(13,19); t2( 8,13);
t2(11,19); t2(13,21); t2(11,21); t2(11,13);
return(A[13-1]);
}