~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~ [ freetext search ] ~ [ file search ] ~

Linux Cross Reference
Tina4/src/tools/nmr-segment/nearest.c

Version: ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  1 /*
  2   nearest.c
  3 
  4   n.thacker
  5 */
  6 
  7 
  8 #include <stdio.h>
  9 #include <values.h>
 10 #include <tina/sys.h>
 11 #include <tina/sysfuncs.h>
 12 #include <tina/math.h>
 13 #include <tina/mathfuncs.h>
 14 #include <tina/vision.h>
 15 #include <tina/visionfuncs.h>
 16 #include <tina/seqoral.h>
 17 #include <tina/stimdef.h>
 18 #include <tina/hist_funcs.h>
 19 
 20 #define KNNTYPE 1000
 21 #define KNNTHRES 2.0
 22 #define KNNUNSEEN exp(-2.0*KNNTHRES*KNNTHRES)
 23 #define NEIGHBOURS 10
 24 
 25 static shistogram *monitor=NULL;
 26 static int total_knn=0;
 27 extern void ***coreg_limits(int *lz, int *uz, int *ly,
 28                                 int *uy, int *lx, int *ux);
 29 
 30 extern void ***coreg_slice_init(Vec3 *ptr);
 31 
 32 static void ***imptrs = NULL;
 33 static   int   imptrlx, imptrux, imptrly, imptruy, imptrlz, imptruz;
 34 
 35 /* the nearest neighbour list data structure is one of pointers to
 36 Match sttuctures
 37 
 38 match->to1  ; leading to   fvector arrays of point in an 
 39 match->type ; dimensional space.
 40 match->to2  ; is for the associated classification structure and
 41 match->weight ; is for parzen density estimation;
 42  */
 43 
 44 double distance_func(float *data1, float *data2, int n)
 45 {
 46    int i;
 47    double dist = 0.0;
 48 
 49    for (i=0;i<n;i++)
 50    {
 51       dist += (data1[i]-data2[i]) *(data1[i]-data2[i]);
 52    }
 53    return(dist/2.0);
 54 }
 55 
 56 void **knn_listfree(void **nearest, int near)
 57 {
 58    int i;
 59    for (i=0;i<near;i++)
 60       rfree((void *)(nearest[i]));
 61    pvector_free(nearest,0);
 62    return(NULL);
 63 }
 64 
 65 void **knn_list(List *density_list, int neighbours, float *data,
 66               double(*distance_func)(/* */))
 67 {
 68    List *plist, *nlist;
 69    void **nearest;
 70    Match *mptr,*nptr,*lptr;
 71    float knn_dist=MAXFLOAT;
 72    double dist;
 73    int i;
 74 
 75    if (density_list ==NULL) return(NULL);
 76    nearest = pvector_alloc(0,neighbours);
 77    for(plist = density_list; plist !=NULL; plist = plist->next)
 78    {
 79       mptr = plist->to;
 80       dist = distance_func(data, mptr->to1, mptr->type);
 81       if (dist  < knn_dist)
 82       {
 83          nptr = match_alloc(mptr->type); 
 84          nptr->to1 = data;
 85          nptr->weight = dist;
 86          nptr->to2 = mptr; /* store matching node on this match */
 87          for (i=0; i<neighbours; i++)
 88          {
 89               lptr = (Match *)nearest[i];
 90               if (nptr!=NULL && (lptr ==NULL || dist < lptr->weight))
 91               {
 92                   nearest[i] = nptr;
 93                   if ((nptr!=NULL)&&(i==neighbours-1))
 94                     knn_dist = nptr->weight;
 95                   nptr = lptr;
 96               }
 97          }
 98          if (nptr!=NULL) rfree(nptr);
 99       }
100    } 
101    return(nearest);
102 }
103 
104 List *knn_destroy(List *density_list)
105 {
106    List *nlist;
107    Match *nptr;
108    float *data;
109 
110    for (nlist = density_list; nlist!=NULL; nlist = nlist->next)
111    {
112       nptr = nlist->to;
113       data = nptr->to1;
114       fvector_free(data,0);
115       rfree((void *)nptr);
116       rfree((void *)nlist);
117    }
118    total_knn = 0;
119    return(NULL);
120 }
121 
122 List *knn_build(List *density_list, float *data, void *classdata,
123                double(*distance_func)(/* */), float threshold,
124                 int vectordim)
125 {
126    List *nlist;
127    void **nearest = NULL;
128    Match *mptr,*nptr;
129    float knn_dist=MAXFLOAT;
130    float *data_copy;
131    float dist;
132    int i;
133 
134    nearest = knn_list(density_list, 1, data, distance_func); 
135    if (nearest==NULL ||
136     ((Match *)(nearest[0]))->weight > threshold)
137    {
138       nptr = match_alloc(vectordim); 
139       data_copy = (float *)fvector_alloc(0, vectordim);
140       for (i=0;i<vectordim;i++) data_copy[i] = data[i];
141       nptr->to1 = data_copy;
142       nptr->to2 = classdata;
143       density_list = link_addtostart(density_list, link_alloc(nptr, KNNTYPE));
144       total_knn++;
145    }
146    if (nearest!=NULL) nearest = knn_listfree(nearest,1);
147    return(density_list);
148 }
149 
150 void knn_fill(List *density_list, float *data,
151                double(*distance_func)(/*   */))
152 {
153    int i;
154    List *nlist;
155    void **nearest;
156    Match *mptr,*nptr;
157    float knn_dist=MAXFLOAT;
158    double dist;
159 
160    nearest = knn_list(density_list, NEIGHBOURS, data, distance_func);
161    for(i=0; i<NEIGHBOURS; i++)
162    {
163       if((mptr = nearest[i]) == NULL) break;
164       nptr = mptr->to2;
165       dist = mptr->weight;
166       hfill1(monitor,dist,1.0);
167       nptr->weight += exp(-dist); /* accumulate density of patterns */
168    } 
169    nearest = knn_listfree(nearest,NEIGHBOURS);
170 }
171 
172 float knn_density(List *density_list, float *data, 
173                double(*distance_func)(/* */))
174 {
175    int i;
176    List *nlist;
177    void **nearest;
178    Match *mptr,*nptr;
179    float dist, knnweight;
180    float knntot=KNNUNSEEN, knnsum=0.0;
181 
182    nearest = knn_list(density_list, NEIGHBOURS, data, distance_func);
183    for(i=0; i<NEIGHBOURS; i++)
184    {
185       if((mptr = nearest[i])==NULL) break;
186       nptr = mptr->to2;
187       dist = mptr->weight;
188       knnweight = exp(-dist);
189       knntot += knnweight;
190       knnsum += nptr->weight*knnweight;
191 /* a radial basis type weighting of local data density */
192 /* effectively a Parzen window estimation */
193    } 
194    return(knnsum/knntot);
195 }
196 
197 Imrect  *imf_knn_density(int neighbours, Imregion *test_roi)
198 {
199   Imrect   *im = NULL;
200   Imregion  roi;
201   float    *data;
202   float    *row1;
203   int       i, j, k;
204   float    *row;
205   List     *density_list = NULL;
206 
207 
208   coreg_slice_init((Vec3 *)NULL);
209   imptrs = coreg_limits(&imptrlz, &imptruz, &imptrly, &imptruy, &imptrlx,
210                         &imptrux);
211 
212   data = (float *)fvector_alloc(imptrlz, imptruz);
213   monitor = hbook1(0,"nearest distances\n",0.0,50.0,50);
214  
215   roi_fill(&roi, imptrlx, imptrly, imptrux, imptruy);
216   im = im_alloc(roi.uy-roi.ly, roi.ux-roi.lx, &roi, float_v);
217   row1 = fvector_alloc(roi.lx, roi.ux);
218   if (test_roi->lx < imptrlx) test_roi->lx = imptrlx;
219   if (test_roi->ux > imptrux) test_roi->ux = imptrux;
220   if (test_roi->ly < imptrly) test_roi->ly = imptrly;
221   if (test_roi->uy > imptruy) test_roi->uy = imptruy;
222 
223   for (i = test_roi->ly; i < test_roi->uy; i++)
224     {
225       for (j = test_roi->lx; j < test_roi->ux; j++)
226       {
227          for (k = imptrlz; k < imptruz; k++)
228          {
229             row = (float*)imptrs[k][i];
230             data[k] = row[j];
231          }
232          density_list = knn_build(density_list,data, NULL, distance_func, 
233                                   KNNTHRES, imptruz-imptrlz);
234        }
235     }
236 
237   for (i = test_roi->ly; i < test_roi->uy; i++)
238     {
239       for (j = test_roi->lx; j < test_roi->ux; j++)
240       {
241          for (k = imptrlz; k < imptruz; k++)
242          {
243             row = imptrs[k][i];
244             data[k] = row[j];
245          }
246          knn_fill(density_list,data, distance_func); 
247       }
248     }
249 
250   for (i = imptrly; i < imptruy; i++)
251     {
252       for (j = imptrlx; j < imptrux; j++)
253       {
254 
255          for (k = imptrlz; k < imptruz; k++)
256          {
257             row = imptrs[k][i];
258             data[k] = row[j];
259          }
260          row1[j] = knn_density(density_list,data, distance_func);
261       }
262       im_put_rowf(row1, im, i, roi.lx, roi.ux);
263     }
264 
265 
266   fvector_free(row1, roi.lx);
267   fvector_free(data, imptrlz);
268   format("total number of nodes %d\n",total_knn);
269   hprint(stdout,monitor);
270   density_list = knn_destroy(density_list);
271   return (im);
272 }
273 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~ [ freetext search ] ~ [ file search ] ~

This page was automatically generated by the LXR engine.
Visit the LXR main site for more information.