1 /**
2 * Copyright (c) 2011, The University of Southampton and the individual contributors.
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without modification,
6 * are permitted provided that the following conditions are met:
7 *
8 * * Redistributions of source code must retain the above copyright notice,
9 * this list of conditions and the following disclaimer.
10 *
11 * * Redistributions in binary form must reproduce the above copyright notice,
12 * this list of conditions and the following disclaimer in the documentation
13 * and/or other materials provided with the distribution.
14 *
15 * * Neither the name of the University of Southampton nor the names of its
16 * contributors may be used to endorse or promote products derived from this
17 * software without specific prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
21 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
23 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
24 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
25 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
26 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
28 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 */
30 package org.openimaj.image.segmentation;
31
32 import java.util.ArrayList;
33 import java.util.List;
34
35 import org.openimaj.feature.FloatFVComparator;
36 import org.openimaj.image.MBFImage;
37 import org.openimaj.image.colour.ColourSpace;
38 import org.openimaj.image.pixel.PixelSet;
39 import org.openimaj.knn.FloatNearestNeighbours;
40 import org.openimaj.knn.FloatNearestNeighboursExact;
41 import org.openimaj.ml.clustering.FloatCentroidsResult;
42 import org.openimaj.ml.clustering.assignment.HardAssigner;
43 import org.openimaj.ml.clustering.kmeans.FloatKMeans;
44 import org.openimaj.ml.clustering.kmeans.KMeansConfiguration;
45
46 /**
47 * Simple image segmentation from grouping colours with k-means.
48 *
49 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
50 *
51 */
52 public class KMColourSegmenter implements Segmenter<MBFImage> {
53 private static final int DEFAULT_MAX_ITERS = 100;
54 protected ColourSpace colourSpace;
55 protected float[] scaling;
56 protected FloatKMeans kmeans;
57
58 /**
59 * Construct using the given colour space and number of segments. Euclidean
60 * distance is used, and the elements of each colour band are unscaled. Up
61 * to 100 K-Means iterations will be performed.
62 *
63 * @param colourSpace
64 * the colour space
65 * @param K
66 * the number of segments
67 */
68 public KMColourSegmenter(ColourSpace colourSpace, int K) {
69 this(colourSpace, null, K, null, DEFAULT_MAX_ITERS);
70 }
71
72 /**
73 * Construct using the given colour space, number of segments, and distance
74 * measure. The elements of each colour band are unscaled. Up to 100 K-Means
75 * iterations will be performed.
76 *
77 * @param colourSpace
78 * the colour space
79 * @param K
80 * the number of segments
81 * @param distance
82 * the distance measure
83 */
84 public KMColourSegmenter(ColourSpace colourSpace, int K, FloatFVComparator distance) {
85 this(colourSpace, null, K, distance, DEFAULT_MAX_ITERS);
86 }
87
88 /**
89 * Construct using the given colour space, number of segments, and distance
90 * measure. The elements of each colour band are by the corresponding
91 * elements in the given scaling vector. Up to 100 K-Means iterations will
92 * be performed.
93 *
94 * @param colourSpace
95 * the colour space
96 * @param scaling
97 * the scaling vector
98 * @param K
99 * the number of segments
100 * @param distance
101 * the distance measure
102 */
103 public KMColourSegmenter(ColourSpace colourSpace, float[] scaling, int K, FloatFVComparator distance) {
104 this(colourSpace, scaling, K, distance, DEFAULT_MAX_ITERS);
105 }
106
107 /**
108 * Construct using the given colour space, number of segments, and distance
109 * measure. The elements of each colour band are by the corresponding
110 * elements in the given scaling vector, and the k-means algorithm will
111 * iterate at most <code>maxIters</code> times.
112 *
113 * @param colourSpace
114 * the colour space
115 * @param scaling
116 * the scaling vector
117 * @param K
118 * the number of segments
119 * @param distance
120 * the distance measure
121 * @param maxIters
122 * the maximum number of iterations to perform
123 */
124 public KMColourSegmenter(ColourSpace colourSpace, float[] scaling, int K, FloatFVComparator distance, int maxIters) {
125 if (scaling != null && scaling.length < colourSpace.getNumBands())
126 throw new IllegalArgumentException(
127 "Scaling vector must have the same length as the number of dimensions of the target colourspace (or more)");
128
129 this.colourSpace = colourSpace;
130 this.scaling = scaling;
131
132 final KMeansConfiguration<FloatNearestNeighbours, float[]> conf =
133 new KMeansConfiguration<FloatNearestNeighbours, float[]>(
134 K,
135 new FloatNearestNeighboursExact.Factory(distance),
136 maxIters);
137
138 this.kmeans = new FloatKMeans(conf);
139 }
140
141 protected float[][] imageToVector(MBFImage image) {
142 final int height = image.getHeight();
143 final int width = image.getWidth();
144 final int bands = image.numBands();
145
146 final float[][] f = new float[height * width][bands];
147 for (int b = 0; b < bands; b++) {
148 final float[][] band = image.getBand(b).pixels;
149 final float w = scaling == null ? 1 : scaling[b];
150
151 for (int y = 0; y < height; y++)
152 for (int x = 0; x < width; x++)
153 f[x + y * width][b] = band[y][x] * w;
154 }
155
156 return f;
157 }
158
159 @Override
160 public List<? extends PixelSet> segment(final MBFImage image) {
161 final MBFImage input = ColourSpace.convert(image, colourSpace);
162 final float[][] imageData = imageToVector(input);
163
164 final FloatCentroidsResult result = kmeans.cluster(imageData);
165
166 final List<PixelSet> out = new ArrayList<PixelSet>(kmeans.getConfiguration().getK());
167 for (int i = 0; i < kmeans.getConfiguration().getK(); i++)
168 out.add(new PixelSet());
169
170 final HardAssigner<float[], ?, ?> assigner = result.defaultHardAssigner();
171 final int height = image.getHeight();
172 final int width = image.getWidth();
173 for (int y = 0, i = 0; y < height; y++) {
174 for (int x = 0; x < width; x++, i++) {
175 final float[] pixel = imageData[i];
176 final int centroid = assigner.assign(pixel);
177
178 out.get(centroid).addPixel(x, y);
179 }
180 }
181
182 return out;
183 }
184 }