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.restoration.inpainting; 031 032import java.util.PriorityQueue; 033 034import org.openimaj.citation.annotation.Reference; 035import org.openimaj.citation.annotation.ReferenceType; 036import org.openimaj.citation.annotation.References; 037import org.openimaj.image.FImage; 038import org.openimaj.image.Image; 039import org.openimaj.image.pixel.FValuePixel; 040import org.openimaj.image.processing.morphology.Dilate; 041import org.openimaj.image.processing.morphology.StructuringElement; 042import org.openimaj.image.processor.SinglebandImageProcessor; 043 044/** 045 * Abstract base class for inpainting algorithms based on the Fast Marching 046 * Method (FMM) for selecting the order of pixels to paint. 047 * <p> 048 * FMM is used for computing the evolution of boundary moving in a direction 049 * <i>normal</i> to itself. Formally, FMM approximates the solution to the <a 050 * href="http://en.wikipedia.org/wiki/Eikonal_equation">Eikonal function</a> 051 * using an <a href="http://en.wikipedia.org/wiki/Upwind_scheme">upwind 052 * scheme<a>. 053 * <p> 054 * The core algorithm implemented by the {@link #performInpainting(Image)} 055 * method follows these steps: 056 * <ul> 057 * <li>Extract the pixel with the smallest distance value (t) in the BAND 058 * pixels.</li> 059 * <li>Update its flag value as KNOWN.</li> 060 * <li>March the boundary inwards by adding new points.</li> 061 * <ul> 062 * <li>If they are either UNKNOWN or BAND, compute its t value using the Eikonal 063 * function for all the 4 quadrants.</li> 064 * <li>If flag is UNKNOWN:</li> 065 * <ul> 066 * <li>Change it to BAND.</li> 067 * <li>Inpaint the pixel.</li> 068 * </ul> 069 * <li>Select the min value and assign it as the t value of the pixel.</li> 070 * <li>Insert this new value in the heap.</li> </ul> </ul> 071 * <p> 072 * The {@link #inpaint(int, int, Image)} method must be implemented by 073 * subclasses to actually perform the inpainting operation 074 * 075 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk) 076 * 077 * @param <IMAGE> 078 * The type of image that this processor can process 079 */ 080@References(references = { 081 @Reference( 082 type = ReferenceType.Article, 083 author = { "Telea, Alexandru" }, 084 title = "An Image Inpainting Technique Based on the Fast Marching Method.", 085 year = "2004", 086 journal = "J. Graphics, GPU, & Game Tools", 087 pages = { "23", "34" }, 088 url = "http://dblp.uni-trier.de/db/journals/jgtools/jgtools9.html#Telea04", 089 number = "1", 090 volume = "9", 091 customData = { 092 "biburl", "http://www.bibsonomy.org/bibtex/2b0bf54e265d011a8e1fe256e6fcf556b/dblp", 093 "ee", "http://dx.doi.org/10.1080/10867651.2004.10487596", 094 "keywords", "dblp" 095 } 096 ), 097 @Reference( 098 type = ReferenceType.Inproceedings, 099 author = { "J. A. Sethian" }, 100 title = "A Fast Marching Level Set Method for Monotonically Advancing Fronts", 101 year = "1995", 102 booktitle = "Proc. Nat. Acad. Sci", 103 pages = { "1591", "", "1595" } 104 ) 105}) 106@SuppressWarnings("javadoc") 107public abstract class AbstractFMMInpainter<IMAGE extends Image<?, IMAGE> & SinglebandImageProcessor.Processable<Float, FImage, IMAGE>> 108 extends 109 AbstractImageMaskInpainter<IMAGE> 110{ 111 private static final int[][] DELTAS = new int[][] { { 0, -1 }, { -1, 0 }, { 0, 1 }, { 1, 0 } }; 112 113 /** 114 * Flag for pixels with a known value 115 */ 116 protected static byte KNOWN = 0; 117 118 /** 119 * Flag for pixels on the boundary 120 */ 121 protected static byte BAND = 1; 122 123 /** 124 * Flag for pixels with an unknown value 125 */ 126 protected static byte UNKNOWN = 2; 127 128 /** 129 * The working flag image 130 */ 131 protected byte[][] flag; 132 133 /** 134 * The space-time map (T) 135 */ 136 protected FImage timeMap; 137 138 /** 139 * The working heap of pixels to process next 140 */ 141 protected PriorityQueue<FValuePixel> heap; 142 143 @Override 144 protected void initMask() { 145 final FImage outside = mask.process(new Dilate(StructuringElement.CROSS), true); 146 147 flag = new byte[mask.height][mask.width]; 148 timeMap = new FImage(outside.width, outside.height); 149 150 heap = new PriorityQueue<FValuePixel>(10, FValuePixel.ValueComparator.INSTANCE); 151 152 for (int y = 0; y < mask.height; y++) { 153 for (int x = 0; x < mask.width; x++) { 154 final int band = (int) (outside.pixels[y][x] - mask.pixels[y][x]); 155 flag[y][x] = (byte) ((2 * outside.pixels[y][x]) - band); 156 157 if (flag[y][x] == UNKNOWN) 158 timeMap.pixels[y][x] = Float.MAX_VALUE; 159 160 if (band != 0) { 161 heap.add(new FValuePixel(x, y, timeMap.pixels[y][x])); 162 } 163 } 164 } 165 } 166 167 /** 168 * Solve a step of the Eikonal equation. 169 * 170 * @param x1 171 * x-position of first pixel (diagonally adjacent to the second) 172 * @param y1 173 * y-position of first pixel (diagonally adjacent to the second) 174 * @param x2 175 * x-position of second pixel (diagonally adjacent to the first) 176 * @param y2 177 * y-position of second pixel (diagonally adjacent to the first) 178 * @return the time/distance value of the pixel at (x2, y1) 179 */ 180 protected float solveEikonalStep(int x1, int y1, int x2, int y2) 181 { 182 float soln = Float.MAX_VALUE; 183 184 final float t1 = timeMap.pixels[y1][x1]; 185 final float t2 = timeMap.pixels[y2][x2]; 186 187 if (flag[y1][x1] == KNOWN) { 188 if (flag[y2][x2] == KNOWN) { 189 final float r = (float) Math.sqrt(2 - (t1 - t2) * (t1 - t2)); 190 float s = (t1 + t2 - r) * 0.5f; 191 192 if (s >= t1 && s >= t2) { 193 soln = s; 194 } else { 195 s += r; 196 197 if (s >= t1 && s >= t2) { 198 soln = s; 199 } 200 } 201 } else { 202 soln = 1 + t1; 203 } 204 } else if (flag[y2][x2] == KNOWN) { 205 soln = 1 + t2; 206 } 207 208 return soln; 209 } 210 211 @Override 212 public void performInpainting(IMAGE image) { 213 final int width = image.getWidth(); 214 final int height = image.getHeight(); 215 216 while (!heap.isEmpty()) { 217 final FValuePixel pix = heap.poll(); 218 final int x = pix.x; 219 final int y = pix.y; 220 flag[y][x] = KNOWN; 221 222 if ((x <= 1) || (y <= 1) || (x >= width - 2) || (y >= height - 2)) 223 continue; 224 225 for (final int[] p : DELTAS) { 226 final int xp = p[0] + x, yp = p[1] + y; 227 228 if (flag[yp][xp] != KNOWN) { 229 timeMap.pixels[yp][xp] = Math.min(Math.min(Math.min( 230 solveEikonalStep(xp - 1, yp, xp, yp - 1), 231 solveEikonalStep(xp + 1, yp, xp, yp - 1)), 232 solveEikonalStep(xp - 1, yp, xp, yp + 1)), 233 solveEikonalStep(xp + 1, yp, xp, yp + 1)); 234 235 if (flag[yp][xp] == UNKNOWN) { 236 flag[yp][xp] = BAND; 237 238 heap.offer(new FValuePixel(xp, yp, timeMap.pixels[yp][xp])); 239 240 inpaint(xp, yp, image); 241 } 242 } 243 } 244 } 245 } 246 247 /** 248 * Inpaint the specified pixel of the given image. 249 * 250 * @param x 251 * the x-ordinate of the pixel to paint 252 * @param y 253 * the y-ordinate of the pixel to paint 254 * @param image 255 * the image 256 */ 257 protected abstract void inpaint(int x, int y, IMAGE image); 258}