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.feature.local.keypoints;
031
032import java.io.DataInput;
033import java.io.DataOutput;
034import java.io.IOException;
035import java.io.PrintWriter;
036import java.io.Serializable;
037import java.util.ArrayList;
038import java.util.Arrays;
039import java.util.List;
040import java.util.Scanner;
041import java.util.StringTokenizer;
042
043import org.openimaj.feature.ByteFV;
044import org.openimaj.feature.local.LocalFeature;
045import org.openimaj.io.VariableLength;
046import org.openimaj.math.geometry.point.Point2d;
047import org.openimaj.math.geometry.point.ScaleSpacePoint;
048
049import Jama.Matrix;
050import cern.jet.random.Normal;
051
052/**
053 * A local interest point with a location, scale, orientation and associated
054 * feature. The feature is stored as an array of bytes.
055 *
056 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
057 */
058public class Keypoint
059implements
060Serializable,
061ScaleSpacePoint,
062LocalFeature<KeypointLocation, ByteFV>,
063VariableLength,
064Cloneable
065{
066        static final long serialVersionUID = 1234554345;
067
068        /**
069         * Default length of standard SIFT features.
070         */
071        private final static int DEFAULT_LENGTH = 128;
072
073        /**
074         * keypoint feature descriptor (i.e. SIFT)
075         */
076        public byte[] ivec;
077
078        /**
079         * dominant orientation of keypoint
080         */
081        public float ori;
082
083        /**
084         * scale of keypoint
085         */
086        public float scale;
087
088        /**
089         * x-position of keypoint
090         */
091        public float x;
092
093        /**
094         * y-position of keypoint
095         */
096        public float y;
097
098        /**
099         * Construct with the default feature vector length for SIFT (128).
100         */
101        public Keypoint() {
102                this.ivec = new byte[DEFAULT_LENGTH];
103        }
104
105        /**
106         * Construct with the given feature vector length.
107         *
108         * @param length
109         *            the length of the feature vector
110         */
111        public Keypoint(int length) {
112                if (length < 0)
113                        length = DEFAULT_LENGTH;
114                this.ivec = new byte[length];
115        }
116
117        /**
118         * Construct with the given parameters.
119         *
120         * @param x
121         *            the x-ordinate of the keypoint
122         * @param y
123         *            the y-ordinate of the keypoint
124         * @param ori
125         *            the orientation of the keypoint
126         * @param scale
127         *            the scale of the keypoint
128         * @param ivec
129         *            the feature vector of the keypoint
130         */
131        public Keypoint(float x, float y, float ori, float scale, byte[] ivec) {
132                this.x = x;
133                this.y = y;
134                this.ori = ori;
135                this.scale = scale;
136                this.ivec = ivec;
137        }
138
139        /**
140         * Construct by copying from another {@link Keypoint}
141         *
142         * @param k
143         *            the {@link Keypoint} to copy from
144         */
145        public Keypoint(Keypoint k) {
146                this(k.x, k.y, k.ori, k.scale, Arrays.copyOf(k.ivec, k.ivec.length));
147        }
148
149        @Override
150        public Float getOrdinate(int dimension) {
151                if (dimension == 0)
152                        return x;
153                if (dimension == 1)
154                        return y;
155                if (dimension == 2)
156                        return scale;
157                return null;
158        }
159
160        @Override
161        public int getDimensions() {
162                return 3;
163        }
164
165        @Override
166        public float getX() {
167                return x;
168        }
169
170        @Override
171        public float getY() {
172                return y;
173        }
174
175        @Override
176        public void setX(float x) {
177                this.x = x;
178        }
179
180        @Override
181        public void setY(float y) {
182                this.y = y;
183        }
184
185        @Override
186        public float getScale() {
187                return scale;
188        }
189
190        @Override
191        public void setScale(float scale) {
192                this.scale = scale;
193        }
194
195        @Override
196        public String toString() {
197                return ("Keypoint(" + this.x + ", " + this.y + ", " + this.scale + ", " + this.ori + ")");
198        }
199
200        /**
201         * Test whether the location of this {@link Keypoint} and another
202         * {@link Keypoint} is the same.
203         *
204         * @param obj
205         *            the other keypoint
206         * @return true if the locations match; false otherwise.
207         */
208        public boolean locationEquals(Object obj) {
209                if (obj instanceof Keypoint) {
210                        final Keypoint kobj = (Keypoint) obj;
211
212                        if (kobj.x == x && kobj.y == y && kobj.scale == scale)
213                                return true;
214                }
215
216                return super.equals(obj);
217        }
218
219        @Override
220        public boolean equals(Object obj) {
221                if (obj instanceof Keypoint) {
222                        final Keypoint kobj = (Keypoint) obj;
223
224                        if (kobj.x == x && kobj.y == y && kobj.scale == scale && Arrays.equals(ivec, kobj.ivec))
225                                return true;
226                }
227
228                return super.equals(obj);
229        }
230
231        @Override
232        public int hashCode() {
233                int hash = 1;
234                hash = hash * 31 + Float.floatToIntBits(y);
235                hash = hash * 31 + Float.floatToIntBits(x);
236                hash = hash * 31 + Float.floatToIntBits(scale);
237                return hash;
238        }
239
240        @Override
241        public Keypoint clone() {
242                final Keypoint clone = new Keypoint();
243
244                clone.x = x;
245                clone.ori = ori;
246                clone.y = y;
247                clone.scale = scale;
248
249                clone.ivec = new byte[ivec.length];
250                System.arraycopy(ivec, 0, clone.ivec, 0, ivec.length);
251
252                return clone;
253        }
254
255        @Override
256        public void copyFrom(Point2d p) {
257                setX(p.getX());
258                setY(p.getY());
259        }
260
261        @Override
262        public void writeBinary(DataOutput out) throws IOException {
263                getLocation().writeBinary(out);
264                out.write(this.ivec);
265        }
266
267        @Override
268        public void writeASCII(PrintWriter out) throws IOException {
269                /* Output data for the keypoint. */
270                getLocation().writeASCII(out);
271                for (int i = 0; i < ivec.length; i++) {
272                        if (i > 0 && i % 20 == 0)
273                                out.println();
274                        out.print(" " + (ivec[i] + 128));
275                }
276                out.println();
277        }
278
279        @Override
280        public void readBinary(DataInput in) throws IOException {
281                final KeypointLocation l = getLocation();
282                l.readBinary(in);
283                setLocation(l);
284
285                in.readFully(ivec);
286        }
287
288        @Override
289        public void readASCII(Scanner in) throws IOException {
290                final KeypointLocation l = getLocation();
291                l.readASCII(in);
292                setLocation(l);
293
294                int i = 0;
295                while (i < ivec.length) {
296                        final String line = in.nextLine();
297                        final StringTokenizer st = new StringTokenizer(line);
298
299                        while (st.hasMoreTokens()) {
300                                ivec[i] = (byte) (Integer.parseInt(st.nextToken()) - 128);
301                                i++;
302                        }
303                }
304        }
305
306        @Override
307        public byte[] binaryHeader() {
308                return "".getBytes();
309        }
310
311        @Override
312        public String asciiHeader() {
313                return "";
314        }
315
316        @Override
317        public ByteFV getFeatureVector() {
318                return new ByteFV(ivec);
319        }
320
321        @Override
322        public KeypointLocation getLocation() {
323                return new KeypointLocation(x, y, ori, scale);
324        }
325
326        /**
327         * Set the location of this {@link Keypoint}
328         *
329         * @param location
330         *            the location
331         */
332        public void setLocation(KeypointLocation location) {
333                x = location.x;
334                y = location.y;
335                scale = location.scale;
336                ori = location.orientation;
337        }
338
339        /**
340         * Create a list of {@link Keypoint}s from the input list, but with the
341         * positions offset by the given amount.
342         *
343         * @param keypoints
344         *            the input list
345         * @param x
346         *            the x offset
347         * @param y
348         *            the y offset
349         * @return the new keypoints
350         */
351        public static List<Keypoint> getRelativeKeypoints(List<Keypoint> keypoints, float x, float y) {
352                final List<Keypoint> shifted = new ArrayList<Keypoint>();
353                for (final Keypoint old : keypoints) {
354                        final Keypoint n = new Keypoint();
355                        n.x = old.x - x;
356                        n.y = old.y - y;
357                        n.ivec = old.ivec;
358                        n.scale = old.scale;
359                        n.ori = old.ori;
360                        shifted.add(n);
361                }
362                return shifted;
363        }
364
365        /**
366         * Add Gaussian noise the feature vectors of some features. The original
367         * features are untouched; the returned list contains a copy.
368         *
369         * @param siftFeatures
370         *            the input features
371         * @param mean
372         *            the mean of the noise
373         * @param sigma
374         *            the standard deviation of the noise
375         * @return the noisy keypoints
376         */
377        public static List<Keypoint> addGaussianNoise(List<Keypoint> siftFeatures, double mean, double sigma) {
378                final List<Keypoint> toRet = new ArrayList<Keypoint>();
379                for (final Keypoint keypoint : siftFeatures) {
380                        final Keypoint kpClone = keypoint.clone();
381                        for (int i = 0; i < keypoint.ivec.length; i++) {
382                                final double deviation = Normal.staticNextDouble(mean, sigma);
383                                int value = 0xff & keypoint.ivec[i];
384                                value += deviation;
385                                if (value < 0)
386                                        value = 0;
387                                else if (value > 255)
388                                        value = 255;
389
390                                kpClone.ivec[i] = (byte) value;
391                        }
392                        toRet.add(kpClone);
393                }
394                return toRet;
395        }
396
397        /**
398         * Scale a list of keypoints by the given amount. This scales the location
399         * and scale of each keypoint. The original features are untouched; the
400         * returned list contains a copy.
401         *
402         * @param keypoints
403         *            the input features.
404         * @param toScale
405         *            the scale factor
406         * @return the scaled features.
407         */
408        public static List<Keypoint> getScaledKeypoints(List<Keypoint> keypoints, int toScale) {
409                final List<Keypoint> shifted = new ArrayList<Keypoint>();
410                for (final Keypoint old : keypoints) {
411                        final Keypoint n = new Keypoint();
412                        n.x = old.x * toScale;
413                        n.y = old.y * toScale;
414                        n.ivec = old.ivec;
415                        n.scale = old.scale * toScale;
416                        n.ori = old.ori;
417                        shifted.add(n);
418                }
419                return shifted;
420        }
421
422        @Override
423        public void translate(float x, float y) {
424                this.x += x;
425                this.y += y;
426        }
427
428        @Override
429        public Keypoint transform(Matrix transform) {
430                float xt = (float) transform.get(0, 0) * getX() + (float) transform.get(0, 1) * getY()
431                                + (float) transform.get(0, 2);
432                float yt = (float) transform.get(1, 0) * getX() + (float) transform.get(1, 1) * getY()
433                                + (float) transform.get(1, 2);
434                final float zt = (float) transform.get(2, 0) * getX() + (float) transform.get(2, 1) * getY()
435                                + (float) transform.get(2, 2);
436
437                xt /= zt;
438                yt /= zt;
439
440                return new Keypoint(xt, yt, this.ori, this.scale, this.ivec.clone());
441        }
442
443        @Override
444        public Point2d minus(Point2d a) {
445                final Keypoint kp = this.clone();
446                kp.x = this.x - (int) a.getX();
447                kp.y = this.y - (int) a.getY();
448                return null;
449        }
450
451        @Override
452        public void translate(Point2d v) {
453                this.translate(v.getX(), v.getY());
454        }
455
456        @Override
457        public Point2d copy() {
458                return clone();
459        }
460
461        @Override
462        public void setOrdinate(int dimension, Number value) {
463                if (dimension == 0)
464                        x = value.floatValue();
465                if (dimension == 1)
466                        y = value.floatValue();
467        }
468}