Not sure if this is the correct place to ask but I have a question about techniques for processing an array of pixels with o(1) complexity. That is to get the sum of a subset of an array but if this subset extends beyond the bounds of an array taking those as zero. This is with a 2D array.

In reality the array can go up to [2000][2000] but lets take a 2D array that is sized [4][4] for simplicity.

array[4][4] = {0,  1,  2,  3
               4,  5,  6,  7
               8,  9,  10, 11
               12, 13, 14, 15}

Now let's say I want to get the sum of the array between [2][2] and [3][3], i.e. adding 10 + 11 + 14 + 15. This can be made in a o(1) solution by using a summed area table.

However I am little confused about how to keep this o(1) complexity providing:

  1. the array subset extends outside the actual array
  2. the array indices outside the actual array are taken as zero.
  3. The algorithm computation is still o(1)

So for example lets say for this pixel sum I am asked to get the sum of [2][2] to [4][4]. This has a theoretical array of, numbers outside actual are denoted f (for fake):

array_theory[5][5] = {0,  1,  2,  3,  0f
                      4,  5,  6,  7,  0f
                      8,  9,  10, 11, 0f
                      12, 13, 14, 15, 0f
                      0f, 0f, 0f, 0f, 0f}

or in an image: enter image description here

I think I have to use some sort of filter or image processing technique that I can't seem to find online or don't know the keyword and am flirting with it in my search results.

Any help would be greatly appreciated!

  • $\begingroup$ OK, is this about a detail in the methodology or is it more like a programming question? Instead of considering the complexity of what seems like an iteration, why not insert a check of the sum bounds so that even if they extend outside of the known area they are "corrected" for the known parts? Out of bound data will anyway be zero and will not be contributing anything to the sum. Or have I missed something? $\endgroup$
    – A_A
    Feb 19 '20 at 9:32
  • $\begingroup$ It is to be applied to programming but I believe it is an image processing (i.e. signal processing) technique hence why I asked here. I agree it will not affect the sum but when it comes to the next layer of complexity of getting an average of a subarray, which can be calculated with the summed array in o(1). I was hoping the same methodology could be applied. $\endgroup$
    – JiPecki
    Feb 19 '20 at 9:37
  • $\begingroup$ Hi, my comment is more trying to understand what the question is about. Again, in the case of an average, the sum will have to be taken over the area but the division over the product of the initial area bounds (?). So, the suggestion here is not to check if a certain sum is about to be run out of bounds during the sumation but do it beforehand by modifying the summation bounds in a reasonable way. $\endgroup$
    – A_A
    Feb 19 '20 at 10:17
  • $\begingroup$ yes I agree. The issue is making the process o(1) regardless if the search window is inside the array or outside the array in a big or small way. $\endgroup$
    – JiPecki
    Feb 19 '20 at 10:25
  • $\begingroup$ The O(1) approach you're talking about uses an integral image, you add and subtract the four corners of the box you want to take the sum over. It is O(1) because you always use only 4 values in your calculation, no matter the size of the box. Modifying the right edge of the box x2 with min(x2,width-1), and doing similarly for the other edges, will lead to the sum over the box using padding with zeros outside the image. This does not change the complexity of the operation, it is still O(1). $\endgroup$ Feb 20 '20 at 17:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.