<html>
  <head>
    <meta content="text/html; charset=ISO-8859-1"
      http-equiv="Content-Type">
  </head>
  <body bgcolor="#FFFFFF" text="#000000">
    <div class="moz-cite-prefix">Ok, so which is the procedure in order
      to make the proposed changes by Miguel.  Even if the parameters
      used by miguel and mauricio, bock=win=1, are not the ones used in
      the demo, this overwrite of memory could happen in practice. <br>
      <br>
      Toni<br>
      <br>
      <br>
      <br>
      <br>
      On 14/10/2012 19:04, Jean-Michel Morel wrote:<br>
    </div>
    <blockquote
cite="mid:CALpGdHdvuHvBdpfOzBgBOnKe4B2-f-8Jh-DuQA3=e=zHyTaqOQ@mail.gmail.com"
      type="cite">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 <br>
      the demo code.<br>
      <br>
      <br>
      <div class="gmail_quote">On Sun, Oct 14, 2012 at 6:14 PM, Miguel
        Colom <span dir="ltr"><<a moz-do-not-send="true"
            href="mailto:Miguel.Colom@cmla.ens-cachan.fr"
            target="_blank">Miguel.Colom@cmla.ens-cachan.fr</a>></span>
        wrote:<br>
        <blockquote class="gmail_quote" style="margin:0 0 0
          .8ex;border-left:1px #ccc solid;padding-left:1ex">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.<br>
          <br>
          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.<br>
          <br>
          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: <a moz-do-not-send="true"
            href="http://dev.ipol.im/%7Ecolom/bad_pixels/"
            target="_blank">http://dev.ipol.im/~colom/bad_pixels/</a><br>
          <br>
          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).<br>
          His images can be downloaded from here: <a
            moz-do-not-send="true"
            href="http://dev.ipol.im/%7Emdelbra/bug/" target="_blank">http://dev.ipol.im/~mdelbra/bug/</a><br>
          <br>
          Best,<br>
          Miguel<br>
          <br>
          Quoting Jean-Michel Morel <<a moz-do-not-send="true"
            href="mailto:Jean-Michel.Morel@cmla.ens-cachan.fr"
            target="_blank">Jean-Michel.Morel@cmla.ens-cachan.fr</a>>:<br>
          <br>
          <blockquote class="gmail_quote" style="margin:0 0 0
            .8ex;border-left:1px #ccc solid;padding-left:1ex">
            <div class="im">
              Can you test it on the same image?<br>
              Best,<br>
              JM<br>
              <br>
              On Sun, Oct 14, 2012 at 5:29 PM, Miguel Colom <<br>
              <a moz-do-not-send="true"
                href="mailto:Miguel.Colom@cmla.ens-cachan.fr"
                target="_blank">Miguel.Colom@cmla.ens-cachan.fr</a>>
              wrote:<br>
              <br>
            </div>
            <blockquote class="gmail_quote" style="margin:0 0 0
              .8ex;border-left:1px #ccc solid;padding-left:1ex">
              <div class="im">
                Dear all,<br>
                Mauricio and I have found a way to modify the code to
                avoid the critical<br>
                sections (SO mutex, slow) and use atomic operations
                (hardware lock, very<br>
                fast).<br>
                <br>
                The source code as published currently in IPOL is
                absolutely buggy.<br>
                <br>
                So, to correct the code you have to put a "#pragma omp
                atomic" at the<br>
                beginning of lines 229 (fpCount[il]++) and another for
                line 232<br>
                (fpO[ii][il] += fpODenoised[ii][iindex] / fTotalWeight;)
                in libdenoising.cpp<br>
                <br>
                Best,<br>
                Miguel<br>
                <br>
                <br>
              </div>
              Quoting Miguel Colom <<a class="moz-txt-link-abbreviated" href="mailto:Miguel.Colom@cmla.ens-cachan.**fr">Miguel.Colom@cmla.ens-cachan.**fr</a><<a
                moz-do-not-send="true"
                href="mailto:Miguel.Colom@cmla.ens-cachan.fr"
                target="_blank">Miguel.Colom@cmla.ens-cachan.fr</a>><br>
              >:<br>
              <br>
               Hi,<br>
              <blockquote class="gmail_quote" style="margin:0 0 0
                .8ex;border-left:1px #ccc solid;padding-left:1ex">
                <div>
                  <div class="h5">
                    I think the problem is at line 232:<br>
                     fpO[ii][il] += fpODenoised[ii][iindex] /
                    fTotalWeight;<br>
                    <br>
                    The fpODenoised is private for every thread, so it's
                    not problematic.<br>
                    <br>
                    Perhaps instead of protecting the loop with a
                    critical section, it'd be<br>
                    faster to just declare the fpO update at line 232 as
                    an atomic operation:<br>
                    <br>
                    #pragma omp atomic<br>
                    fpO[ii][il] += fpODenoised[ii][iindex] /
                    fTotalWeight;<br>
                    <br>
                    Best,<br>
                    Miguel<br>
                    <br>
                    Quoting Mauricio Delbracio <<a
                      moz-do-not-send="true"
                      href="mailto:mdelbra@gmail.com" target="_blank">mdelbra@gmail.com</a>>:<br>
                    <br>
                     Dear all,<br>
                  </div>
                </div>
                <blockquote class="gmail_quote" style="margin:0 0 0
                  .8ex;border-left:1px #ccc solid;padding-left:1ex">
                  <div>
                    <div class="h5">
                      <br>
                      I may have found a bug in the NL-means IPOL
                      implementation. The<br>
                      problem is due to parallelism, particularly when
                      updating shared<br>
                      values by more than one threading (race condition,
                      race bug).<br>
                      <br>
                      In NL-means this happens in the filtered image
                      (fpO) which is shared<br>
                      and updated by all the threads. The image is
                      decomposed in overlapped<br>
                      patches that are denoised each of them separately,
                      and then they are<br>
                      aggregated in the final image (fpO). The problem
                      is that when the<br>
                      update of fpO  takes place, may happen that two
                      overlapped patches<br>
                      running in different threads try to update the
                      same memory address.<br>
                      <br>
                      This not happen very frequently, since it is very
                      unlikely that two<br>
                      overlapped patches take the same amount of time to
                      arrive at that part<br>
                      of the code...The probability of this to happen
                      increases if the<br>
                      search block (the block where similar patches are
                      searched) is very<br>
                      small.<br>
                      <br>
                      To eliminate the bug, the way I found (a.k.a the
                      easy way) is to<br>
                      enclose the writing of fpO in a "omp critical"
                      block. This means that<br>
                      only one thread at at a time can write in fpO
                      (there's a loss in<br>
                      execution time, probably there other ways of
                      avoiding this problem,<br>
                      e.g. by using local memory blocks and then update
                      at the end? i don't<br>
                      know I'm not really familiar with OpenMP).<br>
                      <br>
                      I attach a possible patch to libdenoising.cpp.<br>
                      <br>
                      The block of code I refer is in libdenoising.cpp
                      between lines 219-238<br>
                    </div>
                  </div>
                  <a moz-do-not-send="true"
                    href="http://www.ipol.im/pub/art/**2011/bcm_nlm/srcdoc/**"
                    target="_blank">http://www.ipol.im/pub/art/**2011/bcm_nlm/srcdoc/**</a><br>
                  libdenoising_8cpp_source.html<<a
                    moz-do-not-send="true"
href="http://www.ipol.im/pub/art/2011/bcm_nlm/srcdoc/libdenoising_8cpp_source.html"
                    target="_blank">http://www.ipol.im/pub/art/2011/bcm_nlm/srcdoc/libdenoising_8cpp_source.html</a>>
                  <div class="im">
                    <br>
                    <br>
                    I also attach an image showing the effect of the bug
                    (parameters<br>
                    bloc=1, win=1) and some pixels that I manually
                    marked.<br>
                    <br>
                    I appreciate any feedback (there are surely many
                    OpenMP experts  in<br>
                    this mailing-list), so let me know what you think.<br>
                    <br>
                    best<br>
                    m<br>
                    <br>
                    <br>
                  </div>
                </blockquote>
                <br>
                ______________________________**_________________<br>
                discuss mailing list<br>
                <a moz-do-not-send="true"
                  href="mailto:discuss@list.ipol.im" target="_blank">discuss@list.ipol.im</a><br>
                <a moz-do-not-send="true"
                  href="https://tools.ipol.im/mailman/**listinfo/discuss"
                  target="_blank">https://tools.ipol.im/mailman/**listinfo/discuss</a><<a
                  moz-do-not-send="true"
                  href="https://tools.ipol.im/mailman/listinfo/discuss"
                  target="_blank">https://tools.ipol.im/mailman/listinfo/discuss</a>><br>
                <br>
                <br>
              </blockquote>
              <br>
              ______________________________**_________________<br>
              discuss mailing list<br>
              <a moz-do-not-send="true"
                href="mailto:discuss@list.ipol.im" target="_blank">discuss@list.ipol.im</a><br>
              <a moz-do-not-send="true"
                href="https://tools.ipol.im/mailman/**listinfo/discuss"
                target="_blank">https://tools.ipol.im/mailman/**listinfo/discuss</a><<a
                moz-do-not-send="true"
                href="https://tools.ipol.im/mailman/listinfo/discuss"
                target="_blank">https://tools.ipol.im/mailman/listinfo/discuss</a>><br>
              <br>
              <br>
            </blockquote>
            <br>
          </blockquote>
          <div class="HOEnZb">
            <div class="h5">
              <br>
              <br>
              _______________________________________________<br>
              discuss mailing list<br>
              <a moz-do-not-send="true"
                href="mailto:discuss@list.ipol.im" target="_blank">discuss@list.ipol.im</a><br>
              <a moz-do-not-send="true"
                href="https://tools.ipol.im/mailman/listinfo/discuss"
                target="_blank">https://tools.ipol.im/mailman/listinfo/discuss</a><br>
              <br>
            </div>
          </div>
        </blockquote>
      </div>
      <br>
      <br>
      <fieldset class="mimeAttachmentHeader"></fieldset>
      <br>
      <pre wrap="">_______________________________________________
discuss mailing list
<a class="moz-txt-link-abbreviated" href="mailto:discuss@list.ipol.im">discuss@list.ipol.im</a>
<a class="moz-txt-link-freetext" href="https://tools.ipol.im/mailman/listinfo/discuss">https://tools.ipol.im/mailman/listinfo/discuss</a></pre>
    </blockquote>
    <br>
  </body>
</html>