# Optimal Chamfer Mask and Coefficients Computation

### Installation and Compilation

The code has been written in C. The following stands for unix/linux systems, but it should not be difficult for windows folks to achieve to compile it.

1. Decompress the archive
• either by tar xvfz chamfer-coefficients-some date.tar.gz
• or by unzip chamfer-coefficients-some date.zip
it should result in a help file (this file) and a directory named src.
2. go in the directory by cd src and compile by make. If you do not have the make command installed, you can also directly compile by
```cc -O -I. -o gener-mask gener-mask.c chamfer.c -lm
```
you end up with a binary file named gener-mask

• Running gener-mask without any command line options, i.e.
```gener-mask
```
gives the list of available options for the command line. The -help option, i.e.
```gener-mask -help
```
will give you more details about each of them

• By default, the mask is built in a NxN(xN) neighborhood (N=3 by default). The command
```gener-mask -dim 3 -size 3 -bo
```
will print the geometry of a 3x3x3 chamfer mask (the -bo option means "build only", i.e. do not compute the coefficients):
```#VECTORS = 3
v[#  0] = ( 1  0  0) c=0
v[#  1] = ( 1  1  0) c=0
v[#  2] = ( 1  1  1) c=0
```
• The first lines indicate the number of and the vectors that are considered (here, because of the symmetries of the isotropic lattice, only 1/48th of the space is considered).
```#CONES = 1   ERR MIN = 0.060191   ERR MAX = 0.060191
```
• This line indicate the number of cones (or sectors) the mask is made of, as well as the minimum and the maximum error of these sectors (0.060191 means 6.0191 %). The maximum error if the error of the mask. The cones are the Farey triangulation of the mask.
```c[#  0] = [( 1  0  0) ( 1  1  0) ( 1  1  1)], E=0.060191
```
• Then the differents sectors are listed (they are sorted in decreasing order of the error).

• Additional vectors of the 3x3x3 masks are added if some assymmetry (i.e. anisotropy) is introduced. The following command specifies a voxel size of 2 units (with th -z option) along the Z direction (by convention, the pixel/voxel size along the X direction is of 1 unit)
```gener-mask -dim 3 -size 3 -z 2 -bo
```
it yields
```#VECTORS = 5
v[#  0] = ( 1  0  0) c=0
v[#  1] = ( 1  1  0) c=0
v[#  2] = ( 1  1  1) c=0
v[#  3] = ( 1  0  1) c=0
v[#  4] = ( 0  0  1) c=0

#CONES = 3   ERR MIN = 0.024113   ERR MAX = 0.090827
c[#  0] = [( 1  0  0) ( 1  1  0) ( 1  1  1)], E=0.090827
c[#  1] = [( 1  0  1) ( 1  0  0) ( 1  1  1)], E=0.088750
c[#  2] = [( 0  0  1) ( 1  0  1) ( 1  1  1)], E=0.024113
```

• Masks can also be built with respect to a maximal error. The following command
```gener-mask -dim 3 -error 0.025 -bo
```
will generate a mask which sectors have an error less than 0.025, i.e.
```#VECTORS = 5
v[#  0] = ( 1  0  0) c=0
v[#  1] = ( 1  1  0) c=0
v[#  2] = ( 1  1  1) c=0
v[#  3] = ( 2  1  1) c=0
v[#  4] = ( 2  1  0) c=0

#CONES = 3   ERR MIN = 0.017352   ERR MAX = 0.024113
c[#  0] = [( 1  0  0) ( 2  1  0) ( 2  1  1)], E=0.024113
c[#  1] = [( 2  1  1) ( 1  1  0) ( 1  1  1)], E=0.024103
c[#  2] = [( 2  1  0) ( 1  1  0) ( 2  1  1)], E=0.017352
```
• Note:
Specifying the option -size N after the option -error E will constrain the newly built vectors to be within the NxNxN neighborhood. Hence a sector can only be splitted if the created vector belongs to the NxNxN neighborhood.
To appreciate this effect, compare
```gener-mask -dim 3 -error 0.012 -bo
```
and
```gener-mask -dim 3 -error 0.012 -size 7 -bo
```

• Last, masks can also be built with respect to a maximal number of vectors. The following command
```gener-mask -dim 3 -vectors 4 -bo
```
will generate a mask of 4 vectors within the considered 1/nth of the space (in 3-D, in an isotropic lattice 1/48th of the space is considered, with an anisotropy along only one dimension (either -y Y or -z Z is specified) 1/16th of the space is considered, and with anisotropies along two dimensions (both -y Y and -z Z are specified) 1/8th of the space is considered).
• Note:
Specifying the option -size N after the option -vectors V will constrain the newly built vectors to be within the NxNxN neighborhood.
To appreciate this effect, compare
```gener-mask -dim 3 -z 2 -bo -vectors 9
```
and
```gener-mask -dim 3 -z 2 -bo -vectors 9 -size 5
```

• The command
```gener-mask -dim 3 -size 3
```
(the -bo option is no more specified) generates
```#VECTORS = 3
v[#  0] = ( 1  0  0) c=0
v[#  1] = ( 1  1  0) c=0
v[#  2] = ( 1  1  1) c=0

#CONES = 1   ERR MIN = 0.060191   ERR MAX = 0.060191
c[#  0] = [( 1  0  0) ( 1  1  0) ( 1  1  1)], E=0.060191
```
• Above is what is related to the mask construction.
• Below is the list of the optimal coefficient sets, that are printed as soon as they are know.
The first line gives the resulting error (e.g. 0.267949 i.e. 26.7949 %), its percentage w.r.t. the best possible error, i.e. the ERR MAX above, (e.g. 0.267949/0.060191 * 100 = 445.162 %), the multiplicative constant that has to divide the integer Chamfer distance map to yield en estimation of the Euclidean distance, and the needed computation time to compute the coefficients.
The second line gives the minimum and the maximum values of the integer Chamfer distance map. We have
Error = (dmax - dmin) / (dmax + dmin)
and
Epsilon = (dmax + dmin) / 2
```Error = 0.267949   445.162 % / OPT --- Epsilon = 0.788675 --- Elapsed time = 0.000000 ms
--- dmin = 0.577350   dmax = 1.000000
v[# 0] = ( 1  0  0)   w=   1
v[# 1] = ( 1  1  0)   w=   1
v[# 2] = ( 1  1  1)   w=   1

Error = 0.171573   285.046 % / OPT --- Epsilon = 1.207107 --- Elapsed time = 0.000000 ms
--- dmin = 1.000000   dmax = 1.414214
v[# 0] = ( 1  0  0)   w=   1
v[# 1] = ( 1  1  0)   w=   2
v[# 2] = ( 1  1  1)   w=   2

...
...
...

Error = 0.079446   131.988 % / OPT --- Epsilon = 3.072526 --- Elapsed time = 0.000000 ms
--- dmin = 2.828427   dmax = 3.316625
v[# 0] = ( 1  0  0)   w=   3
v[# 1] = ( 1  1  0)   w=   4
v[# 2] = ( 1  1  1)   w=   5

...
...
...

Error = 0.061054   101.433 % / OPT --- Epsilon = 20.235455 --- Elapsed time = 30.000000 ms
--- dmin = 19.000000   dmax = 21.470911
v[# 0] = ( 1  0  0)   w=  19
v[# 1] = ( 1  1  0)   w=  27
v[# 2] = ( 1  1  1)   w=  33
```
• Once the computation ends, the results are again displayed in a more concise table (using the -latex option, i.e. by specifying -latex filename in the command line, it can also be written in LaTeX format).
``` Best possible error = 0.060191
[ 1]   [ 1]   [ 1]
[ 0]   [ 1]   [ 1]  ---       err      %/opt      eps         time
[ 0]   [ 0]   [ 1]

1      1      1   ---    26.794919 ( 445.2)   0.788675       0.00
1      2      2   ---    17.157288 ( 285.0)   1.207107       0.00
2      3      3   ---    12.701665 ( 211.0)   1.984059       0.00
2      3      4   ---    10.102051 ( 167.8)   2.224745       0.00
3      4      5   ---     7.944565 ( 132.0)   3.072526       0.00
4      6      7   ---     6.787889 ( 112.8)   4.291288       0.00
7     10     12   ---     6.389617 ( 106.2)   7.401106      10.00
11     16     19   ---     6.320549 ( 105.0)  11.709777      10.00
12     17     21   ---     6.255385 ( 103.9)  12.800735      10.00
19     27     33   ---     6.105399 ( 101.4)  20.235455      30.00
```

### Examples

The -matlab option (by specifying -matlab filename in the command line) generates a Matlab file commands that allows to visualize the distribution of errors (in percentage) on the mask sectors. The figures

have been respectively generated by
```gener-mask -dim 3 -size 5 -y 1.0 -z 1.0 -matlab mask_size5.m -bo
```
and
```gener-mask -dim 3 -size 7 -y 1.0 -z 1.0 -matlab mask_size7.m -bo
```

### Options

The command

```gener-mask -help
```
generates
```gener-mask:
[-prebuild|-pb %d] [-build-only|-bo] [-y %f] [-z %f]
[-f %d] [-l %d]
[-res %s] [-matlab %s] [-latex %s]
[-help|--help] [-examples|-ex]

-dim %d : space dimension (3 or 2 (default))
3 (default) -> mask 3x3 or 3x3x3
5 ->  mask 5x5 or 5x5x5
etc.
-vectors %d : maximal number of vectors in mask
if -mask-size is also specified (after in the command line)
the vectors are restricted in the given neighborhood
-error %f : maximal sector error
0.01 means 1%
can be used in conjunction with -mask-size and -vectors
-prebuild|-pb %d : prebuilt masks (assume dim=3)
335
355
this was implemented for comparison with (Fouard, IVC, 2005)
-y %f : pixel or voxel dimension along Y
-z %f : voxel dimension along z
-build-only|-bo: do not compute weights

=====  weight computing  =====
-f %d : first weight value (default=1)
-l %d : last weight value (default=20)

===== output controlling =====
-res %s : specify output text file (default is stdout)
-matlab %s : specify output matlab file