Selected Developed Software
The research software provided on this web site ("software") is provided by
NIST as a public service. You may use, copy and distribute copies of the
software in any medium, provided that you keep intact this entire notice.
You may improve, modify and create derivative works of the software or any
portion of the software, and you may copy and distribute such modifications
or works. Modified works should carry a notice stating that you changed the
software and should note the date and nature of any such change. Please
explicitly acknowledge the National Institute of Standards and Technology
as the source of the software.
The software is expressly provided "AS IS." NIST MAKES NO WARRANTY OF ANY
KIND, EXPRESS, IMPLIED, IN FACT OR ARISING BY OPERATION OF LAW, INCLUDING,
WITHOUT LIMITATION, THE IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR
A PARTICULAR PURPOSE, NON-INFRINGEMENT AND DATA ACCURACY. NIST NEITHER
REPRESENTS NOR WARRANTS THAT THE OPERATION OF THE SOFTWARE WILL BE
UNINTERRUPTED OR ERROR-FREE, OR THAT ANY DEFECTS WILL BE CORRECTED. NIST
DOES NOT WARRANT OR MAKE ANY REPRESENTATIONS REGARDING THE USE OF THE
SOFTWARE OR THE RESULTS THEREOF, INCLUDING BUT NOT LIMITED TO THE
CORRECTNESS, ACCURACY, RELIABILITY, OR USEFULNESS OF THE SOFTWARE.
You are solely responsible for determining the appropriateness of using and
distributing the software and you assume all risks associated with its use,
including but not limited to the risks and costs of program errors,
compliance with applicable laws, damage to or loss of data, programs or
equipment, and the unavailability or interruption of operation. This software
is not intended to be used in any situation where a failure could cause risk
of injury or damage to property. The software was developed by NIST employees.
NIST employee contributions are not subject to copyright protection within
the United States.
Software for computing a partial elastic shape registration of two simple
surfaces in 3-dimensional space and the elastic shape distance between them
corresponding to the partial registration:
ESD_surf_3d.zip, zip file with Fortran and Matlab programs, Matlab
mex file of Fortran program, compiled mex file, and sample data files, etc.
for computing a partial elastic shape registration of two simple
surfaces in 3-dimensional space and the elastic shape distance between them
corresponding to the partial registration.
[zip file].
Software for computing the elastic registration of two simple curves in
d-dimensional space and the elastic shape distance between them:
ESD_alldim.zip, zip file with Fortran and Matlab programs, Matlab
mex file of Fortran program, compiled mex file, and sample data files, etc.
for computing the elastic registration of two simple curves in d-dimensional
space and the elastic shape distance between them.
[zip file].
Software for computing matrices of maximal trace over rotation matrices:
Maximal_Trace.zip, zip file with Fortran and Matlab programs, Matlab
mex file of Fortran program, compiled mex file, and sample data file of 3x3
matrices. Programs are for computing matrices of maximal trace over rotation
matrices from input matrices. Note the option exists in the Fortran code to do
everything using our version of the SVD (singular value decomposition) method
only. Otherwise it does it with a procedure based on the Cayley transform and
Newton's method that for each input matrix M computes a rotation matrix U such
that UM is symmetric. If the procedure is successful (Newton's method didn't fail)
a rotation matrix R (without the SVD) is computed such that RUM is of maximal
trace over rotation matrices. If Newton’s method fails, then using our version
of the SVD method, the program computes a rotation matrix R such that RM is of
maximal trace over rotation matrices. We also note that in the Fortran code
integer variable ITEX is set to the maximum number of allowed iterations per
input matrix of Newton’s method. Note as well that instead of using the Fortran
program, the Matlab program can be used for the same purposes. The option also
exists in the Matlab code to do everything using the Matlab version of the SVD
method only. Otherwise the Matlab mex file of the Fortran program is used by
the Matlab code. This has the effect of executing the Fortran code as described
above from the Matlab code.
[zip file].
Fast Dynamic Programming Sofware for pairwise elastic registration of curves:
Fast_Dynamic_Programming.zip, zip file with copies of
implementation of Algorithm adapt-DP as Fortran files (a Matlab Fortran mex
file and a Python compatible Fortran file) for execution with Matlab/Python,
Matlab/Python test file for executing adapt-DP Matlab Fortran mex file and
Python compatible Fortran file, respectively, example data files, usage
intructions in README files, etc. Algorithm adapt-DP
is based on DP (dynamic programming) restricted to an adapting strip for
computing in linear time optimal diffeomorphisms for elastic registration
of curves. Description of Algorithm adapt-DP can be found in
"Fast Dynamic Programming for Elastic Registration of Curves", Proceedings
of the 2nd International Workshop on Differential Geometry in
Computer Vision and Machine Learning (DIFF-CVML'16) in conjunction with
Computer Vision Pattern Recognition Conference (CVPR) 2016, Las Vegas,
Nevada, June 26-July 1, 2016.
[zip file].
Karcher mean computation Sofware for elastic registration of curves using
Fast Dynamic Programming:
Karcher_mean_computation.zip, zip file with copies of
implementation of Algorithm adapt-DP as a Matlab Fortran mex file for
execution with Matlab, Matlab file for executing adapt-DP Matlab Fortran
mex file repeatedly for computing Karcher mean of set of functions, example
data files for the functions, usage intructions in README file, etc.
Algorithm adapt-DP is based on DP (dynamic programming) restricted to an
adapting strip for computing in linear time optimal diffeomorphisms for
elastic registration of curves. Description of Algorithm adapt-DP can be
found in "Fast Dynamic Programming for Elastic Registration of Curves",
Proceedings of the 2nd International Workshop on Differential Geometry in
Computer Vision and Machine Learning (DIFF-CVML'16) in conjunction with
Computer Vision Pattern Recognition Conference (CVPR) 2016, Las Vegas,
Nevada, June 26-July 1, 2016. Program for computing Karcher mean is based
on a program obtained from website of the Florida State University
Statistical Shape Analysis and Modeling Group. See README file for simple
and complex demonstrations of codes.
[zip file].
Exact Arithmetic Sofware:
exacta2.f, Fortran 77 program for presenting examples
of how exact arithmetic routines are used to carry out certain
geometrical computations in 2-d Euclidean space.
[Source code].
exacta3.f, Fortran 77 program for presenting examples
of how exact arithmetic routines are used to carry out certain
geometrical computations in 3-d Euclidean space.
In preparation.
[Source code].
2-D and 3-D Delaunay, Regular, Voronoi, Power constructs Sofware:
deltri.f, double precision Fortran 77 program for
reading/computing a 2-dimensional Delaunay triangulation for
a set of points, and for accomplishing any of the following tasks
as desired: inserting an additional set of points and/or a set
of line segments into current (Constrained) Delaunay triangulation
and obtaining a (Constrained) Delaunay triangulation that contains
the inserted points and/or line segments; deleting a set of points
that are vertices in the current (Constrained) Delaunay triangulation
and obtaining a (Constrained) Delaunay triangulation that does not
contain the deleted points; computing circumcenters of triangles
(Voronoi vertices) in final (Constrained) Delaunay triangulation.
In addition, if Voronoi vertices are computed and Delaunay triangulation
is unconstrained (no inserted line segments), the corresponding
Voronoi diagram is well defined, and then program can be used
for inserting edges of a rectangle into Voronoi diagram (a rectangle
that contains in its interior set of points for which Voronoi
diagram is defined) so that parts of Voronoi cells outside rectangle
(in particular unbounded cells) are clipped by these edges.
Input coordinates of points can have as many as 14 significant
figures with as many as 9 significant figures to either the left
or the right of the decimal point. Exact arithmetic is used when
necessary.
If a prompt file does not exist the program will create
a file that can be used as such in order to avoid user intervention
in subsequent executions of the program.
[Source code].
pltvor.f, double precision Fortran 77 program for
producing data files and script file for plotting Voronoi diagram
of a set of points with matlab. It is assumed that an unconstrained
Delaunay triangulation for the set has already been computed using
program deltri above. It is also assumed that the Voronoi vertices of
the Voronoi diagram of the set were also computed with deltri. From
the output files of program deltri the program here produces data
files and script file vorplot.m that when executed with matlab creates
from the data files a plot of the Voronoi diagram. If as described for
program deltri above, the Voronoi diagram has been clipped by the
edges of a rectangle, files for plotting the clipped Voronoi diagram
will be produced by this program. If a prompt file does not exist the
program will create a file that can be used as such in order to avoid
user intervention in subsequent executions of the program.
[Source code].
pltdel.f, double precision Fortran 77 program for
producing data file and script file for plotting a constrained or
unconstrained Delaunay triangulation of a set of points with matlab.
It is assumed that a Delaunay triangulation for the set has already
been computed using program deltri above. From the output files of
program deltri the program here produces data file and script file
delplot.m that when executed with matlab creates from the data file
a plot of the Delaunay triangulation. If as described for program
deltri above, during the execution of deltri an unconstrained Delaunay
was computed and the associated Voronoi diagram was clipped by the
edges of a rectangle, the files produced by this program will be for
plotting the Delaunay triangulation minus some triangles that are
eliminated because of the clipping. Accordingly, the plotted
triangulation may not be convex. If a prompt file does not exist the
program will create a file that can be used as such in order to avoid
user intervention in subsequent executions of the program.
[Source code].
arelen.f, double precision Fortran 77 program for computing
areas of Voronoi cells in the Voronoi diagram of a set of points in
2-dimensional space, lengths of faces of these cells, and the
distances obtained by computing for each face the distance between the
two points in the set that define the face (inter-neighbor distances).
It is assumed that an unconstrained Delaunay triangulation for the set
has already been computed using program deltri above. It is also assumed
that the Voronoi vertices of the Voronoi diagram of the set were also
computed with deltri.
[Source code].
dynvor.f, double precision Fortran 77 program for computing
Delaunay triangulations and Voronoi diagrams of dynamic data, i. e., of a
set of moving points in 2-d space. Currently program is set up to handle
999 or fewer input files making up dynamic data. Each input data set
contains the same number of distinct data points (no duplicates)
in the plane. Each time an input data set is read the current Delaunay
triangulation and Voronoi diagram are updated on a local basis, i. e.,
taking into account only those points that have moved. If the percentage
of points that have moved is too high then the whole Delaunay
triangulation and Voronoi diagram are computed. Exact arithmetic is
used when necessary.
[Source code].
pltdyn.f, double precision Fortran 77 program for producing
data files and script file for plotting with matlab in the form of a
movie Voronoi diagrams of dynamic data, i. e., of a set of moving
points in 2-d space. It is assumed that another existing program,
program dynvor, has been executed thus producing the Delaunay
triangulations and Voronoi diagrams of the dynamic data and the
corresponding output files. From the output files of program dynvor
the program here produces data files and script file dynplot.m that
when executed with matlab creates from the data files a movie of the
plots of the Voronoi diagrams of the dynamic data in the order in which
program dynvor reads the input data files that define the dynamic data.
Note that during the execution of dynplot.m with matlab the return key
should be pressed each time the execution pauses.
[Source code].
dynamic_input_data.zip, 100 sample input dynamic data sets
for programs dynvor.f and pltdyn.f for testing purposes: pn001,
pn002, ..., pn100.
[Sample data].
aggres.f, double precision Fortran 77 program for computing
an estimate of the surface of an aggregate as a power crust from a
point cloud obtained from the surface of the aggregate. Besides a power
crust of the object, the program also produces the area of the power
crust and the volume of the solid it encloses. Here an aggregate is
defined as an object in 3-dimensional space that has no holes and
contains its center of mass in its interior. Output file with power crust
information will be formatted for the purpose of plotting the power crust
with matlab and a script for processing this file with matlab and
obtaining the plot of the power crust is included in the main routine of
the code. Actually the requirement in the definition of an aggregate about
the center of mass can be ignored if a point is known that lies in the
interior of the object at a reasonable distance from the surface.
Exact arithmetic is used when necessary.
[Source code].
regtet.f, double precision Fortran 77 program for computing
with incremental topological flipping a Regular tetrahedralization for
a set of points in 3-dimensional space. Input coordinates and weights
of points can have as many as 14 significant figures with as many as
9 significant figures to either the left or the right of the decimal
point. In the absence of weights the program computes a Delaunay
tetrahedralization. A Regular tetrahedralization is the dual of a Power
diagram. It is essentially a Delaunay tetrahedralization for a set of
points with weights. In this program artificial points are handled
lexicographically. Exact arithmetic is used when necessary. As a result
this program is both fast and robust. If a prompt file does not exist
the program will create a file that can be used as such in order to
avoid user intervention in subsequent executions of the program.
[Source code].
ragtat.f,
same as program regtet.f above but with the option of either computing
from scratch a Regular/Delaunay tetrahedralization for a set of points
in 3-d space or inserting a new set of points in 3-d space into an
existing Regular/Delaunay tetrahedralization. If a prompt file does not
exist the program will create a file that can be used as such in order
to avoid user intervention in subsequent executions of the program.
[Source code].
pwrvtx.f, double precision Fortran 77 program for computing
the Power/Voronoi vertices and unbounded edges for a set of points in
3-dimensional space from a Regular/Delaunay tetrahedralization for the
set. It is assumed that a Regular/Delaunay tetrahedralization for the set
has already been computed using program regtet/ragtat above with logical
variable artfcl set to .false.. The output tetrahedron list from
regtet/ragtat is then used as input for this program. As in the case of
regtet/ragtat, exact arithmetic is used when necessary. The lengths of
input coordinates and weights follow the same rules as when using
regtet/ragtat.
[Source code].
volare.f, double precision Fortran 77 program for computing
volumes of Power/Voronoi cells in the Power/Voronoi diagram of a set of
points in 3-dimensional space, areas of facets of these cells, and the
distances obtained by computing for each facet the distance between the
two points in the set that define the facet (inter-neighbor distances).
It is assumed that a Regular/Delaunay tetrahedralization for the set has
already been computed using program regtet/ragtat above with logical
variable artfcl set to .false.. It is also assumed that the Power/Voronoi
vertices of the Power/Voronoi diagram of the set have already been
computed using program pwrvtx above with the output tetrahedron list
from regtet/ragtat as input. The output Power/Voronoi vertex and
tetrahedron lists from pwrvtx are then used as input for this program.
[Source code].
dtread.f, double precision Fortran 77 program for exhibiting
how output data produced by program volare above must be read and used.
All done in a friendly way.
[Source code].
fctvtx.f, double precision Fortran 77 program for identifying
vertices of each facet of each Power/Voronoi cell in the Power/Voronoi
diagram of a set of points in 3-dimensional space. It is assumed programs
regtet/ragtat, pwrvtx have been executed as described above,
thus producing the corresponding output files.
[Source code].
fvread.f, double precision Fortran 77 program for exhibiting
how output data produced by program fctvtx above must be read and used.
It is also assumed program volare has been executed as described above.
All done in a friendly way.
[Source code].
pwrtet.f, double precision Fortran 77 program for doing 3D
nearest point searches. It identifies Power cells in the Power
diagram of a 3-dimensional set of points S that contain points in a
3-dimensional set R. In other words, for each point in R this program
finds a point in S that is as Power close to the point in R as any
other point in S. If no weights are present then it identifies Voronoi
cells in the Voronoi diagram of S that contain points in R. In
addition, this program determines where with respect to the convex hull
of S the points in R are located. It is assumed that a Regular/Delaunay
tetrahedralization for S has already been computed using program regtet
above with logical variable artfcl set to .true.. The output tetrahedron
list from regtet is then used as input for this program. As in the case
of regtet, exact arithmetic is used when necessary. The lengths of input
coordinates and weights follow the same rules as when using regtet.
The program is based on an algorithm for constructing Regular
tetrahedralizations with incremental topological flipping.
However no actual flippings take place. Given a point in R,
if weights are present a weight is assigned to the point so that
the Power cell of the point in the Power diagram of S together
with the point contains the point. The program then goes through
the motions of inserting the point into the Regular/Delaunay
tetrahedralization for S without actually doing it. This way a
subset of points in S is identified that contains what would be
the Voronoi/Power neighbors of the point in the Voronoi/Power
diagram of S together with the point. The desired point in S
is then a point in this subset closest to the the point in R
in the Power sense. If weights are present care is taken in
choosing the weight assigned to the point in R so that it is as
small as possible.
[Source code].
tritet.f, double precision Fortran 77 program for
inserting a set of 2-dimensional triangles into a tetrahedralization.
The resulting tetrahedralization is then constrained by the triangles.
Topological flipping is used whenever possible in order to obtain the
desired tetrahedralization. Steiner points are used as a last resort.
Since the insertion of the 2-d triangles causes the resulting
tetrahedralization to be partitioned into regions having pair-wise
disjoint interiors, on output tetrahedra are marked according to
the region they belong to. Regions are numbered either arbitrarily
by program or as requested by user. If requested by user the volume of
each region is computed. In this program exact arithmetic is used when
necessary.
[Source code].
pntloc.f, double precision Fortran 77 program for
locating points in a tetrahedralization by moving in a straight
line to each point from a point whose location is known.
In this program exact arithmetic is used when necessary.
[Source code].
Other Sofware:
km_anyd.f, double precision Fortran 77 program for
computing k-means clustering of a set of points in any dimension.
If a rectangle in the form of a 2-d rectangular grid can be
associated with the input points, the option exists for creating
a txt file of k-means cluster indices on the rectangular grid
that can then be used as input to create an image with imagej of
the rectangle partitioned into clusters.
[Source code].
em_anyd.f, double precision Fortran 77 program for
computing k-Gaussian mixture clustering of a set of points in
any dimension with EM (Expectation Maximization) algorithm.
If a rectangle in the form of a 2-d rectangular grid can be
associated with the input points, the option exists for creating
a txt file of k-Gaussian mixture cluster indices on the rectangular
grid that can then be used as input to create an image with imagej
of the rectangle partitioned into clusters. If the program does not
produce a satisfactory k-Gaussian mixture clustering, it is
recommended that a k-means clustering be computed instead with
program km_anyd.f above.
[Source code].
spline.f, single precision Fortran 77 program for
computing cubic spline interpolation under the "not a knot"
condition. Results from this program appear to be exactly the
same as those obtained with the matlab spline function. Program
is based on original code in Slatec package obtained from Guide
to Available Mathematical Software (GAMS) web site at the
National Institute of Standards and Technology.
[Source code].
neurbt.f,
has been replaced by sagrad.f below.
sagrad.f, Fortran 77 program for computing neural networks for
classification using batch learning. Neural network training is based on
a combination of simulated annealing and a scaled conjugate gradient
algorithm, the latter a variation of the traditional conjugate gradient
method. User intervention required. At different times during the
execution of the training process, in order to provide the user with the
option of getting out of a possibly bad run of the process, user will be
asked to decide on whether or not to terminate current run of the training
process. If the run is terminated then user will be asked to decide on
whether program should stop or do a new cold start of the training process.
Training process consists of essentially three steps that involve the
scaled conjugate gradient algorithm and simulated annealing versions of
low and high intensity. The low-intensity version of simulated annealing
(in first step) is used for the (re)initialization of weights required
to (re)start the scaled conjugate gradient algorithm (in second step)
the first time and each time thereafter that it shows insufficient progress
in reaching a possibly local minimum; the high-intensity version of
simulated annealing (in third step) exploits intensively weight space for
a possible global solution, and is used once the scaled conjugate gradient
algorithm has possibly reduced the squared error considerably but becomes
stuck at a local minimum or flat area of weight space. With user
intervention, before the third step is executed (at most once), the first
two steps, one following the other, may be executed several times in hopes
that the scaled conjugate gradient algorithm in the second step will
eventually compute a reasonable solution (squared error for solution close
enough to zero, i.e., less than some tolerance). The scaled conjugate
gradient algorithm in the second step uses as its initial solution the
output weights from the last execution of the low-intensity simulated
annealing in the first step. On the other hand, the low-intensity simulated
annealing in the first step uses as input the best weights found so far
among all executions of the scaled conjugate gradient algorithm in the
second step except at the start of the execution of the process. At the
start of the execution of the process the low-intensity simulated annealing
in the first step uses as input weights that are randomly generated in the
interval (-1,1). It should be noted that all executions of the low-intesity
simulated annealing in the first step tend to produce good initial
solutions for the scaled conjugate gradient algorithm in the second step.
However it is the first execution of the low-intensity simulated annealing
in the first step that usually reduces considerably the squared error while
all others usually produce no reduction at all. Eventually, as the first
two steps are repeatedly executed, either a reasonable solution is found
and the process is terminated, or the third step, which involves an
execution of the high-intensity simulated annealing followed by an
execution of the scaled conjugate gradient algorithm, is executed one time
in hopes of finding a reasonable solution. Note that even if a reasonable
solution has been found by executing only the first two steps, user can
still direct training process to go to the third step perhaps for a better
solution. Note as well that it may take several cold starts of the training
process before a reasonable solution is obtained. Such a solution should
then be tested for quality by applying the corresponding neural network on
independent sample patterns of known classification.
[Source code].
sagrad_data.zip,
Data for testing sagrad program as it appears in publication about
sagrad program.
[sagrad data].