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}