patchGNU Octave - Patches: patch #9606, [octave forge] (image) New...

 
 

patch #9606: [octave forge] (image) New function integralImage

Submitter:  Avinoam Kalma <avinoam>
Submitted:  Thu 22 Mar 2018 05:43:54 PM UTC
   
 
Category:  Forge : new function Priority:  5 - Normal
Status:  Done Privacy:  Public
Assigned to:  carandraug Open/Closed:  Closed
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Wed 04 Sep 2019 08:19:42 PM UTC, comment #18: 

integralImage3 is even simpler than integralImage
see patch #9849

Avinoam Kalma <avinoam>
Group Member
Thu 15 Aug 2019 12:34:12 AM UTC, comment #17: 

Thank you for the patches, reviews, and changes. I have pushed the new function now.

I noticed that there's also integralImage3 which maybe you want to implement since maybe they're similar? Would be nice to know what Matlab does in 4D cases and add tests for it.

Carnë Draug <carandraug>
Group Member
Wed 14 Aug 2019 12:05:15 PM UTC, comment #16: 

Thanks for the review. I will make a proper changeset.

Avinoam Kalma <avinoam>
Group Member
Tue 13 Aug 2019 07:50:21 AM UTC, comment #15: 

I have had a look at the V6 version of comment #14:

  • line 59: space behind class is missing
  • line 60: space behind double
  • line 77: space behind size (twice)
  • line 85: Yes, this todo comment is more appropriate now :)
  • line 106: space behind uint8
  • line 107: space behind double


Since all of the above are only minor formatting issues, I would suggest that you prepare a patch now (including the above style issues). And if Carne does not have any objections, we could push this to the repo then.


Hartmut <hardy>
Sun 11 Aug 2019 09:28:37 PM UTC, comment #14: 

Thanks Hartmut for reviewing.
Attached V6, according to your comment.


(file #47328)

Avinoam Kalma <avinoam>
Group Member
Sun 11 Aug 2019 02:53:14 PM UTC, comment #13: 

I have had a look at the V5 version of comment #12.

  • The execution time for the "rotated" version seems much better now. Here is what I tested:
    • tic; I = magic(5000); J=integralImage(I); toc
      • Online-Matlab: 0.35s
      • Octave V5 version: 0.67s
    • tic; I = magic(5000); J=integralImage(I, 'rotated'); toc
      • Online-Matlab: 1.19s (=3.4 times slower as "upright")
      • Octave V5 version: 2.17s (=3.2 times slower as "upright")
  • The copyright notice is still from 2018. Maybe change it to 2019?
  • In the new test cases, there a some spaces missing in function calls of magic and integralImage. (I know, those missing spaces are from my example code... Sorry)


My conlcusion: I suggest to include this V5 version fully into the image package. Including the "rotated" option, and without any warnings in the help texts, now. It is now reasonably fast on usable images sizes (25Mpix in the example above).

Thanks for this code improvement, Avinoam.

Hartmut <hardy>
Fri 09 Aug 2019 04:51:03 AM UTC, comment #12: 

Adding the test from comment #4 (thanks Hartmut), in V5

(file #47308)

Avinoam Kalma <avinoam>
Group Member
Thu 08 Aug 2019 09:57:54 PM UTC, comment #11: 

sorry, V3 is wrong. V4 is OK (though slower...)

(file #47307)

Avinoam Kalma <avinoam>
Group Member
Thu 08 Aug 2019 09:39:39 PM UTC, comment #10: 

Please review the attached V3,
(not final yet, but has better performance).
Thanks

(file #47306)

Avinoam Kalma <avinoam>
Group Member
Thu 08 Aug 2019 06:26:33 PM UTC, comment #9: 

Ok, seems fair to put it on the image package. Matlab documentation has integralImage on both image and vision. I checked a local machine and the function is only on the image processing package.

So I checked the code and is fine for the upright version. But like Hartmut said, the non-vectorised rotated option is unusable in real life. I'd lean to not include that option at all  (error with option not implemented). If we do let this slow implementation go, we will not get a reputation for implementing a lot of Mathlab features, instead we will get a reputation for veing very slow.

Carnë Draug <carandraug>
Group Member
Sat 03 Aug 2019 06:46:09 PM UTC, comment #8: 

I completely agree with Hartmut.
We do not have enough volume yet for Vision package.

In the past I thought about creating a vision toolbox, that
will use OpenvCV, using mexopencv (https://kyamagu.github.io/mexopencv/) or python API (as done in octsympy), but it seems like a too big project, that I cannot handle now.

Avinoam Kalma <avinoam>
Group Member
Sat 03 Aug 2019 07:39:21 AM UTC, comment #7: 

When I checked on the Mathworks Website today and searched for "IntegralImage", then I got TWO hits:

  • in the "Image Processing Toolbox"
  • and as well in the "Computer Vision Toolbox"


So I would suggest that we have our Octave version of IntegralImage in the "image" package for now. Should a bigger number of functions accumulate in "image" that (also) belong to the Matlab "Computer Vision Toolbox", then we should probably start this (but to my knowledge this is not the case right now). Or if there is someone who is willing to engage and start this new toolbox, then I would also tend to support this.


Hartmut <hardy>
Fri 02 Aug 2019 07:10:54 PM UTC, comment #6: 

I was going to merge this in, when I realised that integralImage is actually part of the computer vision package and not the image processing.

I think there was talk at some point of having a computer vision package in Octave. What do you think?

Carnë Draug <carandraug>
Group Member
Thu 18 Jul 2019 12:05:26 PM UTC, comment #5: 

Sorry, the speed in Matlab is 4-times slower for the "upright" version, not 3-times.

Hartmut <hardy>
Thu 18 Jul 2019 12:04:32 PM UTC, comment #4: 

Thanks for your second patch, Avinoam.

I have had a look at this V2 code from comment #3:

  • The double quotes are fine, now.
  • All tests still pass. (I still do not know if those test results are Matlab compatible.)
  • I have tried the two examples from the Matlab documentation page. Those gave me identical results as the V2 patch. Here are the details, maybe you want to include those as additional tests?


I = magic(5);
J = integralImage(I)
J_matlab = [0     0     0     0     0     0;
     0    17    41    42    50    65;
     0    40    69    77    99   130;
     0    44    79   100   142   195;
     0    54   101   141   204   260;
     0    65   130   195   260   325]
alle_gleich = all(all(J_matlab ==J))


[x, y, w, h] = deal(3, 1, 3, 2);
J = integralImage(I, 'rotated')
J_matlab = [0 0 0 0 0 0 0;
  0 17 24 1 8 15 0;
  17 64 47 40 38 39 15;
  64 74 91 104 105 76 39;
  74 105 149 188 183 130 76;
  105 170 232 272 236 195 130]
alle_gleich = all(all(J == J_matlab))
regionSum = J(y+w+h,x+w-h+1) + J(y,x+1) - J(y+h,x-h+1) - J(y+w,x+w+1)
regionSum_matlab = 133

  • Matlab only accepts 2d images as inputs. Our V2 code also accepts Nd inputs. (This is nothing bad, just a note.) Maltab then has integralImage3 for 3d input images.
  • The (only) main problem I still see it the run time for the "rotated" version. Since it uses nested for-loops it runs horribly long. This basically make the "rotated" version un-usable for real images! I see two ways to proceed with this:
    • Add a warning to the doc string of integralImage.m to say that the "rotated" version will give right (i.e. Matlab compatible) results but has a very bad speed performance, and therefore should better not be used for real image processing. (Since the whole point of the function integralImage.m is to speed up other calculations that use its output.)
    • Eventuelly find a vectorised solution for the two nested for-loops in the subfunction integralImage_rotate_2D. How to you like the following idea? 1. accept the input image I. 2. generate a new "distorted" image I45 from it, by (using a for loop) going through its rows and shifting each line sidewards by one index, thus generating the new I45. 3. then use cumsum on I45 to generate the final results (and maybe cut off some extra rows and columns). Advantages: only 1 for loop (not 2 any more). And no real calculation in the for loop, just shifting indices around. I hope this can be much faster.
    • note: In Matlab (tested on I=magic(5000)) the result of the "rotated" calculation is roughly 3times slower than the "upright" version.
Hartmut <hardy>
Mon 01 Jul 2019 03:53:08 AM UTC, comment #3: 

Please review V2,
I would like to push it

Avinoam Kalma <avinoam>
Group Member
Sun 25 Mar 2018 06:31:26 PM UTC, comment #2: 

@Hartmut: thanks for reviewing.
I have fixed the 45 degrees issue, and also changed the
single quotes to double quotes.
I need help in vectorizing "rotated" section.

Attahced V2.

(file #43674)

Avinoam Kalma <avinoam>
Group Member
Sun 25 Mar 2018 02:55:53 PM UTC, comment #1: 

Thanks for creating this new function, Avinoam.

I've had a quick glance over it. Some comments:

  • In the doc string: You could mention the 45 degrees value to clarify the "rotated" option.
  • The "upright" code version uses cumsum, but the "rotated" code path uses two nested for-loops. Could this somehow be vectorized (as already mentioned in the code comments) for speed?
  • The tests all pass. But I haven't checked if they are Matlab compatible.
  • I think the coding styles requires double quotes for strings.


Hartmut <hardy>
Thu 22 Mar 2018 05:43:54 PM UTC, original submission:  


Please review

Avinoam Kalma <avinoam>
Group Member

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #47328:  integralImage_V6.m added by avinoam (5KiB - application/octet-stream)
file #47308:  integralImage_V5.m added by avinoam (5KiB - application/octet-stream)
file #47307:  integralImage_V4.m added by avinoam (5KiB - application/octet-stream)
file #47306:  integralImage_V3.m added by avinoam (5KiB - application/octet-stream)
file #43674:  integralImage_V2.m added by avinoam (5KiB - application/octet-stream)
file #43632:  integralImage.m added by avinoam (5KiB - application/octet-stream)

 

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 avinoam (Submitted the item)
  • -email is unavailable- added by avinoam
  • -email is unavailable- added by avinoam
  •  

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

    Date Changed by Updated Field Previous Value => Replaced by
    2019-08-15 carandraug StatusNone Done
        Open/ClosedOpen Closed
    2019-08-11 avinoam Attached File- Added integralImage_V6.m, #47328
    2019-08-09 avinoam Attached File- Added integralImage_V5.m, #47308
    2019-08-08 avinoam Attached File- Added integralImage_V4.m, #47307
    2019-08-08 avinoam Attached File- Added integralImage_V3.m, #47306
    2019-03-07 mtmiller Summary[Octave-forge] (image) New function integralImage [octave forge] (image) New function integralImage
    2018-03-25 avinoam Attached File- Added integralImage_V2.m, #43674
    2018-03-22 avinoam Attached File- Added integralImage.m, #43632
        Carbon-Copy- Added carandraug
        Carbon-Copy- Added hardy

    Back to the top

    Powered by Savane 3.13-cf05.
    Corresponding source code