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}