bugGNU Octave - Bugs: bug #55172, [octave forge] (image) b =...

 
 

bug #55172: [octave forge] (image) b = bwmorph (BW, 'thin', 1) is not Matlab compatible

Submitter:  Avinoam Kalma <avinoam>
Submitted:  Thu 06 Dec 2018 04:42:48 PM UTC
 
Category:  Octave Forge Package Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Matlab Compatibility
Status:  Fixed Assigned to:  avinoam
Originator Name:  Open/Closed:  * Closed
Release:  * other Operating System:  * Any
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment (Rich Markup)
   

Comment Type & Canned Response:
       

 

( Jump to the original submission )

Mon 24 Dec 2018 08:20:44 PM UTC, comment #15: 

Closing.

Avinoam Kalma <avinoam>
Project Member
Tue 18 Dec 2018 05:21:21 AM UTC, comment #14: 

Thanks for pushing this patch.
Since there is an open bug for "thicken" (bug #51884),
maybe we should continue there the discussion?

Avinoam Kalma <avinoam>
Project Member
Tue 18 Dec 2018 01:01:32 AM UTC, comment #13: 

I have pushed the changes after removing the trailing whitespace and editing the NEWS entry.

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?

Carnë Draug <carandraug>
Project Member
Mon 17 Dec 2018 09:36:17 PM UTC, comment #12: 

I hope this is the final patch ...
attached bwmorph_V3.patch

(file #45684)

Avinoam Kalma <avinoam>
Project Member
Mon 17 Dec 2018 05:11:06 AM UTC, comment #11: 

Thanks for the detailed review.
This should be fixed. I will push fixed version.

Avinoam Kalma <avinoam>
Project Member
Sun 16 Dec 2018 08:30:30 PM UTC, comment #10: 

I've had a look at the V2 patch file. All the previously mentioned things seem to be fixed, now. But I found another small thing:

  • In the code of bwmorph.m the (commented out) helper functions are called "@__thin_lut1__" (and ...2). But the two files in the devel folder are named "__thin_fun1__.m" (and ...2). Could you adjust either of them, and make them identical? I think this will avoid later confusion about the usage of those two helper functions.

Otherwise I think this patch will then be ready for pushing, thanks again for dealing with it.

Hartmut <hardy>
Sat 15 Dec 2018 06:31:46 PM UTC, comment #9: 

Thanks for the review.
Here is a fixed version.

(file #45675)

Avinoam Kalma <avinoam>
Project Member
Sat 15 Dec 2018 03:09:37 PM UTC, comment #8: 

Thanks for implementing this new (and compatible!) "thin" algorithm. In principle I think this is a good patch now, there are just some minor things to polish up:

  • As you said in comment #7 it would be good to use the old "thin-pratt" algorithm in the "thicken" procedure of bwmorph, for the time beeing. (We can then later look at "thicken" to maybe also make it compatible.) But currently your mentioned change (i.e. using thin-pratt inside of thicken) is NOT part of the patch, yet. Could you add it, please?
  • There seem to be no other uses of "thin" in the image package, so no other side effects should be expected.
  • Your 2 tests in the patch file pass and are Matlab compatible. I have checked this.
  • I have some other tests (they also pass and are also Matlab compatible). You could add them to your patch:

H3 = [0 0 0 0 0 0;
      0 1 1 1 0 0;
      0 1 1 1 0 0;
      0 0 0 1 0 1;
      0 0 0 0 1 1;
      0 0 0 1 1 1];
out3 = bwmorph (H3, "thin", 1);
expected3 = logical(
    [0   0   0   0   0   0;
     0   0   0   0   0   0;
     0   1   1   0   0   0;
     0   0   0   1   0   1;
     0   0   0   0   1   0;
     0   0   0   1   1   0]);
assert (out3, expected3);

out33 = bwmorph (H3, "thin", 2);
expected33 = logical(
    [0   0   0   0   0   0;
     0   0   0   0   0   0;
     0   1   1   0   0   0;
     0   0   0   1   0   1;
     0   0   0   0   1   0;
     0   0   0   1   0   0]);
assert (out33, expected33);

out333 = bwmorph (H3, "thin", inf);
assert  (out333, expected33);

Hartmut <hardy>
Wed 12 Dec 2018 09:04:42 PM UTC, comment #7: 

Attached a new patch:

  • bwmorph (BW, "thin", 1) is now Matlab compatible
  • I added to devel directory the functions that create the LUT
  • old "thin" was changed to "thin-pratt"
  • "thicken" is using "thin-pratt", so there are no changes for "thicken"

Please review

(file #45639)

Avinoam Kalma <avinoam>
Project Member
Sun 09 Dec 2018 08:54:38 PM UTC, comment #6: 

@Hartmut: thanks for the review.
I will prepare a new cs, according to your suggestions.

Avinoam Kalma <avinoam>
Project Member
Sun 09 Dec 2018 12:38:11 PM UTC, comment #5: 
  • Could we keep the old "thin" algorithm (with the old lut) in bwmorph? Maybe as "thin_pratt"? That would allow people to still use it in order to get compatible results to how they were before.
Hartmut <hardy>
Sat 08 Dec 2018 07:45:27 PM UTC, comment #4: 
  • What would the side effects be of changing the "thin" algorithm that way?
    • Do all the tests in bwmorph (e.g. the ones that test "thicken") still pass? (It might even be a good thing when some of them start to fail, see next point.)
    • Does the "thicken" option become more Matlab compatible with this change? It relies fully on the "thin" option, and is currently not very compatible (see bug #51884).
    • Do ALL the tests in the whole image package still pass? This would be a good thing to test for this very change, because I think there are several functions that have an optional parameter to do a final "thinning" step at their end.
Hartmut <hardy>
Sat 08 Dec 2018 07:16:54 PM UTC, comment #3: 
  • I haven't tested the output values of your supposed function, yet. Have you? Dou you get Matlab compatible results for a couple of meaningful examples? If yes, could you add tests for those to bwmorph.m? (Do we need to remove existing tests in bwmorph?)
  • Could you add the content of your thin_fun1.m and thin_fun2.m somehow to the existing private function _conditional_mark_patterns_lut_fun_ ? I like the way this was done before: the final LUT numbers were hard-coded into the code of bwmorph.m, but  there was also a (commented out) code line how to produce this LUT via the _conditional_mark_patterns_lut_fun_ function. This made it possible for me to understand where those numbers (the LUT) came from, and imprived the maintainability of the code.
  • Could you add the detailed paper reference into the code? (Maybe into _conditional_mark_patterns_lut_fun_ .m?)
Hartmut <hardy>
Sat 08 Dec 2018 08:39:59 AM UTC, comment #2: 

Matlab algoirthm for bwmorph (BW, 'thin') is based on the paper
 "Thinning Methodologies - A Comprehensive Survey", by Louisa Lam, Seong-Whan Lee, and Ching Y. Suen, published in IEEE Transactions on Pattern Analysis and Machine Intelligence,
Vol 14, No. 9, September 1992. https://pdfs.semanticscholar.org/0404/ba243ecbb8efc6bcb07a754b6f8770856131.pdf.

The specific algorithm used by matlab appears on page 879, bottom of first column through top of second column.
The algorithm has two steps:

function ret = thin_fun1 (A)

## stage 1 in thin algorithm

  x1 = A(2,3);
  x2 = A(1,3);
  x3 = A(1,2);
  x4 = A(1,1);
  x5 = A(2,1);
  x6 = A(3,1);
  x7 = A(3,2);
  x8 = A(3,3);

  p = A(2,2);

## condition 1
  b1 = (~x1) & (x2 | x3);
  b2 = (~x3) & (x4 | x5);
  b3 = (~x5) & (x6 | x7);
  b4 = (~x7) & (x8 | x1);
  xh = b1 + b2 + b3 + b4;

## condition 2
  n1 = (x1 | x2) + (x3 | x4) + (x5 | x6) + (x7 | x8);
  n2 = (x2 | x3) + (x4 | x5) + (x6 | x7) + (x8 | x1);
  m = min(n1, n2);

## condition 3
  G3 = (x2 | x3 | (!x8)) & x1;
  G3 = ~G3;

## point p is deleted iff all three condistions are true
  ret = p & (~((xh == 1) & (m == 2 | m == 3) & G3));

end

and 2nd step:

function ret = thin_fun2 (A)

## stage 2 in thin algorithm

  x1 = A(2,3);
  x2 = A(1,3);
  x3 = A(1,2);
  x4 = A(1,1);
  x5 = A(2,1);
  x6 = A(3,1);
  x7 = A(3,2);
  x8 = A(3,3);

  p = A(2,2);

## condition 1
  b1 = (~x1) & (x2 | x3);
  b2 = (~x3) & (x4 | x5);
  b3 = (~x5) & (x6 | x7);
  b4 = (~x7) & (x8 | x1);
  xh = b1 + b2 + b3 + b4;

## condition 2
  n1 = (x1 | x2) + (x3 | x4) + (x5 | x6) + (x7 | x8);
  n2 = (x2 | x3) + (x4 | x5) + (x6 | x7) + (x8 | x1);
  m = min(n1, n2);

## condition 3
  G3 = (x6 | x7 | (~x4)) & x5;
  G3 = ~G3;

## point p is deleted iff all three condistions are true
  ret = p & (~((xh == 1) & (m == 2 | m == 3) & G3));

end

We can use a LUT to implement the function

function bw2 = thin (bw)

  lut1 = makelut (@thin_fun1, 3);
  lut2 = makelut (@thin_fun2, 3);

  bw1 = applylut (bw, lut1);
  bw2 = applylut (bw1, lut2);
  end

The LUTs I get are different from the LUTs in current version of bwmorph, and the final command is different.

Attached a revised version of bwmorph.
Please review.

(file #45596, file #45597, file #45598, file #45599)

Avinoam Kalma <avinoam>
Project Member
Fri 07 Dec 2018 03:05:18 PM UTC, comment #1: 

Tu my understanding this is not really a positive indication
of bug in Octaveforge(image)::bwmorph ...

Hence, dear Mr. Kalma, can you please verify (show some evidence)
that the results computed by the Software from The Mathworks
Company are really correct (according to the widely
adopted/accepted definitions).

Perhaps you will have to inspect the source code of
the corresponding MATLAB toolbox (and/or to talk to
the Developers at MathWorks).

Please share the full details you are able to collect
on the algorithmic procedure and its applicaton parameters
(which kind of structuring elements are used; are there any
heuristics in place (e.g. in order to speed up computation) ...
and so on)

thank you

Anonymous
Thu 06 Dec 2018 04:42:48 PM UTC, original submission:  

Running the script

H = false (7,7);
H(2:3,2:3) = 1;
H(5:6,5:6) = 1;
a = bwmorph (H, 'thin', 1)
H(4:6,4:6) = 1;
b = bwmorph (H, 'thin', 1)

I get

Matlab:

a =

   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   0
   0   0   0   0   1   0   0
   0   0   0   0   0   0   0


b =

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

Octave:

a =

  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
  0  0  0  0  0  1  0
  0  0  0  0  0  0  0

b =

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

Avinoam Kalma <avinoam>
Project Member

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #45684:  bwmorph_V3.patch added by avinoam (13KiB - application/octet-stream)
file #45675:  bwmorph_V2.patch added by avinoam (13KiB - application/octet-stream)
file #45639:  bwmorph_V1.patch added by avinoam (11KiB - application/octet-stream)
file #45596:  thin.patch added by avinoam (6KiB - application/octet-stream)
file #45597:  thin_fun2.m added by avinoam (696B - application/octet-stream)
file #45598:  thin_fun1.m added by avinoam (699B - application/octet-stream)
file #45599:  thin.m added by avinoam (800B - application/octet-stream)

 

Depends on the following items: None found

Items that depend on this one: None found

 

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

    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 project members can vote.

     

     

     

     

    Follow 13 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2018-12-24 avinoam Open/ClosedOpen Closed
    2018-12-18 avinoam StatusPatch Submitted Fixed
    2018-12-17 avinoam Attached File- Added bwmorph_V3.patch, #45684
    2018-12-15 avinoam Attached File- Added bwmorph_V2.patch, #45675
        StatusNone Patch Submitted
    2018-12-12 avinoam Attached File- Added bwmorph_V1.patch, #45639
    2018-12-08 avinoam Attached File- Added thin.patch, #45596
        Attached File- Added thin_fun2.m, #45597
        Attached File- Added thin_fun1.m, #45598
        Attached File- Added thin.m, #45599
    2018-12-06 avinoam Summary [octave forge] (image) b = bwmorph (BW, 'thin', 1) is not Maltab compatible [octave forge] (image) b = bwmorph (BW, 'thin', 1) is not Matlab compatible
    2018-12-06 avinoam Carbon-Copy- Added hardy
        Carbon-Copy- Added carandraug

    Back to the top


    Powered by Savane 3.9