{"worksheets": [{"cells": [{"cell_type": "markdown", "metadata": {}, "source": ["Texture Synthesis and Inpainting using Patch Projections", "========================================================", "", "*Important:* Please read the [installation page](http://gpeyre.github.io/numerical-tours/installation_python/) for details about how to install the toolboxes.", "$\\newcommand{\\dotp}[2]{\\langle #1, #2 \\rangle}$", "$\\newcommand{\\enscond}[2]{\\lbrace #1, #2 \\rbrace}$", "$\\newcommand{\\pd}[2]{ \\frac{ \\partial #1}{\\partial #2} }$", "$\\newcommand{\\umin}[1]{\\underset{#1}{\\min}\\;}$", "$\\newcommand{\\umax}[1]{\\underset{#1}{\\max}\\;}$", "$\\newcommand{\\umin}[1]{\\underset{#1}{\\min}\\;}$", "$\\newcommand{\\uargmin}[1]{\\underset{#1}{argmin}\\;}$", "$\\newcommand{\\norm}[1]{\\|#1\\|}$", "$\\newcommand{\\abs}[1]{\\left|#1\\right|}$", "$\\newcommand{\\choice}[1]{ \\left\\{  \\begin{array}{l} #1 \\end{array} \\right. }$", "$\\newcommand{\\pa}[1]{\\left(#1\\right)}$", "$\\newcommand{\\diag}[1]{{diag}\\left( #1 \\right)}$", "$\\newcommand{\\qandq}{\\quad\\text{and}\\quad}$", "$\\newcommand{\\qwhereq}{\\quad\\text{where}\\quad}$", "$\\newcommand{\\qifq}{ \\quad \\text{if} \\quad }$", "$\\newcommand{\\qarrq}{ \\quad \\Longrightarrow \\quad }$", "$\\newcommand{\\ZZ}{\\mathbb{Z}}$", "$\\newcommand{\\CC}{\\mathbb{C}}$", "$\\newcommand{\\RR}{\\mathbb{R}}$", "$\\newcommand{\\EE}{\\mathbb{E}}$", "$\\newcommand{\\Zz}{\\mathcal{Z}}$", "$\\newcommand{\\Ww}{\\mathcal{W}}$", "$\\newcommand{\\Vv}{\\mathcal{V}}$", "$\\newcommand{\\Nn}{\\mathcal{N}}$", "$\\newcommand{\\NN}{\\mathcal{N}}$", "$\\newcommand{\\Hh}{\\mathcal{H}}$", "$\\newcommand{\\Bb}{\\mathcal{B}}$", "$\\newcommand{\\Ee}{\\mathcal{E}}$", "$\\newcommand{\\Cc}{\\mathcal{C}}$", "$\\newcommand{\\Gg}{\\mathcal{G}}$", "$\\newcommand{\\Ss}{\\mathcal{S}}$", "$\\newcommand{\\Pp}{\\mathcal{P}}$", "$\\newcommand{\\Ff}{\\mathcal{F}}$", "$\\newcommand{\\Xx}{\\mathcal{X}}$", "$\\newcommand{\\Mm}{\\mathcal{M}}$", "$\\newcommand{\\Ii}{\\mathcal{I}}$", "$\\newcommand{\\Dd}{\\mathcal{D}}$", "$\\newcommand{\\Ll}{\\mathcal{L}}$", "$\\newcommand{\\Tt}{\\mathcal{T}}$", "$\\newcommand{\\si}{\\sigma}$", "$\\newcommand{\\al}{\\alpha}$", "$\\newcommand{\\la}{\\lambda}$", "$\\newcommand{\\ga}{\\gamma}$", "$\\newcommand{\\Ga}{\\Gamma}$", "$\\newcommand{\\La}{\\Lambda}$", "$\\newcommand{\\si}{\\sigma}$", "$\\newcommand{\\Si}{\\Sigma}$", "$\\newcommand{\\be}{\\beta}$", "$\\newcommand{\\de}{\\delta}$", "$\\newcommand{\\De}{\\Delta}$", "$\\newcommand{\\phi}{\\varphi}$", "$\\newcommand{\\th}{\\theta}$", "$\\newcommand{\\om}{\\omega}$", "$\\newcommand{\\Om}{\\Omega}$"]}, {"cell_type": "markdown", "metadata": {}, "source": ["This numerical tour explores texture synthesis and inpainting using patch", "averaging."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["from __future__ import division", "import nt_toolbox as nt", "from nt_solutions import graphics_6_patches as solutions", "%matplotlib inline", "%load_ext autoreload", "%autoreload 2"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Creating a Dictionary of Patches", "--------------------------------", "Given an exemplar image, we extract many patch that are our library. We", "even perform PCA dimensionality reduction to speed up nearest neighbors", "search.", "", "", "The main parameter is the width of the patches."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["w = 5"]}, {"cell_type": "markdown", "metadata": {}, "source": ["The other parameter is the number of patch in the exemplar dictionary."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["q = 1000"]}, {"cell_type": "markdown", "metadata": {}, "source": ["We load an exemplar image."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["name = 'corral'", "n = 128", "M0 = load_image(name, n)", "M0 = rescale(crop(M0, n))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["We set up larges |(w,w,n-w+1,n-w+1)| matrices representing the X and Y", "position of the pixel to extract."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["p = n-w + 1"]}, {"cell_type": "markdown", "metadata": {}, "source": ["location of pixels"]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["[Y, X] = meshgrid(1: p, 1: p)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["offsets"]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["[dY, dX] = meshgrid(0: w-1, 0: w-1)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["location of pixels to extract"]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["X = reshape(X, [1 1 p p])", "Y = reshape(Y, [1 1 p p])", "X = repmat(X, [w w 1 1]) + repmat(dX, [1 1 p p])", "Y = repmat(Y, [w w 1 1]) + repmat(dY, [1 1 p p])"]}, {"cell_type": "markdown", "metadata": {}, "source": ["We extract all the patches and reshape the matrix of patch so that", "|P(:,:,i)| is a patch"]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["P0 = M0(X + (Y-1)*n)", "P0 = reshape(P0, w, w, p*p)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Sub-sample the patches"]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["sel = randperm(size(P0, 3)); sel = sel(1: q)", "P0 = P0(: , : , sel)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Image Patch-wise Projection", "---------------------------", "The basic step for synthesis or inpainting is to project each patch of an", "image to its nearest neighbor in the dictionary.", "", "", "The initial image is just noise for instance."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["n = 128", "M = rand(n)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["We define an offset vector to shift the projected patch. This needs to be", "changed during the iteration of the algorithm (either synthesis or", "inpainting)."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["ofx = 2", "ofy = 1"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Patch locations."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["[Y, X] = meshgrid(1: w: n, 1: w: n)", "p = size(X, 1)", "[dY, dX] = meshgrid(0: w-1, 0: w-1)", "X = reshape(X, [1 1 p p])", "Y = reshape(Y, [1 1 p p])", "X = repmat(X, [w w 1 1]) + repmat(dX, [1 1 p p])", "Y = repmat(Y, [w w 1 1]) + repmat(dY, [1 1 p p])"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Shift location, with proper boundary condition (cyclic)."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["Xs = mod(X + ofx-1, n) + 1", "Ys = mod(Y + ofy-1, n) + 1"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Extract the patches."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["P = M(Xs + (Ys-1)*n)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Replace each patch by its closest match."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["for i in 1: p*p:", "    % distance to current patch", "    d = sum(sum((P0 - repmat(P(: , : , i), [1 1 q])).^2))", "    % best match", "    [tmp, s] = min(d)", "    % replace the patch", "    P(: , : , i) = P0(: , : , s)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Reconstruct the image."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["Mp = M", "Mp(Xs + (Ys-1)*n) = P"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Display."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["imageplot(M, 'Input', 1, 2, 1)", "imageplot(Mp, 'Projected', 1, 2, 2)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Texture Synthesis", "-----------------", "Texture synthesis is obtained by performing the projection for several", "offset and averaging the results.", "", "", "To speed up performance, we consider only a subset of all possible |w*w|", "offsets."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["noffs = 10"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Compute a randomized list of offsets"]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["sel = randperm(w*w); sel = sel(1: noffs)", "OffX = dX(sel); OffY = dY(sel)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["We perform one step of synthesis by cycling through the offset."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["M1 = zeros(n)", "for j in 1: noffs:", "    ofx = OffX(j)", "    ofy = OffY(j)", "    % shift locations", "    Xs = mod(X + ofx-1, n) + 1", "    Ys = mod(Y + ofy-1, n) + 1", "    % extract patch", "    P = M(Xs + (Ys-1)*n)", "    % replace by closest patch", "for i in 1: p*p:", "        d = sum(sum((P0 - repmat(P(: , : , i), [1 1 q])).^2))", "        [tmp, s] = min(d)", "        P(: , : , i) = P0(: , : , s)", "", "    % reconstruct the image.", "    M1(Xs + (Ys-1)*n) = M1(Xs + (Ys-1)*n) + P", "", "M1 = M1 / noffs"]}, {"cell_type": "markdown", "metadata": {}, "source": ["To enhance the synthesis result, we perform histogram equalization."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["M1 = perform_hist_eq(M1, M0)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Display the result."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["imageplot(M, 'Input', 1, 2, 1)", "imageplot(M1, 'Projected', 1, 2, 2)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["__Exercise 1__", "", "Perform several step of synthesis."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["solutions.exo1()"]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["## Insert your code here."]}, {"cell_type": "markdown", "metadata": {}, "source": ["Display the results."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["imageplot(M0, 'Exemplar', 1, 2, 1)", "imageplot(M, 'Synthesized', 1, 2, 2)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["__Exercise 2__", "", "Perform more iteration, and increase the value of |q| and |noffs|."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["solutions.exo2()"]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["## Insert your code here."]}, {"cell_type": "markdown", "metadata": {}, "source": ["__Exercise 3__", "", "Explore the influence of the parameters |w| and |q| on the quality of", "the synthesis."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["solutions.exo3()"]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["## Insert your code here."]}, {"cell_type": "markdown", "metadata": {}, "source": ["__Exercise 4__", "", "Perform the synthesis using different textures."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["solutions.exo4()"]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["## Insert your code here."]}, {"cell_type": "markdown", "metadata": {}, "source": ["__Exercise 5__", "", "Extend the algorithm to handle color textures."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["solutions.exo5()"]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["## Insert your code here."]}, {"cell_type": "markdown", "metadata": {}, "source": ["Texture Inpainting", "------------------", "Texture inpainting corresponds to filling in large hole in an image. It", "It corresponds to a constraints synthesis inside the area of the hole.", "", "", "Load a texture."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["name = 'hair'", "n = 128", "Ma = load_image(name)", "Ma = rescale(crop(Ma, n))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Compute a binary mask representing holes in the textures.", "", "size of the holes"]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["h = 9"]}, {"cell_type": "markdown", "metadata": {}, "source": ["number of holes"]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["nh = 20", "mask = zeros(n)", "[V, U] = meshgrid(1: n, 1: n)", "for i in 1: nh:", "    % location of the hole", "    x = floor(rand(2, 1)*(n-1)) + 1", "    d = (U-x(1)).^2 + (V-x(2)).^2", "    mask(d <= h^2) = 1"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Create holes."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["M0 = Ma", "M0(mask = =1) = 0"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Display with / without holes."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["imageplot(Ma, 'Original', 1, 2, 1)", "imageplot(M0, 'To inpaint', 1, 2, 2)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Collect all the patches from the image."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["p = n-w + 1", "[Y, X] = meshgrid(1: p, 1: p)", "[dY, dX] = meshgrid(0: w-1, 0: w-1)", "X = reshape(X, [1 1 p p])", "Y = reshape(Y, [1 1 p p])", "X = repmat(X, [w w 1 1]) + repmat(dX, [1 1 p p])", "Y = repmat(Y, [w w 1 1]) + repmat(dY, [1 1 p p])", "P0 = M0(X + (Y-1)*n)", "P0 = reshape(P0, w, w, p*p)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Remove those that cross the holes."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["I = find(min(min(P0, [], 1), [], 2)~ = 0)", "P0 = P0(: , : , I)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Number of patches."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["q = 1000"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Sub-sample the patches"]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["sel = randperm(size(P0, 3)); sel = sel(1: q)", "P0 = P0(: , : , sel)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Initialize the inpainting with random values inside the hole."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["M = M0", "I = find(mask = =1)", "M(I) = rand(length(I), 1)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Extract non-overlapping patches in the image, with a given offset."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["ofx = 2; ofy = 1", "[Y, X] = meshgrid(1: w: n, 1: w: n)", "p = size(X, 1)", "[dY, dX] = meshgrid(0: w-1, 0: w-1)", "X = reshape(X, [1 1 p p])", "Y = reshape(Y, [1 1 p p])", "X = repmat(X, [w w 1 1]) + repmat(dX, [1 1 p p])", "Y = repmat(Y, [w w 1 1]) + repmat(dY, [1 1 p p])", "Xs = mod(X + ofx-1, n) + 1", "Ys = mod(Y + ofy-1, n) + 1", "P = M(Xs + (Ys-1)*n)", "Pmask = M(Xs + (Ys-1)*n)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Replace each patch by its closest match."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["for i in 1: p*p:", "    if sum(sum(Pmask(: , : , i))) >0", "        % project only a patch crossing the hole.", "        % distance to current patch", "        d = sum(sum((P0 - repmat(P(: , : , i), [1 1 q])).^2))", "        % best match", "        [tmp, s] = min(d)", "        % replace the patch", "        P(: , : , i) = P0(: , : , s)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Reconstruct the image."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["Mp = M", "Mp(Xs + (Ys-1)*n) = P"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Impose the values of the known pixels."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["Mp(mask = =0) = M0(mask = =0)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Display."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["imageplot(M, 'Input', 1, 2, 1)", "imageplot(Mp, 'Projected', 1, 2, 2)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["__Exercise 6__", "", "Perform the inpainting by repeating several time the projection with", "different offsets. You do not needs to average the offset for", "inpainting.", "nitialization"]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["solutions.exo6()"]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["## Insert your code here."]}, {"cell_type": "markdown", "metadata": {}, "source": ["Display."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["imageplot(M0, 'To inpaint', 1, 2, 1)", "imageplot(M, 'Inpainted', 1, 2, 2)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["__Exercise 7__", "", "Test the inpainting with larger holes and with various B&W and color", "images."]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["solutions.exo7()"]}, {"cell_type": "code", "language": "python", "metadata": {}, "outputs": [], "collapsed": false, "input": ["## Insert your code here."]}]}], "nbformat": 3, "metadata": {"name": ""}, "nbformat_minor": 0}