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

 
 

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

Submitted by:  None
Submitted on:  Fri 13 May 2022 12:32:56 PM UTC
 
Category:  Octave Forge Package Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Incorrect Result
Status:  Confirmed Assigned to:  None
Originator Name:  Originator Email:  -email is unavailable-
Open/Closed:  * Open Release:  * 7.1.0
Operating System:  * Any
* Mandatory Fields

Add a New Comment (Rich Markup)
   

Comment Type & Canned Response:
       

 

( Jump to the original submission )

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>
Project 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>
Project 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>
Project 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>
Project 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>
Project 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>
Project 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>
Project 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:
   

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by None (Posted a comment)
  • -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 project members can vote.

     

     

     

     

    Follow 2 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    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.9