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

 
 

bug #56141: [octave forge] (image) bwmorph option 'endpoints' not implemented

Submitter:  Nicholas Jankowski <nrjank>
Submitted:  Mon 15 Apr 2019 06:17:45 PM UTC
   
 
Category:  Octave Package Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Feature Request
Status:  Fixed Assigned to:  None
Originator Name:  Nicholas Jankowski Open/Closed:  * Closed
Release:  * 5.1.0 Operating System:  * Any
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Thu 30 May 2019 05:56:27 PM UTC, comment #23: 

I have (eventually) done some very rough testing:

  • all tests in bwmorph pass (except for the two known test failures)
  • the code implementation and general approach behind look reasonable to me
Hartmut <hardy>
Thu 30 May 2019 03:39:15 AM UTC, comment #22: 
Avinoam Kalma <avinoam>
Group Member
Sat 11 May 2019 06:10:01 PM UTC, comment #21: 

Ping...

Please review. Thanks :-)

Avinoam Kalma <avinoam>
Group Member
Fri 03 May 2019 08:33:03 PM UTC, comment #20: 

Attached my updated cs. Please review

(file #46863)

Avinoam Kalma <avinoam>
Group Member
Sun 28 Apr 2019 08:22:01 PM UTC, comment #19: 

The definition of the algorithm is simple: a pixel is not removed if its value is 1, and he has 0-7 consecutive neighbours, which means, that the ones in the ring around it are all connected in 4-neigbourhood.

I am attaching:
1. A short program that implements this algorithm
2. A program which created the LUT (endpoints.m)
3. The LUT
4. diff of bwmorph

It is not completed yet, since I need to add some tests. They will be taked from the comments below.

Please review (nrjank, Hartmut and Carne). Thanks.


(file #46847, file #46848, file #46849, file #46850)

Avinoam Kalma <avinoam>
Group Member
Tue 23 Apr 2019 10:13:48 PM UTC, comment #18: 

ok. I'll make a manual one.  Will also start trying to find a logic scheme that can work like those LUT files. Will hope to have something you can look at after vacation. Enjoy!

Nicholas Jankowski <nrjank>
Group Member
Tue 23 Apr 2019 08:11:26 PM UTC, comment #17: 

Sounds good.
But, since I have found some logic in this operator, (also without understanding it, see comment #12)
I would like also to code it like the LUT files in http://hg.code.sf.net/p/octave/image/file/34db32781b12/devel
I will be glad if you will create also a LUT, so we could check each other.

BTW, I am going on a vacation, so I will be able to do it only next week.

Thanks

Avinoam Kalma <avinoam>
Group Member
Tue 23 Apr 2019 04:21:16 PM UTC, comment #16: 

I ran a quick script to test 3x3 arrays output in matlab. (fed it 0 to 511 converted to 9-digit binary, reshaped to 3x3, recorded which ones had 1 or 0 in the returned value).

so I could use this output in a manual function fed to makelut to generate a look-up table that will emulate matlab's endpoints behavior. I'm hesitant to do it that way because it's more-or-less flying blind without understanding the ruleset behind the LUT. We wouldn't be able to troubleshoot anything, but it would guarantee we are compatible with (this version of) matlab.

Here are the 57 3x3 arrays that produce a '1' from find endpoints:


>> bw_endpoints_true
bw_endpoints_true(:,:,1) =
     0     0     0
     0     1     0
     0     0     0
bw_endpoints_true(:,:,2) =
     0     0     0
     0     1     0
     0     0     1
bw_endpoints_true(:,:,3) =
     0     0     0
     0     1     1
     0     0     0
bw_endpoints_true(:,:,4) =
     0     0     0
     0     1     1
     0     0     1
bw_endpoints_true(:,:,5) =
     0     0     1
     0     1     0
     0     0     0
bw_endpoints_true(:,:,6) =
     0     0     1
     0     1     1
     0     0     0
bw_endpoints_true(:,:,7) =
     0     0     1
     0     1     1
     0     0     1
bw_endpoints_true(:,:,8) =
     0     0     0
     0     1     0
     0     1     0
bw_endpoints_true(:,:,9) =
     0     0     0
     0     1     0
     0     1     1
bw_endpoints_true(:,:,10) =
     0     0     0
     0     1     1
     0     1     1
bw_endpoints_true(:,:,11) =
     0     0     1
     0     1     1
     0     1     1
bw_endpoints_true(:,:,12) =
     0     1     0
     0     1     0
     0     0     0
bw_endpoints_true(:,:,13) =
     0     1     1
     0     1     0
     0     0     0
bw_endpoints_true(:,:,14) =
     0     1     1
     0     1     1
     0     0     0
bw_endpoints_true(:,:,15) =
     0     1     1
     0     1     1
     0     0     1
bw_endpoints_true(:,:,16) =
     0     1     1
     0     1     1
     0     1     1
bw_endpoints_true(:,:,17) =
     0     0     0
     0     1     0
     1     0     0
bw_endpoints_true(:,:,18) =
     0     0     0
     0     1     0
     1     1     0
bw_endpoints_true(:,:,19) =
     0     0     0
     0     1     0
     1     1     1
bw_endpoints_true(:,:,20) =
     0     0     0
     0     1     1
     1     1     1
bw_endpoints_true(:,:,21) =
     0     0     1
     0     1     1
     1     1     1
bw_endpoints_true(:,:,22) =
     0     1     1
     0     1     1
     1     1     1
bw_endpoints_true(:,:,23) =
     0     0     0
     1     1     0
     0     0     0
bw_endpoints_true(:,:,24) =
     0     0     0
     1     1     0
     1     0     0
bw_endpoints_true(:,:,25) =
     0     0     0
     1     1     0
     1     1     0
bw_endpoints_true(:,:,26) =
     0     0     0
     1     1     0
     1     1     1
bw_endpoints_true(:,:,27) =
     0     0     0
     1     1     1
     1     1     1
bw_endpoints_true(:,:,28) =
     0     0     1
     1     1     1
     1     1     1
bw_endpoints_true(:,:,29) =
     0     1     1
     1     1     1
     1     1     1
bw_endpoints_true(:,:,30) =
     1     0     0
     0     1     0
     0     0     0
bw_endpoints_true(:,:,31) =
     1     1     0
     0     1     0
     0     0     0
bw_endpoints_true(:,:,32) =
     1     1     1
     0     1     0
     0     0     0
bw_endpoints_true(:,:,33) =
     1     1     1
     0     1     1
     0     0     0
bw_endpoints_true(:,:,34) =
     1     1     1
     0     1     1
     0     0     1
bw_endpoints_true(:,:,35) =
     1     1     1
     0     1     1
     0     1     1
bw_endpoints_true(:,:,36) =
     1     1     1
     0     1     1
     1     1     1
bw_endpoints_true(:,:,37) =
     1     0     0
     1     1     0
     0     0     0
bw_endpoints_true(:,:,38) =
     1     1     0
     1     1     0
     0     0     0
bw_endpoints_true(:,:,39) =
     1     1     1
     1     1     0
     0     0     0
bw_endpoints_true(:,:,40) =
     1     1     1
     1     1     1
     0     0     0
bw_endpoints_true(:,:,41) =
     1     1     1
     1     1     1
     0     0     1
bw_endpoints_true(:,:,42) =
     1     1     1
     1     1     1
     0     1     1
bw_endpoints_true(:,:,43) =
     1     0     0
     1     1     0
     1     0     0
bw_endpoints_true(:,:,44) =
     1     0     0
     1     1     0
     1     1     0
bw_endpoints_true(:,:,45) =
     1     0     0
     1     1     0
     1     1     1
bw_endpoints_true(:,:,46) =
     1     0     0
     1     1     1
     1     1     1
bw_endpoints_true(:,:,47) =
     1     0     1
     1     1     1
     1     1     1
bw_endpoints_true(:,:,48) =
     1     1     0
     1     1     0
     1     0     0
bw_endpoints_true(:,:,49) =
     1     1     1
     1     1     0
     1     0     0
bw_endpoints_true(:,:,50) =
     1     1     1
     1     1     1
     1     0     0
bw_endpoints_true(:,:,51) =
     1     1     1
     1     1     1
     1     0     1
bw_endpoints_true(:,:,52) =
     1     1     0
     1     1     0
     1     1     0
bw_endpoints_true(:,:,53) =
     1     1     0
     1     1     0
     1     1     1
bw_endpoints_true(:,:,54) =
     1     1     0
     1     1     1
     1     1     1
bw_endpoints_true(:,:,55) =
     1     1     1
     1     1     0
     1     1     0
bw_endpoints_true(:,:,56) =
     1     1     1
     1     1     0
     1     1     1
bw_endpoints_true(:,:,57) =
     1     1     1
     1     1     1
     1     1     0


Nicholas Jankowski <nrjank>
Group Member
Tue 23 Apr 2019 02:12:19 AM UTC, comment #15: 

I spent a little time looking at any other algorithms, and haven't found many. One thing a number of people on stackexchange pointed to was called the 'hit and miss' algorithm. Even after reading about it I don't get the meaning of the name, but the description is at:

http://homepages.inf.ed.ac.uk/rbf/HIPR2/hitmiss.htm

according to them, endpoints of a skeleton (1 pixel wide) image is accomplished by applying all four rotations of the :


X X X
0 1 0
0 0 0


stencil (X indicates you don't care what that cell is, any combination of 1s and 0s will pass)

This makes perfect sense, and I could code up a quick function to generate a LUT, but it should give a zero for the first example in Comment #7 and the second example in Comment #11.

Nicholas Jankowski <nrjank>
Group Member
Mon 22 Apr 2019 07:19:30 PM UTC, comment #14: 

Some how I write 0 and it changed to 1.
sorry for the noise

Avinoam Kalma <avinoam>
Group Member
Mon 22 Apr 2019 07:18:10 PM UTC, comment #13: 

A small correction

1. neigbours to the center pixel (1 case) - the pixel remains:

should be

  1. neigbours to the center pixel (1 case) - the pixel remains:


Avinoam Kalma <avinoam>
Group Member
Mon 22 Apr 2019 07:16:26 PM UTC, comment #12: 

I have tried to undestand the logic inside this function.
I took a 3x3 image, put 1 in the middle, 0/1 in other places, and see the results of bwmorph.
There are 256 such binary images:

  1. neigbours to the center pixel (1 case) - the pixel remains:



A = [0, 0, 0; 0, 1, 0; 0, 0, 0];
bwmorph(A,'endpoints') = A;


1 neigbours (8 cases) - the pixel remains:


A = [1, 0, 0; 0, 1, 0; 0, 0, 0];
B = bwmorph(A,'endpoints') = A


2 neigbours (28 cases):

here it is a little bit complicated. If the two neigbours
are adjacent in the same row or column (4-neighbours)
the pixel remains, otherwise it is removed.

3 neigbours (56 cases):

if the 3 pixels are in the same row or column, or create
with the internal pixel a 2x2 block (e.g. [1 1 0; 1 1 0; 0 0 0]), the pixel remains, otherwise it is removed.

7 neighbours (8 cases): the pixel remains

8 neighbours (1 case): the pixe is removed.

So, I figure out 1 + 8 + 28 + 56 + 8 + 1 = 102 out of 256.

left to  figure out:
4 neigbours - 70 cases
5 neigbours - 56 cases
6 neigbours - 28 cases
 

Avinoam Kalma <avinoam>
Group Member
Mon 22 Apr 2019 02:34:07 AM UTC, comment #11: 

more oddities.

using the same B as before:


>> B
B =
  3×14 logical array
   0   0   0   0   0   0   0   0   0   0   0   0   0   0
   0   0   1   1   1   1   1   1   1   1   1   1   0   0
   0   0   0   0   0   0   0   0   0   0   0   0   0   0
>> blah1 = bwmorph(B,'endpoints')
blah1 =
  3×14 logical array
   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   1   0   0
   0   0   0   0   0   0   0   0   0   0   0   0   0   0
>> ~B
ans =
  3×14 logical array
   1   1   1   1   1   1   1   1   1   1   1   1   1   1
   1   1   0   0   0   0   0   0   0   0   0   0   1   1
   1   1   1   1   1   1   1   1   1   1   1   1   1   1
>> blah2 = bwmorph(~B,'endpoints')
blah2 =
  3×14 logical array
   1   0   0   0   0   0   0   0   0   0   0   0   0   1
   1   1   0   0   0   0   0   0   0   0   0   0   1   1
   1   0   0   0   0   0   0   0   0   0   0   0   0   1


Nicholas Jankowski <nrjank>
Group Member
Sun 21 Apr 2019 06:23:09 PM UTC, comment #10: 

I haven't found a simple ruleset yet. I'm honestly wondering if they just sat down and manually went through the 128 cell iterations to generate a lookup table.

It could be they only generated the ruleset for 1 pixel wide (skeletonized) images, and that other images falling outside this definition are unintentional oddities.

Nicholas Jankowski <nrjank>
Group Member
Sun 21 Apr 2019 04:20:33 PM UTC, comment #9: 

Looking in your examples in comment #7, I can't understand matlab behavior.

In the second example, all points have 2 neighbours, and all of removed, which agrees with the initial algorithm, but in the first example, all the points have 3, 5 or 8 neighbours, and only the one with 8 neighbours is removed.

In the example of comment #6, the only points that left are with 1 or 7 neighbours.

Also, in Matlab documentation it is written: "To find end points, the image must be skeletonized".
What does it mean? That in binary images which are not a result of a skeletonization process the result does not have to be the endpoints?

Avinoam Kalma <avinoam>
Group Member
Sun 21 Apr 2019 12:57:38 AM UTC, comment #8: 

if anyone can come up with a good 3x3 stencil / or set of functions I can pass to a lookup table generator that works for these examples, I'd appreciate it.

Nicholas Jankowski <nrjank>
Group Member
Sun 21 Apr 2019 12:40:52 AM UTC, comment #7: 

going to capture a few more here:


>> A = [0 0 0 0 0; 0 1 1 1 0; 0 1 1 1 0; 0 1 1 1 0; 0 0 0 0 0]
A =
     0     0     0     0     0
     0     1     1     1     0
     0     1     1     1     0
     0     1     1     1     0
     0     0     0     0     0
>> B = bwmorph(A,'endpoints')
B =
  5×5 logical array
   0   0   0   0   0
   0   1   1   1   0
   0   1   0   1   0
   0   1   1   1   0
   0   0   0   0   0
>> B = bwmorph(B,'endpoints')
B =
  5×5 logical array
   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
>> 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]
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
>> B = bwmorph(A,'endpoints')
B =
  5×5 logical array
   0   0   0   0   0
   0   0   1   0   0
   0   1   0   1   0
   0   0   1   0   0
   0   0   0   0   0
>> B = bwmorph(B,'endpoints')
B =
  5×5 logical array
   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
>> A = [0 0 0 0 0; 0 1 0 0 0; 0 0 1 0 0; 0 0 0 1 0; 0 0 0 0 0]
A =
     0     0     0     0     0
     0     1     0     0     0
     0     0     1     0     0
     0     0     0     1     0
     0     0     0     0     0
>> B = bwmorph(A,'endpoints')
B =
  5×5 logical array
   0   0   0   0   0
   0   1   0   0   0
   0   0   0   0   0
   0   0   0   1   0
   0   0   0   0   0
>> B = bwmorph(B,'endpoints')
B =
  5×5 logical array
   0   0   0   0   0
   0   1   0   0   0
   0   0   0   0   0
   0   0   0   1   0
   0   0   0   0   0


Nicholas Jankowski <nrjank>
Group Member
Sat 20 Apr 2019 10:35:04 PM UTC, comment #6: 

ok, this method is a bit too simple.  was able to test against matlab and at least two problems:

this one fails:


>> 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]
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


>> bwout = bwmorph(A,'endpoints)

Matlab:

bwout =

  5×5 logical array

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


Octave:

bwout =

  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


the current method runs into problems if one pixel from a corner.

Second, I looked at the test 'skel' image again on their help page, and it looked like matlab puts an endpoint on the intersection between the two lines at the bottom.  zooming in, it appears that that section has the following form:


>> logical(A(195:201,141:148))
ans =
  7×8 logical array
   0   0   0   0   0   0   0   0
   1   1   0   0   0   0   1   1
   0   0   1   1   1   1   0   0
   0   0   0   1   1   0   0   0
   0   0   1   1   1   1   0   0
   0   1   0   0   0   0   1   0
   1   0   0   0   0   0   0   1

>> bwout = bwmorph(A(195:201,141:148),'endpoints')
bwout =
  7×8 logical array
   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   1   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   1


it appears that within the same image, it doesn't care if you go from 1 to 0 or 0 to 1, it considers both as endpoints within the same image if it is only connected to one of the same type.  Odd, but for compatibility I'll see if I can come up with an easy fix.

Nicholas Jankowski <nrjank>
Group Member
Sat 20 Apr 2019 09:35:20 PM UTC, comment #5: 

Will.do. I don't have MATLAB access at the moment. Does anyone know if it preserves single pixels as endpoints?  An isolated pixel would get zeroed out with my function.

A quick test would be to run the endpoints function twice and see if the output is all zeros.

Nicholas Jankowski <nrjank>
Group Member
Sat 20 Apr 2019 08:35:54 PM UTC, comment #4: 

The code in comment #2 looks very good.
When you make a changeset, please add BIST(s). Thanks :-)

Avinoam Kalma <avinoam>
Group Member
Sat 20 Apr 2019 08:23:41 PM UTC, comment #3: 

by "peeked at that function" I meant I looked again at Octave's bwmorph.  don't want anyone to get the wrong idea.

Nicholas Jankowski <nrjank>
Group Member
Sat 20 Apr 2019 08:22:30 PM UTC, comment #2: 

ok, I didn't dive into that python code, but just playing with your 3 step process the following seems to work:



%stencil
>> A = [1,1,1;1,0,1;1,1,1]
A =

   1   1   1
   1   0   1
   1   1   1

%single line image
>> B = logical([0,0,0,0,0,0,0,0,0,0,0,0,0,0;...
                0,0,1,1,1,1,1,1,1,1,1,1,0,0;...
                0,0,0,0,0,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  0  1  1  1  1  1  1  1  1  1  1  0  0
  0  0  0  0  0  0  0  0  0  0  0  0  0  0

%find number of neighbors
>> C = convn(B,A,"same")
C =

   0   1   2   3   3   3   3   3   3   3   3   2   1   0
   0   1   1   2   2   2   2   2   2   2   2   1   1   0
   0   1   2   3   3   3   3   3   3   3   3   2   1   0


%find pixels from image with only 1 neighbor
>> D = and(B,C==1)
D =

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


tested it on the skeleton image on the matlab help page and it seems to find the endpoints properly.

I just peeked at that function.  seems it expects each case to output a morph anonymous function that is then applied to the image at the end. So I need to turn that into a one line function.

I think this should work:



>> morph = @(x) and(x,conv(x,[1,1,1;1,0,1;1,1,1],'same')==1);

>> morph(B)
ans =

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


I'll work up a patch.

Nicholas Jankowski <nrjank>
Group Member
Thu 18 Apr 2019 09:14:24 PM UTC, comment #1: 

There is a simple python code in
https://gist.github.com/bmabey/4dd36d9938b83742a88b6f68ac1901a6
that computes bwmorph (I, 'endpoints'). It has 3 steps:

1. convolve the image with [1 1 1; 1 0 1; 1 1 1]). The result is number of neighbours of each pixel.
2. Setting zero in all zero pixels in the original image (i.e. count the neigbours of each non zero elements).
3. Find the pixels with only 1 neighbour.

What do you think about this algorithm?

Avinoam Kalma <avinoam>
Group Member
Mon 15 Apr 2019 06:17:45 PM UTC, original submission:  

Help list request noted that the bwmorph function produces an error.  Verified that call with 'endpoints' results in:

error: bwmorph: unknown OPERATION 'endpoints' requested

lines 313-314 show:


#    case "endpoints"
#      ## not implemented


Adding this bug report as a feature/compatibility request. Matlab help does not indicate what algorithm is used, but does give a graphical depiction of what should happen, and mentions that it should follow a 'skel' operation (so the Pratt reference might be of use).

https://www.mathworks.com/help/images/ref/bwmorph.html

Nicholas Jankowski <nrjank>
Group Member

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #46863:  endpoints.cs added by avinoam (8KiB - application/octet-stream)
file #46847:  bwmorph.diff added by avinoam (2KiB - application/octet-stream)
file #46848:  endpoints.m added by avinoam (387B - application/octet-stream)
file #46849:  __endpoints_fun__.m added by avinoam (3KiB - application/octet-stream)
file #46850:  lut.txt added by avinoam (1KiB - text/plain)

 

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 jwe (Updated the item)
  • -email is unavailable- added by avinoam (Posted a comment)
  • -email is unavailable- added by avinoam
  • -email is unavailable- added by avinoam
  • -email is unavailable- added by nrjank (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 12 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2019-05-30 avinoam StatusPatch Submitted Fixed
        Open/ClosedOpen Closed
    2019-05-03 avinoam Attached File- Added endpoints.cs, #46863
        StatusConfirmed Patch Submitted
    2019-04-28 avinoam Attached File- Added bwmorph.diff, #46847
        Attached File- Added endpoints.m, #46848
        Attached File- Added _endpoints_fun_.m, #46849
        Attached File- Added lut.txt, #46850
    2019-04-20 jwe Item GroupMatlab Compatibility Feature Request
    2019-04-18 avinoam StatusNone Confirmed
        Carbon-Copy- Added carandraug
        Carbon-Copy- Added hardy

    Back to the top

    Powered by Savane 3.13-d3ae.
    Corresponding source code