ellipsoid-fit

Ellipsoid fitting in C++ using Eigen. Widely inspired by https://www.mathworks.com/matlabcentral/fileexchange/24693-ellipsoid-fit

Note

The radii of the fitted ellipsoid surface are arranged based on the smallest rotation angle of the ellipsoid axes, deviated from the defined reference frame, along its axis of rotation containing its approximate center.

This arrangement also applies to the sequence of the eigenvalues and their corresponding eigenvectors. Consequently, the transpose of the eigenvectors' matrix from *evec_column_p, generated by the function

Parameters ellipsoid::fit(..., Eigen::Vector3d* eval_p, Eigen::Matrix3d* evec_column_p, ...);

can be used as a rotation matrix to rotate the fitted ellipsoid to the nearest non-rotated ellipsoid, in term of rotation angle.

Mathematical Details

From the C++ function above, suppose *eval_p contains $[e_0\ e_1\ e_2]^T$, and let its diagonal matrix eval_p->asDiagonal() denoted as $E$. Meanwhile, let evec_column_p->transpose() be denoted as $R$.

Consider the inputs be $d_{in}=[x_{in}\ y_{in}\ z_{in}]^T$, while the outputs produced from rotating the inputs be $d_{out}=[x_{out}\ y_{out}\ z_{out}]^T$. The relationship between these vectors is given by:

$$e_0\ x_{out}^2+e_1\ y_{out}^2+e_2\ z_{out}^2 = d_{in}^T R^T E\ R\ d_{in}$$

Hence, the rotation from $d_{in}$ to $d_{out}$ is performed using $d_{out} = R\ d_{in}$ or

...
Eigen::Vector3d d_in; // Inputs
Eigen::Matrix3d R = evec_column_p->transpose();

// Perform the multiplication d_out = R * d_in
Eigen::Vector3d d_out = R * d_in;
...

Additionally, the transformation from the fitted ellipsoid to a unit sphere can be achieved using $d_{out} = \sqrt{E} R\ d_{in}$, or

...
Eigen::Vector3d d_in; // Inputs
Eigen::Matrix3d R = evec_column_p->transpose();
Eigen::Matrix3d sqrt_E = eval_p->cwiseSqrt().asDiagonal();

// Perform sphere mapping d_out = E^(0.5) * R * d_in
Eigen::Vector3d d_out = sqrt_E * R * d_in;
...

This process involves first rotating the inputs, followed by scaling them.

Warning

If any of the radii results in a 'NaN' value, it indicates that the fitted surface is a hyperboloid, not an ellipsoid.

Possible causes include:

1. Incomplete coverage of the surface points in the input data.
2. Numerical errors during the least square minimization in the fitting process. (A fix is required in the future)

Package Overview

The ellipsoid-fit package contains the following:

• Libraries:

  • ellipsoid-fit (shared)

• Examples:

  • fitting-example

• Tests:

  • test-ellipsoid-fit

Installation and Usage

The ellipsoid-fit project is packaged using PID, a build and deployment system based on CMake.

If you wish to adopt PID for your develoment please first follow the installation procedure here.

If you already are a PID user or wish to integrate ellipsoid-fit in your current build system, please read the appropriate section below.

Using an existing PID workspace

This method is for developers who want to install and access ellipsoid-fit from their PID workspace.

You can use the deploy command to manually install ellipsoid-fit in the workspace:

cd <path to pid workspace>
pid deploy package=ellipsoid-fit # latest version
# OR
pid deploy package=ellipsoid-fit version=x.y.z # specific version

Alternatively you can simply declare a dependency to ellipsoid-fit in your package's CMakeLists.txt and let PID handle everything:

PID_Dependency(ellipsoid-fit) # any version
# OR
PID_Dependency(ellipsoid-fit VERSION x.y.z) # any version compatible with x.y.z

If you need more control over your dependency declaration, please look at PID_Dependency documentation.

Once the package dependency has been added, you can use ellipsoid-fit/ellipsoid-fit as a component dependency.

You can read PID_Component and PID_Component_Dependency documentations for more details.

Standalone installation

This method allows to build the package without having to create a PID workspace manually. This method is UNIX only.

All you need to do is to first clone the package locally and then run the installation script:

git clone https://gite.lirmm.fr/rpc/math/ellipsoid-fit.git
cd ellipsoid-fit
./share/install/standalone_install.sh

The package as well as its dependencies will be deployed under binaries/pid-workspace.

You can pass --help to the script to list the available options.

Using ellipsoid-fit in a CMake project

There are two ways to integrate ellipsoid-fit in CMake project: the external API or a system install.

The first one doesn't require the installation of files outside of the package itself and so is well suited when used as a Git submodule for example. Please read this page for more information.

The second option is more traditional as it installs the package and its dependencies in a given system folder which can then be retrived using find_package(ellipsoid-fit). You can pass the --install <path> option to the installation script to perform the installation and then follow these steps to configure your environment, find PID packages and link with their components.

Using ellipsoid-fit with pkg-config

You can pass --pkg-config on to the installation script to generate the necessary pkg-config files. Upon completion, the script will tell you how to set the PKG_CONFIG_PATH environment variable for ellipsoid-fit to be discoverable.

Then, to get the necessary compilation flags run:

pkg-config --static --cflags ellipsoid-fit_ellipsoid-fit

pkg-config --variable=c_standard ellipsoid-fit_ellipsoid-fit

pkg-config --variable=cxx_standard ellipsoid-fit_ellipsoid-fit

To get linker flags run:

pkg-config --static --libs ellipsoid-fit_ellipsoid-fit

Offline API Documentation

With Doxygen installed, the API documentation can be built locally by turning the BUILD_API_DOC CMake option ON and running the doc target, e.g

pid cd ellipsoid-fit
pid -DBUILD_API_DOC=ON doc

The resulting documentation can be accessed by opening <path to ellipsoid-fit>/build/release/share/doc/html/index.html in a web browser.

License

The license that applies to the whole package content is GNULGPL. Please look at the license.txt file at the root of this repository for more details.

Authors

ellipsoid-fit has been developed by the following authors:

• Benjamin Navarro (LIRMM)
• CK-Explorer ()

Please contact Benjamin Navarro (navarro@lirmm.fr) - LIRMM for more information or questions.