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 static java.lang.Math.PI; 033import static java.lang.Math.cos; 034import static java.lang.Math.round; 035import static java.lang.Math.sin; 036import gnu.trove.map.hash.TIntFloatHashMap; 037import gnu.trove.map.hash.TIntObjectHashMap; 038import gnu.trove.procedure.TIntFloatProcedure; 039import gnu.trove.procedure.TIntObjectProcedure; 040 041import java.util.List; 042 043import org.apache.log4j.Logger; 044import org.openimaj.image.FImage; 045import org.openimaj.image.analyser.ImageAnalyser; 046import org.openimaj.math.geometry.shape.Circle; 047import org.openimaj.util.queue.BoundedPriorityQueue; 048 049/** 050 * An implementation of the Hough transform for circles. 051 * 052 * @author Sina Samangooei (ss@ecs.soton.ac.uk) 053 */ 054public class HoughCircles implements ImageAnalyser<FImage> { 055 Logger logger = Logger.getLogger(HoughCircles.class); 056 057 /** 058 * A circle with an associated weight. 059 * 060 * @author Sina Samangooei (ss@ecs.soton.ac.uk) 061 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk) 062 */ 063 public static class WeightedCircle extends Circle implements Comparable<WeightedCircle> { 064 /** 065 * The weight 066 */ 067 public float weight; 068 069 /** 070 * Construct with the given geometry and weight. 071 * 072 * @param x 073 * the x-ordinate of the center 074 * @param y 075 * the y-ordinate of the center 076 * @param radius 077 * the radius of the circle 078 * @param weight 079 * the associated weight 080 */ 081 public WeightedCircle(float x, float y, float radius, float weight) { 082 super(x, y, radius); 083 this.weight = weight; 084 } 085 086 @Override 087 public int compareTo(WeightedCircle o) { 088 return Float.compare(o.weight, this.weight); 089 } 090 } 091 092 protected int minRad; 093 protected int maxRad; 094 protected TIntObjectHashMap<TIntObjectHashMap<TIntFloatHashMap>> radmap; 095 private float[][] cosanglemap; 096 private float[][] sinanglemap; 097 private int nRadius; 098 private int nDegree; 099 private int radIncr; 100 101 /** 102 * Construct with the given parameters. 103 * 104 * @param minRad 105 * minimum search radius 106 * @param maxRad 107 * maximum search radius 108 * @param radIncrement 109 * amount to increment search radius by between min and max. 110 * @param nDegree 111 * number of degree increments 112 */ 113 public HoughCircles(int minRad, int maxRad, int radIncrement, int nDegree) { 114 super(); 115 this.minRad = minRad; 116 if (this.minRad <= 0) 117 this.minRad = 1; 118 this.maxRad = maxRad; 119 this.radmap = new TIntObjectHashMap<TIntObjectHashMap<TIntFloatHashMap>>(); 120 this.radIncr = radIncrement; 121 this.nRadius = (maxRad - minRad) / this.radIncr; 122 this.nDegree = nDegree; 123 this.cosanglemap = new float[nRadius][nDegree]; 124 this.sinanglemap = new float[nRadius][nDegree]; 125 for (int radIndex = 0; radIndex < this.nRadius; radIndex++) { 126 for (int angIndex = 0; angIndex < nDegree; angIndex++) { 127 final double ang = angIndex * (2 * PI / nDegree); 128 final double rad = minRad + (radIndex * this.radIncr); 129 this.cosanglemap[radIndex][angIndex] = (float) (rad * cos(ang)); 130 this.sinanglemap[radIndex][angIndex] = (float) (rad * sin(ang)); 131 } 132 } 133 } 134 135 @Override 136 public void analyseImage(FImage image) { 137 final int height = image.getHeight(); 138 final int width = image.getWidth(); 139 this.radmap = new TIntObjectHashMap<TIntObjectHashMap<TIntFloatHashMap>>(); 140 for (int y = 0; y < height; y++) { 141 for (int x = 0; x < width; x++) { 142 if (image.pixels[y][x] == 1) 143 { 144 for (int rad = 0; rad < nRadius; rad++) { 145 final int actualrad = (rad * this.radIncr) + this.minRad; 146 final float radiusWeight = 1f / this.nDegree; 147 // if(actualrad == 0){ 148 // throw new 149 // RuntimeException("The weight should never be 0"); 150 // } 151 for (int ang = 0; ang < nDegree; ang++) { 152 final int x0 = round(x + this.cosanglemap[rad][ang]); 153 final int y0 = round(y + this.sinanglemap[rad][ang]); 154 155 TIntObjectHashMap<TIntFloatHashMap> xMap = this.radmap.get(actualrad); 156 if (xMap == null) { 157 this.radmap.put(actualrad, xMap = new TIntObjectHashMap<TIntFloatHashMap>()); 158 } 159 TIntFloatHashMap yMap = xMap.get(x0); 160 if (yMap == null) { 161 xMap.put(x0, yMap = new TIntFloatHashMap()); 162 } 163 yMap.adjustOrPutValue(y0, radiusWeight, radiusWeight); 164 // if(x0 == 37 && y0 == 22 && actualrad == 1){ 165 // logger.debug("This should not be !"); 166 // logger.debug(String.format("Pixel = %d,%d", 167 // x,y)); 168 // logger.debug(String.format("x=%d,y=%d,r=%d,v=%2.5f",x0 169 // ,y0 ,actualrad , newValue )); 170 // } 171 // if(x0 > 22 && x0 < 27 && y0 > 22 && y0 < 27 && 172 // actualrad > 10 && actualrad < 14){ 173 // logger.debug("This should be correct!"); 174 // logger.debug(String.format("x=%d,y=%d,r=%d,v=%2.5f",x0 175 // ,y0 ,actualrad , newValue )); 176 // } 177 // if(Float.isInfinite(newValue)){ 178 // throw new 179 // RuntimeException("The value held should never be infinity"); 180 // } 181 // logger.debug(String.format("x=%d,y=%d,r=%d,v=%2.5f\n",x0 182 // ,y0 ,actualrad , newValue )); 183 // maxWeight = Math.max(newValue, maxWeight); 184 } 185 } 186 } 187 } 188 } 189 logger.debug("Done analysing the image!"); 190 } 191 192 /** 193 * Get the n-best detected circles. 194 * 195 * @param n 196 * the number of circles to return 197 * @return the n best detected circles. 198 */ 199 public List<WeightedCircle> getBest(int n) { 200 // final List<WeightedCircle> toSort = new ArrayList<WeightedCircle>(); 201 final BoundedPriorityQueue<WeightedCircle> bpq = new BoundedPriorityQueue<WeightedCircle>(n); 202 this.radmap.forEachEntry(new TIntObjectProcedure<TIntObjectHashMap<TIntFloatHashMap>>() { 203 204 @Override 205 public boolean execute(final int radius, TIntObjectHashMap<TIntFloatHashMap> b) { 206 b.forEachEntry(new TIntObjectProcedure<TIntFloatHashMap>() { 207 208 @Override 209 public boolean execute(final int x, TIntFloatHashMap b) { 210 b.forEachEntry(new TIntFloatProcedure() { 211 212 @Override 213 public boolean execute(int y, float weightedCount) { 214 bpq.offer(new WeightedCircle(x, y, radius, weightedCount)); 215 return true; 216 } 217 }); 218 return true; 219 } 220 }); 221 return true; 222 } 223 }); 224 225 return bpq.toOrderedList(); 226 } 227}