0

I'm trying to find an algorithm to find a space in a Bitmap large enough to contain a new bitmap. Currently I'm iterating each x and y pixel and seeing if my smaller bitmap will collide with the background at all. It works but it's extremely slow. I've recently become aware of something called Integral Image to parse the background image and then check if a space in it is available in constant time.

The algorithm I'm using is:

public class IntegralImage 
{
private int[][] integralImage = null;

public IntegralImage(Bitmap image) 
{
    int originalImageHeight = image.getHeight();
    int originalImageWidth = image.getWidth();
    integralImage = new int[originalImageHeight][originalImageWidth];
    int[][] originalPixels = new int[image.getHeight()][image.getWidth()];
    for(int i = 0; i < image.getHeight(); i++)
    {
        for(int j = 0; j < image.getWidth(); j++)
        {
            originalPixels[i][j] = image.getPixel(j, i);
        }
    }
    int originalPixelValue = 0;
    for (int row = 0; row < originalImageHeight; row++) 
    {
        for (int column = 0; column < originalImageWidth; column++) 
        {
            originalPixelValue = originalPixels[column][row];

            if (row == 0 && column == 0) 
            {
                integralImage[row][column] = originalPixelValue;
            }

            else if (row == 0) 
            {
                integralImage[row][column] = originalPixelValue + integralImage[row][column - 1];
            }


            else if (column == 0) 
            {
                integralImage[row][column] = originalPixelValue + integralImage[row - 1][column];
            }
            else 
            {
                integralImage[row][column] = originalPixelValue + integralImage[row][column - 1] + integralImage[row - 1][column] - integralImage[row - 1][column - 1];
            }
        }
    }
}

public int total(int x1, int y1, int x2, int y2) 
{
    int a = x1 > 0 && y1 > 0 ? integralImage[x1-1][y1-1] : 0;
    int b = x1 > 0 ? integralImage[x1-1][y2] : 0;
    int c = y1 > 0 ? integralImage[x2][y1-1] : 0;
    int d = integralImage[x2][y2];
    return a + d - b - c;
}

}

However when I call it using this:

if(imageIntegral.total(i, j, i + _imageBitmap.getWidth(), j + _imageBitmap.getHeight()) == 0)

It always returns true and just stacks all the text bitmaps on top of each other.

Does anyone have any experience in trying to fit bitmaps within a bitmap without overlapping efficiently?

It's my understanding that it should return zero if the sub-array contains nothing but white pixels.

Thank you.

Lurr
  • 861
  • 4
  • 11
RyPope
  • 2,645
  • 27
  • 51
  • A similar problem: http://stackoverflow.com/questions/2478447/find-largest-rectangle-containing-only-zeros-in-an-n×n-binary-matrix – MBo Jul 30 '14 at 05:17

1 Answers1

0

I can suggest few improvements in your approach to make it faster.

First we can find a possible location faster:

int w = _imageBitmap.getWidth();
int h = _imageBitmap.getHeight();

for (int i = originalImageWidth - 1; i >= w/4; i -= w/2)
    for (int j = originalImageHeight  - 1; j >= h/4; j -= h/2)
    {
        //it may be a bit strange to check (i - w/2, j - h/2, i, j) instead of ( i, j, i + w/2, j + h/2)
        // but it's simpler considering your integral image implementation.
        if (imageIntegral.total(i - w/2, j - h/2, i, j) == 0)
        {
            //check if there is enough space around
        }
    }

If there is a place for _imageBitmap it should contain at least one of w/2 x h/2 tiles. You can reduce number of checks almost in h*w/4 times in best case this way.

There also no need to check every pixel inside (h/2 x w/2) tile for being center of place for bitmap. If there is empty place (i - w1, j - h1, i, j) suppose that w1 < w and h1 < h and we want check if there is place for (w x h) bitmap around we can check following for placements of mid size rectangle

(i - w1, j - h1, i - w1 + (w + w1)/2, j - h1 + (h + h1)/2)
(i - w1, j - (h + h1)/2, i- w1 + (w + w1)/2, j)
(i - (w + w1)/2, j - h1, i, j - h1 + (h + h1)/2)
(i - (w + w1)/2, j - (h + h1)/2, i, j)

(each one is is rectangle of (w + w1)/2 x (h + h1)/2 size matching with inner rectangle in some corner) If no one of four of them is free there is no free place for (w x h) rectangle either, else it will shrink area of further search in four times. You can repeat this checks in loop to check position in logarithmic time.

I'm not completely sure what do you mean by It always returns true , your code should work correctly if it does not contain unnoticed mistakes somewhere else (and if 0 correspond to white pixel and etc.). Maybe you are searching for free place again after placing some new picture on bitmap without updating integral image? If you are drawing smth. on bitmap and searching for free place again complete updating of integral image may be slow anyway, you may try to update only areas of integral image which are used, or try to use some other approach - possibly something related to object collision detection, but optimal method depends from specific details of task.

Lurr
  • 861
  • 4
  • 11