/* * Copyright 2010-2013 Institut Pasteur. * * This file is part of Icy. * * Icy is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * Icy is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with Icy. If not, see <http://www.gnu.org/licenses/>. */ package icy.roi; import icy.type.TypeUtil; import icy.type.collection.array.DynamicArray; import java.awt.Point; import java.awt.Rectangle; import java.util.ArrayList; import java.util.Arrays; import java.util.Comparator; import java.util.List; /** * Class to define a 2D boolean mask and make basic boolean operation between masks.<br> * The bounds property of this object define the area of the mask where the mask contains the * boolean mask itself. * * @author Stephane */ public class BooleanMask2D implements Cloneable { private static class Component { public DynamicArray.Int points; public List<Component> children; private Component root; public Component() { points = new DynamicArray.Int(0); children = new ArrayList<Component>(); root = this; } public void addPoint(int x, int y) { points.addSingle(x); points.addSingle(y); } public void addComponent(Component c) { final Component croot = c.root; if (croot != root) { children.add(croot); croot.setRoot(root); } } public boolean isRoot() { return root == this; } private void setRoot(Component value) { root = value; final int size = children.size(); for (int c = 0; c < size; c++) children.get(c).setRoot(value); } public int getTotalSize() { int result = points.getSize(); final int size = children.size(); for (int c = 0; c < size; c++) result += children.get(c).getTotalSize(); return result; } public int[] getAllPoints() { final int[] result = new int[getTotalSize()]; // get all point getAllPoints(result, 0); return result; } private int getAllPoints(int[] result, int offset) { final int[] intPoints = points.asArray(); System.arraycopy(intPoints, 0, result, offset, intPoints.length); int off = offset + intPoints.length; final int csize = children.size(); for (int c = 0; c < csize; c++) off = children.get(c).getAllPoints(result, off); return off; } } /** * Build global boolean mask from union of all specified mask */ public static BooleanMask2D getUnion(List<BooleanMask2D> masks) { BooleanMask2D result = null; // compute global union boolean mask of all ROI2D for (BooleanMask2D bm : masks) { // update global mask if (result == null) result = new BooleanMask2D(bm.bounds, bm.mask); else result = getUnion(result, bm); } // return an empty BooleanMask2D instead of null if (result == null) result = new BooleanMask2D(); return result; } /** * Build resulting mask from union of the mask1 and mask2.<br> * If <code>mask1</code> is <code>null</code> then a copy of <code>mask2</code> is returned.<br> * If <code>mask2</code> is <code>null</code> then a copy of <code>mask1</code> is returned.<br> * An empty mask is returned if both <code>mask1</code> and <code>mask2</code> are * <code>null</code>. */ public static BooleanMask2D getUnion(BooleanMask2D mask1, BooleanMask2D mask2) { if ((mask1 == null) && (mask2 == null)) return new BooleanMask2D(); if ((mask1 == null) || mask1.isEmpty()) return (BooleanMask2D) mask2.clone(); if ((mask2 == null) || mask2.isEmpty()) return (BooleanMask2D) mask1.clone(); return getUnion(mask1.bounds, mask1.mask, mask2.bounds, mask2.mask); } /** * Build resulting mask from union of the mask1 and mask2: * * <pre> * mask1 + mask2 = result * * ################ ################ ################ * ############## ############## ################ * ############ ############ ################ * ########## ########## ################ * ######## ######## ################ * ###### ###### ###### ###### * #### #### #### #### * ## ## ## ## * </pre> */ public static BooleanMask2D getUnion(Rectangle bounds1, boolean[] mask1, Rectangle bounds2, boolean[] mask2) { final Rectangle union = bounds1.union(bounds2); if (!union.isEmpty()) { final boolean[] mask = new boolean[union.width * union.height]; int offDst, offSrc; // calculate offset offDst = ((bounds1.y - union.y) * union.width) + (bounds1.x - union.x); offSrc = 0; for (int y = 0; y < bounds1.height; y++) { for (int x = 0; x < bounds1.width; x++) mask[offDst + x] |= mask1[offSrc++]; offDst += union.width; } // calculate offset offDst = ((bounds2.y - union.y) * union.width) + (bounds2.x - union.x); offSrc = 0; for (int y = 0; y < bounds2.height; y++) { for (int x = 0; x < bounds2.width; x++) mask[offDst + x] |= mask2[offSrc++]; offDst += union.width; } return new BooleanMask2D(union, mask); } return new BooleanMask2D(); } /** * Build global boolean mask from intersection of all specified mask */ public static BooleanMask2D getIntersection(List<BooleanMask2D> masks) { BooleanMask2D result = null; // compute global intersect boolean mask of all ROI2D for (BooleanMask2D bm : masks) { // update global mask if (result == null) result = new BooleanMask2D(bm.bounds, bm.mask); else result = getIntersection(result, bm); } // return an empty BooleanMask2D instead of null if (result == null) result = new BooleanMask2D(); return result; } /** * Build resulting mask from intersection of the mask1 and mask2.<br> * An empty mask is returned if <code>mask1</code> or <code>mask2</code> is <code>null</code>. */ public static BooleanMask2D getIntersection(BooleanMask2D mask1, BooleanMask2D mask2) { if ((mask1 == null) || (mask2 == null)) return new BooleanMask2D(); return getIntersection(mask1.bounds, mask1.mask, mask2.bounds, mask2.mask); } /** * Build resulting mask from intersection of the mask1 and mask2: * * <pre> * mask1 intersect mask2 = result * * ################ ################ ################ * ############## ############## ############ * ############ ############ ######## * ########## ########## #### * ######## ######## * ###### ###### * #### #### * ## ## * </pre> */ public static BooleanMask2D getIntersection(Rectangle bounds1, boolean[] mask1, Rectangle bounds2, boolean[] mask2) { final Rectangle intersect = bounds1.intersection(bounds2); if (!intersect.isEmpty()) { final boolean[] mask = new boolean[intersect.width * intersect.height]; // calculate offsets int off1 = ((intersect.y - bounds1.y) * bounds1.width) + (intersect.x - bounds1.x); int off2 = ((intersect.y - bounds2.y) * bounds2.width) + (intersect.x - bounds2.x); int off = 0; for (int y = 0; y < intersect.height; y++) { for (int x = 0; x < intersect.width; x++) mask[off++] = mask1[off1 + x] & mask2[off2 + x]; off1 += bounds1.width; off2 += bounds2.width; } return new BooleanMask2D(intersect, mask); } return new BooleanMask2D(); } /** * Build global boolean mask from exclusive union of all specified mask */ public static BooleanMask2D getExclusiveUnion(List<BooleanMask2D> masks) { BooleanMask2D result = null; // compute global exclusive union boolean mask of all ROI2D for (BooleanMask2D bm : masks) { // update global mask if (result == null) result = new BooleanMask2D(bm.bounds, bm.mask); else result = getExclusiveUnion(result, bm); } // return an empty BooleanMask2D instead of null if (result == null) result = new BooleanMask2D(); return result; } /** * Build resulting mask from exclusive union of the mask1 and mask2.<br> * If <code>mask1</code> is <code>null</code> then a copy of <code>mask2</code> is returned.<br> * If <code>mask2</code> is <code>null</code> then a copy of <code>mask1</code> is returned.<br> * <code>null</code> is returned if both <code>mask1</code> and <code>mask2</code> are * <code>null</code>. */ public static BooleanMask2D getExclusiveUnion(BooleanMask2D mask1, BooleanMask2D mask2) { if ((mask1 == null) && (mask2 == null)) return new BooleanMask2D(); if ((mask1 == null) || mask1.isEmpty()) return (BooleanMask2D) mask2.clone(); if ((mask2 == null) || mask2.isEmpty()) return (BooleanMask2D) mask1.clone(); return getExclusiveUnion(mask1.bounds, mask1.mask, mask2.bounds, mask2.mask); } /** * Build resulting mask from exclusive union of the mask1 and mask2: * * <pre> * mask1 xor mask2 = result * * ################ ################ * ############## ############## ## ## * ############ ############ #### #### * ########## ########## ###### ###### * ######## ######## ################ * ###### ###### ###### ###### * #### #### #### #### * ## ## ## ## * </pre> */ public static BooleanMask2D getExclusiveUnion(Rectangle bounds1, boolean[] mask1, Rectangle bounds2, boolean[] mask2) { final Rectangle union = bounds1.union(bounds2); if (!union.isEmpty()) { final boolean[] mask = new boolean[union.width * union.height]; int offDst, offSrc; // calculate offset offDst = ((bounds1.y - union.y) * union.width) + (bounds1.x - union.x); offSrc = 0; for (int y = 0; y < bounds1.height; y++) { for (int x = 0; x < bounds1.width; x++) mask[offDst + x] ^= mask1[offSrc++]; offDst += union.width; } // calculate offset offDst = ((bounds2.y - union.y) * union.width) + (bounds2.x - union.x); offSrc = 0; for (int y = 0; y < bounds2.height; y++) { for (int x = 0; x < bounds2.width; x++) mask[offDst + x] ^= mask2[offSrc++]; offDst += union.width; } final BooleanMask2D result = new BooleanMask2D(union, mask); // optimize bounds result.optimizeBounds(); return result; } return new BooleanMask2D(); } /** * Build resulting mask from the subtraction of mask2 from mask1.<br> * If <code>mask2</code> is <code>null</code> then a copy of <code>mask1</code> is returned.<br> * If <code>mask1</code> is <code>null</code> then a empty mask is returned. */ public static BooleanMask2D getSubtraction(BooleanMask2D mask1, BooleanMask2D mask2) { if (mask1 == null) return new BooleanMask2D(); if (mask2 == null) return (BooleanMask2D) mask1.clone(); return getSubtraction(mask1.bounds, mask1.mask, mask2.bounds, mask2.mask); } /** * Build resulting mask from the subtraction of mask2 from mask1: * * <pre> * mask1 - mask2 = result * * ################ ################ * ############## ############## ## * ############ ############ #### * ########## ########## ###### * ######## ######## ######## * ###### ###### ###### * #### #### #### * ## ## ## * </pre> */ public static BooleanMask2D getSubtraction(Rectangle bounds1, boolean[] mask1, Rectangle bounds2, boolean[] mask2) { final boolean[] mask = mask1.clone(); final Rectangle subtract = new Rectangle(bounds1); final BooleanMask2D result = new BooleanMask2D(subtract, mask); // compute intersection final Rectangle intersection = bounds1.intersection(bounds2); // need to subtract something ? if (!intersection.isEmpty()) { // calculate offset int offDst = ((intersection.y - subtract.y) * subtract.width) + (intersection.x - subtract.x); int offSrc = ((intersection.y - bounds2.y) * bounds2.width) + (intersection.x - bounds2.x); for (int y = 0; y < intersection.height; y++) { for (int x = 0; x < intersection.width; x++) mask[offDst + x] &= !mask2[offSrc + x]; offDst += subtract.width; offSrc += bounds2.width; } // optimize bounds result.optimizeBounds(); } return result; } /** * @deprecated Use {@link #getUnion(List)} instead. */ @Deprecated public static BooleanMask2D getUnionBooleanMask(List<BooleanMask2D> masks) { return getUnion(masks); } /** * @deprecated Use {@link ROIUtil#getUnion(List)} instead. */ @Deprecated public static BooleanMask2D getUnionBooleanMask(ROI2D[] rois) { final List<BooleanMask2D> masks = new ArrayList<BooleanMask2D>(); // compute global union boolean mask of all ROI2D for (ROI2D roi : rois) masks.add(roi.getBooleanMask(true)); return getUnionBooleanMask(masks); } /** * @deprecated Use {@link ROIUtil#getUnion(List)} instead. */ @Deprecated public static BooleanMask2D getUnionBooleanMask(ArrayList<ROI2D> rois) { return getUnionBooleanMask(rois.toArray(new ROI2D[rois.size()])); } /** * @deprecated Use {@link #getUnion(BooleanMask2D, BooleanMask2D)} instead. */ @Deprecated public static BooleanMask2D getUnionBooleanMask(BooleanMask2D mask1, BooleanMask2D mask2) { return getUnion(mask1, mask2); } /** * @deprecated Use {@link #getUnion(Rectangle, boolean[], Rectangle, boolean[])} instead. */ @Deprecated public static BooleanMask2D getUnionBooleanMask(Rectangle bounds1, boolean[] mask1, Rectangle bounds2, boolean[] mask2) { return getUnion(bounds1, mask1, bounds2, mask2); } /** * @deprecated Use {@link #getIntersection(List)} instead. */ @Deprecated public static BooleanMask2D getIntersectionBooleanMask(List<BooleanMask2D> masks) { return getIntersection(masks); } /** * @deprecated Use {@link #getIntersection(BooleanMask2D, BooleanMask2D)} instead. */ @Deprecated public static BooleanMask2D getIntersectionBooleanMask(BooleanMask2D mask1, BooleanMask2D mask2) { return getIntersection(mask1, mask2); } /** * @deprecated Use {@link #getIntersection(Rectangle, boolean[], Rectangle, boolean[])} instead. */ @Deprecated public static BooleanMask2D getIntersectionBooleanMask(Rectangle bounds1, boolean[] mask1, Rectangle bounds2, boolean[] mask2) { return getIntersection(bounds1, mask1, bounds2, mask2); } /** * @deprecated Use {@link ROIUtil#getIntersection(List)} instead. */ @Deprecated public static BooleanMask2D getIntersectBooleanMask(ROI2D[] rois) { final List<BooleanMask2D> masks = new ArrayList<BooleanMask2D>(); // compute global union boolean mask of all ROI2D for (ROI2D roi : rois) masks.add(roi.getBooleanMask(true)); return getIntersectionBooleanMask(masks); } /** * @deprecated Use {@link ROIUtil#getIntersection(List)} instead. */ @Deprecated public static BooleanMask2D getIntersectBooleanMask(ArrayList<ROI2D> rois) { return getIntersectBooleanMask(rois.toArray(new ROI2D[rois.size()])); } /** * @deprecated Use {@link #getIntersectionBooleanMask(BooleanMask2D, BooleanMask2D)} instead. */ @Deprecated public static BooleanMask2D getIntersectBooleanMask(BooleanMask2D mask1, BooleanMask2D mask2) { return getIntersectionBooleanMask(mask1.bounds, mask1.mask, mask2.bounds, mask2.mask); } /** * @deprecated Use * {@link #getIntersectionBooleanMask(Rectangle, boolean[], Rectangle, boolean[])} * instead. */ @Deprecated public static BooleanMask2D getIntersectBooleanMask(Rectangle bounds1, boolean[] mask1, Rectangle bounds2, boolean[] mask2) { return getIntersectionBooleanMask(bounds1, mask1, bounds2, mask2); } /** * @deprecated Use {@link #getExclusiveUnion(List)} instead. */ @Deprecated public static BooleanMask2D getExclusiveUnionBooleanMask(List<BooleanMask2D> masks) { return getExclusiveUnion(masks); } /** * @deprecated Use {@link ROIUtil#getExclusiveUnion(List)} instead. */ @Deprecated public static BooleanMask2D getExclusiveUnionBooleanMask(ROI2D[] rois) { final List<BooleanMask2D> masks = new ArrayList<BooleanMask2D>(); // compute global union boolean mask of all ROI2D for (ROI2D roi : rois) masks.add(roi.getBooleanMask(true)); return getExclusiveUnion(masks); } /** * @deprecated Use {@link ROIUtil#getExclusiveUnion(List)} instead. */ @Deprecated public static BooleanMask2D getExclusiveUnionBooleanMask(ArrayList<ROI2D> rois) { return getExclusiveUnionBooleanMask(rois.toArray(new ROI2D[rois.size()])); } /** * @deprecated Use {@link #getExclusiveUnion(BooleanMask2D, BooleanMask2D)} instead. */ @Deprecated public static BooleanMask2D getExclusiveUnionBooleanMask(BooleanMask2D mask1, BooleanMask2D mask2) { return getExclusiveUnion(mask1, mask2); } /** * @deprecated Use {@link #getExclusiveUnion(Rectangle, boolean[], Rectangle, boolean[])} * instead. */ @Deprecated public static BooleanMask2D getExclusiveUnionBooleanMask(Rectangle bounds1, boolean[] mask1, Rectangle bounds2, boolean[] mask2) { return getExclusiveUnion(bounds1, mask1, bounds2, mask2); } /** * @deprecated Use {@link #getExclusiveUnionBooleanMask(ROI2D[])} instead. */ @Deprecated public static BooleanMask2D getXorBooleanMask(ROI2D[] rois) { return getExclusiveUnionBooleanMask(rois); } /** * @deprecated Use {@link #getExclusiveUnionBooleanMask(List)} instead. */ @Deprecated public static BooleanMask2D getXorBooleanMask(ArrayList<ROI2D> rois) { return getExclusiveUnionBooleanMask(rois); } /** * @deprecated Use {@link #getExclusiveUnionBooleanMask(BooleanMask2D, BooleanMask2D)} instead. */ @Deprecated public static BooleanMask2D getXorBooleanMask(BooleanMask2D mask1, BooleanMask2D mask2) { return getExclusiveUnionBooleanMask(mask1, mask2); } /** * @deprecated Uses * {@link #getExclusiveUnionBooleanMask(Rectangle, boolean[], Rectangle, boolean[])} * instead. */ @Deprecated public static BooleanMask2D getXorBooleanMask(Rectangle bounds1, boolean[] mask1, Rectangle bounds2, boolean[] mask2) { return getExclusiveUnionBooleanMask(bounds1, mask1, bounds2, mask2); } /** * Region represented by the mask. */ public Rectangle bounds; /** * Boolean mask array. */ public boolean[] mask; /** * Create an empty BooleanMask2D */ public BooleanMask2D() { this(new Rectangle(), new boolean[0]); } /** * @param bounds * @param mask */ public BooleanMask2D(Rectangle bounds, boolean[] mask) { super(); this.bounds = bounds; this.mask = mask; } /** * Build a new boolean mask from the specified array of {@link Point}.<br> */ public BooleanMask2D(Point[] points) { super(); if ((points == null) || (points.length == 0)) { bounds = new Rectangle(); mask = new boolean[0]; } else { int minX = Integer.MAX_VALUE; int minY = Integer.MAX_VALUE; int maxX = Integer.MIN_VALUE; int maxY = Integer.MIN_VALUE; for (Point pt : points) { final int x = pt.x; final int y = pt.y; if (x < minX) minX = x; if (x > maxX) maxX = x; if (y < minY) minY = y; if (y > maxY) maxY = y; } bounds = new Rectangle(minX, minY, (maxX - minX) + 1, (maxY - minY) + 1); mask = new boolean[bounds.width * bounds.height]; for (Point pt : points) mask[((pt.y - minY) * bounds.width) + (pt.x - minX)] = true; } } /** * Build a new boolean mask from the specified array of integer representing points.<br> * <br> * The array should contains point coordinates defined as follow:<br> * <code>result.length</code> = number of point * 2<br> * <code>result[(pt * 2) + 0]</code> = X coordinate for point <i>pt</i>.<br> * <code>result[(pt * 2) + 1]</code> = Y coordinate for point <i>pt</i>.<br> */ public BooleanMask2D(int[] points) { super(); if ((points == null) || (points.length == 0)) { bounds = new Rectangle(); mask = new boolean[0]; } else { int minX = Integer.MAX_VALUE; int minY = Integer.MAX_VALUE; int maxX = Integer.MIN_VALUE; int maxY = Integer.MIN_VALUE; for (int i = 0; i < points.length; i += 2) { final int x = points[i + 0]; final int y = points[i + 1]; if (x < minX) minX = x; if (x > maxX) maxX = x; if (y < minY) minY = y; if (y > maxY) maxY = y; } bounds = new Rectangle(minX, minY, (maxX - minX) + 1, (maxY - minY) + 1); mask = new boolean[bounds.width * bounds.height]; for (int i = 0; i < points.length; i += 2) { final int x = points[i + 0]; final int y = points[i + 1]; mask[((y - minY) * bounds.width) + (x - minX)] = true; } } } /** * Return true if boolean mask is empty<br> */ public boolean isEmpty() { return bounds.isEmpty(); } /** * Return true if mask contains the specified point */ public boolean contains(int x, int y) { if (bounds.contains(x, y)) return mask[(x - bounds.x) + ((y - bounds.y) * bounds.width)]; return false; } /** * Return true if mask contains the specified 2Dmask. */ public boolean contains(BooleanMask2D booleanMask) { return contains(booleanMask.bounds, booleanMask.mask); } /** * Return true if mask contains the specified 2D mask. */ public boolean contains(Rectangle rect, boolean[] bmask) { final Rectangle intersect = bounds.intersection(rect); // intersection should be equal to rect if (intersect.equals(rect)) { // calculate offsets int off1 = ((intersect.y - bounds.y) * bounds.width) + (intersect.x - bounds.x); int off2 = ((intersect.y - rect.y) * rect.width) + (intersect.x - rect.x); for (int y = 0; y < intersect.height; y++) { for (int x = 0; x < intersect.width; x++) if (bmask[off2 + x] && !mask[off1 + x]) return false; off1 += bounds.width; off2 += rect.width; } return true; } return false; } /** * Return true if mask intersects (contains at least one point) the specified 2D mask. */ public boolean intersects(BooleanMask2D booleanMask) { return intersects(booleanMask.bounds, booleanMask.mask); } /** * Return true if mask intersects (contains at least one point) the specified 2D mask region. */ public boolean intersects(Rectangle rect, boolean[] bmask) { final Rectangle intersect = bounds.intersection(rect); if (!intersect.isEmpty()) { // calculate offsets int off1 = ((intersect.y - bounds.y) * bounds.width) + (intersect.x - bounds.x); int off2 = ((intersect.y - rect.y) * rect.width) + (intersect.x - rect.x); for (int y = 0; y < intersect.height; y++) { for (int x = 0; x < intersect.width; x++) if (mask[off1 + x] && bmask[off2 + x]) return true; off1 += bounds.width; off2 += rect.width; } } return false; } /** * Return an array of {@link Point} representing all points of the current mask.<br> * Points are returned in ascending XY order : * * <pre> * Ymin 12 * 3456 * 78 * Ymax 9 * </pre> * * @see #getPointsAsIntArray() */ public Point[] getPoints() { return TypeUtil.toPoint(getPointsAsIntArray()); } /** * Return an array of integer representing all points of the current mask.<br> * <code>result.length</code> = number of point * 2<br> * <code>result[(pt * 2) + 0]</code> = X coordinate for point <i>pt</i>.<br> * <code>result[(pt * 2) + 1]</code> = Y coordinate for point <i>pt</i>.<br> * Points are returned in ascending XY order : * * <pre> * Ymin 12 * 3456 * 78 * Ymax 9 * </pre> */ public int[] getPointsAsIntArray() { if (bounds.isEmpty()) return new int[0]; int[] points = new int[mask.length * 2]; final int maxx = bounds.x + bounds.width; final int maxy = bounds.y + bounds.height; int pt = 0; int off = 0; for (int y = bounds.y; y < maxy; y++) { for (int x = bounds.x; x < maxx; x++) { if (mask[off++]) { points[pt++] = x; points[pt++] = y; } } } final int[] result = new int[pt]; System.arraycopy(points, 0, result, 0, pt); return result; } /** * Return a 2D array of integer representing points of each component of the current mask.<br> * A component is basically an isolated object which does not touch any other objects.<br> * Internal use only. */ protected List<Component> getComponentsPointsInternal() { final List<Component> components = new ArrayList<Component>(); final int w = bounds.width; final int minx = bounds.x; final int miny = bounds.y; // cache final Component[] line0 = new Component[w + 2]; final Component[] line1 = new Component[w + 2]; Arrays.fill(line0, null); Arrays.fill(line1, null); Component[] prevLine = line0; Component[] currLine = line1; Component left; Component top; Component topleft; int offset = 0; for (int y = 0; y < bounds.height; y++) { // prepare previous cache topleft = null; left = null; for (int x = 0; x < w; x++) { top = prevLine[x + 1]; // we have a component pixel if (mask[offset++]) { if (topleft != null) { // mix component if ((left != null) && (left != topleft)) topleft.addComponent(left); left = topleft; } else if (top != null) { // mix component if ((left != null) && (left != top)) top.addComponent(left); left = top; } else if (left == null) { // new component left = new Component(); components.add(left); } // add pixel to component left.addPoint(x + minx, y + miny); } else { // mix component if ((left != null) && (top != null) && (left != top)) top.addComponent(left); left = null; } topleft = top; // set current component index line cache currLine[x + 1] = left; } Component[] pl = prevLine; prevLine = currLine; currLine = pl; } final List<Component> result = new ArrayList<Component>(); // remove partial components for (Component component : components) if (component.isRoot()) result.add(component); return result; } /** * Compute and return a 2D array of {@link Point} representing points of each component of the * current mask.<br> * A component is basically an isolated object which do not touch any other object.<br> * <br> * The array is returned in the following format :<br> * <code>result.lenght</code> = number of component.<br> * <code>result[c].length</code> = number of point of component c.<br> * <code>result[c][n]</code> = Point n of component c.<br> * * @param sorted * When true points are returned in ascending XY order : * * <pre> * Ymin 12 * 3456 * 78 * Ymax 9 * </pre> * @see #getComponentsPointsAsIntArray() */ public Point[][] getComponentsPoints(boolean sorted) { if (bounds.isEmpty()) return new Point[0][0]; final Comparator<Point> pointComparator; if (sorted) { pointComparator = new Comparator<Point>() { @Override public int compare(Point p1, Point p2) { if (p1.y < p2.y) return -1; if (p1.y > p2.y) return 1; return 0; } }; } else pointComparator = null; final int[][] cPoints = getComponentsPointsAsIntArray(); final Point[][] cResult = new Point[cPoints.length][]; for (int i = 0; i < cPoints.length; i++) { final Point[] result = TypeUtil.toPoint(cPoints[i]); // sort points if (pointComparator != null) Arrays.sort(result, pointComparator); cResult[i] = result; } return cResult; } /** * Compute and return a 2D array of integer representing points of each component of the * current mask.<br> * A component is basically an isolated object which do not touch any other object.<br> * <br> * The array is returned in the following format :<br> * <code>result.lenght</code> = number of component.<br> * <code>result[c].length</code> = number of point * 2 for component c.<br> * <code>result[c][(pt * 2) + 0]</code> = X coordinate for point <i>pt</i> of component * <i>c</i>.<br> * <code>result[c][(pt * 2) + 1]</code> = Y coordinate for point <i>pt</i> of component * <i>c</i>.<br> * * @see #getComponentsPoints(boolean) */ public int[][] getComponentsPointsAsIntArray() { if (bounds.isEmpty()) return new int[0][0]; final List<Component> components = getComponentsPointsInternal(); final int[][] result = new int[components.size()][]; // convert list of point to Point array for (int i = 0; i < result.length; i++) result[i] = components.get(i).getAllPoints(); return result; } /** * Return an array of boolean mask representing each independent component of the current * mask.<br> * A component is basically an isolated object which does not touch any other objects. */ public BooleanMask2D[] getComponents() { if (bounds.isEmpty()) return new BooleanMask2D[0]; final int[][] componentsPoints = getComponentsPointsAsIntArray(); final List<BooleanMask2D> result = new ArrayList<BooleanMask2D>(); // convert array of point to boolean mask for (int[] componentPoints : componentsPoints) result.add(new BooleanMask2D(componentPoints)); return result.toArray(new BooleanMask2D[result.size()]); } /** * Return an array of {@link Point} containing the contour points of the mask.<br> * Points are returned in ascending XY order: * * <pre> * 123 * 4 5 * 6 7 * 89 * </pre> * * @see #getContourPointsAsIntArray() */ public Point[] getContourPoints() { return TypeUtil.toPoint(getContourPointsAsIntArray()); } /** * Return an array of integer containing the contour points of the mask.<br> * <code>result.length</code> = number of point * 2<br> * <code>result[(pt * 2) + 0]</code> = X coordinate for point <i>pt</i>.<br> * <code>result[(pt * 2) + 1]</code> = Y coordinate for point <i>pt</i>.<br> * Points are returned in ascending XY order: * * <pre> * 123 * 4 5 * 6 7 * 89 * </pre> */ public int[] getContourPointsAsIntArray() { if (isEmpty()) return new int[0]; final int[] points = new int[mask.length * 2]; final int h = bounds.height; final int w = bounds.width; final int maxx = bounds.x + (w - 1); final int maxy = bounds.y + (h - 1); // cache boolean top = false; boolean bottom = false; boolean left = false; boolean right = false; boolean current; int offset = 0; int pt = 0; // special case if ((w == 1) && (h == 1)) { if (mask[0]) { points[pt++] = bounds.x; points[pt++] = bounds.y; } } else if (w == 1) { // first pixel of row top = false; current = mask[offset]; bottom = mask[++offset]; // current pixel is a border ? if (current && !(top && bottom)) { points[pt++] = bounds.x; points[pt++] = bounds.y; } // row for (int y = bounds.y + 1; y < maxy; y++) { // cache top = current; current = bottom; bottom = mask[++offset]; // current pixel is a border ? if (current && !(top && bottom)) { points[pt++] = bounds.x; points[pt++] = y; } } // cache top = current; current = bottom; bottom = false; // current pixel is a border ? if (current && !(top && bottom)) { points[pt++] = bounds.x; points[pt++] = maxy; } } // special case else if (h == 1) { // first pixel of line left = false; current = mask[offset]; right = mask[++offset]; // current pixel is a border ? if (current && !(left && right)) { points[pt++] = bounds.x; points[pt++] = bounds.y; } // line for (int x = bounds.x + 1; x < maxx; x++) { // cache left = current; current = right; right = mask[++offset]; // current pixel is a border ? if (current && !(left && right)) { points[pt++] = x; points[pt++] = bounds.y; } } // last pixel of first line left = current; current = right; right = false; // current pixel is a border ? if (current && !(left && right)) { points[pt++] = maxx; points[pt++] = bounds.y; } } else { // first pixel of first line top = false; left = false; current = mask[offset]; bottom = mask[offset + w]; right = mask[++offset]; // current pixel is a border ? if (current && !(top && left && right && bottom)) { points[pt++] = bounds.x; points[pt++] = bounds.y; } // first line for (int x = bounds.x + 1; x < maxx; x++) { // cache left = current; current = right; bottom = mask[offset + w]; right = mask[++offset]; // current pixel is a border ? if (current && !(top && left && right && bottom)) { points[pt++] = x; points[pt++] = bounds.y; } } // last pixel of first line left = current; current = right; bottom = mask[offset + w]; right = false; offset++; // current pixel is a border ? if (current && !(top && left && right && bottom)) { points[pt++] = maxx; points[pt++] = bounds.y; } for (int y = bounds.y + 1; y < maxy; y++) { // first pixel of line left = false; current = mask[offset]; top = mask[offset - w]; bottom = mask[offset + w]; right = mask[++offset]; // current pixel is a border ? if (current && !(top && left && right && bottom)) { points[pt++] = bounds.x; points[pt++] = y; } for (int x = bounds.x + 1; x < maxx; x++) { // cache left = current; current = right; top = mask[offset - w]; bottom = mask[offset + w]; right = mask[++offset]; // current pixel is a border ? if (current && !(top && left && right && bottom)) { points[pt++] = x; points[pt++] = y; } } // last pixel of line left = current; current = right; top = mask[offset - w]; bottom = mask[offset + w]; right = false; offset++; // current pixel is a border ? if (current && !(top && left && right && bottom)) { points[pt++] = maxx; points[pt++] = y; } } // first pixel of last line left = false; current = mask[offset]; top = mask[offset - w]; bottom = false; right = mask[++offset]; // current pixel is a border ? if (current && !(top && left && right && bottom)) { points[pt++] = bounds.x; points[pt++] = maxy; } // last line for (int x = bounds.x + 1; x < maxx; x++) { // cache left = current; current = right; top = mask[offset - w]; right = mask[++offset]; // current pixel is a border ? if (current && !(top && left && right && bottom)) { points[pt++] = x; points[pt++] = maxy; } } // last pixel of last line left = current; current = right; top = mask[offset - w]; right = false; // current pixel is a border ? if (current && !(top && left && right && bottom)) { points[pt++] = maxx; points[pt++] = maxy; } } final int[] result = new int[pt]; System.arraycopy(points, 0, result, 0, pt); return result; } /** * @deprecated Use {@link #getContourPoints()} instead. */ @Deprecated public Point[] getEdgePoints() { return TypeUtil.toPoint(getContourPointsAsIntArray()); } /** * Computes and returns the length of the contour.<br/> * This is different from the number of contour point as it takes care of approximating * correctly distance between each contour point. * * @author Alexandre Dufour * @return the length of the contour */ public double getContourLength() { double perimeter = 0; final int[] edge = getContourPointsAsIntArray(); final int baseX = bounds.x; final int baseY = bounds.y; final int width = bounds.width; final int height = bounds.height; // count the edges and corners in 2D/3D double sideEdges = 0, cornerEdges = 0; for (int i = 0; i < edge.length; i += 2) { final int x = edge[i + 0] - baseX; final int y = edge[i + 1] - baseY; final int xy = x + (y * width); // count the edges in 4-connectivity int nbEdges = 0; if (x == 0 || !mask[xy - 1]) nbEdges++; // left if (x == width - 1 || !mask[xy + 1]) nbEdges++; // right if (y == 0 || !mask[xy - width]) nbEdges++; // north if (y == height - 1 || !mask[xy + width]) nbEdges++; // south switch (nbEdges) { case 0: break; case 1: // "side" edge sideEdges++; perimeter++; break; case 2: // "corner" edge cornerEdges++; perimeter += Math.sqrt(2); break; case 3: // "salient" point cornerEdges += 2; perimeter += 2 * Math.sqrt(2); break; default: // single pixel, weird, but happens... perimeter++; } } // adjust the perimeter empirically according to the edge distribution double overShoot = Math.min(sideEdges / 10, cornerEdges); return perimeter - overShoot; } /** * Compute intersection with specified mask and return result in a new mask */ public BooleanMask2D getIntersection(BooleanMask2D booleanMask) { return getIntersection(this, booleanMask); } /** * Compute intersection with specified mask and return result in a new mask */ public BooleanMask2D getIntersection(Rectangle bounds, boolean[] mask) { return getIntersection(this.bounds, this.mask, bounds, mask); } /** * @deprecated Use {@link #getIntersection(BooleanMask2D)} instead. */ @Deprecated public BooleanMask2D getIntersect(BooleanMask2D booleanMask) { return getIntersection(booleanMask); } /** * @deprecated Use {@link #getIntersection(Rectangle, boolean[])} instead. */ @Deprecated public BooleanMask2D getIntersect(Rectangle bounds, boolean[] mask) { return getIntersection(bounds, mask); } /** * Compute union with specified mask and return result in a new mask */ public BooleanMask2D getUnion(BooleanMask2D booleanMask) { return getUnion(this, booleanMask); } /** * Compute union with specified mask and return result in a new mask */ public BooleanMask2D getUnion(Rectangle bounds, boolean[] mask) { return getUnion(this.bounds, this.mask, bounds, mask); } /** * Compute exclusive union operation with specified mask and return result in a new mask */ public BooleanMask2D getExclusiveUnion(BooleanMask2D booleanMask) { return getExclusiveUnion(this, booleanMask); } /** * Compute exclusive union operation with specified mask and return result in a new mask */ public BooleanMask2D getExclusiveUnion(Rectangle bounds, boolean[] mask) { return getExclusiveUnion(this.bounds, this.mask, bounds, mask); } /** * Subtract the specified mask from current and return result in a new mask. */ public BooleanMask2D getSubtraction(BooleanMask2D mask) { return getSubtraction(this, mask); } /** * Subtract the specified mask from current and return result in a new mask. */ public BooleanMask2D getSubtraction(Rectangle bounds, boolean[] mask) { return getSubtraction(this.bounds, this.mask, bounds, mask); } /** * @deprecated Use {@link #getExclusiveUnion(BooleanMask2D)} instead. */ @Deprecated public BooleanMask2D getXor(BooleanMask2D booleanMask) { return getExclusiveUnion(booleanMask); } /** * @deprecated Use {@link #getExclusiveUnion(Rectangle, boolean[])} instead. */ @Deprecated public BooleanMask2D getXor(Rectangle bounds, boolean[] mask) { return getExclusiveUnion(bounds, mask); } /** * @deprecated Use {@link #getIntersection(BooleanMask2D)} instead. */ @Deprecated public void intersect(BooleanMask2D booleanMask) { final BooleanMask2D result = getIntersection(booleanMask); bounds = result.bounds; mask = result.mask; } /** * @deprecated Use {@link #getIntersection(Rectangle, boolean[])} instead. */ @Deprecated public void intersect(Rectangle bounds, boolean[] mask) { final BooleanMask2D result = getIntersection(bounds, mask); this.bounds = result.bounds; this.mask = result.mask; } /** * @deprecated Use {@link #getUnion(BooleanMask2D)} instead. */ @Deprecated public void union(BooleanMask2D booleanMask) { union(booleanMask.bounds, booleanMask.mask); } /** * @deprecated Use {@link #getUnion(Rectangle, boolean[])} instead. */ @Deprecated public void union(Rectangle bounds, boolean[] mask) { final BooleanMask2D result = getUnion(bounds, mask); this.bounds = result.bounds; this.mask = result.mask; } /** * @deprecated Use {@link #getExclusiveUnion(BooleanMask2D)} instead. */ @Deprecated public void exclusiveUnion(BooleanMask2D booleanMask) { exclusiveUnion(booleanMask.bounds, booleanMask.mask); } /** * @deprecated Use {@link #getExclusiveUnion(Rectangle, boolean[])} instead. */ @Deprecated public void exclusiveUnion(Rectangle bounds, boolean[] mask) { final BooleanMask2D result = getExclusiveUnion(bounds, mask); this.bounds = result.bounds; this.mask = result.mask; } /** * @deprecated Use {@link #exclusiveUnion(BooleanMask2D)} instead */ @Deprecated public void xor(BooleanMask2D booleanMask) { exclusiveUnion(booleanMask); } /** * @deprecated Use {@link #exclusiveUnion(Rectangle, boolean[])} instead */ @Deprecated public void xor(Rectangle bounds, boolean[] mask) { exclusiveUnion(bounds, mask); } /** * Get the smallest bounds which fit mask content. */ public Rectangle getOptimizedBounds() { // find best bounds final int sizeX = bounds.width; final int sizeY = bounds.height; int minX = sizeX; int minY = sizeY; int maxX = -1; int maxY = -1; int offset = 0; for (int y = 0; y < sizeY; y++) { for (int x = 0; x < sizeX; x++) { if (mask[offset++]) { if (x < minX) minX = x; if (x > maxX) maxX = x; if (y < minY) minY = y; if (y > maxY) maxY = y; } } } // empty --> return empty bounds if (minX == sizeX) return new Rectangle(bounds.x, bounds.y, 0, 0); // new calculated bounds return new Rectangle(bounds.x + minX, bounds.y + minY, (maxX - minX) + 1, (maxY - minY) + 1); } /** * Optimize mask bounds so it fit mask content. */ public void optimizeBounds() { moveBounds(getOptimizedBounds()); } /** * @deprecated Use {@link #moveBounds(Rectangle)} instead. */ @Deprecated public void setBounds(Rectangle value) { moveBounds(value); } /** * Change the bounds of BooleanMask.<br> * Keep mask data intersecting from old bounds. */ public void moveBounds(Rectangle value) { // bounds changed ? if (!bounds.equals(value)) { // copy bounds as we modify them final Rectangle oldBounds = new Rectangle(bounds); final Rectangle newBounds = new Rectangle(value); // replace to origin (relative to old bounds) oldBounds.translate(-bounds.x, -bounds.y); newBounds.translate(-bounds.x, -bounds.y); final boolean[] newMask = new boolean[newBounds.width * newBounds.height]; final Rectangle intersect = newBounds.intersection(oldBounds); if (!intersect.isEmpty()) { int offSrc = 0; int offDst = 0; // adjust offset in source mask if (intersect.x > 0) offSrc += intersect.x; if (intersect.y > 0) offSrc += intersect.y * oldBounds.width; // adjust offset in destination mask if (newBounds.x < 0) offDst += -newBounds.x; if (newBounds.y < 0) offDst += -newBounds.y * newBounds.width; // preserve data for (int j = 0; j < intersect.height; j++) { System.arraycopy(mask, offSrc, newMask, offDst, intersect.width); offSrc += oldBounds.width; offDst += newBounds.width; } } // set new image and maskData mask = newMask; // set new bounds bounds = value; } } @Override public Object clone() { return new BooleanMask2D((Rectangle) bounds.clone(), mask.clone()); } }