1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
|
*** General notes about rounding
Suppose a function is sampled at positions [k + o] where k is an
integer and o is a fractional offset 0 <= o < 1.
To round a value to the nearest sample, breaking ties by rounding up,
we can do this:
round(x) = floor(x - o + 0.5) + o
That is, first subtract o to let us pretend that the samples are at
integer coordinates, then add 0.5 and floor to round to nearest
integer, then add the offset back in.
To break ties by rounding down:
round(x) = ceil(x - o - 0.5) + o
or if we have an epsilon value:
round(x) = floor(x - o + 0.5 - e) + o
To always round *up* to the next sample:
round_up(x) = ceil(x - o) + o
To always round *down* to the previous sample:
round_down(x) = floor(x - o) + o
If a set of samples is stored in an array, you get from the sample
position to an index by subtracting the position of the first sample
in the array:
index(s) = s - first_sample
*** Application to pixman
In pixman, images are sampled with o = 0.5, that is, pixels are
located midways between integers. We usually break ties by rounding
down (i.e., "round towards north-west").
-- NEAREST filtering:
The NEAREST filter simply picks the closest pixel to the given
position:
round(x) = floor(x - 0.5 + 0.5 - e) + 0.5 = floor (x - e) + 0.5
The first sample of a pixman image has position 0.5, so to find the
index in the pixel array, we have to subtract 0.5:
floor (x - e) + 0.5 - 0.5 = floor (x - e).
Therefore a 16.16 fixed-point image location is turned into a pixel
value with NEAREST filtering by doing this:
pixels[((y - e) >> 16) * stride + ((x - e) >> 16)]
where stride is the number of pixels allocated per scanline and e =
0x0001.
-- CONVOLUTION filtering:
A convolution matrix is considered a sampling of a function f at
values surrounding 0. For example, this convolution matrix:
[a, b, c, d]
is interpreted as the values of a function f:
a = f(-1.5)
b = f(-0.5)
c = f(0.5)
d = f(1.5)
The sample offset in this case is o = 0.5 and the first sample has
position s0 = -1.5. If the matrix is:
[a, b, c, d, e]
the sample offset is o = 0 and the first sample has position s0 =
-2.0. In general we have
s0 = (- width / 2.0 + 0.5).
and
o = frac (s0)
To evaluate f at a position between the samples, we round to the
closest sample, and then we subtract the position of the first sample
to get the index in the matrix:
f(t) = matrix[floor(t - o + 0.5) + o - s0]
Note that in this case we break ties by rounding up.
If we write s0 = m + o, where m is an integer, this is equivalent to
f(t) = matrix[floor(t - o + 0.5) + o - (m + o)]
= matrix[floor(t - o + 0.5 - m) + o - o]
= matrix[floor(t - s0 + 0.5)]
The convolution filter in pixman positions f such that 0 aligns with
the given position x. For a given pixel x0 in the image, the closest
sample of f is then computed by taking (x - x0) and rounding that to
the closest index:
i = floor ((x0 - x) - s0 + 0.5)
To perform the convolution, we have to find the first pixel x0 whose
corresponding sample has index 0. We can write x0 = k + 0.5, where k
is an integer:
0 = floor(k + 0.5 - x - s0 + 0.5)
= k + floor(1 - x - s0)
= k - ceil(x + s0 - 1)
= k - floor(x + s0 - e)
= k - floor(x - (width - 1) / 2.0 - e)
And so the final formula for the index k of x0 in the image is:
k = floor(x - (width - 1) / 2.0 - e)
Computing the result is then simply a matter of convolving all the
pixels starting at k with all the samples in the matrix.
--- SEPARABLE_CONVOLUTION
For this filter, x is first rounded to one of n regularly spaced
subpixel positions. This subpixel position determines which of n
convolution matrices is being used.
Then, as in a regular convolution filter, the first pixel to be used
is determined:
k = floor (x - (width - 1) / 2.0 - e)
and then the image pixels starting there are convolved with the chosen
matrix. If we write x = xi + frac, where xi is an integer, we get
k = xi + floor (frac - (width - 1) / 2.0 - e)
so the location of k relative to x is given by:
(k + 0.5 - x) = xi + floor (frac - (width - 1) / 2.0 - e) + 0.5 - x
= floor (frac - (width - 1) / 2.0 - e) + 0.5 - frac
which means the contents of the matrix corresponding to (frac) should
contain width samplings of the function, with the first sample at:
floor (frac - (width - 1) / 2.0 - e) + 0.5 - frac
This filter is called separable because each of the k x k convolution
matrices is specified with two k-wide vectors, one for each dimension,
where each entry in the matrix is computed as the product of the
corresponding entries in the vectors.
|
