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}