ini/trakem2/vector/EditionsND.java

   1 /**
   2
   3 TrakEM2 plugin for ImageJ(C).
   4 Copyright (C) 2007-2009 Albert Cardona.
   5
   6 This program is free software; you can redistribute it and/or
   7 modify it under the terms of the GNU General Public License
   8 as published by the Free Software Foundation (http://www.gnu.org/licenses/gpl.txt )
   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 You may contact Albert Cardona at acardona at ini.phys.ethz.ch
  20 Institute of Neuroinformatics, University of Zurich / ETH, Switzerland.
  21 **/
  22
  23 package ini.trakem2.vector;
  24
  25 import ini.trakem2.utils.Utils;
  26 import ini.trakem2.utils.IJError;
  27 import ini.trakem2.persistence.Loader;
  28
  29 import mpi.fruitfly.math.datastructures.FloatArrayND;
  30
  31 import java.util.*;
  32 import javax.vecmath.Point3f;
  33
  34
  35 /** To extract the sequence of editions that convert any number of open N-dimensional vector strings to an ideal common N-dimensional open vector string. */
  36 public class EditionsND {
  37
  38         protected VectorString3D[] vs;
  39         protected double delta;
  40
  41         protected int[][] editions;
  42         protected double distance;
  43
  44         protected Loader loader;
  45
  46         public EditionsND(final Loader loader, final VectorString3D[] vs, final double delta) throws Exception {
  47                 int ndim = vs[0].getDimensions();
  48                 for (int i=1; i<vs.length; i++) {
  49                         if (vs[i].getDimensions() != ndim) throw new Exception("All VectorString must have the same number of dimensions.");
  50                 }
  51                 this.vs = vs;
  52                 this.delta = delta;
  53                 this.loader = loader;
  54                 init();
  55         }
  56
  57         final private void init() {
  58                 // equalize point interdistance
  59                 for (int i=0; i<vs.length; i++) {
  60                         vs[i].resample(delta);
  61                 }
  62
  63                 FloatArrayND fa = makeMatrix();
  64                 // matrix is of length vs.length times the length of each vector.
  65         }
  66
  67         private FloatArrayND makeMatrix() { // equivalent to the misnamed Editions.findEditMatrix
  68                 // create a 1-dimensional array to hold the n-dimensional matrix
  69                 final int n_dims = vs.length;
  70                 final int[] len = new int[n_dims];
  71                 long size = vs[0].length();
  72                 for (int i=0; i<n_dims; i++) {
  73                         len[i] = vs[i].length();
  74                         if (i > 0) size *= len[i];
  75                 }
  76                 loader.releaseToFit((long)(size * 1.1));
  77                 final FloatArrayND fa = new FloatArrayND(len);
  78                 final float felta = (float)delta;
  79                 final int[] i = new int[n_dims]; // the positions on each dimension, iu.e. (3,2,6,...4)
  80                 int j = 0;
  81                 final int[] i1 = new int[n_dims];
  82                 for (;;) {
  83                         for (j=0; j<n_dims; j++) {
  84                                 if (++i[j] >= len[j]) i[j] = 0;
  85                                 else break;
  86                                 // here: the i[] contains all the positions, one for each
  87                                 //
  88                                 // The "equivalent" of the difference of 2 vectors, but for N vectors.
  89                                 float val = felta - (float)VectorString3D.getAverageVectorLength(i, vs);
  90
  91                                 // min cost deletions and insertions, in all possible combinations
  92                                 final float fun1 = getMinCost(fa, i);
  93                                 // cost mutation:
  94                                 for (int k=0; k<n_dims; k++) {
  95                                         if (i[k] -1 > 0) i1[k] = i[k] -1;
  96                                 }
  97                                 final float fun3 = fa.get(i1) + val;
  98
  99                                 fa.set(Math.min(fun1, fun3), i);
 100
 101                         }
 102                         if (j == n_dims) break;
 103                 }
 104                 return fa;
 105         }
 106
 107         private final float getMinCost(final FloatArrayND fa, final int[] i) {
 108                 float min = Float.MAX_VALUE;
 109                 // TODO explore, for i positions, all combinations of i and i-1
 110                 return min;
 111         }
 112
 113 }