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

 
 

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

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

Add a New Comment(Rich Markup)
   

You are not logged in

Please log in, so followups can be emailed to you.

 

( Jump to the original submission)

Sat 11 May 2019 06:10:01 PM UTC, comment #21:

Ping...

Please review. Thanks :-)

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

Attached my updated cs. Please review

(file #46863)

Avinoam Kalma <avinoam>
Project 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>
Project 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>
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>
Project 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:

Nicholas Jankowski <nrjank>
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 :

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

1 neigbours (8 cases) - the pixel remains:

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>
Project Member
Mon 22 Apr 2019 02:34:07 AM UTC, comment #11:

more oddities.

using the same B as before:

Nicholas Jankowski <nrjank>
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>
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>
Project 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>
Sun 21 Apr 2019 12:40:52 AM UTC, comment #7:

going to capture a few more here:

Nicholas Jankowski <nrjank>
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:

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:

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

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:

I'll work up a patch.

Nicholas Jankowski <nrjank>
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>
Project 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:

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>

 

(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 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)
  •  

    Do you think this task is very important?
    If so, you can add your encouragement to it.
    This task has 0 encouragements so far.

    Only project members can vote.

     

     

     

    Follow 10 latest changes.

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