2
<title>Design and implementation of the new denoiser</title>
3
<body bgcolor=ffffff text=000000 link=ff0000 vlink=ff00ff alink=33ff00>
4
<center><h1>Design and implementation of the new denoiser</h1></center>
5
<p>In theory, the design of the denoiser is pretty simple; getting it
6
to perform was the hard part.
7
<p>It maintains a list of the last several frames, called <i>reference
8
frames</i>. Each reference frame is composed of <i>reference
9
pixels</i>, which accumulate the values of several pixels.
10
Every time a pixel in one frame is proven to be a moved instance of a
11
pixel in another frame, the reference-pixel incorporates its value,
12
and produces an average value for the pixel. The oldest reference
13
frame, therefore, gets a pretty good idea of the real value of every
14
pixel, but of course output is delayed by the number of reference
16
<p>It compares every pixel in the current frame with all pixels
17
in the previous frame, within a given search-radius, and any pixels
18
that are equal within the given error tolerance are assumed to be the
19
same pixel. It builds contiguous regions of matched pixels, with
20
the motion vector that's common to the region.
21
<p>If there are too many matches for a particular area of the image, or
22
if the largest contiguous match in the area is too large, it's applied
23
to the image right then, and then searching continues. Applying a
24
region means to flood-fill the region (to make it the largest size
25
possible, and to flesh out its borders to pixel accuracy), then
26
hooking up the corresponding reference-frame pixels to the new frame
27
at their new location, and incorporating the values of all the new
28
pixels into the corresponding reference pixels. Doing this before
29
the end of searching the frame means the affected areas don't have
30
to be part of the search any more, helping to reduce the amount of
31
work needed to search the rest of the frame.
32
<p>At the end of the frame, matches are applied to the new frame, from
33
the largest to the smallest, discounting any areas that have
34
already been resolved. Any new-frame pixels not resolved by now
35
are considered to be new information, and a new reference-pixel is
36
generated for each one.
37
<p>The search is not actually done one pixel at a time; it's done in
38
terms of pixel groups. An entire pixel-group has to match for any
39
match to be found, but all possible pixel-groups are tested (i.e. all
40
possible overlaps are checked). Using pixel-groups helps to establish
41
a minimum standard for what may be considered a match, in order to
42
avoid finding lots of really small (and really useless) matches.
43
The flood-fill still extends the matches out to pixel accuracy,
44
so the only details that can't be found by motion-detection are the
45
ones smaller than a pixel-group, which is not a bad sacrifice for
47
<p><br>Table of contents:
49
<li><a href="#Overview">Overview</a>
50
<li><a href="#Implementation">Implementation</a>
52
<li><a href="#ImplementationSkipList">SkipList, Set</a>
53
<li><a href="#ImplementationRegion2D">Region2D, SetRegion2D,
55
<li><a href="#ImplementationReferenceFrame">Pixel, ReferencePixel,
57
<li><a href="#ImplementationMotionSearcher">MotionSearcher,
58
SearchWindow, SearchBorder</a>
60
<li><a href="#ImplementationMotionSearcherVersion1">Version 1</a>
61
<li><a href="#ImplementationMotionSearcherVersion2">Version 2</a>
64
<li><a href="#FutureExtensions">Future Extensions</a>
65
<!-- <li><a href="#XXX">XXX</a> -->
68
<a name="Overview"><h1>Overview</h1>
69
<p><tt>main.c</tt> parses command-line options and the YUV stream header.
70
<tt>newdenoise.cc</tt> converts between YUV format and the denoiser's
71
internal format, and calls the denoiser. <tt>MotionSearcher.hh</tt> is
72
the denoiser's top-level file. <tt>SearchWindow.hh</tt> and
73
<tt>SearchBorder.hh</tt> are two high-level pieces of the denoiser that
74
were broken out into their own classes, for use in other contexts.
75
<tt>ReferenceFrame.hh</tt> contains the definitions for pixels,
76
reference pixels, and reference frames.
77
<tt>Region2D.hh</tt> is the base class for 2-dimensional region classes;
78
<tt>SetRegion2D.hh</tt> implements a region using a Set of horizontal
79
extents, and <tt>BitmapRegion2D.hh</tt> uses an array of integers to
80
implement a bitmap. <tt>Set.hh</tt> is much like the STL "set" class,
81
except that it's based on <tt>SkipList.hh</tt>. <tt>Allocator.hh</tt>,
82
<tt>DoublyLinkedList.hh</tt>, <tt>Limits.hh</tt>, <tt>Status_t.h</tt>, and
83
<tt>TemplateLib.hh</tt> contain other basic definitions, most of which
84
should be standardly available; I'm just not sure they're standardly
85
available on all supported platforms.
86
<p>The denoiser classes are highly templated and highly reconfigurable;
87
<tt>newdenoise.cc</tt> uses them in a way suited to YUV420P video.
88
Intensity pixels are one 8-bit unsigned integer, color pixels are
89
two 8-bit unsigned integers, intensity pixel-groups are 4x2, color
90
pixel-groups are 2x2, intensity is denoised separately from color, and
91
the search-radius used for color is proportional to the relative size
92
of the intensity and color planes (and may, in effect, be
96
<a name="Implementation"><h1>Implementation</h1></a>
97
<p><tt>newdenoise.cc</tt> gives a good top-level view of how to use the
98
denoiser for YUV420P video. Although the top-level class of the
99
denoiser is <tt>MotionSearcher</tt>, a small army of classes is
100
responsible for implementing all the necessary pieces.
102
<a name="ImplementationSkipList"><h2>SkipList, Set</h2></a>
103
<p><tt>SkipList</tt> is a highly optimized version of the famous
104
probabilistically-balanced logarithmic-complexity sorted list
105
structure. Skip lists are well-described in other documents. Note
106
that this skip-list uses the "fix the dice" and "search finger"
107
extensions described in the literature, and its p value is
108
<sup>1</sup>/e, which maximizes speed & causes nodes to have an
109
average of 1.71 forward pointers. (A tree node would have to have
110
2 pointers, one for left and one for right, so a skip-list is more
111
space-efficient than a tree structure also.)
112
<p>One big advantage of skip-lists over tree structures, given the way
113
the denoiser uses them, is that iterator forward/backward operations
114
are small-constant complexity; they're implemented by a single pointer
115
dereference. The typical tree-structure iterator forward/backward is
116
logarithmic. Iterator forward/backward is used constantly throughout
118
<p><tt>Set</tt> is much like STL's <tt>set</tt> class, except that it's
119
based on <tt>SkipList</tt>.
121
<a name="ImplementationRegion2D"><h2>Region2D, SetRegion2D,
122
BitmapRegion2D</h2></a>
123
<p><tt>SetRegion2D</tt> was the first region class written for the
124
denoiser; later, <tt>Region2D</tt> and <tt>SetRegion2D</tt> were split
125
into two classes, and <tt>BitmapRegion2D</tt> was made a subclass of
126
<tt>Region2D</tt>. It was not a perfect separation, and <tt>Region2D</tt>
127
remains a sketch of what I'd like to see, rather than a completed
128
product. I could solve its problem using virtual methods, but that
129
would prevent a lot of function-inlining from happening, and for
130
performance reasons I don't want to do that.
131
<p><tt>SetRegion2D</tt> uses <tt>Set</tt> to implement regions as a set of
132
horizontal extents, i.e. as y/x-start/x-end triplets. Quite a bit of
133
work went into writing efficient union/subtraction methods.
134
<p><tt>BitmapRegion2D</tt> uses an array of integers, treated like a bit
135
field, to implement regions. It's faster to use them in some cases,
136
though they're a lot less memory-efficient than <tt>SetRegion2D</tt>,
137
and have to be created with a maximum size.
139
<a name="ImplementationReferenceFrame"><h2>Pixel, ReferencePixel,
140
ReferenceFrame</h2></a>
141
<p>The <tt>Pixel</tt> class is templated with a numeric type for storing
142
pixel values, the number of dimensions in the pixel's value, and
143
a numeric type to use when doing tolerance calculations. The rule of
144
thumb is, the tolerance type should be able to hold the value of two
145
pixel-value types multiplied together.
146
<p>For YUV420P video, a Y pixel is
147
<tt>Pixel<uint_8,1,int32_t></tt> and a color (i.e. CbCr) pixel
148
is <tt>Pixel<uint8_t,2,int32_t></tt>.
149
<p>The <tt>Pixel</tt> class contains methods to get and set the value of
150
pixels, and to compare two pixels within a given tolerance. It also
151
contains methods to generate tolerance values from integers, in case
152
the pixel type has special rules. (For instance, the tolerance value
153
for a color pixel is the square of its integer counterpart, since CbCr
154
color is 2-dimensional.)
155
<p>The <tt>ReferencePixel</tt> is templated much like the <tt>Pixel</tt>
156
class. It holds a sum of pixel values, and the number of pixel values
157
summed so far. It also counts the number of reference-frames that
158
point to it. It's intended to represent a single pixel that's found
159
to exist over several frames, and to produce an average value for the
160
pixel, so as to smooth away errors.
161
<p>The <tt>ReferenceFrame</tt> is a rectangular array of
162
<tt>ReferencePixel</tt>s, representing each frame and the parts of the
163
image that it has in common with other frames.
165
<a name="ImplementationMotionSearcher"><h2>MotionSearcher,
166
SearchWindow, SearchBorder</h2></a>
167
<p>OK, so much for the easy part.
168
<p><tt>MotionSearcher</tt> maintains a circular list of
169
<tt>ReferenceFrame</tt>s. To make space for a new frame, the oldest
170
frame is returned to the client.
171
<p><tt>AddFrame()</tt> is responsible for processing new frames. It does
172
so in several stages. First, it looks for pixels that haven't moved,
173
i.e. new pixels whose corresponding reference-pixels are within the
174
error tolerance. That resolves most of the average frame.
175
<p>Next, it detects moved areas, i.e. parts of the new frame that match
176
parts of the previous frame except that they've moved.
177
<p>It could iterate through the frame in any order, but to keep the
178
implementation of <tt>SearchWindow</tt> and <tt>SearchBorder</tt> simple
179
and efficient, it iterates through the frame in a zigzag pattern,
180
i.e. starting at the upper-left corner, it moves right to the edge,
181
then down a line, then left to the edge, then down a line, and so on
182
to the end of the frame.
183
<p>The search-window consists of the reference-frame's pixels,
184
partitioned into search-window cells. Each cell contains a
185
pixel-group (i.e. a rectangular array of pixels, containing the
186
minimum pixel pattern that can be searched for). The pixel-groups
187
in each cell overlap other cells; although the motion-search is done
188
in terms of pixel-groups, it still looks at all all possible
189
combinations of pixels that could form a pixel-group.
190
<p>The pixel-sorter is a tree structure that partitions pixel-groups
191
(actually, search-window cells, which contain a pixel-group).
192
The total number of dimensions of a pixel-group is the number of
193
pixels in the group, times the dimension of a pixel. For the
194
YUV420 implementation, 4x2 pixel-groups are used for intensity pixels,
195
which consist of 1 dimension, for a total of 8, and 2x2 pixel groups
196
are used for color pixels, which consist of 2 dimensions, again for a
197
total of 8. Partitioning n dimensions requires 2<sup>n</sup>
198
branches per tree node; in this example, that's 256. (So if the
199
pixel-sorter tree is well-balanced, then descending to a child branch
200
cuts out all but <sup>1</sup>/256 of the remaining pixel-groups, which
201
is supposed to make searching for matching pixel-groups very efficient.)
202
Search-window cells are inserted into the pixel-sorter tree, and
203
descend into child branches based on their value. But if any of the
204
pixel-group's pixel dimension values are within the error tolerance of
205
the split-point for that dimension in the current pixel-sorter branch
206
node, then that pixel-group won't fit neatly into any of the children
207
nodes, and thus the search-window cell has to stay at that level of
208
the tree. (Alternately, a copy of it could be placed in multiple
209
children, but this design opts not to do that.) Each pixel-sorter
210
branch node maintains a doubly-linked list of search-window cells that
211
are attached to it. As an optimization, once a search-window cell is
212
inserted into the pixel-sorter, that result is used for the rest of
213
the frame, as the search-window cell is added to and removed from the
214
pixel-sorter, depending on whether that search-window cell is within
215
the search radius of the current new-frame pixel-group.
216
<p>To look for matches between the current pixel-group from the new
217
frame, and all pixel-groups from the previous frame within the search
218
radius, one just matches the current pixel-group to every
219
search-window cell attached to the pixel-sorter branch nodes, and
220
descend the tree according to the new pixel-group's values. (One
221
optimization is possible here: If the search-window cell was forced
222
to stop at that level of the pixel-sorter because one of its pixel
223
values was within the tolerance of the split value of that
224
pixel-sorter branch node, and none of the current pixel-group's
225
pixel values are within twice the tolerance of the split value
226
of that pixel-sorter branch node, then we can save time and avoid the
227
comparison, for no search-window cell that had to stop at that level
228
could possibly intersect the new pixel-group. This especially helps
229
in the presence of low error thresholds.)
230
<p>As matches are found, the search-border builds contiguous regions of
231
matches that all have the same motion-vector. (The "border" is the
232
border between the searched area and the not-yet-searched area.)
233
It's designed to move through the regions of matches in a zigzag
234
pattern, and constantly maintain a list of all regions that would
235
be contiguous with the current new-frame pixel-group. When a match
236
is found, all such regions with the same motion-vector are now
237
contiguous, once the current pixel-group's area is added.
238
<p>The search-border is implemented by sets of startpoints/endpoints.
239
Every horizontal extent (that could potentially intersect a
240
new-frame pixel-group) of every region under construction along the
241
border is represented in the set of startpoints/endpoints. The
242
search-border also has two arrays of set iterators, one for
243
startpoints, one for endpoints. As the search zig-zags across the
244
new frame, these two arrays of iterators keep track of all regions
245
that will be contiguous with the current new-frame pixel-group, and
246
all regions that are no longer contiguous with the current new-frame
247
pixel-group; by doing this, it's very efficient to maintain the set
248
of border regions that would be contiguous with the current new-frame
250
<p>The general idea is to analyze the entire frame like this, then run
251
through the found regions from largest to smallest, and apply them to
252
the new frame. This can be a lot of data, too much in fact. To
253
limit the search to a reasonable complexity, two throttles exist --
254
one on the number of matches in the area of the current pixel-group,
255
and one on the size of the the largest match in the area of the
256
current pixel-group. If there are too many regions in the area,
257
or if the biggest region in the area is too large, then the best
258
region found so far is chosen, all other regions in the area are
259
thrown away, and that best region is applied to the new frame right
260
then. This will eliminate pixel-groups from consideration in the
261
search-window and pixel-sorter, which will save time in the search.
262
This will also resolve new-frame pixels; only pixel-groups that
263
contain nothing but unresolved pixels can be searched for in the
264
pixel-sorter, which also saves time in the remainder of the search.
265
Only after the entire frame is analyzed are regions applied from
267
<p>Before a match is applied to the new frame, it's flood-filled in
268
order to resolve its entire extent. Searching is done in terms of
269
pixel-groups, so it won't be able to find any detail that's smaller
270
than a pixel-group. Also, the region may not have been completed, if
271
it was chosen because a throttle value was exceeded, so its full
272
extent is not known. Plus, parts of that match may have already
273
been resolved. The flood-fill takes care of all of these situations.
274
<p>Any pixels not found by the above searches are declared to be new
275
information, and new reference-pixels are allocated for all such
277
<p>The whole point of this design is to use as many high-level-design
278
features as possible to reduce the amount of work necessary to perform
279
the job. It attempts to accomplish this with a heavy reliance on
280
data structures over more mathematical algorithms, a drive to
281
locate sub-linear/sub-quadratic algorithms for common tasks (e.g.
282
the pixel-sorter tree, which reduced quadratic to logarithmic, and
283
the iterator arrays in the search-border, which reduced logarithmic
284
to small-constant), and to use data structure design to understand
285
the problem in ways that directly lead to efficient implementations.
287
<a name="ImplementationMotionSearcherVersion1"><h3>Version 1</h3></a>
288
<p>The above discussion describes the intent of the first version of
289
the denoiser (which I'm calling version 0). However, the very last
290
high-level change I made to it, right before releasing it under GPL,
291
was defective! In effect, the match-count throttle was always 1, and
292
the best match was applied every pixel-group! It was intended
293
to be a performance increase, and it was, but obviously it broke the
294
code...except that this bugged change also vastly increased the
295
quality! There is every reason in the world to believe that such a
296
bug should have broken the denoiser's quality, except that it didn't.
297
What a stroke of luck!
298
<p>I decided to take the implications of this accidental discovery to
299
the next logical level. Before, I wouldn't have believed that the
300
best match could be found without amassing a large list of
301
possibilities from several pixel-group searches. Now, each match
302
found is flood-filled, and the first one to exceed the match-size
303
throttle is applied to the image right then and there, and all other
304
possibilities aren't considered. So there is no big list of regions
306
<p>This version performed better than the bugged version, which is
307
surprising enough, but the quality was vastly improved too.
308
<p>Parallel processing was added at this time too. Color can be
309
denoised in a thread separate from intensity denoising, and
310
reading/writing frames can be moved into separate threads too.
312
<a name="ImplementationMotionSearcherVersion2"><h3>Version 2</h3></a>
313
<p>If match-size-throttling is in use (which is usually is), now it
314
picks the largest such match, instead of the first match that's larger
315
than the throttle size. This led to a pretty serious increase in quality!
316
<p>Parallel processing was modified so that the reader/writer threads can be
317
used independently of the denoiser threads. This may not be very useful,
318
but there was no good reason to prevent it.
321
<a name="ImplementationXXX"><h2>XXX</h2></a>
325
<a name="FutureExtensions"><h1>Future Extensions</h1></a>
326
<p>The motion-detector is highly parallel, and a better multi-threaded
327
version should be written. So far, color and intensity can be
328
analyzed separately. But a thread could conceivably denoise one half of
329
the remaining area of an image plane. The pixel-sorter would have to
330
become its own class for this to work, since there'd now be more than
331
one per search-window, and the search-window would have to keep
332
pixel-sorters from colliding with each other (i.e. the areas being
333
searched by each can't overlap). Also, depending on how efficient
334
the thread-synchronization methods are, the pixel-sorter could feed
335
results to the flood-filling stage. Perhaps both approaches can be
336
taken. Anything that allows the denoiser to fill up processors is
337
probably worth trying.
338
<p>The motion-detector should probably be able to find matches in
339
more than one previous frame. I'd probably want to avoid later-frame
340
matches that occur in earlier frames, for efficiency's sake.
341
<p>The search-border should allow the insertion of new regions. It
342
would need a method, implemented somewhat like <tt>AddNewMatch()</tt>,
343
to generate a startpoint/endpoint for every horizontal extent in the
344
region that intersected the border area. This could be used to make
345
a <tt>ChooseBestActiveRegion()</tt> that eliminated flood-filled areas
346
from the other regions on the border and then put those regions back
347
into the border. I don't know if this would speed things up, though.
348
<p>I think the search-border can be used to implement removal of
349
transient phenomena, e.g. film lint/scratches, LaserDisc rot,
350
analog-broadcast static, etc. After the new frame has had motion
351
detection run on it, look at the 2nd-to-oldest frame, and build
352
contiguous regions of pixels that have the same reference count.
353
(Film lint/scratches will be limited to 1 reference count; I think
354
LaserDisc rot can extend over several frames.) If a region has
355
the right shape and the expected contents for a known sort of
356
artifact, it's declared to be an instance of that artifact, and a
357
blend involving the next/previous frame is used to generate the values
358
of pixels affected by the artifact. We'll probably want to take the
359
result of motion-detection into account too.
360
<p>I think the search-window could replace the radius-search in
361
yuvmedianfilter. It could even do motion-detection for mpeg2enc.
363
<p>Copyright (C) 2004-2009 by
364
<a href="mailto:ulatec@users.sourceforge.net">Steven Boswell</a>.
365
All rights reserved, and all that stuff.
366
<br>Released to the public under the GNU General Public License v2.
367
See the file COPYING for more information.
added
removed
y4mdenoise/implementation.html
