Pileus Git - ~andy/gtk/blob - gdk-pixbuf/pixops/pixbuf-transform-math.ltx

   1 \documentclass{article}
   2
   3 \begin{document}
   4
   5 \title{Some image transform math}
   6 \author{Owen Taylor}
   7 \date{18 February 2003}
   8 \maketitle
   9
  10 \section{Basics}
  11
  12 The transform process is composed of three steps;
  13 first we reconstruct a continuous image from the
  14 source data \(A_{i,j}\):
  15 \[a(u,v) = \sum_{i = -\infty}^{\infty} \sum_{j = -\infty}^{\infty} A_{i,j}F\left( {u - i \atop v - j} \right) \]
  16 Then we transform from destination coordinates to source coordinates:
  17 \[b(x,y) = a\left(u(x,y) \atop v(x,y)\right)
  18          = a\left(t_{00}x + t_{01}y + t_{02} \atop t_{10}x + t_{11}y + t_{12} \right)\]
  19 Finally, we resample using a sampling function \(G\):
  20 \[B_{x_0,y_0} = \int_{-\infty}^{\infty}\int_{-\infty}^{\infty} b(x,y)G\left( {x - x_0 \atop y - y_0} \right) dxdy\]
  21 Putting all of these together:
  22 \[B_{x_0,y_0} =
  23 \int_{-\infty}^{\infty}\int_{-\infty}^{\infty}
  24 \sum_{i = -\infty}^{\infty} \sum_{j = -\infty}^{\infty} A_{i,j}
  25 F\left( {u(x,y) - i \atop v(x,y) - j} \right)
  26 G\left( {x - x_0 \atop y - y_0} \right) dxdy\]
  27 We can reverse the order of the integrals and the sums:
  28 \[B_{x_0,y_0} =
  29 \sum_{i = -\infty}^{\infty} \sum_{j = -\infty}^{\infty} A_{i,j}
  30 \int_{-\infty}^{\infty}\int_{-\infty}^{\infty}
  31 F\left( {u(x,y) - i \atop v(x,y) - j} \right)
  32 G\left( {x - x_0 \atop y - y_0} \right) dxdy\]
  33 Which shows that the destination pixel values are a linear combination of the
  34 source pixel values. But the coefficents depend on \(x_0\) and \(y_0\).
  35 To simplify this a bit, define:
  36 \[i_0 = \lfloor u(x_0,y_0) \rfloor = \lfloor {t_{00}x_0 + t_{01}y_0 + t_{02}} \rfloor \]
  37 \[j_0 = \lfloor v(x_0,y_0) \rfloor = \lfloor {t_{10}x_0 + t_{11}y_0 + t_{12}} \rfloor \]
  38 \[\Delta_u = u(x_0,y_0) - i_0 = t_{00}x_0 + t_{01}y_0 + t_{02} - \lfloor {t_{00}x_0 + t_{01}y_0 + t_{02}} \rfloor \]
  39 \[\Delta_v = v(x_0,y_0) - j_0 = t_{10}x_0 + t_{11}y_0 + t_{12} - \lfloor {t_{10}x_0 + t_{11}y_0 + t_{12}} \rfloor \]
  40 Then making the transforms \(x' = x - x_0\), \(y' = y - x_0\), \(i' = i - i_0\), \(j' = j - x_0\)
  41 \begin{eqnarray*}
  42 F(u,v) & = & F\left( {t_{00}x + t_{01}y + t_{02} - i \atop t_{10}x + t_{11}y + t_{12} - j} \right)\\
  43        & = & F\left( {t_{00}(x'+x_0) + t_{01}(y'+y_0) + t_{02} - (i'+i_0) \atop
  44                       t_{10}(x'+x_0) + t_{11}(y'+y_0) + t_{12} - (j'+j_0)} \right) \\
  45        & = & F\left( {\Delta_u + t_{00}x' + t_{01}y' - i' \atop
  46                       \Delta_v + t_{10}x' + t_{11}y' - j'} \right)
  47 \end{eqnarray*}
  48 Using that, we can then reparameterize the sums and integrals and
  49 define coefficients that depend only on \((\Delta_u,\Delta_v)\),
  50 which we'll call the \emph{phase} at the point \((x_0,y_0)\):
  51 \[
  52 B_{x_0,y_0} =
  53 \sum_{i = -\infty}^{\infty} \sum_{j = -\infty}^{\infty} A_{i_0+i,j_0+j} C_{i,j}(\Delta_u,\Delta_v)
  54 \]
  55 \[
  56 C_{i,j}(\Delta_u,\Delta_v) =
  57 \int_{-\infty}^{\infty}\int_{-\infty}^{\infty}
  58 F\left( {\Delta_u + t_{00}x + t_{01}y - i \atop
  59          \Delta_v + t_{10}x + t_{11}y - j} \right)
  60 G\left( {x \atop y} \right) dxdy
  61 \]
  62 \section{Separability}
  63 A frequent special case is when the reconstruction and sampling functions
  64 are of the form:
  65 \[F(u,v) = f(u)f(v)\]
  66 \[G(x,y) = g(x)g(y)\]
  67 If we also have a transform that is purely a scale and translation;
  68 (\(t_{10} = 0\), \(t_{01} = 0\)), then we can separate
  69 \(C_{i,j}(\Delta_u,\Delta_v)\) into the product of a \(x\) portion
  70 and a \(y\) portion:
  71 \[C_{i,j}(\Delta_u,\Delta_v) = c_{i}(\Delta_u) c_{j}(\Delta_v)\]
  72 \[c_{i}(\Delta_u) = \int_{-\infty}^{\infty} f(\Delta_u + t_{00}x - i)g(x)dx\]
  73 \[c_{j}(\Delta_v) = \int_{-\infty}^{\infty} f(\Delta_v + t_{11}y - j)g(y)dy\]
  74
  75 \section{Some filters}
  76 gdk-pixbuf provides 4 standard filters for scaling, under the names ``NEAREST'',
  77 ``TILES'', ``BILINEAR'', and ``HYPER''. All of turn out to be separable
  78 as discussed in the previous section.
  79 For ``NEAREST'' filter, the reconstruction function is simple replication
  80 and the sampling function is a delta function\footnote{A delta function is an infinitely narrow spike, such that:
  81 \[\int_{-\infty}^{\infty}\delta(x)f(x) = f(0)\]}:
  82 \[f(t) = \cases{1, & if \(0 \le t \le 1\); \cr
  83                 0, & otherwise}\]
  84 \[g(t) = \delta(t - 0.5)\]
  85 For ``TILES'', the reconstruction function is again replication, but we
  86 replace the delta-function for sampling with a box filter:
  87 \[f(t) = \cases{1, & if \(0 \le t \le 1\); \cr
  88                 0, & otherwise}\]
  89 \[g(t) = \cases{1, & if \(0 \le t \le 1\); \cr
  90                 0, & otherwise}\]
  91 The ``HYPER'' filter (in practice, it was originally intended to be
  92 something else) uses bilinear interpolation for reconstruction and
  93 a box filter for sampling:
  94 \[f(t) = \cases{1 - |t - 0.5|, & if \(-0.5 \le t \le 1.5\); \cr
  95                 0, & otherwise}\]
  96 \[g(t) = \cases{1, & if \(0 \le t \le 1\); \cr
  97                 0, & otherwise}\]
  98 The ``BILINEAR'' filter is defined in a somewhat more complicated way;
  99 the definition depends on the scale factor in the transform (\(t_{00}\)
 100 or \(t_{01}]\). In the \(x\) direction, for \(t_{00} < 1\), it is
 101 the same as for ``TILES'':
 102 \[f_u(t) = \cases{1, & if \(0 \le t \le 1\); \cr
 103                   0, & otherwise}\]
 104 \[g_u(t) = \cases{1, & if \(0 \le t \le 1\); \cr
 105                   0, & otherwise}\]
 106 but for \(t_{10} > 1\), we use bilinear reconstruction and delta-function
 107 sampling:
 108 \[f_u(t) = \cases{1 - |t - 0.5|, & if \(-0.5 \le t \le 1.5\); \cr
 109                   0, & otherwise}\]
 110 \[g_u(t) = \delta(t - 0.5)\]
 111 The behavior in the \(y\) direction depends in the same way on \(t_{11}\).
 112 \end{document}