001/*******************************************************************************
002 * This software is provided as a supplement to the authors' textbooks on digital
003 * image processing published by Springer-Verlag in various languages and editions.
004 * Permission to use and distribute this software is granted under the BSD 2-Clause
005 * "Simplified" License (see http://opensource.org/licenses/BSD-2-Clause).
006 * Copyright (c) 2006-2023 Wilhelm Burger, Mark J. Burge. All rights reserved.
007 * Visit https://imagingbook.com for additional details.
008 ******************************************************************************/
009package imagingbook.common.regions;
010
011import imagingbook.common.geometry.basic.Pnt2d;
012import imagingbook.common.geometry.basic.Pnt2d.PntDouble;
013import imagingbook.common.geometry.basic.Pnt2d.PntInt;
014import imagingbook.common.geometry.ellipse.GeometricEllipse;
015import imagingbook.common.util.GenericProperties;
016
017import java.awt.Rectangle;
018import java.util.Formatter;
019import java.util.List;
020import java.util.Locale;
021import java.util.Objects;
022
023import static imagingbook.common.math.Arithmetic.sqr;
024import static java.lang.Math.sqrt;
025
026/**
027 * <p>
028 * This class represents a connected component or binary region. See Sec. 8.4 of [1] for additional details. Instances
029 * of this class support iteration over the contained pixel coordinates of type {@link Pnt2d}, e.g., by
030 * </p>
031 * <pre>
032 * import imagingbook.pub.geometry.basic.Pnt2d;
033 * BinaryRegion R = ...;
034 * for (Pnt2d p : R) {
035 *    // process point p ...
036 * }
037 * </pre>
038 * <p>
039 * The advantage of providing iteration only is that it avoids the creation of (possibly large) arrays of pixel
040 * coordinates.
041 * </p>
042 * <p>
043 * [1] W. Burger, M.J. Burge, <em>Digital Image Processing &ndash; An Algorithmic Introduction</em>, 3rd ed, Springer
044 * (2022).
045 * </p>
046 *
047 * @author WB
048 * @version 2023/01/02
049 */
050public abstract class BinaryRegion implements Comparable<BinaryRegion>, Iterable<Pnt2d>, GenericProperties {
051        
052        // Constructor, to be used by package-local sub-classes only.
053        BinaryRegion() {
054        }
055
056        /**
057         * Returns the sum of the x-coordinates of the points contained in this region.
058         *
059         * @return the sum of x-values.
060         */
061        public abstract long getX1Sum();
062
063        /**
064         * Returns the sum of the y-coordinates of the points contained in this region.
065         *
066         * @return the sum of y-values.
067         */
068        public abstract long getY1Sum();
069
070        /**
071         * Returns the sum of the squared x-coordinates of the points contained in this region.
072         *
073         * @return the sum of squared x-values.
074         */
075        public abstract long getX2Sum();
076
077        /**
078         * Returns the sum of the squared y-coordinates of the points contained in this region.
079         *
080         * @return the sum of squared y-values.
081         */
082        public abstract long getY2Sum();
083
084        /**
085         * Returns the sum of the mixed x*y-coordinates of the points contained in this region.
086         *
087         * @return the sum of xy-values.
088         */
089        public abstract long getXYSum();
090
091        /**
092         * Calculates and returns a vector of ordinary moments: (m10, m01, m20, m02, m11).
093         *
094         * @return vector of ordinary moments
095         */
096        public double[] getMoments() {
097                final int n = this.getSize();
098                if (n == 0) {
099                        throw new IllegalStateException("empty region, moments are undefined");
100                }
101                double m10 = getX1Sum() / (double) n;
102                double m01 = getY1Sum() / (double) n;
103                double m20 = getX2Sum() / (double) n;
104                double m02 = getY2Sum() / (double) n;
105                double m11 = getXYSum() / (double) n;
106                return new double[] {m10, m01, m20, m02, m11};
107        }
108
109        /**
110         * Calculates and returns a vector of central moments: (mu20, mu02, mu11).
111         *
112         * @return vector of central moments
113         */
114        public double[] getCentralMoments() {
115                final int n = this.getSize();
116                if (n == 0) {
117                        throw new IllegalStateException("empty region, moments are undefined");
118                }
119                double mu20 = getX2Sum() - getX1Sum() * getX1Sum() / (double) n;
120                double mu02 = getY2Sum() - getY1Sum() * getY1Sum() / (double) n;
121                double mu11 = getXYSum() - getX1Sum() * getY1Sum() / (double) n;
122                return new double[] {mu20, mu02, mu11};
123        }
124
125        /**
126         * <p>
127         * Returns the 2x2 covariance matrix for the pixel coordinates contained in this region: <br> | &sigma;<sub>20</sub>
128         * &sigma;<sub>11</sub> | <br> | &sigma;<sub>11</sub> &sigma;<sub>02</sub> |
129         * </p>
130         *
131         * @return the covariance matrix
132         */
133        public double[][] getCovarianceMatrix() {
134                final int n = this.getSize();
135                double[] mu = getCentralMoments(); // = [mu20, mu02, mu11]
136                double[][] S = {
137                                {mu[0]/n, mu[2]/n},
138                                {mu[2]/n, mu[1]/n}};
139                return S;
140        }
141
142        /**
143         * Get the size of this region.
144         * @return the number of region points.
145         */
146        public abstract int getSize();
147
148        /**
149         * Get the x/y axes-parallel bounding box as a rectangle (including the extremal coordinates).
150         *
151         * @return the bounding box rectangle.
152         */
153        public abstract Rectangle getBoundingBox();
154
155
156        /**
157         * Returns the center of this region as a 2D point.
158         * @return the center point of this region.
159         */
160        public Pnt2d getCenter() {
161                final int n = this.getSize();
162                if (n == 0) {
163                        throw new IllegalStateException("empty region, center is undefined");
164                }
165                return PntDouble.from(((double)this.getX1Sum())/n, ((double)this.getY1Sum())/n);
166        }
167
168        /**
169         * <p>
170         * Calculates and returns this region's equivalent ellipse (see Sec. 8.6.3 of [1] for details).
171         * </p>
172         * <p>
173         * [1] W. Burger, M.J. Burge, <em>Digital Image Processing &ndash; An Algorithmic Introduction</em>, 3rd ed,
174         * Springer (2022).
175         * </p>
176         *
177         * @return the equivalent ellipse (instance of {@link GeometricEllipse})
178         */
179        public GeometricEllipse getEquivalentEllipse() {
180                final double n = this.getSize();
181                Pnt2d xc = this.getCenter();
182                double[] moments = this.getCentralMoments(); // = (mu20, mu02, mu11)
183                final double mu20 = moments[0];
184                final double mu02 = moments[1];
185                final double mu11 = moments[2];
186                
187                // direct calculation (without explicit Eigensolver): 
188                final double theta = 0.5 * Math.atan2(2 * mu11, mu20 - mu02);   // see [1], eq. 8.28
189                final double A = mu20 + mu02;
190                final double B = sqr(mu20 - mu02) + 4 * sqr(mu11);
191                if (B < 0) {
192                        throw new RuntimeException("negative B: " + B); // this should never happen
193                }               
194                final double a1 = A + sqrt(B);          // see [1], eq. 8.38
195                final double a2 = A - sqrt(B);
196                final double ra = sqrt(2 * a1 / n);     // see [1], eq. 8.40
197                final double rb = sqrt(2 * a2 / n);
198                
199                // same calculation using Eigensolver:
200//              Eigensolver2x2 solver = new Eigensolver2x2(mu20, mu11, mu11, mu02);
201//              double ra = 2 * Math.sqrt(solver.getRealEigenvalue(0) / n);
202//              double rb = 2 * Math.sqrt(solver.getRealEigenvalue(1) / n);
203//              double[] e0 = solver.getEigenvector(0).toArray();
204//              double theta = Math.atan2(e0[1], e0[0]);
205                
206                return new GeometricEllipse(ra, rb, xc.getX(), xc.getY(), theta);
207        }
208        
209        abstract void setOuterContour(Contour.Outer contr);
210
211        /**
212         * Returns the (single) outer contour of this region if available, null otherwise. Points on an outer contour are
213         * arranged in clockwise order.
214         *
215         * @return the outer contour or {@code null} if not available
216         */
217        public abstract Contour getOuterContour();
218
219        /**
220         * Get all inner contours of this region if available, null otherwise. Points on inner contours are arranged in
221         * counter-clockwise order.
222         *
223         * @return the (possibly empty) list of inner contours or {@code null} if not available
224         */
225        public abstract List<Contour> getInnerContours();
226
227        // Compare method for sorting by region size (larger regions at front)
228        @Override
229        public int compareTo(BinaryRegion other) {
230                return Integer.compare(other.getSize(), this.getSize());
231        }
232
233        /**
234         * Checks if the given pixel position is contained in this {@link BinaryRegion} instance.
235         *
236         * @param u x-coordinate
237         * @param v y-coordinate
238         * @return true if (u,v) is contained in this region
239         */
240        public abstract boolean contains(int u, int v);
241
242        /**
243         * Checks if the given pixel position is contained in this {@link BinaryRegion} instance.
244         *
245         * @param p the pixel coordinate
246         * @return true if the position is contained in this region
247         */
248        public boolean contains(PntInt p) {
249                return this.contains(p.x, p.y);
250        }
251
252        // for attaching properties at runtime ---------------------------------
253
254        private PropertyMap properties = null;
255
256        @Override
257        public PropertyMap getPropertyMap() {
258                if (Objects.isNull(properties)) {
259                        properties = new PropertyMap();
260                }
261                return properties;
262        }
263
264        // ---------------------------------------------------------------------
265        
266        @Override
267        public String toString() {
268                Pnt2d xc = this.getCenter();
269                try (Formatter fm = new Formatter(new StringBuilder(), Locale.US)) {
270                        fm.format("%s:", this.getClass().getSimpleName());
271                        fm.format(" area = %d", this.getSize());
272                        fm.format(", bounding box = %s", this.getBoundingBox());
273                        fm.format(", center = (%.2f, %.2f)", xc.getX(), xc.getY());
274        //              if (innerContours != null)
275        //                      fm.format(", holes = %d", innerContours.size());
276                        //String s = fm.toString();
277                        return fm.toString();
278                } //fm.close();
279                //return s;
280        }
281        
282
283}