Skip to main content

enforcing tile computation order

5 replies [Last post]
cafeanimal
Offline
Joined: 2008-04-29

Hi folks,

A while ago I wrote an operator to 'regionalize' an image, ie. identify regions of uniform value in the source image...

http://code.google.com/p/jai-tools/wiki/Regionalize

But I did a pretty poor job of dealing with regions that cross tile boundaries :-( The easiest way to fix the problems, and avoid artefacts on tile boundaries, is to impose an order to the computation of tiles. But what is the best way to do this ?

I'd rather not mess with TileScheduler if I don't have to (looks scary in there). I was thinking it might be OK to use java.util.concurrent classes within my OpImage class to impose an order, e.g. when tile X, Y is requested a blocking queue ensures that all prior (spatially) tiles are computed and cached first.

Does this sound reasonable ? Is there an easier way ?

Very grateful for any tips

cheers
Michael

Reply viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.
cafeanimal
Offline
Joined: 2008-04-29

The approach described in the last message seems to work well. The cost is that a caller requesting a single tile may have to wait while the fill algorithm fills regions extending into other tiles, but that's offset by results that make sense :)

Code for the new, hopefully reliable operator can be viewed online here...

http://bit.ly/lGTmF

...and you can check the code out from the same site using svn

As usual, any comments or patches will be very gratefully accepted.

Michael

cafeanimal
Offline
Joined: 2008-04-29

Worked out a way of doing this that appears (so far) to be ok. In the unlikely event that it's useful to anyone else, here's what I do...

1. Override the getTile method and check if other tiles, required to compute the currently requested tile (at tileX, tileY), are already in the cache. If not, process them in order...

synchronized (computeLock) {
for (int y = getMinTileY(); y <= tileY; y++) {
for (int x = getMinTileX(); x <= tileX; x++) {
if (getTileFromCache(x, y) == null) {
try {
tile = executor.submit(new ComputeTileTask(x, y)).get();
addTileToCache(x, y, tile);
} catch (ExecutionException execEx) {
throw new IllegalStateException(execEx);
} catch (InterruptedException intEx) {
// @todo is this safe ?
return null;
}
}
}
}
}

In the above snippet, executor is a single thread executor service and computeLock is a simple object...

this.executor = Executors.newSingleThreadExecutor();
this.computeLock = new Object();

ComputeTileTask is an inner class of the OpImage...

private class ComputeTileTask implements Callable<Raster> {
int tileX, tileY;
ComputeTileTask(int tileX, int tileY) {
this.tileX = tileX;
this.tileY = tileY;
}

public Raster call() throws Exception {
return computeTile(tileX, tileY);
}
}

Meanwhile, I've realized that even with tile computation order set, it's still possible for my regionalizing algorithm (based on a flood fill) to produce artefacts at tile boundaries :-( As far as I can see, the only way to avoid this is to pre-create and cache all of the destination tiles and do the flood-filling with iterators such that any single flood is allowed to cross a tile edge if necessary.

Michael

Simone Giannecchini

My suggestion might be competely worng, but what about using an
untiled image instead?

Simone.
-------------------------------------------------------
Ing. Simone Giannecchini
GeoSolutions S.A.S.
Founder - Software Engineer
Via Carignoni 51
55041 Camaiore (LU)
Italy

phone: +39 0584983027
fax: +39 0584983027
mob: +39 333 8128928

http://www.geo-solutions.it
http://geo-solutions.blogspot.com/
http://simboss.blogspot.com/
http://www.linkedin.com/in/simonegiannecchini

-------------------------------------------------------

On Tue, Sep 15, 2009 at 3:45 AM, wrote:
> Worked out a way of doing this that appears (so far) to be ok. In the unlikely event that it's useful to anyone else, here's what I do...
>
> 1. Override the getTile method and check if other tiles, required to compute the currently requested tile (at tileX, tileY), are already in the cache. If not, process them in order...
>
>                synchronized (computeLock) {
>                    for (int y = getMinTileY(); y <= tileY; y++) {
>                        for (int x = getMinTileX(); x <= tileX; x++) {
>                            if (getTileFromCache(x, y) == null) {
>                                try {
>                                    tile = executor.submit(new ComputeTileTask(x, y)).get();
>                                    addTileToCache(x, y, tile);
>
>                                } catch (ExecutionException execEx) {
>                                    throw new IllegalStateException(execEx);
>
>                                } catch (InterruptedException intEx) {
>                                    // @todo is this safe ?
>                                    return null;
>                                }
>                            }
>                        }
>                    }
>
> In the above snippet, executor is a single thread executor service and computeLock is a simple object...
>
>        this.executor = Executors.newSingleThreadExecutor();
>        this.computeLock = new Object();
>
> ComputeTileTask is an inner class of the OpImage...
>
>    private class ComputeTileTask implements Callable {
>        int tileX, tileY;
>
>        ComputeTileTask(int tileX, int tileY) {
>            this.tileX = tileX;
>            this.tileY = tileY;
>        }
>
>        public Raster call() throws Exception {
>            return computeTile(tileX, tileY);
>        }
>    }
>
> Meanwhile, I've realized that even with tile computation order set, it's still possible for my regionalizing algorithm (based on a flood fill) to produce artefacts at tile boundaries :-(  As far as I can see, the only way to avoid this is to pre-create and cache all of the destination tiles and do the flood-filling with iterators such that any single flood is allowed to cross a tile edge if necessary.
>
> Michael
> [Message sent by forum member 'cafeanimal' (michael.bedward@gmail.com)]
>
> http://forums.java.net/jive/thread.jspa?messageID=363965
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: interest-unsubscribe@jai.dev.java.net
> For additional commands, e-mail: interest-help@jai.dev.java.net
>
>

---------------------------------------------------------------------
To unsubscribe, e-mail: interest-unsubscribe@jai.dev.java.net
For additional commands, e-mail: interest-help@jai.dev.java.net

cafeanimal
Offline
Joined: 2008-04-29

> My suggestion might be competely worng, but what
> about using an
> untiled image instead?

Yes - with an untiled image the original algorithm works well but then you are limited in the size of the images that the operator can deal with.

At the moment I'm rewriting it (yet again !) so that the operator has its own jaitools.tiledimage.DiskMemImage to hold the destination data and provide a dedicated tile cache. Then, when a given tile is requested, the flood filler helper class processes the tile rectangle but also allows fills to extend into other tiles. That way, tiles can be requested in any order but region ID artefacts on tile boundaries will be avoided (fingers crossed).

As it happens, this approach also reduces the amount of code in the OpImage quite substantially !

Michael

cafeanimal
Offline
Joined: 2008-04-29

Bit more on this...

I'm now playing with having a single thread ExecutorService within my OpImage class, set up so to run tile compulations in the right order. Then when a client requests a particular tile the executor will execute tile computations in row/col order up to, and including, the requested tile.

Just trying to work out what to put into the Callable objects to be run, ie. what OpImage or other JAI class method(s) to call.

Don't know if this is the right track so I'd still appreciate any ideas.

cheers
Michael