[IPOL discuss] possible bug in NL-means (ipol)

[Mauricio Delbracio]

Dear all,

I may have found a bug in the NL-means IPOL implementation. The
problem is due to parallelism, particularly when updating shared
values by more than one threading (race condition, race bug).

In NL-means this happens in the filtered image (fpO) which is shared
and updated by all the threads. The image is decomposed in overlapped
patches that are denoised each of them separately, and then they are
aggregated in the final image (fpO). The problem is that when the
update of fpO  takes place, may happen that two overlapped patches
running in different threads try to update the same memory address.

This not happen very frequently, since it is very unlikely that two
overlapped patches take the same amount of time to arrive at that part
of the code...The probability of this to happen increases if the
search block (the block where similar patches are searched) is very
small.

To eliminate the bug, the way I found (a.k.a the easy way) is to
enclose the writing of fpO in a "omp critical" block. This means that
only one thread at at a time can write in fpO (there's a loss in
execution time, probably there other ways of avoiding this problem,
e.g. by using local memory blocks and then update at the end? i don't
know I'm not really familiar with OpenMP).

I attach a possible patch to libdenoising.cpp.

The block of code I refer is in libdenoising.cpp between lines 219-238
http://www.ipol.im/pub/art/2011/bcm_nlm/srcdoc/libdenoising_8cpp_source.html

I also attach an image showing the effect of the bug (parameters
bloc=1, win=1) and some pixels that I manually marked.

I appreciate any feedback (there are surely many OpenMP experts  in
this mailing-list), so let me know what you think.

best
m
-------------- next part --------------
A non-text attachment was scrubbed...
Name: denoisedN_std3_orig_lab.png
Type: image/png
Size: 450157 bytes
Desc: not available
URL: <https://tools.ipol.im/mailman/archive/discuss/attachments/20121014/ae0da67b/attachment.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: nlmeansC.patch
Type: application/octet-stream
Size: 997 bytes
Desc: not available
URL: <https://tools.ipol.im/mailman/archive/discuss/attachments/20121014/ae0da67b/attachment.obj>