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

Linux Cross Reference
Tina5/tina-libs/tina/vision/visMatch_dynamic.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 Lesser 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 Lesser General Public License for more details.
 14  *
 15  * You should have received a copy of the GNU Lesser 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  **********
 20  *
 21  * Program :    TINA
 22  * File    :  $Source: /home/tina/cvs/tina-libs/tina/vision/visMatch_dynamic.c,v $
 23  * Date    :  $Date: 2003/10/06 12:29:47 $
 24  * Version :  $Revision: 1.3 $
 25  * CVS Id  :  $Id: visMatch_dynamic.c,v 1.3 2003/10/06 12:29:47 neil Exp $
 26  *
 27  * Author  : Legacy TINA
 28  *
 29  * Notes :
 30  * 
 31  * general routines for perfoming dynamic programming
 32  * 
 33  * the sum of weights of the matches is maximised.
 34  * 
 35  * the solution allows primitives to be skipped
 36  * 
 37  * on route to maximal solutions (missed matches score 0) 
 38  *
 39  *********
 40 */
 41 
 42 #include "visMatch_dynamic.h"
 43 
 44 #if HAVE_CONFIG_H
 45   #include <config.h>
 46 #endif
 47 
 48 
 49 #include <math.h>
 50 #include <tina/sys/sysDef.h>
 51 #include <tina/sys/sysPro.h>
 52 #include <tina/math/mathDef.h>
 53 #include <tina/geometry/geomDef.h>
 54 #include <tina/geometry/geomPro.h>
 55 
 56 #define INCLUDED(c,r) (c>=first && c<=last && r>=low[c] && r<=up[c])
 57 
 58 /* construct a list of match data (referenced in the DP array) starts
 59  * from the solution and walks back through the optimal path on the
 60  * basis of the type fields of the DP nodes */
 61 static List *back_track(int i, int j, Dpnode ** dp_array, int *low, int *up, int first, int last)
 62 {
 63     List   *list = NULL;
 64 
 65     while (INCLUDED(i, j))
 66     {
 67         Dpnode *dp = &dp_array[i][j];
 68 
 69         switch (dp->m_type)
 70         {
 71         case DP_MATCHED:
 72             if (dp->data != NULL)
 73                 list = ref_addtostart(list, (void *) dp->data, MATCH);
 74             i--;
 75             j--;
 76             break;
 77         case DP_PVTROW:
 78             i--;
 79             break;
 80         case DP_PVTCOL:
 81             j--;
 82             break;
 83         }
 84     }
 85     return (list);
 86 }
 87 
 88 /* find solution to DP that has been found by dp_accum
 89  * 
 90  * examine the last active row of the DP array for the highest value
 91  * solution and track it throgh the solution path collecting valid
 92  * matches along the way */
 93 List   *dp_solution(Dpnode ** dp_array, int *low, int *up, int first, int last)
 94 {
 95     int     i, j;
 96     float   max_sup;
 97     int     maxj;
 98 
 99     i = last;
100     maxj = low[i];
101     max_sup = dp_array[i][low[i]].m_tot;
102     for (j = maxj + 1; j <= up[i]; ++j)
103     {
104         float   sup = dp_array[i][j].m_tot;
105 
106         if (sup > max_sup)
107         {
108             max_sup = sup;
109             maxj = j;
110         }
111     }
112 
113     /* now we can back track from the solution */
114     return (back_track(i, maxj, dp_array, low, up, first, last));
115 }
116 
117 /* accumulate the DP array
118  * 
119  * 3 preceeding values are compared to update each node the type field is
120  * set depening upon which is maximal */
121 void    dp_accum(Dpnode ** dp_array, int *low, int *up, int first, int last)
122 {
123     int     i, j;
124 
125     for (i = first; i <= last; ++i)
126     {
127         for (j = low[i]; j <= up[i]; ++j)
128         {
129             Dpnode *dp_new = &dp_array[i][j];
130             float   m_tot, r_prev = (float) 0.0, c_prev = (float) 0.0;
131 
132             /* compute best cost to this node */
133 
134             m_tot = dp_new->cost;
135             if (INCLUDED(i - 1, j - 1))
136                 m_tot += dp_array[i - 1][j - 1].m_tot;
137             if (INCLUDED(i - 1, j))
138                 r_prev = dp_array[i - 1][j].m_tot;
139             if (INCLUDED(i, j - 1))
140                 c_prev = dp_array[i][j - 1].m_tot;
141 
142             if (m_tot > r_prev && m_tot > c_prev)
143             {
144                 dp_new->m_tot = m_tot;
145                 dp_new->m_type = DP_MATCHED;
146             } else if (c_prev > r_prev) /* prevented along the column */
147             {
148                 dp_new->m_tot = c_prev;
149                 dp_new->m_type = DP_PVTCOL;
150             } else
151             {
152                 /* prevented row best */
153                 dp_new->m_tot = r_prev;
154                 dp_new->m_type = DP_PVTROW;
155             }
156         }
157     }
158 }
159 

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