home *** CD-ROM | disk | FTP | other *** search
/ Photo CD Demo 1 / Demo.bin / gems / graphics / median.c < prev    next >
Text File  |  1992-04-09  |  3KB  |  80 lines
  1. /*
  2. Median Finding on a 3-by-3 Grid
  3. by Alan Paeth
  4. from "Graphics Gems", Academic Press, 1990
  5. */
  6.  
  7. #define s2(a,b) {register int t; if ((t=b-a)<0) {a+=t; b-=t;}}
  8. #define mn3(a,b,c) s2(a,b); s2(a,c);
  9. #define mx3(a,b,c) s2(b,c); s2(a,c);
  10. #define mnmx3(a,b,c) mx3(a,b,c); s2(a,b);
  11. #define mnmx4(a,b,c,d) s2(a,b); s2(c,d); s2(a,c); s2(b,d);
  12. #define mnmx5(a,b,c,d,e) s2(a,b); s2(c,d); mn3(a,c,e); mx3(b,d,e);
  13. #define mnmx6(a,b,c,d,e,f) s2(a,d); s2(b,e); s2(c,f);\
  14.                             mn3(a,b,c); mx3(d,e,f);
  15. med3x3(b1, b2, b3)
  16.     int *b1, *b2, *b3;
  17. /*
  18.  * Find median on a 3x3 input box of integers.
  19.  * b1, b2, b3 are pointers to the left-hand edge of three
  20.  * parallel scan-lines to form a 3x3 spatial median.
  21.  * Rewriting b2 and b3 as b1 yields code which forms median
  22.  * on input presented as a linear array of nine elements.
  23.  */
  24.     {
  25.     register int r1, r2, r3, r4, r5, r6;
  26.     r1 = *b1++; r2 = *b1++; r3 = *b1++;
  27.     r4 = *b2++; r5 = *b2++; r6 = *b2++;
  28.     mnmx6(r1, r2, r3, r4, r5, r6);
  29.     r1 = *b3++;
  30.     mnmx5(r1, r2, r3, r4, r5);
  31.     r1 = *b3++;
  32.     mnmx4(r1, r2, r3, r4);
  33.     r1 = *b3++;
  34.     mnmx3(r1, r2, r3);
  35.     return(r2);
  36.     }
  37.  
  38.  
  39. /* t2(i,j) transposes elements in A[] such that A[i] <= A[j] */
  40.  
  41. #define t2(i, j) s2(A[i-1], A[j-1])
  42.  
  43.  
  44. int median25(A)
  45.     int A[25];
  46.     {
  47. /*
  48.  * median25(A) partitions the array A[0..24] such that element
  49.  * A[12] is the median and subarrays A[0..11] and A[13..24]
  50.  * are partitions containing elements of smaller and larger
  51.  * value (rank), respectively.
  52.  *
  53.  * The exchange table lists element indices on the range 1..25,
  54.  * this accounts for the "-1" offsets in the macro t2 and in
  55.  * the final return value used to adjust subscripts to C-code
  56.  * conventions (array indices begin at zero).
  57.  */
  58.     t2( 1, 2); t2( 4, 5); t2( 3, 5); t2( 3, 4); t2( 7, 8);
  59.     t2( 6, 8); t2( 6, 7); t2(10,11); t2( 9,11); t2( 9,10);
  60.     t2(13,14); t2(12,14); t2(12,13); t2(16,17); t2(15,17);
  61.     t2(15,16); t2(19,20); t2(18,20); t2(18,19); t2(22,23);
  62.     t2(21,23); t2(21,22); t2(24,25); t2( 3, 6); t2( 4, 7);
  63.     t2( 1, 7); t2( 1, 4); t2( 5, 8); t2( 2, 8); t2( 2, 5);
  64.     t2(12,15); t2( 9,15); t2( 9,12); t2(13,16); t2(10,16);
  65.     t2(10,13); t2(14,17); t2(11,17); t2(11,14); t2(21,24);
  66.     t2(18,24); t2(18,21); t2(22,25); t2(19,25); t2(19,22);
  67.     t2(20,23); t2( 9,18); t2(10,19); t2( 1,19); t2( 1,10);
  68.     t2(11,20); t2( 2,20); t2( 2,11); t2(12,21); t2( 3,21);
  69.     t2( 3,12); t2(13,22); t2( 4,22); t2( 4,13); t2(14,23);
  70.     t2( 5,23); t2( 5,14); t2(15,24); t2( 6,24); t2( 6,15);
  71.     t2(16,25); t2( 7,25); t2( 7,16); t2( 8,17); t2( 8,20);
  72.     t2(14,22); t2(16,24); t2( 8,14); t2( 8,16); t2( 2,10);
  73.     t2( 4,12); t2( 6,18); t2(12,18); t2(10,18); t2( 5,11);
  74.     t2( 7,13); t2( 8,15); t2( 5, 7); t2( 5, 8); t2(13,15);
  75.     t2(11,15); t2( 7, 8); t2(11,13); t2( 7,11); t2( 7,18);
  76.     t2(13,18); t2( 8,18); t2( 8,11); t2(13,19); t2( 8,13);
  77.     t2(11,19); t2(13,21); t2(11,21); t2(11,13);
  78.     return(A[13-1]);
  79.     }
  80.