← Back to branch summary

~ubuntu-branches/ubuntu/maverick/ekiga/maverick

« back to all changes in this revision

Viewing changes to lib/pixops/pixbuf-transform-math.ltx

  • Committer: Bazaar Package Importer
  • Author(s): Eugen Dedu, Eugen Dedu, Loic Minier
  • Date: 2008-09-27 10:00:00 UTC
  • mfrom: (1.1.8 upstream)
  • mto: (1.4.1 squeeze)
  • mto: This revision was merged to the branch mainline in revision 38.
  • Revision ID: james.westby@ubuntu.com-20080927100000-l5k5werb6czr5b3h
Tags: 3.0.1-1
http://bugs.debian.org/500089
http://bugs.debian.org/488199
http://bugs.debian.org/467212
http://bugs.debian.org/440159
http://bugs.debian.org/412604
http://bugs.debian.org/505536
http://bugs.debian.org/505535
[ Eugen Dedu ]
* New version.  (Closes: #500089).
* Add our own changelog file in /usr/share/doc.
* Remove gnomemeeting transitional package.
* Discover new interfaces.  (Closes: #488199).
* Compile with dbus support.  (Closes: #467212).
* Numeric keypad inserts digits at correct position.  (Closes: #440159).
* Use libnotify upon call.  (Closes: #412604).
* Symlink identical GNOME help files, to reduce size.  (Closes: #505536).
* Explicitely build-depends on a few dev packages, even if they were
  pulled out anyway by the other dependencies.

[ Loic Minier ]
* Use clean:: instead of clean: in rules.
* Don't disable Uploaders: generation for control.in -> control generation
  in rules.
* Fix some tabs which were size 4 anyway.
* Generate a PO template during build by calling intltool-update -p in
  install; thanks Ubuntu and Martin Pitt; closes: #505535.
* Also let the -dbg depend on ${misc:Depends}.
* Cleanup rules; in particular, use dpkg-parsechangelog and honor
  distclean/clean failures, remove old clean rules, commented out stuff,
  gtk-only stuff.
* Pass -s to dh_* in binary-arch.
* Use debian/*.links and debian/*.manpages instead of symlink manually or
  passing files to dh_installman.
* Use ftp.gnome.org in copyright.
* Switch to quilt and fix target deps in the process; build-dep on quilt
  instead of dpatch; rename news.dpatch to 00_news.patch and refresh;
  replace 00list with series.
* Install autotools-dev config.guess and .sub after patching.

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/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}
 
 
b'\\ No newline at end of file'