Wafa Aissa
email: wafa.aissa@lip6.fr

Laure Soulier
email: laure.soulier@lip6.fr

Ludovic Denoyer
email: ludovic.denoyer@lip6.fr

A Reinforcement Learning-driven Translation Model for Search-Oriented Conversational Systems

Search-oriented conversational systems rely on information needs expressed in natural language (NL). We focus here on the understanding of NL expressions for building keywordbased queries. We propose a reinforcementlearning-driven translation model framework able to 1) learn the translation from NL expressions to queries in a supervised way, and, 2) to overcome the lack of large-scale dataset by framing the translation model as a word selection approach and injecting relevance feedback as a reward in the learning process.Experiments are carried out on two TREC datasets. We outline the effectiveness of our approach in a retrieval task.

Introduction

Artificial Intelligence, and more particularly deep learning, have recently opened tremendous perspectives for reasoning over semantics in textbased applications such as machine translation [START_REF] Lample | Unsupervised machine translation using monolingual corpora only[END_REF], chat-bot [START_REF] Bordes | Learning end-to-end goal-oriented dialog[END_REF], knowledge base completion [START_REF] Lin | Learning entity and relation embeddings for knowledge graph completion[END_REF] or extraction [START_REF] Hoffmann | Knowledge-based weak supervision for information extraction of overlapping relations[END_REF]. Very recently, conversational information retrieval (IR) has emerged as a new paradigm in IR [START_REF] Burtsev | Search-oriented conversational ai (scai)[END_REF][START_REF] Joho | Cair'17: First international workshop on conversational approaches to information retrieval at sigir 2017[END_REF], in which natural conversations between humans and computers are used to satisfy an information need. As for now, conversational systems are limited to simple conversational interactions (namely, chit-chat conversations) [START_REF] Li | A diversity-promoting objective function for neural conversation models[END_REF][START_REF] Ritter | Data-driven response generation in social media[END_REF], closed worlds driven by domain-adapted or slotfilling patterns [START_REF] Bordes | Learning end-to-end goal-oriented dialog[END_REF][START_REF] Wang | A simple and generic belief tracking mechanism for the dialog state tracking challenge: On the believability of observed information[END_REF]) (e.g., a travel planning task requiring to book a flight, then a hotel, etc...), or knowledge-base extraction (e.g., information extraction tasks) [START_REF] Dhingra | Towards end-to-end reinforcement learning of dialogue agents for information access[END_REF].

In contrast, search-oriented conversational systems (SOCS) aim at finding information in an open world (both unstructured information sources and knowledge-bases) in response to users' information needs expressed in natural language (NL); the latter often being ambiguous. Therefore, one key challenge of SOCS is to understand users' information needs expressed in NL to identify relevant documents.

Formulating an information need through queries has been outlined as a difficult task [START_REF] Vakulenko | Conversational exploratory search via interactive storytelling[END_REF][START_REF] Agichtein | Improving web search ranking by incorporating user behavior information[END_REF][START_REF] Joachims | Optimizing Search Engines Using Clickthrough Data[END_REF] which is generally tackled by refining/reformulating queries using pseudorelevance feedback or users' clicks. In SOCS, there is an upstream challenge dealing with the building of the query from a NL expression that initiates the search session to avoid useless users' interactions with the system. This problem could be tackled for instance through deep neural translation models (e.g., encoder-decoder approaches) as initiated by [START_REF] Song | Translation of natural language query into keyword query using a rnn encoder-decoder[END_REF][START_REF] Zi Yin | Deepprobe: Information directed sequence understanding and chatbot design via recurrent neural networks[END_REF]. However, these methods learn the query formulation model independently of the search task at hand. To overpass this limitation, [START_REF] Nogueira | Taskoriented query reformulation with reinforcement learning[END_REF] have proposed a reinforcement learning model for query reformulation in which the reward is based on terms of documents retrieved by the IR system.

In this work, we propose to bridge these two lines of work: 1) machine translation to learn the mapping between information needs expressed in NL and information needs formulated using keywords [START_REF] Song | Translation of natural language query into keyword query using a rnn encoder-decoder[END_REF][START_REF] Zi Yin | Deepprobe: Information directed sequence understanding and chatbot design via recurrent neural networks[END_REF], and 2) reinforcement learning to inject the task objectives within the machine translation model [START_REF] Nogueira | Taskoriented query reformulation with reinforcement learning[END_REF]. More particularly, we propose a two-step model which first learns the translation model through the supervision of NL-query pairs and then refines the translation model using a relevance feedback provided by the search engine. It is worth mentioning that there does not exist SOCS-oriented dataset that both aligns users' information needs in NL with keyword-based queries and includes a document collection to perform a retrieval task. To the best of our knowledge, TREC datasets are the only ones expressing such constraint, but the number of NL-query pairs is however limited. To fit with the issue of dealing with large vocabulary and the dataset constraint, we frame the translation model as a word selection one which aims at identifying which words in the NL expression can be used to build the query. Our model is evaluated on two TREC datasets. The obtained results outline the effectiveness of combining reinforcement learning with machine translation models.

The remaining of the paper is organized as follows. Section 2 details our translation model. Section 3 presents the evaluation protocol and results are highlighted in Section 4. The conclusion and perspectives are discussed in Section 5.

2 Reinforcement learning-driven translation model

Notation and problem formulation

Our reinforcement learning-driven translation model allows to formulate a user's information need x expressed in NL into a keyword-based query y. The user's information need x is a sequence of n words (x = x 1 , ..., x i , ..., x n ). To fit with our word selection objective, the query y is modeled as a binary vector y ∈ {0, 1} n of size n (namely, the size of the natural language expression x). Each element y j ∈ y equals to 1 if word x i ∈ x exists in query y and 0 otherwise. For example, if we consider the NL as "Identify documents that discuss sick building syndrome or building related illnesses." and the key-words query as "sick building syndrome.", the expected query will be formulated as follows: y = (0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0) . The objective of our model f θ (with θ being the parameters of our model) is to estimate the probability p(y|x) of generating the binary vector y given the NL expression x. Since terms are not independent within the formulation of NL expressions and queries, it makes sense to consider that the selection of a word is conditioned by the sequence of decisions taken on previous words y <i . Thus, P (y|x) could be written as follows:

p(y|x) = y i ∈y p(y i |y <i , x) (1)
This probability is first learned using a maximum likelihood estimation (MLE) on the basis of NL-query pairs (Section 2.2). Then, this probability is refined using reinforcement learning techniques (Section 2.3). We end up with the network architecture used in the translation model.

Supervised translation model: from NL to queries

The translation model works as a supervised word selection model aiming at building queries y by using the vocabulary available in NL expressions x. To do so, we use a set D of N NL-query pairs

D = {(x 1 , y 1 ), ..., (x k , y k ), ..., (x N , y N )}.
The objective of the translation model is to predict whether each word x k i in the NL expression x k is included in the expected query y k . In other words, it consists in predicting the probability p(ŷ k i = y k i |ŷ k <i , x k ) that the i th element ŷk i of vector ŷk is equal to the same element y k i in the original query y k (namely, that ŷk i = y k i ) given the state of previous elements ŷk <i and the NL expression x k . This probability p(ŷ k i = y k i |ŷ k <i , x k ) is modeled using a Bernoulli distribution in which parameters are estimated through the probability distribution.

(x k , y k ), f (θ,x k ) = y k i ∈y k log(p(ŷ k i = y k i |ŷ k <i , x k ))
. The translation model is trained by maximizing the following MLE over the set D of NL-query pairs (x k , y k ):

L SM T = (x k ,y k )∈D log(f (θ, x k ))
(2)

Reinforcement learning

To inject the task objective in the translation model, we consider that the process of query building could be enhanced through reinforcement learning techniques. Therefore, the word selection could be seen as a sequence of choices of selecting word x t at each time step t. The choices are rewarded at the end of the selection process by a metric measuring the effectiveness of the query building process within a retrieval task. Particularly, the predicted query ŷ obtained from the binary vector ŷ is fed to a retrieval model to rank documents. For each NL expression x (and accordingly associated predicted query ŷ), we dispose of a set D x of relevant documents (also called ground truth). We note GT the set of n pairs (x; D x ). With this in mind, the effectiveness of the obtained ranking could be estimated using an effectiveness-driven metric (e.g., the MAP). Thus, the reward R for a generated query ŷ given the relevance feedback pair (x, D x ) is obtained as follows:

R(ŷ) = M AP (ŷ, D x ) (3)
At the end of the selection process, the objective function aims at maximizing the expectation of the search effectiveness over the predicted queries:

L RL (θ) = arg max θ E (x;Dx)∈GT ŷ∼f θ (x) [R(ŷ)] ( 4
)
where ŷ is given by the translation model f θ (x). This objective function is maximized using gradient descent techniques [START_REF] Baxter | Direct gradient-based reinforcement learning: Ii. gradient ascent algorithms and experiments[END_REF].

Model architecture

The model is based on an encoder-decoder building a query q from the input x. Particularly, each element x i of x is modeled through word embeddings w x i ; resulting in a sequence w x of word embeddings for input x. As shown in Figure 2, the encoder is a bi-directional LSTM [START_REF] Hochreiter | Long short-term memory[END_REF] aiming to transform the input sequence w x to its continuous representation h n . The decoder is composed of a LSTM in which each word x i is injected to estimate the word selection probability p(y i |y <i , x) using the hidden vector h n learned in the encoder network and the current word x i ; leading to estimate probability p(y i |y <i , x i , h n ).

3 Protocol design

Datasets

Since there does not exist yet SOCS-driven datasets including NL-query pairs, we use TREC tracks (namely, Robust 2004and Web 2000-2001). In these tracks, query topics include a title, a topic description and a narrative text; the two latter being formulated in natural language. To build query-NL pairs, we use the title to form the set of keyword queries and the description for the set of information needs expressed in NL. An example of a query-NL pair is: This NL-query building process results in 350 pairs in total as presented in Table 1.

We are aware that the use of TREC datasets is biased in the sense that it does not exactly fit with the expression of NL information need in the context of conversational systems, but we believe that the description is enough verbose to evaluate the impact of our query building model in this ex- [START_REF] Song | Translation of natural language query into keyword query using a rnn encoder-decoder[END_REF], will be carried out in the future.

We also analyze the issue of duplicate words into TREC descriptions since it can directly impact the query formulation process based on word selection in the word sequence of TREC descriptions. In practice, this might lead to select several times the same word to build the query, and, therefore, directly impact the retrieval performance. As shown in Table 1, the ratio of duplicate words in TREC descriptions over the whole set of queries is very low (1.1 duplicate words in average in each query for TREC Robust and 0.65 for TREC Web). This suggests that this issue is minor in the used datasets. We, therefore, decided to skip this issue for the moment.

Metrics and baselines

To evaluate our approach, we measure the retrieval effectiveness of the predicted queries. To do so, for each predicted query, we run the BM25 model through an IR system (namely, PyLucene1 ) to obtain a document ranking. The latter is evaluated through the MAP metric.

To show the soundness of our approach (namely, translating information needs expressed in NL into queries), we compare our generated queries to scenario NL feeding the natural language information needs (TREC descriptions in our protocol) to the IR retrieval system.

Since the objective of our model is to formulate queries, we also evaluate the effectiveness of original TREC titles (scenario Q). This setting rather refers to the oracle that our model must reach.

We mentioned that before training the selection model we transformed each x to its binary representation y based on the presence of the words in the ground truth query. The dataset being slightly biased by this binary modeling, we observed that not all the words existing in the query do exist in x. To analyze this bias, we also compare our approach with these binary queries (scenario Q bin) referring to the projection of queries Q on the vocabulary available in the NL description.

We also compare our model to a random approach which randomly selects 3 words from x to build queries (scenario Random).

Different variants of our model are also tested:

• SMT which only considers the first component of our model based on a supervised machine translation approach (Section 2.2). This variant could be assimilated to the approach proposed in [START_REF] Song | Translation of natural language query into keyword query using a rnn encoder-decoder[END_REF] in the sense that the machine translation is performed independently of the task objective.

• RL which only considers the reinforcement learning objective function (Section 2.3) without pre-training of the supervised translation model.

• SMT+RL which is our full model in which we start by pre-training the model using the supervised translation model (Section 2.3), and, then, we inject the reward signal in the translation probabilities (Section 2.4).

Implementation details

To transform each word x i to its vector representation w x i , we use Fasttext2 [START_REF] Bojanowski | Enriching word vectors with subword information[END_REF] pre-trained word embeddings. The encoder and decoders have one hidden layer with 100 hidden units each.

To train our model, we perform 10-fold crossvalidation. For the SMT+RL model, we start by a pre-training using the supervised translation model for 100 iterations. The training is then pursued by 1000 iterations while including the reinforcement learning approach. In the latter, the reward, namely the MAP metric, is estimated over document rankings obtained by the BM25 model in PyLucene. We use a minibatch Adam (Kingma and Ba, 2014) algorithm to pre-train the model and SGD for the reinforcement learning part. Each update is computed after a minibatch of 12 sentences.

Results

We present here the effectiveness of our approach aiming at generating queries from users' information needs expressed in NL. In Table 2, we present the retrieval effectiveness (regarding the MAP) of our model and the different baselines (NL, Q, Q bin, Random, SMT, and RL) described in section 3.2. From a general point of view, results highlight that in both datasets, our proposed model SMT+RL outperforms the different baselines with improvements that are generally significant, ranging from +3.22% to +468.91%.

More particularly, the effectiveness analysis allows to draw the following statements:

• The overall performance of the compared approaches generally outperforms the retrieval effectiveness of the NL baseline. For instance, on TREC Robust, queries generated by our model allows to significantly improve the retrieval performance of +15.25% regarding information needs expressed in NL (MAP: 0.10286 vs. 0.08925). This result validates the motivation of this work to formulate queries from NL expressions. This is relatively intuitive since NL expressions are verbose by nature and might include non-specific words willing to inject noise in the retrieval process.

• Our approach SMT+RL provides similar re-sults as the Q and Q bin. Since the objective function of our model is guided by the initial query Q transformed in a binary vector (Q bin), these baselines could be considered as oracles. We note however that our model obtains higher results (improvements from +3.22% to +16.26%) with a significant difference for the Q bin baseline for TREC Robust. To get a better understanding to what extent our generated queries are different from those used in baselines Q and Q bin, we illustrate in Table 3 some examples. While queries in Q identify the most important words leading to an exploratory query (e.g. "steel productions"), our model SMT+RL provides additional words that precise which facet of the query is concerned (e.g., "new methods of..."), and accordingly improves the ranking of documents.

• Our model SMT+RL is significantly higher than the SMT baseline which converges to a relatively low MAP value (0.06845 and 0.08891 for TREC Robust and TREC Web, respectively). This could be explained by the fact that our datasets are very small (250 and 100 NL-query pairs respectively for TREC Robust and TREC Web) and that such machine translation approaches are wellknown to be data hungry. Reinforcement learning techniques could be a solution to overpass this problem since they inject additional information (namely, the reward) in the network learning.

• The RL baseline achieves relatively good retrieval performances. As we can see from TREC Web, the RL model obtains a MAP of 0.16474 against 0.15913 for the NL baseline. The RL baseline allows approaching the retrieval performances of baselines Q and Q bin, although it obtains lower results. This reinforces our intuition that 1) applying machine translation approaches should be driven by the task (retrieval task in our context) and 2) reinforcement learning techniques provide good strategies to build effective queries. The latter statement has also been outlined in previous work [START_REF] Nogueira | Taskoriented query reformulation with reinforcement learning[END_REF].

• The comparison of our model SMT+RL regarding SMT and RL baselines outlines that reinforcement learning techniques might be more beneficial when a pre-training is performed. In our context, the pre-training is performed using the SMT model (Section 2.3) which helps the model to be more general and effective before using the reward signal to guide the selection process.

It is worth mentioning that we also trained in preliminary experiments a state of the art translation models such as a generative encoder-decoder RNN with attention mechanism, as done in [START_REF] Zi Yin | Deepprobe: Information directed sequence understanding and chatbot design via recurrent neural networks[END_REF][START_REF] Song | Translation of natural language query into keyword query using a rnn encoder-decoder[END_REF]. We did not report the results the model was not able to generalize in the testing phase over new samples from the NL-query dataset used in the training phase. This is probably due to the trade-off between the number of training pairs and the large size of the vocabulary which is not enough represented in different contexts. However, we believe that combining reinforcement learning with attention-mechanism for query-generation is promising. We let this perspective for future work.

Conclusion and future work

We propose a selection model to transform user's need in NL into a keyword query to increase the retrieval effectiveness in a SOCS context. Our model bridges two lines of work dealing with supervised machine translation and reinforcement learning. Our model has been evaluated using two different TREC datasets and outlines promising results in terms of effectiveness. Our approach has some limitations we plan to overcome in the future. First, our model is framed as a word selection process that could be turned into a generative model. Second, experiments are carried out on small datasets (250 and 100 NL-query pairs) that could be augmented using the evaluation protocol proposed in [START_REF] Song | Translation of natural language query into keyword query using a rnn encoder-decoder[END_REF]. In long term, we plan to adapt our model by totally skipping the query formulation step and designing retrieval models dealing with NL expressions.

Figure 1 :

 1 Figure 1: Overview of our reinforcement learning-driven translation model for SOCS

Figure 2 :

 2 Figure 2: Network architecture of our translation model

Table 1 :

 1 Dataset statistics separated per document collections ploratory work. Further experiments with generated datasets, as done in

	TREC track	collection pairs NL length avg of duplic. word in NL
	TREC Robust (2004)	disk4-5	250	15.333	1.108
	TREC Web (2000 2001) WT10G	100	11.47	0.65

Table 2 :

 2 Comparative effectiveness analysis of our approach. %Chg: improvement of SMT+RL over corresponding baselines. Paired t-test significance *: 0.01 < t ≤ 0.05 ; **: 0.001 < t ≤ 0.01 ; ***: t ≤ 0.001.

	Baseline		TREC Robust(2004)	TREC Web (2000-2001)
			MAP	%Chg	MAP	%Chg
	NL	0.08925 +15.25% ***	0.15913 +12.88% *
	Q	0.09804 +4.92%	0.16543 +8.58%
	Q bin	0.08847 +16.26% *	0.17402 +3.22%
	Random	0.01808 +468.91% *** 0.04060 +342.44% ***
	SMT	0.06845 +50.27% ***	0.08891 +102.04% ***
	RL	0.08983 +14.51% ***	0.16474 +9.04%
	SMT+RL 0.10286		0.17963
	NL		Q		Q bin	SMT+RL
	what are new methods of producing	steel producing	producing steel	new methods of pro-
	steel				ducing steel
	what are the advantages and or disad-	implant dentistry	implant	advantages disadvan-
	vantages of tooth implant				tages tooth implant
	find documents that discuss the toronto	toronto film awards	toronto film awards	the toronto film festival
	film festival awards				awards
	find documents that give growth rates of	where can i find growth	growth rates pine trees	growth rates of pine
	pine trees		rates for the pine trees	trees

Table 3 :

 3 Examples of query formulation for NL queries, the original query Q, the binary version Q bin of the original query, and our model SMT+RL.

http://lucene.apache.org/pylucene/

https://github.com/facebookresearch/ fastText/


H Nassar

A Lebée

L Monasse

Fitting surfaces with the Miura tessellation

The paper characterizes Miura surfaces defined as smooth surfaces that the regular periodic Miura ori can fit in the limit where the size of the creases is infinitely small compared to the typical radius of curvature. Based on a model due to Schenk and Guest, the Miura crease pattern is enriched so as to allow access to non-planar configurations. In contrast with previous work where the pattern is modified in order to fit different target surfaces, here we are interested in the converse problem of determining all the surfaces that can be fitted by one and the same pattern. The central result is a constrained nonlinear partial differential equation satisfied by the parametrization of any Miura surface. As an application, examples of bounded and unbounded Miura surfaces are presented along with a complete classification of axisymmetric and ruled ones.

Introduction

Finding the surfaces that the plane can deform into and fit under various kinematical constraints is a problem with a long history. Euler proved that an inextensible plane can only fit those surfaces qualified as developable such as cylinders and cones. Later, Gauss established a connection between curvature and in-plane deformations in the context of his "Theorema Egregium". Developable surfaces are thus characterized as surfaces with vanishing Gaussian curvature. Armed with Gauss' theorem, Chebyshev tackled the problem of clothing curved surfaces [Ghys 11]. He mathematically modeled a cloth as a plane grid of inextensible threads now known as a Chebyshev grid. As the cloth deforms, the grid can be bent and sheared but cannot be stretched or compressed. Recently, it was proven that Chebyshev grids can cover any surface with a sufficiently small total absolute Gaussian curvature [Samelson and Dayawansa 12,Masson and Monasse 16]. The relevance of these and other fitting problems to the mechanics of plates and shells hardly needs emphasis. We mention the application of Chebyshev grids to the design of gridshells useful in architecture [Douthe et al. 09,Baverel et al. 12].

Rigid folding constitutes another class of kinematical constraints. It is wellknown among origamists that fold tessellations allow for inextensible paper to fit curved surfaces in a way that challenges Euler's result [Lebée 15]. Euler had precluded folding by requiring smoothness whereas in the case of origami, paper is allowed to fold along predefined crease lines. Motivated by similar considerations, Resch and Christiansen famously attempted to fold a periodic crease pattern into an egg, namely the Vegreville Easter egg. The pattern was designed by Resch and is now referred to as the Ron Resch pattern [Resch and Christiansen 70]. After six months of computer-assisted trials, they failed [Blinn 88]. Their final design introduced cuts that transformed Resch's pattern into the so-called Kagome lattice capable of fitting surfaces admitting a conformal metric, i.e., surfaces that can be flattened by applying some isotropic, although inhomogeneous, in-plane strain field [Konaković et al. 16].

Lately, significant efforts, with remarkable outcomes, have been made to design crease patterns that can be folded to fit target surfaces [Tachi 09,Tachi 13,Zhou et al. 15,Dudte et al. 16]. Here, we are interested in the converse question, that is in determining the surfaces that can be fitted with one and the same periodic origami tessellation, namely the regular periodic Miura ori. More specifically, we will characterize Miura surfaces defined as smooth surfaces that the Miura ori can fit in the limit where the size of the creases is infinitely small compared to the typical radius of curvature. Building on previous work [Schenk and Guest 13,Wei et al. 13,Nassar et al. 17a,Nassar et al. 17b], our central result is a constrained nonlinear partial differential equation satisfied by the parametrization of any Miura surface. As an application, various Miura surfaces are constructed and fitted. In particular, a complete classification of axisymmetric and ruled Miura surfaces is derived. But first, a useful algorithm allowing to construct a Miura ori based on the giving of some of its vertices is presented.

2 Discrete modeling of the Miura ori The Miura ori crease pattern is depicted on Figure 1a. The pattern can be folded along edges: solid and dashed lines represent valley and mountain folds respectively. If faces remain rigid then the only deformation mode of the Miura ori is the one represented on Figure 1b. Physical models, say made out of paper, of the Miura ori exhibit however other in-plane and out-of-plane modes that require the faces to bend. To explain these modes within the framework of rigid origami, a modified, enriched, crease pattern can be introduced [Schenk and Guest 13]. It includes additional creases, namely the dotted lines in Figure 1c, that can be folded either in mountains or in valleys. It is this modified pattern that is of interest here. We further restrict our attention to the regular Miura ori, the one whose all edges are equal in length, for simplicity.

(a) (b)

Step 0

Step 1

Step 2

Step 7 All possible configurations of a Miura ori can be spanned by a fairly simple algorithm. First, assume given the three vertices A 0 , B 0 and A 1 shown on Figure 2a and that the oriented angle (B 0 A 1 , B 0 A 0 ) is in the interval ]0, 2π/3]. Then, vertex C 0 belongs to the intersection of three spheres of equal radii and centered on A 0 , B 0 and A 1 . Although in general two intersection points exist, the position of C 0 must accommodate a mountain fold along B 0 C 0 . Thus, C 0 is the unique intersection of the described spheres that is located above the plane (A 0 B 0 A 1 ). By iterating this procedure, if the red zigzag of Figure 2a is given at step 0, the next dotted zigzag can be uniquely determined in step 1. Then the construction is pursued until one zigzag exhibits an incompatible angle smaller than 0 or larger than 2π/3, or until the current zigzag contains a single point. In this manner, the Miura ori can be uniquely constructed by propagating one zigzag up and down. The construction can be formalized as the autonomous discrete Cauchy problem

zigzag n+1 -zigzag n = function(zigzag n ) (1)
where zigzag 0 is the initial red zigzag and is given. The above algorithm will terminate in 2N -1 steps at most when zigzag 0 contains 2N + 1 points. However, it is expected that the algorithm will terminate sooner due to the appearance of angles incompatible with the inextensibility constraints. The Miura ori spanned by in-plane uniform zigzags correspond to the states encountered in the flat-folding motion of Figure 1b. For circular zigzags embedded in a short cylinder of radius R with a uniform inner angle of π/3, the spanned Miura ori are illustrated on Figure 2b for a decreasing edge size r. It is seen then that as r/R approaches zero while other parameters remain the same, the Miura ori approaches a smooth saddle surface. The purpose of the next section is to characterize such smooth surfaces referred to as Miura surfaces.

Differential geometry of Miura surfaces

Hereafter, we present a set of algebraic identities satisfied by the metric and curvature of a general Miura surface. Each identity can be seen as the giving of either the in-plane or the out-of-plane Poisson's ratio of the Miura tessellation in specific directions [Schenk and Guest 13,Wei et al. 13]. Combined with relevant tools of differential geometry, the identities yield a nonlinear partial differential equation governing the parametrization of a general Miura surface. This equation constitutes the continuous equivalent to algorithm (1) and is the main result of the present paper. Last, given the parametrization of a Miura surface, we describe how the underlying fitting tessellation can be generated.

Parametrization and metric

Let S be a smooth surface and R be its minimum radius of curvature. We call S a Miura surface if the Miura ori with edge size r can fit it in the limit r/R → 0. Let φ : (x, y) ∈ R 2 → S ⊂ R 3 be a parametrization of S where x and y are the curvilinear coordinates along vectors w and w * respectively as shown on Figure 3. In other words, we set

φ x = w/r, φ y = w * /r, (2)
with x ≡ ∂ x and y ≡ ∂ y . The first fundamental form of S , also known as the metric, in the parametrization φ then reads

I = φ x , φ x φ x , φ y φ x , φ y φ y , φ y = 4 sin 2 (θ /2) 0 0 4 cos 2 (θ * /2) ≡ 4s 2 0 0 4c * 2 . (3)
Therein, we introduced the angles θ and θ * of Figure 3 and used the fact that w is orthogonal to w * due to mirror symmetry. For later purposes, similarly define c ≡ cos(θ /2) and s * ≡ sin(θ * /2). It is then elementary, although not straightforward [Schenk and Guest 13,Wei et al. 13,Nassar et al. 17a], to check that 2cc * = 1.

(4)

Angles θ ≡ θ (x, y) and θ * ≡ θ * (x, y) determine the folding state of the Miura ori in the vicinity of a point P(x, y) of the fitted surface S : for (θ = 0, θ * = 2π/3), the Miura ori is fully folded whereas for (θ = 2π/3, θ * = 0), it is fully unfolded.

In any case, (θ , θ * ) remains in the rectangle [0, 2π/3] 2 . However, we shall assume (θ , θ * ) ∈]0, 2π/3] × [0, 2π/3[ so as to keep I from being singular.

Second fundamental form

Let n = φ x × φ y /(4sc * ) be the unit vector directly normal to S . The second fundamental form is defined as

II = φ xx , n φ xy , n φ xy , n φ yy , n ≡ e f f g . ( 5
)
Together, forms I and II allow to determine the various curvatures of S . For instance, the normal curvatures in the directions x and y are respectively given by

κ x = e φ x 2 = e 4s 2 , κ y = g φ y 2 = g 4c * 2 , ( 6
)
whereas the Gaussian and mean curvatures are

K = eg -f 2 16s 2 c * 2 , H = ec * 2 + gs 2 8s 2 c * 2 . (7)
Remarkably, it was proven that the normal curvatures of the Miura ori satisfied the identity

κ y κ x = -tan 2 (θ /2) = - s 2 c 2 or ec * 2 + gc 2 = 0, (8)
in the context of infinitesimal strains, i.e., θ (x, y) = θ 0 + δθ (x, y), δθ θ 0 [Schenk and Guest 13,Wei et al. 13]. Fortunately, using two-scale asymptotic expansions, it is possible to demonstrate that the above identity holds for finite strains as well but only in the homogenization limit r/R 1 [Nassar et al. 17a]. The interested reader is referred to the cited papers for proofs.

As an important corollary, note that e and g have opposite signs so that K is necessarily negative: all Miura surfaces are saddle-shaped.

The fitting problem

Based on the above results, we now derive a continualized version of algorithm (1), i.e., its asymptotic equivalent written in differential form. For that purpose, we express the vectors φ xx , φ xy and φ yy in the basis (φ x , φ y , n). This amounts to calculating the Christoffel symbols [Ciarlet 06]. We find

φ xx = (s 2 ) x 2s 2 φ x - (s 2 ) y 2c * 2 φ y + e n, φ xy = (s 2 ) y 2s 2 φ x + (c * 2 ) x 2c * 2 φ y + f n, φ yy = - (c * 2 ) x 2s 2 φ x + (c * 2 ) y 2c * 2 φ y + g n. (9)
Then, thanks to equations ( 4) and ( 8), it is straightforward to check that the parametrization of a Miura surface satisfies the constrained nonlinear partial differential equation

φ xx 1 -φ x , φ x /4 + φ yy φ y , φ y /4 = 0, ( 10a
) (1 -φ x , φ x /4) φ y , φ y = 1, (10b) φ x , φ y = 0, ( 10c
) ( φ x , φ x , φ y , φ y ) ∈]0, 3]×]1, 4]. (10d)
Equation ( 10) constitutes the fitting problem and summarizes our central result: if S is a Miura surface then it admits a parametrization solution to (10). Equation ( 10) is the asymptotic equivalent to equation (1) in the sense that, provided with an initial condition (φ (x, y = 0), φ y (x, y = 0)), it generates a unique solution φ .

Having found a solution φ to (10), or equivalently to (3), ( 4) and ( 8), a fitting Miura ori with an arbitrarily small error can be constructed using algorithm (1). To do so,

• choose a small but finite discretization step r;

• construct the zigzag whose nodes are the A n and B m ,

n = 0 . . . N, m = 0 . . . N -1,
where N is a large integer of the order of 1/r; see Figure 2. Set1 A n = φ (x = nr, y = 0) and determine B n such that A n B n = B n A n+1 = r and that the vector sum B n A n + B n A n+1 is parallel to, say, φ y (x = nr + r/2, y = 0); • finally, feed the zigzag (A 0 B 0 . . . B N-1 A N ) into algorithm (1).

Discussion

Various open questions revolving around the fitting problem are worthy of investigation. These exceed the scope of the present paper and we content ourselves with a number of comments concluding this section.

First, it is remarkable that the quantities figuring in (10b) and (10c) are conserved in some sense. As a matter of fact, assuming only (10a) holds a priori, projecting onto φ x and φ y respectively yields

∂ x φ x , φ y 1 -φ x , φ x /4 = - 1 2 ∂ y ln[(1 -φ x , φ x /4) φ y , φ y ], ∂ y φ x , φ y 1 -φ x , φ x /4 = 1 2 ∂ x ln[(1 -φ x , φ x /4) φ y , φ y ]. (11)
Now add the assumption that φ satisfies the constraints (10b) and (10c) at y = 0 and for all x. Then, the above equations can be understood as an autonomous Cauchy problem in the variable y and the unknown functions φ x , φ y and ln[(1φ x , φ x /4) φ y , φ y ] with a vanishing initial condition. Therefore, by Cauchy-Lipschitz theorem, φ x , φ y and ln[(1φ x , φ x /4) φ y , φ y ] are identically null.

That is: φ satisfies (10b) and (10c) for all x and y. Therefore, due to this conservation result, it seems that formulating (10) as a Cauchy problem is advantageous. Indeed, by appending an initial condition compatible with (10b) and (10c), one would no longer need to worry about these constraints. Alternatively, problem (10) can be formulated as a Dirichlet problem. In that case however, it is not clear what boundary data will be compatible with (10b) and (10c).

Unfortunately, equation ( 10a) is elliptic and thus will generally lead to an illposed Cauchy problem [Alessandrini et al. 09]. That is, a general solution φ will be very sensitive to uncertainties and errors in the initial condition. In practice, when loop (1) is iterated long enough, a numerical instability appears. Then, the construction algorithm terminates prematurely before generating the full Miura tessellation. See Figures 9 and 10 below for examples.

In any case, finding what combinations of boundary/initial conditions guarantee existence, uniqueness and stability remains an open question of fundamental importance both practical and theoretical.

Case studies

In the following, we prove the existence of certain fittings based on the equations derived in the previous section. Specifically, we classify all axisymmetric Miura surfaces and we prove that all ruled surfaces can be realized as nearly flat-folded Miura surfaces with an arbitrarily small fitting error. The presented examples do not exhaust all possible Miura surfaces but illustrate the advantages that the continuum approach (10) brings over the discrete formulation (1).

Developable surfaces

Let S be a developable Miura surface, i.e., a surface with constantly vanishing Gaussian curvature K = 0. But since eg is already negative, equation ( 7) implies e = g = f = 0 so that S is a plane: the plane is the unique developable Miura surface. The plane can be fitted in a uniform manner, i.e., with constant θ , as shown on Figure 1b. Other non-uniform fittings of the plane, or at least parts thereof, can be generated at will by initiating algorithm (1) with an arbitrary in-plane zigzag. The Miura rose of Figure 4 is one such example where the initial zigzag is plane circular with a uniform inner angle θ o = π/3 and an arbitrary radius ρ o . Here in particular, ρ o was chosen so as to fit an integer number of unit cells in the circumference, e.g., ρ o = r sin(θ o /2)/ sin(π/N) with N a large integer. It is then easy to see, as if by conservation of the number of unit cells, that ρ/s is uniform. Since √ 3/2 is the maximum value of s, the radius of the rose is given by ρ M = √ 3 2 sin(θ o /2) ρ o and can be made arbitrarily large by making either ρ o larger or θ o smaller, both consistent with the fact that origami kinematics are scale-invariant.

The Miura rose is an example of an asymptotically axisymmetric plane fitting. Axisymmetry is hardly surprising the initial zigzag being axisymmetric itself. There exists however one other axisymmetric plane fitting generated by a non-axisymmetric initial zigzag. We call it the Miura ring and it is depicted on Figure 5a. The initial zigzag is visible on Figure 5b: it is fully collapsed on the inner circumference and fully extended on the outer one. Thus the radii ratio is

ρ M /ρ m = max c * / min c * = 2.
Two remarks are in order here. First, the Miura ring cannot be fully constructed with a single initial zigzag. Indeed, by referring to Figure 2a, one sees that the initial zigzag only permits to construct a single "petal" shown on Figure 5a. The ring can then be spanned by successive rotations. Note that these rotations are compatible with the fitting of a single petal as is visible on the magnified view of Figure 5b. Second, the profile of the inner angle of the initial zigzag θ (x) = 2 arctan(2x/ρ m ) would have been tedious to extract from a discrete description of the Miura ori.

Here, it is obtained by solving equations ( 3) and ( 4) for a parametrization of the form φ (x, y) = (ρ(x) cos(αy), ρ(x) sin(αy), 0). It is in such circumstances that the usefulness of a continuous description of the Miura ori is undisputed. Axisymmetric Miura surfaces are in particular invariant by rotation about the z-axis. Thus, surfaces of the first kind admit a parametrization of the form φ (x, y) = (ρ(y) cos(αx), ρ(y) sin(αx), z(y)).

(

) 12
By substitution into equations ( 3), ( 4) and ( 8), it is deduced that

ρ s = ρ o s o , ρ = 4α 2 ρ (α 2 ρ 2 -4) 2 . ( 13
)
The second equation can be integrated once into

z = cos β c = cos β o c o ; sin β = ρ 2c * , ( 14
)
where β is the angle that the tangent plane makes with the z-axis. Therein, parameters (ρ o , ρ o , θ o ) are determined by an initial condition, i.e., the initial zigzag. It can be argued that a Miura surface of the first kind belongs to one of the classes A, B and C schematically depicted on Figure 6. As a matter of fact,

• since K < 0, ρ is a convex function of z; • ρ is bounded since s is; • ρ cannot admit a horizontal asymptote other than 0 since ρ → ρ ∞ as z → ±∞
implies κ y → 0 and, by identity (8), s → 0 and ρ → 0; • and, if the range of existence of φ cannot be extended beyond a finite value of y denoted y f , then θ (y = y f ) is equal to either 0 or 2π/3.

Therefore,

• ρ can decrease from a maximum value ρ M to reach a non-zero minimum ρ m and then increase back to ρ M ; these profiles correspond to class A. In this case, at ρ = ρ m , β = 0 and θ = θ m = 0 so that

cos β c = 1 c m > 1. (15)
• ρ can increase from a null minimum value ρ m = 0 to reach a maximum value ρ M ; these profiles correspond to class B. Note that ρ m = 0 since otherwise ρ would be uniformly null by Cauchy-Lipschitz theorem. Thus, θ m = 0 and β m = 0 so that

cos β c = cos β m < 1. (16)
• ρ can increase from a null infimum non-minimum value ρ m = 0 to reach a maximum value ρ M ; such profiles correspond to class C. Here, as ρ → 0, θ → 0 and

β → 0 so that cos β c = 1. (17)
z = 4 3 ρ 2 M -ρ 2 - 2 √ 3 ρ M ln   4ρ 2 M -3ρ 2 + 2ρ M ρ   . ( 18
)
We call it the Miura horn and it is depicted on Figure 9. Note that while constructing the fitting of the Miura horn, we have encountered a numerical instability that forbids the Miura tessellation from reaching deep into the tail of the horn; see Figure 9b. This constitutes a first example of the stability issues discussed in subsection 3.4 in connection with elliptic Cauchy problems. We will comment on another example hereafter.

Axisymmetric surfaces of the second kind

Axisymmetric Miura surfaces of the second kind admit a parametrization of the form φ (x, y) = (ρ(x) cos(αy), ρ(x) sin(αy), z(x)).

By substitution into equations (3), ( 4) and ( 8), two conserved quantities emerge: To construct the underlying tessellations, equation (20) needs to be integrated so as to determine the initial zigzag. Here, closed-form expressions are available and read once the normalized initial conditions (θ o = θ m , ρ o = 1, ρ o = 0, z o = 0) have been adopted. Last, as θ m approaches 0, the numerical instability encountered with the Miura horn manifests here as well. By comparing the plots of Figure 10a, it is seen that for θ m ≤ π/6, the construction of the tessellation terminates abruptly before reaching the rhomboidal shape characteristic of algorithm (1) (see Figure 2a).

ρ c * = ρ o c * o , z /2 = s cos β = s o cos β o . (20
ρ = 4c 2 o x 2 + 1, z = 2s o x, x ∈ [-s * o , s * o ] (21)

Ruled surfaces

Call N and M the number of unit cells in the directions x and y respectively. So far, numbers N and M increased proportionally to R/r in such a manner that the constructed Miura surfaces maintained finite extents in the directions x and y of the order of Nr and Mr respectively. In this subsection, we explore Miura surfaces in the limit where θ uniformly approaches 0, that is in the regime 0 < Θ ≡ max(θ ) 2π/3. Accordingly, we let N grow at a faster rate inversely proportional to rΘ/R so that, as θ approaches 0 and the Miura ori flat-folds, a finite extent in the x direction is maintained.

It is then appropriate to rescale variable x by carrying the change of variables (X,Y ) = (Θx, y). The fitting problem (10) becomes

Θ 2 φ XX 1 -Θ 2 φ x , φ x /4 + φ YY φ Y , φ Y /4 = 0, (1 -Θ 2 φ X , φ x /4) φ Y , φ Y = 1, φ X , φ Y = 0, (Θ 2 φ X , φ X , φ Y , φ Y ) ∈]0, 3]×]1, 4]. (22)
Passing to the limit then yields

φ YY = 0, φ Y , φ Y = 1, φ X , φ Y = 0. ( 23
)
Finally, integrating twice, the parametrization of a Miura surface in the flat-folding limit turns out to admit the expression

φ (X,Y ) = Yu(X) + v(X), (24)
with u unitary and orthogonal v. These parametrizations cover all ruled surfaces. We therefore conclude that the set of nearly flat-folded Miura surfaces is exactly the set of all ruled surfaces.

Figure 11: Fitting a helicoid: The edges of the Miura ori are rendered in black whereas the helicoid is rendered as a solid opaque surface. The fact that the edges are visible from both sides of the helicoid reflects the fact that the absolute fitting error is of the order of r.

As a first example, recall that developable surfaces are ruled surfaces: they all can be fitted by a nearly-flat folded Miura ori. It is worth mentioning that our earlier result stating that the plane is the unique developable Miura surface holds as long as flat-folding is precluded as a singularity. In the present flat-folding limit however, all developable surfaces become Miura surfaces. We have already encountered two nearly developable Miura surfaces while classifying the axisymmetric surfaces of the first kind. Indeed, looking at Figures 7 and8, it is easy to see that, as θ o approaches 0, both cylindrical and conical Miura surfaces can be obtained.

The helicoid is a second example of a ruled but non-developable Miura surface. A helicoid with thread L is spanned in the limit (θ o → 0, r/L → 0) by a rectilinear zigzag with a uniform inner angle θ o and with teeth rotating around its axis with a uniform step of 2π/N such that 2 sin(θ o /2)Nr = L. The result is shown on Figure 11. The parameters used are such that r/L ∼ 1/100 and θ o as large3 as π/3.

Conclusion

A continuous characterization of the deformation modes of an enriched Miura ori, or equivalently, of the smooth surfaces that it can fit, has proven advantageous on many levels. It permitted to predict the existence of various Miura surfaces and in particular to establish a complete classification of axisymmetric and ruled ones. It also allowed to gain deeper insight into the discrete kinematics of the tessellation and to raise a number of issues regarding its stability in connection to the type of enforced boundary/initial conditions for instance. Not to mention that the present purely kinematical study is a first step in establishing a continuum mechanical model of the tessellation that takes into account elasticity effects.

Figure 1 :

 1 Figure 1: The Miura crease pattern: (a) original pattern; (b) its unique deformation mode; (c) modified pattern.

Figure 2 :

 2 Figure 2: (a) Algorithm: construction by zigzag propagation. (b) Convergence study: surfaces spanned by a uniform circular zigzag as the edge size decreases.

Figure 3 :

 3 Figure3: A Miura surface: a blow-up of a neighborhood centered on a point P reveals the microstructure of the Miura ori. The underlying vectors w and w * are tangent to the surface and define the coordinate system (x, y).

Figure 4 :

 4 Figure 4: Two views of the Miura rose.

Figure 5 :

 5 Figure 5: The Miura ring: (a) rows of unit cells (x = cste) are concentric circles; (b) a magnified view. Note that ρ M /ρ m → 2 as r/ρ m → 0.

Figure 6 :

 6 Figure 6: Classification of axisymmetric Miura surfaces of the first kind.

7:

  Axisymmetric Miura surfaces of the first kind, class A: instances for varying θ o and a vanishing β o .

Figure 8 :

 8 Figure 8: Axisymmetric Miura surfaces of the first kind, class B: instances for varying β o and a constant θ o = π/2. In summary, homotheties and rigid body motions aside, axisymmetric Miura surfaces of the first kind form a two-parameter family of surfaces parametrized by two angles, namely β o and θ o , and classified into three classes A, B and C depending on whether cos β o /c o is smaller, larger or equal to unity, respectively. Instances of class A are depicted on Figure 7 for a varying θ o > 0 and a vanishing β o . Instances of class B are depicted on Figure 8 for a varying β o < π/4 and a constant θ o = π/2. The unique surface of class C admits the implicit equation

Figure 9 :

 9 Figure 9: The Miura horn or the unique axisymmetric Miura surface of the first kind, class C: (a) global view; (b) magnified view. Both the surface (semi-transparent, blue) and its discrete fitting (black edges) are depicted.The fitting reaches deeper into the tail with smaller errors as r decreases further but in any case fails to account for the infinite extension of the surface due to a visible numerical instability.

)

  Using similar techniques as before, these surfaces can be classified into two classes A and B. Surfaces of class A have a minimum non-vanishing angle θ = θ m attained at β = 0 and therefore constitute a one-parameter family of surfaces parametrized with θ m ∈]0, 2π/3[. The unique surface of class B has a vanishing infimum θ m = 0 and is identical to the Miura ring. Here too, algorithm (1) cannot generate the full surface out of a single initial zigzag. Instead a portion can be constructed and then the surface spanned by successive rotations as described for the Miura ring of Figure5. Surfaces and partial fittings are visible on Figure10.

Figure 10 :

 10 Figure 10: Axisymmetric Miura surfaces of the second kind, class A: (a) instances for varying θ m ; (b) magnified view of the tessellation for θ m = π/3. The Miura ring, the unique surface of class B, is realized in the limit θ m → 0 + .

Then, A n+1 -A n = rφ x + o(r) in accordance with equation (2).

More precisely, one reflection and one glide reflection with a vanishingly small translation.

Why asymptotics carried in the vicinity of 0 should be valid near π/3 is a mystery. An explanation might be found in the fact that (24) is identical to a first order Taylor expansion in Y . But this will not be pursued here.


High spatial resolution detection of low-energy electrons using an event-counting method, application to point projection microscopy

Evelyne Salançon * , Alain Degiovanni, Laurent Lapena and Roger Morin Aix Marseille Univ, CNRS, CINAM, Marseille, France Abstract: An event-counting method using a two-microchannel plate stack in a low-energy electron point projection microscope is implemented. 15µm screen-spatial resolution i.e. the distance between first-neighbor microchannels is demonstrated. This leads to a 7 times better microscope-resolution. Compared to previous work with neutrons 1 , the large number of detection events achieved with electrons shows that the local response of the detector is mainly governed by the angle between the hexagonal structures of the two microchannel plates. Using this method in point projection microscopy offers the prospect of working with a source-object distance one order of magnitude greater (500nm instead of 50nm), advancing toward atomic resolution.

1-Introduction

The fundamental spatial resolution of a microscope is given by Abbe's diffraction limit. This means that the smallest visible distance is given by = . .

, with λ the wavelength of the wave used and N.A. the numerical aperture. The N.A. characterizes the angle over which the system detects waves propagating from the object. For a pure (lensless) projector, it is given by the geometry of the setup . . = √ + ⁄ where R is the radius of the detector and D the object to screen distance. Thus, for a projector:

= √ [1]
However in order to obtain this resolution ε, a suitable detector is required. Since a microscope locates absolute positions of a point in the object plane, a displacement of ε in the object plane has to be detectable in the image plane. In that plane the corresponding displacement is ε where G is the geometrical magnification of the projector i.e. =

, where d is the source-object distance. Therefore the screen-spatial resolution η required for the detector is = , thus:

= [2]
Combining [1] and [2], we obtain for a projector:

= √ ( ) [3]
Or, for high enough magnification (D>>d) and D≥2R:

≈ . [3']
This shows that for a detector of given screenresolution η and radius R a microscoperesolution ε (limited by Abbe's criteria) can always be obtained but at the cost of working at a small enough source-to-object distance d.

A low-energy electron point projection microscope (figure 1) is a projector based on an electron point source 2 . The image detector is usually a microchannel plate fluorescent screen assembly of radius R=20mm. The screenresolution η of this assembly is about 100µm [see below and 3 ]. Up to now, the microscopespatial resolution obtained with this setup has been about 1nm 4, 5, 6, † . In addition to angle limitations in the emission or in the scattering process and to noise problems (e.g. vibrations, parasitic electromagnetic fields) this is due to limitations inherent to the detector itself, especially in terms of its spatial resolution η. Equation [3'] shows that for 100 eV electrons (λ=1.22Å), a microscope-resolution of λ can only be obtained for < 50"#. † Using a 75mm diameter detector, Fink's group at Zürich recently achieved 0.8 nm resolution on protein deposited on graphene.

Working at such short source-object distances, however, raises numerous problems with respect to high resolution imaging: (i) the field on the object increases with the decrease of d, causing image distortion 7,8,9,10,11 ; (ii) decreasing d induces a decrease in the emission voltage 2 , which impacts the resolution via both the increase in λ and the blurring effect resulting from the electron energy spread; (iii) decreasing d increases the influence of the finite size of the source 12,13 ; (iv) the small d approach prevents the use of promising sources 14 more bulky than field emission tips, like the one used here.

An event-counting detection method using a microchannel plate (MCP) stack with a fluorescent screen and a CCD camera is already used for photon or neutron detection 1, 15,16,17 and shows sub-15µm spatial resolution. The method is based on the fact that one single particle impact at the channel plate input creates one single stain on the screen. The centroid of this stain is attributed to the impact position of one single particle and to one pixel of an eventcounting image. By accumulating event-counting images, a high spatial resolution image is obtained.

Here, using a two-microchannel plate (chevron) fluorescent screen assembly, the event-counting detection method is applied to low-energy electron imaging in a point projection microscope. Demonstration of 15µm resolution of the detector paves the way for working with a source-to-sample distance about one order of magnitude greater than previously achieved 4,5,6 . Moreover, the large number of detection events counted with electrons enables more accurate analysis of the detector response than previously achieved with neutrons 1 .

Note that the counting method used in transmission electron microscopes 18 could not be applied here because electron energy is too small. Inversely, the technique reported here cannot be applied for high energy electrons because of the MCP limitations.

Materials and methods

The low-energy electron point projection microscope (figure 1) is a lensless setup 19 . An electron point source illuminates a perforated object (e.g. holey carbon film) which elastically scatters electron waves. The interference pattern of the reference wave (directly propagating from the source) and the scattered wave (propagating from the object) is produced on the fluorescent screen. The recorded pattern, showing a shadow surrounded by fringes, corresponds to the so-called hologram of the object 20 . The numerical reconstruction of this hologram gives a magnified image of the object 21 . The spatial resolution given by the microscope is obtained from the reconstructed image of the object. Usually, the low-energy electron source is an ultra-sharp field emission W tip but noble-metalcoated W tips 22 , alloy tips 23 or a carbon nanotube 24 have also been used. Here, a more bulky recently developed source 14 is used, based on the point emission from a mineral particle deposited on the apex of a 12µm diameter carbon fiber. The object is a holey carbon film which is sufficiently perforated to obtain a reference wave. The source-to-object distance d, is controlled by a piezoelectric actuator providing a distance control from 100nm to 2.5cm. The screen is 56 cm away from the source. Because individual stains are required for the eventcounting method, the impact of one single electron at the entrance of the MCP has to produce a detectable stain on the screen.

Therefore instead of a one-stage MCPfluorescent screen assembly, a two-stage MCP (Hamamatsu -F2221-21P) is used: the amplification given by the manufacturer is about 10 6 that means up to a hundred times higher compare to one-stage. The optical microscopic view of the MCP (figure 2) shows a lattice hexagonal structure for the arrangement of the microchannels, whose diameter is only 12µm. This suggests that electron impacts cannot be localized more accurately than this under our conditions (the minimum microchannel size available is 7µm). The event-counting method consists in collecting the centroid of each single stain. An individual stain is separately identified provided it is not too close to another. Thus electron intensity and time frame have to be adjusted in order to detect only a few stains per frame. With an exposure time of 10ms, we tune electron intensity to about 10 ()* on a (3 × 3) ##² part of the screen. This corresponds to a detection rate of about 5 electrons (stains) per (512x512) pixel frame. The detection rate could be higher than the one used but cannot give more than 500 stains per frame to be able to separate them. This gives a maximum intensity of about 10 -14 A on a (3 × 3)##².

The size and intensity of one stain depends on the amplification of the MCP. With a 2kV supply applied to the two-stage MCP and a 4kV acceleration voltage between the MCP exit and the screen, we observe stains with a typical full width at half-maximum (FWHM) of about 60µm.

The signal-to-noise ratio (-

= . /
) calculated by measuring the typical gray level of a stain (µ) and the standard gray level deviation of the whole recorded image (σ) is about 10.

The determination of centroids uses the plugin QuickPalm 25 under ImageJ. QuickPALM is a set of program developments for PALM and STORM ("photoactivated localization microscopy" and "stochastic optical reconstruction microscopy"). A stain is detected depending on the Signal-to-Noise ratio (SNR) and the typical full width at half maximum (FWHM). A first frame is recorded to determine the SNR and FWHM of a typical stain. These values are introduced as parameters in the program in order to assign the value '1' to one pixel in the center of one stain. Then a sequence of frames can be recorded and analyzed in order to produce multiple binary frames that are added together to create a counting image. Each frame is sent to the computer, recorded and then treated either immediately or at the end of the series. In the first case, recording time is lost between frames and in the second case, a computer memory of almost 1TB is required. To obtain representative information in the screen, considering the highest intensity (10 -14 A on on a (3 × 3)##²) available with this method and the highest frame rate available with actual cameras, the whole screen can be completely lightened after minimum 500 frames then a minimum time of about 5sec. With this electron rate, the minimum computer memory usable is about 4GB.

Therefore, we first record the whole image in analogical mode and second, we record only a zone of interest in counting mode. The analogical mode corresponds to the direct gray level image accumulated with the camera whereas the counting mode consists on adding the centroid single-event short frames. The emission intensity has to be tuned so as both to record an analogical image in a few seconds and to record the same image for hours (in conditions described here) in counting mode. In practice, in a low-energy electron microscope, the intensity increases with the electric field which increases with the source-object distance decrease and with the voltage applied to the source that gives the electron energy.

2-Results and discussion

To compare analogical and counting modes in terms of spatial resolution on the screen, the shadow of the edge of a carbon membrane is produced at low magnification in both modes for the same exposure time t and the same electron dose. The cumulative images from t=3sec to 3000sec are shown in figure 3. The first observation is that the image quickly appears in analogical mode. The second information is given from the final signal-to-noise ratio ( 0 ) obtained in both conditions. It is measured with the ratio between the mean gray levels or the mean number of counts in the black part and in the lightened part of the analogical or counting images respectively. Here we find ( 0 ) 1213 = 4.3 and ( 0 ) 56728 = 7.7. This signal-to-noise ratio is always better in counting mode but can be much higher if the SNR chosen to detect stains is much higher. For example, figure 3 was constructed with a SNR=20 if we choose a SNR=30 then the final signal-to-noise ratio is about ( 0 ) 56728 = 16

and the bright spots observables in figure 3 decrease. Finally, from figure 3 we can measure that the spatial resolution is better in counting mode. This is illustrated by the intensity profile through the edge of the shadow in figure 4. Profiles are fitted by an error function (convolution of a step function assumed for the shadow and a Gaussian response of standard error σ assumed for the detection). In analogical mode, the fit closely follows the recorded profile and corresponds to σ=95µm (coefficient of determination: = 0.99). In counting mode, σ=18µm although the recorded profile fluctuates a lot around the fit (coefficient of determination: = 0.08). A close look at the profile indicates that detection events are counted every 15µm. This suggests that detection events appear only at the microchannel locations, none being counted in the surrounding area. At the edge of the counting profile the signal changes abruptly, suggesting that its position is indeed defined by the size of the channel. Measuring the spatial resolution of the detector by its response to a sharp edge image is not the sole method possible. Because an electron impact can only be detected when it occurs inside a channel (as suggested by the counting record of figure 4), the arrangement of these channels can be determined simply by looking at the bright part of the image where the average intensity is constant. Such a counting image is shown in figure 5. Several observations can be made: first, the microchannel bundle boundaries visible in optical microscopy are recognizable; second, detection spots appear along lines; third, the intensity of these spots is highly variable. Note that the lines (figure 6a) cross the boundaries of the bundles without changing direction. These lines look like the reticular lines of the 2D lattice of the microchannels observed in optical microscopy where a distance between adjacent channel centers = = 14.6μ# is measured. However because of the change in intensity of the spots, we perform FFT and amplitude analysis of the image. This FFT (figure 6b) shows a hexagonal structure with a distance between reticular planes of

? = = √@
, with a the lattice parameter. This result already obtained with neutrons 1 confirms the previous observation at an edge. This hexagonal structure in the FFT appears with relatively poor statistical sampling (i.e. with widely fluctuating intensity of the spots), which means that the structure of the MCP suggests that of a hexagonal bi-dimensional crystal. With larger statistical sampling (>500.000 detection events on a 512x512 pixel image), a hexagonal superstructure appears in the FFT (in blue in the FFT, figure 6c). This superstructure is rotated by A = (15 ± 1)° from the microchannel hexagonal lattice. Its lattice parameter s presents a dimension ratio of D 1 = 3.6 relative to the lattice parameter a of the hexagonal microchannel structure. While intensity is not uniform in the two zones identified in figure 5, this superstructure is the same in both zones. The geometry of the chevron mounts of the microchannels was held responsible for a "nonsymmetric hexagonal pattern", which is not sufficient to explain a superstructure in the FFT. We show hereafter that the superstructure likely results from a Moiré effect induced by the rotation of one MCP with respect to the other in the assembly. Calculations to determine the different rotation angles for which a superstructure appears are presented in the appendix. The channel network is considered as a perfect hexagonal lattice. The shortest superstructures (with lattice parameter s such that Another effect results from the relative positioning of the two plates. Looking at the stain shape in original data records, it appears that three different kinds of stain are observable (figure 8a): two are circular with diameters of about 40µm and 60µm and one is elliptical, about 60µm long and about 40µm wide. Although the observed stain is much bigger than the channel diameter, it seems that the corresponding kind of site depends on the number of channels of the second MCP that overlaps one channel of the first plate. Figure 8b shows the image built by superimposing an optical microscopy image of the MCP with the same image rotated 27.8°: the three kinds of site are clearly identified in this view. Analysis of the size distribution of stains (figure 8) indicates two characteristic sizes: 40 and 60µm. Length and width are reported together so these two peaks are characteristic of the three kinds of site. However, a different distribution is found in zone 1 and zone 2 as defined in figure 5. Clearly the ratio of 60µm stains to 40µm stains is much higher in zone 2. To see how this can be related to the stacking of the plates, we examine a small random translation in addition to the 28° rotation between the two plates. This is shown in figure 9. The FFTs produced by these two situations are the same, which may explain the variable intensities observed in zones 1 and 2 in figure 5.

3-Conclusion

Two methods were used to determine the resolution of an imaging detector composed of a two-stage MCP fluorescent screen assembly used in a counting mode in a low-energy electron projection microscope. The first method is based on viewing the edge of a carbon membrane, the second method is based on a uniform electron illumination of the assembly. Both methods show that the response of the detector is described by a network of detection sites that closely reflects the geometrical structure of the microchannel packing. This leads to a spatial resolution of ~15 µm which is the shortest distance between the centers of two microchannels. While the overall response reflects the hexagonal structure of the microchannel packing in one plate, we show that the local response of the detector varies because of the relative positioning of the two MCPs (rotation and translation).

In a low-energy electron point projection microscope the enhanced resolution of the detection, from 100µm (previously obtained by conventional recording of the image on the screen) to 15µm distance between microchannels (in the present work, but possibly 10 µm with smaller diameter microchannels), paves the way to working with a larger sourceto-sample distance (about one order of magnitude greater than previously achieved). This widens the source property requirements for subnanometer resolution imaging. It would be worth implementing immediate treatment of detection events inside the camera (determination of the centroid of stains) before transfer to the computer to improve image acquisition time.

discussions on the statistically representative information.

Figure 1 :

 1 Figure 1: Low-energy electron point projection microscope. A CCD camera records the hologram produced via one microchannel plate in front of a fluorescent screen (the "bidimensionnal detector"). The numerical holographic reconstruction of this record gives the image of the object with a resolution of about 1nm in the best cases.

Figure 2 :

 2 Figure 2: Optical microscopic view of the microchannel plate: large hexagonal bundles of channels are observable (side length=450µm).The lattice parameter of the microchannel hexagonal structure is about a=14.6µm (channel diameter is 12µm).

Figure 3 :

 3 Figure 3: Construction of cumulative analogical and counting records. The upper line corresponds to the analogical images with a gray level representation; the lower line corresponds to the counting images with calculation of stain centroids and the sum of each binary image. I=8.5x10 -17 A, (3x3) mm² area on the screen; 2kV applied to the MCPs, electron energy of about 500eV.

Figure 4 :

 4 Figure 4: Signal profiles along the same line of analogical and counting images of the same edge.

Figure 5 :

 5 Figure 5: Counting image in a uniformly lit part of the screen: detection is localized (bright spots), a microchannel bundle is located by the hexagonal red line. A polygonal boundary (green line) between two zones (zone 1 and 2) of different average intensity is visible.

Figure 6 :

 6 Figure 6: (a) close-up of a hexagonal bundle with lines indicating the main alignments of detection sites; (b) FFT of the screen image for $ = 3000 × 10ms: the lattice parameter measurable in the FFT is a=14.6µm (c) FFT of the screen image for $ E = 300000 × 10ms: a superstructure appears (blue) (s=46.5µm). Its FFT is (15 ± 1)° rotated from the main channel structure. This superstructure was hardly visible in the Tremsin et al. 1 records due to poorer statistical sampling than in the present work. This means that their interpretation of the FFT result cannot satisfactorily explain the whole superstructure.The geometry of the chevron mounts of the microchannels was held responsible for a "nonsymmetric hexagonal pattern", which is not sufficient to explain a superstructure in the FFT. We show hereafter that the superstructure likely results from a Moiré effect induced by the rotation of one MCP with respect to the other in the assembly. Calculations to determine the different rotation angles for which a superstructure appears are presented in the appendix. The channel network is considered as a perfect hexagonal lattice. The shortest superstructures (with lattice parameter s such that

D 1 < 6 )

 16 appear for only 5 rotation angles: F =21.8°, 27.8°, 13.2°, 17.9° and 9.4° with the respective dimension ratio D 1 =2.64, 3.60, 4.36, 5.57, 6.08. Clearly the present work corresponds to the second case, since the corresponding dimension ratio of 3.6 is in close agreement with the experimental result of figure 6c. A simulation of the FFT created from a 27.8° rotation between MCPs is presented in figure 7. In this simulation the FFT is applied to an image built by superimposing one part of the optical microscopy view of the MCP (figure 2) on an identical part of the view which is rotated 27.8°. This FFT shows a rotation angle in the Fourier space: A = G = 13.9° that appears quite similar to the experimental pattern of figure 6c.

Figure 7 :

 7 Figure 7: Simulation of rotation between MCPs and the related FFT. A rotation of 27.8° between MCPs leads to a FFT giving a dimension ratio between the microchannel network and the superstructure of D 1 = 3.6 and an angle between them of A = 13.9°.

Figure 8 :

 8 Figure 8: Histogram of stain size distribution in zones 1 and 2 of figure 5 (from original data) -(a) shape of detected stains showing three kinds of site: two circular (blue and green) and one elliptical (red) -(b) sum of the microscope view of the MCP and the same view rotated (here 27.8°). One channel from the first MCP overlaps with one (blue), two (red) or three (green) channels of the second MCP.

Figure 9 :

 9 Figure 9: Illustration of the different kinds of site obtained with and without translation. The white part in channels defines the number of sites impinging on the second MCP. Without translation there are few sites where one

W. Stocker, HW Fink and R. Morin, Ultramicroscopy

31, 379 (1989) 3 E. Steinwand , J.-N.Longchamp, H.-W.Fink, Ultramicroscopy 110, 1148 (2010)

Acknowledgment

The authors would like to thank Marjorie Sweetko for improving the English of this article and Yannick Boursier from CPPM for constructive

Appendix

The calculation consists in the identification of rotations of two hexagonal lattices leading to a periodic structure. Because of the bijection between a plane and the complex number space, positions of nodes of the lattice are identified by complex numbers. The distance ratio between the structure and the superstructure is:

And the correspondence of scalar and vector products gives: