text:
Print the N-bonacci sequence
This isn't very widely known, but what we call the Fibonacci sequence, AKA
1, 1, 2, 3, 5, 8, 13, 21, 34...

is actually called the Duonacci sequence. This is because to get the next number, you sum the previous 2 numbers. There is also the Tribonacci sequence,
1, 1, 1, 3, 5, 9, 17, 31, 57, 105, 193, 355, 653, 1201...

because the next number is the sum of the previous 3 numbers. And the Quadronacci sequence
1, 1, 1, 1, 4, 7, 13, 25, 49, 94, 181, 349, 673...

And everybody's favorite, the Pentanacci sequence:
1, 1, 1, 1, 1, 5, 9, 17, 33, 65, 129...

And the Hexanacci sequence, the Septanacci sequence, the Octonacci sequence, and so on and so forth up to the N-Bonacci sequence.
The N-bonacci sequence will always start with N 1s in a row.
The Challenge
You must write a function or program that takes two numbers N and X, and prints out the first X N-Bonacci numbers. N will be a whole number larger than 0, and you can safely assume no N-Bonacci numbers will exceed the default number type in your language.  The output can be in any human readable format, and you can take input in any reasonable manner. (Command line arguments, function arguments, STDIN, etc.)
As usual, this is Code-golf, so standard loopholes apply and the shortest answer in bytes wins!
Sample IO
#n,  x,     output
 3,  8  --> 1, 1, 1, 3, 5, 9, 17, 31
 7,  13 --> 1, 1, 1, 1, 1, 1, 1, 7, 13, 25, 49, 97, 193
 1,  20 --> 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
 30, 4  --> 1, 1, 1, 1       //Since the first 30 are all 1's
 5,  11 --> 1, 1, 1, 1, 1, 5, 9, 17, 33, 65, 129

Man, I had this idea a while ago and never got around to writing it up.

Wouldn't 3-bonacci be 1, 1, 2, 4, 7 as the third position would be 0 + 1 + 1?  ... and so one with the others?

@umbrella No, the tribonacci starts with 3 1s. See my edit to clarify this point.

Well then, that rules out using this approach. What a shame.

Boolfuck, 6 bytes
,,[;+]

You can safely assume no N-Bonacci numbers will exceed the default number type in your language.

The default number type in Boolfuck is a bit. Assuming this also extends to the input numbers N and X, and given that N>0, there are only two possible inputs - 10 (which outputs nothing) and 11 (which outputs 1).
, reads a bit into the current memory location. N is ignored as it must be 1. If X is 0, the loop body (surrounded by []) is skipped. If X is 1, it is output and then flipped to 0 so the loop does not repeat.

@StanStrum From before or after this answer?

@StanStrum In fact, this answer is the example linked to in the initial version of that loophole.

After this answer was posted, exploiting too-small number types because a standard loophole. That's what StanStrum's deleted comment was talking about.

Indeed, abusing native number types is one of the loopholes that doesn't apply retroactively. I personally disagree with this policy and think it should, but I accept that consensus is against me.

Python 2, 79 bytes
n,x=input()
i,f=0,[]
while i<x:v=[sum(f[i-n:]),1][i<n];f.append(v);print v;i+=1

Try it online

Try replacing the last line with exec"v=[sum(f[i-n:]),1][i<n];f+=[v];print v;i+=1;"*x

Pyth, 13
<Qu+Gs>QGEm1Q

Test Suite
Takes input newline separated, with n first.
Explanation:
<Qu+Gs>QGEm1Q  ##  implicit: Q = eval(input)
  u      Em1Q  ##  read a line of input, and reduce that many times starting with
               ##  Q 1s in a list, with a lambda G,H
               ##  where G is the old value and H is the new one
   +G          ##  append to the old value
     s>QG      ##  the sum of the last Q values of the old value
<Q             ##  discard the last Q values of this list

Wow, that was fast. I barely had time to close my browser before you'd already posted this!

Haskell, 56 bytes
g l=sum l:g(sum l:init l)
n#x|i<-1<$[1..n]=take x$i++g i

Usage example: 3 # 8-> [1,1,1,3,5,9,17,31].
How it works
i<-1<$[1..n]           -- bind i to n copies of 1
take x                 -- take the first x elements of
       i++g i          -- the list starting with i followed by (g i), which is
sum l:                 -- the sum of it's argument followed by
      g(sum l:init l)  -- a recursive call to itself with the the first element
                       -- of the argument list replaced by the sum

Shouldn't that be tail l instead of init l?

@proudhaskeller: it doesn't matter. we keep  the last n elements int the list. There's no difference between removing from the end and adding to the front and the other way around, i.e. removing from the front and adding to the end, because the initial list is made up of only 1s.

Oh, I get it. That's a nifty way to replace ++[] by :!

@proudhaskeller: yes, exactly!

Javascript ES6/ES2015, 107 97 85 80 Bytes
Thanks to @user81655, @Neil and @ETHproductions for save some bytes

(i,n)=>eval("for(l=Array(i).fill(1);n-->i;)l.push(eval(l.slice(-i).join`+`));l")

try it online

Test cases:
console.log(f(3,  8))// 1, 1, 1, 3, 5, 9, 17, 31
console.log(f(7,  13))// 1, 1, 1, 1, 1, 1, 1, 7, 13, 25, 49, 97, 193
console.log(f(5,  11))// 1, 1, 1, 1, 1, 5, 9, 17, 33, 65, 129

Nice. A couple of golfing tips: for is always better than while, x.split('') -> [...x], ~~a -> +a, n-=1 -> n--, if you enclose the entire function body in an eval you don't need to write return. Also, even shorter than [...'1'.repeat(i)] is Array(i).fill(1) and you can remove the ~~ from a and b. And you're allowed to remove the f=.

This is what it looks like with my tips (85 bytes): (i,n)=>eval("for(l=Array(i).fill(1);n-->i;)l.push(l.slice(-i).reduce((a,b)=>a+b));l"). I changed the order of statements, combined the n-- into n-i and removed l from the arguments to save a few extra bytes.

@user81655 I don't get the eval saving; (i,n)=>{for(l=Array(i).fill(1);n-->i;)l.push(l.slice(-i).reduce((a,b)=>a+b));return l} is still 85 bytes.

@Neil Looks like 86 bytes to me...

@user81655 Sorry I must have miscounted.

l.slice(-i).reduce((a,b)=>a+b) => eval(l.slice(-i).join`+`)

ES6, 66 bytes
(i,n)=>[...Array(n)].map((_,j,a)=>a[j]=j<i?1:j-i?s+=s-a[j+~i]:s=i)

Sadly map won't let you access the result array in the callback.

Save a byte by currying the parameters.

Jelly, 12 bytes
ḣ³S;
b1Ç⁴¡Uḣ

Try it online!
How it works
b1Ç⁴¡Uḣ  Main link. Left input: n. Right input: x.

b1       Convert n to base 1.
    ¡    Call...
  Ç        the helper link...
   ⁴       x times.
     U   Reverse the resulting array.
      ḣ  Take its first x elements.

ḣ³S;     Helper link. Argument: A (list)

ḣ³       Take the first n elements of A.
  S      Compute their sum.
   ;     Prepend the sum to A.

Python 2, 55 bytes
def f(x,n):l=[1]*n;exec"print l[0];l=l[1:]+[sum(l)];"*x

Tracks a length-n window of the sequence in the list l, updated by appending the sum and removing the first element. Prints the first element each iteration for x iterations.
A different approach of storing all the elements and summing the last n values gave the same length (55).
def f(x,n):l=[1]*n;exec"l+=sum(l[-n:]),;"*x;print l[:x]

Haskell, 47 bytes
q(h:t)=h:q(t++[h+sum t])
n?x=take x$q$1<$[1..n]

Try it online!
<$ might have been introduced into Prelude after this challenge was posted.

Haskell, 53 bytes
n%i|i>n=sum$map(n%)[i-n..i-1]|0<1=1
n?x=map(n%)[1..x]

Try it online!
Defines the binary function ?, used like 3?8 == [1,1,1,3,5,9,17,31].
The auxiliary function % recursively finds the ith element of the n-bonacci sequence by summing the previous n values. Then, the function ? tabulates the first x values of %.

Old answer, but do you mean "The auxiliary function %"?

Switching the guards will turn i<=n into i>n.

@ØrjanJohansen I noticed that too when editing, though looking back the whole method seems bad, so I might just re-do the whole golf.

Husk, 9 bytes
↑§¡ȯΣ↑_B1

Try it online!
Starts from the Base-1 representation of N (simply a list of N ones) and ¡teratively sums (Σ) the last (↑_) N elements and appends the result to the list. Finally, takes (↑) the first X numbers in this list and returns them.

Haskell, 46 bytes
g _ 0=[]
g(h:t)n=h:g(t++[sum$h:t])(n-1)

g.g[1]

Attempt This Online!
This is based on xnor's answer but it employs 1 clever trick.
The \$n\$-bonacci sequence always start with \$n\$ 1s.  A more general version of this might start with just any \$n\$ values.  And this more general version is what we implement with g.  g takes a list of \$n\$ integers and a value \$m\$ and gives us a list of the first \$m\$ terms of this generalized \$n\$-bonacci sequence.
The trick is then that g[1] is a cheap way to generate \$n\$ 1s.  Since the sequence starting with [1] is just an endless stream of 1s.  So we use g in two ways, and even though g might be slightly longer because it implements something a little more general, it saves bytes because it serves two purposes.

Very nice, I see you re-used g as a helper to initialize the list of n ones, which also avoids using <$.

C#, 109 bytes
(n,x)=>{int i,j,k;var y=new int[x];for(i=-1;++i<x;y[i]=i<n?1:k){k=0;for(j=i-n;j>-1&j<i;)k+=y[j++];}return y;}

Try it online!

(n, x) => {
    int i, j, total;
    var result = new int[x];
    for (i = -1; ++i < x; ) { //calculate each term one at a time
        total = 0; //value of the current term
        for (j = i - n; j > -1 & j < i;) //sum the last n terms
        {
            total += result[j++];
        }
        result[i] = i < n ? 1 : total; //first n terms are always 1 so ignore the total if i < n
    }
    return result;
}

C++11, 360 bytes
Hi I just like this question. I know c++ is a very hard language to win this competition. But I'll thrown a dime any way.
#include<vector>
#include<numeric>
#include<iostream>
using namespace std;typedef vector<int>v;void p(v& i) {for(auto&v:i)cout<<v<<" ";cout<<endl;}v b(int s,int n){v r(n<s?n:s,1);r.reserve(n);for(auto i=r.begin();r.size()<n;i++){r.push_back(accumulate(i,i+s,0));}return r;}int main(int c, char** a){if(c<3)return 1;v s=b(atoi(a[1]),atoi(a[2]));p(s);return 0;}

I'll leave this as the readable explanation of the code above.
#include <vector>
#include <numeric>
#include <iostream>

using namespace std;
typedef vector<int> vi;

void p(const vi& in) {
    for (auto& v : in )
        cout << v << " ";
    cout << endl;
}

vi bonacci(int se, int n) {
    vi s(n < se? n : se, 1);
    s.reserve(n);
    for (auto it = s.begin(); s.size() < n; it++){
        s.push_back(accumulate(it, it + se, 0));
    }
    return s;
}

int main (int c, char** v) {
    if (c < 3) return 1;
    vi s = bonacci(atoi(v[1]), atoi(v[2]));
    p(s);
    return 0;
}

Welcome to Programming Puzzles and Code Golf. This is a good answer, however I have noticed that you have lots of whitespace, and variable and function names that are longer than 1 character long. As it stands, this is a good readable version of your code, but you should add a golfed version. When you do, I will give you an upvote, but until it is golfed I will not.

@wizzwizz4 Hi, added a golfed version of the code above. I left the ungolfed code around to let people see how I did it. Besides I like to read a function bonacci that returns vi which still sounds like vibonacci. I do feel I should not make the main function shorter because the standardard mandates using int main(int, char**) as entry point of the program. Further I believe all variables are max 1 character long and all non significant whitespaces are removed.

This is not code-"comply with the standards". This is [tag:code-golf]. We manipulate and take advantage of our languages. If any variables are ints, remove the int. If any functions are called foo, call them f. Be brutal; ignore the standard and exploit the compiler. That is how you golf.

Puns and nice code belong in the ungolfed code only. But feel free to keep them there; actually, it is recommended to. But be really, really mean to the compiler when you golf your code. Get it as small as possible no matter what. (Oh, and here's the +1 I promised!)

@wizzwizz4 Is removing "int" valid? I thought implied int won't run.

@DJMcGoathem http://codegolf.stackexchange.com/a/40266/43394 and the other answers on Tips for golfing in C.

@DJMcGoathem It Would definitely be possible in C any function without explicit  return type will return int. In C++ I don't think it's possible. Except perhaps it might be possible when abusing the compiler for code golf.

252 bytes

Java, 82 + 58 = 140 bytes
Function to find the ith n-bonacci number (82 bytes):
int f(int i,int n){if(i<=n)return 1;int s=0,q=0;while(q++<n)s+=f(i-q,n);return s;}

Function to print first k n-bonacci number (58 bytes):
(k,n)->{for(int i=0;i<k;i++){System.out.println(f(i,n));}}

Uiua (version 0.0.7), 34 bytes
→(;;)⍥(⊂∶/+↙∶→,⇌.)∶→(-,,)[⍥.-1∶1].

Python 3, 59
Saved 20 bytes thanks to FryAmTheEggman.
Not a great solution, but it'll work for now.
def r(n,x):f=[1]*n;exec('f+=[sum(f[-n:])];'*x);return f[:x]

Also, here are test cases:
assert r(3, 8) == [1, 1, 1, 3, 5, 9, 17, 31]
assert r(7, 13) == [1, 1, 1, 1, 1, 1, 1, 7, 13, 25, 49, 97, 193]
assert r(30, 4) == [1, 1, 1, 1]

APL, 21
{⍵↑⍺{⍵,+/⍺↑⌽⍵}⍣⍵+⍺/1}

This is a function that takes n as its left argument and x as its right argument.
Explanation:
{⍵↑⍺{⍵,+/⍺↑⌽⍵}⍣⍵+⍺/1}
                   ⍺/1  ⍝ begin state: X ones
                  +     ⍝ identity function (to separate it from the ⍵)
    ⍺{         }⍣⍵     ⍝ apply this function N times to it with X as left argument
      ⍵,               ⍝ result of the previous iteration, followed by...
        +/              ⍝ the sum of
          ⍺↑            ⍝ the first X of
            ⌽          ⍝ the reverse of
             ⍵         ⍝ the previous iteration
 ⍵↑                    ⍝ take the first X numbers of the result

Test cases:
      ↑⍕¨ {⍵↑⍺{⍵,+/⍺↑⌽⍵}⍣⍵+⍺/1} /¨ (3 8)(7 13)(1 20)(30 4)(5 11)
 1 1 1 3 5 9 17 31
 1 1 1 1 1 1 1 7 13 25 49 97 193
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 1 1 1 1
 1 1 1 1 1 5 9 17 33 65 129

C, 132 bytes
The recursive approach is shorter by a couple of bytes.
k,n;f(i,s,j){for(j=s=0;j<i&j++<n;)s+=f(i-j);return i<n?1:s;}main(_,v)int**v;{for(n=atoi(v[1]);k++<atoi(v[2]);)printf("%d ",f(k-1));}

Ungolfed
k,n; /* loop index, n */

f(i,s,j) /* recursive function */
{
    for(j=s=0;j<i && j++<n;) /* sum previous n n-bonacci values */
        s+=f(i-j);
    return i<n?1:s; /* return either sum or n, depending on what index we're at */
}

main(_,v) int **v;
{
    for(n=atoi(v[1]);k++<atoi(v[2]);) /* print out n-bonacci numbers */
        printf("%d ", f(k-1));
}

Brain-Flak, 144 124 122 bytes
-20 bytes thanks to Nitroden
This is my first Brain-Flak answer, and I'm sure it can be improved. Any help is appreciated.
(([{}]<>)<{({}(()))}{}>)<>{({}[()]<<>({<({}<({}<>)<>>())>[()]}{})({}<><({({}<>)<>}<>)>)<>>)}{}<>{({}<{}>())}{}{({}<>)<>}<>

Try it online!

Pari/GP, 46 bytes
The generating function of the sequence is:
$$\frac{(n-1)x^n}{x^{n+1}-2x+1}-\frac{1}{x-1}$$
(n,m)->Vec(n--/(x-(2-1/x)/x^n)-1/(x-1)+O(x^m))

Try it online!

R, 60 bytes
function(n,m){for(i in 1:m)T[i]=`if`(i>n,sum(T[i-1:n]),1);T}

Try it online!

Vyxal , 8 bytes
1ẋ?‡W∑*Ḟ

Try it Online!
1ẋ       # [1] * input
   ‡W∑   # Function summing its inputs
  ?   *  # Set the arity to the input
       Ḟ # Generate an infinite list from the function and the vector of 1s.

Julia, 78 bytes
f(n,x)=(z=ones(Int,n);while endof(z)<x push!(z,sum(z[end-n+1:end]))end;z[1:x])

This is a function that accepts two integers and returns an integer array. The approach is simple: Generate an array of ones of length n, then grow the array by adding the sum of the previous n elements until the array has length x.
Ungolfed:
function f(n, x)
    z = ones(Int, n)
    while endof(z) < x
        push!(z, sum(z[end-n+1:end]))
    end
    return z[1:x]
end

MATL, 22 26 bytes
1tiXIX"i:XK"tPI:)sh]K)

This uses current release (10.2.1) of the language/compiler.
Try it online!
A few extra bytes :-( due to a bug in the G function (paste input; now corrected for next release)
Explanation
1tiXIX"      % input N. Copy to clipboard I. Build row array of N ones
i:XK         % input X. Build row array [1,2,...X]. Copy to clipboard I
"            % for loop: repeat X times. Consumes array [1,2,...X]
  t          % duplicate (initially array of N ones)
  PI:)       % flip array and take first N elements
  sh         % compute sum and append to array
]            % end
K)           % take the first X elements of array. Implicitly display

Perl 6, 52~72 47~67 bytes
sub a($n,$x){EVAL("1,"x$n~"+*"x$n~"...*")[^$x]}

Requires the module MONKEY-SEE-NO-EVAL, because of the following error:

===SORRY!=== Error while compiling -e
  EVAL is a very dangerous function!!! (use MONKEY-SEE-NO-EVAL to override,
  but only if you're VERY sure your data contains no injection attacks)
  at -e:1

$ perl6 -MMONKEY-SEE-NO-EVAL -e'a(3,8).say;sub a($n,$x){EVAL("1,"x$n~"+*"x$n~"...*")[^$x]}'
(1 1 1 3 5 9 17 31)

Anyone know of a way to turn off strict mode, etc?

I think if you use a pre-christmas 2015 Perl 6 release, it doesn't enforce monkey-see-no-eval.

Perl 6, 38 bytes
->\N,\X{({@_[*-N..*].sum||1}...*)[^X]} # 38 bytes

-> \N, \X {
  (

    {

      @_[
        *-N .. * # previous N values
      ].sum      # added together

      ||     # if that produces 0 or an error
      1      # return 1

    } ... *  # produce an infinite list of such values

  )[^X]      # return the first X values produced
}

Usage:
# give it a lexical name
my &n-bonacci = >\N,\X{…}

for ( (3,8), (7,13), (1,20), (30,4), (5,11), ) {
  say n-bonacci |@_
}

(1 1 1 3 5 9 17 31)
(1 1 1 1 1 1 1 7 13 25 49 97 193)
(1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
(1 1 1 1)
(1 1 1 1 1 5 9 17 33 65 129)

J, 31 bytes
]{.(],[:+/[{.])^:(-@[`]`(1#~[))

Ungolfed:
] {. (] , [: +/ [ {. ])^:(-@[`]`(1 #~ [))

explanation
Fun times with the power verb in its gerund form:
(-@[`]`(1 #~ [)) NB. gerund pre-processing

Breakdown in detail:

] {. ... Take the first <right arg> elements from all this stuff to the right that does the work...
<left> ^: <right> apply the verb <left> repeatedly <right> times... where <right> is specified by the middle gerund in (-@[](1 #~ [), ie, ], ie, the right arg passed into the function itself.  So what is <left>? ...
(] , [: +/ [ {. ]) The left argument to this entire phrase is first transformed by the first gerund, ie, -@[.  That means the left argument to this phrase is the negative of the left argument to the overall function. This is needed so that the phrase [ {. ] takes the last elements from the return list we're building up.  Those are then summed: +/.  And finally appended to that same return list: ] ,.
So how is the return list initialized?  That's what the third pre-processing gerund accomplishes:  (1 #~ [) -- repeat 1 "left arg" number of times.

Try it online!

Ruby, 41 bytes
->a,b{r=[1]*a;b.times{z,*r=r<<r.sum;p z}}

Try it online!

R, 68 bytes
function(n,x){a=1+!1:n;for(i in n+1:x){a[i]=sum(a[(i-n:1)])};a[1:x]}

Try it online!

K (ngn/k), 26 24 bytes
{(y-x){y,+/x#y}[-x]/x#1}

Try it online!

Vyxal, 8 bytes
1ẋ{:∑pṫ,

Try it Online!
-2 bytes thanks to emanresu A

8

JavaScript, 65 bytes
The eval & slice are annoying me!
x=>g=(n,...a)=>n?g(n-1,...a,a[x-1]?eval(a.slice(-x).join`+`):1):a

Try it online!

Thunno 2, 13 bytes
{1}¹{K°ɱS}K¹ɱ

Attempt This Online!
Explanation
{1}¹{K°ɱS}K¹ɱ  # Implicit input
{1}            # Push 1 to the stack n times
   ¹{    }     # Repeat x times:
     K°ɱ       #  Take the top n items of the stack
        S      #  And sum this list
          K¹ɱ  # Take the top x items of the stack
               # Implicit output

PHP, 78 bytes
for(list(,$n,$x)=$argv;$i<$x;print${$i++}." ")$s+=$$i=$i<$n?1:$$d+$s-=${$d++};

Try it online!
-4 Bytes using PHP>=7.1 [,$n,$x] instead of list(,$n,$x)

Jq 1.5, 67 bytes
def C:if length>X then.[:X]else.+=[.[-N:]|add]|C end;[range(N)|1]|C

Assumes input provided by N and X e.g.
def N: 5;
def X: 11;

Expanded
def C:                        # . is current array
    if length>X               # stop when array is as long as X
    then .[:X]                # return first X elements
    else .+=[.[-N:]|add] | C  # recursively add sum of last N elements to array
    end
;
  [range(N)|1]                # initial state
| C

Try it online!

Mathematica, 59 bytes
((f@#=1)&/@Range@#;f@n_:=Tr[f[n-#]&/@Range@#];f/@Range@#2)&

You'll probably want to Clear@f between function calls. Arguments are n,x, just like the test cases.

-18 bytes

Tidy, 36 bytes
{x,n:n^recur(*tile(x,c(1)),sum@c,x)}

Try it online!
Explanation
{x,n:n^recur(*tile(x,c(1)),sum@c,x)}
{x,n:                              }   lambda taking parameters `x` and `n`
     n^                                take the first `n` terms of...
       recur(                     )        a recursive function
             *tile(x,c(1)),                whose seed is `x` `1`s
                           sum@c,          taking the sum of each window
                                 x         with a window size of `x`

Japt, 18 bytes
@ZsVn)x}gK=Vì1;K¯U

Try it online!
Explanation:
         K=Vì1        :Start with n 1s in an array K
@      }gK            :Extend K to at least x elements by setting each new element to:
      x               : The sum of
 ZsVn                 : The previous n elements
              ;       :Then
               K¯U    :Return the first n elements of K

MathGolf, 10 bytes
ª*kÆ_Σ▐├p;

Try it online!
Explanation
ª            push [1]
 *           pop a, b : push(a*b)
  k          read integer from input
   Æ         start block of length 5
    _        duplicate TOS
     Σ       sum(list), digit sum(int)
      ▐      append to end of list
       ├     pop from left of string/array
        p    print with newline
         ;   discard TOS

Japt, 16 12 bytes
@ZÔ¯V x}hVÆ1

Try it
@ZÔ¯V x}hVÆ1     :Implicit input of integers U=X & V=N
         VÆ1     :Map the range [0,V) returning 1 for each element
        h        :Push the result of the following to the array and repeat until its length equals U
@                :  Pass the array through the following function as Z
 ZÔ              :    Reverse Z
   ¯V            :    Slice to the Vth element
      x          :    Reduce by addition
       }         :  End function

C# (.NET Core), 130 bytes
(n,x)=>{int j=0,k=0,l=0;var b=new int[x];for(;j<(x<n?x:n);)b[j++]=1;for(j=n;j<x;l=0){for(k=n;k>0;)l+=b[j-k--];b[j++]=l;}return b;}

Try it online!

C (gcc), 94 bytes
a(c,C,i){for(int Q[C+c],*q=Q;C--;printf("%d ",*q++))for(*q=Q-q>(i=-c);Q-q<=i&i<0;)*q+=q[i++];}

Try it online!

krrp, 72 bytes
^nx:\L[take]x,^nl:?nL#!fl@-n1#!r[append]lL[sum]lEl.x[map]^_:1.[range]0n.

Try it online!

Explanation
^nx:              ~ lambda expression in two parameters
 \L               ~  import list module
 [take]x          ~  the first x elements of
  ,^nl:           ~   extend the initial list of n ones
    ?n            ~    if n is non-zero
     L #!fl       ~     keep the first element
      @-n1        ~     recur
       #!r        ~     separate the first element
        [append]l ~      append an additional element,
         L[sum]lE ~      namely the sum of the previous elements
     l            ~    if n is zero, yield l
   . x            ~ extend x elements, yielding in a list of n+x elements
   [map]^_:1.     ~   map a constant function
   [range]0n.     ~   onto a list of n elements

Try it online!

PostScript, 83 bytes
/f{/x exch def/n exch def[1 1 x{n le{1}{n copy n 1 sub{add}repeat}ifelse}for]==}def

e.g., 5 11 f prints [1 1 1 1 1 5 9 17 33 65 129].
Try it online!


text:
What's the point?
Write a program or function that takes in two integers that represent the X and Y coordinates of a point on a Cartesian plane.
The input may come in any reasonable format as long as the X value comes before the Y. For example, 1 -2, (1,-2), [1, -2], or 1\n-2 would all be fine for X = 1, Y = -2.
Print or return a single character string (followed by an optional trailing newline) that describes the location of the point in the plane:

1 if the point is in quadrant I
2 if the point is in quadrant II
3 if the point is in quadrant III
4 if the point is in quadrant IV
X if the point is on the x-axis (lowercase x is not allowed)
Y if the point is on the y-axis (lowercase y is not allowed)
O if the point is on the origin (that's a capital letter "oh", not zero)

The shortest code in bytes wins. Tiebreaker goes to the higher voted answer.
Test Cases
(1,-2) -> 4
(30,56) -> 1
(-2,1) -> 2
(-89,-729) -> 3
(-89,0) -> X
(0,400) -> Y
(0,0) -> O
(0,1) -> Y
(0,-1) -> Y
(1,0) -> X
(-1,0) -> X
(1,1) -> 1
(1,-1) -> 4
(-1,1) -> 2
(-1,-1) -> 3

So for the purposes of this challenge, X and Y axis are in no quadrant?

@RikerW Right. Otherwise the point (0, 9) could be said to be quadrant I or II.

Is a complex number (or a string representation of it, like "30+56i") a valid input format?

@steveverrill Yes

Can the input be in the form of a complex number? (e.g. 1+2j)

Jelly, 14 bytes
Ṡḅ3ị“Y4X13X2YO

Try it online!
How it works
Ṡḅ3ị“Y4X13X2YO    Main link. Input: [x, y]

Ṡ                 Apply the sign function to both coordinates.
 ḅ3               Convert the resulting pair from base 3 to integer.
                  Because of how base conversion is implemented in Jelly, this maps
                  [a, b] to (3a + b), even if a and b aren't valid ternary digits.
                  Therefore:
                      [0, 1]   ->  1
                      [1, -1]  ->  2
                      [1, 0]   ->  3
                      [1, 1]   ->  4
                      [-1, -1] -> -4
                      [-1, 0]  -> -3
                      [-1, 1]  -> -2
                      [0, -1]  -> -1
                      [0, 0]   ->  0
   ị“Y4X13X2YO    Retrieve the character at that index from the string.
                Indexing is 1-based and modular in Jelly, so 1ị retrieves the
                first character, -1ị the penultimate, and 0ị the last.

Joining the Jelly from phone club.

Aaaaaand Jelly wins once again...

Very good approach!

Ruby, 35 bytes
->x,y{%w[OY X14 X23][x<=>0][y<=>0]}

Leveraging the "spaceship" (<=>) operator.
x <=> 0 will return

0 if x == 0
1 if x > 0
-1 if x < 0

Hence,

if x == 0, we return 'OY'[y<=>0]. This is

O if y == 0 (string indexing at 0)
Y if y != 0 (this is true because both 1 and -1 will result in Y when indexing on this string, as -1 refers to the last character in the string, which also happens to be the one at index 1)

if x > 0, we return 'X14'[y<=>0]. This is X if y == 0, 1 if y > 0, and 4 if y < 0 (see explanation above).
if x < 0, we return 'X23'[y<=>0].

JavaScript, 44 bytes
(x,y)=>x?y?x>0?y>0?1:4:y>0?2:3:'X':y?'Y':'O'

f=(x,y)=>x?
            y?
                x>0?
                    y>0?1
                    :4
                :y>0?2:3
            :'X'
        :y?'Y':'O'

document.body.innerHTML = '
' +
    'f(1,-2) -> ' + f(1,-2) + '
' +
    'f(30,56) -> ' + f(30,56) + '
' +
    'f(-2,1) -> ' + f(-2,1) + '
' +
    'f(-89,-729) -> ' + f(-89,-729) + '
' +
    'f(-89,0) -> ' + f(-89,0) + '
' +
    'f(0,400) -> ' + f(0,400) + '
' +
    'f(0,0) -> ' + f(0,0) + '
' +
    'f(0,1) -> ' + f(0,1) + '
' +
    'f(0,-1) -> ' + f(0,-1) + '
' +
    'f(1,0) -> ' + f(1,0) + '
' +
    'f(-1,0) -> ' + f(-1,0) + '
' +
    'f(1,1) -> ' + f(1,1) + '
' +
    'f(1,-1) -> ' + f(1,-1) + '
' +
    'f(-1,1) -> ' + f(-1,1) + '
' +
    'f(-1,-1) -> ' + f(-1,-1) + '
' +
'
';

My eyes hurt, that's one long chain of ternary operators

afaik its allowed to write an anonymous function (s/^f=//)

ES6, 43 bytes
(x,y)=>"OYYX32X41"[3*!!x+3*(x>0)+!!y+(y>0)]

A whole byte shorter than all of those ternaries!

Japt, 30 22 bytes
"3Y2XOX4Y1"g4+3*Ug +Vg

Inspired by @Dennis' Jelly answer before he added an explanation. Test it online!
Fun fact: this would be two bytes shorter if I had added support for negative numbers in the g function for strings.
Another attempt, closer to the Jelly one (23 bytes):
"3Y2XOX4Y1"gNmg m+1 ¬n3

Sadly, incrementing a list costs 4 bytes...

MATL, 22 bytes
'3X2YOY4X1'iZSQI1h*sQ)

This uses current release (10.2.1) of the language/compiler.
Try it online!
Explanation
This shamelessly borrows the great approach in Dennis' answer.
'3X2YOY4X1'     % literal string. Will be indexed into to produce result
i               % input array of two numbers
ZS              % sign of each number in that array. Gives -1, 0 or 1
Q               % add 1 to produce 0, 1 or 2
I1h             % array [3 1]
*s              % multiply both arrays element-wise and compute sum
Q               % add 1. Gives a value from 1 to 9
)               % index into string. Display

Pyth, 18 bytes
@"OY4X13X2Y"i._RQ3

Explanation:
                   - Autoassign Q = eval(input())
             ._RQ  - map(cmp, Q)
            i    3 - convert to base 3
@"OY4X13X2Y"       - "OY4X13X2Y"[^] (A lookup table)

Try it here.
Or the whole test suite

Python 2, 75 bytes
lambda x,y,b=bool:[['OX','YO'][b(y)][b(x)],[[1,2],[4,3]][y<0][x<0]][b(x*y)]

Pretty straightforward.

Mathematica 81 bytes
Switch[Sign@#,{1,-1},4,{1,1},1,{-1,1},2,{-1,-1},3,{0,0},"O",{_,0},"X",{0,_},"Y"]&

%/@{{1, -2}, {30, 56}, {-2, 1}, {-89, -729}, {-89, -0}, {0, 400}, {0, 0},{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}}

{4, 1, 2, 3, "X", "Y", "O", "Y", "Y", "X", "X", 1, 4, 2, 3}

Retina, 52
This is a simple substitution-based method:
^0 0
O
^0.*
Y
.* 0
X
-.*-.*
3
^-.*
2
.*-.*
4
.* .*
1

Try it online.  The extra m`  at the start of some lines is only needed to test multiple inputs in one go, so are not counted in the score.

Previously I tried this more interesting approach, but its quite a bit longer (about 65 without the m modifiers):
[1-9]\d*
1
-1
2
(.) (.)
$1$*3$2$*1
3
111
m`^(.)*$
$#1
T`d`OYYX14X23

substitute all non-zero numbers to 1, leaving - signs in place
Substitute -1 with 2
Convert 1st and 2nd numbers unary with 3 and 1 respectively as the unary digits .  This effectively gives 2 base3 digits, expressed in unary
Convert to 3s to 111.  This effectively gives the a single unary number that corresponds to each of the quadrants, axes and origin
Convert the unary to one decimal digit
Transpose the decimal digit to the appropriate output char.

I don't think the X stage needs $ since there won't be leading zeroes in the input.

The more interesting approach can be shortened to at least 40 bytes. Now I will look at it tomorrow some more.

For batch run you need some tweaking.

Pyth, 24
Too long, but perhaps an interesting approach:
?Q?sQ?eQh%/yPQ.n04\X\Y\O

The input must be specified as a complex number, e.g. 1-2j.  Basically a nested ternary to test:

if input is zero - output O
else if real part is zero - output Y
else if imaginary part is zero - output X
else calculate the complex phase, multiply by 2, integer divide by π, then mod and add to give the appropriate quadrant number.

Try it online.

Octave, 34 bytes
@(p)['3X2YOY4X1'](sign(p)*[3;1]+5)

The old base-3 trick through vector multiplication (although I had to add 5 to account for 1-based array indices) plus some Octave indexing magic.
Input is a vector of the form [1, -2] (with or without the comma), so when assigned to a variable w:
>> w([1 -2])
ans = 4

Here it is on ideone.

Ideone seems to be working again. Did you do anything special to use it?

@LuisMendo This one uses an anonymous function. Named functions are still borked for me. :(

Aah, you are right. It was named functions that were not working. So still the same :-/

Java 8, 64 bytes
this is a lambda expression for a BiFunction<Integer,Integer,String>.
(x,y)->"OYYX14X23".charAt(3*(x>0?1:x<0?2:0)+(y>0?1:y<0?2:0))+"";

3 bytes could be saved by returning a Character instead of a String but i'm not completely sure if autoboxing will play nicely with the lambda.

Oh neat, this answer using the PCCG Handicap System scores better (1.5598) than Dennis's Jelly answer (1.5929).

that's quite interesting. thanks for pointing that out

Ran the values for a few entries on this one out of curiosity (all scores were between 1.5 and 2, for reference).

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
Patch the Image
In a popular image editing software there is a feature, that patches (The term used in image processing is inpainting as @mınxomaτ pointed out.) a selected area of an image, based on the information outside of that patch. And it does a quite good job, considering it is just a program. As a human, you can sometimes see that something is wrong, but if you squeeze your eyes or just take a short glance, the patch seems to fill in the gap quite well.

Challenge
Given an image and a mask that specifies a rectangular area of the image should be patched (also as image, or any other preferred format), your program should try to fill the specified area with a patch that tries to blend in with the rest of the image. The program cannot use the information of the original image that was within the specified area.
You can assume that the patch always is at least it's width away from the sides, and it's height away from the top and the bottom of the image. That means the maximum area of a patch is 1/9 of the whole image.
Please add a brief description on how your algorithm works.
Voting
Voters are asked to judge how well the algorithms perform and vote accordingly.
Some suggestions on how to judge: (Again, thanks @mınxomaτ for the some more criterions.)

If you squint your eyes and the picture looks fine?
Can you exactly tell where the patch is?
How well are structures and textures from the image background and surrounding area continued?
How much stray false color pixels does the edited area contain?
Are there any uniformly colored blobs/blocks in the area that don't seem to belong there?
Does the edited area have any drastic color / contrast or brightness shifts compared to the rest of the image?

Validity criterion
In order for a submission to be valid, the output image must exactly match the input image outside of the specified area.
Test case
On the left the source image, on the right the corresponding mask:

Can we accept the mask input as text arguments (eg. inpaint.exe left top width height img.jpg)?

Sure, the input/output format is not really that important, as it is a popularity contest where first of all the performance of your algorithm is important.

This is a very practical challenge. It is possible the results will be better than existing algorithms used in GIMP and other open source image editing software. Fortune, Fame, and Glory could be yours!

@Sparr and finally ugly watermarks can be removed from downloaded media;)

Can we have some clarification on whether inpainting builtins are permitted?

Builtins are perfectly ok, I do doubt their going to be very popular though.

Are masks always guaranteed to be rectangular? If not, can we have some test cases with non-rectangular masks?

No, the mask is always rectangular as specified.

AutoIt, VB
Introduction
This is an implementation of the Object Removal by Exemplar-Based Inpainting algorithm developed by A. Criminisi, P. Perez (Cambridge Microsoft Research Ltd.) and K. Toyama (Microsoft) [X]. This algorithm is targeted at high-information images (and video frames) and aims to be the balance between structural reconstruction and organic reconstruction. Paragraphs of this answer contain full text quotes from the original paper (since it is no longer officially available) to make this answer more self-contained.
The Algorithm
Goal: Replace a selected (masked) area (preferably a visually separated foreground object) with visually plausible backgrounds.
In previous work, several researchers have considered texture synthesis as a way to fill large image regions with "pure" textures - repetitive two-dimensional textural patterns with moderate stochasticity. This is based on a large body of texture-synthesis research, which seeks to replicate texture ad infinitum, given a small source sample of pure texture [1] [8] [9] [10] [11] [12] [14] [15] [16] [19] [22].
As effective as these techniques are in replicating consistent texture, they have difficulty filling holes in photographs of real-world scenes, which often consist of linear structures and composite textures – multiple textures interacting spatially [23]. The main problem is that boundaries between image regions are a complex product of mutual influences between different textures. In contrast to the two-dimensional nature of pure textures, these boundaries form what might be considered more one-dimensional, or linear, image structures.
Image inpainting techniques fill holes in images by propagating linear structures (called isophotes in the inpainting literature) into the target region via diffusion. They are inspired by the partial differential equations of physical heat flow, and work convincingly as restoration algorithms. Their drawback is that the diffusion process introduces some blur, which is noticeable.

The region to be filled, i.e., the target region is indicated by Ω, and its contour is denoted δΩ. The contour evolves inward as the algorithm progresses, and so we also refer to it as the “fill front”. The source region, Φ, which remains fixed throughout the algorithm, provides samples used in the filling process. We now focus on a single iteration of the algorithm to show how structure and texture are adequately handled by exemplar-based synthesis. Suppose that the square template Ψp ∈ Ω centred at the point p (fig. 2b), is to be filled. The best-match sample from the source region comes from the patch Ψqˆ ∈ Φ, which is most similar to those parts that are already filled in Ψp. In the example in fig. 2b, we see that if Ψp lies on the continuation of an image edge, the most likely best matches will lie along the same (or a similarly coloured) edge (e.g., Ψq' and Ψq'' in fig. 2c). All that is required to propagate the isophote inwards is a simple transfer of the pattern from the best-match source patch (fig. 2d). Notice that isophote orientation is automatically preserved. In the figure, despite the fact that the original edge is not orthogonal to the target contour δΩ, the propagated structure has maintained the same orientation as in the source region.
Implementation and Algorithm Details
The functionality of this implementation is encapsulated in an ActiveX COM DLL which is dropped from the host program as a binary and then invoked on the fly by calling the inpainter by IID. In this specific case, the API is written in VisualBasic and can be called from any COM-enabled language. The following section of the code drops the binary:
Func deflate($e=DllStructCreate,$f=@ScriptDir&"\inpaint.dll")
    If FileExists($f) Then Return
    !! BINARY CODE OMITTED FOR SIZE REASONS !!
    $a=$e("byte a[13015]")
    DllCall("Crypt32.dll","bool","CryptStringToBinaryA","str",$_,"int",0,"int",1,"struct*",$a,"int*",13015,"ptr",0,"ptr",0)
    $_=$a.a
    $b=$e('byte a[13015]')
    $b.a=$_
    $c=$e("byte a[14848]")
    DllCall("ntdll.dll","int","RtlDecompressBuffer","int",2,"struct*",$c,"int",14848,"struct*",$b,"int",13015,"int*",0)
    $d=FileOpen(@ScriptDir&"\inpaint.dll",18)
    FileWrite($d,Binary($c.a))
    FileClose($d)
EndFunc

The library is later instantiated using the CLSID and IID:
Local $hInpaintLib = DllOpen("inpaint.dll")
Local $oInpaintLib = ObjCreate("{3D0C8F8D-D246-41D6-BC18-3CF18F283429}", "{2B0D9752-15E8-4B52-9569-F64A0B12FFC5}", $hInpaintLib)

The library accepts a GDIOBJECT handle, specifically a DIBSection of any GDI/+ bitmap (files, streams etc.). The specified image file is loaded, and drawn onto an empty bitmap constructed from Scan0 from the input image dimensions.
The input file for this implementation is any GDI/+ compatible file format containing masked image data. The mask(s) is one or more uniformly colored regions in the input image. The user supplies a RGB color value for the mask, only pixels with exactly that color value will be matched. The default masking color is green (0, 255, 0). All masked regions together represent the target region, Ω, to be removed and filled. The source region, Φ, is defined as the entire image minus the target region (Φ = I−Ω).
Next, as with all exemplar-based texture synthesis [10], the size of the template window Ψ (aka "scan radius") must be specified. This implementation provides a default window size of 6² pixels, but in practice require the user to set it to be slightly larger than the largest distinguishable texture element, or “texel”, in the source region. An additional modification to the original algorithm is the user-definable "block size" which determines the area of pixels to be replaced with a new uniform color. This increases speed and decreases quality. Block sizes geater than 1px are meant to be used with extremely uniform areas (water, sand, fur etc.), however, Ψ should be kept at max. .5x the block size (which can be impossible depending on the mask).
To not stall the algorithm on 1bit images, every time an image with less than 5 colors is received, the window size is amplified by 10x.
Once these parameters are determined, the remainder of the region-filling process is completely automatic. In our algorithm, each pixel maintains a colour value (or “empty”, if the pixel is unfilled) and a confidence value, which reflects our confidence in the pixel value, and which is frozen once a pixel has been filled. During the course of the algorithm, patches along the fill front are also given a temporary priority value, which determines the order in which they are filled. Then, our algorithm iterates the following three steps until all pixels have been filled.
Step 1:  Computing patch priorities
Filling order is crucial to non-parametric texture synthesis [1] [6] [10] [13]. Thus far, the default favorite has been the “onion peel” method, where the target region is synthesized from the outside inward, in concentric layers. Our algorithm performs this task through a best-first filling algorithm that depends entirely on the priority values that are assigned to each patch on the fill front. The priority computation is biased toward those patches which are on the continuation of strong edges and which are surrounded by high-confidence pixels, these pixel are the boundary, marked by the value -2. The following code recalculates the priorities:
For j = m_top To m_bottom: Y = j * m_width: For i = m_left To m_right
    If m_mark(Y + i) = -2 Then m_pri(Y + i) = ComputeConfidence(i, j) * ComputeData(i, j)
Next i: Next j

Given a patch Ψp centered at the point p for some p ∈ δΩ (see fig. 3), its priority P(p) is defined as the product of the calculated confidence (ComputeConfidence, or C(p)) and the data term (ComputeData, or D(p)), where

(source: imgup.net)
, where
|Ψp| is the area of Ψp, α is a normalization factor (e.g., α = 255 for a typical grey-level image), and np is a unit vector orthogonal to the front δΩ in the point p. The priority is computed for every border patch, with distinct patches for each pixel on the boundary of the target region.
Implemented as
Private Function ComputeConfidence(ByVal i As Long, ByVal j As Long) As Double
    Dim confidence As Double
    Dim X, Y As Long

    For Y = IIf(j - Winsize > 0, j - Winsize, 0) To IIf(j + Winsize < m_height - 1, j + Winsize, m_height - 1): For X = IIf(i - Winsize > 0, i - Winsize, 0) To IIf(i + Winsize < m_width - 1, i + Winsize, m_width - 1)
        confidence = confidence + m_confid(Y * m_width + X)
    Next X: Next Y

    ComputeConfidence = confidence / ((Winsize * 2 + 1) * (Winsize * 2 + 1))
End Function

Private Function ComputeData(ByVal i As Long, ByVal j As Long) As Double
    Dim grad As CPOINT
    Dim temp As CPOINT
    Dim grad_T As CPOINT
    Dim result As Double
    Dim magnitude As Double
    Dim max As Double
    Dim X As Long
    Dim Y As Long
    Dim nn As CPOINT
    Dim Found As Boolean
    Dim Count, num As Long
    Dim neighbor_x(8) As Long
    Dim neighbor_y(8) As Long
    Dim record(8) As Long
    Dim n_x As Long
    Dim n_y As Long
    Dim tempL As Long
    Dim square As Double

    For Y = IIf(j - Winsize > 0, j - Winsize, 0) To IIf(j + Winsize < m_height - 1, j + Winsize, m_height - 1): For X = IIf(i - Winsize > 0, i - Winsize, 0) To IIf(i + Winsize < m_width - 1, i + Winsize, m_width - 1)
        If m_mark(Y * m_width + X) >= 0 Then
            Found = False
            Found = m_mark(Y * m_width + X + 1) < 0 Or m_mark(Y * m_width + X - 1) < 0 Or m_mark((Y + 1) * m_width + X) < 0 Or m_mark((Y - 1) * m_width + X) < 0
            If Found = False Then
                temp.X = IIf(X = 0, m_gray(Y * m_width + X + 1) - m_gray(Y * m_width + X), IIf(X = m_width - 1, m_gray(Y * m_width + X) - m_gray(Y * m_width + X - 1), (m_gray(Y * m_width + X + 1) - m_gray(Y * m_width + X - 1)) / 2#))
                temp.Y = IIf(Y = 0, m_gray((Y + 1) * m_width + X) - m_gray(Y * m_width + X), IIf(Y = m_height - 1, m_gray(Y * m_width + X) - m_gray((Y - 1) * m_width + X), (m_gray((Y + 1) * m_width + X) - m_gray((Y - 1) * m_width + X)) / 2#))
                magnitude = temp.X ^ 2 + temp.Y ^ 2
                If magnitude > max Then
                    grad.X = temp.X
                    grad.Y = temp.Y
                    max = magnitude
                End If
            End If
        End If
    Next X: Next Y

    grad_T.X = grad.Y
    grad_T.Y = -grad.X

    For Y = IIf(j - 1 > 0, j - 1, 0) To IIf(j + 1 < m_height - 1, j + 1, m_height - 1): For X = IIf(i - 1 > 0, i - 1, 0) To IIf(i + 1 < m_width - 1, i + 1, m_width - 1): Count = Count + 1
        If X <> i Or Y <> j Then
            If m_mark(Y * m_width + X) = -2 Then
                num = num + 1
                neighbor_x(num) = X
                neighbor_y(num) = Y
                record(num) = Count
            End If
        End If
    Next X: Next Y

    If num = 0 Or num = 1 Then
        ComputeData = Abs((0.6 * grad_T.X + 0.8 * grad_T.Y) / 255)
    Else
        n_x = neighbor_y(2) - neighbor_y(1)
        n_y = neighbor_x(2) - neighbor_x(1)
        square = CDbl(n_x ^ 2 + n_y ^ 2) ^ 0.5
        ComputeData = Abs((IIf(n_x = 0, 0, n_x / square) * grad_T.X + IIf(n_y = 0, 0, n_y / square) * grad_T.Y) / 255)
    End If
End Function

The confidence term C(p) may be thought of as a measure of the amount of reliable information surrounding the pixel p. The intention is to fill first those patches which have more of their pixels already filled, with additional preference given to pixels that were filled early on (or that were never part of the target region).
This automatically incorporates preference towards certain shapes along the fill front. For example, patches that include corners and thin tendrils of the target region will tend to be filled first, as they are surrounded by more pixels from the original image. These patches provide more reliable information against which to match. Conversely, patches at the tip of “peninsulas” of filled pixels jutting into the target region will tend to be set aside until more of the surrounding pixels are filled in. At a coarse level, the term C(p) of (1) approximately enforces the desirable concentric fill order.
As filling proceeds, pixels in the outer layers of the target region will tend to be characterized by greater confidence values, and therefore be filled earlier; pixels in the center of the target region will have lesser confidence values. The data term D(p) is a function of the strength of isophotes hitting the front δΩ at each iteration. This term boosts the priority of a patch that an isophote "flows" into. This factor is of fundamental importance in our algorithm because it encourages linear structures to be synthesized first, and, therefore propagated securely into the target region. Broken lines tend to connect, thus realizing the "Connectivity Principle" of vision psychology [7]  [17].
The fill order is dependent on image properties, resulting in an organic synthesis process that eliminates the risk of “broken-structure” artifacts and also reduces blocky artifacts without an expensive patch-cutting step [9] or a blur-inducing blending step [19].
Step 2: Propagating texture and structure information
Once all priorities on the fill front (boundary) have been computed, the patch Ψpˆ with highest priority is found. We then fill it with data extracted from the source region Φ. We propagate image texture by direct sampling of the source region. Similar to [10], we search in the source region for that patch which is most similar to Ψpˆ. Formally,

(source: imgup.net)
, where
the distance d(Ψa, Ψb) between two generic patches Ψa and Ψb is simply defined as the sum of squared differences (SSD) of the already filled pixels in the two patches. No further analysis or manipulation (especially no blurring) is done in this step. This calculation runs in the main cycle loop and is implemented as follows:
Getting the maximum priority:
For j = m_top To m_bottom: Jidx = j * m_width: For i = m_left To m_right
    If m_mark(Jidx + i) = -2 And m_pri(Jidx + i) > max_pri Then
        pri_x = i
        pri_y = j
        max_pri = m_pri(Jidx + i)
    End If
Next i: Next j

Finding the most similar patch:
min = 99999999

For j = PatchT To PatchB: Jidx = j * m_width: For i = PatchL To PatchR
    If m_source(Jidx + i) Then
        sum = 0
        For iter_y = -Winsize To Winsize: target_y = pri_y + iter_y
            If target_y > 0 And target_y < m_height Then
                target_y = target_y * m_width: For iter_x = -Winsize To Winsize: target_x = pri_x + iter_x
                    If target_x > 0 And target_x < m_width Then
                        Tidx = target_y + target_x
                        If m_mark(Tidx) >= 0 Then
                            source_x = i + iter_x
                            source_y = j + iter_y
                            Sidx = source_y * m_width + source_x
                            temp_r = m_r(Tidx) - m_r(Sidx)
                            temp_g = m_g(Tidx) - m_g(Sidx)
                            temp_b = m_b(Tidx) - m_b(Sidx)
                            sum = sum + temp_r * temp_r + temp_g * temp_g + temp_b * temp_b
                        End If
                    End If
                Next iter_x
            End If
        Next iter_y

        If sum < min Then: min = sum: patch_x = i: patch_y = j
    End If
Next i: Next j

Step 3: Updating confidence values
After the patch Ψpˆ has been filled with new pixel values, the confidence C(p) is updated in the area delimited by Ψpˆ as follows:

(source: imgup.net)
This simple update rule allows us to measure the relative confidence of patches on the fill front, without image-specific parameters. As filling proceeds, confidence values decay, indicating that we are less sure of the color values of pixels near the center of the target region. Implemented here (along with all other necessary updates):
x0 = -Winsize
For iter_y = -Winsize To Winsize: For iter_x = -Winsize To Winsize
    x0 = patch_x + iter_x
    y0 = patch_y + iter_y
    x1 = pri_x + iter_x
    y1 = pri_y + iter_y
    X1idx = y1 * m_width + x1
    If m_mark(X1idx) < 0 Then
        X0idx = y0 * m_width + x0
        PicAr1(x1, y1) = m_color(X0idx)
        m_color(X1idx) = m_color(X0idx)
        m_r(X1idx) = m_r(X0idx)
        m_g(X1idx) = m_g(X0idx)
        m_b(X1idx) = m_b(X0idx)
        m_gray(X1idx) = CDbl((m_r(X0idx) * 3735 + m_g(X0idx) * 19267 + m_b(X0idx) * 9765) / 32767)
        m_confid(X1idx) = ComputeConfidence(pri_x, pri_y)
    End If
Next iter_x: Next iter_y

For Y = IIf(pri_y - Winsize - 2 > 0, pri_y - Winsize - 2, 0) To IIf(pri_y + Winsize + 2 < m_height - 1, pri_y + Winsize + 2, m_height - 1): Yidx = Y * m_width: For X = IIf(pri_x - Winsize - 2 > 0, pri_x - Winsize - 2, 0) To IIf(pri_x + Winsize + 2 < m_width - 1, pri_x + Winsize + 2, m_width - 1)
    m_mark(Yidx + X) = IIf(PicAr1(X, Y).rgbRed = MaskRed And PicAr1(X, Y).rgbgreen = MaskGreen And PicAr1(X, Y).rgbBlue = MaskBlue, -1, Source)
Next X: Next Y

For Y = IIf(pri_y - Winsize - 2 > 0, pri_y - Winsize - 2, 0) To IIf(pri_y + Winsize + 2 < m_height - 1, pri_y + Winsize + 2, m_height - 1): Yidx = Y * m_width: For X = IIf(pri_x - Winsize - 2 > 0, pri_x - Winsize - 2, 0) To IIf(pri_x + Winsize + 2 < m_width - 1, pri_x + Winsize + 2, m_width - 1)
    If m_mark(Yidx + X) = -1 Then
        Found = (Y = m_height - 1 Or Y = 0 Or X = 0 Or X = m_width - 1) Or m_mark(Yidx + X - 1) = Source Or m_mark(Yidx + X + 1) = Source Or m_mark((Y - 1) * m_width + X) = Source Or m_mark((Y + 1) * m_width + X) = Source
        If Found Then: Found = False: m_mark(Yidx + X) = -2
    End If
Next X: Next Y

For i = IIf(pri_y - Winsize - 3 > 0, pri_y - Winsize - 3, 0) To IIf(pri_y + Winsize + 3 < m_height - 1, pri_y + Winsize + 3, m_height - 1): Yidx = i * m_width: For j = IIf(pri_x - Winsize - 3 > 0, pri_x - Winsize - 3, 0) To IIf(pri_x + Winsize + 3 < m_width - 1, pri_x + Winsize + 3, m_width - 1)
    If m_mark(Yidx + j) = -2 Then m_pri(Yidx + j) = ComputeConfidence(j, i) * ComputeData(j, i)
Next j: Next i

Complete Code
Here's the run-able code, complete with the libraries' source code as comments.
The code is invoked by
inpaint(infile, outfile, blocksize, windowsize, r, g, b)

Examples are included in the form of
;~ inpaint("gothic_in.png", "gothic_out.png")
;~ inpaint("starry_in.png", "starry_out.png")
;~ inpaint("scream_in.png", "scream_out.png")
;~ inpaint("mona_in.png", "mona_out.png")
;~ inpaint("maze_in.png", "maze_out.png")
;~ inpaint("checker_in.png", "checker_out.png")

just uncomment the example you want to run using CTRL+Q.
Official Test Files
This algorithm is made to be adjusted for each image. Therefore, the default values (and also the default masks) are completely suboptimal. The default values are chosen so that every sample can be processed in a reasonable amount of time. I highly recommend to play with irregularly shaped masks and better window sizes. Click the images to enlarge!
Checkerboard

(source: imgup.net)
→
(source: imgup.net)
American Gothic

(source: imgup.net)
→
(source: imgup.net)
Maze

(source: imgup.net)
→
(source: imgup.net)
Mona Lisa

(source: imgup.net)
→
(source: imgup.net)
(terrible mask)
Scream

(source: imgup.net)
→
(source: imgup.net)
Starry

(source: imgup.net)
→
(source: imgup.net)
Real-World Examples
These all use custom hand-drawn masks.

(source: imgup.net)

(source: imgup.net)

(source: imgup.net)
If you have other interesting images you'd like to see included, leave a comment.
EBII Improvements
There are multiple variants of EBII out there, created by various researchers. AnkurKumar Patel caught my attention with his collection of papers [24] on various EBII improvements.
Specifically the paper "Improved Robust Algorithm For Exemplar Based Image Inpainting" [25] mentions two improvements on the weighing of the priority values.
The improvement
The effective modification is in Step 1 (see above) of the algorithm, and extends the C(p) and D(p) effect on the priority rating for this pixel using this:
In the formula for C and D given above,  and  are respectively the normalization factor (e.g., α = 255), the isophote vector, and the unit vector orthogonal to the front  in the point p.
Further,

The priority function is defined as the weight sum of the regularized confidence term C(p) and the new data term D(p). Where α is the adjustment coefficient, satisfying 0<w<1. Finally the robust priority function Rp(p) is defined follows:

Where α and β are respectively the component weights of the confidence and the data terms. Note that α+β=1.
Objective scoring
What is really interesting though is that this paper contains a proposed (and simple!) method for scoring the performance if EBII algorithms. Take this with a grain of salt though, as this is a method chosen by the paper authors themselves to verify the effectiveness of the proposed variance approach and the improvement on several images.
The result evaluation is performed by comparing the PSNR (the Peak Signal-to-Noise Ratio [26]) between the restored image and original image. Generally the higher the PSNR value the larger the similarity of the repaired image to the original. The equation to calculate the PSNR is as follows:

These are the staggering 2 (two!) real-world test images they used:

(source: imgup.net)

(source: imgup.net)
The conclusion is as disappointing as the quality of the paper itself. It shows very little improvement. The main thing here is a possible object scoring method for this kind of challenge (and other image-repair challenges):
+-------+---------------+----------+
| Image | EBII Original | Improved |
+-------+---------------+----------+
|     1 |       52.9556 |  53.7890 |
|     2 |       53.9098 |  53.8989 |
+-------+---------------+----------+

Meh.
Research to be done
(Specific to EBII)
a) Pre-Processing
Everything comes down to the "Magic Erase" principle that the algorithm should "just work" for everything. My naive solution for this is a color-based amplification (see above), but there are better ways. I'm thinking of recognizing the geometric mean of all traceable texels to auto-adjust the window size and making the stamp size (also my improvement) dependent on texel- and whole-image resolution. Research has to be done here.
b) Post-Processing
The original authors already did a great job of debunking all post processing filters that come in mind. Today, I tried something else, inspired by the always uncanny Mona Lisa (thanks undergroundmonorail). If you take just the inpainted region and apply a new mask to all strange blocks of color and feed that into a despeckling algorithm, you're left with an almost perfect result. I may explore this some time in the future.

[X] — Object Removal by Exemplar-Based Inpainting by A. Criminisi, P. Perez, K. Toyama
[1] — M. Ashikhmin. Synthesizing natural textures. In Proc. ACM Symp. on Interactive 3D Graphics, pp. 217–226, Research Triangle Park, NC, Mar 2001.
[5] — M. Bertalmio, L. Vese, G. Sapiro, and S. Osher. Simultaneous structure and texture image inpainting. to appear, 2002
[6] —  R. Bornard, E. Lecan, L. Laborelli, and J-H. Chenot. Missing data correction in still images and image sequences. In ACM Multimedia, France, Dec 2002.
[7] — T. F. Chan and J. Shen. Non-texture inpainting by curvature-driven diffusions (CDD). J. Visual Comm. Image Rep., 4(12), 2001.
[8] — J.S. de Bonet. Multiresolution sampling procedure for analysis and synthesis of texture images. In Proc. ACM Conf. Comp. Graphics (SIGGRAPH), volume 31, pp. 361–368, 1997.
[9] — A. Efros and W.T. Freeman. Image quilting for texture synthesis and transfer. In Proc. ACM Conf. Comp. Graphics (SIGGRAPH), pp. 341–346, Eugene Fiume, Aug 2001.
[10] — A. Efros and T. Leung. Texture synthesis by non-parametric sampling. In Proc. ICCV, pp. 1033–1038, Kerkyra, Greece, Sep 1999.
[11] — W.T. Freeman, E.C. Pasztor, and O.T. Carmichael. Learning low level vision. Int. J. Computer Vision, 40(1):25–47, 2000.
[12] — D. Garber. Computational Models for Texture Analysis and Texture Synthesis. PhD thesis, Univ. of Southern California, USA, 1981.
[13] — P. Harrison. A non-hierarchical procedure for re-synthesis of complex texture. In Proc. Int. Conf. Central Europe Comp. Graphics, Visua. and Comp. Vision, Plzen, Czech Republic, Feb 2001.
[14] — D.J. Heeger and J.R. Bergen. Pyramid-based texture analysis/synthesis. In Proc. ACM Conf. Comp. Graphics (SIGGRAPH), volume 29, pp. 229–233, Los Angeles, CA, 1995.
[15] — A. Hertzmann, C. Jacobs, N. Oliver, B. Curless, and D. Salesin. Image analogies. In Proc. ACM Conf. Comp. Graphics (SIGGRAPH), Eugene Fiume, Aug 2001.
[16] — H. Igehy and L. Pereira. Image replacement through texture synthesis. In Proc. Int. Conf. Image Processing, pp. III:186–190, 1997.
[17] — G. Kanizsa. Organization in Vision. Praeger, New York, 1979.
[19] — L. Liang, C. Liu, Y.-Q. Xu, B. Guo, and H.-Y. Shum. Real-time texture synthesis by patch-based sampling. In ACM Transactions on Graphics, 2001.
[22] — L.-W. Wey and M. Levoy. Fast texture synthesis using tree-structured vector quantization. In Proc. ACM Conf. Comp. Graphics (SIGGRAPH), 2000.
[23] — A. Zalesny, V. Ferrari, G. Caenen, and L. van Gool. Parallel composite texture synthesis. In Texture 2002 workshop - (in conjunction with ECCV02), Copenhagen, Denmark, Jun 2002.
[24] — AkurKumar Patel, Gujarat Technological University, Computer Science and Engineering
[25] — Improved Robust Algorithm For Exemplar Based Image Inpainting

[26] — Wikipedia, Peak-Signal-to-Noise-Ratio

This is awesome. The Starry Night is so good. Still, that Mona Lisa...

First let me say "oh my god this is incredible". Second: I've already commented "That Mona Lisa is some SCP shit" on another question here, but that owl actually looks like something that could appear on the SCP wiki.

Can you rehost the images? It seems like all links are broken...

@mınxomaτ Uhm. Might be my network or something. NVM then.

Could the quoted paragraphs you mention be made quote blocks?

@trichoplax There are minor modifications in almost every sentence, they're not exact quotes. Consider the algorithm description the same as the org. paper except when it says modification or code. I don't want to clutter the formatting any more :)

When I tried to look at something very carefully in my dreams, sometimes things turn to be exactly like this.

How long does it run? I already waited a few minutes and I'm not sure I did it right.

@jimmy23013 I made you a ZIP for convenience. Open the wef.au3 in SciTe and run it with F5. This will take a while and produce the output files in the same directory. (If in doubt, compile the script with F7 and start wef.exe using an admin console). Either way, while it is running, the console output should look like this. As you can see it takes a while :).

It worked for the standard test cases. And it turns out that the area to be patched was too big in my images, in most cases. But it also errors for images such as a completely black one, and runs very slowly for this: http://i.stack.imgur.com/HYwXJ.png

@jimmy23013 Well, there's almost no information in that image. This algo is made for megapixel real-word photos. :). It's also very fast with the right parameters and very slow with the wrong ones. You'd probably want to write a GUI interface for trial&error.

The hand-drawn-real-world examples blew me away

Images and gist link are down

Please post images to Stack’s Imgur account, not an external service. That is the only place guaranteed to last as long as the post itself.

Matlab
This is a simple interpolation approach. The idea is first mirroring what is on each side of the patch. Then those mirror image pixels are interpolated by how close they are to the corresponding edge:

The tricky part was finding a nice interpolation weights. After some playing around I came up with a rational function that is zero on all edges except the one where we mirrored at. This is then transformed by a third degree polynomial for some smoothing:

This simple approach does surprisingly well on "natural" images, but as soon as you are confronted with sharp edges, the game is over. In the american gothic example the spikes of the hay fork line up nicely with the pixel grid, which makes it look quite nice, but it would have been much worse otherwise.
So here the results:

And finally, the code:
imgfile= 'filename.png';
maskfile = [imgfile(1:end-4),'_mask.png'];
img = double(imread(imgfile));
mask = rgb2gray(imread(maskfile));
%% read mask
xmin = find(sum(mask,1),1,'first');
xmax = find(sum(mask,1),1,'last');
ymin = find(sum(mask,2),1,'first');
ymax = find(sum(mask,2),1,'last');
%% weight transformation functiosn
third = @(x)-2* x.^3 + 3* x.^2;
f=@(x)third(x);
w=@(x,y)y.*(x-1).*(y-1)./( (x+y).*(x+1-y));

for x=xmin:xmax
    for y=ymin:ymax
        %Left Right Up Down;
        P = [img(y,xmin-(x-xmin)-1,:);img(y,xmax+(xmax-x)+1,:);img(ymin-(y-ymin)-1,x,:);img(ymax+(ymax-y)+1,x,:)];
        % normalize coordinates
        rx = (x-xmin)/(xmax-xmin);
        ry = (y-ymin)/(ymax-ymin);
        % calculate the weights
        W = [w(rx,ry),w(1-rx,ry),w(ry,rx),w(1-ry,rx)]';
        W = f(W);
        W(isnan(W))=1;
        img(y,x,:) = sum(bsxfun(@times,P,W),1)/sum(W);
    end
end
imshow(img/255);
imwrite(img/255,[imgfile(1:end-4),'_out.png']);

Mona Lisa creeps me out.

Ḿ̳̜͇͓͠o̢̎̓̀ǹ̰͎̣͙a̤̩̖̞̝ͧ̈ͤͤ ̣̖̠̮̘̹̠̾̇ͣL͉̻̭͌i̛̥͕̱͋͌ş̠͔̏̋̀ạ̫͕͎ͨͮͪ̐͡ͅ

That Mona Lisa is some SCP shit

The checkered image looks really cool IMHO.

I wouldn't be surprised if you won your own challenge with this. This is a really nice solution.

King Diamond meets Mona Lisa

Mathematica
This uses Mathematica's Inpaint function. Because Mathematica itself does all the heavy lifting, this is a community wiki.
inPaint (below) is a simple adaptation of Inpaint.
For colored paintings/photos, it uses the default, "TextureSynthesis", setting.
If it detects that the picture is black and white (because the image data of the picture is the same as the image data of the binary form of the picture), it then binarizes the image and applies the "TotalVariation" patch.
The If clause either applies Binarize or Identity to the picture. (The Identity function returns its argument unchanged.)
inPaint[picture_, mask_] :=
 If[bw = ImageData@Rasterize[Binarize[picture]] == ImageData[picture], Binarize, Identity]@
  Inpaint[picture, mask, Method -> If[bw, "TotalVariation", "TextureSynthesis"]]

The image and mask are entered as arguments to inPaint. Partition and Grid are merely for formatting purposes.

The outputs have been patched.  There was no retouching of the images after inPaint.

It might be a coincidence, but I'm amazed about the performance of the labyrinth!

@flawr I'd throw in something like this just to mess with this solution;) (Who knows? Those black-and-whites really are baffling.)

I don't think this should be a community wiki.

lawr, Yes, Inpaint seems to look for symmetries across the whole black and white image. – DavidC 9 hours ago

Are you sure the black-and-white algorithm doesn't involve sacrificing goats anywhere? How ---on Earth--- the hell does it guess the central structure of the image, if all of it is masked??

I agree with Dennis. This is worth the rep you'd gain...

@mbomb007, I would consider having it treated as regular submission but I don't believe it is possible to reclassify it.

Andras, I'm also puzzled by how it fills in unique regions of the black and white images.  I'll experiment with that more systematically to see what I can find out.

Python 2 and PIL
This program blends copies of regions North, South, East, and West to create replacement pixels that use colours, textures, and shading from the local image region.
The example outputs:

The code first finds the bounding box for the patch. Then for each pixel to be generated, it computes the colour of each channel (RGB) based on the weighted sum of the 4 surrounding regions.
import sys
from PIL import Image

infile, maskfile, outfile = sys.argv[1:4]
imageobj = Image.open(infile)
maskobj = Image.open(maskfile)
image = imageobj.load()
mask = maskobj.load()

assert imageobj.size == maskobj.size
W, H = imageobj.size
pixels = [(x,y) for x in range(W) for y in range(H)]
whitepart = [xy for xy in pixels if sum(mask[xy]) > 230*3]
xmin = min(x for x,y in whitepart)
xmax = max(x for x,y in whitepart)
ymin = min(y for x,y in whitepart)
ymax = max(y for x,y in whitepart)
xspan = xmax - xmin + 1
yspan = ymax - ymin + 1

def mkcolor(channel):
    value = image[(xmin-dx, y)][channel] * 0.5*(xspan - dx)/xspan
    value += image[(xmax+1 + xspan - dx, y)][channel] * 0.5*dx/xspan
    value += image[(x, ymin-dy)][channel] * 0.5*(yspan - dy)/yspan
    value += image[(x, ymax+1 + yspan - dy)][channel] * 0.5*dy/yspan
    return int(value)

for dx in range(xspan):
    for dy in range(yspan):
        x = xmin + dx
        y = ymin + dy
        image[(x, y)] = (mkcolor(0), mkcolor(1), mkcolor(2))

imageobj.save(outfile)

This Mona Lisa is also terrifying! Are all Mona Lisas in this challenge doomed to be scary??

@undergroundmonorail I guess computer-generated accidental faces come right from the depths of the uncanny valley.

Where do you get PIL from?

@ElliotA. My understanding is that PIL proper is dead, but it was open source and so it lives on under the name "Pillow". If you google "python pillow" you should find it.

Python 3, PIL
This program uses the sobel operator, and draws lines onto the image based on that.
The sobel operator finds the angle of each edge, so any edges extruding into the unknown area should continue.
from PIL import Image, ImageFilter, ImageDraw
import time
im=Image.open('2.png')
im1=Image.open('2 map.png')
a=list(im.getdata())
b=list(im1.getdata())
size=list(im.size)
'''
def dist(a,b):
    d=0
    for x in range(0,3):
        d+=(a[x]-b[x])**2
    return(d**0.5)
#'''
C=[]
d=[]
y=[]
for x in range(0,len(a)):
    if(b[x][0]==255):
        C.append((0,0,0))
    else:
        y=(a[x][0],a[x][1],a[x][2])
        C.append(y)
im1.putdata(C)
k=(-1,0,1,-2,0,2,-1,0,1)
k1=(-1,-2,-1,0,0,0,1,2,1)
ix=im.filter(ImageFilter.Kernel((3,3),k,1,128))
iy=im.filter(ImageFilter.Kernel((3,3),k1,1,128))
ix1=list(ix.getdata())
iy1=list(iy.getdata())
d=[]
im2=Image.new('RGB',size)
draw=ImageDraw.Draw(im2)
c=list(C)
Length=0
for L in range(100,0,-10):
    for x in range(0,size[0]):
        for y in range(0,size[1]):
            n=x+(size[0]*y)
            if(c[n]!=(0,0,0)):
                w=(((iy1[n][0]+iy1[n][1]+iy1[n][2])//3)-128)
                z=(((ix1[n][0]+ix1[n][1]+ix1[n][2])//3)-128)
                Length=(w**2+z**2)**0.5
                if Length==0:
                    w+=1
                    z+=1
                Length=(w**2+z**2)**0.5
                w/=(Length/L)
                z/=(Length/L)
                w=int(w)
                z=int(z)
                draw.line(((x,y,w+x,z+y)),c[n])

d=list(im2.getdata())
S=[]
d1=[]
A=d[0]
for x in range(0,size[0]):
    for y in range(0,size[1]):
        n=y+(size[1]*x)
        nx=y+(size[1]*x)-1
        ny=y+(size[1]*x)-size[0]
        if d[n]==(0,0,0):
            S=[0,0,0]
            for z in range(0,3):
                S[z]=(d[nx][z]+d[ny][z])//2
            #print(S)
            d1.append(tuple(S))
        else:
            d1.append(tuple(d[n]))
d=list(d1)
im2.putdata(d)
#im2=im2.filter(ImageFilter.GaussianBlur(radius=0.5))
d=im2.getdata()
f=[]
#'''
for v in range(0,len(a)):
    if(b[v][0]*b[v][1]*b[v][2]!=0):
        f.append(d[v])
    else:
        f.append(C[v])
#'''
im1.putdata(f)
im1.save('pic.png')

Meanwhile, here are the sample images.

Mona Lisa  Mona Lisa  Ḿ͠oǹ̰͎̣a ̾̇Lisa  Ḿ͠o̢̎̓̀ǹ̰͎̣aͧ̈ͤ ̣̖̠̮̘̹̠̾̇ͣLisa  Ḿ̳̜͇͓͠o̢̎̓̀ǹ̰͎̣͙a̤̩̖̞̝ͧ̈ͤͤ ̣̖̠̮̘̹̠̾̇ͣL͉̻̭͌i̛̥͕̱͋͌ş̠͔̏̋̀ạ̫͕͎ͨͮͪ̐͡ͅ

The area in the above image is as smooth as a cactus
It is not very good with constant color.

"...'cause baby you're a fiiiirewooork..." I like that totally new approach. The patches of the first two really just fit into the image! The only unsovled thing are perhaps the sharp edges of the patch. And sometimes I cannot really see where the colour of such and edge is coming from. It also seems the right side is always painted last, perhaps you can alternate which side is worked one. Another suggestion: Insted of stright lines, you could fit polynomials/bezier curves to those lines and exctend them in a not so straight way!

Oh, and could you please add the B/W test cases?

Looks really good on the Starry Night one.

Wow, this looks incredible now! The patches are still noticeable but a great new idea! My favourite so far=)

+1 for "  Mona Lisa Mona Lisa Ḿ͠oǹ̰͎̣a ̾̇Lisa Ḿ͠o̢̎̓̀ǹ̰͎̣aͧ̈ͤ ̣̖̠̮̘̹̠̾̇ͣLisa Ḿ̳̜͇͓͠o̢̎̓̀ǹ̰͎̣͙a̤̩̖̞̝ͧ̈ͤͤ ̣̖̠̮̘̹̠̾̇ͣL͉̻̭͌i̛̥͕̱͋͌ş̠͔̏̋̀ạ̫͕͎ͨͮͪ̐͡ͅ  "

You win the "scariest Mona Lisa" contest, IMO. 0_o

Python 2
Simple python script that creates patch using values from pixels just outside gap. It takes color values from end of pixels' row and column and calculates weighted average using distance from those pixels.
Output is not so pretty, but it's art.

And then, code:
IMGN = "6"

IMGFILE = "images/img%s.png" % (IMGN,)
MASKFILE = "images/img%s_mask.png" % (IMGN,)

BLUR = 5

def getp(img,pos):
    return img.get_at(pos)[:3]
def setp(img,pos,color):
    img.set_at(pos, map(int, color))

def pixelavg(L):
    return map(int, [sum([i[q] for i in L])/float(len(L)) for q in [0,1,2]])
def pixelavg_weighted(L, WL):   # note: "inverse" weights. More weight => less weight
    # colors [sum, max]
    color_data = [[0, 0], [0, 0], [0, 0]]
    for color,weight in zip(L, WL):
        for i in [0, 1, 2]: # r,g,b
            color_data[i][0] += inv_w_approx(weight) * color[i]
            color_data[i][1] += inv_w_approx(weight) * 255
    return [255*(float(s)/m) for s,m in color_data]
def inv_w_approx(x):
    return (1.0/(x+1e-10))

import pygame
image = pygame.image.load(IMGFILE)
mask = pygame.image.load(MASKFILE)

size = image.get_size()
assert(size == mask.get_size())

# get square from mask
min_pos = None
max_pos = [0, 0]
for x in range(size[0]):
    for y in range(size[1]):
        if getp(mask, [x, y]) == (255, 255, 255):
            if min_pos == None:
                min_pos = [x, y]
            max_pos = [x, y]
if not min_pos:
    exit("Error: no mask found.")
# patch area info
patch_position = min_pos[:]
patch_size = [max_pos[0]-min_pos[0], max_pos[1]-min_pos[1]]

# remove pixels from orginal image (fill black)
for dx in range(patch_size[0]):
    for dy in range(patch_size[1]):
        setp(image, [patch_position[0]+dx, patch_position[1]+dy], [0, 0, 0])

# create patch
patch = pygame.Surface(patch_size)

# take pixels around the patch
top = [getp(image, [patch_position[0]+dx, patch_position[1]-1]) for dx in range(patch_size[0])]
bottom = [getp(image, [patch_position[0]+dx, patch_position[1]+patch_size[1]+1]) for dx in range(patch_size[0])]
left = [getp(image, [patch_position[0]-1, patch_position[1]+dy]) for dy in range(patch_size[1])]
right = [getp(image, [patch_position[0]+patch_size[0]+1, patch_position[1]+dy]) for dy in range(patch_size[1])]

cpixels = top+left+right+bottom

# set area to average color around it
average = [sum([q[i] for q in cpixels])/float(len(cpixels)) for i in [0, 1, 2]]

for dx in range(patch_size[0]):
    for dy in range(patch_size[1]):
        setp(patch, [dx, dy], average)

# create new pixels
for dx in range(patch_size[0]):
    for dy in range(patch_size[1]):
        setp(patch, [dx, dy], pixelavg_weighted([top[dx], bottom[dx], left[dy], right[dy]], [dy, patch_size[1]-dy, dx, patch_size[0]-dx]))

# apply patch
for dx in range(patch_size[0]):
    for dy in range(patch_size[1]):
        setp(image, [patch_position[0]+dx, patch_position[1]+dy], getp(patch, [dx, dy]))

# blur patch?
for r in range(BLUR):
    for dx in range(patch_size[0]):
        for dy in range(patch_size[1]):
            around = []
            for ddx in [-1,0,1]:
                for ddy in [-1,0,1]:
                    around.append(getp(image, [patch_position[0]+dx+ddx, patch_position[1]+dy+ddy]))
            setp(patch, [dx, dy], pixelavg(around))

    # apply blurred patch
    for dx in range(patch_size[0]):
        for dy in range(patch_size[1]):
            setp(image, [patch_position[0]+dx, patch_position[1]+dy], getp(patch, [dx, dy]))

# save result
pygame.image.save(image, "result.png")

At the moment you see those horizontal/vertical stripes, perhaps you can improve it by including other directions!

I actually tried it, but I was unable to get good results, so I just decided just to blur image :D

Finally, a Mona Lisa that doesn't scare me to death, but looks like an arrested murderer instead.

Mathematica
Inpaint

It just so happens that Mathematica has a built-in function that performs exactly this task, and I mean exactly:

Inpaint[image, region]

retouches parts of image that correspond to nonzero elements in region.

By default it uses a "best-fit texture synthesis method using random sampling" which produces good results on the paintings, but poor results for the maze and checkerboard:

Playing around with the settings didn't net me an increase in quality across all of the images, so I just used the defaults (to save bytes—this is codegolf.se after all!).

"It just so happens that Mathematica has a built-in function"... surprise, surprise;)

For the maze and checker board it's better to use the "TotalVariation" method along with Binarize (to eliminate gray smudges).  Try this:  methods = {"TextureSynthesis", "Diffusion", "FastMarching",     "NavierStokes", "TotalVariation"};g[pic_, mask_] :=   Join[{Labeled[Framed@pic, "Original"]},    Labeled[ Binarize@Inpaint[pic, mask, Method -> #], #] & /@ methods]

@DavidC I tried the other methods, but only TextureSynthesis looks good on the paintings; and I don't think we're allowed to tune our settings for each individual test case.  (If we could, then we could trivially supply the missing portion as a 'setting'.)

The maze and checkerboard results are really puzzling to me. Why is Mathematica's reconstruction of the missing region so irregular and asymmetric?

This will automatically detect whether an image is black and white and make the appropriate adjustments (binaries and "TotalVariation" method).  inPaint[picture_, mask_] :=  If[bw = ImageData@Rasterize[Binarize[picture]] == ImageData[picture],     Binarize, Identity]@   Inpaint[picture, mask,     Method -> If[bw, "TotalVariation", "TextureSynthesis"]]

@DavidC You should post that as your own answer!

In this case I think it's better to have just one answer.  Maybe make this a community wiki?  (By the way: This is not code-golf; it's a popularity-contest. So the size of the code is not at issue. )

Python3
This answer implements the idea in the paper "Deep Image Prior" by Ulyanov et al. (CVPR 2018) In this paper they explored the idea that the way well performing neural nets for image processing are designed closely reflects our idea of what a natural image should look like (the "prior" distribution).
They proposed a method that can be used for inpainting as well as noise and artifact removal that just uses the given image with no training on any other data. The actual concept is quite simple: The net is trained to output the desired image (for some fixed random noise as input) by penalizing only the erros outside some given mask. If you want to remove noise, you just don't need to mask anything, but just stop early in the training.
For inpainting you mask the part you want to inpaint and train until convergence. It is certainly not state-of-the-art, but I still wanted to post try it and post it here due to the simplicity of the idea and the still remarkable performance. In my experiments the inpainting of larger patches didn't turn out that well but for smaller segments the results can be a lot more convincing.
I implemented this using the popular U-Net architecture from jaxony on github. The code for training and processing the images can be found below.
Training
This is a visualization of the training process. Every frame is the state ofter a certain number of iterations:

Examples

Code
Note that on a cpu this can take hours to run for just a single image, while a good cuda enabled gpu might take a lot less time.
import torch
import numpy as np
unet = __import__('unet-pytorch')
import PIL.ImageOps
#specify device (cpu/cuda)
device = "cpu"
#specify file and size
file = 'mona'
size = 512 #pad to this size (no smaller than original image), must be divisible by 2^5
img_pil = PIL.Image.open(file +'.png').convert('RGB')
mask_pil = PIL.Image.open(file +'-mask.png').convert('RGB')

net = unet.UNet(num_classes=3, in_channels=32, depth=6, start_filts=64).to(device)
h,w = img_pil.size
pad = (0, 0, size - h, size - w)
img = PIL.ImageOps.expand(img_pil, border=pad)
img = torch.Tensor(np.array(img).transpose([2, 0, 1])[None, :, :, :].astype(np.double)).to(device)
mask = PIL.ImageOps.expand(mask_pil, border=pad)
mask = torch.Tensor((np.array(mask)==0).transpose([2, 0, 1])[None, 0:3, :, :].astype(np.double)).to(device)
mean = img.mean()
std = img.std()
img = (img - mean)/std
optimizer = torch.optim.Adam(net.parameters(), lr=0.0001)
criterion = torch.nn.MSELoss()
input = torch.rand((1, 32, size, size)).to(device)
for it in range(5000):
    if it == 1000:
        optimizer.param_groups[0]['lr'] = 0.00003
    out = net(input)
    loss = criterion(out * mask, img * mask)
    optimizer.zero_grad()
    loss.backward()
    optimizer.step()
out = out.detach().cpu().numpy()[0].transpose([1,2,0])*std.item() + mean.item()
out = np.clip(out, 0, 255).astype(np.uint8)[0:w, 0:h, :]
mask_np = (np.array(mask_pil) > 0).astype(np.uint8)
img_np = np.array(img_pil)
inpaint = (img_np * (1-mask_np) + mask_np * out).astype(np.uint8)
PIL.Image.fromarray(inpaint).save('./{}_inpainted.png'.format(file))

does Deep Image Prior use something different from U-Nets? seems like they'd get better results

Also, have you tried with Deep Image Prior's code

@ASCII-only They state in the paper that they do indeed mainly use the U-Net, but I cannot find the exact parameters they used. They might have used a net with a greater capacity. I only had a computer with a very limited amount of power. So I had to choose parameters that still fit into the memory and that didn't take too long to train. I'm not sure how long exactly it took but on the computer I used (only with a CPU) these images take multiple days. (If you have a spare cuda enabled GPU let me know :)

I also suspect that due to the design of the network having rectangular masks is also not ideal (and smaller masks would probably also look better), if you compare for example the first few images to the last two (that do not use rectangular masks).

Python with OpenCV
OpenCV has a function called inpaint. There are two types of inpainting used, I will use the Fast Marching Method. According to the documentation, the algorithm works like this:

Consider a region in the image to be inpainted. Algorithm starts from the boundary of this region and goes inside the region gradually filling everything in the boundary first. It takes a small neighbourhood around the pixel on the neigbourhood to be inpainted. This pixel is replaced by normalized weighted sum of all the known pixels in the neigbourhood. Selection of the weights is an important matter. More weightage is given to those pixels lying near to the point, near to the normal of the boundary and those lying on the boundary contours. Once a pixel is inpainted, it moves to next nearest pixel using Fast Marching Method. FMM ensures those pixels near the known pixels are inpainted first, so that it just works like a manual heuristic operation.

Here is the code*:
import numpy as np
import cv2
from matplotlib import pyplot as plt
img = cv2.imread('gothic.jpg')
b,g,r = cv2.split(img)
img2 = cv2.merge([r,g,b])
mask = cv2.imread('mask.jpg',0)
dst = cv2.inpaint(img2,mask,3,cv2.INPAINT_TELEA)
(h, w) = dst.shape[:2]
center = (w / 2, h / 2)
# rotate the image by 180 degrees
M = cv2.getRotationMatrix2D(center, 180, 1.0)
rotated = cv2.warpAffine(dst, M, (w, h))
plt.imshow(rotated)

Note how I convert the BGR to RGB for plotting reasons. Also, I rotate it. Here are the results:

Mona Lisa returns!

As you can see, it i not the best with the two color ones.

Mona Lisa got a facelift

Java
A color averaging approach. Can probably be improved.
import java.awt.Color;
import java.awt.image.BufferedImage;
import java.io.File;
import java.util.Scanner;

import javax.imageio.ImageIO;

public class ImagePatcher{
    public static void main(String[]args) throws Exception{
        Scanner in=new Scanner(System.in);
        int white=Color.WHITE.getRGB();
        int black=Color.BLACK.getRGB();
        BufferedImage image=ImageIO.read(new File(in.nextLine())),mask=ImageIO.read(new File(in.nextLine()));
        assert(image.getWidth()==mask.getWidth()&&image.getHeight()==mask.getHeight());
        boolean bool=true;
        while(bool){
            bool=false;
        for(int x=0;x<image.getWidth();x+=2){
            for(int y=0;y<image.getHeight();y+=2){
                if(mask.getRGB(x,y)!=white)continue;
                int r=0,g=0,b=0,n=0;
                for(int dx=-1;dx<=1;dx++){
                    if(x+dx<0)continue;
                    if(x+dx>=image.getWidth())continue;
                    for(int dy=-1;dy<=1;dy++){
                        if(y+dy<0)continue;
                        if(y+dy>=image.getHeight())continue;
                        if(mask.getRGB(x+dx,y+dy)==white)continue;
                        Color c=new Color(image.getRGB(x+dx,y+dy));
                        r+=c.getRed();
                        g+=c.getGreen();
                        b+=c.getBlue();
                        n++;
                    }
                }
                if(n==0){bool=true;continue;}
                Color c=n>0?new Color(r/n,g/n,b/n):new Color(100,100,100);
                image.setRGB(x,y,c.getRGB());
                mask.setRGB(x, y, black);
            }
        }
        for(int x=0;x<image.getWidth();x+=2){
            for(int y=1;y<image.getHeight();y+=2){
                if(mask.getRGB(x,y)!=white)continue;
                int r=0,g=0,b=0,n=0;
                for(int dx=-1;dx<=1;dx++){
                    if(x+dx<0)continue;
                    if(x+dx>=image.getWidth())continue;
                    for(int dy=-1;dy<=1;dy++){
                        if(y+dy<0)continue;
                        if(y+dy>=image.getHeight())continue;
                        if(mask.getRGB(x+dx,y+dy)==white)continue;
                        Color c=new Color(image.getRGB(x+dx,y+dy));
                        r+=c.getRed();
                        g+=c.getGreen();
                        b+=c.getBlue();
                        n++;
                    }
                }
                if(n==0){bool=true;continue;}
                Color c=n>0?new Color(r/n,g/n,b/n):new Color(100,100,100);
                image.setRGB(x,y,c.getRGB());
                mask.setRGB(x, y, black);
            }
        }
        for(int x=1;x<image.getWidth();x+=2){
            for(int y=0;y<image.getHeight();y+=2){
                if(mask.getRGB(x,y)!=white)continue;
                int r=0,g=0,b=0,n=0;
                for(int dx=-1;dx<=1;dx++){
                    if(x+dx<0)continue;
                    if(x+dx>=image.getWidth())continue;
                    for(int dy=-1;dy<=1;dy++){
                        if(y+dy<0)continue;
                        if(y+dy>=image.getHeight())continue;
                        if(mask.getRGB(x+dx,y+dy)==white)continue;
                        Color c=new Color(image.getRGB(x+dx,y+dy));
                        r+=c.getRed();
                        g+=c.getGreen();
                        b+=c.getBlue();
                        n++;
                    }
                }
                if(n==0){bool=true;continue;}
                Color c=n>0?new Color(r/n,g/n,b/n):new Color(100,100,100);
                image.setRGB(x,y,c.getRGB());
                mask.setRGB(x, y, black);
            }
        }
        for(int x=1;x<image.getWidth();x+=2){
            for(int y=1;y<image.getHeight();y+=2){
                if(mask.getRGB(x,y)!=white)continue;
                int r=0,g=0,b=0,n=0;
                for(int dx=-1;dx<=1;dx++){
                    if(x+dx<0)continue;
                    if(x+dx>=image.getWidth())continue;
                    for(int dy=-1;dy<=1;dy++){
                        if(y+dy<0)continue;
                        if(y+dy>=image.getHeight())continue;
                        if(mask.getRGB(x+dx,y+dy)==white)continue;
                        Color c=new Color(image.getRGB(x+dx,y+dy));
                        r+=c.getRed();
                        g+=c.getGreen();
                        b+=c.getBlue();
                        n++;
                    }
                }
                if(n==0){bool=true;continue;}
                Color c=n>0?new Color(r/n,g/n,b/n):new Color(100,100,100);
                image.setRGB(x,y,c.getRGB());
                mask.setRGB(x, y, black);
            }
        }
        };
        ImageIO.write(image, "png", new File("output.png"));
    }
}

Results:

Why do you always get lines in this particular angle? The top left corners seem to match relatively well, while the bottom right part does not match at all.

I think it has to do with the manner  in which I iterate through the region. I'll probably change that eventually.

It always looks like there are trapezoids.

@ericw31415 It's an artifact of the iteration order.

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/