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.processing.morphology;
031
032import java.util.Arrays;
033import java.util.HashSet;
034import java.util.Set;
035
036import org.openimaj.image.pixel.Pixel;
037
038/**
039 * Morphological structuring element
040 * 
041 * The central element is the pixel 0,0. Other s.e. pixels are relative to this.
042 * 
043 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
044 * 
045 */
046public class StructuringElement {
047        /**
048         * Standard 3x3 box structuring element
049         */
050        public final static StructuringElement BOX;
051
052        /**
053         * Standard 3x3 cross structuring element
054         */
055        public final static StructuringElement CROSS;
056
057        /**
058         * Standard horizontal pit structuring element [x . x]
059         */
060        public final static StructuringElement HPIT;
061
062        // build the elements
063        static {
064                BOX = new StructuringElement();
065                BOX.positive.add(new Pixel(-1, -1));
066                BOX.positive.add(new Pixel(0, -1));
067                BOX.positive.add(new Pixel(1, -1));
068                BOX.positive.add(new Pixel(-1, 0));
069                BOX.positive.add(new Pixel(0, 0));
070                BOX.positive.add(new Pixel(1, 0));
071                BOX.positive.add(new Pixel(-1, 1));
072                BOX.positive.add(new Pixel(0, 1));
073                BOX.positive.add(new Pixel(1, 1));
074
075                CROSS = new StructuringElement();
076                CROSS.positive.add(new Pixel(0, -1));
077                CROSS.positive.add(new Pixel(-1, 0));
078                CROSS.positive.add(new Pixel(0, 0));
079                CROSS.positive.add(new Pixel(1, 0));
080                CROSS.positive.add(new Pixel(0, 1));
081
082                HPIT = new StructuringElement();
083                HPIT.positive.add(new Pixel(-1, 0));
084                HPIT.positive.add(new Pixel(1, 0));
085        }
086
087        /**
088         * Set of positive pixels in the structuring element
089         */
090        public Set<Pixel> positive = new HashSet<Pixel>();
091
092        /**
093         * Set of negative pixels in the structuring element
094         */
095        public Set<Pixel> negative = new HashSet<Pixel>();
096
097        /**
098         * Construct an empty structuring element
099         */
100        public StructuringElement() {
101
102        }
103
104        /**
105         * Construct a structuring element with the given positive and negative
106         * pixels
107         * 
108         * @param positive
109         *            the positive pixels
110         * @param negative
111         *            the negative pixels
112         */
113        public StructuringElement(Set<Pixel> positive, Set<Pixel> negative) {
114                if (positive != null)
115                        this.positive.addAll(positive);
116                if (negative != null)
117                        this.negative.addAll(negative);
118        }
119
120        /**
121         * Construct a structuring element with the given positive and negative
122         * pixels
123         * 
124         * @param positive
125         *            the positive pixels
126         * @param negative
127         *            the negative pixels
128         */
129        public StructuringElement(Pixel[] positive, Pixel[] negative) {
130                if (positive != null)
131                        this.positive.addAll(Arrays.asList(positive));
132                if (negative != null)
133                        this.negative.addAll(Arrays.asList(negative));
134        }
135
136        /**
137         * Get the size of the structuring element in the form [width, height, x, y]
138         * 
139         * @return the size of the structuring element
140         */
141        public int[] size() {
142                int xmin = Integer.MAX_VALUE;
143                int xmax = -Integer.MAX_VALUE;
144                int ymin = Integer.MAX_VALUE;
145                int ymax = -Integer.MAX_VALUE;
146
147                for (final Pixel p : positive) {
148                        if (p.x < xmin)
149                                xmin = p.x;
150                        if (p.x > xmax)
151                                xmax = p.x;
152                        if (p.y < ymin)
153                                ymin = p.y;
154                        if (p.y > ymax)
155                                ymax = p.y;
156                }
157                for (final Pixel p : negative) {
158                        if (p.x < xmin)
159                                xmin = p.x;
160                        if (p.x > xmax)
161                                xmax = p.x;
162                        if (p.y < ymin)
163                                ymin = p.y;
164                        if (p.y > ymax)
165                                ymax = p.y;
166                }
167
168                return new int[] { 1 + xmax - xmin, 1 + ymax - ymin, xmin, ymin };
169        }
170
171        /**
172         * Construct a structuring element from a @link{String} of the form produced
173         * by @link{#toString()}.
174         * 
175         * @see #toString()
176         * 
177         * @param ele
178         *            the string defining the element
179         * @param cx
180         *            the top-left x-coordinate
181         * @param cy
182         *            the top-left y-coordinate
183         * @return a new structuring element
184         */
185        public static StructuringElement parseElement(String ele, int cx, int cy) {
186                final String[] lines = ele.split("\\n");
187                final int height = lines.length;
188                final int width = lines[0].length();
189
190                final StructuringElement se = new StructuringElement();
191
192                for (int j = 0; j < height; j++) {
193                        for (int i = 0; i < width; i++) {
194                                final char c = lines[j].charAt(i);
195
196                                if (c == '*') {
197                                        se.positive.add(new Pixel(i - cx, j - cy));
198                                } else if (c == 'o') {
199                                        se.negative.add(new Pixel(i - cx, j - cy));
200                                }
201                        }
202                }
203
204                return se;
205        }
206
207        @Override
208        public String toString() {
209                final int[] sz = size();
210                String s = "";
211
212                for (int j = 0; j < sz[1]; j++) {
213                        for (int i = 0; i < sz[0]; i++) {
214                                final Pixel p = new Pixel(i + sz[2], j + sz[3]);
215
216                                if (positive.contains(p))
217                                        s += "*";
218                                else if (negative.contains(p))
219                                        s += "o";
220                                else
221                                        s += ".";
222                        }
223                        s += "\n";
224                }
225
226                return s;
227        }
228
229        /**
230         * Determine if this structuring element is completely contained in the
231         * pixels centered at p.
232         * 
233         * @param p
234         *            the centre
235         * @param pixels
236         *            the pixels
237         * @return true if completely contained, false otherwise
238         */
239        public boolean matches(Pixel p, Set<Pixel> pixels) {
240                // is the s.e completely contained in the pixels centered at p?
241                return (intersect(p, pixels).size() == countActive());
242        }
243
244        Set<Pixel> intersect(Pixel p, Set<Pixel> pixels) {
245                final Set<Pixel> intersect = new HashSet<Pixel>();
246
247                // positive
248                for (final Pixel sep : positive) {
249                        final Pixel imp = new Pixel(p.x + sep.x, p.y + sep.y);
250
251                        if (pixels.contains(imp))
252                                intersect.add(imp);
253                }
254
255                // negative
256                for (final Pixel sep : negative) {
257                        final Pixel imp = new Pixel(p.x + sep.x, p.y + sep.y);
258
259                        if (!pixels.contains(imp))
260                                intersect.add(imp);
261                }
262
263                return intersect;
264        }
265
266        /**
267         * Count the total (positive and negative) number of pixels in this
268         * structuring element
269         * 
270         * @return the total number of pixels
271         */
272        public int countActive() {
273                return positive.size() + negative.size();
274        }
275
276        /**
277         * Build a disk shaped structuring element with the given radius.
278         * 
279         * @param radius
280         *            the disk radius
281         * @return the disk shaped S.E.
282         */
283        public static StructuringElement disk(int radius) {
284                final StructuringElement se = new StructuringElement();
285                final int r2 = radius * radius;
286
287                for (int j = -radius; j <= radius; j++) {
288                        final int j2 = j * j;
289                        for (int i = -radius; i <= radius; i++) {
290                                if ((i * i + j2) <= r2) {
291                                        se.positive.add(new Pixel(i, j));
292                                }
293                        }
294                }
295
296                return se;
297        }
298}