{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbsphinx": "hidden"
   },
   "outputs": [],
   "source": [
    "import open3d as o3d\n",
    "import os\n",
    "import time\n",
    "import sys\n",
    "\n",
    "# monkey patches visualization and provides helpers to load geometries\n",
    "sys.path.append('..')\n",
    "import open3d_tutorial as o3dtut\n",
    "# change to True if you want to interact with the visualization windows\n",
    "o3dtut.interactive = not \"CI\" in os.environ"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Intrinsic shape signatures (ISS)\n",
    "\n",
    "In this tutorial we will show how to detect the **ISS** Keypoints of a 3D shape. The implementation is based on the keypoint detection modules proposed in Yu Zhong , \"Intrinsic Shape Signatures: A Shape Descriptor for 3D Object Recognition\", 2009.\n",
    "\n",
    "\n",
    "## ISS Keypoints\n",
    "\n",
    "ISS saliency measure is based on the Eigenvalue Decomposition (EVD) of the scatter matrix $\\boldsymbol{\\Sigma}(\\mathbf{p})$ of the points belonging to the support of $p$, i.e.\n",
    "\n",
    "$$\\begin{array}{l}\n",
    "\\boldsymbol{\\Sigma}(\\mathbf{p})=\\frac{1}{N} \\sum_{\\mathbf{q} \\in \\mathcal{N}(\\mathbf{p})}\\left(\\mathbf{q}-\\mu_{\\mathbf{p}}\\right)\\left(\\mathbf{q}-\\mu_{\\mathbf{p}}\\right)^{T} \\quad \\text { with } \\\\\n",
    "\\mu_{\\mathbf{p}}=\\frac{1}{N} \\sum_{\\mathbf{q} \\in \\mathcal{N}(\\mathbf{p})} \\mathbf{q}\n",
    "\\end{array}$$\n",
    "\n",
    "Given $\\boldsymbol{\\Sigma}(\\mathbf{p})$, its eigenvalues in decreasing magnitude order are denoted here as $\\lambda_1$, $\\lambda_2$, $\\lambda_3$. During the pruning stage, points whose ratio between two successive eigenvalues is below a threshold are retained:\n",
    "\n",
    "$$\\frac{\\lambda_{2}(\\mathbf{p})}{\\lambda_{1}(\\mathbf{p})}<\\gamma_{12} \\wedge \\frac{\\lambda_{3}(\\mathbf{p})}{\\lambda_{2}(\\mathbf{p})}<\\gamma_{23}$$\n",
    "\n",
    "The rationale is to avoid detecting keypoints at points exhibiting a similar spread along the principal directions, where a repeatable canonical reference frame cannot be established and, therefore, the subsequent description stage can hardly turn out effective. Among remaining points, the saliency is determined by the magnitude of the smallest eigenvalue\n",
    "\n",
    "$$\\rho(\\mathbf{p}) \\doteq \\lambda_{3}(\\mathbf{p})$$\n",
    "\n",
    "So as to include only points with large variations along each principal direction.\n",
    "\n",
    "After the detection step, a point will be considered a **keypoint** if it has the maximum saliency value on a given neighborhood.\n",
    "\n",
    "**NOTE:** For more details please refer to the original publication or to \"Performance Evaluation of 3D Keypoint Detectors\", by Tombari et.al.\n",
    "\n",
    "## ISS keypoint detection example"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Compute ISS Keypoints on ArmadilloMesh\n",
    "armadillo = o3d.data.ArmadilloMesh()\n",
    "mesh = o3d.io.read_triangle_mesh(armadillo.path)\n",
    "mesh.compute_vertex_normals()\n",
    "\n",
    "pcd = o3d.geometry.PointCloud()\n",
    "pcd.points = mesh.vertices\n",
    "\n",
    "tic = time.time()\n",
    "keypoints = o3d.geometry.keypoint.compute_iss_keypoints(pcd)\n",
    "toc = 1000 * (time.time() - tic)\n",
    "print(\"ISS Computation took {:.0f} [ms]\".format(toc))\n",
    "\n",
    "mesh.compute_vertex_normals()\n",
    "mesh.paint_uniform_color([0.5, 0.5, 0.5])\n",
    "keypoints.paint_uniform_color([1.0, 0.75, 0.0])\n",
    "o3d.visualization.draw_geometries([keypoints, mesh], front=[0, 0, -1.0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# This function is only used to make the keypoints look better on the rendering\n",
    "def keypoints_to_spheres(keypoints):\n",
    "    spheres = o3d.geometry.TriangleMesh()\n",
    "    for keypoint in keypoints.points:\n",
    "        sphere = o3d.geometry.TriangleMesh.create_sphere(radius=0.001)\n",
    "        sphere.translate(keypoint)\n",
    "        spheres += sphere\n",
    "    spheres.paint_uniform_color([1.0, 0.75, 0.0])\n",
    "    return spheres"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Compute ISS Keypoints on Standford BunnyMesh, changing the default parameters\n",
    "bunny = o3d.data.BunnyMesh()\n",
    "mesh = o3d.io.read_triangle_mesh(bunny.path)\n",
    "mesh.compute_vertex_normals()\n",
    "\n",
    "pcd = o3d.geometry.PointCloud()\n",
    "pcd.points = mesh.vertices\n",
    "\n",
    "tic = time.time()\n",
    "keypoints = o3d.geometry.keypoint.compute_iss_keypoints(pcd,\n",
    "                                                        salient_radius=0.005,\n",
    "                                                        non_max_radius=0.005,\n",
    "                                                        gamma_21=0.5,\n",
    "                                                        gamma_32=0.5)\n",
    "toc = 1000 * (time.time() - tic)\n",
    "print(\"ISS Computation took {:.0f} [ms]\".format(toc))\n",
    "\n",
    "mesh.compute_vertex_normals()\n",
    "mesh.paint_uniform_color([0.5, 0.5, 0.5])\n",
    "o3d.visualization.draw_geometries([keypoints_to_spheres(keypoints), mesh])"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Edit Metadata",
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}