bugGNU Octave - Bugs: bug #51884, [octave forge] (image) bwmorph...

 
 

bug #51884: [octave forge] (image) bwmorph 'thicken' operation not matlab compatible

Submitter:  None
Submitted:  Tue 29 Aug 2017 01:40:39 PM UTC
   
 
Category:  Octave Package Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Matlab Compatibility
Status:  In Progress Assigned to:  None
Originator Name:  hans messner Originator Email:  -email is unavailable-
Open/Closed:  * Open Release:  * 4.2.1
Operating System:  * GNU/Linux Fixed Release:  None
Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Fri 13 May 2022 07:31:59 PM UTC, comment #24: 

the original bug is fixed, but the incompatability with matlab described in comment #14 remains with Octave 6.4.0, image 2.14.0, and matlab 2022a.

the bug report about 'thin' has been closed as fixed, it appears there's a path forward to compatability. i've retitled and regrouped the bug accordingly.

Nicholas Jankowski <nrjank>
Group Member
Tue 18 Dec 2018 05:24:26 AM UTC, comment #23: 

Carnë asked, in bug #55172:

"Since the thin operator is now Matlab compatible, and Matlab claims to use it for the thicken operation, shouldn't we be using thin on thicken instead of thin-pratt?"

Avinoam Kalma <avinoam>
Group Member
Thu 06 Dec 2018 04:43:41 PM UTC, comment #22: 
Avinoam Kalma <avinoam>
Group Member
Thu 06 Dec 2018 03:57:31 PM UTC, comment #21: 

i have found a matlab compatibility bug in bwmorph (‘thin’).
I will open a new bug report on this.
Please don’t close this bug report, because
the thick operator depends on the thin operator

Avinoam Kalma <avinoam>
Group Member
Thu 06 Dec 2018 02:45:39 PM UTC, comment #20: 

this final patch looks good to me (as far as I can tell ;-)

I suggest to close this bug

Many thanks and, please, keep the fantastic project
GNU Octave going!!


hans messner

Anonymous
Thu 06 Dec 2018 01:49:58 PM UTC, comment #19: 

I have pushed a slightly modified version of the patch http://hg.code.sf.net/p/octave/image/rev/3bf76823f18e

I'm unsure if you want to close this issue since the results are still not matlab compatible

Carnë Draug <carandraug>
Group Member
Thu 06 Dec 2018 12:51:13 PM UTC, comment #18: 

Matlab does not say they use the Lam book for the thicken operation, they only say they use the Lam book for the thin operation. And while Octave's implementation of thicken uses thin behind the scenes, we don't know if Matlab's implementation does the same. Also, I have spent many hours implementing algorithms from the references in Matlab documentation to know that it's often bullshit.

Carnë Draug <carandraug>
Group Member
Tue 04 Dec 2018 06:58:43 PM UTC, comment #17: 

The Octave implementation of bwmorph(thicken) relies on the details in the Pratt book (see literature in comment #15), as stated in our source code (_conditional_mark_patterns_lut_fun_.m). But the Matlab version states in its help page to rely on the details in the Lam book (see their section on "thin"). So I would assume they are just doing a slightly different thing.

I myself can't spend the effort to fully re-implement the Octave version, using a different algorithm (as stated in the Lam book) in order to become fully compatible in this case.

Nevertheless I think that the current patch (file #41737) is an improvement to the current Octave implementation. The original ideas come from Hans, a new contributor to the image package. Using this patch, our current code will better do what it claims to do in its help text. Is this enough to make use of this code? My personal opinion would be yes.

Hartmut <hardy>
Tue 04 Dec 2018 08:32:52 AM UTC, comment #16: 

ERRATUM in comment  #15:
-------------------------

Octave code should read:

   if you do in GNU Octave:

      bw = false (5,5); bw(3,3) = true;
      out1=bwmorph(bw,'thicken');
      out2=bwmorph(out1,'thicken');
      out=bwmorph(out2,'thicken');

      #short cut: out=bwmorph(bw,'thicken', 3);


Anonymous
Tue 04 Dec 2018 08:27:30 AM UTC, comment #15: 

In the literature you should look for the basic Mathematical Definition of morphological operators; the way they are implemented in some Software (e.g. Matlab, Octave, Gimp, ...) is best documented in the corresponding source code -- "Use the source, Luke" ;-)

To my understanding, thickening is more or less the dual of thinning.

The Mathworks Company has some details on the algorithms they use:
  https://www.mathworks.com/help/images/ref/bwmorph.html#bui7chk-1

They have also a fine bibliography available:

  -  Haralick, Robert M., and Linda G. Shapiro, Computer and Robot Vision, Vol. 1, Addison-Wesley, 1992.

  -  Lam, L., Seong-Whan Lee, and Ching Y. Suen, "Thinning Methodologies-A Comprehensive Survey," IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol 14, No. 9, September 1992, page 879, bottom of first column through top of second colum

   -  Pratt, William K., Digital Image Processing, John Wiley & Sons, Inc., 1991.n.

Possibly also of interest:
   - http://www.di.univr.it/documenti/OccorrenzaIns/matdid/matdid699113.pdf
   - https://homes.di.unimi.it/ferrari/ElabImm2011_12/EI2011_12_13_morphology_double.pdf
   - high performance implementation for GIMP: https://alessandrofrancesconi.it/projects/morphop/
 

As for the thickening in the octave package:

https://octave.sourceforge.io/image/function/bwmorph.html

   Function File: bwmorph (bw, operation, n)

      For a binary image bw, performs the morphological operation, n times.

     ‘thicken’      Performs a thickening operation. This
                    operation "thickens" objects avoiding their
                    fusion. Its implemented as a thinning of the
                    background. That is, thinning on negated
                    image. Finally a diagonal fill operation
                    is performed to avoid "eight-connecting"
                    objects.

Obviously you get the same result as you get with your MATLAB
for the test case:

   bw = false (5,5); bw(3,3) = true;
   out=bwmorph(bw, "thicken", 1);

if you do in GNU Octave:

   bw = false (5,5); bw(3,3) = true;
   out1=bwmorph(bw,'thicken');
   out2=bwmorph(out1,'thicken');
   out=bwmorph(out1,'thicken');
   #short cut:  out=bwmorph(bw,'thicken', 3);

I guess the guys at The Mathworks Company can help you with  the investigation of the imagetoolbox::bwmorph() implementation details (which structuring elements gets used, what is the default value of "n", etc.)

Anonymous
Mon 03 Dec 2018 09:30:37 PM UTC, comment #14: 

Tried a simple example:


H = false (5,5);
H(3,3) = 1;
a = bwmorph(H,'thicken', 1)

Matlab:

a =

  5×5 logical array

   0   1   1   1   0
   1   1   1   1   1
   1   1   1   1   1
   1   1   1   1   1
   0   1   1   1   0


Octave:

a =

  0  0  0  0  0
  0  0  1  0  0
  0  1  1  1  0
  0  0  1  0  0
  0  0  0  0  0


BTW, what is the mathematical definition of 'thicken'?

Avinoam Kalma <avinoam>
Group Member
Mon 03 Dec 2018 09:51:00 AM UTC, comment #13: 

please neglect about my suggestion in the former comment; your
Patch in file #41737 from comment #11 is perfect!

I should have understood earlier that
   assert (out, true (3, 3));
enforces verification of out(1,3) == true!

sorry for the confusion

hans

Anonymous
Mon 03 Dec 2018 09:05:08 AM UTC, comment #12: 

The Patch (by HG2 in file #41737; see comment #11) looks fine to
me.

I would suggest to append to the very last test case:

   %!test
   %! bw = false (3, 3);
   %! bw(3, 1) = true;
   %! out = bwmorph(bw, "thicken", 4);
   %! assert (out, true (3, 3));

the assert statement:

   %! assert (out, true (1, 3));

as another important relation in the corresponding context. (For
bwmorph(bw, "thicken", 3) the upper right corner would be 'false'; since we are thickening with '4' the corner gets filled,  too).

Vielen Dank, dass Sie sich um die Einpflegung des Verbesserungsvorschlages zu bwmorph() kümmern!

hG

hans messner




Anonymous
Sun 02 Dec 2018 09:08:22 PM UTC, comment #11: 

please review (patch HG2 in file #41737)

Hartmut <hardy>
Tue 05 Sep 2017 07:44:25 PM UTC, comment #10: 

You are right, this wasn't enough padding, yet. Thanks for spotting this.

Here is a new PATCH (HG2 in file name) to fix this, including the additional test from comment #9.

(file #41737)

Hartmut <hardy>
Mon 04 Sep 2017 08:24:52 PM UTC, comment #9: 

I guess the "border" (padding margin) to be added needs to be large enough. Otherwise we might fail to reach the corners. Please test your (HG1 version; attached file #41717) this
way:


octave:11> test_bw = false(3,3); test_bw(3,1)=true;disp(test_bw);
  0  0  0
  0  0  0
  1  0  0

octave:12> bw=bwmorph(test_bw, 'thicken', 2)
bw =

  1  0  0
  1  1  0
  1  1  1

octave:13> bw=bwmorph(test_bw, 'thicken', Inf)
bw =

  1  1  0
  1  1  1
  1  1  1


If we use a large enough (say patch version HG1.1) padding
as in code:


    case "thicken"
      if (n > 0)
        n_pad = 2 * min ([ max(size (bw)), n ]);
        bw_padded = padarray (bw, [n_pad, n_pad], "zeros");
        bw = bwmorph (! bw_padded, "thin", n);
        loop_once = true;
        morph = @(x) bwmorph (x, "diag");
        post_morph = @(x) ! x(1+n_pad : end-n_pad, 1+n_pad : end-n_pad);
      endif


Now, even our "academic" (synthetic) test case works (the image gets filled up for n=4):


octave:18> test_bw = false(3,3); test_bw(3,1)=true;disp(test_bw);
  0  0  0
  0  0  0
  1  0  0
octave:19> bw=bwmorph(test_bw, 'thicken', 4)
bw =

  1  1  1
  1  1  1
  1  1  1


I guess this relates to the fact that the "thicken" operation actually is implemented by its dual: thinning of the background.

Thanks for the code cleanup (I learned more about GNU Octave ;-)


Anonymous
Sat 02 Sep 2017 10:52:10 AM UTC, comment #8: 

I've cleaned up your code a bit, and wrapped it into a PATCH file (attached as HG1 version). Have a look at it.

Thanks for the code suggestion again.

Now we'll have to wait for the package maintainer (Carné) to review this and probably add this to the image repository (and then this would go to the next release of the image package).

(file #41717)

Hartmut <hardy>
Thu 31 Aug 2017 07:33:32 AM UTC, comment #7: 

In order to get a correct (i.e. not negated) result for "n==0" we
test for this case ...


 case "thicken"

   if (n > 0)
      ## 31-Aug-2017 MeJ:: going for a >>bwmorph(bw, 'thicken', n)<< and including the "add border workaround"
      add_border = 2*(min([ max(size(bw)), n ]));
      bw_framed = false(size(bw,1)+(2*add_border),size(bw,2)+(2*add_border));
      lb1 = (add_border+1); ub1 = (size(bw,1)+add_border);
      lb2 = (add_border+1); ub2 = (size(bw,2)+add_border);
      bw_framed(lb1:ub1,lb2:ub2) = bw;
      bw = bwmorph (! bw_framed, "thin", n);
      loop_once = true;
      morph = @(x) bwmorph (x, "diag");
      post_morph = @(x) ! x(lb1:ub1,lb2:ub2);
   endif

   ## --------- original code fragement (as of octave forge package image 2.6.1)
   ## This implementation also "thickens" the border. To avoid this,
   ## a simple solution could be to add a border of 1 to the reversed
   ## image.
   #
   #    bw = bwmorph (! bw, "thin", n);
   #    loop_once = true;
   #    morph = @(x) bwmorph (x, "diag");



Test case:


octave:5> test_bw = false(3,3); test_bw(3,1)=true;disp(test_bw);
  0  0  0
  0  0  0
  1  0  0

octave:6> bw0=bwmorph(test_bw, 'thicken', 0)
bw0 =

  0  0  0
  0  0  0
  1  0  0



Anonymous
Wed 30 Aug 2017 04:58:46 PM UTC, comment #6: 

Thanks for your code suggestions, Hans. I'll try to have a closer look during the following days.

Hartmut <hardy>
Wed 30 Aug 2017 10:33:49 AM UTC, comment #5: 

// this is the final edition (I hope)

This is my suggestion for the "thicken" case:


    case "thicken"
      ## This implementation also "thickens" the border. To avoid this,
      ## a simple solution could be to add a border of 1 to the reversed
      ## image.

      ## 30-Aug-2017 MeJ:: going for a
      ##                bwmorph(bw, 'thicken', n)
      ##             with "add a border" workaround
      max_dim = max( size(bw) );
      add_border = 2 * ( min([ max_dim, n ]) );
      bw_framed = false(size(bw,1)+(2*add_border),size(bw,2)+(2*add_border));
      lb1 = (add_border+1); ub1 = (size(bw,1)+add_border);
      lb2 = (add_border+1); ub2 = (size(bw,2)+add_border);
      bw_framed(lb1:ub1,lb2:ub2) = bw;
      bw = bwmorph (! bw_framed, "thin", n);
      loop_once = true;
      morph = @(x) bwmorph (x, "diag");
      post_morph = @(x) ! x(lb1:ub1,lb2:ub2);

      ## --------- original code fragement
      ##           (as of octave forge package image 2.6.1)
      ##   bw = bwmorph (! bw, "thin", n);
      ##   loop_once = true;
      ##   morph = @(x) bwmorph (x, "diag");


Some Tests:


## 1.)
octave:61> test_bw = false(8,7); test_bw(8,1)=true; disp(test_bw);
  0  0  0  0  0  0  0
  0  0  0  0  0  0  0
  0  0  0  0  0  0  0
  0  0  0  0  0  0  0
  0  0  0  0  0  0  0
  0  0  0  0  0  0  0
  0  0  0  0  0  0  0
  1  0  0  0  0  0  0
octave:62>
octave:62> bb = bwmorph(test_bw, "thicken", 6)
bb =

  0  0  0  0  0  0  0
  1  0  0  0  0  0  0
  1  1  0  0  0  0  0
  1  1  1  0  0  0  0
  1  1  1  1  0  0  0
  1  1  1  1  1  0  0
  1  1  1  1  1  1  0
  1  1  1  1  1  1  1


## 2.)
octave:63> test_bw = false(8,7); test_bw(2,4)=true; disp(test_bw);
  0  0  0  0  0  0  0
  0  0  0  1  0  0  0
  0  0  0  0  0  0  0
  0  0  0  0  0  0  0
  0  0  0  0  0  0  0
  0  0  0  0  0  0  0
  0  0  0  0  0  0  0
  0  0  0  0  0  0  0


octave:65> thickened_bw=bwmorph(test_bw, "thicken", 2)
thickened_bw =

  0  0  1  1  1  0  0
  0  1  1  1  1  1  0
  0  0  1  1  1  0  0
  0  0  0  1  0  0  0
  0  0  0  0  0  0  0
  0  0  0  0  0  0  0
  0  0  0  0  0  0  0
  0  0  0  0  0  0  0


Anonymous
Wed 30 Aug 2017 10:03:30 AM UTC, comment #4: 

sorry for the HTML character encoding of my posting below ...
(perhaps I should not have done a preview before ;-)

case "thicken";
      ## This implementation also "thickens" the border. To avoid this,
      ## a simple solution could be to add a border of 1 to the reversed
      ## image.

      ## 30-Aug-2017 MeJ:: going for a >>bwmorph(bw, 'thicken', n)<<; with "add border workaround"
      max_dim = max( size(bw) );
      add_border = 2 * ( min([ ceil(max_dim/2), n ]) );
      bw_framed = false(size(bw,1)+(2*add_border),size(bw,2)+(2*add_border));
      lb1 = (add_border+1); ub1 = (size(bw,1)+add_border);
      lb2 = (add_border+1); ub2 = (size(bw,2)+add_border);
      bw_framed(lb1:ub1,lb2:ub2) = bw;
      bw = ! bwmorph (! bw_framed, "thin", n);
      loop_once = true;
      morph = @(x) bwmorph (x, "diag");
      post_morph = @(x) x(lb1:ub1,lb2:ub2);

      ## --------- original code fragement (as of octave forge package image 2.6.1)
      ##   bw = bwmorph (! bw, "thin", n);
      ##   loop_once = true;
      ##   morph = @(x) bwmorph (x, "diag");



Testing:
---------

octave: test_bw = false(8,7); test_bw(6,3)=true; disp(test_bw);
  0  0  0  0  0  0  0
  0  0  0  0  0  0  0
  0  0  0  0  0  0  0
  0  0  0  0  0  0  0
  0  0  0  0  0  0  0
  0  0  1  0  0  0  0
  0  0  0  0  0  0  0
  0  0  0  0  0  0  0

octave: thickened_bw=bb=bwmorph(test_bw, "thicken", 1); disp(thickened_bw);
  0  0  0  0  0  0  0
  0  0  0  0  0  0  0
  0  0  0  0  0  0  0
  0  0  0  0  0  0  0
  0  0  1  0  0  0  0
  0  1  1  1  0  0  0
  0  0  1  0  0  0  0
  0  0  0  0  0  0  0

octave: thickened_bw=bb=bwmorph(test_bw, "thicken", 3); disp(thickened_bw);
  0  0  0  0  0  0  0
  0  0  0  0  0  0  0
  0  0  1  0  0  0  0
  0  1  1  1  0  0  0
  1  1  1  1  1  0  0
  1  1  1  1  1  1  0
  1  1  1  1  1  0  0
  0  1  1  1  0  0  0

# I am no expert in this area ... but the results look reasonable.

Anonymous
Wed 30 Aug 2017 09:51:37 AM UTC, comment #3: 


## here is my suggestion for an improvement of the &quot;thicken&quot; case

case &quot;thicken&quot;
      ## This implementation also &quot;thickens&quot; the border. To avoid this,
      ## a simple solution could be to add a border of 1 to the reversed
      ## image.

      ## 30-Aug-2017 MeJ:: going for a &gt;&gt;bwmorph(bw, 'thicken', n)&lt;&lt; with &quot;add border workaround&quot;
      max_dim = max( size(bw) );
      add_border = 2 * ( min([ ceil(max_dim/2), n ]) );
      bw_framed = false(size(bw,1)+(2*add_border),size(bw,2)+(2*add_border));
      lb1 = (add_border+1); ub1 = (size(bw,1)+add_border);
      lb2 = (add_border+1); ub2 = (size(bw,2)+add_border);
      bw_framed(lb1:ub1,lb2:ub2) = bw;
      bw = ! bwmorph (! bw_framed, &quot;thin&quot;, n);
      loop_once = true;
      morph = @(x) bwmorph (x, &quot;diag&quot;);
      post_morph = @(x) x(lb1:ub1,lb2:ub2);

      ## --------- original code fragement (as of octave forge package image 2.6.1)
      ##   bw = bwmorph (! bw, &quot;thin&quot;, n);
      ##   loop_once = true;
      ##   morph = @(x) bwmorph (x, &quot;diag&quot;);


Anonymous
Tue 29 Aug 2017 06:16:40 PM UTC, comment #2: 

Here is the current source code (just type "edit bwmorph" to see it):


    case "thicken"
      ## This implementation also "thickens" the border. To avoid this,
      ## a simple solution could be to add a border of 1 to the reversed
      ## image.
      bw = bwmorph (! bw, "thin", n);
      loop_once = true;
      morph = @(x) bwmorph (x, "diag");

[...]

  if (loop_once && n > 1)
    n = 1;
  endif

[...]

  while (i <= n) ## a for loop wouldn't work because n can be Inf
    bw2_tmp = morph (bw);
    if (isequal (bw, bw2_tmp))
      ## if it doesn't change we don't need to process it further
      break
    endif
    bw = bw2_tmp;
    i++;
  endwhile


Do you have a good suggestion how to improve this code (the "case thicken" section) with your current insight into the topic? Could you include your workaround into the code in a good way? (Or would you say that the problem is already in the "thin" subroutine?)

Hartmut <hardy>
Tue 29 Aug 2017 02:47:33 PM UTC, comment #1: 

In case you want to "thicken" with width 'w' you will have to use an extra border at least of size w+1 in the workaround

Anonymous
Tue 29 Aug 2017 01:40:39 PM UTC, original submission:  




Problem Environment:
---------------------

octave:41> ver
--------------------------------------------------
GNU Octave Version: 4.2.1
GNU Octave License: GNU General Public License
Operating System: Linux 2.6.32.54-0.3-default
                  #2 SMP Fri Nov 29 16:05:00 CET 2013 x86_64
--------------------------------------------------
Package Name   | Version | Installation directory
---------------+---------+-----------------------
      general  |   2.0.0 | /octave/general-2.0.0
        image *|   2.6.1 | /octave/image-2.6.1
           io *|   2.4.7 | /octave/io-2.4.7
miscellaneous  |   1.2.1 | /octave/miscellaneous-1.2.1
     parallel  |   3.1.1 | /octave/parallel-3.1.1
      sockets  |   1.2.0 | /octave/sockets-1.2.0
   statistics *|   1.3.0 | /octave/statistics-1.3.0
       struct  |  1.0.14 | /octave/struct-1.0.14


Problematic Code fragment:
---------------------------


octave:44> a0 = false(5);
octave:45> a0(3,3) = true;
octave:47> a0
a0 =

  0  0  0  0  0
  0  0  0  0  0
  0  0  1  0  0
  0  0  0  0  0
  0  0  0  0  0

octave:46> bb=bwmorph(a0, "thicken", 1)
bb =

  0  0  1  0  0
  0  1  1  1  0
  1  1  0  1  1
  0  1  1  1  0
  0  0  1  0  0


%% ======= We expected (not negated; margin not growing):
%
%  0  0  0  0  0
%  0  0  1  0  0
%  0  1  1  1  0
%  0  0  1  0  0
%  0  0  0  0  0
%


%% ======== and can be achieved by some kind of "workaround":
octave:50> m_border = false(size(a0,1)+4);
octave:51> m_border(3:(size(a0,1)+2),3:(size(a0,1)+2)) = a0;
octave:52> bb = !bwmorph(m_border, 'thicken', 1) ...
                        (3:(size(a0,1)+2), 3:(size(a0,1)+2))
bb =

  0  0  0  0  0
  0  0  1  0  0
  0  1  1  1  0
  0  0  1  0  0
  0  0  0  0  0

%% however, I guess this needs a fix in the source code.


Anonymous

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

Attached Files

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by nrjank (Posted a comment)
  • -email is unavailable- added by avinoam (Posted a comment)
  • -email is unavailable- added by hardy (Posted a comment)
  • -email is unavailable- added by hardy
  • -email is unavailable- added by hardy
  • -email is unavailable- added by jwe (Updated the item)
  • -email is unavailable- added by None (Submitted the item)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only group members can vote.

     

    Follow 8 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2022-05-13 nrjank Item GroupIncorrect Result Matlab Compatibility
        Summary[octave forge] (image) bwmorph(blackNwhiteMatrix, &quot;thicken&quot;, 1) returns negated result (+ strange behavior at border) [octave forge] (image) bwmorph 'thicken' operation not matlab compatible
    2018-12-18 avinoam StatusNone In Progress
    2017-09-05 hardy Attached File- Added bwmorph_thicken_padding_HG2.patch, #41737
    2017-09-02 hardy Attached File- Added bwmorph_thicken_padding_HG1.patch, #41717
    2017-08-29 hardy Carbon-Copy- Added avinoam
        Carbon-Copy- Added carandraug
    2017-08-29 jwe Summarybwmorph(blackNwhiteMatrix, &quot;thicken&quot;, 1) returns negated result (+ strange behavior at border) [octave forge] (image) bwmorph(blackNwhiteMatrix, "thicken", 1) returns negated result (+ strange behavior at border)

    Back to the top

    Powered by Savane 3.13-cf05.
    Corresponding source code