Debian Codegraph @

y4mdenoise/implementation.html

raw
1 <html>
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
15 frames.
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
46 performance's sake.
47 <p><br>Table of contents:
48 <ul>
49 <li><a href="#Overview">Overview</a>
50 <li><a href="#Implementation">Implementation</a>
51 <ul>
52 <li><a href="#ImplementationSkipList">SkipList, Set</a>
53 <li><a href="#ImplementationRegion2D">Region2D, SetRegion2D,
54 BitmapRegion2D</a>
55 <li><a href="#ImplementationReferenceFrame">Pixel, ReferencePixel,
56 ReferenceFrame</a>
57 <li><a href="#ImplementationMotionSearcher">MotionSearcher,
58 SearchWindow, SearchBorder</a>
59 <ul>
60 <li><a href="#ImplementationMotionSearcherVersion1">Version 1</a>
61 <li><a href="#ImplementationMotionSearcherVersion2">Version 2</a>
62 </ul>
63 </ul>
64 <li><a href="#FutureExtensions">Future Extensions</a>
65 <!-- <li><a href="#XXX">XXX</a> -->
66 </ul>
67
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
93 rectangular).
94 <br>
95
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.
101
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 &amp; 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
117 the denoiser.
118 <p><tt>Set</tt> is much like STL's <tt>set</tt> class, except that it's
119 based on <tt>SkipList</tt>.
120
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.
138
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&lt;uint_8,1,int32_t&gt;</tt> and a color (i.e. CbCr) pixel
148 is <tt>Pixel&lt;uint8_t,2,int32_t&gt;</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.
164
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
249 pixel-group.
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
266 largest to smallest.
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
276 new-frame pixels.
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.
286
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
305 to try at the end.
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.
311
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.
319
320 <!--
321 <a name="ImplementationXXX"><h2>XXX</h2></a>
322 <p>
323 -->
324
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.
362
363 <p>Copyright (C) 2004-2009 by
364 <a href="mailto:[email protected]">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.
368 </body>
369 </html>