bbhec: A Branch-and-Bound Algorithm for Globally Optimal Hand-Eye Calibration

Jan Heller <hellej1@cmp.felk.cvut.cz>

June 1, 2012

1 What is bbhec?

Program bbhec is a research implementation of the hand-eye calibration method described in [1]. It also implements enhancements to the original method described in [2]. It is written in C++ and will compile with gcc under a reasonably recent Linux distribution. The program is distributed in the hope it will be useful for research purposes, but without ANY warranty. It is covered by GNU General Public License, either version 3, or (at your option) any later version.

2 Where to download?

The current version of bbhec is 0.2 and can be downloaded as bbhec-0.2.tgz.

3 How to cite?

If you use bbhec in your scientific work, please cite as [1].

4 How to compile?

To compile bbhec, you will need a reasonably recent Linux distribution with gcc >= 4.0.0. The source code probably won’t compile with any other compiler. Also, it will not compile under Windows, since it uses unix specific system calls. The source code depends on several third party libraries:

  1. Eigen >= 3.0.0 (http://eigen.tuxfamily.org)
  2. levmar >= 2.6 (http://www.ics.forth.gr/~lourakis/levmar/)
  3. glpk >= 4.47 (http://www.gnu.org/software/glpk/)

To compile a dynamically linked version of bbhec switch to the root directory of the bbhec distribution and simply run

$ make

in your favorite shell. A Statically linked version can be build using

$ make static

command.

You can add compiler and linker flags by setting CPPFLAGS and LDFLAGS environment variables respectively. For finer control over the compilation process edit src/Makefile. For your convenience, two statically linked versions of bbhec are distributed with the source code. These can be found in bin directory as bbhec_static_sse2 and bbhec_static_sse4.1.

There is a couple of things to note about the source code:

5 How to install?

bbhec does not install. Just run it from any convenient location. However, in case you are running the multi-core version, make sure that the current working directory is writable and that it is on locally mounted file system. This is because bbhec uses named pipes to communicate with the child processes and will create them in the current working directory. The pipes will be deleted once the parent process exits.

6 How to run?

The bbhec binary takes several optional parameters followed by the name of the file containing the input data.

6.1 Parameters

$ bbhec [-v vlevel] [-p noproc] [-e epsilon] [-s sigma_min] [-h] experiment.txt

-v vlevel
Verbosity level. Set to 1 to see the progress info output of the branch-and-bound algorithm. Default value is 0.
-p noproc
Number of processes. In case noproc is more than 1, bbhec will fork noproc child processes for parallel computation. In case of a multi-core CPU, set noproc to match the number of cores. Default value is 1.
-e epsilon
An upper estimate of the resulting error in radians. This value is crucial for the correct behavior of the algorithm. In case of a loose estimate, the algorithm may take too long to finish, in case the resulting error is underestimated, the algorithm will not find the optimal solution at all. Default value is 0.2.
-s sigma_min
Stopping criterion. The subdivision process will not continue if a cube with the edge length equal to sigma_min is found. The algorithm will process the remaining cubes in the queue and will return the best solution found so far. Default value is 0.001.
-h
Help.

6.2 Input File Structure

The hand-eye calibration method that bbhec implements requires relative robotic gripper movements and 3D image correspondences. Please see [1] for more details. The structure of the input file is best explained by an example. Suppose the robotic gripper was commanded into four poses, resulting into n = 3 relative movements

                     (                                    )
       (         )   |  0.9161   0.1201   − 0.3824 302.2180  |
B1  =    RB1⊤  tB1  = |(  0.0158   0.9424   0.3341  − 337.5020 |) ,
          0    1        0.4005  − 0.3121  0.8614   170.9839
                     (    0       0        0        1     )
       (         )      0.9654   0.0939   − 0.2432 321.2479
B   =    RB2  tB2  = ||  0.0087   0.9439   0.3299  − 329.7359 || ,
 2        0⊤   1     (  0.2606  − 0.3164  0.9121    33.6801  )
                          0       0        0        1
                     (   0.9814   0.0587  0.1823 − 147.5893 )
       ( RB3  tB3)   |  − 0.0841 0.9872  0.1349 − 188.8623 |
B3  =     0⊤   1   = |(  − 0.1720 − 0.1477 0.9739  437.8913  |) .
                           0       0       0        1
Further suppose that m1 = 2 correspondences
u   ↔ v  , u  ,v  ∈ ℝ3,∥u ∥ = ∥v  ∥ = 1,j = 1,...,m ,
  1j    1j   1j  1j        1j     1j               1

where determined for the first relative movement:

     (          )           (          )
         0.1542                  0.1005
u11 = ( − 0.6585 ) ↔   v11 = ( − 0.5347 ) ,
     (   0.7365  )           (   0.8389  )
        − 0.4502               − 0.6326
u12 = ( − 0.0154 ) ↔   v12 = (  0.0349  ) .
         0.8927                  0.7736

Analogously, m2 = 2 correspondence u21 v21 and u22 v22 were determined for the second relative movement

     (          )           (          )
         0.1005                  0.0837
u21 = ( − 0.5347 ) ↔   v21 = ( − 0.4314 ) ,
     (   0.8389  )           (   0.8982  )
        − 0.6327               − 0.7201
u22 = (  0.0349  )  ↔   v22 = (  0.0674  ) .
         0.7736                  0.6906

and m3 = 2 correspondences u31 v31 and u32 v32 where determined for the third relative movement

     (   0.0837  )           (   0.0544  )
u31 = ( − 0.4314 ) ↔   v31 = ( − 0.3046 ) ,
         0.8982                  0.9509
     (  − 0.7201 )          (  − 0.5436 )
u32 = (  0.0673  )  ↔   v32 = (  0.1092  ) .
         0.6905                  0.8321

The input file describing this configuration should have the following structure:

n
RB1(1,1)  RB1(1,2)  RB1(1,3) RB1(2,1)  RB1(2,2)  RB1(2,3) RB1(3,1)  RB1(3,2)  RB1(3,3)
RB2(1,1)  RB2(1,2)  RB2(1,3) RB2(2,1)  RB2(2,2)  RB2(2,3) RB2(3,1)  RB2(3,2)  RB2(3,3)
RB3(1,1)  RB3(1,2)  RB3(1,3) RB3(2,1)  RB3(2,2)  RB3(2,3) RB3(3,1)  RB3(3,2)  RB3(3,3)
tB1(1)    tB1(2)    tB1(3)
tB2(1)    tB2(2)    tB2(3)
tB3(1)    tB3(2)    tB3(3)
m1
u11(1)   u11(2)   u11(3)   v11(1)   v11(2)    v11(3)
u12(1)   u12(2)   u12(3)   v12(1)   v12(2)    v12(3)
m2
u21(1)   u21(2)   u21(3)   v21(1)   v21(2)    v21(3)
u22(1)   u22(2)   u22(3)   v22(1)   v22(2)    v22(3)
m3
u31(1)   u31(2)   u31(3)   v31(1)   v31(2)    v31(3)
u32(1)   u32(2)   u32(3)   v32(1)   v32(2)    v32(3)

This structure translates into the following input file:

3  
0.9161 0.1201 -0.3824 0.0158 0.9424 0.3341 0.4005 -0.3121 0.8614  
0.9654 0.0939 -0.2432 -0.0087 0.9439 0.3299 0.2606 -0.3164 0.9121  
0.9814 0.0587 0.1823 -0.0841 0.9872 0.1349 -0.1720 -0.1477 0.9739  
302.2180 -337.5020 170.9839  
321.2479 -329.7359 33.6801  
-147.5893 -188.8623 437.8913  
2  
0.1542 -0.6585 0.7365 0.1005 -0.5347 0.8389  
-0.4502 -0.0154 0.8927 -0.6326 0.0349 0.7736  
2  
0.1005 -0.5347 0.8389 0.0837 -0.4314 0.8982  
-0.6327 0.0349 0.7736 -0.7201 0.0674 0.6906  
2  
0.0837 -0.4314 0.8982 0.0544 -0.3046 0.9509  
-0.7201 0.0673 0.6905 -0.5436 0.1092 0.8321

6.3 Output

The program will output the value of the optimal hand-eye calibration as rotational matrix Rx and translational vector tx. It will also output the value of the error of this solution as epsilon_min and the rotation block there this solution has been found opt.block. The following console output is an example of the output returned by bbhec on an synthetically generated experiment exp/syn_180_0.0003.txt:

$ bbhec -s 0.001 exp/syn_180_0.0003.txt  
epsilon_min = 0.0031545162  
         tx = [17.9216136932, -61.9211006165, 90.4134521484]  
 opt. block = [-0.1748738140, -0.0659611747, 0.1242524460, 0.0015339808]  
         Rx = [ 0.9901014566, -0.1183245182, -0.0754880905  
                0.1296278685,  0.9771243930,  0.1685957164  
                0.0538122393, -0.1767122298,  0.9827904105]

This output shows the optimal hand-eye calibration

                 (                                                          )
    (        )      0.9901014566  − 0.1183245182 − 0.0754880905  17.9216136932
X =    RX  tX   = ||  0.1296278685  0.9771243930   0.1685957164  − 61.9211006165 || .
      0⊤   1     (  0.0538122393  − 0.1767122298  0.9827904105   90.4134521484  )
                         0            0              0              1

References

  1. Jan Heller, Michal Havlena and Tomas Pajdla, A Branch-and-Bound Algorithm for Globally Optimal Hand-Eye Calibration, IEEE Conference on Computer Vision And Pattern Recognition, Providence, Rhode Island, 2012.
  2. Jan Heller, Michal Havlena and Tomas Pajdla, bbhec: A Branch-and-Bound Algorithm for Globally Optimal Hand-Eye Calibration, Research Report CTU–CMP–2012–12, Czech Technical University in Prague, 2012 [PDF].