libs/gil/doc/html/_sources/image_processing/affine-region-detectors.rst.txt

   1 Affine region detectors
   2 -----------------------
   3
   4 What is being detected?
   5 ~~~~~~~~~~~~~~~~~~~~~~~
   6
   7 Affine region is basically any region of the image
   8 that is stable under affine transformations. It can be
   9 edges under affinity conditions, corners (small patch of an image)
  10 or any other stable features.
  11
  12 --------------
  13
  14 Available detectors
  15 ~~~~~~~~~~~~~~~~~~~
  16
  17 At the moment, the following detectors are implemented
  18
  19 -  Harris detector
  20
  21 -  Hessian detector
  22
  23 --------------
  24
  25 Algorithm steps
  26 ~~~~~~~~~~~~~~~
  27
  28 Harris and Hessian
  29 ^^^^^^^^^^^^^^^^^^
  30
  31 Both are derived from a concept called Moravec window. Lets have a look
  32 at the image below:
  33
  34 .. figure:: ./Moravec-window-corner.png
  35    :alt: Moravec window corner case
  36
  37    Moravec window corner case
  38
  39 As can be noticed, moving the yellow window in any direction will cause
  40 very big change in intensity. Now, lets have a look at the edge case:
  41
  42 .. figure:: ./Moravec-window-edge.png
  43    :alt: Moravec window edge case
  44
  45    Moravec window edge case
  46
  47 In this case, intensity change will happen only when moving in
  48 particular direction.
  49
  50 This is the key concept in understanding how the two corner detectors
  51 work.
  52
  53 The algorithms have the same structure:
  54
  55 1. Compute image derivatives
  56
  57 2. Compute Weighted sum
  58
  59 3. Compute response
  60
  61 4. Threshold (optional)
  62
  63 Harris and Hessian differ in what **derivatives they compute**. Harris
  64 computes the following derivatives:
  65
  66 ``HarrisMatrix = [(dx)^2, dxdy], [dxdy, (dy)^2]``
  67
  68 (note that ``d(x^2)`` and ``(dy^2)`` are **numerical** powers, not gradient again).
  69
  70 The three distinct terms of a matrix can be separated into three images,
  71 to simplify implementation. Hessian, on the other hand, computes second
  72 order derivatives:
  73
  74 ``HessianMatrix = [dxdx, dxdy][dxdy, dydy]``
  75
  76 **Weighted sum** is the same for both. Usually Gaussian blur
  77 matrix is used as weights, because corners should have hill like
  78 curvature in gradients, and other weights might be noisy.
  79 Basically overlay weights matrix over a corner, compute sum of
  80 ``s[i,j]=image[x + i, y + j] * weights[i, j]`` for ``i, j``
  81 from zero to weight matrix dimensions, then move the window
  82 and compute again until all of the image is covered.
  83
  84 **Response computation** is a matter of choice. Given the general form
  85 of both matrices above
  86
  87 ``[a, b][c, d]``
  88
  89 One of the response functions is
  90
  91 ``response = det - k * trace^2 = a * c - b * d - k * (a + d)^2``
  92
  93 ``k`` is called discrimination constant. Usual values are ``0.04`` -
  94 ``0.06``.
  95
  96 The other is simply determinant
  97
  98 ``response = det = a * c - b * d``
  99
 100 **Thresholding** is optional, but without it the result will be
 101 extremely noisy. For complex images, like the ones of outdoors, for
 102 Harris it will be in order of 100000000 and for Hessian will be in order
 103 of 10000. For simpler images values in order of 100s and 1000s should be
 104 enough. The numbers assume ``uint8_t`` gray image.
 105
 106 To get deeper explanation please refer to following **paper**:
 107
 108 `Harris, Christopher G., and Mike Stephens. "A combined corner and edge
 109 detector." In Alvey vision conference, vol. 15, no. 50, pp. 10-5244.
 110 1988. <http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.434.4816&rep=rep1&type=pdf>`__
 111
 112 `Mikolajczyk, Krystian, and Cordelia Schmid. "An affine invariant interest point detector." In European conference on computer vision, pp. 128-142. Springer, Berlin, Heidelberg, 2002. <https://hal.inria.fr/inria-00548252/document>`__
 113
 114 `Mikolajczyk, Krystian, Tinne Tuytelaars, Cordelia Schmid, Andrew Zisserman, Jiri Matas, Frederik Schaffalitzky, Timor Kadir, and Luc Van Gool. "A comparison of affine region detectors." International journal of computer vision 65, no. 1-2 (2005): 43-72. <https://hal.inria.fr/inria-00548528/document>`__
 115