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

[Jean-Michel Morel]

So this is our first bug in a published code in IPOL. Since the published
code cannot be changed, we will have to publish the erratum and to change
the demo code.


On Sun, Oct 14, 2012 at 6:14 PM, Miguel Colom <
Miguel.Colom at cmla.ens-cachan.fr> wrote:

> Mauricio and I have done the tests in the same image and we both get the
> same problem with the current code. When we add our solution, the problem
> is solved.
>
> To show the problem clearly, I've made that the noise generator gives
> exactly the same noise values, so the difference between the images are
> caused by the algorithm, not by the noise.
>
> I've uploaded a version of the output image (sigma=3, block=win=1) using
> the current implementation (denoised_err.png) and the same with the
> corrected code (denoised_corr.png). You can see the bad pixels. One of them
> is near the third antenna, for example. The image can be downloaded here
> for comparison: http://dev.ipol.im/~colom/bad_**pixels/<http://dev.ipol.im/~colom/bad_pixels/>
>
> Mauricio has also done his own tests with the same parameters and he
> obtains similar results (bad pixels in the original code and without them
> with our modification).
> His images can be downloaded from here: http://dev.ipol.im/~mdelbra/**bug/<http://dev.ipol.im/~mdelbra/bug/>
>
> Best,
> Miguel
>
> Quoting Jean-Michel Morel <Jean-Michel.Morel at cmla.ens-**cachan.fr<Jean-Michel.Morel at cmla.ens-cachan.fr>
> >:
>
>  Can you test it on the same image?
>> Best,
>> JM
>>
>> On Sun, Oct 14, 2012 at 5:29 PM, Miguel Colom <
>> Miguel.Colom at cmla.ens-cachan.**fr <Miguel.Colom at cmla.ens-cachan.fr>>
>> wrote:
>>
>>  Dear all,
>>> Mauricio and I have found a way to modify the code to avoid the critical
>>> sections (SO mutex, slow) and use atomic operations (hardware lock, very
>>> fast).
>>>
>>> The source code as published currently in IPOL is absolutely buggy.
>>>
>>> So, to correct the code you have to put a "#pragma omp atomic" at the
>>> beginning of lines 229 (fpCount[il]++) and another for line 232
>>> (fpO[ii][il] += fpODenoised[ii][iindex] / fTotalWeight;) in
>>> libdenoising.cpp
>>>
>>> Best,
>>> Miguel
>>>
>>>
>>> Quoting Miguel Colom <Miguel.Colom at cmla.ens-cachan.****fr<
>>> Miguel.Colom at cmla.ens-**cachan.fr <Miguel.Colom at cmla.ens-cachan.fr>>
>>> >:
>>>
>>>  Hi,
>>>
>>>> I think the problem is at line 232:
>>>>  fpO[ii][il] += fpODenoised[ii][iindex] / fTotalWeight;
>>>>
>>>> The fpODenoised is private for every thread, so it's not problematic.
>>>>
>>>> Perhaps instead of protecting the loop with a critical section, it'd be
>>>> faster to just declare the fpO update at line 232 as an atomic
>>>> operation:
>>>>
>>>> #pragma omp atomic
>>>> fpO[ii][il] += fpODenoised[ii][iindex] / fTotalWeight;
>>>>
>>>> Best,
>>>> Miguel
>>>>
>>>> Quoting Mauricio Delbracio <mdelbra at gmail.com>:
>>>>
>>>>  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/**<http://www.ipol.im/pub/art/**2011/bcm_nlm/srcdoc/**>
>>>>> libdenoising_8cpp_source.html<**http://www.ipol.im/pub/art/**
>>>>> 2011/bcm_nlm/srcdoc/**libdenoising_8cpp_source.html<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
>>>>>
>>>>>
>>>>>
>>>> ______________________________****_________________
>>>> discuss mailing list
>>>> discuss at list.ipol.im
>>>> https://tools.ipol.im/mailman/****listinfo/discuss<https://tools.ipol.im/mailman/**listinfo/discuss>
>>>> <https://**tools.ipol.im/mailman/**listinfo/discuss<https://tools.ipol.im/mailman/listinfo/discuss>
>>>> >
>>>>
>>>>
>>>>
>>> ______________________________****_________________
>>> discuss mailing list
>>> discuss at list.ipol.im
>>> https://tools.ipol.im/mailman/****listinfo/discuss<https://tools.ipol.im/mailman/**listinfo/discuss>
>>> <https://**tools.ipol.im/mailman/**listinfo/discuss<https://tools.ipol.im/mailman/listinfo/discuss>
>>> >
>>>
>>>
>>>
>>
>
> ______________________________**_________________
> discuss mailing list
> discuss at list.ipol.im
> https://tools.ipol.im/mailman/**listinfo/discuss<https://tools.ipol.im/mailman/listinfo/discuss>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://tools.ipol.im/mailman/archive/discuss/attachments/20121014/946c5c57/attachment.html>