patchGNU Octave - Patches: patch #9488, image package: new functions...

 
 

patch #9488: image package: new functions imhmax, imextendedmax, imimposemin (and imhmin, imextendedmin)

Submitter:  Hartmut <hardy>
Submitted:  Tue 14 Nov 2017 10:21:10 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

Wed 10 Jan 2018 06:41:02 PM UTC, comment #6: 

I have folded your two commits for the new set of functions (v2)

https://bitbucket.org/hgimpel/octave-image/commits/b025e3bbaf8bd3563f779f41c898bcbfb0492e43
https://bitbucket.org/hgimpel/octave-image/commits/0c00cef5b40d01a8cc469267028369e64b954fcc

with the removal of some trailing whitespace, and listing the functions in the INDEX and NEWS file and pushed them into the default branch

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

Thank you for the new functions, I will look at imfindcircles next of which this was a blocker.

Carnë Draug <carandraug>
Group Member
Tue 28 Nov 2017 09:43:18 PM UTC, comment #5: 

(1.) complex input images

I have now used the new version of imreconstruct.cc, and yes it can then well deal with the inputs that are generated by complex inputs to imextendedmax.m and the others. (Octave's order relation for complex number is mainly based on their absolute magnitude.)

Still I do NOT want to allow for complex input values in my new functions. To understand this, please consider the following code example:


im = zeros (10);
im(2:4, 2:4) = 3;
im(6:8, 6:8) = 8;
out_real = imhmax (im, 4)

im = im .* sqrt(-1);
out_complex = imhmax (im, 4)


If I remove the isreal check, then the result of this code becomes:


out_real =

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

out_complex =

   0 + 0i   0 + 0i   0 + 0i   0 + 0i   0 + 0i   0 + 0i   0 + 0i   0 + 0i   0 + 0i   0 + 0i
   0 + 0i   0 + 3i   0 + 3i   0 + 3i   0 + 0i   0 + 0i   0 + 0i   0 + 0i   0 + 0i   0 + 0i
   0 + 0i   0 + 3i   0 + 3i   0 + 3i   0 + 0i   0 + 0i   0 + 0i   0 + 0i   0 + 0i   0 + 0i
   0 + 0i   0 + 3i   0 + 3i   0 + 3i   0 + 0i   0 + 0i   0 + 0i   0 + 0i   0 + 0i   0 + 0i
   0 + 0i   0 + 0i   0 + 0i   0 + 0i   0 + 0i   0 + 0i   0 + 0i   0 + 0i   0 + 0i   0 + 0i
   0 + 0i   0 + 0i   0 + 0i   0 + 0i   0 + 0i   0 + 8i   0 + 8i   0 + 8i   0 + 0i   0 + 0i
   0 + 0i   0 + 0i   0 + 0i   0 + 0i   0 + 0i   0 + 8i   0 + 8i   0 + 8i   0 + 0i   0 + 0i
   0 + 0i   0 + 0i   0 + 0i   0 + 0i   0 + 0i   0 + 8i   0 + 8i   0 + 8i   0 + 0i   0 + 0i
   0 + 0i   0 + 0i   0 + 0i   0 + 0i   0 + 0i   0 + 0i   0 + 0i   0 + 0i   0 + 0i   0 + 0i
   0 + 0i   0 + 0i   0 + 0i   0 + 0i   0 + 0i   0 + 0i   0 + 0i   0 + 0i   0 + 0i   0 + 0i


The first result (with real input) is what you expect from imhmax. All maxima that are not 4 heigher than their neighborhood are removed. So the 3 peak is gone, but the 8 peak remains (just lowered by 4).

But the second result (complex input) is NOT what you would (maybe) like to get. The 3i peak is not gone this time. But it should be gone, because its magnitude (which is the base of Octave's ordering relation in the complex numbers) is by less then 4 bigger than its neihgborhood. The reason for this "wrong" behavior is, that for complex numbers the assumptions of the imhmax algorithm are not true any more, when you add a (real) value of h (the number 4) to a complex number, you do NOT get something that is by 4 bigger than before! If you add 4 to 3i then you only get something with a magnitude of 5 (=sqrt(4^2+3^2), which is only 2 bigger than 3i. So the underlying algorithm of all those new functions is not correct any more for complex input values. (And it does NOT help to allow for complex h values, because the complex im inputs might have complex angles in different directions.)

So I would like to forbid those complex input values, because the provoke wrong results in the above sense.

(2.) delta value for float inputs in imimposemin.m

This operation can be found in the literature as "Minima imposition". The detailed references are given in the source code of this function. But I personally also had never heard of this functions, nor used it before.

I have only implemented this function for completeness. I wanted to implement imhmax.m (because it was very useful in my new imfindcircles.m) And then I searched for similar functions in the Matlab help. And because their core algorithm is mostly only a one-liner, I've just implemented them all in one go.

So the reason I've implemented the function at all is "because Matlab has it". And as a conclusion I would like to also mimic the Matlab behavior of the delta value for float inputs. Let's stick to the Matlab values, just "because Matlab does it".  (There are already test in place for this Matlab compatible behavior.)

So my bottom line is, to please push those functions as they are now (i.e. V2). But let me know if you have a different view to those topics.

Hartmut <hardy>
Mon 27 Nov 2017 04:37:13 PM UTC, comment #4: 


> When I remove the test for "isreal" in my implementation of imextendedmax.m (and also in immhmax.m, which is called by it) then I get the following result from the above sample code: "error: imreconstruct: MARKER must be less or equal than MASK"


You are not using the latest development of the image package. The error message you are getting was removed with http://hg.code.sf.net/p/octave/image/rev/4957d5743185

With current development sources of the image package, imreconstruct will accept complex numbers.

> I don't know which definition of order Octave has on the complex numbers (Carne mentioned this, I though that proper math does not have this),


There was a bug report about this, and whether the Octave definition made sense and whether it was Matlab compatible. Not sure the conclusion was but Octavge certainly has some sort of "sens" since you can use < and > operators with complex numbers.  Even sort() will handle complex numbers.

> but even if I take this for granted, there would currently be no immediate benefit of allowing complex input values in imextendedmax.m.


I would put it the other way around. What's the benefit of preventing the use of complex numbers? It's more code to check for this than not checking. The only requirement is that the elements have a order.

> The current Octave result is probably better in some sense. But this Octave result is also very fragile and difficult to understand. For example is the first value of the Octave result matrix equal to 10+eps(10) which is difficult to distinguish from 10 in the display, and this meaningful difference of eps(10) might quickly get lost in the following calculations that the user does.
>
> @Carne: What shall we do? Mimic the (somehow arbitrary, but probably useful) Matlab behavior, or stick to the "theoretically better" result (as done with imregionalmax in bug #51724) ?


I'm reading about imimposemin for the first time so I don't have a strong opinion. Can you think of case where using the Matlab approach, instead of eps(img), could lead to an incorrect result? For example, what if one of the values in img that is not in the marker region is Inf?

What's the real name of this operation? The matlab documentation do not mention anything beyond "modifies the intensity image I using morphological reconstruction so it only has regional minima wherever BW is nonzero" which would mean that an array of Inf and -Inf only would be a "correct" result.

I will leave the decision up to you, but I would like to have tests for such corner cases and I'm only making sure they have been thought about.

Carnë Draug <carandraug>
Group Member
Fri 24 Nov 2017 10:28:29 PM UTC, comment #3: 

I have put a new patch with my additional tests here:

https://bitbucket.org/hgimpel/octave-image/commits/b025e3bbaf8bd3563f779f41c898bcbfb0492e43

I will also attach those 5 m-files (V2) as a zip file.

For the two topics mentioned in comment #2:

  • I have left the isreal check in, for now
  • I have changed the delta value of imimposemin to the Matlab behavior.




(file #42473)

Hartmut <hardy>
Fri 24 Nov 2017 08:22:39 PM UTC, comment #2: 

I have now gathered the necessary information to add more tests for the mentioned functionality. But before supplying them as a patch, I would like to discuss the following two topics:

(1.) complex inputs (to imextendedmax, maybe also to other functions)


I have tested the following sample code:


im = zeros (10);
im(2:4, 2:4) = 3;
im(6:8, 6:8) = 8;
im = im .* sqrt(-1);
out = imextendedmax (im, 4)


The Matlab result is:

Error using imextendedmax
Expected input number 1, I, to be real.

Error in imextendedmax>ParseInputs (line 73)
validateattributes(I, {'numeric'}, {'real' 'nonsparse'}, mfilename, 'I', 1);

Error in imextendedmax (line 61)
[I,h,conn] = ParseInputs(varargin{:});

Error in my_tests (line 192)
out = imextendedmax (im, 4)


So Matlab does NOT support complex inputs in this case. But it is a valid question if Octave could do better here.

When I remove the test for "isreal" in my implementation of imextendedmax.m (and also in immhmax.m, which is called by it) then I get the following result from the above sample code:

error: imreconstruct: MARKER must be less or equal than MASK


I don't know which definition of order Octave has on the complex numbers (Carne mentioned this, I though that proper math does not have this), but even if I take this for granted, there would currently be no immediate benefit of allowing complex input values in imextendedmax.m. (The imreconstruct error message might be due to bug #48794, but I have not digged deep enough into this to be sure.)

@Carne: What shall I do here? My suggesion would be to insist on isreal in the input checks.

(2.) The delta value for float images in imimposemin.m

In my first commit, I set this to be delta=eps(max(im(:))). But as discussed in bug #51724 this is just a suboptimal approach, due to a bug in eps() in Octave 4.2.1. Carne then introduced _eps_() into the image package, to temporarily fix this. Now it would be the best approach to also use this _eps_ function in imimposemin, and use delta=__eps__(im). (This is now also done in imregionalmax, see bug #51724.)

Unfortunatelly, Matlab does NOT seem to do this. Here are two Matlab results that I have tested:


im0 = uint8 ([5 5 5 5 5;
              5 4 3 4 5;
              5 3 0 3 5;
              5 4 3 4 5;
              5 5 5 5 5]);
bw0 = false (5);
bw0(4,4) = true;

imimposemin (double(im0), bw0)

ans =
    5.0050    5.0050    5.0050    5.0050    5.0050
    5.0050    4.0050    3.0050    4.0050    5.0050
    5.0050    3.0050    0.0050    3.0050    5.0050
    5.0050    4.0050    3.0050      -Inf    5.0050
    5.0050    5.0050    5.0050    5.0050    5.0050


The Octave result, using delta=__eps__(im) is instead:

ans =
   5.00000   5.00000   5.00000   5.00000   5.00000
   5.00000   4.00000   3.00000   4.00000   5.00000
   5.00000   3.00000   0.00000   3.00000   5.00000
   5.00000   4.00000   3.00000      -Inf   5.00000
   5.00000   5.00000   5.00000   5.00000   5.00000


And the second Matlab result:

im = uint8 (10 .* ones (10));
im(6:8,6:8) = 2;
im(2:4,2:4) = 7;
im(3,3) = 5;
im(2,9) = 9;
im(3,8) = 9;
im(9,2) = 9;
im(8,3) = 9;
bw = false (10);
bw(3,3) = true;
bw(6:8, 6:8) = true;

imimposemin (double(im), bw)

ans =
   10.0080   10.0080   10.0080   10.0080   10.0080   10.0080   10.0080   10.0080   10.0080   10.0080
   10.0080    7.0080    7.0080    7.0080   10.0080   10.0080   10.0080   10.0080   10.0080   10.0080
   10.0080    7.0080      -Inf    7.0080   10.0080   10.0080   10.0080   10.0080   10.0080   10.0080
   10.0080    7.0080    7.0080    7.0080   10.0080   10.0080   10.0080   10.0080   10.0080   10.0080
   10.0080   10.0080   10.0080   10.0080   10.0080   10.0080   10.0080   10.0080   10.0080   10.0080
   10.0080   10.0080   10.0080   10.0080   10.0080      -Inf      -Inf      -Inf   10.0080   10.0080
   10.0080   10.0080   10.0080   10.0080   10.0080      -Inf      -Inf      -Inf   10.0080   10.0080
   10.0080   10.0080   10.0080   10.0080   10.0080      -Inf      -Inf      -Inf   10.0080   10.0080
   10.0080   10.0080   10.0080   10.0080   10.0080   10.0080   10.0080   10.0080   10.0080   10.0080
   10.0080   10.0080   10.0080   10.0080   10.0080   10.0080   10.0080   10.0080   10.0080   10.0080


Whereas the Octave result (still with delta=__eps__(im)) is:

ans =
   10.0000   10.0000   10.0000   10.0000   10.0000   10.0000   10.0000   10.0000   10.0000   10.0000
   10.0000    7.0000    7.0000    7.0000   10.0000   10.0000   10.0000   10.0000   10.0000   10.0000
   10.0000    7.0000      -Inf    7.0000   10.0000   10.0000   10.0000   10.0000   10.0000   10.0000
   10.0000    7.0000    7.0000    7.0000   10.0000   10.0000   10.0000   10.0000   10.0000   10.0000
   10.0000   10.0000   10.0000   10.0000   10.0000   10.0000   10.0000   10.0000   10.0000   10.0000
   10.0000   10.0000   10.0000   10.0000   10.0000      -Inf      -Inf      -Inf   10.0000   10.0000
   10.0000   10.0000   10.0000   10.0000   10.0000      -Inf      -Inf      -Inf   10.0000   10.0000
   10.0000   10.0000   10.0000   10.0000   10.0000      -Inf      -Inf      -Inf   10.0000   10.0000
   10.0000   10.0000   10.0000   10.0000   10.0000   10.0000   10.0000   10.0000   10.0000   10.0000
   10.0000   10.0000   10.0000   10.0000   10.0000   10.0000   10.0000   10.0000   10.0000   10.0000


This leads me to the conclusion that Matlab does something similar to

delta= ( max(im(:)) - min(im(:)) ) / 1000


The current Octave result is probably better in some sense. But this Octave result is also very fragile and difficult to understand. For example is the first value of the Octave result matrix equal to 10+eps(10) which is difficult to distinguish from 10 in the display, and this meaningful difference of eps(10) might quickly get lost in the following calculations that the user does.

@Carne: What shall we do? Mimic the (somehow arbitrary, but probably useful) Matlab behavior, or stick to the "theoretically better" result (as done with imregionalmax in bug #51724) ?

Hartmut <hardy>
Wed 22 Nov 2017 07:24:26 PM UTC, comment #1: 

I would like to add some more tests to all those functions. Currently there are no tests for the neighborhood functionality, nor for float input images. But those tests will only be able to pass after fixing imregionalmax (see bug #51724) and also a similar fix for imregionalmin.

I hope to find the time for this during the next weeks.

@Carne: Sorry for making the inter-dependency of the outstanding patches even more complicated by this...

Hartmut <hardy>
Tue 14 Nov 2017 10:21:10 PM UTC, original submission:  

I have implemented the following 5 missing functions for the image package:

  • imhmax
  • imhmin
  • imextendedmax
  • imextendedmin
  • imimposemin
  • (there is no "imimposemax" in Matlab)


Those functions all deal with regional minima and maxima using morphological operations. Their core algorithms are mostly one-liners that rely on the existing functionality of imreconstruct.

The sources of the algorithms are always cited in the code. It's the book of Soille and the following web page:

https://clouard.users.greyc.fr/Pantheon/experiments/morphology/index-en


You can find those new m-file on my bitbucket repository:
https://bitbucket.org/hgimpel/octave-image/commits/0c00cef5b40d01a8cc469267028369e64b954fcc

The files are on the default branch there, with the bookmark "new-imhmax_etc" attached.

I will also add a zip-file (V1) with these 5 new functions to this report.

The intention was to make these functions Matlab compatible. And they do pass all Matlab compatible tests that I could find in the Matlab documentation.

I would be happy to hear comments or feedback on this.

Hartmut <hardy>

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #42473:  new-imhmax_etc_V2.zip added by hardy (12KiB - application/zip)
file #42405:  new-imhmax_etc_V1.zip added by hardy (11KiB - application/zip)

 

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 6 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2018-01-10 carandraug StatusNone Done
        Open/ClosedOpen Closed
    2017-11-24 hardy Attached File- Added new-imhmax_etc_V2.zip, #42473
    2017-11-14 hardy Attached File- Added new-imhmax_etc_V1.zip, #42405
        Carbon-Copy- Added avinoam
        Carbon-Copy- Added carandraug

    Back to the top

    Powered by Savane 3.13-cf05.
    Corresponding source code