patchGNU Octave - Patches: patch #9077, image package: new function...

 
 

patch #9077: image package: new function imfill.m

Submitter:  Hartmut <hardy>
Submitted:  Mon 08 Aug 2016 08:32:56 PM UTC
   
 
Category:  Forge : new function Priority:  5 - Normal
Status:  Done Privacy:  Public
Assigned to:  None Open/Closed:  Closed
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Mon 03 Oct 2016 07:00:16 PM UTC, comment #20: 

Thanks for the explanations. So this seems to be finished now :)

Hartmut <hardy>
Mon 03 Oct 2016 05:04:10 PM UTC, comment #19: 
  • line 22: You have added one of the two supported (but in Matlab undocumented) syntax versions: imfill(I, 'holes'). Then it would probably a good idea to add the second supported but undocumented version as well: imfill(I, CONN, 'holes').
  • line 28: two typos
  • line 90: in this comment, we need to remove the first half: "imfill(BW, CONN)", this is no valid syntax.


Done, done, and done. Thank you http://hg.code.sf.net/p/octave/image/rev/c998fe65b8fb

  • I have seen how you avoid my stupy "padding", very nice :)
  • on several occasions you are calling the two helper functions check_loc and the set_nonborder_pixels with the full variable img as parameter. Isn't this creating a second memory copy of the (potentially huge) image data in img? I was intentionally only calling check_loc with "size(img)" instead of "img" in order to save this memory. And since your "fancy" way of avoiding the "stupid" padding all around, was motivated by saving memory, shouldn't we try to avoid this second full copy of the image data here as well? (But maybe my understanding of when Octave will do a memory copy is not exhaustive...)


Two different cases:

  • check_loc - This does not create a new copy of the image.  Octave does copy on write https://en.wikipedia.org/wiki/Copy-on-write which means that if you pass a variable to a function in the list of arguments, no copy is made until that function changes the variable. Since check_loc never modifies the image (it only uses img to get the size), no copy of the image is ever made.  There was no technical need for that change, but it allows to use "ndims (img)" instead of "numel (sz)" which is a bit clearer on the meaning.


  • set_nonborder_pixels - This creates a copy of the image but it's a copy that you will use. There is no extra copy when you return the created marker, and you will need at the same time as the original (mask) when calling imreconstruct.



  ## marker is a copy but we really need it to call imreconstruct
  marker = set_nonborder_pixels (mask, conn, false);
  imreconstruct (marker, mask, conn);

[...]

function marker = set_nonborder_pixels (img, conn, val)
  [...]
  marker = img;
  ## marker, is img, which is mask on the caller.  No copy has been made yet.
  marker(nonborder_idx{:}) = val;
  ## This triggered a copy.  This is returned to the caller, no new copy
  ## will be made
endfunction


But the issue of extra copies on the previous 2d solution using padarray is not at that step.  The code now also makes a copy, and the extra memory used for the padding is usually negligible (except for images with many dimensions where some of the dimensions are "short").  The issue was the copy triggered by the the unpadding.

Carnë Draug <carandraug>
Group Member
Sun 02 Oct 2016 07:33:53 PM UTC, comment #18: 

Thanks a lot for carefully adjusting my code to Octave coding guidelines, and reviewing it.

I went through the new version of the code (the latest version in the official repo) and will make some comments below. Otherwise I am fine with the code, as long as the tests still pass :)

Here are my comments:

  • line 22: You have added one of the two supported (but in Matlab undocumented) syntax versions: imfill(I, 'holes'). Then it would probably a good idea to add the second supported but undocumented version as well: imfill(I, CONN, 'holes').
  • line 28: two typos
  • line 90: in this comment, we need to remove the first half: "imfill(BW, CONN)", this is no valid syntax.
  • I have seen how you avoid my stupy "padding", very nice :)
  • on several occasions you are calling the two helper functions check_loc and the set_nonborder_pixels with the full variable img as parameter. Isn't this creating a second memory copy of the (potentially huge) image data in img? I was intentionally only calling check_loc with "size(img)" instead of "img" in order to save this memory. And since your "fancy" way of avoiding the "stupid" padding all around, was motivated by saving memory, shouldn't we try to avoid this second full copy of the image data here as well? (But maybe my understanding of when Octave will do a memory copy is not exhaustive...)


Otherwise I am fine with releasing this :)

Hartmut <hardy>
Sat 01 Oct 2016 10:46:43 PM UTC, comment #17: 

On top of your last file, I changed the line ending to linux style and then made the following changes:

https://bitbucket.org/carandraug/octave-image/commits/94cd74b32a7c77885b7931fc3f8acc79b8220cc5

I left the comments about the changes there and the commit there so you can see the changes. They are minor and mostly whitespace and addition of brackets.  I have folded this on top of you file and rebased it. The final cset is pushed as

http://hg.code.sf.net/p/octave/image/rev/3d617c42bfe7

I then added ND support with

http://hg.code.sf.net/p/octave/image/rev/2807d044df89

Let me know if you find any issue with it. I hope I can get a release of the package with this change done soon (later this week).

Carnë Draug <carandraug>
Group Member
Wed 17 Aug 2016 07:18:59 PM UTC, comment #16: 

The chanages from your previous commit are here https://bitbucket.org/carandraug/octave-image/commits/916c51dc2838435aabbab2b55e2a5c7eca1d03cb?at=new-function-imfill-patch-9077


> It seems a bit of a "overkill" to me to assign warning ids to my imfill warnings, only to silence them. I found another "workaround" way to achive this: I just renamed the corresponding "!test" lines into "!warning" lines. If you have "ethical" problems with this and prefer warning messages during the tests, then just undo this change again.


The "%!warning" blocks are to test if a piece of code does throw an expected warning.  I forgot that you don't actually need a warning id, you can simply turn all warnings off for the test.

> Am an not sure about the advantages of the proposed different way of dealing it. Do you want to be faster, or use less memory? I think both results would not be significantly obtained by this.


It uses less memory. As the number of dimensions go up, the size of padding makes a big difference. It also involves a lot of copying internally which makes things slower and require a lot more memory temporarily. I'm already not happy that imreconstruct does more padding internally but in that case the alternative I can think of is to check for coordinates at each pixel which would be a performance killer.  Also, half of that more complex code will be required to get the indexing for ND anyway.

Enjoy the vacations. This should be merged before the 3 weeks.

Carnë Draug <carandraug>
Group Member
Wed 17 Aug 2016 06:23:56 PM UTC, comment #15: 

I have had a look at your comments in bitbucket (link from comment #13) and you comment on how to silence warnings in comment #14.

As a result I've produced a new version of my PATCH (V5 in the filename). My comments on this:

  • It seems a bit of a "overkill" to me to assign warning ids to my imfill warnings, only to silence them. I found another "workaround" way to achive this: I just renamed the corresponding "!test" lines into "!warning" lines. If you have "ethical" problems with this and prefer warning messages during the tests, then just undo this change again.


  • Regarding the input checking of the "holes" option: I didn't know the command validatestring before. I like your proposal and included it into my latest patch.


  • Regarding the proposed alternative to full border padding:
    • I do like my version with full border padding better! The code is clearer to read, it is therefore better to maintain, and I am pretty sure this will also work in unforseen corner cases.
    • Am an not sure about the advantages of the proposed different way of dealing it. Do you want to be faster, or use less memory? I think both results would not be significantly obtained by this.
    • Nevertheless, I do NOT object when you prefer to change this part into your proposed version where the padding depends on the given connectivity definition. But this is currently not included in my latest patch. And please do check beforehand that this alternative also works fine, even for your mentioned corner cases.
    • I think it should be equally easy to transform this "full border padding" into its Nd counterpart. Just use the vector [1, 1, 1, ...] instead of the current [1,1] in the padarray command. And take as many 1s as there are dimensions in the image.


What comes to my mind what is (at least) necessary to have full Nd image support:

  • Nd border padding as discussed above.
  • Also the removing of this padded border afterwards. The Nd version of "(I2(2:end-1, 2:end-1)"
  • Any input checking that currently assumes 2D images. For example the check of the LOCATIONs via "ndims(opt2)<=2" (twice in the code). Maybe somewhere else...
  • The checking of the given LOCATION indices are matrix indices (done in the subfunction check_loc). The Nd version of "size(loc, 2)==2".
  • The conversion from matrix indices to linear indices in the subfunction check_loc.
  • add tests with Nd images, some also with Nd connectivity definitions.


I will be offline now for 3 weeks, during my summer vacation. I would be happy to see this new imfill function in the next release of the image package, afterwards :)

Cheers!



(file #38242)

Hartmut <hardy>
Tue 16 Aug 2016 10:43:05 PM UTC, comment #14: 

To silence warnings, a warning needs to have an id. Then you could do:


%!test
%!  warning ("off", "warningid", "local");
%!  assert (foo_that_throws_warning (), ...)


I will add the ND support I mentioned below, and add more tests with extra dimensions so that this goes in the next release too.

Carnë Draug <carandraug>
Group Member
Tue 16 Aug 2016 10:38:27 PM UTC, comment #13: 

I pushed your new commit here https://bitbucket.org/carandraug/octave-image/commits/e04ba70324a14e43c50e0de49ac83fab68041670?at=new-function-imfill-patch-9077

so we can see exactly what changed since your previous commit. I left my comments there.

While padarray will work, would be better if we could avoid padding at all. I left a snippet there that checks which dimension matters for connectivity. Then we create indices for the image based on that so that it includes "1:end" or "2:end-1" based on the previous check. Then just use that for setting the value of non-border elements.

This should add the support for ND images so it's all done.

Carnë Draug <carandraug>
Group Member
Tue 16 Aug 2016 08:19:41 PM UTC, comment #12: 

I liked very much viewing your comments directly between the code lines in the bitbucket repository. But since I am not very "fluent" in version control systems I have not started yet to create my own account on bitbucket to share code there, for the time being.

Nevertheless I have prepared a new PATCH (with V4 in its name). The patch before (V3) could only deal with connectivity settings of 4 and 8. I thought from the Matlab help page that this was the full Matlab behavior. But now I checked, and the Matlab version of imfill can also deal with more exotic definitions of connectivity.

So this V4 version of imfill does one further step of adopting the core algorithm: It pads both the marker and the mask image with +Inf (and removes the former -I border of the marker image). This seems to work at least on the examples you mentioned so far. (Those examples are now also included as tests.)

This new patch (V4) also tries to include all comments mentioned in the bitbucket link of comment #11.

Let me know if you have further comments on this. (But after tomorrow evening I will be offline during my 3 weeks of vacation.)

Note: There are still the three code lines with TODO in it, because I don't know how to silence expected warnings during tests.

(file #38233)

Hartmut <hardy>
Mon 15 Aug 2016 01:18:45 AM UTC, comment #11: 

The only real issue now is about connectivities other than 4 and 8.  Your check is too rigorous.  It should allow connectivity of class double and also things such as "eye (3)". And disabling the checks, it shows a bug on the approach.

I have made more detailed comments online, including a code example showing the bug.

I pushed your changes to my draft clone of the Octave image repository.  I think this will make it simple for me to review changes and if you also have a clone there, for you to ask for review. Instead of preparing a whole new cset, I can see only what changed and you don't have to export and upload a new file each time.  Don't worry about having multiple commits and commit message now. In the end, I'll fold all into one with your name (the trick is on setting the repository in bitbucket as non-publishing on the settings).

See https://bitbucket.org/carandraug/octave-image/commits/400498c55fb6622a7664e37ab8f6eb07f3c3f3ec or checkout bookmark "new-function-imfill-patch-9077"

https://bitbucket.org/carandraug/octave-image/commits/branch/new-function-imfill-patch-9077

Carnë Draug <carandraug>
Group Member
Thu 11 Aug 2016 07:42:24 PM UTC, comment #10: 

note: There a 3 lines with TODO in the patch. I don't know how to silence (intentional) warning messages during function calls in tests.

Hartmut <hardy>
Thu 11 Aug 2016 07:41:00 PM UTC, comment #9: 

Here is an new version (V3) of my PATCH. I've tried to include all hints and wishes from comment #8.

Several remarks:

  • input check "if (nargin == 1 .... && islogical (I))": For imfill(bw) Matlab goes into an interactive mode, which is not supported by my new imfill currently. That's why I throw an error here. Whereas imfill(I) is a shortcut for imfill(I,'holes') and does hole filling on grayscale images.
  • If the Matlab version of imfill gets locations outside of the image, then it throws a warning, deletes the improper locations, and proceedes with the remaining correct locations. Even if no correct location remain at all, it stays in the operation mode for imfill(...,LOCATIONS) and does not switch to the operation mode for imfill(...).


I am happy to hear that you, Carne, plan to add ND image support to imfill. That will make our new imfill version equally powerful as the Matlab version.

Let me know if there is anything else to improve on this patch.

(file #38180)

Hartmut <hardy>
Thu 11 Aug 2016 12:14:42 AM UTC, comment #8: 

After looking at it, I believe I can add the support for nd arrays myself afterwards without much trouble.

Some points:

  • you don't need to do:



    if islogical (I)
        mask = uint8 (I);
    else
        mask = I;
    endif


you can leave mask as logical. The issue is on assigning the value of -Inf later, but you can check for the class at that point and set it to false if it's logical, -Inf otherwise. By the way you already have the text for each step right before the first step. So don't repeat them, each line already matches one step.

  • during input check, if (nargin == 1 .... && islogical (I)) you give an error. Should it not throw an error always or is matlab not interactive for grayscale images at all?


  • you can start with if nargin < 1 || nargin > 3 .  Use print_usage instead of an error message for this type of failure.


  • what does Matlab do if any of the locations is outside of the image? And can you add a test for that?


  • Can you add a test with concentric rings? And images with 1 and 2 rows only?


  • a minor improvement on code:



## don't write:
marker(2:rows(marker)-1, 2:columns(marker)-1) = -Inf;
## write
marker(2:end-1, 2:end-1) = -Inf;


There's some other coding guidelines that would be nice to follow but I can adjust them myself later.

Carnë Draug <carandraug>
Group Member
Wed 10 Aug 2016 12:08:48 PM UTC, comment #7: 

typo: on Matlab for large images IMFILL is faster than bwfill by a factor of 2.

Hartmut <hardy>
Wed 10 Aug 2016 12:05:48 PM UTC, comment #6: 

I've also done some quick timing testing on Matlab (not the same pc though) with the test script of comment #5.
Results:

  • On Matlab imfill and bwfill have mostly the same speed compared to each other.
    • For small images bwfill is faster by a factor of 2
    • For large images bwfill is faster by a factor of 2.


  • The Octave implementation is not much slower than the Matlab implementation.
    • For SMALL images Octave's bwfill is much faster than both Matlab commands,
    • and Octave's imfill is slower than Matlab by factor of ~1.5.
    • For LARGE images both Octave commands are faster than the Matlab version of bwfill,
    • but (still for large images) both Octave's commands are slower than the Matlab version of imfill by a factor of ~1.5).
Hartmut <hardy>
Tue 09 Aug 2016 08:43:28 PM UTC, comment #5: 

I've done some timing tests  (all on the 'holes' option):

  • for small images imfill is slower than bwfill, in worst case it's  ~14 times slower on my pc
  • for bigger images, imfill gets better compared to bwfill.
  • for very big images, roughtly around 4 Megapixels, imfill starts to be even faster than bwfill, for connectivity 4. (For connectivity 8 the crossover seems to be at 10 Megapixel images.)


Here is my test script if you want to play around yourself:

% test timing of new imfill.m in comparison to bwfill.cc
% on 2D binary images
clear, close all

% set test conditions
conn = 4; % connectivity: 4 or 8
n_repeat = 3;
%im_sizes = [10 15; 30 50; 100 150]; % imfill is factor ~14 slower (for conn=4 and 8)
%im_sizes = [30 50; 100 150; 300 500];  % imfill is factor ~6 slower (for conn=4 and 8)
%im_sizes = [1000 1500; 3000 5000]; % imfill is factor 1.3 faster for conn=4 and factor 1.0 for conn=8
im_sizes = [10 15; 30 50; 100 150; 300 500;1000 1500; 3000 5000];
im_white_ratios = [0.05 0.1 0.25 0.5 0.8];

% loop over all test conditions
ns=size(im_sizes, 1);
ms=length(im_white_ratios);
timing_im = zeros(ns, ms);
timing_bw = zeros(ns, ms);
im_white_factors = 0.5 .* 1./im_white_ratios;
for n = 1:ns
    im_size = im_sizes(n,:);
    for m = 1:ms
        im_white_factor = im_white_factors(m);
        clear t;
        for r = 1:n_repeat
            bw = logical(round(im_white_factor.*rand(im_size)));
            tic;
            bw2 = imfill(bw, conn, 'holes');
            t_im(r) = toc;
            tic;
            bw2 = bwfill(bw, 'holes', conn);
            t_bw(r) = toc;
        end
        timing_im(n,m) = mean(t_im);
        timing_bw(n,m) = mean(t_bw);
    end
    avg_timing_im(n) = mean(timing_im(n,:));
    avg_timing_bw(n) = mean(timing_bw(n,:));
end

mean_im = mean(timing_im(:))
mean_bw = mean(timing_bw(:))
ration_im_over_bw = mean_im / mean_bw;

figure, imagesc(timing_im);
title(['timing of imfill.m (mean=',num2str(mean_im*1e3),'ms)']);
xlabel('white ratio'); ylabel('image size');

figure, imagesc(timing_bw);
title(['timing of bwfill.cc (mean=',num2str(mean_bw*1e3),'ms)']);
xlabel('white ratio'); ylabel('image size');

close all;

num_pix = im_sizes(:,1) .* im_sizes(:,2);
figure, loglog(num_pix, avg_timing_im, 'r', num_pix, avg_timing_bw, 'b');
legend('imfill', 'bwfill', 'location', 'northwest');
xlabel('number of image pixels [MPix]');
ylabel('avg. calculation time [s]');
grid on;


What do we conclude? Do we want to use bwfill instead of imreconstruct in imfill? What about very big images (where timing is more painful)? Do we stick with imreconstruct in imfill? Do we switch depending on input image size (would feel akward to me)?

Hartmut <hardy>
Tue 09 Aug 2016 07:50:45 PM UTC, comment #4: 

imreconsruct is written in C++ but does a lot more work to handle N dimensions. Also I never got around to write the specialization for bool arrays. So that's two optimization missing compared to bwfill and I expect it to be slower. I'm just curious how much slower.

Carnë Draug <carandraug>
Group Member
Tue 09 Aug 2016 07:23:13 PM UTC, comment #3: 

Yes, if imreconstruct can deal with ND IMAGES, then the "core 4 lines" of code in my new imfill.m can also deal with it. (1. imcomplement, 2. create marker, 3. imreconstruct, 4. imcomplement).

Nevertheless I have not implemented Nd support so far, because it only involves much kind of coding that I'm not so good in:

  • even more complicated checking and sorting of input parameters
  • Nd support for the indexing in step 2 (marker creation)
  • Nd support in the transformation of Nd-matrix indices to Nd linear indices
  • some kind of defining neighborhoods (connectivity parameter) for Nd images.


If you are more familiar with those tasks, feel free to add the Nd feature. On the "image processing algorithm" side, this new imfill.m is ready for it.

I will try to do some TIMING TESTS for 2D binary images between bwfill.cc and the new imfill.m and report here. (I hope imfill.m can stand the competition, because its core function imreconstruct also is coded in C...)

Hartmut <hardy>
Tue 09 Aug 2016 07:09:33 PM UTC, comment #2: 

I will take a look at this tomorrow. But since imreconstruct handles ND images, can't your implementation of imfill be able to handle them?

Also, how does this imfill compares in performance to the existing bwfill for 2d binary images? We have some specializations for 2d images in other functions because they work much faster.

Carnë Draug <carandraug>
Group Member
Tue 09 Aug 2016 07:02:13 PM UTC, comment #1: 

Here is a new version of my PATCH (V2) with an improved version of imfill.m

The other (V1) version had some funny "automatic guessing of logical images" in it, that I ment to read in the Matlab documentation of imfill.m. But tests showed me that the Matlab version of the command also does NOT do this funny guessing, so I've removed this feature from my implementation as well.

(file #38158)

Hartmut <hardy>
Mon 08 Aug 2016 08:32:56 PM UTC, original submission:  

Here is a new function for the Octave image package: imfill.m

It does hole filling on binary and grayscale 2D images, and is compatible to the Matlab version of imfill.m. (It does currently not support Nd images or interactive use.)

The algorithms is based on morphological reconstruction, so this new m-file makes extensive use of imreconstruct.cc. The algorithm is taken from the book of Gonzales & Woods "Digital Image processing". Details in the patch itself.

I originally intended to only write a wrapper around bwfill.cc (see bug #46124), but it turned out (because of the already existing imreconstruct.cc) to be much easier to use morphological reconstruction instead. (The Matlab help page for imfill also says that their imfill uses morphological reconstruction.) Tests on some simple input images gave me Matlab compatible result images.

Let me know any feedback you might have on this PATCH.


Hartmut <hardy>

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #38242:  new_imfill_V5.patch added by hardy (16KiB - text/x-diff)
file #38233:  new_imfill_V4.patch added by hardy (16KiB - text/x-diff)
file #38180:  new_imfill_V3.patch added by hardy (14KiB - text/x-diff)
file #38158:  new_imfill_V2.patch added by hardy (12KiB - text/x-diff)
file #38150:  new_imfill.patch added by hardy (13KiB - text/x-diff)

 

Depends on the following items: None found

Items that depend on this one: None found

 

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

    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 logged-in users can vote.

     

    Follow 9 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2016-10-01 carandraug StatusNone Done
        Open/ClosedOpen Closed
    2016-08-17 hardy Attached File- Added new_imfill_V5.patch, #38242
    2016-08-16 hardy Attached File- Added new_imfill_V4.patch, #38233
    2016-08-11 hardy Attached File- Added new_imfill_V3.patch, #38180
    2016-08-09 hardy Attached File- Added new_imfill_V2.patch, #38158
    2016-08-08 hardy Attached File- Added new_imfill.patch, #38150
        Carbon-Copy- Added carandraug
        Carbon-Copy- Added avinoam

    Back to the top

    Powered by Savane 3.13-f8d8.
    Corresponding source code