Harris 3D - Detecting interest points on 3D Meshes

We have proposed a fast and effective interest point detector for 3D meshes. This page is devoted to present our method. In addition, implementations are available for research purposes.

The Method

Our algorithm works in a vertex-wise manner in order to compute the Harris response for each vertex. We aim at considering a local neighborhood around a vertex as an image, so it is possible to apply the well-known Harris operator. Briefly, our method performs as follows:
  • It determines a neighborhood for each vertex. It can be spatial, adaptive or ring neighborhoods.
  • It finds a canonical local system by applying PCA to the neighborhood.
  • It fits a quadratic surface on the normalized neighborhood.
  • It computes derivatives on the fitted surface. Gaussian functions are used for smoothing the derivatives. By using integration between the derivatives and the gaussians, the method is robust to local geometric changes.
  • Using the derivatives, the algorithm constructs the auto-correlation function needed to evaluate the Harris operator. Subsequently, a response is computed for each vertex.
  • Our method suggests two ways for selecting the interest points based on the vertex's responses: a number of vertices with the highest responses, or clustering for well distributed interest points.

The following figure shows an example (Shape was taken from the TOSCA dataset).

Our method is the fastest interest point detector on 3D meshes. In addition, it has proven to be effective in different scenarios. It has been tested with the SHREC'2010 and SHREC'2011 feature detection and description benchmark, obtaining remarkable results. Furthermore, it has been applied in Non-Rigid Retrieval in the SHREC'2011 Non-Rigid Retrieval contest.

Publications

  • Boyer, E., Bronstein, Alexander M., Bronstein, Michael M., Bustos, Benjamin, Darom, T., Horaud, Radu, Hotz, I., Keller, Y., Keustermans, J., Kovnatsky, A., Litman, R., Reininghaus, J., Sipiran, Ivan, Smeets, D., Suetens, P., Vandermeulen, D., Zaharescu, Andrei, and Zobel, V.: SHREC 2011: robust feature detection and description benchmark, Proc. Workshop on 3D Object Retrieval (3DOR'11), Eurographics Association, 2011, To appear [pdf]
  • Boyer, E., Bronstein, Alexander M., Bronstein, Michael M., Bustos, Benjamin, Darom, T., Horaud, Radu, Hotz, I., Keller, Y., Keustermans, J., Kovnatsky, A., Litman, R., Reininghaus, J., Sipiran, Ivan, Smeets, D., Suetens, P., Vandermeulen, D., Zaharescu, Andrei, and Zobel, V.: SHREC 2011: robust feature detection and description benchmark, Technical report. [pdf]
  • Lian, Zhouhui, Godil, Afzal, Bustos, Benjamin, Daoudi, Mohamed, Hermans, J., Kawamura, Shun, Kurita, Y., Lavoue, G., Nguyen, H.V., Ohbuchi, Ryutarou, Ohishi, Y., Porikli, F., Reuter, Martin, Sipiran, Ivan, Smeets, D., Suetens, P., Tabia, H., and Vandermeulen, D.: SHREC'11 Track: Shape retrieval on Non-Rigid 3D Watertight Meshes>, Proc. Workshop on 3D Object Retrieval (3DOR'11), Eurographics Association, 2011, To appear [pdf]
  • Ivan Sipiran and Benjamin Bustos. A robust 3D interest points detector based on Harris operator. Proc. Eurographics Workshop on 3D Object Retrieval (3DOR'10). [pdf]
  • Alexander Bronstein, Michael Bronstein, Benjamin Bustos, Umberto Castellani, Marco Crisani, Bianca Falcidieno, Leonidas Guibas, Iasonas Kokkinos, Vittorio Murino, Ivan Sipiran, Maks Ovsjanikov, Giuseppe Patane, Michuela Spagnuolo, Jian Sun. SHREC 2010: Robust feature detection and description benchmark. Proc. Eurographics Workshop on 3D Object Retrieval (3DOR'10). [pdf]

Source code

We make available two implementations of Harris 3D. The source codes can be used only for research purposes. Do not hesitate to email me if you have any suggestion, bug, or comment. Any use of the source codes must refer to the paper: A robust 3D interest points detector based on Harris operator by Sipiran and Bustos.

C++ Implementation

The source code has been tested only under Linux. The following requeriments are needed for compiling:
  • Cmake (>= 2.4): Required to properly compile our project.
  • CGAL (>=3.6): Required for efficient spatial neighborhood determination.
  • GSL (>=1.15): Required for solving the eigenvalue problem of the Harris matrix.
In order to compile the source code:
  • In a console, go to the directory with the source files.
  • Execute: cgal_create_cmake_script demo. It generates a CMakeLists.txt file with the configuration for cmake. Open the CMakeLists.txt with your favorite editor. Go to the line with the command "target_link_libraries" and, at the final of the command (before the closing parenthesis), add "gsl gslcblas".
  • Execute cmake: "cmake -DBUILD_TYPE=RELEASE ." (Note the . at the end of the command). It generates a valid Makefile for the final step.
  • Execute make.
  • It's done!
Once the executable is generated, it has to be executed as follows:
./harris_executable off_file [properties_file]

Our implementation supports only the OFF file format. The program writes the interest points indices onto a file with the same name as the input OFF file, but with the extension "int". In addition, as the algorithm needs some parameters, a properties file has to be optionally given (If a property file is not given, default parameters are used, as presented in the original paper). A property file is a text file specifying the parameters for the algorithm. The following parameters can be set: (An example of properties file comes along with the source code - example.prop)

  • type-neighborhood = {adaptive, spatial, rings} : Defines the neighborhood type for each vertex
  • parameter-neighborhood = number : For adaptive and spatial, number is a fraction of the diagonal of the bounding box of the 3D object. For rings, number is the number of rings considered as neighborhood.
  • K = number: The parameter for the evaluation of Harris response.
  • ring-maxima-detection = number: Number of rings considered to evaluate the maximum response for each vertex.
  • interest-points-selection = {fraction, clustering}: Type of selection for final interest points.
  • parameter-selection = number: For fraction, it represents the fraction of the total number of vertices. For clustering, the distance (in terms of fraction of the diagonal of the bounding box) of clustering for a vertex.

Matlab/C++ Implementation

This source code has been tested only under Linux with Matlab R14. This implementation provides an interface of Harris 3D for Matlab. It is worth noting that this implementation does not support spatial neighborhoods. In addition, it returns a Harris responses array.

In order to compile the source code:
  • In a console, got to the directory with the source files.
  • Open the Makefile provided with your favorite editor. Probably, you need to change the paths of the mex executable and the compiler. Lines 1-4 and 8 contain that information. Change them according to your system configuration.
  • Execute: make
  • It's done. It should create a file harrisInterface.mexglx.

Go to Matlab, and now you can execute the command

[IP resp] = harrisInterface(off_file, property_file)
The function delivers the set of interest points (with indices starting in 1) and an array with the Harris responses for each vertex.