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 */
030
031package org.openimaj.image.analysis.algorithm;
032
033import java.util.ArrayList;
034import java.util.List;
035
036import org.openimaj.feature.DoubleFV;
037import org.openimaj.feature.FeatureVectorProvider;
038import org.openimaj.feature.MultidimensionalDoubleFV;
039import org.openimaj.image.FImage;
040import org.openimaj.image.analyser.ImageAnalyser;
041import org.openimaj.image.pixel.ConnectedComponent;
042import org.openimaj.image.processing.edges.CannyEdgeDetector2;
043import org.openimaj.math.geometry.point.Point2d;
044import org.openimaj.math.geometry.point.Point2dImpl;
045import org.openimaj.math.statistics.distribution.Histogram;
046
047/**
048 * Uses the Edge Direction Coherence Histograms to attempt to classify an image
049 * as city or landscape. This uses the coherent edge histogram technique
050 * described in "On Image Classification: City Images vs. Landscapes" by
051 * Vailaya, Jain and Zhang, Michigan State University.
052 * 
053 * @author David Dupplaw (dpd@ecs.soton.ac.uk), 7th July 2005
054 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
055 */
056@SuppressWarnings("deprecation")
057public class EdgeDirectionCoherenceVector
058                implements ImageAnalyser<FImage>, FeatureVectorProvider<DoubleFV>
059{
060        /**
061         * An edge direction histogram. Contains two histograms: one for coherent
062         * edges and one for incoherent edges.
063         * 
064         * @author David Dupplaw (dpd@ecs.soton.ac.uk)
065         * @created 10 Jun 2011
066         * 
067         */
068        public class EdgeDirectionCoherenceHistogram
069        {
070                /** The coherent part of the histogram */
071                public Histogram coherentHistogram = null;
072
073                /** The incoherent part of the histogram */
074                public Histogram incoherentHistogram = null;
075
076                /**
077                 * Get the histogram (coherent followed by incoherent) as a double
078                 * vector.
079                 * 
080                 * @return A {@link DoubleFV} feature vector
081                 */
082                public DoubleFV asDoubleFV()
083                {
084                        final double[] d = new double[coherentHistogram.values.length +
085                                        incoherentHistogram.values.length];
086                        int i = 0;
087                        for (final double dd : coherentHistogram.asDoubleVector())
088                                d[i++] = dd;
089                        for (final double dd : incoherentHistogram.asDoubleVector())
090                                d[i++] = dd;
091                        return new DoubleFV(d);
092                }
093
094                /**
095                 * Get the histogram as a multidimensional vector, where the coherent
096                 * and incoherent histograms occupy different dimensions. So the vector
097                 * will be 2xnBins.
098                 * 
099                 * @return A {@link MultidimensionalDoubleFV}
100                 */
101                public MultidimensionalDoubleFV asMultidimensionalDoubleFV()
102                {
103                        final double[][] d = new double[2][coherentHistogram.values.length];
104                        int i = 0;
105                        for (final double dd : coherentHistogram.asDoubleVector())
106                                d[0][i++] = dd;
107                        i = 0;
108                        for (final double dd : incoherentHistogram.asDoubleVector())
109                                d[1][i++] = dd;
110                        return new MultidimensionalDoubleFV(d);
111                }
112        }
113
114        /** The calculated direction histograms */
115        private EdgeDirectionCoherenceHistogram coDirHist = null;
116
117        /** Number of bins in each histogram */
118        private int numberOfDirBins = 72;
119
120        /** The direction threshold for considering an edge is coherent */
121        private float directionThreshold = 360 / numberOfDirBins;
122
123        /** The connect mode for tracing edges */
124        private ConnectedComponent.ConnectMode mode =
125                        ConnectedComponent.ConnectMode.CONNECT_8;
126
127        /**
128         * The factor of the image are size over which edges are considered
129         * coherent. In other words, an edge is coherent if the number of pixels in
130         * the edge is greater than image_width * image_height * coherenceFactor.
131         */
132        private double coherenceFactor = 0.00002;
133
134        /** The edge detector used */
135        private CannyEdgeDetector2 cannyEdgeDetector = null;
136
137        /**
138         * Default constructor
139         */
140        public EdgeDirectionCoherenceVector()
141        {
142                cannyEdgeDetector = new CannyEdgeDetector2();
143        }
144
145        /**
146         * @return numberOfDirBins
147         */
148        public int getNumberOfDirBins()
149        {
150                return numberOfDirBins;
151        }
152
153        /**
154         * Set the number of bins.
155         * 
156         * @param nb
157         *            the number of bins
158         */
159        public void setNumberOfBins(int nb)
160        {
161                this.numberOfDirBins = nb;
162                this.directionThreshold = 360 / numberOfDirBins;
163        }
164
165        /**
166         * @return coDirHist
167         */
168        public EdgeDirectionCoherenceHistogram getLastHistogram()
169        {
170                return coDirHist;
171        }
172
173        /*
174         * (non-Javadoc)
175         * 
176         * @see
177         * org.openimaj.image.analyser.ImageAnalyser#analyseImage(org.openimaj.image
178         * .Image)
179         */
180        @Override
181        public void analyseImage(FImage image)
182        {
183                final int w = image.getWidth();
184                final int h = image.getHeight();
185
186                // Calculate the edge image.
187                final FImage edgeImage = image.clone();
188                cannyEdgeDetector.processImage(edgeImage);
189
190                final float[] mags = cannyEdgeDetector.getMagnitude();
191                final float[] dirs = cannyEdgeDetector.getOrientation();
192
193                // Check we've got some stuff to work on
194                if (mags == null || dirs == null)
195                        System.out.println("Canny Edge Detector did not " +
196                                        "return magnitude or direction.");
197
198                // Histogram definition. We add a bin for non-edges
199                final int numberOfBins = numberOfDirBins + 1;
200
201                // -- THE HISTOGRAM --
202                final double[] dirHist = new double[numberOfBins];
203
204                // Count the number of non-edge pixels. Edges are white from this
205                // CannyEdgeDetector2, non-edges value 0.
206                int nonEdgeCount = 0;
207                for (int y = 0; y < edgeImage.getHeight(); y++)
208                        for (int x = 0; x < edgeImage.getWidth(); x++)
209                                if (edgeImage.getPixel(x, y) == 0)
210                                        nonEdgeCount++;
211                dirHist[0] = nonEdgeCount;
212
213                // Bin all the directions. We use bin 0 for non-edge pixels
214                // and bin i+1 for the direction i. We then back-project on to an
215                // image so that we can trace the edges later.
216                final FImage directionImage = new FImage(w, h);
217                for (int j = 0; j < w * h; j++)
218                {
219                        final int x = j % w;
220                        final int y = j / w;
221
222                        if (edgeImage.getPixel(x, y) > 0)
223                        {
224                                // dirs[j] is between -180 and 180
225                                // Bin the direction of the pixel
226                                final int dirBin = (int) ((dirs[j] + 180) * numberOfDirBins / 360f) % numberOfDirBins;
227                                dirHist[dirBin + 1]++;
228
229                                final float v = (dirs[j] + 180);
230                                directionImage.setPixel(x, y, v);
231                        }
232                        // Set the non-edge pixel to -1
233                        else
234                                directionImage.setPixel(x, y, -1f);
235                }
236
237                final int numberOfEdgePix = w * h - nonEdgeCount;
238
239                // -- NORMALISE HISTOGRAM --
240                for (int j = 0; j < numberOfDirBins; j++)
241                        dirHist[j + 1] /= numberOfEdgePix;
242                dirHist[0] /= w * h;
243
244                // Now to work out the coherency of the edge pixels.
245                // To do this we go to a random edge pixel, and attempt
246                // to trace from there to somewhere else. We check that
247                // the direction is within 5 degrees of the first pixel.
248                // We keep a vector of these pixels, and when the iteration
249                // finished (run out of edge pixels, or it goes outside our
250                // bin), then we determine whether it's coherent or not, based
251                // on the number of pixels within the connected set.
252                //
253                // To make all this easier, we back projected the direction
254                // histogram onto another image (bi). As we use a pixel we
255                // remove it from bi, so that we don't get caught in loops, etc.
256                // We can't check the BP-image intensities directly (although
257                // it seems at first pragmatic) because of the "binning-problem"
258                // where pixels may sit right on the edge of a histogram bin.
259
260                // -- THE COHERENCE HISTOGRAM --
261                // 0 is incoherent
262                // 1 is coherent
263                coDirHist = new EdgeDirectionCoherenceHistogram();
264                coDirHist.coherentHistogram = new Histogram(numberOfDirBins);
265                coDirHist.incoherentHistogram = new Histogram(numberOfDirBins);
266
267                // Coherent Edge Image (only coherent edges displayed)
268                final FImage outputImage = new FImage(w, h);
269
270                // First we find an edge pixel
271                for (int j = 0; j < w * h; j++)
272                {
273                        final int x = j % w;
274                        final int y = j / w;
275
276                        // Get the back projected edge pixel
277                        final float p = directionImage.getPixel(x, y);
278
279                        // in bi, non-edge pixels are set to 0x00000000 (transparent black)
280                        // which allows discretion between non-transparent black edge pixels
281                        if (p != -1)
282                        {
283                                // Get the edges connected to the current point.
284                                final List<Point2d> v = getConnectedEdges(x, y, w, h, p,
285                                                numberOfBins, directionImage, dirs, mode);
286
287                                // dirs[j] is between -180 and 180
288                                final int dirBin = (int) ((dirs[j] + 180)
289                                                * numberOfDirBins / 360f) % numberOfDirBins;
290
291                                // If the edge is coherent...
292                                boolean isCoherent = false;
293                                if (v.size() > (w * h * coherenceFactor))
294                                {
295                                        for (int k = 0; k < v.size(); k++)
296                                        {
297                                                final Point2d pp = v.get(k);
298                                                outputImage.setPixel(
299                                                                Math.round(pp.getX()),
300                                                                Math.round(pp.getY()),
301                                                                1f);
302                                        }
303
304                                        isCoherent = true;
305                                }
306
307                                if (isCoherent)
308                                        coDirHist.coherentHistogram.values[dirBin] += v.size();
309                                else
310                                        coDirHist.incoherentHistogram.values[dirBin] += v.size();
311                        }
312                }
313
314                image.internalAssign(outputImage);
315        }
316
317        /**
318         * Function that given a pixel at x, y with value p, in image bi, it will
319         * find all connected edges that fall within the same bin.
320         * 
321         * @param xx
322         *            The x coordinate of the seed edge pixel
323         * @param yy
324         *            The y coordinate of the seed edge pixel
325         * @param w
326         *            The width of the edge image (required to index directions
327         *            array)
328         * @param h
329         *            The height of the edge image
330         * @param p
331         *            The intensity of the given pixel
332         * @param numberOfBins
333         *            Number of bins in the edge histogram (to work out direction)
334         * @param edgeImage
335         *            The back-projected edge image
336         * @param dirs
337         *            The original edge directions map
338         * @param connectedness
339         *            4 or 8-connected
340         */
341        private List<Point2d> getConnectedEdges(int xx, int yy, int w, int h, float p,
342                        int numberOfBins, FImage edgeImage, float[] dirs,
343                        ConnectedComponent.ConnectMode connectedness)
344        {
345                final List<Point2d> v = new ArrayList<Point2d>();
346
347                // The original point is always in the final set
348                v.add(new Point2dImpl(xx, yy));
349
350                // Pixels are wiped out as they're traced. So we wipe out the
351                // first pixel where we start.
352                edgeImage.setPixel(xx, yy, -1f);
353
354                final float dir = dirs[yy * w + xx];
355                boolean connected = true;
356                int x = xx, y = yy;
357                while (connected)
358                {
359                        int nx = x, ny = y;
360
361                        switch (connectedness)
362                        {
363                        // Check 4-connected neighbourhood
364                        case CONNECT_4:
365                                nx = x + 1;
366                                ny = y;
367                                if (nx >= 0 && ny >= 0 && nx < w && ny < h &&
368                                                dirs[ny * w + nx] < dir + directionThreshold &&
369                                                dirs[ny * w + nx] > dir - directionThreshold &&
370                                                edgeImage.getPixel(nx, ny) != -1)
371                                        break;
372                                nx = x;
373                                ny = y + 1;
374                                if (nx >= 0 && ny >= 0 && nx < w && ny < h &&
375                                                dirs[ny * w + nx] < dir + directionThreshold &&
376                                                dirs[ny * w + nx] > dir - directionThreshold &&
377                                                edgeImage.getPixel(nx, ny) != -1)
378                                        break;
379                                nx = x - 1;
380                                ny = y;
381                                if (nx >= 0 && ny >= 0 && nx < w && ny < h &&
382                                                dirs[ny * w + nx] < dir + directionThreshold &&
383                                                dirs[ny * w + nx] > dir - directionThreshold &&
384                                                edgeImage.getPixel(nx, ny) != -1)
385                                        break;
386                                nx = x;
387                                ny = y - 1;
388                                if (nx >= 0 && ny >= 0 && nx < w && ny < h &&
389                                                dirs[ny * w + nx] < dir + directionThreshold &&
390                                                dirs[ny * w + nx] > dir - directionThreshold &&
391                                                edgeImage.getPixel(nx, ny) != -1)
392                                        break;
393                                nx = x;
394                                ny = y;
395                                break;
396
397                        // Check 8-connected neighbourhood
398                        case CONNECT_8:
399                                nx = x + 1;
400                                ny = y - 1;
401                                if (nx >= 0 && ny >= 0 && nx < w && ny < h &&
402                                                dirs[ny * w + nx] < dir + directionThreshold &&
403                                                dirs[ny * w + nx] > dir - directionThreshold &&
404                                                edgeImage.getPixel(nx, ny) != -1)
405                                        break;
406                                nx = x + 1;
407                                ny = y;
408                                if (nx >= 0 && ny >= 0 && nx < w && ny < h &&
409                                                dirs[ny * w + nx] < dir + directionThreshold &&
410                                                dirs[ny * w + nx] > dir - directionThreshold &&
411                                                edgeImage.getPixel(nx, ny) != -1)
412                                        break;
413                                nx = x + 1;
414                                ny = y + 1;
415                                if (nx >= 0 && ny >= 0 && nx < w && ny < h &&
416                                                dirs[ny * w + nx] < dir + directionThreshold &&
417                                                dirs[ny * w + nx] > dir - directionThreshold &&
418                                                edgeImage.getPixel(nx, ny) != -1)
419                                        break;
420                                nx = x;
421                                ny = y + 1;
422                                if (nx >= 0 && ny >= 0 && nx < w && ny < h &&
423                                                dirs[ny * w + nx] < dir + directionThreshold &&
424                                                dirs[ny * w + nx] > dir - directionThreshold &&
425                                                edgeImage.getPixel(nx, ny) != -1)
426                                        break;
427                                nx = x - 1;
428                                ny = y + 1;
429                                if (nx >= 0 && ny >= 0 && nx < w && ny < h &&
430                                                dirs[ny * w + nx] < dir + directionThreshold &&
431                                                dirs[ny * w + nx] > dir - directionThreshold &&
432                                                edgeImage.getPixel(nx, ny) != -1)
433                                        break;
434                                nx = x - 1;
435                                ny = y;
436                                if (nx >= 0 && ny >= 0 && nx < w && ny < h &&
437                                                dirs[ny * w + nx] < dir + directionThreshold &&
438                                                dirs[ny * w + nx] > dir - directionThreshold &&
439                                                edgeImage.getPixel(nx, ny) != -1)
440                                        break;
441                                nx = x - 1;
442                                ny = y - 1;
443                                if (nx >= 0 && ny >= 0 && nx < w && ny < h &&
444                                                dirs[ny * w + nx] < dir + directionThreshold &&
445                                                dirs[ny * w + nx] > dir - directionThreshold &&
446                                                edgeImage.getPixel(nx, ny) != -1)
447                                        break;
448                                nx = x;
449                                ny = y - 1;
450                                if (nx >= 0 && ny >= 0 && nx < w && ny < h &&
451                                                dirs[ny * w + nx] < dir + directionThreshold &&
452                                                dirs[ny * w + nx] > dir - directionThreshold &&
453                                                edgeImage.getPixel(nx, ny) != -1)
454                                        break;
455                                nx = x;
456                                ny = y;
457                                break;
458                        }
459
460                        if ((nx >= 0 && nx != x) || (ny >= 0 && ny != y))
461                        {
462                                v.add(new Point2dImpl(nx, ny));
463                                edgeImage.setPixel(nx, ny, -1f);
464                                x = nx;
465                                y = ny;
466                        }
467                        else
468                                connected = false;
469                }
470                return v;
471        }
472
473        /**
474         * Returns the edge direction coherence histogram that was calculated.
475         * 
476         * @return the edge direction coherence histogram.
477         */
478        public EdgeDirectionCoherenceHistogram getHistogram()
479        {
480                return coDirHist;
481        }
482
483        /**
484         * {@inheritDoc}
485         * 
486         * @see org.openimaj.feature.FeatureVectorProvider#getFeatureVector()
487         */
488        @Override
489        public DoubleFV getFeatureVector()
490        {
491                return coDirHist.asMultidimensionalDoubleFV();
492        }
493
494        /**
495         * Get the edge detector used.
496         * 
497         * @return the canny edge detector
498         */
499        public CannyEdgeDetector2 getCannyEdgeDetector()
500        {
501                return cannyEdgeDetector;
502        }
503
504        /**
505         * Get the edge coherence factor. This is the relative size of the edge
506         * compared to the image over which an edge will be considered coherent and
507         * is generally a very small number. The default is 0.00002.
508         * 
509         * @return the coherence factor
510         */
511        public double getCoherenceFactor()
512        {
513                return coherenceFactor;
514        }
515
516        /**
517         * Set the edge coherence factor. This is the relative size of the edge
518         * compared to the image over which an edge will be considered coherent and
519         * is generally a very small number. The default is 0.00002.
520         * 
521         * @param coherenceFactor
522         *            the coherence factor value
523         */
524        public void setCoherenceFactor(double coherenceFactor)
525        {
526                this.coherenceFactor = coherenceFactor;
527        }
528}