libs/gil/doc/html/image_processing/affine-region-detectors.html

   1
   2
   3 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
   4   "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
   5 <html xmlns="http://www.w3.org/1999/xhtml">
   6   <head>
   7     <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
   8
   9     <title>Affine region detectors - Boost.GIL  documentation</title>
  10     <link rel="stylesheet" href="../_static/pygments.css" type="text/css" />
  11     <link rel="stylesheet" href="../_static/style.css" type="text/css" />
  12     <script type="text/javascript">
  13       var DOCUMENTATION_OPTIONS = {
  14           URL_ROOT:    '../',
  15           VERSION:     '',
  16           COLLAPSE_MODINDEX: false,
  17           FILE_SUFFIX: '.html'
  18       };
  19     </script>
  20     <script type="text/javascript" src="../_static/jquery.js"></script>
  21     <script type="text/javascript" src="../_static/underscore.js"></script>
  22     <script type="text/javascript" src="../_static/doctools.js"></script>
  23     <link rel="index" title="Index" href="../genindex.html" />
  24     <link rel="search" title="Search" href="../search.html" />
  25     <link rel="top" title="Boost.GIL  documentation" href="../index.html" />
  26     <link rel="up" title="Image Processing" href="index.html" />
  27     <link rel="next" title="IO extensions" href="../io.html" />
  28     <link rel="prev" title="Basics" href="basics.html" />
  29   </head>
  30   <body>
  31     <div class="header">
  32     <table border="0" cellpadding="7" cellspacing="0" width="100%" summary=
  33     "header">
  34       <tr>
  35         <td valign="top" width="300">
  36           <h3><a href="../index.html"><img
  37           alt="C++ Boost" src="../_static/gil.png" border="0"></a></h3>
  38         </td>
  39
  40         <td >
  41           <h1 align="center"><a href="../index.html"></a></h1>
  42         </td>
  43         <td>
  44       <div id="searchbox" style="display: none">
  45         <form class="search" action="../search.html" method="get">
  46           <input type="text" name="q" size="18" />
  47           <input type="submit" value="Search" />
  48           <input type="hidden" name="check_keywords" value="yes" />
  49           <input type="hidden" name="area" value="default" />
  50         </form>
  51       </div>
  52       <script type="text/javascript">$('#searchbox').show(0);</script>
  53         </td>
  54       </tr>
  55     </table>
  56     </div>
  57     <hr/>
  58     <div class="content">
  59     <div class="navbar" style="text-align:right;">
  60
  61
  62       <a class="prev" title="Basics" href="basics.html"><img src="../_static/prev.png" alt="prev"/></a>
  63       <a class="up" title="Image Processing" href="index.html"><img src="../_static/up.png" alt="up"/></a>
  64       <a class="next" title="IO extensions" href="../io.html"><img src="../_static/next.png" alt="next"/></a>
  65
  66     </div>
  67
  68   <div class="section" id="affine-region-detectors">
  69 <h1>Affine region detectors</h1>
  70 <div class="section" id="what-is-being-detected">
  71 <h2>What is being detected?</h2>
  72 <p>Affine region is basically any region of the image
  73 that is stable under affine transformations. It can be
  74 edges under affinity conditions, corners (small patch of an image)
  75 or any other stable features.</p>
  76 </div>
  77 <hr class="docutils" />
  78 <div class="section" id="available-detectors">
  79 <h2>Available detectors</h2>
  80 <p>At the moment, the following detectors are implemented</p>
  81 <ul class="simple">
  82 <li>Harris detector</li>
  83 <li>Hessian detector</li>
  84 </ul>
  85 </div>
  86 <hr class="docutils" />
  87 <div class="section" id="algorithm-steps">
  88 <h2>Algorithm steps</h2>
  89 <div class="section" id="harris-and-hessian">
  90 <h3>Harris and Hessian</h3>
  91 <p>Both are derived from a concept called Moravec window. Lets have a look
  92 at the image below:</p>
  93 <div class="figure" id="id1">
  94 <img alt="Moravec window corner case" src="../_images/Moravec-window-corner.png" />
  95 <p class="caption"><span class="caption-text">Moravec window corner case</span></p>
  96 </div>
  97 <p>As can be noticed, moving the yellow window in any direction will cause
  98 very big change in intensity. Now, lets have a look at the edge case:</p>
  99 <div class="figure" id="id2">
 100 <img alt="Moravec window edge case" src="../_images/Moravec-window-edge.png" />
 101 <p class="caption"><span class="caption-text">Moravec window edge case</span></p>
 102 </div>
 103 <p>In this case, intensity change will happen only when moving in
 104 particular direction.</p>
 105 <p>This is the key concept in understanding how the two corner detectors
 106 work.</p>
 107 <p>The algorithms have the same structure:</p>
 108 <ol class="arabic simple">
 109 <li>Compute image derivatives</li>
 110 <li>Compute Weighted sum</li>
 111 <li>Compute response</li>
 112 <li>Threshold (optional)</li>
 113 </ol>
 114 <p>Harris and Hessian differ in what <strong>derivatives they compute</strong>. Harris
 115 computes the following derivatives:</p>
 116 <p><code class="docutils literal"><span class="pre">HarrisMatrix</span> <span class="pre">=</span> <span class="pre">[(dx)^2,</span> <span class="pre">dxdy],</span> <span class="pre">[dxdy,</span> <span class="pre">(dy)^2]</span></code></p>
 117 <p>(note that <code class="docutils literal"><span class="pre">d(x^2)</span></code> and <code class="docutils literal"><span class="pre">(dy^2)</span></code> are <strong>numerical</strong> powers, not gradient again).</p>
 118 <p>The three distinct terms of a matrix can be separated into three images,
 119 to simplify implementation. Hessian, on the other hand, computes second
 120 order derivatives:</p>
 121 <p><code class="docutils literal"><span class="pre">HessianMatrix</span> <span class="pre">=</span> <span class="pre">[dxdx,</span> <span class="pre">dxdy][dxdy,</span> <span class="pre">dydy]</span></code></p>
 122 <p><strong>Weighted sum</strong> is the same for both. Usually Gaussian blur
 123 matrix is used as weights, because corners should have hill like
 124 curvature in gradients, and other weights might be noisy.
 125 Basically overlay weights matrix over a corner, compute sum of
 126 <code class="docutils literal"><span class="pre">s[i,j]=image[x</span> <span class="pre">+</span> <span class="pre">i,</span> <span class="pre">y</span> <span class="pre">+</span> <span class="pre">j]</span> <span class="pre">*</span> <span class="pre">weights[i,</span> <span class="pre">j]</span></code> for <code class="docutils literal"><span class="pre">i,</span> <span class="pre">j</span></code>
 127 from zero to weight matrix dimensions, then move the window
 128 and compute again until all of the image is covered.</p>
 129 <p><strong>Response computation</strong> is a matter of choice. Given the general form
 130 of both matrices above</p>
 131 <p><code class="docutils literal"><span class="pre">[a,</span> <span class="pre">b][c,</span> <span class="pre">d]</span></code></p>
 132 <p>One of the response functions is</p>
 133 <p><code class="docutils literal"><span class="pre">response</span> <span class="pre">=</span> <span class="pre">det</span> <span class="pre">-</span> <span class="pre">k</span> <span class="pre">*</span> <span class="pre">trace^2</span> <span class="pre">=</span> <span class="pre">a</span> <span class="pre">*</span> <span class="pre">c</span> <span class="pre">-</span> <span class="pre">b</span> <span class="pre">*</span> <span class="pre">d</span> <span class="pre">-</span> <span class="pre">k</span> <span class="pre">*</span> <span class="pre">(a</span> <span class="pre">+</span> <span class="pre">d)^2</span></code></p>
 134 <p><code class="docutils literal"><span class="pre">k</span></code> is called discrimination constant. Usual values are <code class="docutils literal"><span class="pre">0.04</span></code> -
 135 <code class="docutils literal"><span class="pre">0.06</span></code>.</p>
 136 <p>The other is simply determinant</p>
 137 <p><code class="docutils literal"><span class="pre">response</span> <span class="pre">=</span> <span class="pre">det</span> <span class="pre">=</span> <span class="pre">a</span> <span class="pre">*</span> <span class="pre">c</span> <span class="pre">-</span> <span class="pre">b</span> <span class="pre">*</span> <span class="pre">d</span></code></p>
 138 <p><strong>Thresholding</strong> is optional, but without it the result will be
 139 extremely noisy. For complex images, like the ones of outdoors, for
 140 Harris it will be in order of 100000000 and for Hessian will be in order
 141 of 10000. For simpler images values in order of 100s and 1000s should be
 142 enough. The numbers assume <code class="docutils literal"><span class="pre">uint8_t</span></code> gray image.</p>
 143 <p>To get deeper explanation please refer to following <strong>paper</strong>:</p>
 144 <p><a class="reference external" href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.434.4816&amp;rep=rep1&amp;type=pdf">Harris, Christopher G., and Mike Stephens. &#8220;A combined corner and edge
 145 detector.&#8221; In Alvey vision conference, vol. 15, no. 50, pp. 10-5244.
 146 1988.</a></p>
 147 <p><a class="reference external" href="https://hal.inria.fr/inria-00548252/document">Mikolajczyk, Krystian, and Cordelia Schmid. &#8220;An affine invariant interest point detector.&#8221; In European conference on computer vision, pp. 128-142. Springer, Berlin, Heidelberg, 2002.</a></p>
 148 <p><a class="reference external" href="https://hal.inria.fr/inria-00548528/document">Mikolajczyk, Krystian, Tinne Tuytelaars, Cordelia Schmid, Andrew Zisserman, Jiri Matas, Frederik Schaffalitzky, Timor Kadir, and Luc Van Gool. &#8220;A comparison of affine region detectors.&#8221; International journal of computer vision 65, no. 1-2 (2005): 43-72.</a></p>
 149 </div>
 150 </div>
 151 </div>
 152
 153
 154     <div class="navbar" style="text-align:right;">
 155
 156
 157       <a class="prev" title="Basics" href="basics.html"><img src="../_static/prev.png" alt="prev"/></a>
 158       <a class="up" title="Image Processing" href="index.html"><img src="../_static/up.png" alt="up"/></a>
 159       <a class="next" title="IO extensions" href="../io.html"><img src="../_static/next.png" alt="next"/></a>
 160
 161     </div>
 162     </div>
 163     <div class="footer" role="contentinfo">
 164       Last updated on 2019-12-10 00:12:10.
 165       Created using <a href="http://sphinx-doc.org/">Sphinx</a> 1.5.6.
 166     </div>
 167   </body>
 168 </html>