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.objectdetection.filtering; 031 032import java.util.ArrayList; 033import java.util.List; 034 035import org.openimaj.math.geometry.shape.Rectangle; 036import org.openimaj.util.pair.ObjectIntPair; 037 038/** 039 * Filter to perform the grouping of detection rectangles in the way OpenCV 040 * does. Basically the groups are formed by grouping together all the rectangles 041 * that overlap by a certain amount. For each group, the mean rectangle is 042 * calculated. Groups that have too little support are removed, as are groups 043 * that are enclosed by other groups. 044 * 045 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk) 046 */ 047public final class OpenCVGrouping implements DetectionFilter<Rectangle, ObjectIntPair<Rectangle>> { 048 /** 049 * The default eps value for determining whether two rectangles overlap 050 * enough to be considered as being of the same group. 051 */ 052 public static final float DEFAULT_EPS = 0.2f; 053 054 /** 055 * The default value for the minimum number of rectangles required within a 056 * group. 057 */ 058 public static final int DEFAULT_MINIMUM_SUPPORT = 3; 059 060 float eps; 061 int minSupport; 062 063 /** 064 * Construct a new {@link OpenCVGrouping} with the given parameters. 065 * 066 * @param eps 067 * The eps value for determining whether two rectangles overlap 068 * enough to be considered as being of the same group. 069 * @param minSupport 070 * The minimum number of rectangles required within a group. 071 * Groups with less than this number of rectangles will be 072 * removed. 073 */ 074 public OpenCVGrouping(float eps, int minSupport) { 075 this.eps = eps; 076 this.minSupport = minSupport; 077 } 078 079 /** 080 * Construct a new {@link OpenCVGrouping} with the given minimum support 081 * number. The {@link #DEFAULT_EPS} value is used for the eps. 082 * 083 * @param minSupport 084 * The minimum number of rectangles required within a group. 085 * Groups with less than this number of rectangles will be 086 * removed. 087 */ 088 public OpenCVGrouping(int minSupport) { 089 this(DEFAULT_EPS, minSupport); 090 } 091 092 /** 093 * Construct a new {@link OpenCVGrouping} with the default values of 094 * {@link #DEFAULT_EPS} for the eps and {@link #DEFAULT_MINIMUM_SUPPORT} for 095 * the support. 096 */ 097 public OpenCVGrouping() { 098 this(DEFAULT_EPS, DEFAULT_MINIMUM_SUPPORT); 099 } 100 101 @Override 102 public List<ObjectIntPair<Rectangle>> apply(List<Rectangle> input) { 103 final int[] classes = new int[input.size()]; 104 final int nClasses = partition(input, classes); 105 106 // Compute the mean rectangle per class 107 final Rectangle[] meanRects = new Rectangle[nClasses]; // mean rect 108 // storage per 109 // class 110 final int[] rectCounts = new int[nClasses]; // number of rectangles per 111 // class 112 for (int i = 0; i < nClasses; i++) { 113 meanRects[i] = new Rectangle(0, 0, 0, 0); 114 } 115 116 for (int i = 0; i < classes.length; i++) { 117 final int cls = classes[i]; 118 119 meanRects[cls].x += input.get(i).x; 120 meanRects[cls].y += input.get(i).y; 121 meanRects[cls].width += input.get(i).width; 122 meanRects[cls].height += input.get(i).height; 123 rectCounts[cls]++; 124 } 125 126 for (int i = 0; i < nClasses; i++) { 127 final Rectangle r = meanRects[i]; 128 final float s = 1.0f / rectCounts[i]; 129 meanRects[i] = new Rectangle(Math.round(r.x * s), Math.round(r.y * s), Math.round(r.width * s), 130 Math.round(r.height * s)); 131 } 132 133 // now filter out any classes that have too few rectangles, or is a 134 // small rectangles inclosed by another class. 135 final List<ObjectIntPair<Rectangle>> rectList = new ArrayList<ObjectIntPair<Rectangle>>(); 136 for (int i = 0; i < nClasses; i++) { 137 final Rectangle r1 = meanRects[i]; 138 final int n1 = rectCounts[i]; 139 140 if (n1 <= minSupport) 141 continue; 142 143 // filter out small face rectangles inside large rectangles 144 int j; 145 for (j = 0; j < nClasses; j++) { 146 final int n2 = rectCounts[j]; 147 148 if (j == i || n2 <= minSupport) 149 continue; 150 final Rectangle r2 = meanRects[j]; 151 152 final int dx = Math.round(r2.width * eps); 153 final int dy = Math.round(r2.height * eps); 154 155 if (i != j && 156 r1.x >= r2.x - dx && 157 r1.y >= r2.y - dy && 158 r1.x + r1.width <= r2.x + r2.width + dx && 159 r1.y + r1.height <= r2.y + r2.height + dy && 160 (n2 > Math.max(3, n1) || n1 < 3)) 161 break; 162 } 163 164 if (j == nClasses) { 165 rectList.add(new ObjectIntPair<Rectangle>(r1, n1)); 166 } 167 } 168 169 return rectList; 170 } 171 172 private int partition(List<Rectangle> rects, int[] classes) { 173 int numClasses = 0; 174 175 for (int i = 0; i < rects.size(); i++) { 176 boolean found = false; 177 for (int j = 0; j < i; j++) { 178 if (equals(rects.get(j), rects.get(i))) { 179 found = true; 180 classes[i] = classes[j]; 181 } 182 } 183 if (!found) { 184 classes[i] = numClasses; 185 numClasses++; 186 } 187 } 188 189 return numClasses; 190 } 191 192 private boolean equals(Rectangle r1, Rectangle r2) { 193 final float delta = eps * (Math.min(r1.width, r2.width) + Math.min(r1.height, r2.height)) * 0.5f; 194 195 return (Math.abs(r1.x - r2.x) <= delta && 196 Math.abs(r1.y - r2.y) <= delta && 197 Math.abs(r1.x + r1.width - r2.x - r2.width) <= delta && Math.abs(r1.y + r1.height - r2.y - r2.height) <= delta); 198 } 199}