sis-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From desruisse...@apache.org
Subject [sis] 02/02: Replace the use of `PixelIterator.Window` by cached values of previous row. It make easier to provide a special case for one-banded images.
Date Wed, 30 Dec 2020 19:23:13 GMT
This is an automated email from the ASF dual-hosted git repository.

desruisseaux pushed a commit to branch geoapi-4.0
in repository https://gitbox.apache.org/repos/asf/sis.git

commit eac2307ae6adc09729e069f1a0e43e1930e4e2a0
Author: Martin Desruisseaux <martin.desruisseaux@geomatys.com>
AuthorDate: Wed Dec 30 18:30:44 2020 +0100

    Replace the use of `PixelIterator.Window` by cached values of previous row.
    It make easier to provide a special case for one-banded images.
---
 .../internal/processing/image/IsolineTracer.java   | 43 +++++-----
 .../sis/internal/processing/image/Isolines.java    | 96 ++++++++++++++--------
 2 files changed, 85 insertions(+), 54 deletions(-)

diff --git a/core/sis-feature/src/main/java/org/apache/sis/internal/processing/image/IsolineTracer.java
b/core/sis-feature/src/main/java/org/apache/sis/internal/processing/image/IsolineTracer.java
index e42e362..364b186 100644
--- a/core/sis-feature/src/main/java/org/apache/sis/internal/processing/image/IsolineTracer.java
+++ b/core/sis-feature/src/main/java/org/apache/sis/internal/processing/image/IsolineTracer.java
@@ -21,7 +21,6 @@ import java.util.Map;
 import java.util.HashMap;
 import java.util.ArrayList;
 import java.util.Collections;
-import java.nio.DoubleBuffer;
 import java.awt.Point;
 import java.awt.Shape;
 import org.opengis.referencing.operation.MathTransform;
@@ -57,9 +56,9 @@ final class IsolineTracer {
     /**
      * The 2×2 window containing pixel values in the 4 corners of current contouring grid
cell.
      * Values are always stored with band index varying fastest, then column index, then
row index.
-     * Capacity and limit of data buffer is <var>(number of bands)</var> × 2
(width) × 2 (height).
+     * The length of this array is <var>(number of bands)</var> × 2 (width)
× 2 (height).
      */
-    private final DoubleBuffer window;
+    private final double[] window;
 
     /**
      * Increment to the position for reading next sample value.
@@ -89,7 +88,7 @@ final class IsolineTracer {
      * @param  pixelStride  increment to the position in {@code window} for reading next
sample value.
      * @param  gridToCRS    final transform to apply on coordinates.
      */
-    IsolineTracer(final DoubleBuffer window, final int pixelStride, final MathTransform gridToCRS)
{
+    IsolineTracer(final double[] window, final int pixelStride, final MathTransform gridToCRS)
{
         this.window      = window;
         this.pixelStride = pixelStride;
         this.gridToCRS   = gridToCRS;
@@ -103,6 +102,11 @@ final class IsolineTracer {
      */
     final class Level {
         /**
+         * Band number where to read values in the {@link #window} array.
+         */
+        private final int band;
+
+        /**
          * The level value.
          *
          * @see #interpolate(int, int)
@@ -122,8 +126,8 @@ final class IsolineTracer {
          * }
          *
          * Bits are set to 1 where the data value is above the isoline {@linkplain #value},
and 0 where the data
-         * value is equal or below the isoline value. Data values exactly equal to the isoline
value are handled
-         * as if they were greater. It does not matter for interpolations: we could flip
this convention randomly,
+         * value is below the isoline value. Data values exactly equal to the isoline value
are handled as if
+         * they were greater. It does not matter for interpolations: we could flip this convention
randomly,
          * the interpolated points would still the same. It could change the way line segments
are assembled in a
          * single {@link Polyline}, but the algorithm stay consistent if we always apply
the same rule for all points.
          *
@@ -219,10 +223,12 @@ final class IsolineTracer {
         /**
          * Creates new isoline levels for the given value.
          *
+         * @param  band   band number where to read values in the {@link #window} array.
          * @param  value  the isoline level value.
          * @param  width  the contouring grid cell width (one cell smaller than image width).
          */
-        Level(final double value, final int width) {
+        Level(final int band, final double value, final int width) {
+            this.band      = band;
             this.value     = value;
             partialPaths   = new HashMap<>();
             polylineOnLeft = new Polyline();
@@ -235,6 +241,8 @@ final class IsolineTracer {
         /**
          * Initializes the {@link #isDataAbove} value with values for the column on the right
side.
          * After this method call, the {@link #UPPER_RIGHT} and {@link #LOWER_RIGHT} bits
still need to be set.
+         *
+         * @see Isolines#setMaskBit(double, int)
          */
         final void nextColumn() {
             /*
@@ -367,12 +375,11 @@ final class IsolineTracer {
                 case UPPER_LEFT | LOWER_RIGHT: {
                     double average = 0;
                     {   // Compute sum of 4 corners.
-                        final DoubleBuffer data = window;
-                        final int limit = data.limit();
-                        int p = data.position();
-                        do average += data.get(p);
-                        while ((p += pixelStride) < limit);
-                        assert (p -= data.position()) == pixelStride * 4 : p;
+                        final double[] data = window;
+                        int p = band;
+                        do average += data[p];
+                        while ((p += pixelStride) < data.length);
+                        assert (p -= band) == pixelStride * 4 : p;
                         average /= 4;
                     }
                     boolean LLtoUR = isDataAbove == (LOWER_LEFT | UPPER_RIGHT);
@@ -439,18 +446,16 @@ final class IsolineTracer {
 
         /**
          * Interpolates the position where the isoline passes between two values.
-         * The {@link #window} buffer position shall be the first sample value
-         * for the band to process.
          *
          * @param  i1  index of first value in the buffer, ignoring band offset.
          * @param  i2  index of second value in the buffer, ignoring band offset.
          * @return a value interpolated between the values at the two given indices.
          */
         private double interpolate(final int i1, final int i2) {
-            final DoubleBuffer data = window;
-            final int    p  = data.position();
-            final double v1 = data.get(p + i1);
-            final double v2 = data.get(p + i2);
+            final double[] data = window;
+            final int    p  = band;
+            final double v1 = data[p + i1];
+            final double v2 = data[p + i2];
             return (value - v1) / (v2 - v1);
         }
 
diff --git a/core/sis-feature/src/main/java/org/apache/sis/internal/processing/image/Isolines.java
b/core/sis-feature/src/main/java/org/apache/sis/internal/processing/image/Isolines.java
index e1c6443..8072396 100644
--- a/core/sis-feature/src/main/java/org/apache/sis/internal/processing/image/Isolines.java
+++ b/core/sis-feature/src/main/java/org/apache/sis/internal/processing/image/Isolines.java
@@ -19,8 +19,6 @@ package org.apache.sis.internal.processing.image;
 import java.util.Arrays;
 import java.util.TreeMap;
 import java.util.NavigableMap;
-import java.nio.DoubleBuffer;
-import java.awt.Dimension;
 import java.awt.Shape;
 import java.awt.geom.Path2D;
 import java.awt.image.RenderedImage;
@@ -29,7 +27,6 @@ import org.opengis.referencing.operation.MathTransform;
 import org.opengis.referencing.operation.TransformException;
 import org.apache.sis.referencing.operation.transform.MathTransforms;
 import org.apache.sis.image.PixelIterator;
-import org.apache.sis.image.TransferType;
 import org.apache.sis.util.ArgumentChecks;
 import org.apache.sis.util.ArraysExt;
 
@@ -62,7 +59,7 @@ public final class Isolines {
      * The given array should be a clone of user-provided array because
      * this constructor may modify it in-place.
      */
-    private Isolines(final IsolineTracer tracer, final double[] values, final int width)
{
+    private Isolines(final IsolineTracer tracer, final int band, final double[] values, final
int width) {
         Arrays.sort(values);
         int n = values.length;
         while (n > 0 && Double.isNaN(values[n-1])) n--;
@@ -74,15 +71,12 @@ public final class Isolines {
         }
         levels = new IsolineTracer.Level[n];
         for (int i=0; i<n; i++) {
-            levels[i] = tracer.new Level(values[i], width);
+            levels[i] = tracer.new Level(band, values[i], width);
         }
     }
 
     /**
-     * Sets the specified bit on {@link IsolineTracer.Level#isDataAbove} for all levels lower
than buffer value.
-     * The {@code window} buffer shall be positioned on the value to read, consistently with
{@code bit} value.
-     * After this method call, the buffer position will be incremented to the next band if
there is more bands
-     * to read, or to the next pixel otherwise.
+     * Sets the specified bit on {@link IsolineTracer.Level#isDataAbove} for all levels lower
than given value.
      *
      * <h4>How strict equalities are handled</h4>
      * Sample values exactly equal to the isoline value are handled as if they were greater.
It does not matter
@@ -96,12 +90,13 @@ public final class Isolines {
      * will produce NaN values and append them to polylines like real values.  Those NaN
values will be filtered
      * out in the final stage, when copying coordinates in {@link Path2D} objects.
      *
-     * @param  data  a 2×2 view on pixel values in the image.
+     * @param  value a sample values from the image.
      * @param  bit   {@value IsolineTracer#UPPER_LEFT}, {@value IsolineTracer#UPPER_RIGHT},
      *               {@value IsolineTracer#LOWER_LEFT} or {@value IsolineTracer#LOWER_RIGHT}.
+     *
+     * @see IsolineTracer.Level#nextColumn()
      */
-    private void setMaskBit(final DoubleBuffer data, final int bit) {
-        final double value = data.get();
+    private void setMaskBit(final double value, final int bit) {
         for (final IsolineTracer.Level level : levels) {
             if (level.value > value) break;                 // See above javadoc for NaN
handling.
             level.isDataAbove |= bit;
@@ -134,21 +129,21 @@ public final class Isolines {
                 gridToCRS = MathTransforms.concatenate(gridToImage, gridToCRS);
             }
         }
-        final PixelIterator iterator = new PixelIterator.Builder().setIteratorOrder(SequenceType.LINEAR)
-                                                        .setWindowSize(new Dimension(2,2)).create(data);
+        final PixelIterator iterator = new PixelIterator.Builder().setIteratorOrder(SequenceType.LINEAR).create(data);
         /*
-         * A window of size 2×2 pixels over pixel values.
+         * Prepares a window of size 2×2 pixels over pixel values. Window elements are traversed
+         * by incrementing indices in following order: band, column, row. The window content
will
+         * be written in this method and read by IsolineTracer.
          */
-        final PixelIterator.Window<DoubleBuffer> window = iterator.createWindow(TransferType.DOUBLE);
-        final DoubleBuffer buffer = window.values;
         final int numBands = iterator.getNumBands();
-        final IsolineTracer tracer = new IsolineTracer(buffer, numBands, gridToCRS);
+        final double[] window = new double[numBands * 4];
+        final IsolineTracer tracer = new IsolineTracer(window, numBands, gridToCRS);
         /*
          * Prepare the set of isolines for each band in the image.
          * The number of cells on the horizontal axis is one less
          * than the image width.
          */
-        final int width = data.getWidth() - 1;
+        final int width = iterator.getDomain().width - 1;
         final Isolines[] isolines = new Isolines[numBands];
         {   // For keeping variable locale.
             double[] levelValues = ArraysExt.EMPTY_DOUBLE;
@@ -158,46 +153,77 @@ public final class Isolines {
                     ArgumentChecks.ensureNonNullElement("levels", b, levelValues);
                     levelValues = levelValues.clone();
                 }
-                isolines[b] = new Isolines(tracer, levelValues, width);
+                isolines[b] = new Isolines(tracer, b, levelValues, width);
             }
         }
         /*
+         * Cache sample values on the top row. Those values are reused by the row just below
row
+         * of cached values. This array is updated during iteration with values of current
cell.
+         */
+        final double[] pixelValues = new double[numBands];
+        final double[] valuesOnPreviousRow = new double[numBands * (width+1)];
+        for (int i=0; i < valuesOnPreviousRow.length; i += numBands) {
+            if (!iterator.next()) return isolines;
+            System.arraycopy(iterator.getPixel(pixelValues), 0, valuesOnPreviousRow, i, numBands);
+        }
+        /*
          * Compute isolines for all bands. Iteration over bands must be the innermost loop
because
          * data layout in buffer is band index varying fastest, then column index, then row
index.
          */
+        final int twoPixels = numBands * 2;
         final int lastPixel = numBands * 3;
 abort:  while (iterator.next()) {
             /*
-             * First pixel of a new row.
+             * Process the first cell of a new row:
+             *
+             *  - Get values on the 4 corners.
+             *  - Save value of lower-left corner for use by next row.
+             *  - Initialize `IsolineTracer.Level.isDataAbove` bits for all levels.
+             *  - Interpolate the first cell.
              */
-            window.update();        // Also reset buffer position to zero.
-            for (int flag = UPPER_LEFT; flag <= LOWER_RIGHT; flag <<= 1) {
+            System.arraycopy(valuesOnPreviousRow, 0, window, 0, twoPixels);
+            System.arraycopy(iterator.getPixel(pixelValues), 0, window, twoPixels, numBands);
+            if (!iterator.next()) break;
+            System.arraycopy(iterator.getPixel(pixelValues), 0, window, lastPixel, numBands);
+            System.arraycopy(window, twoPixels, valuesOnPreviousRow, 0, twoPixels);
+            for (int i=0, flag = UPPER_LEFT; flag <= LOWER_RIGHT; flag <<= 1) {
                 for (int b=0; b<numBands; b++) {        // Must be the inner loop (see
above comment).
-                    isolines[b].setMaskBit(buffer, flag);
+                    isolines[b].setMaskBit(window[i++], flag);
                 }
             }
-            for (int b=0; b<numBands; b++) {
-                buffer.position(b);
-                for (final IsolineTracer.Level level : isolines[b].levels) {
+            for (final Isolines iso : isolines) {
+                for (final IsolineTracer.Level level : iso.levels) {
                     level.interpolate();
                 }
             }
             /*
-             * All pixels on a row after the first column. We can reuse the bitmask of previous
-             * iteration with a simple bit shift operation.
+             * Process all pixels on a row after the first column. We can reuse the bitmask
of previous
+             * iteration with a simple bit shift operation. This is done by the `nextColumn()`
call.
+             * The series for `System.arraycopy(…)` calls are for moving 3 pixel values
of previous
+             * iteration that we can reuse, then fetch the only new value from the iterator.
              */
             for (tracer.x = 1; tracer.x < width; tracer.x++) {
-                if (!iterator.next()) break abort;
-                window.update();
+                final int offsetOnPreviousRow = (tracer.x + 1) * numBands;
+                if (!iterator.next()) break abort;                              // Should
never abort
+                if (numBands == 1) {                                            // Optimization
for a common case
+                    window[2] = window[3];                                      // Lower-right
→ Lower-left
+                    window[0] = window[1];                                      // Upper-right
→ Upper-left
+                    window[1] = valuesOnPreviousRow[offsetOnPreviousRow];       // Take upper-right
from previous row
+                    window[3] = valuesOnPreviousRow[offsetOnPreviousRow] = iterator.getSampleDouble(0);
+                } else {
+                    System.arraycopy(window, numBands,  window, 0,         numBands);   //
Upper-right → Upper-left
+                    System.arraycopy(window, lastPixel, window, twoPixels, numBands);   //
Lower-right → Lower-left
+                    System.arraycopy(valuesOnPreviousRow, offsetOnPreviousRow, window, numBands,
numBands);
+                    System.arraycopy(iterator.getPixel(pixelValues), 0, window, lastPixel,
numBands);
+                    System.arraycopy(window, lastPixel, valuesOnPreviousRow, offsetOnPreviousRow,
numBands);
+                }
                 for (int b=0; b<numBands; b++) {
                     final Isolines iso = isolines[b];
                     for (final IsolineTracer.Level level : iso.levels) {
                         level.nextColumn();
                     }
-                    // TODO! remove cast on JDK9.
-                    iso.setMaskBit((DoubleBuffer) buffer.position(numBands  + b), UPPER_RIGHT);
-                    iso.setMaskBit((DoubleBuffer) buffer.position(lastPixel + b), LOWER_RIGHT);
-                    buffer.position(b);
+                    iso.setMaskBit(window[numBands  + b], UPPER_RIGHT);
+                    iso.setMaskBit(window[lastPixel + b], LOWER_RIGHT);
                     for (final IsolineTracer.Level level : iso.levels) {
                         level.interpolate();
                     }


Mime
View raw message