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

Linux Cross Reference
Tina6/tina-libs/tina/vision/visMatch_mdp.c

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

  1 /**********
  2  *
  3  * This file is part of the TINA Open Source Image Analysis Environment
  4  * henceforth known as TINA
  5  *
  6  * TINA is free software; you can redistribute it and/or modify
  7  * it under the terms of the GNU General Public License as
  8  * published by the Free Software Foundation.
  9  *
 10  * TINA 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 TINA; if not, write to the Free Software Foundation, Inc.,
 17  * 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 18  *
 19  * ANY users of TINA who require exemption from the existing licence must
 20  * negotiate a new licence with Dr. Neil.A.Thacker, the sole agent for
 21  * the University of Manchester.
 22  *
 23  **********
 24  *
 25  * Program :    TINA
 26  * File    :  $Source: /home/tina/cvs/tina-libs/tina/vision/visMatch_mdp.c,v $
 27  * Date    :  $Date: 2008/12/09 00:15:22 $
 28  * Version :  $Revision: 1.4 $
 29  * CVS Id  :  $Id: visMatch_mdp.c,v 1.4 2008/12/09 00:15:22 paul Exp $
 30  *
 31  * Author  : Legacy TINA
 32  *
 33  * Notes :
 34  * 
 35  * general routines for perfoming dynamic programming over a list of
 36  * matches
 37  * 
 38  * match indices are held in the DP_INDEX property of the match
 39  * 
 40  * the indices (ints) indicate the monoticity of the underlying problem 
 41  *
 42  *********
 43 */
 44 
 45 #include "visMatch_mdp.h"
 46 
 47 #if HAVE_CONFIG_H
 48   #include <config.h>
 49 #endif
 50 
 51 #include <string.h>
 52 #include <math.h>
 53 #include <tina/sys/sysDef.h>
 54 #include <tina/sys/sysPro.h>
 55 #include <tina/vision/vis_MatchDef.h>
 56 #include <tina/vision/vis_MatchPro.h>
 57 
 58 /* static variables to maitain DP array
 59  * 
 60  * prevents repeted allocation and freeing of these data structures
 61  * 
 62  * a large array is allocated prior to dynamic programming over match
 63  * lists. */
 64 
 65 static int dp_size;
 66 static Dpnode **dp_array;       /* the DP array */
 67 static int *low, *up;           /* lower and upper indices into DP
 68                                  * array */
 69 
 70 void    dp_mlist_build(int s)
 71 {
 72     if (s <= dp_size)
 73         return;
 74     narray_free((char **) dp_array, 0, dp_size, 0, dp_size, sizeof(Dpnode));
 75     rfree((void *) low);
 76     rfree((void *) up);
 77     dp_size = s;
 78     dp_array = ts_narray_alloc(0, 0, dp_size, dp_size, Dpnode);
 79     low = (int *) ralloc((unsigned) (sizeof(int *) * dp_size));
 80     up = (int *) ralloc((unsigned) (sizeof(int *) * dp_size));
 81 }
 82 
 83 /* adjust low and up values between first and last to represent a
 84  * minimally valid and fully connected DP array. */
 85 void    form_valid_dp_array(int *low, int *up, int firsti, int lasti, int minj)
 86 {
 87     int     i, m;
 88 
 89     /* make DP array a strict envelope */
 90 
 91     for (i = firsti; i <= lasti; ++i)
 92         if (low[i] > minj)
 93             --low[i];
 94 
 95     for (i = firsti; i < lasti; ++i)
 96     {
 97         if (up[i + 1] > up[i])
 98             up[i] = up[i + 1] - 1;
 99     }
100 
101     m = up[firsti];
102     for (i = firsti + 1; i <= lasti; ++i)
103     {
104         if (up[i] > m)
105             m = up[i];
106         else
107             up[i] = m;
108     }
109 
110     m = low[lasti];
111     for (i = lasti - 1; i >= firsti; --i)
112     {
113         if (low[i] != -1 && low[i] < m)
114             m = low[i];
115         else
116             low[i] = m;
117     }
118 
119     /* ensure fully connected envelope */
120     for (i = firsti; i < lasti; ++i)
121     {
122         if (up[i] < low[i])
123             up[i] = low[i];
124         if (up[i] < low[i + 1])
125             up[i] = low[i + 1];
126     }
127 }
128 
129 void    mlist_set_dp_indices(List * mlist, int (*index_func) ( /* ??? */ ), void *data)
130 {
131     List   *lptr;
132 
133     for (lptr = mlist; lptr != NULL; lptr = lptr->next)
134     {
135         /*int to1, to2;*/
136         long int to1, to2; /*JD, 2015.01.27*/
137         Match  *m = (Match *) lptr->to;
138         Pair   *p;
139 
140         to1 = index_func(m->to1, m->type, data);
141         to2 = index_func(m->to2, m->type, data);
142         /*p = pair_make(to1, 0, to2, 0);*/       
143         p = pair_make((void *) to1, 0, (void *) to2, 0); /*JD, 2015.01.27*/
144         m->props = proplist_addifnp(m->props, (void *) p, DP_INDEX, rfree, true);
145     }
146 }
147 
148 List   *dp_mlist(List * list, double (*cost_func) ( /* ??? */ ))
149 /* list of list of matches in assending order */
150 
151 {
152     List   *ptr;
153     Match  *match;
154     Pair   *indices;
155     int     firsti, lasti, maxj, minj;
156     int     i, j, n;
157 
158     if (list == NULL)
159         return (NULL);
160 
161     for (n = 0, ptr = list; ptr != NULL; ptr = ptr->next)
162     {
163         match = (Match *) ptr->to;
164         indices = (Pair *) prop_get(match->props, DP_INDEX);
165         if (indices == NULL)
166             return (NULL);
167         /*i = (int) indices->to1;*/
168         i = (long int) indices->to1; /*JD, 2015.01.27*/
169 
170         if (i > n)
171             n = i;
172     }
173     n++;
174 
175     if (n > dp_size)
176     {
177         error("dp_mlist: dynamic programming table limit exeeded", warning);
178         return (NULL);
179     }
180     for (i = 0; i < n; ++i)
181         low[i] = up[i] = -1;
182 
183     maxj = 0;
184     minj = dp_size - 1;
185     for (ptr = list; ptr != NULL; ptr = ptr->next)
186     {
187         match = (Match *) ptr->to;
188         indices = (Pair *) prop_get(match->props, DP_INDEX);
189         /*i = (int) indices->to1;*/
190         i = (long int) indices->to1; /*JD, 2015.01.27*/
191         /*j = (int) indices->to2;*/
192         j = (long int) indices->to2; /*JD, 2015.01.27*/
193 
194         if (low[i] == -1 || j < low[i])
195             low[i] = j;
196         if (up[i] == -1 || j > up[i])
197             up[i] = j;
198         if (j > maxj)
199             maxj = j;
200         if (j < minj)
201             minj = j;
202     }
203 
204     if (maxj > dp_size)
205     {
206         error("dp_mlist: dynamic programming table limit exeeded", warning);
207         return (NULL);
208     }
209     /* find range of used values */
210     for (i = 0; i < n; ++i)
211         if (low[i] != -1)
212             break;
213     firsti = i;
214     lasti = n - 1;
215 
216     if (firsti > lasti)
217         return (NULL);
218 
219     form_valid_dp_array(low, up, firsti, lasti, minj);
220 
221     /* initialise DP array elements */
222 
223     for (i = firsti; i <= lasti; ++i)
224         (void) memset((char *) &dp_array[i][low[i]], 0, (up[i] - low[i] + 1) * sizeof(Dpnode));
225 
226     /* fill in values from match list */
227 
228     for (ptr = list; ptr != NULL; ptr = ptr->next)
229     {
230         match = (Match *) ptr->to;
231         indices = (Pair *) prop_get(match->props, DP_INDEX);
232         /*i = (int) indices->to1;*/
233         i = (long int) indices->to1; /*JD, 2015.01.27*/
234         /*j = (int) indices->to2;*/
235         j = (long int) indices->to2; /*JD, 2015.01.27*/
236 
237         dp_array[i][j].data = (void *) match;
238         if (cost_func == NULL)
239             dp_array[i][j].cost = match->weight;
240         else
241             dp_array[i][j].cost = (float)cost_func(match);
242     }
243 
244     dp_accum(dp_array, low, up, firsti, lasti);
245     list = dp_solution(dp_array, low, up, firsti, lasti);
246 
247     return (list);
248 }
249 

~ [ 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.