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

 
 

bug #62452: [octave forge] (image) bwmorph spur produces wrong result

Submitter:  None
Submitted:  Fri 13 May 2022 12:32:56 PM UTC
   
 
Category:  Octave Package Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Incorrect Result
Status:  Patch Reviewed Assigned to:  None
Originator Name:  Anonymous Originator Email:  -email is unavailable-
Open/Closed:  * Open Release:  * other
Operating System:  * Any Fixed Release:  None
Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Sat 24 Sep 2022 12:25:47 PM UTC, comment #23: 

Thanks for dealing with makelut and applylut, Avinoam. I think we could deal with this makelut/applylut issue in the existing report bug #62978. No need to have even more bug numbers ;)

Hartmut <hardy>
Sat 24 Sep 2022 11:41:03 AM UTC, comment #22: 

Thanks, Hartmut for testing this and for your valuable comments.

Indeed there is a problem in Applylut, see bug #62978.
Currently, both Applylut and makelut are not Matlab compatible,
though they are compatible with each other.
I will open a report regarding makelut, and a fix that fixes
makelut & applylut. Probably this will cause more changes in regionpropls and maybe elsewhere.

Avinoam Kalma <avinoam>
Group Member
Sat 24 Sep 2022 09:41:59 AM UTC, comment #21: 

I have tested the code change of applylut.m, as mentioned in comment #20. This code change acutally means to rotate the filter kernel by 180 degrees.

Unfortunatelly it does not seem to be that easy. After doing this code change, the first unit test ("2-by-2 test") in applylut.m fails. The result there should be [1 1 1], this is also what Matlab gives, but with the suggested code change, the new Octave result becomes [1 1 0] and therefore the unit test in applylut.m rightfully fails.

I have not checked if this code change (comment #20) improves anything in bwmorph, as intended. (I expect it will.) But I think we canNOT do this code change because it would generate a regression in applylut, and probably generate much more issues than it solves.

Hartmut <hardy>
Mon 29 Aug 2022 03:44:25 PM UTC, comment #20: 

Regarding comment #13:

Hartmut, could you please if the incompatibilities are still exist, if you replace line 42 of applylut.m


 A=LUT(filter2(w,BW)+1);


by


 A = LUT (conv2 (BW, w, 'same') + 1);


Thanks.

Avinoam Kalma <avinoam>
Group Member
Sun 28 Aug 2022 09:50:14 PM UTC, comment #19: 

Thanks, Hartmut for confirming this.
I will open a new bug report. I wrote it here because this is the reason for the incompatibilities you have mentioned in comment #13.

I have checked that for all 3x3, 4x4, and 5x5 binary images, the Octave result is the same as the Matlab result, and all the incompatibilities will disappear after applylut will be fixed.

Avinoam Kalma <avinoam>
Group Member
Sun 28 Aug 2022 09:36:48 PM UTC, comment #18: 

@Avinoam: Yes, I can confirm your observation in comment #7. But please open a NEW bug report for this observations, because it seems to be a misbehavior of the applylut function in the image package (and not of bwmorph).

Hartmut <hardy>
Sun 28 Aug 2022 02:40:50 PM UTC, comment #17: 

Trying to debug this routine, I have found that


a = [
    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   1   0   0
   0   0   0   0   0   0
   0   0   1   0   0   0
   0   0   1   0   0   0
   0   0   0   0   0   0
   0   0   1   0   0   0
   0   0   0   1   0   0
   0   0   0   0   0   0
   0   0   0   1   0   0
   0   0   1   0   0   0
   0   0   0   0   0   0
   0   0   0   0   0   0
];
a = logical(a);
lut2 = false (512, 1);
lut2(19) = true;

applylut (a, lut2)


MATLAB and Octave results are different.
Can someone confirm this?

Avinoam Kalma <avinoam>
Group Member
Thu 25 Aug 2022 04:10:24 PM UTC, comment #16: 

sorry, my mistake. Ignore previous comment

Avinoam Kalma <avinoam>
Group Member
Thu 25 Aug 2022 04:01:32 PM UTC, comment #15: 

Regarding the line


+      morph = @(x) xor (x, applylut (applylut (padarray (x, [1 1], true), ...
+                        lut1), lut2)(2:end-1, 2:end-1));


Maybe it should be



+      morph = @(x) xor (x(2:end-1, 2:end-1), applylut (applylut (padarray (x, [1 1], true), ...
+                        lut1), lut2));


?

Avinoam Kalma <avinoam>
Group Member
Mon 08 Aug 2022 04:48:10 AM UTC, comment #14: 


Thanks, Hartmut,
I will review the patch.

Avinoam Kalma <avinoam>
Group Member
Sun 07 Aug 2022 03:36:54 PM UTC, comment #13: 

I have had a look at the code suggested in comment #12. And it seems to perform in a much more Matlab compatible way compared to before. Even the existing xtest now passes with it. Thanks a lot for preparing and submitting this code.

Therefore I have prepared a patch file for this code (V1) from the algorithm in comment #12 and BISTs from several comments before. These new BISTs all pass.

Please review the attached V1 patch.

Nevertheless, there are some incompatibilities left over:

  • The last example in comment #7 and 8 still gives a different result.
  • The examples in comment #5 and 6 still give a different result.


I would be fine with pushing the code change as it is today to the image repo. But if someone can improve on the above mentioned leftover incompatiblities it would be even nicer.



(file #53542)

Hartmut <hardy>
Wed 18 May 2022 04:40:44 PM UTC, comment #12: 

I figured out the following generating function:

1 . Pad the image with the value 1.
2.  Use the structuring elements described in Wikipedia [1] to find the end points and remove them. If the end-points image consists of two elements connnected components like this:


    [1 1] , [1; 1] , [1 0; 0 1] , [0 1; 1 0]


- For the vertical pattern keep the top element.
- For the horizontal pattern keep the left element.
- For the diagonal patterns keep the right element.
  However it seems that MATLAB has a random behavior. For example in the case of the diagonal pattern it sometimes keeps the left element and sometime keeps the right element.

3. Keep sigle pixels.
4. Remove the padded border.

The generating function would be:


bw = padarray (bw, [1 1], true);

endpoints_fcn = @(x) x(5) && ((x(2) && all (! x([4 6 7 8 9])))...
  ||(x(4) && all (! x([2 3 6 8 9])))...
  ||(x(8) && all (! x([1 2 3 4 6])))...
  ||(x(6) && all (! x([1 2 4 7 8])))...
  ||(sum(x(:)) == 2 && any (x(:) & [1 0 1;0 0 0;1 0 1](:))));

endpoints_lut = makelut(endpoints_fcn, 3);

endpoints_image = applylut(bw, lut);

endpoints_keep_fcn = @(x) (x(5) && sum(x(:)) == 2 ...
  && any (x(:) & [1 0 0;0 0 1;1 1 0](:)))...          # two elements pattern
  || (x(5) && sum(x(:)) == 1);                        # single pixel

endpoints_keep_lut = makelut(endpoints_keep_fcn, 3);

remaining_endpoints_image = applylut(endpoints_image, endpoints_keep_lut);

bw = xor(bw, remaining_endpoints_image);

bw = bw(2:end-1, 2:end-1);


By precomputing the look-up table the function will be reduced to (to be used in bwmorph.m):
 

lut1 = false (512, 1);
lut2 = false (512, 1);

lut1 ([18,19,20,21,23,24,25,26,49,53,81,89,90,145,209,273,305,309,401,465]) = true;
lut2 ([17, 19, 25, 81, 273]) = true;

morph = @(x) xor (x, applylut (applylut (padarray (x, [1 1], true), lut1), lut2)(2:end-1, 2:end-1));


[1] https://en.wikipedia.org/wiki/Pruning_(morphology)#Structuring_Elements

Anonymous
Wed 18 May 2022 01:30:39 PM UTC, comment #11: 

i haven't looked at any of the references, do we expect this one operates on a 9 point stencil (absent the 4 or 6pt edges)?  I remember we had to brute force bug #56141 in the absense of a sensible generating function...

Nicholas Jankowski <nrjank>
Group Member
Wed 18 May 2022 04:56:27 AM UTC, comment #10: 



a =

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


b = bwmorph (a, 'spur')

b =

  5×4 logical array

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


Avinoam Kalma <avinoam>
Group Member
Wed 18 May 2022 03:59:11 AM UTC, comment #9: 

I'm curious to know what is the behavior with this pattern:


a = [
  1 1 1 1
  1 0 0 1
  1 0 1 1
  1 0 0 1
  1 1 1 1
]

b = bwmorph (a, 'spur')


Anonymous
Wed 18 May 2022 03:29:27 AM UTC, comment #8: 


>> for idx=1:8, b{idx},end
ans =
  3×3 logical array
   1   0   1
   0   0   0
   1   0   1
ans =
  5×5 logical array
   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
ans =
  4×4 logical array
   1   1   0   1
   0   0   0   1
   1   0   0   0
   1   0   1   1
ans =
  4×4 logical array
   1   0   1   1
   1   0   0   0
   0   0   0   1
   1   1   0   1
ans =
  5×5 logical array
   0   1   0   0   0
   0   0   0   0   1
   0   0   0   0   0
   1   0   0   0   0
   0   0   0   1   0
ans =
  5×5 logical array
   0   1   1   0   0
   0   0   0   0   1
   1   0   0   0   1
   1   0   0   0   0
   0   0   1   1   0
ans =
  8×8 logical array
   1   0   0   1   0   0   1   0
   0   0   0   0   0   0   0   1
   0   0   0   0   0   0   0   0
   1   0   0   1   0   0   0   0
   0   0   0   0   0   0   0   1
   0   0   0   0   0   0   0   0
   1   0   0   0   0   0   0   0
   0   1   0   0   1   0   0   1
ans =
  8×8 logical array
   0   1   0   0   1   0   0   1
   1   0   0   0   0   0   0   0
   0   0   0   0   0   0   0   0
   0   0   0   0   1   0   0   1
   1   0   0   0   0   0   0   0
   0   0   0   0   0   0   0   0
   0   0   0   0   0   0   0   1
   1   0   0   1   0   0   1   0


Nicholas Jankowski <nrjank>
Group Member
Wed 18 May 2022 03:21:29 AM UTC, comment #7: 

Thanks!
It seems that the behavior is different on borders. Could you please run this on MATLAB?


a = {[
  1 0 1
  0 0 0
  1 0 1
];[
  0 0 1 0 0
  0 0 0 0 0
  1 0 1 0 1
  0 0 0 0 0
  0 0 1 0 0
];[
  1 1 0 1
  0 0 0 1
  1 0 0 0
  1 0 1 1
];[
  1 0 1 1
  1 0 0 0
  0 0 0 1
  1 1 0 1
];[
  0 1 0 0 0
  0 1 0 1 1
  0 0 0 0 0
  1 1 0 1 0
  0 0 0 1 0
];[
  0 1 1 0 0
  0 0 0 0 1
  1 0 0 0 1
  1 0 0 0 0
  0 0 1 1 0
];[
  1 0 0 1 0 0 1 0
  0 1 0 0 1 0 0 1
  0 0 0 0 0 0 0 0
  1 0 0 1 0 0 1 0
  0 1 0 0 1 0 0 1
  0 0 0 0 0 0 0 0
  1 0 0 1 0 0 1 0
  0 1 0 0 1 0 0 1
];[
  0 1 0 0 1 0 0 1
  1 0 0 1 0 0 1 0
  0 0 0 0 0 0 0 0
  0 1 0 0 1 0 0 1
  1 0 0 1 0 0 1 0
  0 0 0 0 0 0 0 0
  0 1 0 0 1 0 0 1
  1 0 0 1 0 0 1 0
]}

b = cellfun (@(x) {bwmorph(x, 'spur')}, a)


Anonymous
Wed 18 May 2022 02:41:55 AM UTC, comment #6: 


b =

  14×4 logical array

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


Nicholas Jankowski <nrjank>
Group Member
Wed 18 May 2022 02:39:52 AM UTC, comment #5: 

Thanks!
A more complete test to be run on MATLAB:


 a = [
   0 0 0 0
   0 1 0 0
   0 0 0 0
   0 1 1 0
   0 0 0 0
   0 1 0 0
   0 1 0 0
   0 0 0 0
   0 1 0 0
   0 0 1 0
   0 0 0 0
   0 0 1 0
   0 1 0 0
   0 0 0 0
 ]

 b = bwmorph(a, 'spur')


Anonymous
Tue 17 May 2022 03:43:57 PM UTC, comment #4: 

here is matlab's output operating on your array:


>> a = [0 0 0 0;1 0 0 0;0 1 0 0;0 0 0 0]
a =
     0     0     0     0
     1     0     0     0
     0     1     0     0
     0     0     0     0
>> b = bwmorph(a, 'spur')
b =
  4×4 logical array
   0   0   0   0
   1   0   0   0
   0   0   0   0
   0   0   0   0
>> c = bwmorph(b, 'spur')
c =
  4×4 logical array
   0   0   0   0
   0   0   0   0
   0   0   0   0
   0   0   0   0


from the first operation, it seems to select 'interior' pixels to be trimmed first. it also balks at ambiguities like:


>> d = [0 0 0 0;1 0 0 0;1 0 0 0;0 0 0 0]
d =
     0     0     0     0
     1     0     0     0
     1     0     0     0
     0     0     0     0

>> e = bwmorph(d,'spur')
e =
  4×4 logical array
   0   0   0   0
   1   0   0   0
   1   0   0   0
   0   0   0   0



Nicholas Jankowski <nrjank>
Group Member
Tue 17 May 2022 05:24:05 AM UTC, comment #3: 

Thanks for reporting this.

What is the exact definition of spur?

As stated in comment #0:
"It sets pixel to 0 if it has only one eight-connected pixel in its neighbourhood."

but in the case of


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


two pixels have one eight-connected pixel in their neighbourhood, but only one is removed, unless, the first pixel is marked as pixel to delete, does not count for the second one.

Avinoam Kalma <avinoam>
Group Member
Fri 13 May 2022 07:38:14 PM UTC, comment #2: 

confirmed.  verifying that matlab 2022a produces the expected output for b.

Nicholas Jankowski <nrjank>
Group Member
Fri 13 May 2022 05:46:49 PM UTC, comment #1: 

adding people to cc

Hartmut <hardy>
Fri 13 May 2022 12:32:56 PM UTC, original submission:  

Documentation of the image package -> the function bwmorph -> the option 'spur' says that:

> Performs a remove spur operation. It sets pixel to 0 if it has only one eight-connected pixel in its neighbourhood.


Given the following example:


a = [ 1 1 1 1 1
      1 0 0 0 1
      1 0 1 0 1
      1 0 1 0 1
      1 1 1 1 1];

b = bwmorph(a, 'spur');


It should produce:


b = [ 1 1 1 1 1
      1 0 0 0 1
      1 0 0 0 1
      1 0 1 0 1
      1 1 1 1 1];


But currently it returns the same array as the input.

I think changing the line 515 of bwmorph.m from


lut([18, 21, 81, 273]) = false;


to


lut([18, 19, 21, 25, 49, 81, 145, 273]) = false;


will solve the problem.

Moreover in the comments it is assumed that the function handle that makes 'spur' lookup table is:


lut = makelut(inline("xor(x(2,2),(sum((x&[0,1,0;1,0,1;0,1,0])(:))==0) ...
      &&(sum((x&[1,0,1;0,0,0;1,0,1])(:))==1)&&x(2,2))","x"),3);


But I believe that the correct generating function is:


lut = makelut(@(x) x(5) & (sum(x(:)) != 2), 3);


Anonymous

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #53542:  bwmorph_spur_V1.patch added by hardy (5KiB - text/x-patch)

 

Depends on the following items: None found

Items that depend on this one: None found

 

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

    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-09-24 avinoam StatusPatch Submitted Patch Reviewed
        Originator Name Anonymous
    2022-08-08 avinoam StatusConfirmed Patch Submitted
        Release7.1.0 other
    2022-08-07 hardy Attached File- Added bwmorph_spur_V1.patch, #53542
    2022-05-28 ineiev Carbon-CopyRemoved 0 -
    2022-05-13 nrjank StatusNone Confirmed
        Summarybwmorph spur produces wrong result [octave forge] (image) bwmorph spur produces wrong result

    Back to the top

    Powered by Savane 3.13-f8d8.
    Corresponding source code