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 Ch08_Binary_Regions; 010 011import ij.IJ; 012import ij.ImagePlus; 013import ij.gui.GenericDialog; 014import ij.plugin.PlugIn; 015import ij.process.ByteProcessor; 016import ij.process.ColorProcessor; 017import imagingbook.common.color.iterate.ColorSequencer; 018import imagingbook.common.color.iterate.FiniteLinearColorSequencer; 019import imagingbook.common.geometry.basic.Pnt2d; 020import imagingbook.common.geometry.moments.FlusserMoments; 021import imagingbook.common.ij.overlay.ShapeOverlayAdapter; 022import imagingbook.common.math.MahalanobisDistance; 023import imagingbook.common.math.Matrix; 024import imagingbook.common.regions.BinaryRegion; 025import imagingbook.common.regions.BinaryRegionSegmentation; 026import imagingbook.common.regions.RegionContourSegmentation; 027import imagingbook.common.util.GenericProperties.PropertyKey; 028import imagingbook.common.util.tuples.Tuple2; 029import imagingbook.core.jdoc.JavaDocHelp; 030import imagingbook.core.resource.ImageResource; 031import imagingbook.sampleimages.kimia.Kimia1070; 032import imagingbook.sampleimages.kimia.KimiaCollage; 033 034import java.awt.Color; 035import java.awt.Font; 036import java.util.ArrayList; 037import java.util.Comparator; 038import java.util.List; 039 040/** 041 * <p> 042 * This ImageJ plugin demonstrates the use of complex invariant Flusser moments for 2D shape matching. It opens a 043 * special binary input image (collage of shapes), where the top row are the reference shapes. They are assigned 044 * different colors. All other shapes are compared to the reference shapes and colored with the color of the most 045 * similar reference shape. See Sec. 8.6.5 of [1] for additional details. 046 * </p> 047 * <p> 048 * The plugin offers two options for finding the "closest" reference moment vector for a given shape: 049 * <br> 050 * (a) Mahalonobis distance (MD, see Eq. 8.57 and Sec. G.3 of [1]): The MD is calculated from the (pre-calculated) 051 * covariance matrix of the moment vectors of the entire 'Kimia1070' dataset to obtain representative statistical shape 052 * parameters. The MD compensates the large magnitude variation between the 11 moment space dimensions. 053 * <br> 054 * (b) Euclidean distance (ED): Here the distance between moment vectors is measured using the ED. The large-magnitude 055 * moment elements obviously dominate this quantity. Typically only the 3-4 largest moments are actually used, all 056 * others have no effect. Thus results with the ED are inferior to the ones obtained with the MD. 057 * <br> 058 * In both cases matching is performed linearly, i.e., a given moment vector is simply compared to all reference 059 * vectors. 060 * </p> 061 * <p> 062 * [1] W. Burger, M.J. Burge, <em>Digital Image Processing – An Algorithmic Introduction</em>, 3rd ed, Springer 063 * (2022). 064 * </p> 065 * 066 * @author WB 067 * @version 2023/01/02 068 * @see Flusser_Moments_Covariance_Matrix 069 */ 070public class Flusser_Moments_Matching_Demo implements PlugIn, JavaDocHelp { 071 072 private static final ImageResource ir = KimiaCollage.ShapeCollage1; 073 private static final int ReferenceBoundaryY = 130; // everything above this position is a reference shape 074 075 private static int MinRegionSize = 100; 076 private static boolean UseMahalanobisDistance = true; 077 private static double MaxMomentDistance = 1.0; 078 079 private static final int FontSize = 20; 080 private static final Color UnmatchedColor = Color.gray; 081 private static final Color[] ReferenceShapeColors = {Color.yellow, Color.green, Color.cyan, Color.magenta, Color.pink}; 082 private static final Font MarkerFont = new Font(Font.SANS_SERIF, Font.BOLD, 14); 083 private static final Color MarkerColor = Color.white; 084 085 private static final PropertyKey<double[]> MomentKey = new PropertyKey<>("mts"); 086 private static final PropertyKey<String> LabelKey = new PropertyKey<>("lbl"); 087 088 private MahalanobisDistance md; // new MahalanobisDistance(cov); 089 private double[][] U; // md.getWhiteningTransformation(); 090 091 @Override 092 public void run(String str) { 093 ImagePlus im = ir.getImagePlus(); 094 im.show(); 095 if (!runDialog()) { 096 return; 097 } 098 099 // segment the image into binary regions 100 ByteProcessor ip = (ByteProcessor) im.getProcessor(); 101 BinaryRegionSegmentation segmenter = new RegionContourSegmentation((ByteProcessor) ip); 102 List<BinaryRegion> regions = segmenter.getRegions(true); 103 if (regions.isEmpty()) { 104 IJ.log("No regions found!"); 105 return; 106 } 107 108 // calculate invariant moment for all regions 109 // and split into reference/other shapes 110 List<BinaryRegion> refShapes = new ArrayList<BinaryRegion>(); 111 List<BinaryRegion> othShapes = new ArrayList<BinaryRegion>(); 112 for (BinaryRegion r : regions) { 113 if (r.getSize() > MinRegionSize) { 114 // calculate invariant Flusser moments for region r 115 double[] moments = new FlusserMoments(r).getInvariantMoments(); 116 r.setProperty(MomentKey, moments); 117 if (r.getCenter().getY() < ReferenceBoundaryY) 118 refShapes.add(r); 119 else 120 othShapes.add(r); 121 } 122 } 123 124 // sort reference shapes by center x-coordinates and assign labels: 125 refShapes.sort(Comparator.comparingDouble(r -> r.getCenter().getX())); 126 { 127 int k = 0; 128 for (BinaryRegion r : refShapes) { 129 r.setProperty(LabelKey, "R" + k); 130 k++; 131 } 132 } 133 134 // sort other shapes by center y-coordinates and assign labels: 135 othShapes.sort(Comparator.comparingDouble(r -> r.getCenter().getY())); 136 { 137 int k = 0; 138 for (BinaryRegion s : othShapes) { 139 s.setProperty(LabelKey, "S" + k); 140 k++; 141 } 142 } 143 144 if (UseMahalanobisDistance) { 145 // Matrix.fromLongBits(Kimia1070.covarianceRegionBits); 146 double[][] cov = Matrix.fromLongBits(Kimia1070.covarianceRegionBits); 147 md = new MahalanobisDistance(cov); 148 // U = md.getWhiteningTransformation(); 149 } 150 151 // ----- perform matching and create output image ------- 152 153 ColorProcessor cp = new ColorProcessor(ip.getWidth(), ip.getHeight()); 154 ShapeOverlayAdapter ola = new ShapeOverlayAdapter(); 155 ola.setFont(MarkerFont); 156 ola.setTextColor(MarkerColor); 157 ColorSequencer randomColor = new FiniteLinearColorSequencer(ReferenceShapeColors); 158 159 // process reference shapes 160 Color[] refColors = new Color[refShapes.size()]; 161 double[][] refMoments = new double[refShapes.size()][]; 162 { 163 int k = 0; 164 for (BinaryRegion r : refShapes) { 165 refMoments[k] = r.getProperty(MomentKey); 166 refColors[k] = randomColor.next(); 167 paintRegion(r, cp, refColors[k]); 168 markRegion(r, ola, r.getProperty(LabelKey)); 169 k++; 170 } 171 } 172 173 // process other shapes 174 for (BinaryRegion s : othShapes) { 175 double[] moments = s.getProperty(MomentKey); 176 // find best-matching reference shape 177 Tuple2<Integer, Double> match = (UseMahalanobisDistance) ? 178 findBestMatchMahalanobis(moments, refMoments) : 179 findBestMatchEuclidean(moments, refMoments); 180 int k = match.get0(); 181 double dist = match.get1(); 182 Color col = (dist <= MaxMomentDistance) ? refColors[k] : UnmatchedColor; 183 paintRegion(s, cp, col); 184 markRegion(s, ola, s.getProperty(LabelKey)); 185 } 186 187 ImagePlus imResult = new ImagePlus("Matched Regions", cp); 188 imResult.setOverlay(ola.getOverlay()); 189 imResult.show(); 190 } 191 192 /** 193 * Finds the reference moment vector closest to the given sample moment vector and returns the associated index (k) 194 * and distance (d). 195 * 196 * @param moments a sample moment vector 197 * @param refMoments an array of reference moment vectors 198 * @return a pair (k, d) consisting of reference index k and min. vector distance d 199 */ 200 private Tuple2<Integer, Double> findBestMatchEuclidean(double[] moments, double[][] refMoments) { 201 int iMin = -1; 202 double dMin = Double.POSITIVE_INFINITY; 203 for (int i = 0; i < refMoments.length; i++) { 204 double d = Matrix.distL2(moments, refMoments[i]); // Euclidean distance 205 if (d < dMin) { 206 dMin = d; 207 iMin = i; 208 } 209 } 210 return new Tuple2<>(iMin, dMin); 211 } 212 213 private Tuple2<Integer, Double> findBestMatchMahalanobis(double[] moments, double[][] refMoments) { 214 int iMin = -1; 215 double dMin = Double.POSITIVE_INFINITY; 216 for (int i = 0; i < refMoments.length; i++) { 217 double d = md.distance(moments, refMoments[i]); // Euclidean distance 218 if (d < dMin) { 219 dMin = d; 220 iMin = i; 221 } 222 } 223 return new Tuple2<>(iMin, dMin); 224 } 225 226 private void markRegion(BinaryRegion r, ShapeOverlayAdapter ola, String s) { 227 Pnt2d c = r.getCenter(); 228 ola.addText(c.getX(), c.getY(), s); 229 } 230 231 private void paintRegion(BinaryRegion r, ColorProcessor cp, Color col) { 232 cp.setColor(col); 233 for (Pnt2d p : r) { 234 cp.drawDot(p.getXint(), p.getYint()); 235 } 236 } 237 238 // ---------------------------------------------------------------------- 239 240 private boolean runDialog() { 241 GenericDialog gd = new GenericDialog(this.getClass().getSimpleName()); 242 gd.addHelp(getJavaDocUrl()); 243 gd.addNumericField("Minimum region size", MinRegionSize, 0); 244 gd.addNumericField("Uax. moment vector distance", MaxMomentDistance, 3); 245 gd.addCheckbox("Use Mahalanobis distance", UseMahalanobisDistance); 246 247 gd.showDialog(); 248 if (gd.wasCanceled()) { 249 return false; 250 } 251 252 MinRegionSize = (int) gd.getNextNumber(); 253 MaxMomentDistance = gd.getNextNumber(); 254 UseMahalanobisDistance = gd.getNextBoolean(); 255 return true; 256 } 257 258} 259