1

So lets say I have a block that is 10x10, my goal is the break this into quadrants and then once I have done that, go back to the first quadrant and break and into four quadrants, go to the second quadrants and break that into four quadrants and so on until they are all broken and then go back to the first and repeat it for the new set of blocks.

So essentially I want to break a block into 4 pieces and break each new block into four pieces and keep going with this pattern.

This is the code I have so far:

private static void getBlockAverage(int startHeight, int endHeight, int startWidth, int endWidth, BufferedImage img, BufferedImage blockImg) {

        int red = 0;
        int green = 0;
        int blue = 0;
        int rgb = 0;

        if(endHeight <= 1 || endWidth <= 1) {
            return;
        }

        // get average
        for(int i = startHeight; i < endHeight; i++) {
            for(int j = startWidth; j < endWidth; j++) {
                rgb = img.getRGB(j, i);
                red += (rgb >> 16) & 0xFF;
                green += (rgb >> 8) & 0xFF;
                blue += (rgb) & 0xFF;
            }
        }

        // get average color
        red = red /((startWidth - endWidth) * (startHeight - endHeight));
        green = green/((startWidth - endWidth) * (startHeight - endHeight));
        blue = blue/((startWidth - endWidth) * (startHeight - endHeight));
        Color color = new Color(red,green,blue);

        // apply 
        for(int i = startHeight; i < endHeight; i++) {
            for(int j = startWidth; j < endWidth; j++) {
                blockImg.setRGB(j, i, color.getRGB());
            }
        }

        getBlockAverage(startHeight, endHeight/2, startWidth, endWidth/2, img, blockImg);
        getBlockAverage(endHeight/2+1, endHeight, endWidth, endWidth/2, img, blockImg);
        getBlockAverage(startHeight, endHeight/2, endWidth/2+1, endWidth, img, blockImg);
        getBlockAverage(endHeight/2+1, endHeight, endWidth/2+1, endWidth, img, blockImg);


    }

So what I am doing is trying to recursively call this function which will continue to break each block into quadrants but I continue to get a stack overflow.

What my code does is takes an image, gets the average colour of that block and displays it. It is a relatively simple concept that I am going to tweek a bit to get some cool images but that is for later, right now I am trying to fix this issue.

Edit here are the results of System.out.println(startHeight + " " + endHeight + " "+ startWidth + " " + endWidth);

0 72 0 108
0 36 0 54
0 18 0 27
0 9 0 13
0 4 0 6
0 2 0 3
0 1 0 1
0 1 2 3
3 4 0 3
3 4 0 1
3 4 2 3
3 4 2 3
3 4 2 3
3 4 2 3
3 4 2 3
3 4 2 3

and then 3 4 2 4 repeats until I get the stack overflow.

QQCompi
  • 225
  • 4
  • 14

1 Answers1

4

Three features are important when doing recursion:

  1. a breaking condition
  2. the actual workload
  3. collating the results of recursions

Specifically:

private static void getBlockAverage(int startHeight, int endHeight, int startWidth, int endWidth, BufferedImage img, BufferedImage blockImg) {
    // break recursion on empty block
    if(endHeight <= startHeight || endWidth <= startWidth)
        return;

    if(startHeight + 1 == endHeight || startWidth + 1 == endWidth) {
        // work on single columns or rows of pixels
        // results are stored to blockImg...
    } else {
        // recurse
        getBlockAverage(startHeight, (startHeight + endHeight)/2, startWidth, (startWidth + endWidth)/2, img, blockImg);
        getBlockAverage((startHeight + endHeight)/2, endHeight, startWidth, (startWidth + endWidth)/2, img, blockImg);
        getBlockAverage(startHeight, (startHeight + endHeight)/2, (startWidth + endWidth)/2, endWidth, img, blockImg);
        getBlockAverage((startHeight + endHeight)/2, endHeight, (startWidth + endWidth)/2, endWidth, img, blockImg);
        // now collate the results in blockImg...
    }
}
BeyelerStudios
  • 4,243
  • 19
  • 38
  • Shouldnt the `if(endHeight <= 1 || endWidth <= 1) return;` take care of that? I tried your method but I still get a stack overflow – QQCompi Nov 20 '15 at 14:10
  • @QQCompi no it won't, your naminig is confusing: your actual `width` is `endWidth - startWidth`, `endHeight` and `endWidth` are not decreased in your recursive calls – BeyelerStudios Nov 20 '15 at 14:13
  • @QQCompi you also need to fix your recursive calls, see my edit – BeyelerStudios Nov 20 '15 at 14:16
  • I see what you mean, also I get why you changed the recursive call. The issue I am facing now is that it doesn't completely cover all pixels within an image, in fact it is only recursively being called about 14,000 times when there are roughly 120,000 pixels – QQCompi Nov 20 '15 at 14:25
  • @QQCompi you need to special handle non-square images – BeyelerStudios Nov 20 '15 at 14:31
  • I am not sure if your `if(endHeight <= startHeight || endWidth <= startWidth) return;` works – QQCompi Nov 20 '15 at 14:52
  • Nvm, there was a small bug in your code with the 3rd getBlockAverage call, works perfectly now, thanks!! – QQCompi Nov 20 '15 at 14:57
  • Actually looking it over, I dont think `if(endHeight <= startHeight || endWidth <= startWidth) return;` would work. Imagine startHeight and startWidth as 0 and endHeight and endWidth as 0. This would cause an infinite loop. – QQCompi Nov 20 '15 at 15:42
  • @QQCompi if `startHeight` and `endHeight` have the same value, the recursion breaks, how ever do you expect an endless loop? – BeyelerStudios Nov 20 '15 at 15:45
  • Sorry I mistyped my example, it should read: Imagine startHeight and startWidth as 0 and endHeight and endWidth as 1. At this point I continue to have an endless loop. I tried updating it with `if(((endWidth - startWidth) <= 1 )|| ((endHeight - startHeight)) <= 1) return;` but this causes my to lose a generous amount of pixels. – QQCompi Nov 20 '15 at 15:53