001/*******************************************************************************
002 * This software is provided as a supplement to the authors' textbooks on digital
003 * image processing published by Springer-Verlag in various languages and editions.
004 * Permission to use and distribute this software is granted under the BSD 2-Clause
005 * "Simplified" License (see http://opensource.org/licenses/BSD-2-Clause).
006 * Copyright (c) 2006-2023 Wilhelm Burger, Mark J. Burge. All rights reserved.
007 * Visit https://imagingbook.com for additional details.
008 ******************************************************************************/
009package imagingbook.spectral.dft;
010
011import java.util.Arrays;
012
013/**
014 * <p>
015 * Common interface for all 2D DFT/FFT implementations. Data arrays are indexed
016 * as {@code data[x][y]}, with 0 &le; x &lt; width and 0 &le; y &lt; height.
017 * Based on associated one-dimensional DFT/FFT methods (see {@link Dft1d}). See
018 * Ch. 19 of [1] for additional details.
019 * </p>
020 * <p>
021 * [1] W. Burger, M.J. Burge, <em>Digital Image Processing &ndash; An Algorithmic
022 * Introduction</em>, 3rd ed, Springer (2022).
023 * </p>
024 * 
025 * @author WB
026 * @version 2022/10/21
027 * @see Dft1d
028 */
029public interface Dft2d {
030        
031        /**
032         * Returns the 'width' of the 2D data array (length of dimension 0).
033         * Data arrays are indexed as {@code data[x][y]}, with 
034         * 0 &le; x &lt; width and 0 &le; y &lt; height.
035         * @return the width of the 2D data array
036         */
037        public int getWidth();
038        
039        /**
040         * Returns the 'height' of the 2D data array (length of dimension 1).
041         * Data arrays are indexed as {@code data[x][y]}, with 
042         * 0 &le; x &lt; width and 0 &le; y &lt; height.
043         * @return the height of the 2D data array
044         */
045        public int getHeight();
046        
047        /**
048         * Returns the scaling mode of this DFT (see {@link ScalingMode}).
049         * @return the scaling mode of this DFT.
050         */
051        public ScalingMode getScalingMode();
052        
053        // -------------------------------------------------------------
054        
055        /**
056         * Sub-interface for 2D DFT implementations operating on {@code float} data.
057         */
058        public interface Float extends Dft2d {
059                
060                /**
061                 * Returns a suitable 1D DFT of the specified size ({@code float}).
062                 * @param size the size of the DFT
063                 * @return a {@link Dft1d.Float} instance
064                 */
065                public Dft1d.Float get1dDft(int size);
066                
067                /**
068                 * Transforms the given 2D arrays 'in-place'. Separate arrays of identical size
069                 * must be supplied for the real and imaginary parts of the signal (forward)
070                 * or spectrum (inverse), neither of which may be null.
071                 * 
072                 * @param inRe real part of the input signal or spectrum (modified)
073                 * @param inIm imaginary part of the input signal or spectrum (modified)
074                 * @param forward forward transformation if {@code true}, inverse transformation if {@code false}
075                 */
076                public default void transform(float[][] inRe, float[][] inIm, boolean forward) {
077                        checkSize(inRe);
078                        checkSize(inIm);
079                        final int width = this.getWidth();
080                        final int height = this.getHeight();
081
082                        // transform each row (in place):
083                        final float[] rowRe = new float[width];
084                        final float[] rowIm = new float[width];
085                        Dft1d.Float dftRow = get1dDft(width);
086                        for (int v = 0; v < height; v++) {
087                                extractRow(inRe, v, rowRe);
088                                extractRow(inIm, v, rowIm);
089                                dftRow.transform(rowRe, rowIm, forward);
090                                insertRow(inRe, v, rowRe);
091                                insertRow(inIm, v, rowIm);
092                        }
093
094                        // transform each column (in place):
095                        final float[] colRe = new float[height];
096                        final float[] colIm = new float[height];
097                        Dft1d.Float dftCol = get1dDft(height);
098                        for (int u = 0; u < width; u++) {
099                                extractCol(inRe, u, colRe);
100                                extractCol(inIm, u, colIm);
101                                dftCol.transform(colRe, colIm, forward);
102                                insertCol(inRe, u, colRe);
103                                insertCol(inIm, u, colIm);
104                        }
105                }
106                
107                public default void extractRow(float[][] g, int v, float[] row) {
108                        for (int u = 0; u < row.length; u++) {
109                                row[u] = g[u][v];
110                        }
111                }
112                
113                public default void insertRow(float[][] g, int v, float[] row) {
114                        for (int u = 0; u < row.length; u++) {
115                                g[u][v] = row[u];
116                        }
117                }
118                        
119                public default void extractCol(float[][] g, int u, float[] col) {
120                        for (int v = 0; v < col.length; v++) {
121                                col[v] = g[u][v];
122                        }
123                }
124                
125                public default void insertCol(float[][] g, final int u, float[] col) {
126                        for (int v = 0; v < col.length; v++) {
127                                g[u][v] = col[v];
128                        }
129                }
130                
131                /**
132                 * Performs an "in-place" forward DFT or FFT on the supplied 2D data.
133                 * The input signal is replaced by the associated DFT spectrum.
134                 * 
135                 * @param gRe real part of the signal (modified)
136                 * @param gIm imaginary part of the signal (modified)
137                 * @see #transform(float[][], float[][], boolean)
138                 */
139                public default void forward(float[][] gRe, float[][] gIm) {
140                        transform(gRe, gIm, true);
141                }
142                
143                /**
144                 * Performs an "in-place" inverse DFT or FFT on the supplied 2D spectrum.
145                 * The input spectrum is replaced by the associated signal.
146                 * 
147                 * @param GRe real part of the spectrum (modified)
148                 * @param GIm imaginary part of the spectrum (modified)
149                 * @see #transform(float[][], float[][], boolean)
150                 */
151                public default void inverse(float[][] GRe, float[][] GIm) {
152                        transform(GRe, GIm, false);
153                }
154                
155                public default void checkSize(float[][] A) {
156                        if (A.length != this.getWidth()) 
157                                throw new IllegalArgumentException(
158                                                String.format("wrong 2D array width %d (expected %d)", A.length, this.getWidth()));
159                        if (A[0].length != this.getHeight()) 
160                                throw new IllegalArgumentException(
161                                                String.format("wrong 2D array height %d (expected %d)", A[0].length, this.getHeight()));
162                }
163                
164                /**
165                 * Calculates and returns the magnitude of the supplied complex-valued 2D data.
166                 * @param re the real part of the data
167                 * @param im the imaginary part of the data
168                 * @return a 2D array of magnitude values
169                 */
170                public default float[][] getMagnitude(float[][] re, float[][] im) {
171                        checkSize(re);
172                        checkSize(im);
173                        final int width = re.length;
174                        final int height = re[0].length;
175                        float[][] mag = new float[width][height];
176                        for (int u = 0; u < width; u++) {
177                                for (int v = 0; v < height; v++) {
178                                        float a = re[u][v];
179                                        float b = im[u][v];
180                                        mag[u][v] = (float) Math.hypot(a, b);
181                                }
182                        }
183                        return mag;
184                }
185        }
186        
187        // -------------------------------------------------------------
188        
189        /**
190         * Sub-interface for 2D DFT implementations operating on {@code double} data.
191         */
192        public interface Double extends Dft2d {
193                
194                /**
195                 * Returns a suitable 1D DFT of the specified size ({@code double}).
196                 * @param size the size of the DFT
197                 * @return a {@link Dft1d.Double} instance
198                 */
199                public Dft1d.Double get1dDft(int size);
200                
201                /**
202                 * Transforms the given 2D arrays 'in-place'. Separate arrays of identical size
203                 * must be supplied for the real and imaginary parts of the signal (forward)
204                 * or spectrum (inverse), neither of which may be null.
205                 * 
206                 * @param gRe real part of the input signal or spectrum (modified)
207                 * @param gIm imaginary part of the input signal or spectrum (modified)
208                 * @param forward forward transformation if {@code true}, inverse transformation if {@code false}
209                 */
210                public default void transform(double[][] gRe, double[][] gIm, boolean forward) {
211                        checkSize(gRe);
212                        checkSize(gIm);
213                        final int width = this.getWidth();
214                        final int height = this.getHeight();
215
216                        // transform each row (in place):
217                        final double[] rowRe = new double[width];
218                        final double[] rowIm = new double[width];
219                        Dft1d.Double dftRow = get1dDft(width);
220                        for (int v = 0; v < height; v++) {
221                                extractRow(gRe, v, rowRe);
222                                extractRow(gIm, v, rowIm);
223                                dftRow.transform(rowRe, rowIm, forward);
224                                insertRow(gRe, v, rowRe);
225                                insertRow(gIm, v, rowIm);
226                        }
227
228                        // transform each column (in place):
229                        final double[] colRe = new double[height];
230                        final double[] colIm = new double[height];
231                        Dft1d.Double dftCol = get1dDft(height);
232                        for (int u = 0; u < width; u++) {
233                                extractCol(gRe, u, colRe);
234                                extractCol(gIm, u, colIm);
235                                dftCol.transform(colRe, colIm, forward);
236                                insertCol(gRe, u, colRe);
237                                insertCol(gIm, u, colIm);
238                        }
239                }
240                
241                public default void extractRow(double[][] g, int v, double[] row) {
242                        if (g == null) {                        // TODO: check if needed
243                                Arrays.fill(row, 0);
244                        }
245                        else {
246                                for (int u = 0; u < row.length; u++) {
247                                        row[u] = g[u][v];
248                                }
249                        }
250                }
251                
252                public default void insertRow(double[][] g, int v, double[] row) {
253                        for (int u = 0; u < row.length; u++) {
254                                g[u][v] = row[u];
255                        }
256                }
257                
258                public default void extractCol(double[][] g, int u, double[] col) {
259                        if (g == null) {                        // TODO: check if needed
260                                Arrays.fill(col, 0);
261                        }
262                        else {
263                                for (int v = 0; v < col.length; v++) {
264                                        col[v] = g[u][v];
265                                }
266                        }
267                }
268                
269                public default void insertCol(double[][] g, final int u, double[] col) {
270                        for (int v = 0; v < col.length; v++) {
271                                g[u][v] = col[v];
272                        }
273                }
274                
275                /**
276                 * Performs an "in-place" forward DFT or FFT on the supplied 2D data.
277                 * The input signal is replaced by the associated DFT spectrum.
278                 * 
279                 * @param gRe real part of the signal (modified)
280                 * @param gIm imaginary part of the signal (modified)
281                 * @see #transform(double[][], double[][], boolean)
282                 */
283                public default void forward(double[][] gRe, double[][] gIm) {
284                        transform(gRe, gIm, true);
285                }
286                
287                /**
288                 * Performs an "in-place" inverse DFT or FFT on the supplied 2D spectrum.
289                 * The input spectrum is replaced by the associated signal.
290                 * 
291                 * @param GRe real part of the spectrum (modified)
292                 * @param GIm imaginary part of the spectrum (modified)
293                 * @see #transform(double[][], double[][], boolean)
294                 */
295                public default void inverse(double[][] GRe, double[][] GIm) {
296                        transform(GRe, GIm, false);
297                }
298                
299                /**
300                 * Calculates and returns the magnitude of the supplied complex-valued 2D data.
301                 * 
302                 * @param re the real part of the data
303                 * @param im the imaginary part of the data
304                 * @return a 2D array of magnitude values
305                 */
306                public default double[][] getMagnitude(double[][] re, double[][] im) {
307                        checkSize(re);
308                        checkSize(im);
309                        final int width = re.length;
310                        final int height = re[0].length;
311                        double[][] mag = new double[width][height];
312                        for (int u = 0; u < width; u++) {
313                                for (int v = 0; v < height; v++) {
314                                        double a = re[u][v];
315                                        double b = im[u][v];
316                                        mag[u][v] = Math.hypot(a, b);
317                                }
318                        }
319                        return mag;
320                }
321                
322                public default void checkSize(double[][] A) {
323                        if (A.length != this.getWidth()) 
324                                throw new IllegalArgumentException(
325                                                String.format("wrong 2D array width %d (expected %d)", A.length, this.getWidth()));
326                        if (A[0].length != this.getHeight()) 
327                                throw new IllegalArgumentException(
328                                                String.format("wrong 2D array height %d (expected %d)", A[0].length, this.getHeight()));
329                }
330        }
331        
332}