Laurent Bienvenu

Rupert Hölzl

Adam R Day

From Bi-immunity to Absolute Undecidability

come

Introduction

Let A ∈ 2 ω be a non-computable infinite binary sequence. How can we gauge the extent to which A is close to being computable? Many basic concepts in computability theory can be seen as providing a partial answer to this question. For example, if A is low, ∆ 0 2 , or of minimal degree, then A could be seen as being close to computable.

In this paper, we will consider a different perspective. Given A and a partial computable function ϕ we will say A extends ϕ if for all x ∈ dom(ϕ), A(x) = ϕ(x) (where A(n) is the value of the n-th bit of A). We will measure how close A is to being computable by considering the size of the domain of any partial computable function that A extends (the larger the domain, the closer A is to being computable).

A set A is bi-immune if neither A nor its complement contain an infinite c.e. (or, equivalently, computable) subset. It is not difficult to see that A is bi-immune if and only if A * This work was done as part of the France-Berkeley project Algorithmic randomness for non-uniform measures.

† Day was supported by a Miller Research Fellowship in the Department of Mathematics at the University of California, Berkeley.

‡ Hölzl was supported by a Feodor Lynen postdoctoral research fellowship by the Alexander von Humboldt Foundation.

1

does not extend a partial computable function with infinite domain. Hence, from this paper's perspective, bi-immune sets are as far from computable as possible. Once bi-immune sets are shown to exist, the property of being bi-immune is clearly not invariant under Turing equivalence. However, it does make sense to ask whether every non-zero Turing degree contains a bi-immune set. The answer is no.

Theorem 1 (Jockusch [START_REF] Jockusch | The degrees of bi-immune sets[END_REF]). There exists a non-zero Turing degree such that no element of this degree is bi-immune.

To determine whether a sequence A is bi-immune, we asked whether A extends a partial computable function with infinite domain. Essentially, bi-immunity regards the domain of a partial computable function as large, if it is infinite. We can weaken the notion of biimmunity by strengthening our concept of largeness. When the upper density of D is zero, we simply say that D has density 0.

Definition 3 ). We say that A ∈ 2 ω is absolutely undecidable if there is no partial computable function ϕ : N → {0, 1} whose domain has positive upper density and such that ϕ(n) = A(n) for all n in the domain of ϕ.

The notion of absolute undecidability comes from the study of generic computability [START_REF] Downey | Asymptotic density and computably enumerable sets[END_REF][START_REF] Jockusch | Generic computability, Turing degrees, and asymptotic density[END_REF][START_REF] Kapovich | Generic-case complexity, decision problems in group theory, and random walks[END_REF]. A sequence A ∈ 2 ω is generically computable if can be "computed modulo a set of density 0", i.e., if there is a partial computable function ϕ such that ϕ(n) = A(n) for all n in the domain of ϕ, and ρ(N \ dom(ϕ)) = 0. Absolute undecidability is the antithesis of generic computability; a set is absolutely undecidable if it cannot be computed at all, modulo a set of positions of density 0.

In Downey, Jockusch and Schupp [START_REF] Downey | Asymptotic density and computably enumerable sets[END_REF], the following question is asked.

Question 4. Does every non-zero Turing degree contain a set which is absolutely undecidable?

In other words, does Theorem 1 fail if we weaken bi-immunity to absolute undecidability? We give a positive answer to this question in Theorem 5. In fact every non-zero truth-table degree contains a sequence which is absolutely undecidable.

Theorems 1 and 5 show that an interesting dichotomy exists between bi-immunity and absolute undecidability. In Section 4, of this paper we investigate what happens between these two notions.

To express this idea precisely, we need to introduce some definitions. For a function

h : N → R >0 , denote by o(h) the set of functions f : N → R such that lim n→∞ f (n)/h(n) = 0.
In particular, write o(n) for o(g) when g is the function n → n. Given D ⊆ N, define κ D : n → |D ∩ {0, . . . , n -1}| and ρ D : n → κ D (n)/n. Theorem 5 is a uniform version of the following statement.

Every non-zero truth-table degree contains an element X such that if ϕ is a partial computable function and X extends ϕ then κ dom(ϕ) ∈ o(n).

To determine what happens between bi-immunity and absolute undecidability, we can ask whether this statement can be strengthened by replacing o(n) with a smaller set of functions. In particular, is this statement still true if we replace o(n) with o(h) for some computable function h ∈ o(n) e.g. n/ log log n?

We will show that the statement cannot be strengthened in this manner. If h is a computable function and h(n) ∈ o(n), then there is a non-zero Turing degree a such that for all sets X ≤ T a, X extends a partial computable function g with κ dom(g) ∈ o(h). In fact we will construct a single Turing degree that works for all such h. This is the content of Theorem 11. Hence the threshold where the behavior changes between bi-immunity and absolute undecidability occurs right at the absolute undecidability end.

Theorem 11 is proved using forcing with computable perfect trees. The structure of this proof is similar to that of Jockusch's proof of Theorem 1 [START_REF] Jockusch | The degrees of bi-immune sets[END_REF], but requires some extra machinery to deal with density.

Coding Theory and Absolute Undecidability

Our objective in this section and the following section, is to answer Question 4 by proving the following theorem.

Theorem 5. There exists a tt-functional Φ such that for every non-computable sequence A ∈ 2 ω , Φ A is absolutely undecidable and Φ A ≡ tt A.

Let us present the structure of our proof. We will show how to encode any sequence A via a tt-reduction Φ into a sequence B in such a way that A can be fully recovered (by another tt-reduction) given B on a set of positive upper density. If A is non-computable, then B = Φ A is necessarily absolutely undecidable. Otherwise, B would extend a partial computable function ϕ with domain a set of positive upper density and thus A could be computed using ϕ.

Our proof will have an element of non-uniformity. Instead of reproducing the set A exactly (given B on a set of positive upper density) we will produce a computable tree of bounded width having A as a path. This is sufficient because any path through a computable tree of bounded width is itself computable. Theorem 10 shows that this non-uniformity cannot be avoided, and, in fact, that even any finite number of decoding procedures do not suffice to decode an arbitrary set A. This is shown to hold for an arbitrary coding scheme, not just for the specific scheme Φ used in the proof of Theorem 5.

The functional Φ is built upon an error correcting code known as a Walsh-Hadamard code (see, e.g. Arora and Barak [START_REF] Arora | Computational complexity[END_REF]Section 19.2.2]). An error correcting code maps finite strings to finite strings, thus for our purposes we will have to use the Walsh-Hadamard code iteratively. On input A, for all n, the initial segment (or prefix) of A of length n, which we denote by A↾n, is encoded into a string σ n . The image of A under Φ will be the sequence B = σ 1 σ 2 σ 3 . . . . Ideally we would like a computable sequence of functions {f n } n∈N , where f n is a function from binary strings of length n to binary strings of some length k n with the following property. For any δ > 0, for all sufficiently large n, for all strings σ of length n, any ⌊δ • k n ⌋ bits of f (σ) uniquely determines σ. In coding theory, such an coding is called an erasure code: one encodes a string σ into τ = f (σ) in such a way that σ can be recovered from any subset τ ′ of the bits of τ of sufficiently large size (think of τ ′ as a version of τ where some of the bits are missing, say replaced with '?', but those that are given are correct).

If there was such a coding, we could prove Theorem 5 by defining B to be equal to

f 1 (A↾1)f 2 (A↾2)f 4 (A↾4)f 8 (A↾8) . . . .
This would be sufficient to prove the theorem, because given B on a set of positive upper density, for some δ, for infinitely many n we would have ⌊δ • k n ⌋ bits of f n (A↾n) allowing us to reconstruct A↾n for these n, and hence reconstruct A itself. Unfortunately, this is too much to ask for. There is a theoretical limit to recovering an encoded string unambiguously from a small fraction of the bits of its encoding. 1 For simplicity let us say that we only want to encode three different strings σ 1 , σ 2 , σ 3 into codewords τ 1 , τ 2 , τ 3 . Without loss of generality we can assume that the codewords all have the same length m. For each position i ≤ m, at least two codewords agree on the bit number i. Thus, by the pigeonhole principle, there exist two strings among τ 1 , τ 2 , τ 3 that agree on at least one third of their bits.

This seems to defeat the plan of retrieving the original string from a small fraction of the bits of its encoding, as the simple example above shows that any fraction smaller that 1/3 is insufficient in general. The solution to this problem is to use another concept from coding theory: list decoding. In the remainder of this section we will review these concepts and explain how they can be used to prove Theorem 5. However, we appreciate that some readers will not have a background in coding theory, so in the following section we will give a proof of Theorem 5 using basic facts about vector spaces, that assumes no prior knowledge of coding theory.

A list decodable code is an error correcting coding scheme such that, if the codeword z for a string x is known without too many errors, one can produce a small list of strings to which x belongs. Define the (normalized) Hamming distance between two words of equal length n as d H (x, y) := #{i | x(i) = y(i)}/n. The minimum distance of a coding scheme is the minimum normalized Hamming distance between two distinct codewords. List decodable codes ensure that a ball (in Hamming distance) around a codeword contains only a small number of other codewords. This means that a codeword can be decoded into a small number of possible strings. In our case this number will be constant, which will allow us to build a computable tree of bounded width.

The Walsh-Hadamard code, which we define in the next section, maps words of length n to codewords of length 2 n . In [1, Section 19.2.2] it is shown that this is a code with minimum distance 1/2, i.e., any two codewords x, y disagree on at least half of their bits. Assume we have a "corrupted" version of a codeword that could either be x or y, where corrupted means that some bits b have been replaced by 1b. Assume that we are guaranteed that the corruption has only happened on at most a quarter of all bits. Then we can be sure that less than half of the bits where x and y disagree have been corrupted, so we can make a majority vote on those bits to decide whether the given corrupted codeword came from x or y. This is completely insufficient for our purposes, of course, since in our construction we will in general only be guaranteed a much smaller fraction ε ≪ 1/4 of bits of the codeword. But we can apply the following theorem:

Theorem 6 (Johnson bound (see, e.g., [START_REF] Arora | Computational complexity[END_REF])). If E : {0, 1} n → {0, 1} m is an error correcting code of minimum distance at least 1/2, then for every x ∈ {0, 1} m and δ ≥ 0, there exist at most l = 1/(2δ 2 ) elements y 1 , . . . , y l elements of {0,

1} n such that d H (x, E(y i )) ≤ 1/2 -δ for all i.
In other words, if we have a corrupt version z ′ of a codeword z = E(y), which is good enough in the sense that a fraction 1/2 + δ of the bits of z ′ coincide with those of z, we can generate from z ′ a list of size 1/(2δ 2 ) of possible candidates for y which will indeed contain y.

In our case, we do not have such a z ′ , but we have instead a fraction δ of bits of z which we are sure are correct and we know their position in z. As we explained above, what we need for this situation is an erasure code.

The following argument shows that we can still use the Walsh-Hadamard code in this context. Imagine we know a fraction δ of the bits of a codeword z for the original word y, together with their respective positions in z. Now fill all the remaining positions with 0's to get a codeword z 0 and with 1's to get a codeword z 1 . Perform a list-decoding on both z 0 and z 1 , thus getting two lists of possible candidates of size 1/(2δ 2 ). Merge the two lists; the resulting list has size at most 2 • 1/(2δ 2 ) = 1/δ 2 . Note that the correct entry is on the list since either z 0 or z 1 must have a fraction at least 1/2 + δ of its bits in common with z, so the list contains the original word y.

output from all linear functionals from {0, 1} 3 to {0, 1} with argument abc. (Note that we do not include the zero functional in this example.) Given any a, b, c ∈ {0, 1} assume we are given 3 bits of f 3 (abc), e.g. the zeroth bit is 1, the fourth bit is 0 and sixth bit is 1. The zeroth bit tells us that a = 1, the fourth bit tells us that b + c = 0, the six bit is redundant information because we already know that a + b + c = 1 from the zeroth and fourth bit. Nevertheless, we can determine that abc ∈ {100, 111} i.e. we know that abc is one of two possibilities. Further, no matter which 3 bits we are given, we are always guaranteed two 'independent' pieces of information and hence if we cannot determine abc, we can always show that there are only two possible values it could take.

What is remarkable is how this example scales. If we define f n in a similar manner for all n, then for any string σ of length n, given 1/4 of bits of f n (σ) we can find a set of size at most two that σ must belong to. Crucially, the maximum size of the set does not depend on n, but only the fraction of the bits we have access to, in this case 1/4.

Let V be a vector space of dimension n over a finite field F of cardinality q. Note that in this paper we are only concerned with the case that q = 2, but we will present the argument in its general form. Denote by V * the dual space of V , i.e., the set of linear functionals from V to F. In the example above, we were given the values of some bits of f n (a, b, c). Each bit told us two things, the position of the bit told us the linear functional used, and the value of the bit told us the value of the linear functional on the argument abc. We can represent this information as a subset S of pairs in (ϕ, z) ∈ V * × F. For any x ∈ V , let

C x = {(ϕ, ϕ(x)) ∈ V * × F | ϕ ∈ V * }.
The set C x simply records the values x takes on each linear functional in V * . Now if S ⊆ C x , then for all (ϕ, z) ∈ S, we have that ϕ(x) = z i.e. the values that x takes on the linear functionals in V * is consistent with the information provided by S.

Proposition 7. Let V , n, F, q, V * and C x be defined as above. For any finite set S of pairs (ϕ, z) ∈ V * × F, the set A S = {x | S ⊆ C x } has cardinality at most q n /|S|.

Proof. Fix a finite set S of pairs (ϕ, z) ∈ V * × F. If A S = ∅ then the result holds trivially so let us assume that A s is not empty and fix some element x 0 ∈ A S . If some ψ appears in two different pairs (ψ, z 1 ) and (ψ, z 2 ) of S, then it is clear that A S = ∅; so we may assume that any ϕ appears at most once in the pairs of S. Call the domain of S (written dom(S)) those ϕ that are the first coordinate of some element of S and let H be the subspace of V * generated by dom(S). Since |H| ≥ |S| we have dim(H) = log q (|H|) ≥ log q (|S|), where the equality is due to the linear independence of vectors in a base.

If y ∈ A S , this means that for all ϕ ∈ dom(S), ϕ(x 0 ) = ϕ(y), and therefore by linearity, that ϕ(x 0 ) = ϕ(y) for all ϕ ∈ H, which again by linearity can be re-written as ϕ(x 0y) = 0 for all ϕ ∈ H. In other words, x 0y belongs to the annihilator H • of H (here we are using the fact that V * * ∼ = V ). Of course, the converse holds, i.e. if x 0y belongs to H • , then ϕ(x 0 ) = ϕ(y) for all ϕ ∈ dom(S) and therefore y ∈ A S . This shows that A S , provided it contains at least one element x 0 , is the affine space x 0 + H • and therefore has the same dimension as H • . Now, using the classical expression of the dimension of the annihilator, dim

(A S ) = dim(H • ) = dim(V * ) -dim(H) = n -dim(H) ≤ n -log q (|S|). This implies that |A S | ≤ q n /|S|.
We will also need the following two easy lemmas about density.

Lemma 8. For all integers n let I n = {2 n , . . . , 2 n+1 -1} (note that the I n form a partition of N \ {0}). If a set D ⊆ N has positive upper density greater than δ, then for infinitely many n, the density of D inside I n (that is, the quantity

|D ∩ I n |/|I n |) is at least δ/2.
Proof. Suppose for the sake of contradiction that |D∩I n |/|I n | < δ/2 for almost all n. Without loss of generality, we may assume that this even holds for all n (by removing finitely many elements from D which does not change the upper density). For any given k, let n = n(k) be such that k ∈ I n = {2 n , . . . , 2 n+1 -1}. Then

|D ∩ {0, . . . , k}| ≤ j≤n |D ∩ I j | ≤ j≤n (δ/2) • 2 j ≤ (δ/2) • 2 n+1 ≤ (δ/2) • 2k ≤ δk.
This contradicts the fact that the upper density of D is greater than δ. We are now ready to prove Theorem 5.

Proof of Theorem 5. We construct Φ block by block. On input A, for all n, the initial segment A↾n is mapped to a string σ n of length 2 n , and the image of A under Φ is the sequence B = σ 1 σ 2 σ 3 . . . . For all n, σ n is constructed as follows:

• Identify {0, 1} n with the vector space V n of dimension n over F 2 , and let x be the element of V n corresponding to A↾n.

• Order the elements of V * n in some canonical way (say lexicographically, as V * n can also be identified with {0, 1} n ):

V * n = {ϕ 1 , ϕ 2 , . . . , ϕ 2 n }.
• Define σ n to be the string ϕ 1 (x)ϕ 2 (x) . . . ϕ 2 n (x).

Let us show that if B = σ 0 σ 1 . . . is not absolutely undecidable, then A is computable. Assuming B is not absolutely undecidable, let f be a partial computable function whose domain D has upper density greater than some rational δ > 0 and such that f (k) = B(k) for all k ∈ D. By Lemma 8, there are infinitely many n such that the density of D in I n is at least δ/2. Since D is c.e. and δ rational, the set of such n is c.e. and therefore contains a computable set {n 0 < n 1 < n 2 < n 3 , . . .}. Note that B↾I n = σ n , so by Lemma 8, for all n i , we can compute a fraction δ/2 of the values of the bits of σ n i (taking the values of f on elements in I n i ). By the construction of σ n i , this means that we can compute a subset of {(ϕ, ϕ(x)) | ϕ ∈ V * n i } (where x is the element of V n i corresponding to A↾n i ) of size at least (δ/2) • 2 n i , which, by Proposition 7, allows us to compute a finite set A i of size at most

2 n i (δ/2)2 n i = 2/δ containing A↾n i . Thus, A belongs to the Π 0 1 class {X ∈ 2 ω | ∀i (X↾n i ) ∈ A i }.
This Π 0 1 class contains at most 2/δ elements as all A i have size at most 2/δ. Thus all elements of this Π 0 1 class are computable, and therefore A is computable. The proof of Theorem 5 constructs a single functional Φ that uniformly encodes any sequence A ∈ 2 ω to Φ A . The reader might notice that the decoding procedure given for recovering A given Φ A on a dense subset is not uniform. Indeed, finding a path in a computable tree which only has finitely many paths cannot be done uniformly in general. And even with a known bound on the number of paths, one cannot effectively compute a finite list of sequences which contains all paths. We shall formally prove that this cannot be avoided, not only for the Walsh-Hadamard coding we use, but for any other coding scheme as well. By analogy to the terminology used above, the next theorem can be informally stated as follows: infinitary erasure codes with finite list decoding do not exist.

In this section we will freely identify 2 ω with the powerset of N. Fix a tt-functional Γ. A Turing functional Ψ correctly decodes X on D, if Ψ can compute X given access to the bits of Γ X in D, along with D itself, i.e. if X = Ψ(D ⊕ (Γ X ∩ D)). The following theorem shows that for a fixed δ, there does not exist a tt-functional Γ, together with a finite number of functionals Ψ 1 , . . . , Ψ k such that for any X, and any D such that ρ(D) ≥ δ, X belongs to the set

{Ψ i (D ⊕ (Γ X ∩ D)) | i ≤ k}.
Theorem 10. Fix k. Let Γ be a tt-functional, Ψ 1 , Ψ 2 , . . . , Ψ k a list of Turing functionals and σ, τ finite strings. There exists computable X and D with σ X and τ D such that:

(i) ρ(D) ≥ 1/3. (ii) X ∈ {Ψ i (D ⊕ (Γ X ∩ D)) | i ≤ k}.
Proof. The proof proceeds by induction on k. For k = 0, there is nothing to prove. For k + 1, let Γ be a tt-functional, Ψ 1 , Ψ 2 , . . . , Ψ k+1 a list of Turing functionals and σ, τ finite strings. Find a finite string σ ′ σ such that |Γ σ ′ | ≥ |τ |. Let X 1 , X 2 , X 3 be three distinct computable infinite binary sequences extending σ ′ and let Y i = Γ X i for i ≤ 3. By the discussion of page 4, for all n, there are 1 ≤ i < j ≤ 3 such that Y i ↾n and Y j ↾n coincide on at least one third of their bits. Thus there are 1 ≤ i < j ≤ 3 such that Y i ↾n and Y j ↾n coincide on at least one third of their bits for infinitely many n. Without loss of generality, assume this holds for the pair (Y 1 , Y 2 ). The set D of positions n such that Y 1 (n) = Y 2 (n) has density at least 1/3. Further as Y 1 and Y 2 must agree on the first |τ | bits, we can adjust D so that τ D without affecting the density of D or the fact that for all n ∈ D, Y

1 (n) = Y 2 (n). If X 1 ∈ {Ψ i (D ⊕ (Y 1 ∩ D)) | i ≤ k + 1}
, then X 1 and D witness that the theorem holds for Γ, Ψ 1 , Ψ 2 , . . . , Ψ k+1 , σ and τ . Otherwise, we can assume without loss of generality that

X 1 = Ψ k+1 (D ⊕ (Y 1 ∩ D)). Observe that there is some m such that X 1 (m) = X 2 (m). Further as Y 1 ∩ D = Y 2 ∩ D, and Ψ k+1 (D ⊕ (Y 2 ∩ D)) = X 1 , there exists τ D and σ X 2 such that | σ| ≥ m + 1, and Ψ k+1 ( τ ⊕ (Γ σ ∩ τ )) X 1 ↾(m + 1).
By our induction hypothesis for Γ, Ψ 1 , Ψ 2 , . . . , Ψ k , σ and τ , there is X, D such that σ X, τ D, and

X ∈ {Ψ i ( D ⊕ (Γ X ∩ D)) | i ≤ k}. Observe that Ψ k+1 ( D ⊕ (Γ X ∩ D)) X 1 ↾(m + 1) = X↾(m + 1
) so in this case X and D witness that the theorem holds.

Between bi-immunity and absolute undecidability

Theorem 5 shows that in every non-trivial tt-degree there is an absolutely undecidable set. In other words, in every such degree there is a set such that we are unable to infinitely often correctly guess a constant percentage of its bits. We show that the statement of the theorem is tight in the sense that there does in fact exist a degree such that for all sets in that degree we can infinitely often decide a portion of their bits arbitrarily close to (but necessarily less than) a constant percentage.

In the rest of this paper, (ϕ e ) e and (Φ e ) e denote respectively a standard enumeration of partial computable functions from N to N and a standard enumeration of partial Turing functionals from 2 ω to 2 ω . We say that a Turing degree d is computably dominated if for all functions f ≤ T d, there is a computable function g such that for all n, g(n) ≥ f (n).

Theorem 11. There is a non-computable set X such that for all Y ≤ T X, and all computable functions h ∈ o(n), there exists a partial computable function ϕ such that:

1. Y extends ϕ (i.e., Y (n) = ϕ(n) for all n ∈ dom(ϕ)).

κ dom(ϕ) ∈ o(h).

Theorem 11 is proved using forcing with computable perfect trees. A tree T ⊆ 2 <ω is perfect, if for all σ ∈ T there is some τ σ such that both τ 0 and τ 1 are in T . Given a tree T ⊆ 2 <ω , define [T ] to be the set of paths through [T ], i.e. [T ] = {X ∈ 2 ω | ∀n X↾n ∈ T }.

We define a partial order P on the set of computable perfect trees in 2 <ω by T

0 ≤ T 1 if [T 0 ] ⊆ [T 1 ]. For any computable A ∈ 2 ω , the set D A = {T ∈ P | (∀X ∈ [T ])(X = A)} is dense in P. If Φ is a Turing functional then the set {T ∈ P | ((∀X ∈ [T ])(Φ X e is partial)) ∨ ((∀X ∈ [T ])(Φ X e is total)
)} is also dense in P. Hence if {T i } i∈N is a descending sequence in P that meets all such dense sets, then any element of i∈N [T i ] is a non-computable set of computably dominated degree. Further such a sequence is computable by ∅ ′′ .

Since a Turing reduction to a set of computably dominated degree is always equivalent to a truth-table reduction it is enough to continue working with the latter class of reductions in the remainder of the proof.

In order to prove Theorem 11 we will show that if h ∈ o(n) is a computable function and Φ is a truth-table functional, then the set

{T ∈ P | (∃e)(∀X ∈ [T ])(Φ X extends ϕ e ∧ κ dom(ϕe) ∈ o(h)} (1)
is dense in P. Fix a computable perfect tree T , a truth-table functional Φ and a computable function h such that h ∈ o(n). For all σ ∈ T we will define two, possibly partial, computable functions f σ : 2 <ω → T and g σ : N → {0, 1} such that if f σ is total then the range of f σ is a computable perfect subtree of T . Further if f σ is total then g σ will witness that the range of f σ is in [START_REF] Arora | Computational complexity[END_REF].

First let f σ (λ) = σ (where λ is the empty string). Now assume that f σ has been defined on all strings of length less than or equal to n and let {σ 1 , . . . , σ 2 n } = {f σ (τ ) | |τ | = n}. We search the tree T for some m > n, a set of nodes {ξ 1 , . . . , ξ 2 n } ∈ T and D ⊆ {0, . . . , m} such that:

(i) ∀i ∈ {1, . . . , 2 n }, ξ i σ i . (ii) ∀x ∈ D, Φ ξ 1 (x) = Φ ξ 2 (x) = . . . = Φ ξ 2 n (x). (iii) |D| > h(m).
If the search succeeds, then for all x ∈ D we define g σ (x) to be the common value (i.e. g σ (x) = Φ ξ 1 (x)). We set f (σ i 0) to be one immediate successor of ξ i in T and f (σ i 1) to be the other immediate successor of ξ i in T .

We claim that there exists some σ ∈ T such that the function f σ is total. To prove this, we will define a condition ⋆ such that if ⋆ holds for σ then f σ is total. Further if ⋆ does not hold for any σ then f λ is total (and though we will not need this, in fact f σ will be total for any σ ∈ T ).

Condition ⋆ holds for σ ∈ T if there exists D ⊆ N of positive upper density such that for all X, Y ∈

[T ] ∩ [σ], the set {x ∈ D | Φ X (x) = Φ Y (x)} has density zero.
Lemma 12. If condition ⋆ holds for σ then f σ is total.

Proof. Let D be the set of positive upper density that witnesses that condition ⋆ holds for σ. Assume that level n of f σ has been defined and that this level is equal to {σ 1 , . . . , σ 2 n }. For all i ∈ {1, . . . , 2 n }, let X i be the left-most path of T above σ i .

For i ∈ {2, 3, . . . ,

2 n } define S i = {x ∈ D | Φ X 1 (x) = Φ X i (x)}.
According to condition ⋆, for each i, the set S i has density 0. Thus if we let D = D \ (S 2 ∪ S 3 ∪ . . . ∪ S 2 n ) we have that D is a set of positive upper density by repeated application of Lemma 9. Further for all x ∈ D, Φ

X 1 (x) = Φ X 2 (x) = . . . = Φ X 2 n (x).
As h(n) ∈ o(n), there exists some m > n such that ρ D(m) > h(m). For each i, let ξ i ∈ T be a sufficiently long initial segment of X i such that Φ ξ i (x) ↓ for all x ≤ m. This means that m, {ξ 1 , ξ 2 , . . . , ξ 2 n } and D ∩ {0, . . . , m -1} met the conditions to define the next level of f σ and hence the search must end successfully at some point.

Lemma 13. If condition ⋆ does not holds for any σ ∈ T then f λ is total.

Proof. Assume that the n-th level of f λ has been defined and that this level is equal to {σ 1 , . . . , σ 2 n }. We argue by induction; let D 1 = N and let X 1 be the left-most path above σ 1 .

For the induction step assume that for some i < 2 n , we have defined D i and X 1 ≻ σ 1 , . . . , X i ≻ σ i such that D i is a set of positive upper density and for all x ∈ D i Φ X 1 (x) = Φ X 2 (x) = . . . = Φ X i (x). Hence the set D 2 n has positive upper density and for all x ∈ D 2 n we have Φ X 1 (x) = Φ X 2 (x) = . . . = Φ X 2 n (x).

As argued in the previous lemma, this is sufficient to show that the construction of f λ can continue.

Proof of Theorem 11. We will show that if Φ is a truth-table functional and h is a computable function such that h ∈ o(n), then the set (1) is dense in P. Take any T ∈ P. Consider the construction of the functions f σ and g σ with respect to T , Φ and h. By Lemmas 12 and 13 for some σ ∈ T the function f σ is total. Let T be the range of f σ . T is a computable perfect tree and T ≤ T . Now for all X ∈ [ T ], Φ X extends g σ . Further κ dom(gσ) ∈ o(h) because when f σ is defined on all strings of length n, for some m > n the construction ensures that κ (domgσ) (m) > h(m).

Let {T i } i∈N be a descending sequence in P that meets all of the sets of the form (1) as well as those dense sets that ensure non-computability and being of computably dominated degree. If X ∈ i [T i ], then X is non-computable. Now if Y ≤ T X then because X is of computably dominated degree Y = Φ X for some truth-table functional Φ. Hence for any computable function h ∈ o(n), there is a partial computable function g such that Y extends g and κ dom(g) ∈ o(h).

One should notice that in the above proof, while the condition ⋆ is Σ 1 2 , the construction can be carried out using ∅ ′′ because it is not necessary to determine if ⋆ holds. All that is required is to find a string σ such that f σ is total.

Definition 2 .

 2 Let D ⊆ N. The upper density of D is the quantity ρ(D) := lim sup n→∞ |D ∩ {0, . . . n -1}| n .

Lemma 9 .

 9 If D ⊆ N has upper density δ and E ⊆ N has density 0 then D \ E has upper density δ. Proof. For all n, |(D\E)∩{0, . . . , n}| ≥ |D∩{0, . . . , n}|-|E∩{0, . . . , n}| ≥ |D∩{0, . . . , n}|o(n). Thus lim sup n |(D \ E) ∩ {0, . . . , n}|/n = lim sup n |D ∩ {0, . . . , n}|/n

  The set D i has positive upper density; and since condition ⋆ fails above all σ ∈ T , it fails in particular above σ i+1 . Therefore there existY, Z ∈ [T ] ∩ [σ i+1 ] such that the set E = {x ∈ D i | Φ Y (x) = Φ Z (x)} does not have density zero i.e. E has positive upper density. Now we can partition E into the sets:E 1 = {x ∈ E | Φ Y (x) = Φ X 1 (x)} and E 2 = {x ∈ E | Φ Z (x) = Φ X 1 (x)}. Atleast one of these sets has positive upper density by Lemma 9. If E 1 has positive upper density we let D i+1 = E 1 and X i+1 = Y . Otherwise we let D i+1 = E 2 and X i+1 = Z.

The same problem occurs for any finite alphabet size.

Every truth table degree contains an absolutely undecidable setWe hope that the reader who is familiar with coding theory can find in the previous section sufficient information to prove Theorem 5. In this section, we present our argument in a self-contained way that assumes no prior knowledge of coding theory. Besides, the direct analysis of the Walsh-Hadamard code for our purposes will give a better bound on the list of candidates than the one we gave in the previous section (1/δ instead of 1/δ 2 ).The core of the proof resides in a combinatorial argument about vector spaces. Before giving the argument let us illustrate it with an example. Define f 3 : {0, 1} 3 → {0, 1} 7 as follows. If a, b, c ∈ {0, 1} thenf 3 (abc) = abc(a + b)(b + c)(a + c)(a + b + c),where addition is performed modulo 2 (caveat: the right-hand side is a concatenation of bits, not a product modulo 2). In other words, f 3 (abc) is obtained by concatenating together the

Acknowledgements. The authors would like to thank Alexander Shen for pointing out to us the notion of list decoding, which we only implicitly used in earlier presentations of our results. Thanks also go to Carl Jockusch for useful comments and discussions.


David Ok

Mateusz Koziński

Renaud Marlet

Nikos Paragios

High-Level Bottom-Up Cues for Top-Down Parsing of Facade Images

We address the problem of parsing images of building facades. The goal is to segment images, assigning to the resulting regions semantic labels that correspond to the basic architectural elements. We assume a top-down parsing framework based on a 2D shape grammar that encodes a prior knowledge on the possible composition of facades. The algorithm explores the space of feasible solutions by generating the possible configurations of the facade and comparing it to the input data by means of a local, pixelor patch-based classifier. We propose new bottom-up cues for the algorithm, both for evaluation of a candidate parse and for guiding the exploration of the space of feasible solutions. The method that we propose benefits from detectionbased information and leverages on the similar appearance of elements that repeat in a given facade. Experiments performed on standard datasets show that this use of more discriminative bottom-up cues improves the convergence in comparison to state-of-the-art algorithms, and gives better results in terms of precision and recall, as well as computation time and performance deviation.

Introduction

Image segmentation remains a generic, and in a large part, unsolved problem in computer vision. For many instances of this problem we are not restricted to using the information contained in the image alone. We may also resort to prior knowledge of the likely compositions of objects present in the scenes. Shape grammars are a concept that encodes such prior knowledge and is used for image segmentation. In the framework of shape grammars, segmentation amounts to assigning semantic labels to image regions and is known under the name of image parsing [START_REF] Zhu | A stochastic grammar of images[END_REF].

Applications involving images of highly structured scenes are likely to benefit most from the development of image grammars. One such field, which has been drawing increasing attention recently, is facade parsing [START_REF] Alegre | A probabilistic approach to the semantic interpretation of building facades[END_REF][START_REF] Müller | Procedural modeling of buildings[END_REF][START_REF] Müller | Imagebased procedural modeling of facades[END_REF][START_REF] Barinova | Geometric image parsing in man-made environments[END_REF][START_REF] Teboul | Segmentation of building facades using procedural shape priors[END_REF][START_REF] Teboul | Shape grammar parsing via reinforcement learning[END_REF]. The goal of facade parsing is to automatically provide a hierarchical decomposition of a building facade into its constituent elements, given an image of the facade. Facade parsing has a variety of applications, including urban planning, thermal performance assessment of existing structures and reconstruction of models of existing buildings for games and simulators.

Amongst the most successful solutions to the problem of facade parsing are the top-down parsers proposed by Teboul et al. [START_REF] Teboul | Segmentation of building facades using procedural shape priors[END_REF][START_REF] Teboul | Shape grammar parsing via reinforcement learning[END_REF]. They draw from the idea of split grammars for architectural modeling [START_REF] Müller | Procedural modeling of buildings[END_REF], where a variety of building models can be generated from a single grammar. The process is analogous to string or sentence derivation in formal and natural language processing. The goal of parsing here is to perform the derivation in such a manner that the resulting model corresponds to the input image. The top-down parsers have proven to be efficient in this task.

However, the robustness of this approach is dependent on the quality of the bottom-up information used for comparing the candidate models with the input image. Such information can be degraded because of challenging lighting conditions, facade appearance variation, or occlusions. This sensitivity is partly due to the fact that the underlying merit function is based on low-level, pixel-or patch-based information, as proposed in [START_REF] Teboul | Shape grammar parsing via reinforcement learning[END_REF]. Besides, because of the high complexity of the problem space and due to the randomized nature of the approach, a good data-driven exploration of the solution space is crucial to simultaneously limit significant performance deviation in the parsing, and achieve fast convergence rate. But again, exploration presented in [START_REF] Teboul | Shape grammar parsing via reinforcement learning[END_REF] is only based on pixels or patches.

To address the above issues, we propose a modified algorithm for top-down facade parsing that benefits from higher level and more robust abstractions, as provided by object detectors and geometric primitives. Namely, we integrate an object detector into the existing framework of [START_REF] Teboul | Shape grammar parsing via reinforcement learning[END_REF], in this case a window detector. For this, we use a robust pattern search method, exploiting the fact that architectural elements present in a particular facade frequently share similar appearance. Additionally, to improve the convergence properties of the method, we guide the parser with the window detections and line segment cues. As a result, the parser not only better locates facade elements but also prunes the 1 solution space much more selectively.

Related Work

The idea of representing the image contents in a hierarchical and semantized manner can be traced back to the work of Kanade and Ohta [12,13]. However, the practical applications of grammars to image interpretation or segmentation are attributed to more recent works [START_REF] Han | Bottom-up/top-down image parsing with attribute graph grammar[END_REF]22,5,[START_REF] Ahuja | Connected Segmentation Tree -A Joint Representation of Region Layout and Hierarchy[END_REF].

In many works, the hierarchical and regular structure of man-made objects is explored to improve segmentation or detection results [22,5,[START_REF] Ahuja | Connected Segmentation Tree -A Joint Representation of Region Layout and Hierarchy[END_REF]. We focus on flexible grammars that allow the user to encode specific knowledge of the domain in the form of production rules that constrain the space of feasible solutions. The grammar-based image interpretation paradigm is thoroughly reviewed in the work of Zhu and Mumford [START_REF] Zhu | A stochastic grammar of images[END_REF]. A good example of this approach is the rectangle-based grammar of Han and Zhu [START_REF] Han | Bottom-up/top-down image parsing with attribute graph grammar[END_REF], in which the prior knowledge is represented by means of an and/or graph. The terminal symbols are rectangles and the production rules combine them into rows, columns or grids, and allow for rectangle nesting. This case illustrates one of the difficulty of the problem: the number of terminals in the solution is unknown. The greedy algorithm presented in the paper copes well with this difficulty. However, since there is no semantic interpretation associated with the rectangles, there is no sensible way of deciding which of any two candidate parse trees is better.

The use of grammar-based facade parsing has been inspired by the successful application of split grammars for generating virtual urban environments [START_REF] Müller | Procedural modeling of buildings[END_REF]. The key to success is to encode in the grammar basic constraints on the generated objects: the principles of adjacency, non-overlap and snaplines. A number of research works has been aimed at applying the grammar principles for retrieving building models from images [START_REF] Teboul | Segmentation of building facades using procedural shape priors[END_REF][START_REF] Teboul | Shape grammar parsing via reinforcement learning[END_REF]8,[START_REF] Riemenschneider | Irregular lattices for complex shape grammar facade parsing[END_REF]. In their work, Teboul et al. present an application of a 2D binary split grammar for parsing rectified facade images [START_REF] Teboul | Segmentation of building facades using procedural shape priors[END_REF]. The method can accommodate several classes of terminal symbols and has been shown to be robust to partial occlusions and relatively flexible to variable facade appearance [START_REF] Teboul | Shape grammar parsing via reinforcement learning[END_REF]. However, the algorithm suffers from a number of shortcomings, including the use of bottom-up gradient cues. The work of Yang et al. [23] focuses on the application of rank-1 matrix approximation for facade parsing. A binary classifier of window color is applied to the facade image. The image is divided into rectangular regions. The algorithm attempts to fit an irregular grid of windows to each of these regions. This is performed by approximating the output of the classifier by a rank-1 matrix. The main drawback of the algorithm is the constraint of two-class (window and wall) facades and the lack of flexibility in defining the grammar. Mathias et al. propose to use the grammar of [START_REF] Müller | Procedural modeling of buildings[END_REF] and generate the building while estimating the attributes of the applied grammar rules from the input images and a 3D point cloud. While the general idea seems attractive, the algorithm has not been shown to perform well with more than two classes of terminal symbols and accommodates only a small subset of rules of the original grammar [8].

Grammar-based Parsing

A shape grammar [16,[START_REF] Zhu | A stochastic grammar of images[END_REF] is a formalism to represent a structured collection of shapes. The symbols of the grammar are basic shapes, and the production rules transform one configuration of basic shapes into another. The split grammars [START_REF] Teboul | Segmentation of building facades using procedural shape priors[END_REF][START_REF] Müller | Procedural modeling of buildings[END_REF] are context-free shape grammars, where the production rules split the non-terminal basic shape on the left-hand side of the production rule along one dimension at a time. This simplification decreases the dimensionality of the space of parameters of a single production rule while preserving the expressive power of the grammar. This makes split grammars particularly suitable for modeling building facades.

The following part of this section gives a brief overview of 2D split grammars for facade modeling. The reader is referred to [START_REF] Teboul | Segmentation of building facades using procedural shape priors[END_REF][START_REF] Teboul | Shape grammar parsing via reinforcement learning[END_REF] for more details.

Split grammars

The grammar dealt with in this paper operates on rectangles as basic shapes. Each production rule splits a rectangle along the horizontal or vertical dimension into a number of new rectangles. In the case of building grammars, the terminal basic shapes represent architectural elements, like windows and wall tiles, and the production rules encode the possible spatial compositions of these elements. Generating from the grammar, one obtains schematic images of building facades [START_REF] Teboul | Segmentation of building facades using procedural shape priors[END_REF][START_REF] Müller | Procedural modeling of buildings[END_REF].

Formally, a 2D split grammar G is a context-free grammar (N , T , R, S) where N is a finite set of non-terminal basic shapes {N 1 , . . . , N m }, T is a finite set of terminal basic shapes {t 1 , . . . , t n }, R is a finite set of rules {r 1 , . . . , r l } and S ∈ N is the starting shape (axiom).

Terminal and non-terminal symbols of the grammar are called basic shapes. They have a semantic type (e.g., window, balcony or floor) from a finite subset C, and a bounding box. The vector of attributes of a basic shape of type c at position (x, y) with width w and height h is denoted as (c, x, y, w, h).

A rule r : A → B 1 B 2 . . . B k splits a single non-terminal basic shape A along a selected dimension into a sequence of basic shapes (B i ) 1≤i≤k . For example, a vertical split rule decomposes a basic shape into multiple chunks of basic shapes along the y axis. The grammar can be transformed into Chomsky Normal Form, so that each rule applies at most one split to the processed basic shape. This reduces the number of continuous attributes of a production rule to one. The generation process starts by applying a production rule to the axiom and continues applying production rules to the non-terminal basic shapes until there are only terminals in the derived configuration. The application of a rule requires the selection of the rule and the determination of its attributes, i.e., the number and positions of the splits. Generation is thus a sequence of decisions. It constructs a derivation tree. The root of the tree is the axiom S and all the nodes correspond to basic shapes, with terminal basic shapes at the leaves. An operation on a non-terminal node is performed by attaching to it the children nodes. Figure 1 illustrates the first two steps of a derivation process for an exemplary split grammar.

The idea of parsing is to construct a derivation tree corresponding to a given configuration of terminal shapes. It can be performed in a top-down or bottom-up fashion. In the first case, the derivation tree is constructed starting from the axiom; in the second case, the leaves of the tree are instantiated first.

In many practical facade parsing applications, the input data consists of a rectified facade image. The goal is to segment the image into a configuration of semantically meaningful regions that is allowed by the grammar. The grammar presented in [START_REF] Teboul | Shape grammar parsing via reinforcement learning[END_REF] represents the Haussmannian architecture of the XIXth century buildings in Paris. The set of terminals includes sky, roof, shop, door, window, wall and balcony areas. As in [START_REF] Teboul | Shape grammar parsing via reinforcement learning[END_REF], choosing a relevant split grammar is an issue we do not address. We assume the split grammar is known and written beforehand.

Reinforcement Learning for Top-Down Parsing

To assess the quality of a derivation tree, a pixelwise merit function is computed first. The merit function m(x, y, c) ∈ [0, 1] estimates the likelihood that a pixel at (x, y) is of semantic type c. In [START_REF] Teboul | Shape grammar parsing via reinforcement learning[END_REF], a random forest (RF) classifier is used to estimate m. The parser's goal is to find a derivation tree T that maximizes the cumulated reward, defined over all the terminals and the input image as:

ti M (t i ). M (t) is the reward for a single terminal t = (c, x, y, w, h) and cumulates the reward over all pixels covered by the terminal: (

M (t) =
) 1
The task is difficult because the effect of decisions taken on the non-terminal nodes is not known until the terminal nodes are instantiated. In [START_REF] Teboul | Shape grammar parsing via reinforcement learning[END_REF], the problem is formulated in terms of a Markov Decision Process. The parser acts as an agent constructing a derivation tree. Such tree has a state s = (T, N ) which consists of the tree T under construction and the next non-terminal node N to be processed. The parser learns a policy function π(s, a), which is the probability of choosing production rule attribute a in state s. By repeatedly simulating derivation trees with the current policy function π(s, a), the parser updates at each iteration π(s, a) accordingly with the history of cumulated rewards, which are determined when derivation trees are complete.

Denoting the current best optimal attribute by a * and the prior distribution of rule attributes by P (a|s), the policy function takes the form

π(s, a) = (1 -ε)δ(a, a * ) + εP (a|s), ( 2
)
where δ is the Kronecker delta and ε is a parameter of the algorithm. Specifically, the policy function either chooses with probability 1 -ε the best rule attribute a * , learnt "from experience", or draws another rule attribute a from the prior distribution P (a|s) with probability ε. After a number of iterations, π(s, a) converges to the optimal policy function, which in turn can generate a derivation tree yielding the highest reward. In order to speed up the convergence, a data-driven version of the algorithm is used, where P (a|s) is determined from the bottom-up cues. The prior distribution P (a|s) for split locations is generated by marginalizing the horizontal and vertical gradient magnitudes along the y and x directions of the image.

Improved bottom-up cues for facade parsing

The algorithm proposed by [START_REF] Teboul | Shape grammar parsing via reinforcement learning[END_REF] only utilizes local, pixelor patch-based information. In particular, this is the case of the merit function, which lacks robustness. Such a limitation is significant in the case of buildings, because of possibly high variations of facade color and lighting conditions of image acquisition. Within the framework, it is also not possible to benefit from the fact that in a single image, elements of the same type may share similar appearance; e.g., the pixel classifier in [START_REF] Teboul | Shape grammar parsing via reinforcement learning[END_REF] looks for any kind of window at any position. It does not reinforce the specific similarity of windows and window surroundings. Besides, the random nature of the Q-learning algorithm used in [START_REF] Teboul | Shape grammar parsing via reinforcement learning[END_REF] results in significant result variations from run to run. In the following part of this paper we propose modifications to the algorithm to address these drawbacks.

Instead of constraining the bottom-up information to a local, low-level merit function, we propose to also use an object detector and a robust pattern search method. Our algorithm may thus exploit the repetition of specific instances of architectural elements within the facade. To better guide the parsing, we also design discriminative distributions of parsing actions using the object detections and line segment cues. As a result, the parser not only better locates elements but also prunes the solution space much more selectively.

In the rest of the paper, we describe our repetitive pattern search, our improved merit function, the new distribution for split positions and provide experimental results.

Detection of repeated objects

There are numerous methods for object detection, in particular based on learning techniques, such as the cascade classifier [START_REF] Viola | Robust real-time face detection[END_REF]. However, these methods are not perfect and still make errors, i.e., miss objects, hallucinate objects, or do not localize them properly. One or several parameters may usually be tuned to favor precision or recall. Moreover, they are trained to recognize a wide variety of object instances. They do not exploit the fact that, in some circumstances, only similar object instances appear in the image, e.g., windows on a given single facade. A hypothesis of these methods is that all detected objects are independent one from another (as long as they do not overlap).

We propose to use such a detector only to find few but very likely object occurrences, tuning the detector for precision. We then use these accurate detections as problemspecific models and rely on a robust pattern search procedure to look for similar instances of these models in the image. For more robustness, to improve recall, this procedure is repeated recursively on the new detections (resulting from the pattern search) until there are no more detections.

In the general case, other similar objects can be seen from different view angles. Assuming the visible part of the considered model object is mostly planar, other instances appear as a projective transformation of this model. In practice, when working on rectified images, mostly translation and rotation are to be expected. Depending on the application, scale could also vary and the expected transformation could then be a similarity. In the particular case of facade windows, there is no rotation, but the window sizes may vary. Indeed, windows on the same facade often have two or three different widths, depending on the size or use of the corresponding room. Although stretched horizon-tally, all windows on the facade however "look alike". Also for older structures, including Haussmanian buildings, bottom floors have higher ceilings and higher windows than top floors, to compensate for the lesser illumination. But here again the window appearance is only stretched, vertically. To accomodate these different situations, our pattern search procedure looks for affine transformations of the model, that satisfy additional, problem-specific constraints. In particular, for facade windows on a rectified image, the score of an affinity matrix A = a 1 a 2 t x a 3 a 4 t y is defined as s(A) = exp(-(a 2 2 + a 2 3 )), to discourage choosing affinities with strong shear components and large rotation angle, which can be generated due to inaccurately localized keypoints. Thus, affinities with a score below threshold s min are discarded.

To improve robustness, our pattern search procedure is based on feature correspondence rather than pixel similarity (e.g., with SSD or NCC). Features located in the model subimage indeed provide a robust model abstraction and are a good indicator of the presence of other pattern instances in the rest of the image. Given the extent P of the pattern in image I, matches to consider are only pairs of features (x, y) such that x is in the model subimage P and y in the rest of the image I \ P .

In this situation, the transformation can be estimated from the feature point positions. Methods as RANSAC or one of its numerous variants [START_REF] Raguram | A comparative analysis of RANSAC techniques leading to adaptive real-time random sample consensus[END_REF] are well suited to determine such a transformation. However, several transformations are to be sought here, one for each instance of the model. RANSAC thus has to be iterated after a first instance is found, to find other ones, or a variant of RANSAC looking simultaneously for several models has to be used [25]. In our case, the model instances are expected to be clearly separated and a simple sequential RANSAC is enough. Note that pattern repetition intrinsically introduces match ambiguities between features associated to repeated elements. Depending on the amount of repetition, the number of match outliers can be huge. In our exemples with windows, the outlier contamination rate can reach 98% of about 500,000 feature matches. That would normally be beyond what most RANSAC variants can handle, but the fact that we are only looking here for (specific) affinities reduces the search space, as these affinities are defined by just a triple of matches. Furthermore, to prevent the exploration of a vast amount of triples than cannot lead to matching the model, we pick a first match (x 1 , y 1 ) and draw the other two matches (x i , y i ) 2≤i≤3 of a triple looking for y i in the neighborhood of y 1 , at a distance less than the diameter of P . Depending on the feature detector, this distance may take into account a scale factor defined by the relative scale of x and y. Moreover, to further speed up model estimation, matches are drawn based on the distance of their descriptor.

Finally, for more robustness, we sligthly increase the area of the model P , by constant factor, to include some environmental information. After patterns are localized, they are shrunk with the same factor to recover the estimated boundary of the actual model instances.

Enhanced merit function

We propose a new, more robust and more accurate merit function, which combines the local, low-level (pixel-or patch-based) information with standalone, high-level object detection. We interpret a detector for a class d as a pixel classifier w d (x, y), the value of which is 1 if (x, y) is a pixel belonging to the detected object and 0 otherwise. Not all semantic categories can have a sensible detector in practice. For instance, a classifier can be trained to detect windows or doors, but it is much harder to practically and reliably detect walls or roofs. Moreover, although the semantic types of terminals have no intersection in this kind of grammar, actual detectors can locate objects that overlap several semantic types of the grammar. For example, a general window model for detection can encompass both window-only areas and cast iron balconies in front of windows in the grammar. We thus make a difference between the semantic classes C of the grammar and the semantic classes The improved merit function m + gives confidence to the high-level detectors over the underlying, low-level merit: in case of a detection at a given pixel, it zeroes the merit of undetected classes (and the merit is renormalized). More formally, let D x,y = {d ∈ D | w d (x, y) = 1} be the set of detected classes at pixel (x, y). We define m + (x, y, c) = m(x, y, c) if D x,y = ∅, i.e., it is unchanged where there are no detection. Otherwise, if D x,y = ∅, then m + (x, y, c) is defined as

   m(x, y, c) c ∈c(Dx,y) m(x, y, c ) if c ∈ c(D x,y ) 0 otherwise. (3)
In our experiments we trained a general window detector that also localizes windows with a cast iron balcony in the foreground. We thus have D = {whole-window} and c(D) = {window, balcony}. Figure 2 illustrates the improved merit function. We display m * (x, y, c) = arg max c m(x, y, c) with different colors for different classes (and likewise for m * + ) and an image illustrating w whole-window with patches of the original image in places where whole windows have been detected.

Enhanced distribution of split positions

Our last contribution is the design of more discriminative distributions of parsing actions P (a|s) for the policy function π(s, a). The most critical parsing action is the choice of the split position that decomposes a basic shape in the optimal manner. We consider two distributions for the split positions: one for horizontal splits and one for vertical splits. In [START_REF] Teboul | Shape grammar parsing via reinforcement learning[END_REF], these distributions are obtained by accumulating gradients in the image along the x and y axes. However, these marginal distributions are noisy because of the harmful accumulation of gradients not corresponding to objects of interest, but resulting from shadows, texture or small architectural details. We propose another approach, based on marginalizing the distribution of line segments detected in the image. These higher-level abstractions are better split indicators.

We first detect line segments L in the image. (In our experiments we use LSD [START_REF] Gioi | LSD: A fast line segment detector with a false detection control[END_REF].) Let v(y) be the distribution of vertical split positions. We denote by [a l , b l ] the projection of a segment l ∈ L on the vertical axis, and by θ l its angle with respect to horizontality. The value of the distribution at height y is computed as follows:

v(y) = C l∈L 1 y∈[a l ,b l ] exp(- tan 2 θ l 2σ 2 ) , (4)
where σ is a parameter of the distribution and C is a normalization constant. The definition is symmetrical for horizontal splits. For our experiments we set σ = 0.06, which roughly leads to a segment contribution of 1 3 for a segment with a 5 • angle, whereas a perfectly axis-aligned segment contributes for 1. To reduce computation time, line segments with an angle beyond a threshold (around 10 • for the given σ value) can be discarded right after detection.

In the same manner, we build a normalized histogram of the contours of the detected objects. The two distributions are summed and the resulting histogram is normalized, yielding the final distribution of applicable split positions. The major benefit of this approach is that the exploration of the solution space is significantly pruned and the splits are attracted to optimal positions. The parser avoids being stuck in local minimum and the temporal standard deviation of the energy decreases over time faster than for the original algorithm (see Figures 3 and5).

Experimental validation

Our experimental validation is mainly based on the ECP CVPR 2010 and ECP Benchmark 2011 datasets [START_REF] Teboul | École Centrale Paris datasets[END_REF], that picture rectified Haussmanian buildings annoted with 7 semantic classes: sky, roof, wall, window, balcony, shop, door. We also used the eTRIMS [6] dataset, which displays many different architectural and building styles, with annotations for windows. As eTRIMS images are not rectified, we first performed the rectification (by hand). We also corrected and normalized the annotations, as the ground truth windows were sometimes erroneous or not delineated similarly as in the ECP datasets. All datasets are publicly available. Before presenting parsing results, we first assess the quality of our window detector alone.

Window detection

In our implementation, the initial model regions are obtained by the Viola-Jones cascade classifier (CC) [START_REF] Viola | Robust real-time face detection[END_REF]. We trained it to detect windows on the 20 training images of the ECP CVPR 2010 dataset. We also added negative examples of windows to minimize false detections. The classifier is parameterized by a detection score threshold τ , to balance precision and recall. We note CC(τ ) the corresponding detector. Using τ , we may search only for reliable windows and then use them as models to find windows that were missed or wrongly localized by the classifier. For feature detection and matching we use Harris-Affine [START_REF] Mikolajczyk | A com-parison of affine region detectors[END_REF], MSER [START_REF] Mikolajczyk | A com-parison of affine region detectors[END_REF] and DoG [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] detectors, and the SIFT [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] descriptor.

We compare the results of the cascade classifier alone for various detection thresholds (CC(τ )) against our pattern search procedure (CC(τ )+PS). We also compare with the grammar-based method of Teboul et al. (RL) [START_REF] Teboul | Shape grammar parsing via reinforcement learning[END_REF], with two different grammars: a binary grammar (windows, not window) that assumes an irregular grid layout (RL(bin)), and a Haussmannian grammar with 7 classes (RL(haussm)). The methods are compared in terms of mean true positive rate (TPR) and mean true negative rate (TNR). Tables 1 and2 summarize our results, and detection examples are shown in Figure 4. In all datasets, for a TNR more than 90%, our pattern search algorithm (CC+PS) outperforms other methods in terms of TPR. It significantly improves the initial TPR of CC, by 12-15 points. It only slightly decreases TNR with respect to CC on rectified eTRIMS, by 3 points.

Facade parsing

To evaluate our approach, we ran the modified shape grammar parser on the test set of the ECP Benchmark 2011 1). We compare this parser against the original one, presented in [START_REF] Teboul | Shape grammar parsing via reinforcement learning[END_REF]. In each case we run the parsers once. The results are evaluated with use of the ground truth annotations accompanying the dataset. We present the results of the comparison in the form of the confusion matrices. The detection rate of building elements corresponds to the diagonal entry of the matrix (see [START_REF] Teboul | Shape grammar parsing via reinforcement learning[END_REF] for details). Table 3 shows the efficiency of our two contributions separately. Consistent improvement of the results over the whole range of classes is visible already even for the partial contributions of the refined merit function and the new distribution of split positions separately. The improvement is amplified when we combine the two modifications into our final algorithm (bottom-right matrix). In particular, the window detection improves from 60% to 85% while most other rates are improved or preserved. Our algorithm also shows better convergence properties than the original one. In Figure 5 we show that the proposed algorithm converges faster, attains better values of the reward function and is less prone to deviate from the optimal solution. A few actual results are illustrated in Figure 6.

          +11 -8 +6 +4 -3 -1 -1           85

Conclusion

We have presented a method to enhance top-down facade parsing. It is based on the parser presented in [START_REF] Teboul | Shape grammar parsing via reinforcement learning[END_REF] and carries two significant contributions with respect to the original version: the use of robust and adaptive object detectors to better estimate the merit function used by the parser, 1 This dataset must not be confused with the ECP CVPR 2010 dataset which consists of 10 test images only. Hence the numbers differ from what is reported in [START_REF] Teboul | Shape grammar parsing via reinforcement learning[END_REF]. Figure 5: The convergence of our algorithm with respect to [START_REF] Teboul | Shape grammar parsing via reinforcement learning[END_REF]. The plot shows the evolution of the reward, the current best reward and the standard deviation of the reward over time for a single run of the parser. The 'mean reward' is the plot of the reward function smoothed over time, to eliminate the high-frequency variation.

and the use of detected objects as well as line segments to better determine split positions, which effectively guides the reinforcement learning algorithm and speeds up its convergence. The significant performance improvements that we observe experimentally demonstrate the importance of high-level bottom-up cues in top-down parsing. We note that our algorithm for repeated pattern detection can be used as a standalone algorithm for detecting multiple object instances in images. The algorithm significantly improves detection performance in cases where a particular type of object repeats over the image. In such situation, the algorithm can be viewed as an adaptive detector that adjusts to the specific appearance of the repeated object.

Figure 6: Examples of images for which our parser outperforms the original algorithm (best viewed using magnification). Top: results of original parser [START_REF] Teboul | Shape grammar parsing via reinforcement learning[END_REF]. Bottom: our modified algorithm.

Figure 1 :

 1 Figure 1: Top-down construction of a derivation tree. Top: the input image with the overlaid symbols. Bottom: the derivation tree under construction.

  , y , c) .

  D of the detectors, and define c(d) as the classes of C that have an intersection with class d ∈ D. In case we have several detectors, for classes in D, we define c(D) = d∈D c(d).

⊕

  = m * (x, y) w whole-window (x, y) m * + (x, y) Figure 2: Classification based on the local merit function(left) vs the higer-level merit function (right). The result of the window detection is presented in the middle.

Figure 3 :

 3 Figure 3: The gradient-based vs the detection-based distribution of split positions.

Figure 4 :

 4 Figure 4: Three window detection results (best viewed using magnification). Top row: results of our pattern search. Bottom row: corresponding detection rates.

Table 1 :

 1 Average performance of window detection on ECP CVPR 2010 and ECP Benchmark 2011.

	Methods	TPR (%) TNR (%)
	CC (τ = 5)	46	96
	CC (τ = 5) + PS	60	93
	RL (bin)	27	77

Table 2 :

 2 Average performance of window detection on the rectified eTRIMS dataset.

Table 3 :

 3 The average confusion matrices. Top-left: the original algorithm. Top-right: the algorithm with the new action distribution. Bottom-left: the algorithm based on the modified merit function. Bottom-right: our final algorithm with both modifications combined. dataset 1 (104 images). The window detector we used is CC(τ = 20)+PS, that experimentally performs best (see Table

Acknowledgements

This work was carried out in IMAGINE, a joint research project between Ecole des Ponts ParisTech (ENPC) and the Scientific and Technical Centre for Building (CSTB). We thank Olivier Teboul for his great help and fruitful discussion.