bugGNU Octave - Bugs: bug #46099, image package: edge(I,'canny')...

 
 

bug #46099: image package: edge(I,'canny') gives very bad quality results

Submitter:  Hartmut <hardy>
Submitted:  Thu 01 Oct 2015 08:31:40 PM UTC
   
 
Category:  Octave Package Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Incorrect Result
Status:  Fixed Assigned to:  None
Originator Name:  Open/Closed:  * Closed
Release:  * other Operating System:  * Any
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Mon 07 Dec 2015 08:15:05 PM UTC, comment #19: 

Closing bug report then. Thank you for improving this a lot.

I don't think a comment about the failing tests is necessary, there's plenty of them on the image package like that. If anything I comment the opposite, i.e., a passing test that is Matlab incompatible on purpose is worth of note.

Carnë Draug <carandraug>
Group Member
Mon 07 Dec 2015 08:10:06 PM UTC, comment #18: 

From my side you can CLOSE this bug report now.

I can (only) see the following issues still open:

  • Your new tests on the returned threshold VALUES are not Matlab compatible. Do we want to mention this somewhere in a comment near the tests?
  • The AUTOMATIC calculation of THRESHOLD values in Matlab seems to be very fancy in some cases. (This seems to be only an incompatibility of the Canny method in edge.m.) But I am not willing to further investigate this just to perfectly mimic the Matlab behavior, here. The current Octave implementation of the Canny edge detection gives good results of the same quality as in Matlab. And the Octave version of the Canny edge detector also does some reasonable estimation of an automatic threshold. I think this level of compatibility is good enough for most use cases (at least it is good enough for my use cases).
  • There is still a DIFFERENT BUG REPORT open (bug #46547) that deals with the Canny edge detection method. This bug might or might not be already solved with our recent patches as well.
Hartmut <hardy>
Mon 07 Dec 2015 07:49:30 PM UTC, comment #17: 


> I intentionally made the filtering along the two dimensions seperatly, because this should execute significantly FASTER. The gaussian filter become quite big in size for the Canny detector (default is already 16x16). The results of your 2D-gaussian filter will probably be 100% the same. But please double check the run time (also with bigger values of sigma) before pushing your 2D-filter patch. Even sigma values of several hundreds (e.g. 300) are a reasonable use case! This is because this parameter determines the size of the edges you are looking for.


Ah, yes. I understand the issue now with performance.  And you're right, one dimension at a time seems much faster for all the sigma cases I tried.  There are two missing functions imgaussfilt, and imgaussfilt3 which should probably do it.

> Nice to hear that even the THRESHOLD values are Matlab compatible for my two tests.
>
> About the AUTOMATIC THRESHOLDS not always being Matlab compatible: I think I have seen this happen. But I do not have a (failing) test at hand for this, sorry. (Yes, I meant the thresholds that are used by edge.m, when the user does not give any explicit threshold values.)


We are having some missunderstanding.  The thresholded image for your test cases was Matlab compatible but not the computed threshold values (second return argument).  The tests you submitted did not even try to set them or test them.

I couldn't figure out from Matlab documentation how they pick those threshold values.  So maybe the actual edge methods is whole Matlab compatible and the difference is only the threshold values?

Do you plan on further improving this or submitting more tests or should I close this bug report?

> About the CONNECTIVITY of the Canny edge results: You are right, when I look at some results with my input images, then all contours are 8-connected, meaning they sometimes do have only a diagonal connection. This means the background is only separated into two separate regions, if you use 4-connectivity for the background. But I have no insight what this means for your tested implementation with imreconstruct.


I'm guessing a bug on the hysteresis on nonmax_supress...

Carnë Draug <carandraug>
Group Member
Mon 07 Dec 2015 07:33:47 PM UTC, comment #16: 

Nice to hear my patch made it :)

Some comments:

  • I intentionally made the filtering along the two dimensions seperatly, because this should execute significantly FASTER. The gaussian filter become quite big in size for the Canny detector (default is already 16x16). The results of your 2D-gaussian filter will probably be 100% the same. But please double check the run time (also with bigger values of sigma) before pushing your 2D-filter patch. Even sigma values of several hundreds (e.g. 300) are a reasonable use case! This is because this parameter determines the size of the edges you are looking for.
  • Nice to hear that even the THRESHOLD values are Matlab compatible for my two tests.
  • About the AUTOMATIC THRESHOLDS not always being Matlab compatible: I think I have seen this happen. But I do not have a (failing) test at hand for this, sorry. (Yes, I meant the thresholds that are used by edge.m, when the user does not give any explicit threshold values.)
  • About the CONNECTIVITY of the Canny edge results: You are right, when I look at some results with my input images, then all contours are 8-connected, meaning they sometimes do have only a diagonal connection. This means the background is only separated into two separate regions, if you use 4-connectivity for the background. But I have no insight what this means for your tested implementation with imreconstruct.


Hartmut <hardy>
Mon 07 Dec 2015 06:48:07 PM UTC, comment #15: 

I have pushed your changes with your tests (I made some changes to the tests and included the Matlab threshold values).

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

Your tests seemed to be Matlab compatible (passes both your tests) but you claim there's some differences (could you add such a test?). Maybe it's because of the way it guesses the threshold values?

One thing I noticed was that you explicitly filter the image once per dimension but did not explain why not use a 2d filter.  I have this patch which seems to not break anything:


-      ## Gaussian filtering to change the edge scale (treat dimensions seperatly)
+      ## Gaussian filtering to change the edge scale
       len = 8 * ceil (sigma);
-      x = -0.5 * (len-1) : 0.5 * (len-1);
-      gauss = exp (-(x.^2)/(2*sigma^2));
-      gauss = gauss ./ sum (gauss);
-      J = imfilter (im, gauss, "replicate");
-      J = imfilter (J, gauss', "replicate");
+      J = imfilter (im, fspecial ("gaussian", [len len], sigma), "replicate");


Did I miss anything that I should not push it?

> @Carne: Before I forget it: The results of the Canny edge detector are supposed to be 4-connected contours, not 8-connected contours. Maybe this can explain your differences when using imreconstruct instead of nonmax_suppress.


Looking into nonmax_supress it seems to be looking in the diagonal values (45 and 135 degrees), so I'm assuming it is connectivity 8.

Carnë Draug <carandraug>
Group Member
Sat 05 Dec 2015 09:31:46 PM UTC, comment #14: 

Here is a new PATCH for this bug:

  • This patch includes two new TESTs for the Canny edge detection method. Those tests will fail if my current patch of bug #45568 is NOT applied before (because then all results will be shifted downwards and to the right by one pixel).
  • This patch (identically) includes my previous patch in this bug report, concerning the edge DIRECTION calculation in nonmax_supress.cc
  • This patch should make the "Canny" method of edge.m mostly Matlab COMPATIBLE. (There will only be slight differences when using automatic threshold computation, because this seems to be extraordinary fancy in Matlab...)


This patch might also fix the issue in bug #46547. (I wasn't able to test this any more.)

Please give me feedback if this patch works as I assume. (And don't forget to apply the patch of bug #45568 beforehand...)



(file #35650)

Hartmut <hardy>
Sat 05 Dec 2015 08:05:40 PM UTC, comment #13: 

@Carne: Before I forget it: The results of the Canny edge detector are supposed to be 4-connected contours, not 8-connected contours. Maybe this can explain your differences when using imreconstruct instead of nonmax_suppress.

Hartmut <hardy>
Fri 04 Dec 2015 10:32:29 PM UTC, comment #12: 

I've supplied a patch for bug #45568. This seemed easier than working around this padding issue on my own. As soon as this patch is accepted I will continue here.

Hartmut <hardy>
Fri 04 Dec 2015 08:47:57 PM UTC, comment #11: 

Unfortunatelly bug #45568 happens also when using the "conv" option in imfilter. I will go on and try to do the padding on my own...

Hartmut <hardy>
Fri 04 Dec 2015 08:24:45 PM UTC, comment #10: 


> As reason for this I found bug #45568 "imfilter incompatible to MATLAB for even filter width".


If I remember correctly, that bug only happens when using "corr" method of imfilter (default).  It should disappear if you use the "conv" option which would give the same results if your filter is symmetric. I have found that issue before and my solution is to skip imfilter altogether and use padarray and convn myself.  That's one extra line of code. It should also be faster and will make it easier to support ND input in the future.  May not be suitable for your case.

Carnë Draug <carandraug>
Group Member
Fri 04 Dec 2015 08:08:49 PM UTC, comment #9: 

I have an improved implementation of the Canny edge detector in Octave nearly ready. It seems to also be very well Matlab compatible. But currently my results are all shifted by one pixel downwards and to the right. As reason for this I found bug #45568 "imfilter incompatible to MATLAB for even filter width".

This bug impacts the implementation of my Canny edge detector because the first step in a Canny edge detection is a filtering with an even sized filter (a Gaussian filter). And I would prefer to do this filtering step with "imfilter" instead of the currently used (but in Matlab not even existing) function "imsmooth('gaussian', ...').

How should I proceed?
(a) Wait for bug #45568 to be fixed?
(b) work around this bug (i.e. shift my results one pixel upwards and to the left)?
(c) leave it as is? (This would results in tests that aren't Matlab compatible.)
(d) other suggestions?

I don't like the ideas (b) and (c) too much, to be honest. But how long could it take to fix bug #45568?

Hartmut <hardy>
Thu 03 Dec 2015 02:45:38 PM UTC, comment #8: 


> @Carne: Your simplification looks reasonable to me. (But what would be benefit? execution time?)


The benefit would be on reduced maintenance, to replace 30 lines of untested C++ (the part of nonmax_supress that performs hysteresis) with 2 lines of m code with well tested functions.  And by then removing the nonmax_supress code that did it, there's no longer two pieces of code around with almost equal purposes.

Maybe using imreconstruct is not a very clear simplication and bwselect would be a better fit (but bwselect also does not have tests). Also I get different results from nonmax_supress's hysteresis than I get from imreconstruct and bwselect so I'm questioning if nonmax_supress hysteresis is correct.

There seems to be a very small increase time by making use of imreconstruct though, but I'd rather spend the time on speeding up imreconstruct for logical input (a simple algorithm, already described in the source as TODO http://hg.code.sf.net/p/octave/image/file/90a52e024691/src/imreconstruct.cc#l285 ) than figuring out nonmax_supress.

> I am on the way to make the Canny method of edge.m much more Matlab compatible, and to add some tests to it. I should be able to supply a patch in a couple of days. (It will necessarily also cover bug #46547). So if you are patient enough, you could test your simplicition step then.


That is great. Thank you for working on this. By the way, although nonmax_supress is not clearly marked as private (it does not have the double underscores on the name), it is meant as such (according to its help text) so you can just remove it or change it as much as you want.

Carnë Draug <carandraug>
Group Member
Wed 02 Dec 2015 10:18:13 PM UTC, comment #7: 

@Carne: Your simplification looks reasonable to me. (But what would be benefit? execution time?)

I am on the way to make the Canny method of edge.m much more Matlab compatible, and to add some tests to it. I should be able to supply a patch in a couple of days. (It will necessarily also cover bug #46547). So if you are patient enough, you could test your simplicition step then.

Hartmut <hardy>
Wed 02 Dec 2015 06:08:20 PM UTC, comment #6: 

While trying to get some tests for canny (we have none at the moment so it makes it tricky to test anything), I came up with a simplication of the hysteresis step.  It seems to me that it can be replaced with imreconstruct (or bwselect), like so:


-      bw = nonmax_supress(Es, Eo, thresh(1), thresh(2));
+      sup = nonmax_supress (Es, Eo);
+      bw = imreconstruct (sup > thresh(2), sup > thresh(1), 8); # hysteresis


My understanding of hysteresis is that this should be equivalent but running some tests, I do not get the same values.  It may be a mistake on my part or it may be that part of the bad quality results are also on the hysteresis step.

Carnë Draug <carandraug>
Group Member
Sun 29 Nov 2015 08:40:58 PM UTC, comment #5: 

See bug #46570 for first test for edge.

Avinoam Kalma <avinoam>
Group Member
Thu 26 Nov 2015 08:55:43 PM UTC, comment #4: 

@Hartmut:

Currently edge() does not have any test. If you add some tests, specially for the bug you are reporting here, I will push your patch.

Carnë Draug <carandraug>
Group Member
Thu 26 Nov 2015 07:35:45 PM UTC, comment #3: 

I think the behavior described in comment #2 is fully independent of the original topic of this bug report. That's why I opened a separate bug report for this new topic (bug #46547). Please let's continue the discussion about the new topic there.

Hartmut <hardy>
Thu 26 Nov 2015 11:15:51 AM UTC, comment #2: 

I'm evaluating an image binarization code (originaly developed for Matlab) with Octave (4.0.0) and image package (2.4.1). After some investigation on why I'm getting worse results with Octave than with Matlab (R2012b), I've found that edge function with 'Canny' method outputs a much noisier result with Octave than with Matlab. In order to give an example, I've run the following code with both software:


clear, close all;
I = imread('sample2.png');
thresholds = [5.2742e-004 0.3899];
BW = edge(I, 'Canny', thresholds);
imwrite(BW, 'result_edge_canny_sample2.png');


As one can see in the attached files, "Octave_result_edge_canny_sample2.png" is much noisier than "ML2012b_result_edge_canny_sample2.png". As a result, the binarized image (generated by the image binarization code, which uses edge function with 'Canny' method) is also noisy and almost useless.


Anonymous
Sun 04 Oct 2015 06:49:07 PM UTC, comment #1: 

I have finally found the source of this bug!

I will attach a PATCH to fully solve this issue, as well as the result of image('canny') when using this patch ("Octave+OrientationPatch_result_canny.png"). Now the contour is properly closed :)

With this patch the results of edge('canny') will be different from the versions before. But the results from the old version were mostly unusable, anyways.

Please test this patch and let me know any feedback. Otherwise I would be happy to see this fix in the next bug fixing release of the image package :)

(file #35061,

Hartmut <hardy>
Thu 01 Oct 2015 08:31:40 PM UTC, original submission:  

Here is a simple script to show the behavior. It uses the file "cannysample.png" to be reproducible (attached to this post, it has only a noisy blob in the center). This happens with the latest Octave (4.0.0) and image package (2.4.0):


clear, close all;
I = imread('cannysample.png');
imshow(I);

sigma = 5;
thresholds = [];
[BW, t] = edge(I, 'Canny', thresholds, sigma);
t
figure, imshow(BW);
imwrite(BW, 'result_canny.png');


Running this script in Octave will give the attached result "Octave_result_canny.png". If you run the very same script in Matlab (R2013b) you will get the attached image "ML2013b_result_canny.png". In recent Matlab versions the behavior of the Canny edge detektor was changed, therefor I also run Matlab with the parameter "canny_old" instead of "canny", the resulting image can be seen in "ML2013b_result_canny_old.png".

I observe the following:

  • The Matlab result (with 'canny' as well as with 'canny_old') gives a CLOSED contour without any missing pieces.
  • The Octave result gives a similar contour, but it has several missing pieces.


The missing pieces in the contour make the Octave result much harder to use in the following steps during image processing, it is not a "closed contour". So you cannot -for example- just go ahead and fill all holes in the binary image to get the regions.

This bug does not only happen with this particular test image, it occurs reproducibly for all similar images as well. I just used a test image here, to make the behavior reproducible.

This is NOT only a compatibility isssue compared to Matlab. The Canny edge detector in general has as one of its useful features, to usually return connected chains of edge pixels, but the Octave implementation of it does NOT do this very well. This is not nice, because the Canny algorithm is one of the most used edge detection algorithms.

Even when I try to optimize the parameter (sigma and the two thresholds) for the Canny algorithm, I cannot make the resulting contour much better. It is often impossible to get a closed contour as a result, even with manual fine tuning.

Another observation (that may or may not be connected to the described issue): I think I have never seen that changing the lower threshold for hysterises thresholding changes anything in the results. This leads me to the suspicion that there might be something wrong with the hysterises thresholding in the file nonmax_supress.cc .


Hartmut <hardy>

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #35558:  sample2.png added by None (24KiB - image/png)
file #35061:  canny_orientation.patch added by hardy (1KiB - text/x-diff)
file #35024:  cannysample.png added by hardy (10KiB - image/png)
file #35025:  Octave_result_canny.png added by hardy (339B - image/png)

 

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 mtmiller (Updated the item)
  • -email is unavailable- added by mtmiller
  • -email is unavailable- added by avinoam
  • -email is unavailable- added by hardy (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 16 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2015-12-07 carandraug StatusPatch Submitted Fixed
        Open/ClosedOpen Closed
    2015-12-05 hardy Attached File- Added edge_canny_direction+compatibility.patch, #35650
    2015-11-26 carandraug Release4.0.0 other
    2015-11-26 None Attached File- Added sample2.png, #35558
        Attached File- Added Octave_result_edge_canny_sample2.png, #35559
        Attached File- Added ML2012b_result_edge_canny_sample2.png, #35560
    2015-10-05 mtmiller StatusNone Patch Submitted
        Carbon-Copy- Added carandraug
    2015-10-04 hardy Attached File- Added canny_orientation.patch, #35061
        Attached File- Added Octave+OrientationPatch_result_canny.png, #35062
    2015-10-03 avinoam Carbon-Copy- Added avinoam
    2015-10-01 hardy Attached File- Added cannysample.png, #35024
        Attached File- Added Octave_result_canny.png, #35025
        Attached File- Added ML2013b_result_canny.png, #35026
        Attached File- Added ML2013b_result_canny_old.png, #35027

    Back to the top

    Powered by Savane 3.13-f8d8.
    Corresponding source code