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.demos; 031 032import java.io.IOException; 033import java.net.URL; 034import java.util.ArrayList; 035import java.util.List; 036 037import org.openimaj.feature.local.list.LocalFeatureList; 038import org.openimaj.feature.local.matcher.FastBasicKeypointMatcher; 039import org.openimaj.feature.local.matcher.MatchingUtilities; 040import org.openimaj.image.DisplayUtilities; 041import org.openimaj.image.FImage; 042import org.openimaj.image.ImageUtilities; 043import org.openimaj.image.MBFImage; 044import org.openimaj.image.colour.RGBColour; 045import org.openimaj.image.feature.local.engine.DoGSIFTEngine; 046import org.openimaj.image.feature.local.keypoints.Keypoint; 047import org.openimaj.math.geometry.line.Line2d; 048import org.openimaj.math.geometry.point.Point2d; 049import org.openimaj.math.geometry.shape.Shape; 050import org.openimaj.math.geometry.shape.Triangle; 051import org.openimaj.math.geometry.triangulation.DelaunayTriangulator; 052import org.openimaj.util.pair.Pair; 053 054public class DTConsistency { 055 public static int computeDTScore(List<? extends Pair<? extends Point2d>> matches) { 056 final int size = matches.size(); 057 058 if (size <= 1) 059 return 0; 060 061 if (size == 2) 062 return 1; 063 064 if (size == 3) 065 return 3; 066 067 final List<Triangle> t1 = triangulateFirst(matches); 068 final List<Triangle> t2 = triangulateSecond(matches); 069 070 int commonEdges = 0; 071 for (int i = 0; i < size; i++) { 072 for (int j = i + 1; j < size; j++) { 073 final boolean e1 = hasEdge(matches.get(i).firstObject(), matches.get(j).firstObject(), t1); 074 final boolean e2 = hasEdge(matches.get(i).secondObject(), matches.get(j).secondObject(), t2); 075 076 if (e1 && e2) 077 commonEdges++; 078 } 079 } 080 081 return commonEdges; 082 } 083 084 public static class DTConsistencyInfo { 085 public List<Triangle> firstTrianglulation; 086 public List<Triangle> secondTrianglulation; 087 public List<Line2d> firstCommonEdges = new ArrayList<Line2d>(); 088 public List<Line2d> secondCommonEdges = new ArrayList<Line2d>(); 089 } 090 091 public static DTConsistencyInfo computeTriangulationInfo(List<? extends Pair<? extends Point2d>> matches) { 092 final int size = matches.size(); 093 094 if (size <= 3) 095 return null; 096 097 final DTConsistencyInfo info = new DTConsistencyInfo(); 098 099 info.firstTrianglulation = triangulateFirst(matches); 100 info.secondTrianglulation = triangulateSecond(matches); 101 102 for (int i = 0; i < size; i++) { 103 final Point2d firsti = matches.get(i).firstObject(); 104 final Point2d secondi = matches.get(i).secondObject(); 105 106 for (int j = i + 1; j < size; j++) { 107 final Point2d firstj = matches.get(j).firstObject(); 108 final Point2d secondj = matches.get(j).secondObject(); 109 110 final boolean e1 = hasEdge(firsti, firstj, info.firstTrianglulation); 111 final boolean e2 = hasEdge(secondi, secondj, info.secondTrianglulation); 112 113 if (e1 && e2) { 114 info.firstCommonEdges.add(new Line2d(firsti, firstj)); 115 info.secondCommonEdges.add(new Line2d(secondi, secondj)); 116 } 117 } 118 } 119 120 return info; 121 } 122 123 @SuppressWarnings("unchecked") 124 public static List<Triangle> triangulateFirst(List<? extends Pair<? extends Point2d>> matches) { 125 return DelaunayTriangulator.triangulate(Pair.getFirst((Iterable<Pair<Point2d>>) matches)); 126 } 127 128 @SuppressWarnings("unchecked") 129 public static List<Triangle> triangulateSecond(List<? extends Pair<? extends Point2d>> matches) { 130 return DelaunayTriangulator.triangulate(Pair.getSecond((Iterable<Pair<Point2d>>) matches)); 131 } 132 133 /** 134 * Search for an edge between the given points in any of the triangles 135 * 136 * @param pt1 137 * @param pt2 138 * @param tris 139 * @return 140 */ 141 private static boolean hasEdge(Point2d pt1, Point2d pt2, List<Triangle> tris) { 142 for (final Triangle t : tris) { 143 boolean foundP1 = false; 144 boolean foundP2 = false; 145 146 for (int i = 0; i < 3; i++) { 147 if (t.vertices[i] == pt1) 148 foundP1 = true; 149 150 if (t.vertices[i] == pt2) 151 foundP2 = true; 152 } 153 154 if (foundP1 && foundP2) 155 return true; 156 } 157 158 return false; 159 } 160 161 public static List<Pair<Keypoint>> filterDuplicatePoints(List<Pair<Keypoint>> matches) { 162 final List<Point2d> d1 = getDuplicatePoints(Pair.getFirst(matches)); 163 final List<Point2d> d2 = getDuplicatePoints(Pair.getSecond(matches)); 164 165 final List<Pair<Keypoint>> toRemove = new ArrayList<Pair<Keypoint>>(); 166 for (final Pair<Keypoint> p : matches) { 167 for (final Point2d d : d1) { 168 if (p.firstObject() == d) 169 toRemove.add(p); 170 } 171 } 172 173 for (final Pair<Keypoint> p : matches) { 174 for (final Point2d d : d2) { 175 if (p.secondObject() == d) 176 toRemove.add(p); 177 } 178 } 179 180 matches.removeAll(toRemove); 181 182 return matches; 183 } 184 185 public static List<Point2d> getDuplicatePoints(List<? extends Point2d> pts) { 186 final List<Point2d> dups = new ArrayList<Point2d>(); 187 188 for (int i = 0; i < pts.size(); i++) { 189 final Point2d pti = pts.get(i); 190 for (int j = 0; j < pts.size(); j++) { 191 final Point2d ptj = pts.get(j); 192 193 if (i != j) { 194 if (pti.getX() == ptj.getX() && pti.getY() == ptj.getY()) { 195 dups.add(pti); 196 dups.add(ptj); 197 } 198 } 199 } 200 } 201 202 return dups; 203 } 204 205 public static void main(String[] args) throws IOException { 206 final FImage image1 = ImageUtilities.readF(new URL( 207 "http://punch-records.co.uk/files/2013/01/Coca-cola-logo-eps-vector-nocturnar-com.jpg")); 208 final FImage image2 = ImageUtilities 209 .readF(new URL( 210 "http://i133.photobucket.com/albums/q78/KylePix/Car%20Shows%20and%20Races/Los%20Angeles%2011/111124-4937CocaColaMotorcycle.jpg")); 211 212 final DoGSIFTEngine engine = new DoGSIFTEngine(); 213 engine.getOptions().setDoubleInitialImage(true); 214 215 final LocalFeatureList<Keypoint> keys1 = engine.findFeatures(image1); 216 final LocalFeatureList<Keypoint> keys2 = engine.findFeatures(image2); 217 218 final FastBasicKeypointMatcher<Keypoint> matcher = new FastBasicKeypointMatcher<Keypoint>(6); 219 matcher.setModelFeatures(keys1); 220 matcher.findMatches(keys2); 221 222 final List<Pair<Keypoint>> matches = filterDuplicatePoints(matcher.getMatches()); 223 224 DisplayUtilities.display(MatchingUtilities.drawMatches(image1, image2, matches, 0F)); 225 226 final DTConsistencyInfo info = DTConsistency.computeTriangulationInfo(matches); 227 228 final MBFImage i1 = MBFImage.createRGB(image2); 229 final MBFImage i2 = MBFImage.createRGB(image1); 230 231 i1.drawLines(info.firstCommonEdges, 5, RGBColour.BLUE); 232 i2.drawLines(info.secondCommonEdges, 5, RGBColour.BLUE); 233 234 for (final Shape s : info.firstTrianglulation) 235 i1.drawShape(s, RGBColour.RED); 236 237 for (final Shape s : info.secondTrianglulation) 238 i2.drawShape(s, RGBColour.RED); 239 240 DisplayUtilities.display(i1); 241 DisplayUtilities.display(i2); 242 } 243}