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

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

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