001 /* 002 * 003 004 Licensed under the Apache License, Version 2.0 (the "License"); 005 you may not use this file except in compliance with the License. 006 You may obtain a copy of the License at 007 008 http://www.apache.org/licenses/LICENSE-2.0 009 010 Unless required by applicable law or agreed to in writing, software 011 distributed under the License is distributed on an "AS IS" BASIS, 012 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 013 See the License for the specific language governing permissions and 014 limitations under the License. 015 */ 016 017 package railo.runtime.img.filter; 018 019 /** 020 * A warp grid. 021 * From "A simplified approach to Image Processing" by Randy Crane 022 */ 023 public class WarpGrid { 024 025 public float[] xGrid = null; 026 public float[] yGrid = null; 027 public int rows, cols; 028 029 public WarpGrid(int rows, int cols, int w, int h) { 030 this.rows = rows; 031 this.cols = cols; 032 xGrid = new float[rows*cols]; 033 yGrid = new float[rows*cols]; 034 int index = 0; 035 for (int row = 0; row < rows; row++) { 036 for (int col = 0; col < cols; col++) { 037 xGrid[index] = (float)col*(w-1)/(cols-1); 038 yGrid[index] = (float)row*(h-1)/(rows-1); 039 index++; 040 } 041 } 042 } 043 044 /** 045 * Add a new row to the grid. "before" must be in the range 1..rows-1. i.e. you can only add rows inside the grid. 046 */ 047 public void addRow( int before ) { 048 int size = (rows+1) * cols; 049 float[] x = new float[size]; 050 float[] y = new float[size]; 051 052 rows++; 053 int i = 0; 054 int j = 0; 055 for (int row = 0; row < rows; row++) { 056 for (int col = 0; col < cols; col++) { 057 int k = j+col; 058 int l = i+col; 059 if ( row == before ) { 060 x[k] = (xGrid[l]+xGrid[k])/2; 061 y[k] = (yGrid[l]+yGrid[k])/2; 062 } else { 063 x[k] = xGrid[l]; 064 y[k] = yGrid[l]; 065 } 066 } 067 if ( row != before-1 ) 068 i += cols; 069 j += cols; 070 } 071 xGrid = x; 072 yGrid = y; 073 } 074 075 /** 076 * Add a new column to the grid. "before" must be in the range 1..cols-1. i.e. you can only add columns inside the grid. 077 */ 078 public void addCol( int before ) { 079 int size = rows * (cols+1); 080 float[] x = new float[size]; 081 float[] y = new float[size]; 082 083 cols++; 084 int i = 0; 085 int j = 0; 086 for (int row = 0; row < rows; row++) { 087 // int i = row*(cols-1); 088 // int j = row*cols; 089 for (int col = 0; col < cols; col++) { 090 if ( col == before ) { 091 x[j] = (xGrid[i]+xGrid[i-1])/2; 092 y[j] = (yGrid[i]+yGrid[i-1])/2; 093 } else { 094 x[j] = xGrid[i]; 095 y[j] = yGrid[i]; 096 i++; 097 } 098 j++; 099 } 100 } 101 xGrid = x; 102 yGrid = y; 103 } 104 105 /** 106 * Remove a row from the grid. 107 */ 108 public void removeRow( int r ) { 109 int size = (rows-1) * cols; 110 float[] x = new float[size]; 111 float[] y = new float[size]; 112 113 rows--; 114 int i = 0; 115 int j = 0; 116 for (int row = 0; row < rows; row++) { 117 for (int col = 0; col < cols; col++) { 118 int k = j+col; 119 int l = i+col; 120 x[k] = xGrid[l]; 121 y[k] = yGrid[l]; 122 } 123 if ( row == r-1 ) 124 i += cols; 125 i += cols; 126 j += cols; 127 } 128 xGrid = x; 129 yGrid = y; 130 } 131 132 /** 133 * Remove a column from the grid. 134 */ 135 public void removeCol( int r ) { 136 int size = rows * (cols+1); 137 float[] x = new float[size]; 138 float[] y = new float[size]; 139 140 cols--; 141 for (int row = 0; row < rows; row++) { 142 int i = row*(cols+1); 143 int j = row*cols; 144 for (int col = 0; col < cols; col++) { 145 x[j] = xGrid[i]; 146 y[j] = yGrid[i]; 147 if ( col == r-1 ) 148 i++; 149 i++; 150 j++; 151 } 152 } 153 xGrid = x; 154 yGrid = y; 155 } 156 157 public void lerp(float t, WarpGrid destination, WarpGrid intermediate) { 158 if (rows != destination.rows || cols != destination.cols) 159 throw new IllegalArgumentException("source and destination are different sizes"); 160 if (rows != intermediate.rows || cols != intermediate.cols) 161 throw new IllegalArgumentException("source and intermediate are different sizes"); 162 int index = 0; 163 for (int row = 0; row < rows; row++) { 164 for (int col = 0; col < cols; col++) { 165 intermediate.xGrid[index] = ImageMath.lerp(t, xGrid[index], destination.xGrid[index]); 166 intermediate.yGrid[index] = ImageMath.lerp(t, yGrid[index], destination.yGrid[index]); 167 index++; 168 } 169 } 170 } 171 172 public void warp(int[] inPixels, int cols, int rows, WarpGrid sourceGrid, WarpGrid destGrid, int[] outPixels) { 173 try { 174 int x, y; 175 int u, v; 176 int[] intermediate; 177 WarpGrid splines; 178 179 if (sourceGrid.rows != destGrid.rows || sourceGrid.cols != destGrid.cols) 180 throw new IllegalArgumentException("source and destination grids are different sizes"); 181 182 int size = Math.max(cols, rows); 183 float[] xrow = new float[size]; 184 float[] yrow = new float[size]; 185 float[] scale = new float[size + 1]; 186 float[] interpolated = new float[size + 1]; 187 188 int gridCols = sourceGrid.cols; 189 int gridRows = sourceGrid.rows; 190 191 splines = new WarpGrid(rows, gridCols, 1, 1); 192 193 for (u = 0; u < gridCols;u++) { 194 int i = u; 195 196 for (v = 0; v < gridRows;v++) { 197 xrow[v] = sourceGrid.xGrid[i]; 198 yrow[v] = sourceGrid.yGrid[i]; 199 i += gridCols; 200 } 201 202 interpolateSpline(yrow, xrow, 0, gridRows, interpolated, 0, rows); 203 204 i = u; 205 for (y = 0;y < rows;y++) { 206 splines.xGrid[i] = interpolated[y]; 207 i += gridCols; 208 } 209 } 210 211 for (u = 0; u < gridCols;u++) { 212 int i = u; 213 214 for (v = 0; v < gridRows;v++) { 215 xrow[v] = destGrid.xGrid[i]; 216 yrow[v] = destGrid.yGrid[i]; 217 i += gridCols; 218 } 219 220 interpolateSpline(yrow, xrow, 0, gridRows, interpolated, 0, rows); 221 222 i = u; 223 for (y = 0;y < rows; y++) { 224 splines.yGrid[i] = interpolated[y]; 225 i += gridCols; 226 } 227 } 228 229 /* first pass: warp x using splines */ 230 intermediate = new int[rows*cols]; 231 232 int offset = 0; 233 for (y = 0; y < rows; y++) { 234 /* fit spline to x-intercepts;resample over all cols */ 235 interpolateSpline(splines.xGrid, splines.yGrid, offset, gridCols, scale, 0, cols); 236 scale[cols] = cols; 237 ImageMath.resample(inPixels, intermediate, cols, y*cols, 1, scale); 238 offset += gridCols; 239 } 240 /* create table of y-intercepts for intermediate mesh's hor splines */ 241 242 splines = new WarpGrid(gridRows, cols, 1, 1); 243 244 offset = 0; 245 int offset2 = 0; 246 for (v = 0; v < gridRows; v++) { 247 interpolateSpline(sourceGrid.xGrid, sourceGrid.yGrid, offset, gridCols, splines.xGrid, offset2, cols); 248 offset += gridCols; 249 offset2 += cols; 250 } 251 252 offset = 0; 253 offset2 = 0; 254 for (v = 0; v < gridRows; v++) { 255 interpolateSpline(destGrid.xGrid, destGrid.yGrid, offset, gridCols, splines.yGrid, offset2, cols); 256 offset += gridCols; 257 offset2 += cols; 258 } 259 260 /* second pass: warp y */ 261 262 for (x = 0; x < cols; x++) { 263 int i = x; 264 265 for (v = 0; v < gridRows; v++) { 266 xrow[v] = splines.xGrid[i];; 267 yrow[v] = splines.yGrid[i];; 268 i += cols; 269 } 270 271 interpolateSpline(xrow, yrow, 0, gridRows, scale, 0, rows); 272 scale[rows] = rows; 273 ImageMath.resample(intermediate, outPixels, rows, x, cols, scale); 274 } 275 } 276 catch (Exception e) { 277 278 } 279 } 280 281 private final static float m00 = -0.5f; 282 private final static float m01 = 1.5f; 283 private final static float m02 = -1.5f; 284 private final static float m03 = 0.5f; 285 private final static float m10 = 1.0f; 286 private final static float m11 = -2.5f; 287 private final static float m12 = 2.0f; 288 private final static float m13 = -0.5f; 289 private final static float m20 = -0.5f; 290 private final static float m22 = 0.5f; 291 private final static float m31 = 1.0f; 292 293 protected void interpolateSpline(float[] xKnots, float[] yKnots, int offset, int length, float[] splineY, int splineOffset, int splineLength) { 294 int index = offset; 295 int end = offset+length-1; 296 float x0, x1; 297 float k0, k1, k2, k3; 298 float c0, c1, c2, c3; 299 300 x0 = xKnots[index]; 301 k0 = k1 = k2 = yKnots[index]; 302 x1 = xKnots[index+1]; 303 k3 = yKnots[index+1]; 304 305 for (int i = 0;i < splineLength;i++) { 306 if (index <= end && i > xKnots[index]) { 307 k0 = k1; 308 k1 = k2; 309 k2 = k3; 310 x0 = xKnots[index]; 311 index++; 312 if ( index <= end ) 313 x1 = xKnots[index]; 314 if ( index < end ) 315 k3 = yKnots[index+1]; 316 else 317 k3 = k2; 318 } 319 float t = (i - x0) / (x1 - x0); 320 c3 = m00*k0 + m01*k1 + m02*k2 + m03*k3; 321 c2 = m10*k0 + m11*k1 + m12*k2 + m13*k3; 322 c1 = m20*k0 + m22*k2; 323 c0 = m31*k1; 324 325 splineY[splineOffset+i] = ((c3*t + c2)*t + c1)*t + c0; 326 } 327 } 328 329 protected void interpolateSpline2(float[] xKnots, float[] yKnots, int offset, float[] splineY, int splineOffset, int splineLength) { 330 int index = offset; 331 float leftX, rightX; 332 float leftY, rightY; 333 334 leftX = xKnots[index]; 335 leftY = yKnots[index]; 336 rightX = xKnots[index+1]; 337 rightY = yKnots[index+1]; 338 339 for (int i = 0;i < splineLength;i++) { 340 if (i > xKnots[index]) { 341 leftX = xKnots[index]; 342 leftY = yKnots[index]; 343 index++; 344 rightX = xKnots[index]; 345 rightY = yKnots[index]; 346 } 347 float f = (i - leftX) / (rightX - leftX); 348 splineY[splineOffset+i] = leftY + f * (rightY - leftY); 349 } 350 } 351 }