1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 package org.openimaj.demos;
31
32 import java.io.IOException;
33 import java.net.URL;
34 import java.util.ArrayList;
35 import java.util.List;
36
37 import org.openimaj.feature.local.list.LocalFeatureList;
38 import org.openimaj.feature.local.matcher.FastBasicKeypointMatcher;
39 import org.openimaj.feature.local.matcher.MatchingUtilities;
40 import org.openimaj.image.DisplayUtilities;
41 import org.openimaj.image.FImage;
42 import org.openimaj.image.ImageUtilities;
43 import org.openimaj.image.MBFImage;
44 import org.openimaj.image.colour.RGBColour;
45 import org.openimaj.image.feature.local.engine.DoGSIFTEngine;
46 import org.openimaj.image.feature.local.keypoints.Keypoint;
47 import org.openimaj.math.geometry.line.Line2d;
48 import org.openimaj.math.geometry.point.Point2d;
49 import org.openimaj.math.geometry.shape.Shape;
50 import org.openimaj.math.geometry.shape.Triangle;
51 import org.openimaj.math.geometry.triangulation.DelaunayTriangulator;
52 import org.openimaj.util.pair.Pair;
53
54 public class DTConsistency {
55 public static int computeDTScore(List<? extends Pair<? extends Point2d>> matches) {
56 final int size = matches.size();
57
58 if (size <= 1)
59 return 0;
60
61 if (size == 2)
62 return 1;
63
64 if (size == 3)
65 return 3;
66
67 final List<Triangle> t1 = triangulateFirst(matches);
68 final List<Triangle> t2 = triangulateSecond(matches);
69
70 int commonEdges = 0;
71 for (int i = 0; i < size; i++) {
72 for (int j = i + 1; j < size; j++) {
73 final boolean e1 = hasEdge(matches.get(i).firstObject(), matches.get(j).firstObject(), t1);
74 final boolean e2 = hasEdge(matches.get(i).secondObject(), matches.get(j).secondObject(), t2);
75
76 if (e1 && e2)
77 commonEdges++;
78 }
79 }
80
81 return commonEdges;
82 }
83
84 public static class DTConsistencyInfo {
85 public List<Triangle> firstTrianglulation;
86 public List<Triangle> secondTrianglulation;
87 public List<Line2d> firstCommonEdges = new ArrayList<Line2d>();
88 public List<Line2d> secondCommonEdges = new ArrayList<Line2d>();
89 }
90
91 public static DTConsistencyInfo computeTriangulationInfo(List<? extends Pair<? extends Point2d>> matches) {
92 final int size = matches.size();
93
94 if (size <= 3)
95 return null;
96
97 final DTConsistencyInfo info = new DTConsistencyInfo();
98
99 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
135
136
137
138
139
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 }