home *** CD-ROM | disk | FTP | other *** search
/ PC Pro 2002 April / pcpro0402.iso / essentials / graphics / Gimp / gimp-src-20001226.exe / src / gimp / unofficial-plug-ins / fixer / patch_classifier.h < prev    next >
Encoding:
C/C++ Source or Header  |  2000-01-02  |  4.8 KB  |  180 lines
  1. /*
  2.     The Fixer - A GIMP plug-in for fixing borders and applying themes to images
  3.     Copyright (C) 2000  Paul Francis Harrison
  4.  
  5.     This program is free software; you can redistribute it and/or modify
  6.     it under the terms of the GNU General Public License as published by
  7.     the Free Software Foundation; either version 2 of the License, or
  8.     (at your option) any later version.
  9.  
  10.     This program is distributed in the hope that it will be useful,
  11.     but WITHOUT ANY WARRANTY; without even the implied warranty of
  12.     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13.     GNU General Public License for more details.
  14.  
  15.     You should have received a copy of the GNU General Public License
  16.     along with this program; if not, write to the Free Software
  17.     Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  18. */
  19.  
  20. /* Nearest vector classifier */
  21.  
  22. template<class t>
  23. struct Classifier {
  24.   struct Node {
  25.     int radius;
  26.     t branchChildItem;
  27.     Node *mainChild, *branchChild;
  28.  
  29.     Node() { mainChild = branchChild = 0; }
  30.     ~Node() { delete mainChild; delete branchChild; }
  31.  
  32.     void nearest(t &find,
  33.                  int yourDist,
  34.              t &best,
  35.          int &bestDist) {
  36.       if (!this)
  37.         return;
  38.  
  39.       if (bestDist == 0 || yourDist-radius > bestDist)
  40.     return;
  41.       
  42.       int branchDist = _distance(find,branchChildItem);
  43.  
  44.       if (branchDist < bestDist) {
  45.         bestDist = branchDist;
  46.     best = branchChildItem;
  47.       }
  48.  
  49.       if (yourDist < branchDist) {
  50.         mainChild->nearest(find, yourDist, best, bestDist);
  51.         branchChild->nearest(find, branchDist, best, bestDist);
  52.       } else {
  53.         branchChild->nearest(find, branchDist, best, bestDist);
  54.         mainChild->nearest(find, yourDist, best, bestDist);
  55.       }
  56.     }
  57.   };
  58.  
  59.   Node *buildNode(int nItems, t *items,  t &myItem) {
  60.     if (nItems == 1) {
  61.       myItem = items[0];
  62.       return 0;
  63.     }
  64.     
  65.     Node *nu = new Node;
  66.  
  67.     t means[2];
  68.     int partitionPoint;
  69.  
  70.     /* Pick two starting means arbitrarily */
  71.     means[0] = items[0];
  72.     means[1] = items[nItems/2];
  73.  
  74.     int iterations = 0;
  75.     for(;;) {
  76.       /* Partition, ala quicksort. Test this!!!!!!!!!!!! */
  77.       int lower=0, upper=nItems-1;
  78.       bool any = false;
  79.       for(;;) {
  80.         while(lower <= upper &&
  81.           _distance(items[lower],means[0]) >
  82.           _distance(items[lower],means[1]))
  83.      lower++;
  84.         while(lower <= upper &&
  85.           _distance(items[upper],means[1]) >
  86.           _distance(items[upper],means[0]))
  87.      upper--;
  88.  
  89.     if (lower > upper) break;
  90.  
  91.     t temp = items[lower];
  92.     items[lower] = items[upper];
  93.     items[upper] = temp;
  94.     lower++; upper--;
  95.     any = true;
  96.       }
  97.       
  98.       partitionPoint = lower;
  99.  
  100.       /* Stop if partition is stable, or we have been iterating
  101.          for too long and don't seem to be getting anywhere, or
  102.      the partition has somehow become degenerate, all in one and
  103.      none in the other. */
  104.       if (!any || iterations > 8 ||
  105.           partitionPoint == 0 || partitionPoint == nItems) break;
  106.  
  107.       iterations++;
  108.       
  109.       /* Calculate means */
  110.       means[0] = items[0];
  111.       for(int i=1;i<partitionPoint;i++)
  112.         means[0] = means[0] + items[i];
  113.       means[0] = means[0] / partitionPoint;
  114.  
  115.       means[1] = items[partitionPoint];
  116.       for(int i=partitionPoint+1;i<nItems;i++)
  117.         means[1] = means[1] + items[i];
  118.       means[1] = means[1] / (nItems-partitionPoint);
  119.     }
  120.  
  121.     /* Did k-means fail utterly? If so just divide arbitrarily */
  122.     if (partitionPoint == nItems || partitionPoint == 0) {
  123.       //printf("Bah.\n");
  124.       partitionPoint = nItems/2;
  125.     }
  126.  
  127.     /* Build main child with larger partition, branch child with smaller */ 
  128.     if (partitionPoint > nItems - partitionPoint) {
  129.       nu->mainChild = buildNode(partitionPoint,items, myItem); 
  130.       nu->branchChild = buildNode(nItems-partitionPoint,items+partitionPoint, 
  131.                                   nu->branchChildItem); 
  132.     } else {
  133.       nu->mainChild = buildNode(nItems-partitionPoint,items+partitionPoint, 
  134.                                 myItem); 
  135.       nu->branchChild = buildNode(partitionPoint,items,nu->branchChildItem); 
  136.     }
  137.     
  138.     /* Calculate radius */
  139.     nu->radius = 0;
  140.     for(int i=0;i<nItems;i++) {
  141.       int d = _distance(myItem,items[i]);
  142.       if (d > nu->radius)
  143.     nu->radius = d;
  144.     } 
  145.  
  146.     return nu;
  147.   }
  148.  
  149.   Node *tree;
  150.   t rootItem;
  151.   
  152.   Classifier() : tree(0) { }
  153.   ~Classifier() { delete tree; }
  154.   
  155.   void build(int nItems,t *items) {
  156.     delete tree;
  157.     tree = buildNode(nItems, items,  rootItem);
  158.   }
  159.  
  160.   t nearest(t &find, t hint,  int &bestDist) { 
  161.     t best = hint;
  162.     bestDist = _distance(hint,find);
  163.  
  164.     int rootDist = _distance(find,rootItem);
  165.     if (rootDist < bestDist) {
  166.       bestDist = rootDist;
  167.       best = rootItem;
  168.     }
  169.     
  170.     tree->nearest(find,
  171.               rootDist,
  172.           best,
  173.           bestDist); 
  174.     return best;
  175.   }
  176. };
  177.  
  178.  
  179.  
  180.