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.workinprogress;
031
032import java.io.File;
033import java.io.IOException;
034import java.util.ArrayList;
035import java.util.Collections;
036import java.util.List;
037
038import org.openimaj.citation.annotation.Reference;
039import org.openimaj.citation.annotation.ReferenceType;
040import org.openimaj.image.DisplayUtilities;
041import org.openimaj.image.FImage;
042import org.openimaj.image.Image;
043import org.openimaj.image.ImageUtilities;
044import org.openimaj.image.pixel.FValuePixel;
045import org.openimaj.image.pixel.Pixel;
046import org.openimaj.image.processing.convolution.Gaussian2D;
047import org.openimaj.image.processing.morphology.Erode;
048import org.openimaj.image.processing.morphology.StructuringElement;
049import org.openimaj.image.processing.restoration.inpainting.AbstractImageMaskInpainter;
050import org.openimaj.image.processor.SinglebandImageProcessor;
051
052/**
053 * FIXME: Finish implementation (it works but is incredibly slow!)
054 *
055 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
056 *
057 * @param <IMAGE>
058 *            The type of image that this processor can process
059 */
060@Reference(
061                type = ReferenceType.Inproceedings,
062                author = { "Efros, Alexei A.", "Leung, Thomas K." },
063                title = "Texture Synthesis by Non-Parametric Sampling",
064                year = "1999",
065                booktitle = "Proceedings of the International Conference on Computer Vision-Volume 2 - Volume 2",
066                pages = { "1033" },
067                url = "http://dl.acm.org/citation.cfm?id=850924.851569",
068                publisher = "IEEE Computer Society",
069                series = "ICCV '99",
070                customData = {
071                                "isbn", "0-7695-0164-8",
072                                "acmid", "851569",
073                                "address", "Washington, DC, USA"
074                })
075public class EfrosLeungInpainter<IMAGE extends Image<?, IMAGE> & SinglebandImageProcessor.Processable<Float, FImage, IMAGE>>
076                extends
077                AbstractImageMaskInpainter<IMAGE>
078{
079        private static final float SIGMA_DIVISOR = 6.4f;
080        private static final float ERR_THRESHOLD = 0.1f;
081        private static final float INITIAL_MAX_ERR_THRESHOLD = 0.3f;
082
083        int windowHalfSize;
084        float sigma;
085        FImage template;
086        FImage gaussian;
087        float templateWeight;
088
089        public EfrosLeungInpainter(int windowSize) {
090                this.windowHalfSize = windowSize / 2;
091                this.sigma = windowSize / SIGMA_DIVISOR;
092                this.gaussian = Gaussian2D.createKernelImage(windowSize, sigma);
093        }
094
095        List<FValuePixel> getUnfilledNeighbours() {
096                final List<FValuePixel> pixels = new ArrayList<FValuePixel>();
097
098                final FImage outside = mask.process(new Erode(StructuringElement.CROSS), true);
099
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}