001/**
002 * Copyright (c) 2011, The University of Southampton and the individual contributors.
003 * All rights reserved.
004 *
005 * Redistribution and use in source and binary forms, with or without modification,
006 * are permitted provided that the following conditions are met:
007 *
008 *   *  Redistributions of source code must retain the above copyright notice,
009 *      this list of conditions and the following disclaimer.
010 *
011 *   *  Redistributions in binary form must reproduce the above copyright notice,
012 *      this list of conditions and the following disclaimer in the documentation
013 *      and/or other materials provided with the distribution.
014 *
015 *   *  Neither the name of the University of Southampton nor the names of its
016 *      contributors may be used to endorse or promote products derived from this
017 *      software without specific prior written permission.
018 *
019 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
020 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
021 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
022 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
023 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
024 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
025 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
026 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
027 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
028 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
029 */
030package org.openimaj.image.analysis.algorithm;
031
032import org.openimaj.image.FImage;
033import org.openimaj.math.geometry.shape.Rectangle;
034
035/**
036 * Implementation of an Integral Image or Summed Area Table. This Implementation
037 * calculates both the sum, squared sum values, and (optionally) 45-degree
038 * tilted sum values.
039 * <p>
040 * See http://en.wikipedia.org/wiki/Summed_area_table and
041 * http://research.microsoft
042 * .com/en-us/um/people/viola/Pubs/Detect/violaJones_IJCV.pdf
043 * <p>
044 * Basically, this provides an efficient way to find the sum of all pixels in a
045 * rectangular area of an image.
046 * 
047 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
048 */
049public class SummedSqTiltAreaTable extends SummedSqAreaTable {
050        /**
051         * The tilted sum data
052         */
053        public FImage tiltSum;
054
055        /**
056         * Construct an empty SAT.
057         */
058        public SummedSqTiltAreaTable() {
059        }
060
061        /**
062         * Construct a SAT for normal sum, squared sum and tilted sum from the
063         * provided image.
064         * 
065         * @param image
066         *            the image.
067         */
068        public SummedSqTiltAreaTable(FImage image) {
069                this(image, true);
070        }
071
072        /**
073         * Construct a SAT for normal sum, squared sum and (optionally) tilted sum
074         * from the provided image.
075         * 
076         * @param image
077         *            the image.
078         * @param computeTilted
079         *            if true compute the tilted features.
080         */
081        public SummedSqTiltAreaTable(FImage image, boolean computeTilted) {
082                computeTable(image, computeTilted);
083        }
084
085        private void computeTable(FImage image, boolean computeTilted) {
086                if (computeTilted) {
087                        computeRotSqSumIntegralImages(image);
088                } else {
089                        computeSqSumIntegralImages(image);
090                }
091        }
092
093        protected void computeSqSumIntegralImages(FImage img) {
094                final int width = img.width;
095                final int height = img.height;
096
097                sum = new FImage(width + 1, height + 1);
098                sqSum = new FImage(width + 1, height + 1);
099
100                final float[][] sumData = sum.pixels;
101                final float[][] sqSumData = sqSum.pixels;
102
103                for (int y = 1; y <= height; y++) {
104                        float rowSum = 0;
105                        float rowSumSQ = 0;
106
107                        final float[] row = img.pixels[y - 1];
108                        for (int x = 1; x <= width; x++) {
109                                final float pix = row[x - 1];
110
111                                rowSum += pix;
112                                rowSumSQ += pix * pix;
113
114                                sumData[y][x] = sumData[y - 1][x] + rowSum;
115                                sqSumData[y][x] = sqSumData[y - 1][x] + rowSumSQ;
116                        }
117                }
118        }
119
120        protected final void computeRotSqSumIntegralImages(FImage image) {
121                final int width = image.width;
122                final int height = image.height;
123
124                sum = new FImage(width + 1, height + 1);
125                sqSum = new FImage(width + 1, height + 1);
126                tiltSum = new FImage(width + 2, height + 2);
127
128                final float[] buffer = new float[width];
129
130                // first two rows are special
131                // y == 1
132                if (height > 0) {
133                        final float[] row = image.pixels[0];
134
135                        float rowSum = 0;
136                        float sqRowSum = 0;
137
138                        for (int x = 1; x <= width; x++) {
139                                final float gray = (row[x - 1]);
140
141                                rowSum += gray;
142                                sqRowSum += gray * gray;
143
144                                sum.pixels[1][x] = rowSum;
145                                buffer[x - 1] = tiltSum.pixels[1][x] = gray;
146                                sqSum.pixels[1][x] = sqRowSum;
147                        }
148                }
149
150                // y == 2
151                if (height > 1) {
152                        final float[] row = image.pixels[1];
153
154                        float rowSum = 0;
155                        float sqRowSum = 0;
156
157                        for (int x = 1; x < width; x++) {
158                                final float gray = (row[x - 1]);
159
160                                rowSum += gray;
161                                sqRowSum += gray * gray;
162
163                                sum.pixels[2][x] = sum.pixels[1][x] + rowSum;
164                                sqSum.pixels[2][x] = sqSum.pixels[1][x] + sqRowSum;
165                                tiltSum.pixels[2][x] = tiltSum.pixels[1][x - 1] + buffer[x - 1] + tiltSum.pixels[1][x + 1] + gray;
166                                buffer[x - 1] = gray;
167                        }
168
169                        // last column is special
170                        if (width > 0) {
171                                final float gray = (row[width - 1]);
172
173                                rowSum += gray;
174                                sqRowSum += gray * gray;
175
176                                sum.pixels[2][width] = sum.pixels[1][width] + rowSum;
177                                sqSum.pixels[2][width] = sqSum.pixels[1][width] + sqRowSum;
178                                tiltSum.pixels[2][width] = tiltSum.pixels[1][width - 1] + buffer[width - 1] + gray;
179                                buffer[width - 1] = gray;
180                        }
181                }
182
183                for (int y = 3; y <= height; y++) {
184                        final float[] row = image.pixels[y - 1];
185
186                        float rowSum = 0;
187                        float sqRowSum = 0;
188
189                        if (width > 0) {
190                                final float gray = row[0];
191                                rowSum += gray;
192                                sqRowSum += gray * gray;
193
194                                sum.pixels[y][1] = sum.pixels[y - 1][1] + rowSum;
195                                sqSum.pixels[y][1] = sqSum.pixels[y - 1][1] + sqRowSum;
196                                tiltSum.pixels[y][1] = tiltSum.pixels[y - 1][2] + buffer[0] + gray;
197                                buffer[0] = gray;
198                        }
199
200                        for (int x = 2; x < width; x++) {
201                                final float gray = row[x - 1];
202                                rowSum += gray;
203                                sqRowSum += gray * gray;
204
205                                sum.pixels[y][x] = sum.pixels[y - 1][x] + rowSum;
206                                sqSum.pixels[y][x] = sqSum.pixels[y - 1][x] + sqRowSum;
207                                tiltSum.pixels[y][x] = tiltSum.pixels[y - 1][x - 1] + buffer[x - 1] + tiltSum.pixels[y - 1][x + 1]
208                                                - tiltSum.pixels[y - 2][x] + gray;
209                                buffer[x - 1] = gray;
210                        }
211
212                        if (width > 0) {
213                                final float gray = row[width - 1];
214                                rowSum += gray;
215                                sqRowSum += gray * gray;
216
217                                sum.pixels[y][width] = sum.pixels[y - 1][width] + rowSum;
218                                sqSum.pixels[y][width] = sqSum.pixels[y - 1][width] + sqRowSum;
219                                tiltSum.pixels[y][width] = tiltSum.pixels[y - 1][width - 1] + buffer[width - 1] + gray;
220                                buffer[width - 1] = gray;
221                        }
222                }
223        }
224
225        /**
226         * Calculate the sum of pixels in the image used for constructing this SAT
227         * within the 45 degree tilted rectangle.
228         * 
229         * @param x
230         * @param y
231         * @param width
232         * @param height
233         * 
234         * @return sum of pixels in given rectangle
235         */
236        public float calculateTiltedSumArea(int x, int y, int width, int height) {
237                final float p0 = tiltSum.pixels[y][x];
238                final float p1 = tiltSum.pixels[y + height][x - height];
239                final float p2 = tiltSum.pixels[y + width][x + width];
240                final float p3 = tiltSum.pixels[y + width + height][x + width - height];
241
242                return p0 - p1 - p2 + p3;
243        }
244
245        /**
246         * Calculate the sum pixels in the image used for constructing this SAT
247         * within the given 45-degree tilted rectangle.
248         * 
249         * @param r
250         *            rectangle
251         * @return sum of pixels in given rectangle
252         */
253        public float calculateTiltedSumArea(Rectangle r) {
254                return calculateTiltedSumArea(Math.round(r.x), Math.round(r.y), Math.round(r.width),
255                                Math.round(r.height));
256        }
257
258        /*
259         * (non-Javadoc)
260         * 
261         * @see
262         * org.openimaj.image.analyser.ImageAnalyser#analyseImage(org.openimaj.image
263         * .Image)
264         */
265        @Override
266        public void analyseImage(FImage image) {
267                computeTable(image, true);
268        }
269}