Landmark Warp Tools Library User Guide

Warp File Format

This is a file format that is compatible with all landmark-based warps that are IParameterizable that are recognized by the LandmarkWarpFactory class.

All data is written as ascii text. The format allows comments on any line and after data, as long as they are preceded by a '#' character (text after that symbol is not parsed). A valid file can have any number of comments. All arrays of numbers are space-delimited with a newline every 80 characters.

Format

The first line of data contains a magic string, "LandmarkWarpFramework", followed by the version of the framework. Next, there is a line indicating the number of parameter blocks that have been encoded. Each parameter block first encodes a header which is a single line containing a name, version and the number of parameters in the block. Next the parameter block encodes the parameters, adding a new line every 80 characeters. For most warps, only one parameter block is needed, but for spline warps, two are needed, one to specify the basis and one to specify the coefficients of the basis.

The meaning of the parameters is very specific to the type of warp. For details about the meaning of the parameters, the javadocs should be referenced.

The filenames have the form "*.lmw".

Example Warp File

Here is an example warp file:

# LandmarkWarpFile 2007-04-03
LandmarkWarpFramework 1.0 
ParameterBlock 2
SplineWarp 1.0 28
2.0 5.0 5.0 5.0 -5.0 -5.0 0.0 5.0 -5.0 -5.0 5.0 0.0 0.0060112295 -0.0 
0.0060112295 -0.0 0.0060112295 -0.0 0.0060112295 -0.0 -0.024044918 0.0 -8.0349545E-17 -0.0 
-1.3226087E-16 -0.0 7.2032137 -0.0 
ThinPlateBasis 1.0 1
2.0 

Landmark File Format

This is a file format that is compatible that encodes K (approximately) unique N-dimensional landmarks to a file.

All data is written as ascii text. The format allows comments on any line and after data, as long as they are preceded by a '#' character (text after that symbol is not parsed). The format also allows arbitrary white space and empty lines

The format is intended to be human readable and compatible with other applications.

Format

Each point is line delimited, where the order of the points in the file reflects the point indices in the LandmarkSet. The coordinates are space delimited.

The filenames have the form "*.lm".

Example Landmark File

Here is an example landmark file:

56.0 49.0
203.0 33.0
243.0 69.0
234.0 93.0
147.0 122.0
123.0 96.0
128.0 77.0
85.0 64.0
86.0 55.0

which is equivalent to

56.0 49.0 
203.0 33.0 # first comment
243.0 69.0

234.0 93.0
# second comment
147.0 122.0
  123.0 96.0
128.0  77.0
85.0 64.0
86.0 55.0

Example Use

Here is a way to make a simple 2-D spline warp which deforms the center of a square to the right:

import java.awt.image.BufferedImage;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Random;

import edu.ucla.loni.ccb.discretedata.io.ArrayIO;
import edu.ucla.loni.ccb.functions.app.FunctionAppUtil;
import edu.ucla.loni.ccb.functions.basis.BasisElasticBodyHyper;
import edu.ucla.loni.ccb.functions.basis.BasisFunctionType;
import edu.ucla.loni.ccb.functions.estimation.FunctionEstimatorFactory;
import edu.ucla.loni.ccb.functions.estimation.LandmarkOperations;
import edu.ucla.loni.ccb.functions.estimation.LandmarkSet;
import edu.ucla.loni.ccb.functions.estimation.LandmarkSetPair;
import edu.ucla.loni.ccb.functions.estimation.SplineBasisEstimator;
import edu.ucla.loni.ccb.functions.io.FunctionIO;
import edu.ucla.loni.ccb.shape.Shape;
import edu.ucla.loni.ccb.shape.ShapeImpl;
import edu.ucla.loni.ccb.shape.geometry.CGALFaceSet;
import edu.ucla.loni.ccb.shape.geometry.IPoint;
import edu.ucla.loni.ccb.shape.geometry.IPointSet;
import edu.ucla.loni.ccb.shape.geometry.IrregularPointSet;
import edu.ucla.loni.ccb.shape.geometry.Point3D;
import edu.ucla.loni.ccb.shape.geometry.PointND;
import edu.ucla.loni.ccb.shape.math.VectorMath;
import edu.ucla.loni.ccb.shape.math.functions.IFunction;
import edu.ucla.loni.ccb.shape.math.functions.MapLoop;
import edu.ucla.loni.ccb.shapeio.duff.DuffIO;

public class Simple2DLandmarkWarpExample
  {
    /**
     * This demonstrates how to apply a warp to a single two dimensional point.
     * 
     * The program creates a simple warp, applies it to
     * a new point and writes the warp to disk.
     */
    public static void main(String [] args)
      {
        try {

          // Define example landmarks
          int dim = 2;
          int num = 5;
          float distance = 5;

          float[][] refData = new float[dim][num];
          float[][] targetData = new float[dim][num];

          float[] novelPoint = { .2f, 1.4f };
          float[] warpedNovelPoint = new float[dim];

          refData[0] = new float[] { distance, distance, -distance, -distance,
              0 };
          refData[1] = new float[] { distance, -distance, -distance, distance,
              0 };

          targetData[0] = new float[] { distance, distance, -distance,
              -distance, distance / 2 };
          targetData[1] = new float[] { distance, -distance, -distance,
              distance, 0 };

          // Create the landmark objects
          LandmarkSet refSet = LandmarkOperations
              .constructFromDimNumArray(refData);
          LandmarkSet targetSet = LandmarkOperations
              .constructFromDimNumArray(targetData);
          LandmarkSetPair landmarks = new LandmarkSetPair(refSet, targetSet);

          // Compute the warp

          IFunction warp = FunctionEstimatorFactory.createNonLinear(
              BasisFunctionType.THIN_PLATE, dim).estimate(landmarks);

          // Evaluate the warp (these are not used for anything here)
          warp.evaluate(novelPoint, warpedNovelPoint);
          System.out.println("Original warped novel point = ["
              + warpedNovelPoint[0] + "," + warpedNovelPoint[1] + "].");

          // Write out the warp file
          String filename = "output/warp" + FunctionIO.SUFFIX;
          FileOutputStream stream = new FileOutputStream(new File(filename));
          FunctionIO.write(stream, warp);

          // Read warp file
          BufferedReader reader = new BufferedReader(new FileReader(new File(
              filename)));
          IFunction readWarp = FunctionIO.read(reader);

          // Demonstrate that the read warp produces the same output at the
          // novel point
          readWarp.evaluate(novelPoint, warpedNovelPoint);
          System.out.println("Read and recomputed warped novel point = ["
              + warpedNovelPoint[0] + "," + warpedNovelPoint[1] + "].");

        } catch (Exception e) {
          System.err.println("Warp write failed.");
          e.printStackTrace();
        }
      }
  }

The above code creates two two-dimensional arrays, a set of source landmarks and a set of destination landmarks. The first four points are the same-- they are the corners of a square. The last point is different by distance/2 in the x-coordinate. Then the warp is created from these points. The warp is applied to a new point. This warp should keep points near the corners stationary and move points near the center to the right. Finally the warp is written to disk for later use.

Here is the resulting warp file:

# LandmarkWarpFile 2007-04-03
LandmarkWarpFramework 1.0 
ParameterBlock 2
SplineWarp 1.0 28
2.0 5.0 5.0 5.0 -5.0 -5.0 0.0 5.0 -5.0 -5.0 5.0 0.0 0.0060112295 -0.0 
0.0060112295 -0.0 0.0060112295 -0.0 0.0060112295 -0.0 -0.024044918 0.0 -8.0349545E-17 -0.0 
-1.3226087E-16 -0.0 7.2032137 -0.0 
ThinPlateBasis 1.0 1
2.0 

There is an example package in the library which provides landmarks for testing as well as main routines for applying the warps to existing shapes.

To allow IO operations, an object must have a parameterization object that implements IParameterization. This parameterization object allows the user to create a ParameterBlock that encodes the instance of the object. The class FunctionIO can be used to write a warp to disk automatically. The file will encode all the parameters necessary to recreate the warp object. This file is ASCII and human readable, although in general it is difficult to interpret the parameters.

Landmark Warp Framework Programmer's Guide Version 1.0

There is also a file format for landmarks. This allows LandmarkSet objects to be read and written to disk. The format is ASCII and human readable and writable. Each point has space-delimited coordinates, and points are line-delimited. The order of the points in the stream implies the indices in the LandmarkSet. Comments are allowed after a '#' character, and arbitrary white-space and empty lines are allowed.

Implementation

Mathematical Background

In a Procrustes warp, the two spaces are related by a rotation and a translation. In a Generalized Procrustes warp, scaling is allowed in addition to the rotation and translation.

The non-linear problem is more open-ended. In the non-linear warp, landmarks in the input space are mapped exactly to landmarks in the output space. The behavior at non-landmark points depends on the basis functions used to define the mapping. The framework allows for the user to implement new basis functions.

For the non-linear case, consider two spaces A and B, and let there be two sets of points p.i from A and q.i from B for i = [0,K]. For our purposes, A and B will both be RN. We would like to find a function f:A->B such that f(p.i) = q.i for all i. This is the mapping we call the warp. Let G be a function G:RN->RNxN which maps a point to a NxN matrix-- this is the basis function. Let d be a function d:RNxRN->RN that is the displacement function d(a,b) = b-a-- we let f(a) = a + d(a,b). We can define d as a linear combination of basis functions and a linear transformation:

Landmark Warp Framework User's Guide Version 1.0

Overview

This is a framework for using non-linear landmark based warps. This provides tools for computing, applying and implementing warp. The general problem is to find a mapping RN->RN that maps a set of points p.i from the domain to points q.i in the codomain for all i=[1,k]-- these are the landmarks. The behavior at non-landmark points depends on the basis functions used to define the mapping. Given a type of basis function and the landmarks, the framework can compute the coefficients that define the warp. Given the coefficients that define the warp, the framework can apply the mapping. Furthermore, the framework allows for the user to implement new basis functions.

Mathematical Background

This section will address the mathematics used to compute the warps.

For two spaces A and B, let there be two sets of points p.i from A and q.i from B for i = [0,K]. For our purposes, A and B will both be RN. We would like to find a function f:A->B such that f(p.i) = q.i for all i. This is the mapping we call the warp. Consider also a function G:RN->RNxN which maps a point to a NxN matrix. This is the mapping we call the basis function. Consider another function d:RNxRN->RN that is the d(a,b) = b-a. This is the displacement-- notice that f(a) = a + d(a,b). We can define d as a linear combination of basis functions and a linear transformation:

d(p) = sum( G(p-p.i) * c.i ) + A * p + b

where the sum is from i = 0 to i = K. P is from RN and is the point to be mapped. p.i from RN is the i-th landmark in the domain. c.i is from RN and is the i-th non-linear coefficient. A is from RNxN and contains the affine coefficients. b is from RN and contains the linear shift coefficients.

The coefficients are computed by solving a system of K*N+N*(N+1) linear equations that imply that satisfy the conditions on f and computing the output of the basis function at K*K points.

For the solution to exist, the domain landmarks must span RN and be distinct. For example, you cannot use points that lie on a plane to define a 3D warp, and you cannot make a warp that has two domain landmarks at the origin.

Implementation

To use this, we need to represent sets of points (landmarks) in some way. One way is to store sets of points as a two dimensional array. This framework is integrated with the ShapeTools library, so you can also use PointSets to encode the landmarks. All points are stored as floats; however, the computation of the coefficients is done with doubles.

The basic interface is IWarp. This has two methods apply(float[]) and getDimension(). The abstract class PointSetWarp implements this interface and provides the methods for applying the warp to more complicated structures, but does not compute the warp. The class LandmarkWarp actually computes the coefficients and applies the warp to novel points.

Landmark warp can be instantiated by either specifying the coefficients, basis function and domain landmarks explicitly or by providing the basis function, domain and codomain landmarks and computing the coefficients. When only landmarks are provided, the class creates a system of linear equations that are solved using LU decomposition.

Basis functions are classes that implement the interface IBasisFunction. All basis functions must implement three methods: getDimension(), apply(float[]), and getName(). The user can implement a new basis function using this interface. Currently, there are two general types of basis functions, thin plate splines and elastic body splines. The first is derived from a model of how metal sheets deform, and the other is derived from the way in which elastic materials deform. There are variations among these basis functions depending on the dimension of the warp and parameters of the model used to derive them.

The warps can be encoded and decoded to disk using the class LandmarkWarpIO. This writes the warp coefficients in an ASCII file for later use.