View Javadoc

1   /**
2    * Copyright (c) 2011, The University of Southampton and the individual contributors.
3    * All rights reserved.
4    *
5    * Redistribution and use in source and binary forms, with or without modification,
6    * are permitted provided that the following conditions are met:
7    *
8    *   * 	Redistributions of source code must retain the above copyright notice,
9    * 	this list of conditions and the following disclaimer.
10   *
11   *   *	Redistributions in binary form must reproduce the above copyright notice,
12   * 	this list of conditions and the following disclaimer in the documentation
13   * 	and/or other materials provided with the distribution.
14   *
15   *   *	Neither the name of the University of Southampton nor the names of its
16   * 	contributors may be used to endorse or promote products derived from this
17   * 	software without specific prior written permission.
18   *
19   * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
20   * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
21   * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22   * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
23   * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
24   * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
25   * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
26   * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27   * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
28   * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29   */
30  package org.openimaj.workinprogress;
31  
32  import java.io.File;
33  import java.io.IOException;
34  import java.util.ArrayList;
35  import java.util.Collections;
36  import java.util.List;
37  
38  import org.openimaj.citation.annotation.Reference;
39  import org.openimaj.citation.annotation.ReferenceType;
40  import org.openimaj.image.DisplayUtilities;
41  import org.openimaj.image.FImage;
42  import org.openimaj.image.Image;
43  import org.openimaj.image.ImageUtilities;
44  import org.openimaj.image.pixel.FValuePixel;
45  import org.openimaj.image.pixel.Pixel;
46  import org.openimaj.image.processing.convolution.Gaussian2D;
47  import org.openimaj.image.processing.morphology.Erode;
48  import org.openimaj.image.processing.morphology.StructuringElement;
49  import org.openimaj.image.processing.restoration.inpainting.AbstractImageMaskInpainter;
50  import org.openimaj.image.processor.SinglebandImageProcessor;
51  
52  /**
53   * FIXME: Finish implementation (it works but is incredibly slow!)
54   *
55   * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
56   *
57   * @param <IMAGE>
58   *            The type of image that this processor can process
59   */
60  @Reference(
61  		type = ReferenceType.Inproceedings,
62  		author = { "Efros, Alexei A.", "Leung, Thomas K." },
63  		title = "Texture Synthesis by Non-Parametric Sampling",
64  		year = "1999",
65  		booktitle = "Proceedings of the International Conference on Computer Vision-Volume 2 - Volume 2",
66  		pages = { "1033" },
67  		url = "http://dl.acm.org/citation.cfm?id=850924.851569",
68  		publisher = "IEEE Computer Society",
69  		series = "ICCV '99",
70  		customData = {
71  				"isbn", "0-7695-0164-8",
72  				"acmid", "851569",
73  				"address", "Washington, DC, USA"
74  		})
75  public class EfrosLeungInpainter<IMAGE extends Image<?, IMAGE> & SinglebandImageProcessor.Processable<Float, FImage, IMAGE>>
76  		extends
77  		AbstractImageMaskInpainter<IMAGE>
78  {
79  	private static final float SIGMA_DIVISOR = 6.4f;
80  	private static final float ERR_THRESHOLD = 0.1f;
81  	private static final float INITIAL_MAX_ERR_THRESHOLD = 0.3f;
82  
83  	int windowHalfSize;
84  	float sigma;
85  	FImage template;
86  	FImage gaussian;
87  	float templateWeight;
88  
89  	public EfrosLeungInpainter(int windowSize) {
90  		this.windowHalfSize = windowSize / 2;
91  		this.sigma = windowSize / SIGMA_DIVISOR;
92  		this.gaussian = Gaussian2D.createKernelImage(windowSize, sigma);
93  	}
94  
95  	List<FValuePixel> getUnfilledNeighbours() {
96  		final List<FValuePixel> pixels = new ArrayList<FValuePixel>();
97  
98  		final FImage outside = mask.process(new Erode(StructuringElement.CROSS), true);
99  
100 		for (int y = 0; y < mask.height; y++) {
101 			for (int x = 0; x < mask.width; x++) {
102 				final int band = (int) (outside.pixels[y][x] - mask.pixels[y][x]);
103 				if (band != 0) {
104 					final float nc = countValidNeighbours(x, y);
105 					if (nc > 0)
106 						pixels.add(new FValuePixel(x, y, nc));
107 				}
108 			}
109 		}
110 
111 		Collections.shuffle(pixels);
112 		Collections.sort(pixels, FValuePixel.ReverseValueComparator.INSTANCE);
113 
114 		return pixels;
115 	}
116 
117 	private float countValidNeighbours(int x, int y) {
118 		int count = 0;
119 		for (int yy = Math.max(0, y - windowHalfSize); yy < Math.min(mask.height, y + windowHalfSize + 1); yy++)
120 			for (int xx = Math.max(0, x - windowHalfSize); xx < Math.min(mask.width, x + windowHalfSize + 1); xx++)
121 				count += (1 - mask.pixels[yy][xx]);
122 
123 		return count;
124 	}
125 
126 	@Override
127 	protected void performInpainting(IMAGE image) {
128 		if (image instanceof FImage)
129 			performInpainting((FImage) image);
130 	}
131 
132 	protected void performInpainting(FImage image) {
133 		this.template = image.newInstance(windowHalfSize * 2 + 1, windowHalfSize * 2 + 1);
134 		float maxErrThreshold = INITIAL_MAX_ERR_THRESHOLD;
135 
136 		while (true) {
137 			final List<FValuePixel> pixelList = getUnfilledNeighbours();
138 
139 			if (pixelList.size() == 0)
140 				return;
141 
142 			boolean progress = false;
143 			for (final Pixel p : pixelList) {
144 				// template = getNeighborhoodWindow(Pixel);
145 				setTemplate(p.x, p.y, image);
146 				final List<FValuePixel> bestMatches = findMatches(image);
147 				final FValuePixel bestMatch = bestMatches.get((int) (Math.random() * bestMatches.size()));
148 				if (bestMatch.value < maxErrThreshold) {
149 					image.pixels[p.y][p.x] = image.pixels[bestMatch.y][bestMatch.x];
150 					mask.pixels[p.y][p.x] = 0;
151 					progress = true;
152 					DisplayUtilities.displayName(image, "");
153 					System.out.println(p);
154 				}
155 			}
156 
157 			if (!progress)
158 				maxErrThreshold *= 1.1;
159 
160 		}
161 
162 	}
163 
164 	private void setTemplate(int x, int y, FImage image) {
165 		this.templateWeight = 0;
166 		template.fill(Float.MAX_VALUE);
167 		for (int j = 0, yy = y - windowHalfSize; yy < y + windowHalfSize + 1; yy++, j++) {
168 			for (int i = 0, xx = x - windowHalfSize; xx < x + windowHalfSize + 1; xx++, i++) {
169 				if (xx >= 0 && xx < mask.width && yy >= 0 && yy < mask.height &&
170 						mask.pixels[yy][xx] == 0)
171 				{
172 					template.pixels[j][i] = image.pixels[yy][xx];
173 					this.templateWeight += this.gaussian.pixels[j][i];
174 				}
175 			}
176 		}
177 	}
178 
179 	List<FValuePixel> findMatches(FImage image) {
180 		final FImage ssd = new FImage(mask.width, mask.height);
181 
182 		float minSSD = Float.MAX_VALUE;
183 		for (int y = windowHalfSize; y < mask.height - windowHalfSize - 1; y++) {
184 			for (int x = windowHalfSize; x < mask.width - windowHalfSize - 1; x++) {
185 
186 				ssd.pixels[y][x] = 0;
187 				masked: for (int j = -windowHalfSize, jj = 0; j <= windowHalfSize; j++, jj++) {
188 					for (int i = -windowHalfSize, ii = 0; i <= windowHalfSize; i++, ii++) {
189 						final float tpix = template.pixels[jj][ii];
190 						final float ipix = image.pixels[y + j][x + i];
191 
192 						if (mask.pixels[y + j][x + i] == 1) {
193 							ssd.pixels[y][x] = Float.MAX_VALUE;
194 							break masked;
195 						} else if (tpix != Float.MAX_VALUE) {
196 							ssd.pixels[y][x] += ((tpix - ipix) * (tpix - ipix)) * gaussian.pixels[jj][ii];
197 						}
198 					}
199 				}
200 				if (ssd.pixels[y][x] != Float.MAX_VALUE) {
201 					// if (ssd.pixels[y][x] == 0)
202 					// System.out.println("here");
203 					ssd.pixels[y][x] /= this.templateWeight;
204 					minSSD = Math.min(minSSD, ssd.pixels[y][x]);
205 				}
206 			}
207 		}
208 
209 		final float thresh = minSSD * (1 + ERR_THRESHOLD);
210 		final List<FValuePixel> pixelList = new ArrayList<FValuePixel>();
211 		for (int y = windowHalfSize; y < mask.height - windowHalfSize - 1; y++) {
212 			for (int x = windowHalfSize; x < mask.width - windowHalfSize - 1; x++) {
213 				if (ssd.pixels[y][x] != Float.MAX_VALUE && ssd.pixels[y][x] <= thresh)
214 					pixelList.add(new FValuePixel(x, y, ssd.pixels[y][x]));
215 			}
216 		}
217 		return pixelList;
218 	}
219 
220 	public static void main(String[] args) throws IOException {
221 		final EfrosLeungInpainter<FImage> ip = new EfrosLeungInpainter<FImage>(7);
222 		final FImage mask = ImageUtilities.readF(new File("/Users/jsh2/veg.PNG"));
223 		final FImage image = ImageUtilities.readF(new File("/Users/jsh2/veg-masked.png"));
224 
225 		ip.setMask(mask);
226 		ip.processImage(image);
227 
228 		DisplayUtilities.display(image);
229 	}
230 }