Optimal Chamfer Mask and Coefficients Computation

Reference Article

Gregoire Malandain and Celine Fouard. On optimal chamfer masks and coefficients. Research Report 5566, INRIA, 2005.
It follows a previous work, published in
- C. Fouard and G. Malandain. 3-D chamfer distances and norms in anisotropic grids, Image and Vision Computing, 23(2):143-158, February 2005.

Download

compressed archive

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.

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.
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`

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

Chamfer mask construction

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
```

Chamfer mask coefficients computation

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 = (d_max - d_min) / (d_max + d_min) and Epsilon = (d_max + d_min) / 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