Approximation Programs

My approximation program comes in three flavors (You can download a ZIP archive, compiled for SGI O2, Octane or Onyx2 and Open Inventor):

Approximation1D

This is the program to approximate real-valued, univariate data sets. It is rather boring, and I am not going to describe it any further.

Approximation2D

This program approximates real-valued, bivariate data sets. These type of data sets include laser range scans and greyscale images.

Approximation2DRGB

This program approximates vector-valued, bivariate data sets. The only source of these sets right now are true-color RGB images.

ShowStack

A viewer program to display approximations and to blend between the levels of multiresolution approximations.

Using Approximation2D And Approximation2DRGB

Data source specifiers: (Exactly one of these has to be used)

-b=<file name>

This specifies the name of a true-color RGB image in the PPM format that is to be used as data source. Though the real-valued algorithm only deals with real-valued functions, the image has to be in true-color RGB format for both programs. The real-valued program converts color to greyscale by itself.

-f=<function index>

This instructs the program to use one of the 16 built-in functions as scattered data source. <function index> has to be in the range from 0 to 15. If this parameter is used, the -s parameter has to be given as well to specify the number of samples to produce. This parameter is not implemented by the vector-valued program.

-d=<file name>

This lets the program load a scattered data file in the often-used (so I heard) *.pts format. Rumour has it that tons of those data files can be found on the net. If this parameter is used, sometimes the -j parameter has to be given as well. Again, only for the real-valued algorithm.

Data source modifiers: (Only for the real-valued program)

-s=<number of samples>

This specifies the number of samples to generate if the data source is one of the built-in functions.

-j=<jitter factor>

I don't like to mention this parameter, but there it is. Sometimes a scattered data file in the *.pts format is not scattered after all, but consists of samples aligned on a rectilinear grid. Due to numeric problems (Say no more...) the approximation program sometimes bombs out on these files. To workaround[tm] this problem, one has to specify a jitter factor to randomly displace samples from their regular positions. A reasonable jitter factor would be a very small factor (like 0.000001) times the grid size.

Creation flags:

-i=<file name>

This parameter instructs the program to load a linear spline data file (in the format written by the save parameter) as a lower-order approximation in an approximation hierarchy. If such an approximation is loaded, the program begins by inserting more vertices into the loaded spline, and it does not change the loaded spline's vertices during the iteration. The spline data file has to be of the correct format (real-valued vs. vector-valued).

-v=<number of vertices>

This parameter specifies the number of vertices to use for a linear spline approximation. If a lower-order approximation is specified using the -i parameter, this parameter gives the number of vertices to add to that included approximation, otherwise it is the total number of vertices to use.
There is a correspondence between the number of vertices and the number of triangles and edges in an approximation: If N is the total number of vertices, and k is the number of vertices lying on the boundary of the convex hull of the sample points, then the number of triangles in the approximation is T = 2N - k - 2 and the number of edges is E = 3N - k - 3. Since k = O(sqrt(N)), expect T = O(2N) and E = O(3N).

-oi

This parameter changes the behaviour of the program while creating an initial configuration. If it is not given, new vertices are inserted into the base configuration at random sites, otherwise vertices are inserted at the site of the worst vertex (that is, the one having the greatest distance from the current spline). This parameter is not very useful for creating good approximations, since it results in too good an initial configuration, but it is interesting to see just how good those initial guesses are.

Modifying the annealing schedule:

-p=<initial acceptance probability>

This parameter determines the initial temperature of the simulated annealing algorithm. This temperature is calculated in the following way: At first, the program takes 100 steps of the iteration scheme and calculates the mean error change of those steps. After that, the initial temperature is defined such that an expected bad step (that is, one resulting in the mean error change) is accepted with the given probability. Set this parameter to 0.5 initially.

-t=<temperature decrease factor

This parameter specifies how fast the temperature is to decrease during the iteration. After a certain number of iteration steps, the temperature is multiplied by this factor (it should be smaller than one to let the algorithm converge). This "certain number" of steps is set as five times the number of moveable vertices in the current approximation. A vertex is moveable, if it is neither lying on the boundary of the convex hull, nor being part of an included lower-order approximation. Set this parameter to 0.95 initially.

Modifying the configuration change:

-g=<global movement threshold>

This parameter determines how "curved" a region of the spline can be to still be considered "flat". Vertices in "flat" regions are moved globally to a random new position in the samples' convex hull, vertices in "curved" regions are moved locally to a random, near-by position. Setting this parameter to 0.75 seems to work in most cases.

-og

If this parameter is given, the program attempts to find a "good" new position for a globally moved vertex by moving it to the position of the worst of all sample points. This does not work as well as expected (and is not implemented in the vector-valued case), but it is interesting nonetheless.

-l=<local movement boundary>

This parameter says exactly how far away a vertex' new position can be to be considered near-by in local movements. If you set this parameter to one, a new position lying on the circle around the to-be-moved vertex that has the same area as the average platelet in the initial configuration is considered near-by in 50 percent of the cases. Clear? Set this parameter to 0.5 if the number of sample points is huge compared to the number of vertices, set it to 1.5 if the other way round. Intermediate values are fine for intermediate cases.

-ol

If this parameter is given, the program tries to find a "good" new position for a locally moved vertex. This does not work as well as one would expect, better not use it.

-r=<probability of edge rotation>

In each iteration step, the algorithm can either move a vertex (globally or locally) or rotate an edge. This parameter gives the probability for an edge rotation. If it is set to zero, edges are never rotated and the algorithm maintains a Delaunay triangulation of the vertices throughout the iteration. If it is set to one, only edge rotations occur, and the algorithm degenerates to a data-dependent triangulation algorithm (a good one, though). Set this parameter to 0.15, it works just fine.

Saving final configurations and running in batch mode:

batch <number of iteration steps>

If this parameter is given, the program runs in batch mode, without displaying each step and giving error and update information. In batch mode, the iteration runs for the given number of steps, no more, no less. Also, in batch mode the final configurations can be saved in various formats.

save <file name>

If this parameter is given, the final configuration after completing the iteration in batch mode is saved to a file of the given name. These files can be read in again to create approximation hierarchies, and they can be displayed using the ShowStack program.

saveps <file name prefix>

If this parameter is given, the program saves the initial configuration, the final configuration, a contour line rendering of the final configuration and the graph of the error norm during the iteration to Encapsulated PostScript files of the respective names: <file name prefix>Initial.eps, <file name prefix>Final.eps, <file name prefix>Heightlines.eps and <file name prefix>Error.eps. This comes in quite handy if you have to prepare a Diploma thesis and need to include nice figures. You can also use the ShowStack program to save a flat-shaded 3D rendering of an approximation to an Encapsulated PostScript file.

If the approximation programs are not started in batch mode, they create and display the initial configuration, but do not start the iteration immediately. To do this, one has to press the C key. To interrupt the iteration, press the S key. (To continue, press C once again.)

Using ShowStack

ShowStack (real | rgb) file1 file2 file3 ... filen

<home>

Switches to the coarsest approximation in a hierarchy.

<left arrow>

Switches to the next coarser approximation in a hierarchy.

<right arrow>

Switches to the next finer approximation in a hierarchy.

<end>

Switches to the finest approximation in a hierarchy.

W

Saves the configuration of the currently displayed approximation to an Encapsulated PostScript file named "Output.eps".

H

Saves a contour line rendering of the currently displayed approximation to an Encapsulated PostScript file named "Output.eps".

S

Saves the current view of the currently displayed real-valued approximation to an Encapsulated PostScript file named "Output.eps".

V

Saves the currently displayed approximation as an Open Inventor file named "Output.iv". This can also be used to create VRML representations of these approximations for distribution on the World Wide Web.

C

Saves the current view of the currently displayed vector-valued approximation to a bitmap embedded in an Encapsulated PostScript file. No, I'm just kidding. Use Snapshot instead!