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 ******************************************************************************/ 009 010package imagingbook.common.image.matching; 011import ij.process.ByteProcessor; 012import imagingbook.common.geometry.basic.Pnt2d.PntInt; 013 014import java.util.ArrayList; 015import java.util.List; 016 017/** 018 * <p> 019 * Instances of this class perform "chamfer" matching on binary images. The "search" image I (to be searched for matches 020 * of the "reference" image R) is linked to this {@link ChamferMatcher} instance. The associated distance transformation 021 * of the search image I is pre-calculated during construction. The assumption is, that the search image I is fixed and 022 * the {@link ChamferMatcher} tries to match multiple reference images R. All images are considered binary, with 023 * non-zero values taken as foreground pixels. See Sec. 23.2.3 (Alg. 23.3) of [1] for additional details. 024 * </p> 025 * <p> 026 * [1] W. Burger, M.J. Burge, <em>Digital Image Processing – An Algorithmic Introduction</em>, 3rd ed, Springer 027 * (2022). 028 * </p> 029 * 030 * @author WB 031 * @version 2022/12/14 032 */ 033public class ChamferMatcher { 034 035 private final int wI, hI; // dimensions of the search image 036 private final float[][] DI; // distance transform of I 037 038 /** 039 * Constructor using the default distance norm (L2). The supplied image must be binary with zero background values. 040 * @param I the binary "search" image (to be searched for matches of the "reference" image) 041 */ 042 public ChamferMatcher(ByteProcessor I) { 043 this(I, DistanceTransform.DistanceType.L2); 044 } 045 046 /** 047 * Constructor using the specified distance norm. The supplied image must be binary with zero background values. 048 * @param I the binary "search" image (to be searched for matches of the "reference" image) 049 * @param norm the distance norm 050 */ 051 public ChamferMatcher(ByteProcessor I, DistanceTransform.DistanceType norm) { 052 this.wI = I.getWidth(); 053 this.hI = I.getHeight(); 054 this.DI = (new DistanceTransform(I, norm)).getDistanceMap(); 055 } 056 057 /** 058 * Calculates the match function for specified reference image R to this matcher's search image I (defined 059 * by the constructor). The returned function Q[r][s] is the match score for reference image R positioned 060 * at (r,s) in the search image coordinate frame. 061 * 062 * @param R a binary reference image 063 * @return a 2D array Q[r][s] of match scores 064 */ 065 public float[][] getMatch(ByteProcessor R) { 066 PntInt[] pR = collectForegroundPoints(R); 067 return getMatch(pR, R.getWidth(), R.getHeight()); 068 } 069 070 // Collect all foreground pixel coordinates of R into a point array. 071 private PntInt[] collectForegroundPoints(ByteProcessor R) { 072 final int w = R.getWidth(); 073 final int h = R.getHeight(); 074 List<PntInt> pntList = new ArrayList<>(); 075 for (int i = 0; i < w; i++) { 076 for (int j = 0; j < h; j++) { 077 if (R.get(i, j) != 0) { // foreground pixel in reference image 078 pntList.add(PntInt.from(i, j)); 079 } 080 } 081 } 082 return pntList.toArray(new PntInt[0]); 083 } 084 085 // ------------------------------------------------------------ 086 087 /** 088 * Matches the specified point set to the (fixed) search image I. The points represent the foreground pixels of a 089 * virtual reference image (R) with the specified width and height. 090 * 091 * @param pR a set of foreground points representing the reference image R 092 * @param wR the width of the reference image 093 * @param hR the height of the reference image 094 * @return a 2D array Q[r][s] of match scores 095 */ 096 public float[][] getMatch(PntInt[] pR, int wR, int hR) { 097 final float[][] Q = new float[wI - wR + 1][hI - hR + 1]; 098 for (int r = 0; r < Q.length; r++) { 099 for (int s = 0; s < Q[r].length; s++) { 100 Q[r][s] = getMatchScore(pR, r, s); 101 } 102 } 103 return Q; 104 } 105 106 // Calculates the match score for a single position (r,s). 107 private float getMatchScore(PntInt[] pR, int r, int s) { 108 float q = 0.0f; 109 for (PntInt p : pR) { 110 final int u = r + p.x; 111 final int v = s + p.y; 112 if (0 <= u && u < DI.length && 0 <= v && v < DI[u].length) { 113 q = q + DI[u][v]; 114 } 115 } 116 return q; 117 } 118 119}