Source code

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