Advice on a faster way to check every pixel in an image.

Newbie & Debugging Questions
#1

Does anyone have any advice on a faster method for checking every single pixel in an entire image?

I’m doing a few coding tests, and I want to experiment with putting pixel data into a 2d byte array, but I’d like to speed up the process a bit, just wondering if anyone has any tricks up their sleeve.

Basically my method runs 2 for loops and line by line/pixel by pixel snags the data on each pixel 1 by 1 and stuffs it in an array. The images it’s dealing with are only 2 color images, red and black.


for(int x = 0; x < image.getWidth(); x++){
	for( int y = 0; y < image.getHeight(); y++){
		if (image.getColor(x, y).getRed() == 255){
			byteArray[x][y] = 1;
		}else{
			byteArray[x][y] = 0;
		}
	}
}

Just wondering if anyone else has any tricks up their sleeve for grabbing all the X/Y coordinates of one specific color on an image that may be faster.

#2

getColor() may have some overhead so if you’re doing it a lot you should turn it into a n array instead.

#3

can you do the following? i dunno how much time it would save by avoiding calling methods, and may be prone to errors:


if (image[x][y].red == 255){
#4

Since EVERY pixel has to be checked (unless they don’t…), what you want here is a cache friendly algorithm.
This means, if possible, single loops, and if double loops are required, y being the outer one is usually faster, due the the way the image is stored internally.

If byteArray can be 1D, then that will reduce cache misses as well. (And keep it indexed [outerLoopVariable][innerLoopVariable] if it’s 2D)

What is this [icode]Image[/icode] in terms of class, if I may ask? I could provide more helpful advice with more info.

#5

Use 1d arrays for starters. I would also think that image.getRGB - int[] would be faster.

#6

It’s an image loaded via Slick2d’s Image class, that’s basically a wrapper around LWJGL’s image/rendering classes.
http://slick.ninjacave.com/javadoc/org/newdawn/slick/Image.html
https://bitbucket.org/kevglass/slick/src/tip/trunk/Slick/src/org/newdawn/slick/Image.java

Also, the coordinates of the pixel found should be retained, that’s where the need for the 2D array comes from; how could a 1D byte array store the coordinates? I suppose it’s possible to store say, a 32x32 image in a 1024 place array, then understand that every 32 places in the array is the next row on the Y axis? (or is there a better way I’m not fully understanding? Because I just made that idea up.)

#7

Assuming you have a 1D array, you can do the following:

data[x + y * width]

in which width would be the width of your picture, x and y the coordinates you want to get/set and the size of the data array would be the width times the height of the picture (e.g. 32*32).

#8

Have fun!


		int width = 64;
		int height = 32;
		int[] pixels = new int[width * height];

		for (int y = 0; y < height; y++) {
			for (int x = 0; x < width; x++) {
				pixels[x + y * width] = 10;
			}
		}

		int getx = 32;
		int gety = 23;
		int index = getx + gety * width;

		int integer = pixels[index];

		int xindex = index % width;
		int yindex = index / width;
#9

Understand this (not optimal, but should point you right direction):


  public void foo(int[] src, byte[] dst, int w, int h) {
    int len = w*h;
    int id  = 0;
    
    for(int i=0; i<len; i++) {
      int p = src[id];   // assuming ARGB with A any value legal
      
      p = 1 + ((((p >> 16) & 0xFF) - 0xFF) >> 8);
      
      dst[id++] = (byte)p;
    }
  }
#10

Humm…that’s probably too hard. Let me try again. What happens if you add 1 to 0xFF that doesn’t for any other value?

#11

I’m seeing Image.getTexture().getTextureData() in the Slick docs, could be useful, but most likely slower than Image.getColor() method if you can’t batch the texture downloads from the card. If getTextureData() is used, Roquen’s method is good, as getTextureData() returns a byte array. Might need to stride over it somehow though.

Otherwise, just use single arrays, and lose the conditional:


int w = img.getWidth();
int a = w * image.getHeight();
byte[] mask = new byte[a];
for(int i = 0; i < a; i++) {
    mask[i] = (img.getColor(i % w, i / w).getRed() + 1) >> 8; //might be able to lose the divisions with twiddling
}
#12

Look at the Image source, linked above.

	public Color getColor(int x, int y) {
		if (pixelData == null) {
			pixelData = texture.getTextureData();
		}

So getTextureData() is definitely the way to go.

#13

Ah, indeed. So like this then:

public byte[] getMask(Image img) {
    int stride = 4; // number of channels
    byte[] data = img.getTexture().getTextureData();
    for(int i = 1; i < data.length; i += stride) { // i = 0 if RGBA, i = 1 if ARGB
        data[i] = (data[i] & 0xFF) + 1 >> 8; // fixed this, now actually returns 1 only if data[i] = 255
    }
    return data;
}
#14

b = byte (method or array), then (b+1)>>8 yields 1 for 0xff and 0 otherwise. Only 0xff will overflow into the ninth bit. Likewise for 32-bit array accesses. d = ((r & 0xFF0000) + 0x10000) >> 24 if ‘alpha’ can be any value…the and can be removed if A is insured to be zero. If A is 0xff, the simply change the additive constant.

#15

Need to either & 0xFF or make sure that the byte is expanded to an int (EDIT: that is what’s killing it), doing (b+1)>>8 on a raw byte does not yield that behavior, oddly enough. Tripped me up earlier.

#16

Sorry to double post, but I realized my implementation wasn’t collapsing the array. (it would work, but you’d need other code that uses the mask to stride through it in the same manner, this one follows principal of least astonishment while still being pretty fast ;))


//assumes ARGB
public byte[] getMask(Image img) {
    int stride = 4;
    byte[] data = img.getTexture().getTextureData();
    byte[] mask = new byte[img.getWidth() * img.getHeight()];
    for(int i = 0; i < mask.length;) {
        mask[i++] = (data[i * stride] & 0xFF) + 1 >> 8;
    }
    return mask;
}

Try that out and tell me how it goes. Index mask as usual with mask[(x + y * w)]

#17

Thanks for all the help. You guys gave me great insight into how byte arrays work, I never could figure them out in the past. The whole concept of holding X and Y values (and the pixel’s color too!) in a single array is just mind bogglingly confusing to me.

Sadly though, I realized the major issue isnt coming from getColor, it’s coming from where getColor has to get it’s data. I was pulling the source image from a very large spritesheet and the problem is when .getColor (or any of your methods) are used it has to grab that value off a huge 1024x512 spritesheet, and there in lies the slowdown. I wasn’t realizing that even though I am only looking at a 32x32 image I pulled from the sheet, when it has to calculate color values it has to load up the entire sheet into memory. Thus, the major slowdown. Problem with that is, even your guy’s methods of snagging the byte array still has similar issues because of that. So your methods are a lot faster, but not fast enough!

In my tests with my current code, if I use a single 32x32 image I can run the code literally about 200 times faster. It executes using my old slow code countless times faster than even your guy’s versions. But, that’s not acceptable, I still need the source information to exist on the sprite sheet.

So, I’ve have a possible idea that may actually be even faster than the byte array examples you’ve been showing me. Basically it involves creating the data only once, based off the image (sort of a “first time load” deal) and saving it as a string of 0s and 1s in a .properties file. Then, I can build the array in-game off a 1024-digit long (height*width) properties key and skipping the need to even look at the image anymore.

Once that’s done, I can add a check on game load to just doublecheck all the last modified dates on the images I’m working with, if they’ve changed I can rebuild the data in the properties files, if they haven’t, just use the existing binary keys.

The final product should mean that the images are only touched once, ever. Unless I update the image, then the program will detect the change and regenerate the files specific to that one sprite sheet.

But even if my idea works out, I’ll probably still use the help you’ve given me and use your methods to do the initial build, because it’s still faster than mine. :smiley:

#18

Are they all tiles of the same size, and right up against each other on the sheet?


class ImageMaskFactory { //or something
    private byte[] sheetData;
    private int w, tileSize;

    public ImageMaskFactory(Image spriteSheet, int tileSize) { //tileSize is in pixels
        this.tileSize = tileSize;
        w = spriteSheet.getWidth();
        sheetData = spriteSheet.getTexture().getTextureData();
    }

    public byte[] getMask(int xSheetLocation, int ySheetLocation) {
        int stride = 4;
        int offset = xSheetLocation * tileSize + ySheetLocation * w * tileSize;
        byte[] mask = new byte[tileSize * tileSize];
        for(int i = 0; i < mask.length;) {
            mask[i++] = (sheetData[(offset + i % tileSize + i / tileSize * w) * stride] & 0xFF) + 1 >> 8; // I believe this is correct
        }
        return mask; //returns tileSize x tileSize mask cut out from the sheet buffer. Nifty!
    }

}

And if getMask() is called frequently with the same tile coords, you could set up a mask cache as well, trading memory for more speed.

#19

Just make sure, you load the image only once at startup and always use the same instance and you should be fine…

#20

I don’t know why nobody ever thought of this yet, but why not multi-thread?

You could (with java 8) use a parallel stream + map() :slight_smile: