001// License: GPL. For details, see LICENSE file.
002package org.openstreetmap.josm.tools;
003
004import java.awt.Dimension;
005import java.awt.geom.Point2D;
006import java.awt.geom.Rectangle2D;
007import java.awt.image.BufferedImage;
008import java.awt.image.DataBuffer;
009import java.util.HashMap;
010import java.util.HashSet;
011import java.util.Map;
012import java.util.Objects;
013import java.util.Set;
014
015/**
016 * Image warping algorithm.
017 * <p>
018 * Deforms an image geometrically according to a given transformation formula.
019 * @since 11858
020 */
021public final class ImageWarp {
022
023    private ImageWarp() {
024        // Hide default constructor
025    }
026
027    /**
028     * Transformation that translates the pixel coordinates.
029     */
030    @FunctionalInterface
031    public interface PointTransform {
032        /**
033         * Translates pixel coordinates.
034         * @param x The x coordinate
035         * @param y The y coordinate
036         * @return transformed pixel coordinates
037         */
038        Point2D transform(double x, double y);
039    }
040
041    /**
042     * Wrapper that optimizes a given {@link ImageWarp.PointTransform}.
043     * <p>
044     * It does so by spanning a grid with certain step size. It will invoke the
045     * potentially expensive master transform only at those grid points and use
046     * bilinear interpolation to approximate transformed values in between.
047     * <p>
048     * For memory optimization, this class assumes that rows are more or less scanned
049     * one-by-one as is done in {@link ImageWarp#warp}. I.e. this transform is <em>not</em>
050     * random access in the y coordinate.
051     */
052    public static class GridTransform implements ImageWarp.PointTransform {
053
054        private final double stride;
055        private final ImageWarp.PointTransform trfm;
056
057        private final Map<Integer, Map<Integer, Point2D>> cache;
058
059        private final boolean consistencyTest;
060        private final Set<Integer> deletedRows;
061
062        /**
063         * Create a new GridTransform.
064         * @param trfm the master transform, that needs to be optimized
065         * @param stride step size
066         */
067        public GridTransform(ImageWarp.PointTransform trfm, double stride) {
068            this.trfm = trfm;
069            this.stride = stride;
070            this.cache = new HashMap<>();
071            this.consistencyTest = Logging.isDebugEnabled();
072            if (consistencyTest) {
073                deletedRows = new HashSet<>();
074            } else {
075                deletedRows = null;
076            }
077        }
078
079        @Override
080        public Point2D transform(double x, double y) {
081            int xIdx = (int) Math.floor(x / stride);
082            int yIdx = (int) Math.floor(y / stride);
083            double dx = x / stride - xIdx;
084            double dy = y / stride - yIdx;
085            Point2D value00 = getValue(xIdx, yIdx);
086            Point2D value01 = getValue(xIdx, yIdx + 1);
087            Point2D value10 = getValue(xIdx + 1, yIdx);
088            Point2D value11 = getValue(xIdx + 1, yIdx + 1);
089            double valueX = (value00.getX() * (1-dx) + value10.getX() * dx) * (1-dy) +
090                    (value01.getX() * (1-dx) + value11.getX() * dx) * dy;
091            double valueY = (value00.getY() * (1-dx) + value10.getY() * dx) * (1-dy) +
092                    (value01.getY() * (1-dx) + value11.getY() * dx) * dy;
093            return new Point2D.Double(valueX, valueY);
094        }
095
096        private Point2D getValue(int xIdx, int yIdx) {
097            final Map<Integer, Point2D> rowMap = getRow(yIdx);
098            // This *was* computeIfAbsent. Unfortunately, it appears that it generated a ton of memory allocations.
099            // As in, this was ~50 GB memory allocations in a test, and converting to a non-lambda form made it 1.3GB.
100            // The primary culprit was LambdaForm#linkToTargetMethod
101            Point2D current = rowMap.get(xIdx);
102            if (current == null) {
103                current = trfm.transform(xIdx * stride, yIdx * stride);
104                rowMap.put(xIdx, current);
105            }
106            return current;
107        }
108
109        private Map<Integer, Point2D> getRow(int yIdx) {
110            cleanUp(yIdx - 3);
111            Map<Integer, Point2D> row = cache.get(yIdx);
112            // Note: using computeIfAbsent will drastically increase memory allocations
113            if (row == null) {
114                row = new HashMap<>(256);
115                cache.put(yIdx, row);
116                if (consistencyTest) {
117                    // should not create a row that has been deleted before
118                    if (deletedRows.contains(yIdx)) throw new AssertionError();
119                    // only ever cache 3 rows at once
120                    if (cache.size() > 3) throw new AssertionError();
121                }
122            }
123            return row;
124        }
125
126        // remove rows from cache that will no longer be used
127        private void cleanUp(int yIdx) {
128            Map<Integer, Point2D> del = cache.remove(yIdx);
129            if (consistencyTest && del != null) {
130                // should delete each row only once
131                if (deletedRows.contains(yIdx)) throw new AssertionError();
132                deletedRows.add(yIdx);
133            }
134        }
135    }
136
137    /**
138     * Interpolation method.
139     */
140    public enum Interpolation {
141        /**
142         * Nearest neighbor.
143         * <p>
144         * Simplest possible method. Faster, but not very good quality.
145         */
146        NEAREST_NEIGHBOR,
147
148        /**
149         * Bilinear.
150         * <p>
151         * Decent quality.
152         */
153        BILINEAR;
154    }
155
156    /**
157     * Warp an image.
158     * @param srcImg the original image
159     * @param targetDim dimension of the target image
160     * @param invTransform inverse transformation (translates pixel coordinates
161     * of the target image to pixel coordinates of the original image)
162     * @param interpolation the interpolation method
163     * @return the warped image
164     */
165    public static BufferedImage warp(BufferedImage srcImg, Dimension targetDim, PointTransform invTransform, Interpolation interpolation) {
166        Objects.requireNonNull(interpolation, "interpolation");
167        BufferedImage imgTarget = new BufferedImage(targetDim.width, targetDim.height, BufferedImage.TYPE_INT_ARGB);
168        Rectangle2D srcRect = new Rectangle2D.Double(0, 0, srcImg.getWidth(), srcImg.getHeight());
169        // These arrays reduce the amount of memory allocations (getRGB and setRGB are
170        // collectively 40% of the memory cost, 78% if LambdaForm#linkToTargetMethod is
171        // ignored). We mostly want to decrease GC pauses here.
172        final int[] pixel = new int[1]; // Yes, this really does decrease memory allocations with TYPE_INT_ARGB.
173        final Object sharedArray = getSharedArray(srcImg);
174        for (int j = 0; j < imgTarget.getHeight(); j++) {
175            for (int i = 0; i < imgTarget.getWidth(); i++) {
176                Point2D srcCoord = invTransform.transform(i, j);
177                if (srcRect.contains(srcCoord)) {
178                    // Convert to switch expression when we switch to Java 17+.
179                    int rgba = 0; // Initialized here so the compiler doesn't complain. Otherwise, BILINEAR needs to have it start at 0.
180                    switch (interpolation) {
181                        case NEAREST_NEIGHBOR:
182                            rgba = getColor((int) Math.round(srcCoord.getX()), (int) Math.round(srcCoord.getY()), srcImg, sharedArray);
183                            break;
184                        case BILINEAR:
185                            int x0 = (int) Math.floor(srcCoord.getX());
186                            double dx = srcCoord.getX() - x0;
187                            int y0 = (int) Math.floor(srcCoord.getY());
188                            double dy = srcCoord.getY() - y0;
189                            int c00 = getColor(x0, y0, srcImg, sharedArray);
190                            int c01 = getColor(x0, y0 + 1, srcImg, sharedArray);
191                            int c10 = getColor(x0 + 1, y0, srcImg, sharedArray);
192                            int c11 = getColor(x0 + 1, y0 + 1, srcImg, sharedArray);
193                            // rgba
194                            // loop over color components: blue, green, red, alpha
195                            for (int ch = 0; ch <= 3; ch++) {
196                                int shift = 8 * ch;
197                                int chVal = (int) Math.round(
198                                    (((c00 >> shift) & 0xff) * (1-dx) + ((c10 >> shift) & 0xff) * dx) * (1-dy) +
199                                    (((c01 >> shift) & 0xff) * (1-dx) + ((c11 >> shift) & 0xff) * dx) * dy);
200                                rgba |= chVal << shift;
201                            }
202                            break;
203                    }
204                    imgTarget.getRaster().setDataElements(i, j, imgTarget.getColorModel().getDataElements(rgba, pixel));
205                }
206            }
207        }
208        return imgTarget;
209    }
210
211    private static Object getSharedArray(BufferedImage srcImg) {
212        final int numBands = srcImg.getRaster().getNumBands();
213        // Add data types as needed (shown via profiling, look for getRGB).
214        switch (srcImg.getRaster().getDataBuffer().getDataType()) {
215            case DataBuffer.TYPE_BYTE:
216                return new byte[numBands];
217            case DataBuffer.TYPE_INT:
218                return new int[numBands];
219            default:
220                return null;
221        }
222    }
223
224    private static int getColor(int x, int y, BufferedImage img, Object sharedArray) {
225        // border strategy: continue with the color of the outermost pixel,
226        final int rx = Utils.clamp(x, 0, img.getWidth() - 1);
227        final int ry = Utils.clamp(y, 0, img.getHeight() - 1);
228        if (sharedArray == null) {
229            return img.getRGB(rx, ry);
230        }
231        return img.getColorModel().getRGB(img.getRaster().getDataElements(rx, ry, sharedArray));
232    }
233}