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

 
 

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

Submitted by:  Avinoam Kalma <avinoam>
Submitted on:  Thu 22 Mar 2018 05:43:54 PM UTC  
 
Category:  Forge : new function Priority:  5 - Normal
Status:  None Privacy:  Public
Assigned to:  CarnĂ« Draug <carandraug> Open/Closed:  Open

Add a New Comment (Rich Markup)
   

You are not logged in

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

 

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

 

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

Attach Files:
   
   
Comment:
   

Attached Files
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
  •  

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

     

     

     

    Follow 5 latest changes.

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