Lucas Barthelemy
email: lbarthelemy@quarkslab.com

Delaram Kahrobaei
email: dkahrobaei@gc.cuny.edu

Guénaël Renault
email: guenael.renault@ssi.gouv.fr

Zoran Šunić
email: zoran.sunic@hofstra.edu

Quadratic time algorithm for inversion of binary permutation polynomials

Keywords: Permutation polynomial, Lagrangian interpolation, Obfuscation

In this paper, we propose a new version of the Lagrangian interpolation applied to binary permutation polynomials and, more generally, permutation polynomials over prime power modular rings. We discuss its application to obfuscation and reverse engineering.

Motivation and Introduction

Permutation polynomials in the context of Galois' fields are very well studied in particular for their applications in cryptography. The study of binary polynomials (polynomials with coefficients in an integer ring modulo a power of 2) is less extensive, but it has been shown recently that they are important for computer security. As discussed in [START_REF] Zhou | Information hiding in software with mixed boolean-arithmetic transforms[END_REF] and in [START_REF] Barthelemy | Binary permutation polynomial inversion and application to obfuscation techniques[END_REF], a straightforward application of binary permutation polynomials is obfuscation. Here we define obfuscation as a way to write computer programs that prevents reverse engineering of applications while minimizing the overhead in memory/computation cost.

In comparison with finite field permutation polynomials, the binary polynomials allow fast computation of bijective functions, since they can be directly implemented with low level arithmetic operations on computers. Moreover their use adds diversity to obfuscation techniques. The last point is of primary concern for obfuscation. Indeed, obfuscation usually does not rely on one overwhelming method, but on an aggregation of several layers of different techniques that aim to prevent automated attacks. For example, in [START_REF] Barthelemy | Binary permutation polynomial inversion and application to obfuscation techniques[END_REF] new classes of polynomials were considered and proved to be resistant to the attacks defined in [START_REF] Biondi | Effectiveness of synthesis in concolic deobfuscation[END_REF].

The second-named author was partially supported by a PSC-CUNY grant from the CUNY Research Foundation and by the ONR (Office of Naval Research) grant N000141512164

In this application context, the study of permutation polynomials is purely algorithmic and a central operation is the computation of the inverse of such a polynomial.

Newton's method for inverting binary permutation polynomials is an effective algorithm, but we present in this paper a new technique based on Lagrangian interpolation with two important properties:

-In a designer point of view, it is very important to measure the strength of any obfuscation technique based on binary permutation polynomials. The interpolation algorithm analyzed in this paper is proven to have a fixed complexity. This provides a more precise framework when measuring attack complexities with regard to computational overhead of using a binary permutation polynomial. -From the reverse engineering point of view, this algorithm enables inversion techniques in a black-box context (i.e. when an encoding function is given as an evaluation function only). This is of importance when considering the reliance of encodings based on binary permutation polynomials since this algorithm can retrieve the explicit function through interpolation.

In addition, our version of Lagrangian interpolation allows a better understanding on how to use binary permutation polynomials. This should prove useful for future work on the subject.

2 Interpolation of the inverse polynomial over Z 2 n

Reduction of integer polynomials

Integer multiples of Newton polynomials may be used to reduce any integer polynomial to a polynomial of relatively small degree (no greater than n+log 2 n) that induces the same function on Z 2 n . The approach follows Mullen and Stevens [START_REF] Mullen | Polynomial functions (mod m)[END_REF] and has recently been used in [START_REF] Barthelemy | Binary permutation polynomial inversion and application to obfuscation techniques[END_REF] in the context of inversion of polynomials by using Largange interpolation and also Newton's method.

For i ≥ 0, let t i be the largest integer such that 2 divides !, and let d n be the largest integer i such that n -t i > 0. Note that d n is always odd and not greater than n + log 2 n. Define

P i (x) = 2 n-ti i-1 j=0 (x -j) for i = 0, 1, . . . , d n , and P dn+1 (x) = dn j=0 (x -j).
Each polynomial P i (x), for i = 0, 1, . . . , d n + 1, is an integer multiple of the Newton polynomial i-1 j=0 (x -j) of degree i, and only the last one, P dn+1 (x), is monic. The ideal I of Z[x] generated by P 0 (x), . . . , P dn+1 (x) consists precisely of all integer polynomials that induce the zero function on Z 2 n . Define the set of reduced polynomials R n as the set of all integer polynomials b 0 +b 1 x+• • •+b dn x dn of degree at most d n , such that, for i = 0, . . . , d n , 0 ≤ b i < 2 n-ti .

For every integer polynomial P (x) there exists a unique reduced polynomial P R (x) such that P (x) and P R (x) induce the same function on Z 2 n . The reduction is performed as follows. First, P (x) is replaced by its reminder modulo the monic polynomial P dn+1 (x), and this yields a polynomial R(x) of degree at most d n . If R(x) is reduced we are done. Otherwise, let i be the largest degree such that the i-coefficient of R(x) is not in the range from 0 to 2 n-ti -1 and let c i be the value of this coefficient. Then there exists a nonzero q such that c i = 2 n-ti q + r, where 0 ≤ r ≤ 2 n-ti -1. Thus, the i-coefficient of the polynomial R(x) -qP i (x) is equal to r, which is in the correct range. Continuing in the same fashion we may push all coefficients, one by one, in the order from highest to lowest degree, into the correct range and obtain a reduced polynomial.

Precise description of the inversion problem

If the degree of the original integer polynomial P (x) is high and/or if its coefficients are large integers, the reduction procedure may take a long time. We are not interested in this issue, our quadratic algorithm assumes that P (x) is given either in reduced form or as a black box that can calculate the sequence of values P (0), P (1), . . . , P (d n ) in Z 2 n in O(n 2 ) time. Note that if we are given a reduced polynomial P (x), then we can calculate P (0), P (1), . . . , P (d n ) in O(n 2 ) time.

We formulate precisely the input and output for our problem.

Let P (x) be an integer polynomial that induces a permutation on Z 2 n . Input: the sequence of values P (0), . . . , P

(d n ) in Z 2 n .
Output: the sequence of coefficients b 0 , b 1 , . . . , b dn of the unique reduced polynomial Q(x) that induces the inverse permutation to P (x) on Z 2 n .

We know with certainty that a polynomial solution exists, since P (x) induces a permutation on a finite set, which implies that some iteration of P (x), which is also a polynomial with integer coefficients, induces the inverse permutation.

Our quadratic "time" complexity actually refers to the number of multiplications and/or additions and/or inversions of units in Z 2 n necessary to calculate the sequence of coefficients of Q(x). The numbers involved in these calculations have O(n) digits, but each addition/multiplication/inversion is counted as being performed in unit time.

We state our main result.

Theorem 1. Let P (x) ∈ Z[x] be a polynomial that induces a permutation on Z 2 n , given by its sequence of values P (0), . . . , P (d n ) in Z 2 n . There exists an algorithm of time complexity O(n 2 ) that determines the sequence of coefficients b 0 , b 1 , . . . , b dn of the unique reduced polynomial Q(x) that induces the inverse permutation to P (x) on Z 2 n .

Binary permutation polynomials

There is a simple characterization of binary permutation polynomials in terms of the coefficients of the polynomial. Namely, a polynomial

P (x) = a 0 + • • • + a m x m ∈ Z[x]
induces a permutation on Z 2 n if and only if (i) a 1 is odd, (ii) the sum a 3 + a 5 + a 7 . . . is even, and (iii) the sum a 2 + a 4 + a 6 + . . . is even. The criterion is stated and proved in this form by Rivest [START_REF] Rivest | Permutation polynomials modulo 2 w[END_REF], but he points out that it also follows easily from the following more general criterion: P (x) induces a permutation on Z p n , where p is a prime and n ≥ 2, if and only if (i) P (x) induces a permutation on Z p and (ii) P (a) ≡ 0 (mod p) for a ∈ Z. The last criterion is stated in the work of Mullen and Stevens [START_REF] Mullen | Polynomial functions (mod m)[END_REF], who consider it a direct corollary of Theorem 123. in the book by Hardy and Wright [START_REF] Hardy | An introduction to the theory of numbers[END_REF].

The following corollary is crucial for our purposes.

Corollary 1. Let P (x) = a 0 + • • • + a m x m ∈ Z[x] induce a permutation on Z 2 n . For all a, b ∈ R, with a = b, the Newton quotient k a,b = P (a)-P (b) a-b is an odd integer. Proof. Indeed, k a,b = a 1 A 1 + a 2 A 2 + • • • + a m A m , where A 1 = 1 and, for i = 2, 3, . . . , m, A i = a i-1 + a i-2 b + • • • + ab i-2 + b i-1 . If both a and b are even then, modulo 2, k a,b ≡ a 1 , if they have different parity then k a,b ≡ a 1 + a 2 + • • • + a m ,
and if they are both odd, k a,b ≡ a 1 + a 3 + a 5 + . . . . Thus, k a,b is always odd.

Solving the associated linear system

Fix n, and to simplify notation, set d = d n .

For i = 0, . . . , d, set x i = P (i) and y i = Q(x i ) = i. We need to solve, over Z 2 n , the linear system of equations

V [x 0 , x 1 , . . . , x d ](b 0 , b 1 , . . . , b d ) T = (y 0 , y 1 , . . . , y d ) T , where V = V [x 0 , x 1 , . . . , x d ] = [v i,j ] (d+1)×(d+1)
is the (d + 1) × (d + 1) Vandermonde matrix in which v i,j = x j i . We will use the following two results by Oruç and Phillips.

Theorem 2 (Oruç-Phillips 2000 [START_REF] Oruç | Explicit factorization of the Vandermonde matrix[END_REF]). Let x 0 , x 1 , . . . , x m be distinct. An explicit LDU decomposition of the Vandermonde matrix V = V [x 0 , x 1 , . . . , x m ] is given by V = LDU , where D is the diagonal matrix

Diag(1, x 1 -x 0 , (x 2 -x 1 )(x 2 -x 0 ), . . . , (x m -x m-1 )(x m -x m-2 ) . . . (x m -x 0 )), L is the lower triangular matrix L = [ i,j ] given by i,j = j-1 t=0 x i -x j-1-t x j -x j-1-t , 0 ≤ j ≤ i ≤ m,
and U is the upper triangular matrix U = [u i,j ] given by

u i,j = τ j-i (x 0 , . . . , x i ) 0 ≤ i ≤ j ≤ m,
with the understanding that empty products are equal to 1 (thus all diagonal entries in both L and U are equal to 1), and τ r (x 0 , . . . , x i ) is the complete symmetric function evaluated at x 0 , . . . , x i , that is,

τ r (x 0 , . . . , x i ) = λ0+λ1+•••+λi=r x λ0 0 x λ1 1 . . . x λi i .
Example 1. For m = 4, we have

L =            1 0 0 0 0 1 1 0 0 0 1 x2-x0 x1-x0 1 0 0 1 x3-x0 x1-x0 (x3-x1)(x3-x0) (x2-x1)(x2-x0) 1 0 1 x4-x0 x1-x0 (x4-x1)(x4-x0) (x2-x1)(x2-x0) (x4-x2)(x4-x1)(x4-x0) (x3-x2)(x3-x1)(x3-x0) 1            U =       1 x 0 x 2 0 x 3 0 x 4 0 0 1 x 0 + x 1 x 2 0 + x 0 x 1 + x 2 1 x 3 0 + x 2 0 x 1 + x 0 x 2 1 + x 3 1 0 0 1 x 0 + x 1 + x 2 x 2 0 + x 0 x 1 + x 2 1 + x 0 x 2 + x 1 x 2 + x 2 2 0 0 0 1 x 0 + x 1 + x 2 + x 3 0 0 0 0 1      
The entries of U can be obtained recursively, by u 0,j = x j 0 , u i,i = 1, and

u i,j = u i-1,j-1 + u i,j-1 • x i , for 1 ≤ i < j. (1)
Theorem 3 (Oruç-Phillips 2000 [START_REF] Oruç | Explicit factorization of the Vandermonde matrix[END_REF]). Let x 0 , x 1 , . . . , x m be distinct. The matrix L from the explicit LDU decomposition of the Vandermonde matrix V = V [x 0 , x 1 , . . . , x m ] given in Theorem 2 decomposes as the product

L = L (1) L (2) . . . L (m)
of subdiagonal (m + 1) × (m + 1) matrices

L (k) = [ (k) i,j
] with 1s on the diagonal and the subdiagonal entries given, for j = 0, . . . , m -1, by

(k) j+1,j =        0, 0 ≤ j < m -k, j-(m-k)-1 t=0 x j+1 -x j-t x j -x j-1-t , m -k ≤ j ≤ m.
Example 2. For m = 4, the following table provides the subdiagonal entries:

j (1) j+1,j (2) j+1,j
(3) j+1,j

(4) j+1,j 0 0 0 0 1 1 0 0 1 x2-x1 x1-x0 2 0 1 x3-x2 x2-x1 (x3-x2)(x3-x1) (x2-x1)(x2-x0) 3 1 x4-x3 x3-x2 (x4-x3)(x4-x2) (x3-x2)(x3-x1) (x4-x3)(x4-x2)(x4-x1) (x3-x2)(x3-x1)(x3-x0)
The subdiagonal entries can be calculated recursively as follows. For fixed j and k = m -j, we have (k) j+1,j = 1, and for k > m -j + 1,

(k) j+1,j = (k-1) j+1,j • x j+1 -x m-k+1 x j -x m-k . ( 2
)
Going back to our situation, we see that the entries of U and D are integers and, as such, are well defined over Z 2 n . The entries of L and L (k) are not necessarily integers, but they are still well defined over Z 2 n .

≤ j ≤ i ≤ d, i,j = j-1 t=0 x i -x j-1-t x j -x j-1-t = j-1 t=0 P (y i ) -P (y j-1-t ) P (y j ) -P (y j-1-t ) = j-1 t=0 (y i -y j-1-t )k i,j-1-t (y j -y j-1-t )k j,j-1-t = j-1 t=0 (i -j + 1 + t)k i,j-1-t (1 + t)k j,j-1-t = i j j-1 t=0 k i,j-1-t k j,j-1-t ,
where each k * , * is an odd integer.

(b) Let d -k ≤ j ≤ d and set s = j -(d -k) -1. By Corollary 1, we have, (k) j+1,j = s t=0
x j+1 -x j-t

x j -x j-1-t = s t=0 P (y j+1 ) -P (y j-t ) P (y j ) -P (y j-1-t ) = s t=0 (y j+1 -y j-t )k j+1,j-t (y j -y j-1-t )k j,j-1-t = s t=0 (1 + t)k j+1,j-t (1 + t)k j,j-1-t = s t=0 k j+1,j-t k j,j-1-t ,
where each k * , * is an odd integer.

We are ready to prove the main result.

Proof (Proof of Theorem 1). Recall that, in our situation, m = d = d n < n + log 2 n and we are solving the system LDU b = y. The recursive formulas (1) and [START_REF] Biondi | Effectiveness of synthesis in concolic deobfuscation[END_REF] show that the entries of U and the subdiagonal entries in all L (k) , k = 1, . . . , d, can be calculated in O(n 2 ) steps. The diagonal entries of D can also be calculated recursively in O(n 2 ) steps. The inverse of L (k) is obtained by simply changing the sign in all subdiagonal entries. Therefore, we can calculate

y = L -1 y = L (m) -1 L (m-1) -1 . . . L (1) -1 y in O(n 2 ) steps.
We then solve the system DU b = y by backward substitution in O(n 2 ) steps. Note that the i-entry of D has the form 2 ti f i , where f i is odd. Because of our constraints on the coefficients of reduced polynomials, we are seeking only for solutions for b i in the range 0 ≤ b i < 2 n-ti , and a solution exists and is unique in this range. More precisely, once b i+1 , . . . , b d are substituted in, we need to solve for b i from an equation of the form 2 ti f i b i = g i (mod 2 n ), for some odd f i and some g i ∈ Z 2 n . We already know that a solution exists, so it must be that g i = 2 ti g i for some g i ∈ Z 2 n . After canceling the term 2 ti we solve for b i from f i b i = g i (mod 2 n-ti ) by inverting f i , and thus produce the unique solution in the range 0 ≤ b i < 2 n-ti .

Another solution

If we are not interested in producing the coefficients of the inverse polynomial Q(x), but rather just in calculating the values of Q(x) at various points, a slightly different algorithm exists and we outline it here.

Let U n be the ring of units of the ring Z 2 n . Without loss of generality we may assume that P (x) separately permutes U n , the odds, and its complement, the evens (if it does not, we may replace P (x) by P (x) + 1).

The ideal I of integer polynomials that induce the zero function on U n is described in [START_REF] Markovski | Polynomial functions on the units of Z2n[END_REF]. It is generated by P i (x) = 2 n-i-ti i-1 j=0 (x -(2j + 1)), for i = 0, 1, . . . , d n , and

P d n +1 (x) = d n j=0 (x -(2j + 1))
, where d n is the largest integer i such that n -i -t i > 0. Every integer polynomial that permutes U n has a unique representative modulo I , which is a polynomial of degree at most d n with the i-coefficient in the range from 0 to 2 n-i-ti -1. The maximum degree d n is approximately half of d n . We may calculate, by using the same approach as above (the Vandermonde matrix will have dimension (d n + 1) × (d n + 1) and the interpolation is preformed for x i = P (2i + 1), i = 0, . . . , d n ) the coefficients of the unique reduced polynomial Q(x) modulo I that inverts the values of P (x) on U n (and not necessarily on its complement).

By a similar approach, the coefficients of another polynomial, Q(x), of degree at most d n that inverts the values of P (x) on the complement of U n may be calculated. The two polynomials Q(x) and Q(x) may then be used to calculate the values of Q(x) (use the former for odd x and the latter for even). Since the degrees of Q(x) and Q(x) are, in general, smaller than the degree of Q(x), this approach may be faster if we need to calculate many values of Q(x).

3 Interpolation of the inverse polynomial over Z p n Fix a prime p and n > 1.

We claim that the same inversion technique works equally well for permutation polynomials over the ring Z p n .

The ideal of integer polynomials that induce the zero function on Z p n is generated by the polynomials

P i (x) = p n-tp,i i-1 j=0 (x -j) for i = 0, 1, . . . , d p,n , and P dp,n+1 (x) = dp,n j=0 (x -j).
where, for i ≥ 0, t p,i is the largest integer such that p divides !, and d p,n is the the largest integer i such that n -t p,i > 0. Each integer polynomial is equivalent, as a function over Z p n , to a unique reduced polynomial, that is, polynomial b 0 + b 1 x + • • • + b dp,n x dp,n of degree at most d p,n , such that, for i = 0, . . . , d p,n , we have 0 ≤ b i < p n-tp,i (see [START_REF] Mullen | Polynomial functions (mod m)[END_REF]Theorem 2.1]).

We prove an analog of Corollary 1. is an integer that is not divisible by p.

Proof. Since P (x) induces a permutation on Z p n , it induces a permutation on Z p and P (a) ≡ 0 (mod p), for all a.

We work modulo p. The rest of the proof is exactly the same as in the binary case, except, of course, that the analog of Proposition 1 should state that, in their simplest form, all denominators of the entries in L are integers not divisible by p, and all numerators and denominators of the entries in L (k) , k = 1, . . . , d p,n , are integers not divisible by p. Thus, L and L (k) are well defined over Z p n .

Thus we may state a more general version of our main result.

Theorem 4. Let p be a prime and P (x) ∈ Z[x] a polynomial that induces a permutation on Z p n , given by its sequence of values P (a), P (a+1), . . . , P (a+d p,n ) in Z p n for some a ∈ Z p n (not necessarily 0). There exists an algorithm of time complexity O(n 2 ) that determines the sequence of coefficients b 0 , b 1 , . . . , b dp,n of the unique reduced polynomial Q(x) that induces the inverse permutation to P (x) on Z p n .

Proposition 1 .

 1 Let P (x) ∈ Z[x] induce a permutation on Z 2 n . (a) Each entry of L is has odd denominator in its simplest form. (b) Each entry of L (k) , for k = 1, . . . , d has odd numerator and odd denominator in its simplest form. Proof. (a) By Corollary 1, we have, for 0

Proposition 2 .

 2 Let P (x) = a 0 + • • • + a m x m ∈ Z[x]induce a permutation on Z p n . For all a, b ∈ Z, with a = b, the Newton quotient k a,b = P (a)-P (b) a-b

  Let a = b and, moreover, a-b ≡ 0. If we assume k a,b ≡ 0, then P (a)-P (b) ≡ (a -b)k a,b ≡ 0, a contradiction, since P (x) permutes Z p .Let a = b, but a ≡ b. Then, for i ≥ 2, we haveA i = a i-1 + a i-2 b + • • • + ab i-2 + b i-1 ≡ ia i-1 and k a,b ≡ a 1 + 2a 2 a + • • • + ma m a m-1 ≡ P (a) ≡ 0.


Afef Kacem Echi
email: afef.ensit@rnu.tn

Abdel Belaïd
email: abdel.belaid@loria.fr

Impact of Features and Classifiers Combinations on the Performances of Arabic Recognition Systems

Arabic recognition is a very challenging task that begins to draw the attention of the OCR community. This work presents our latest contributions to this task, exploring the impact of several features and classifiers combinations on the performances of some developed systems. Different types of writings were considered (machine-printed, multi-fonts, handwritten, unconstrained, multi-writers, bi-dimensional, large vocabulary, ancient manuscripts). For each type of writing, we have considered both the most appropriate features and classifiers: contextual primitives to compensate the Arabic morphology variation, statistical features to recognize mathematical symbols and spectral features, mainly run lengths histogram-based features and histogram of oriented gradient-based descriptors to discriminate between machine-printed/handwritten and Arabic/Latin words. We have also used the shape context descriptor, for touching characters segmentation, which has been useful to train the models in the template-based recognition system. We have taken advantage of the Hough generalized transform to spot separator words in ancien arabic manuscripts. Otherwise Bayesian networks are used to apprehend the writing uncertainty and transparent neural networks to exploit the morphological aspect of Arabic language and integrate linguistic knowledge in the recognition process. The proposed systems are designed based on the characteristics, the similarities and the differences of Arabic writings.

I. INTRODUCTION

The automatic script recognition for Latin and others languages has been extensively investigated. In contrast, written Arabic recognition only has been researched in recent years and research has been growing very slowly. This slow growth is mainly due to the lack of standardized database and to the inherent difficulties in written Arabic recognition. Nowadays, commercial OCRs integrate this language into their possibilities and we find ICR for Arabic as efficient as for Latin. The challenge remains, however, for large vocabulary, mathematical formulas, unconstraint documents and ancient Arabs, where the calligraphic aspect is more intense and complex to deal with, offering challenges for decades.

Typically, the recognition systems can be divided into three main steps: 1) preprocessing step which aims to improve the text image by enhancing contrast and removing noise, 2) feature extraction and selection step which describe the input image so that features of interest are highlighted, and 3) classification and recognition step which assign a label to a word based on the information provided by its description. This paper focuses on feature extraction and classification steps and their impact on the performances of Arabic recognition systems. Note that the performance of a classifier can rely as much on the quality of the features as on the classifier itself. A good set of features should represent characteristics that are particular for one class and be as invariant as possible to changes within this class. A feature set made to feed a classifier can be a mixture of different types of features. This paper attempts to understand the difference in performance of various features and classifiers when applied to different recognition problems. Different types of writings were considered (machine-printed, multi-fonts, handwritten, unconstrained, multi-writers, bi-dimensional, large vocabulary, ancient manuscripts) and many features and classifiers are tested and used in different contexts. This should give researchers the chance to gain more insight into the natures of the problems and, thus, be better able to do classifier-problem matching.

This paper is organized as follows. In section II, we discuss different types of features used in the proposed recognition systems. Different models, trained and tested, are provided with illustrations in the remaining sections: 1) Transparent Neural Network-based system to recognize a large vocabulary of Arabic words, 2) Probabilistic Graphical Model-based system to handle with non-linear distortions in the Arabic handwriting, 3) Template-based system to extract and segment touching components in Arabic manuscripts and 4) a rulebased system to recognize Arabic mathematical formulas. In each section, we report and analyze the performances of the proposed systems. We finally give some conclusions.

II. FEATURE EXTRACTION

Different feature extraction methods can be divided into two categories structural and statistical.

A. Structural Features

There is a close interrelation among various parts of the word. Such interrelation representing the structural properties must be taken into account to achieve the best recognition performance. Additionally to the fact that structural features serve to better describe the topological and geometrical characteristics of words, we believe that words can be represented by this type of features with high tolerance to distortions and style variations. However, their extraction is not easy as it requires a lot of precaution considering the cursive aspect of the Arabic script.

For handwritten Arabic word recognition [START_REF] Khémiri | Arabic Handwritten Words Off-line Recognition based on HMMs and DBNs[END_REF] and large vocabulary recognition [START_REF] Kacem Echi | Collaborative combination of neuron-linguistic classifiers for large Arabic word vocabulary recognition[END_REF], we extracted some structural features, mainly ascenders, descenders, loops and dots and their positions relative to the baseline. As handwritten words are not usually written on a single baseline, we extracted a sequence of sub-baselines and formed the entire word baseline by juxtaposition of its PAW baselines. Some heuristics are employed for such local extractions. For example, if the PAW consists of ascending letter like the Alif, its baseline corresponds to the bottom of its bounding box. Thus, the word baseline is estimated to mainly cope with the problems of inclination and overlap. More details are given in [START_REF] Khémiri | Arabic Handwritten Words Off-line Recognition based on HMMs and DBNs[END_REF]. In Fig. 1, we report some comparisons between some existing methods and the one we proposed. To provide for the greatest number of opportunities to find such features, the effective word central band is estimated based on the extracted baseline (see Fig. 2).

B. Statistical Features

Statistical features are derived from the statistical distributions of pixels. In [START_REF] Khazri Ayeb | A Syntax Directed System for the Recognition of Printed Arabic Mathematical Formulas[END_REF], we used Hu and Zernike moments, run-length histograms, bi-level co-occurrence and white pixel portion to recognize mathematical symbols. In general, statistical features are easy to extract. Such features may not have physical meaning. But, they are usually effective and computable. Nevertheless, they may be misleading due of noise.

For machine-printed/handwritten and Arabic/Latin word discrimination, we computed black run lengths (BRL) [START_REF] Kacem | A Texture-based Approach for Word Script and Nature Identification[END_REF], histogram of oriented gradients (HOG), pyramid HOG [START_REF] Saïdani | Co-occurrence Matrix of Oriented Gradients for Word Script and Nature Identification[END_REF] (PHOG) and cooccurrence matrices of oriented gradients (Co-MOG) [START_REF] Saïdani | Co-occurrence Matrix of Oriented Gradients for Word Script and Nature Identification[END_REF]. The idea is to exploit the writing orientation as a discriminative descriptor between Arabic and Latin scripts. In fact, letters in Arabic words, as written from right to left, are generally tilted to the left, following the writing direction (see Fig. 3(a)). In contrast, letters in Latin script, as written from left to right, tend to be inclined to the right (see Fig. 3(b)). Thus, Arabic letter strokes are generally diagonally down whereas those written in Latin are diagonally up. Furthermore, machine-printed Arabic words are characterized by the use of horizontal ligatures, more or less long depended on the used font (see Fig. 3(c)). Oppositely, machine-printed Latin words are composed by successive letters without any ligature between them (see Fig. 3(d)). Consequently, horizontal strokes would be more frequent in Arabic words than in Latin words. Both scripts use vertical strokes for ascenders. In [START_REF] Kacem | A Texture-based Approach for Word Script and Nature Identification[END_REF], a BRL vector P is defined as follows. Each element P (i) represents the number of runs with black pixels and length of run equal to i in a given direction. The BRL vector's size is M which corresponds to the maximum run length in words. An orientation is defined using a displacement vector d(x, y), where x and y are the displacements for the x-axis and y-axis respectively. The typical orientations are horizontal, right diagonal, vertical and left diagonal, then calculating the run-length encoding for each direction will produce four BRL vectors. The four obtained BRL vectors are then concatenated into a single vector characterizing the word and implicitly its script.Various texture features are then derived from BRL vectors which measure the distribution of short and long runs, the similarities of gray level values and of the length of runs through out the word's image and the homogeneity and the distribution of runs of the word's image in a specific direction. These features aim to capture the coarseness of a texture in specified directions [START_REF] Galloway | Texture analysis using gray level run lengths[END_REF]. We tested with different classifiers and we find that 1-NN achieves the best accuracy: 99%.

In [START_REF] Saïdani | Co-occurrence Matrix of Oriented Gradients for Word Script and Nature Identification[END_REF], we made use of HOG-based features. Being based on shape descriptors, HOG has interesting properties for script characterization. It is a histogram which counts the gradient orientation at pixels in a given image. The number of features depends on the number of cells and orientation.

While HOG counts occurrences of gradient orientation in localized portions of an image, Pyramid HOG captures perceptually salient features taking into account the spatial property the local shape while representing an image by HOG. The spatial information is represented by tiling the image into regions at multiple resolutions based on spatial pyramid matching (see Fig. 4). Table I according to the cell number using different classifiers. Table II shows the effects of orientation bins number on the accuracy using PHOG. We considered 24000 word images from public databases: IAM database for Latin handwritten, IFN-ENIT and AHTID/MW for Arabic handwritten and APTI for Arabic and Latin printed words. In [START_REF] Saïdani | Co-occurrence Matrix of Oriented Gradients for Word Script and Nature Identification[END_REF], we took advantage of Co-MOG to express the distribution of gradient information over an image. These feature captures more spatial information than PHOG by counting the frequency of co-occurrences of oriented gradients between pairs of pixels. A total of 324 features are extracted from each word image. Genetic algorithm is applied for reducing the dimensionality of the features vectors to 248. We used SVM, k-NN and AODEsr classfiers and we respectively achieved 96.43%, 99.85% and 99.71% as identification rates. Overall, features extracted from BRL seem quite valuable for word level script identification. Features from HOG descriptors are characterized with high robustness against intra-class variability and fast enough for real time classification. In addition, they are scale invariant which means that words can be classified without any need for size normalization. They do not require word segmentation. Although Co-MOG features only include angular orientation of gradient and co-occurrence of angular orientation of gradient, they achieve the best performance in all script identification experiments.

displays HOG results

The main drawback with the statistical feature extraction is that it is difficult to take contextual dependence into consideration. In [START_REF] Aouadi | A proposal for touching component segmentation in Arabic manuscripts[END_REF], we investigated the use of the shape context descriptor for touching characters (TC) segmentation. The idea is to find the most similar model, among those stored in a code book with their prior known segmented parts, for the TC to be segmented using a similarity metric computed from the shape context descriptor. Finding correspondences between a model and a TC consists on searching for each point p i of TC's contour, the best matching point q j on the model's contour by comparing their edge point's shape context histogram, as illustrated in Fig. 5. Fig. 5. Matching with SC: (a) SC of p in T C 1 ,(b) log-polar histogram for p (c) SC of q in T C 2 , (d) log-polar histogram for q which is similar to that in (b), but different of p ′ in (f). The best matching is between p in T C 1 and q in T C 2 . Black bins correspond to a higher number of pixels in that bin, gray bins contains fewer pixels than the black cells. Log-polar histogram similarity is according to the χ 2 distance.

In [START_REF] Aouadi | Word Spotting for Arabic Handwritten Historical Document Retrieval using Generalized Hough Transform[END_REF], we used the Generalized Hough Transform to spot separator words in ancien Arabic manuscripts. This technique provides features invariants to global deformation and seems to be tolerant of gaps in feature descriptions and relatively unaffected by image noise.

III. RECOGNITION SYSTEMS

The proposed recognition systems are based on templatematching, probabilistic graphical models and Transparent neural networks.

A. Template-based Recognition System

For templates without strong features, or when the bulk of the template image constitutes the matching image, a templatebased approach may be effective. In [START_REF] Aouadi | A proposal for touching component segmentation in Arabic manuscripts[END_REF], we proposed a template-based recognition system to address the problem of TC extraction and separation in Arabic manuscripts. The proposed system first extracts the TCs in the document whether between successive text-lines or words of the same text-line. For vertically/up-down TCs, we improved an existing method, that of Ouwayed and Belaïd [START_REF] Ouwayed | Segmentation en lignes de documents an-ciens: application aux documents arabes[END_REF]. For horizontally/left-right TCs, we proposed a novel extraction method based on the morphology analysis of the terminal letters of Arabic words. To evaluate the vertically inter-connected TC extraction, we used 500 TCs and we achieved an extraction rate of 94%. For horizontally inter-connected TCs, we used 600 TCs and achieved an extraction rate of 94.2%. We then recognized the TCs relying on templates, using shape context descriptor and an interpolation function the Thin Plate Spline transformation (see Fig. 6). Note that the shape context descriptor has the advantage to summarize a global shape in a rich and local descriptor. It greatly simplifies recovery of correspondences between points of two given shapes and it is tolerant to all common shape deformations. We finally segmented the TCs based on the distance from the central points of the recognized template's parts. Tests are performed using a large dataset of TCs and three metrics: Manhattan, Euclidean and Canberra distances and we respectively achieved 94%, 92.6% and 92% as segmentation rates. For the TC segmentation evaluation, we used 3000 TCs (670 horizontally inter-connected TCs and 2330 vertically inter-connected TCs). We achieved a segmentation rate of 94%. Obtained results strongly support the efficiency of the proposed TC extraction and segmentation methods and outperform results of some related works, taking into account the different types, variability and complexity of the TCs.

B. Transparent Neural Network-based Recognition System

Most of the actual research in writing recognition focuses on specific applications where the vocabulary is relatively small. Many applications can be opened up when handling with large vocabulary. In [START_REF] Kacem Echi | Collaborative combination of neuron-linguistic classifiers for large Arabic word vocabulary recognition[END_REF], we proposed a collaborative combination of Neuron-Linguistic classifiers for large Arabic word vocabulary recognition. The proposed approach is based on three networks, which exploit the morphological aspect of the Arabic word and collaborate for a better word recognition. We focused on decomposable words which are derived from healthy tri-consonantal roots and easy to proof the decomposition. To perform word recognition, the system extracts a set of global structural features. Then, it learns and recognizes roots, schemes and conjugation elements that compose the word. To help the recognition, some local perceptual information is used in case of ambiguities. This interaction between global recognition and local checking makes easier the recognition of complex scripts as Arabic (see Fig. 7). Several experiments have been performed using a vocabulary of 5757 words, organized in a corpus of more than 17271 samples. We achieved a recognition rate of 95.33%.

C. Probabilistic Graphical Model-based Recognition System

We explored a better understanding of the relative performance of probabilistic graphical models, known by their power in several recognition problems that require reasoning under uncertainty, for recognizing handwritten Arabic words. The objective was to exploit the Arabic writing process and the ability of these models to handle with nonlinear distortions of the Arabic script and uncertainly of human writing. In [START_REF] Khemiri | A System for off-line Arabic Handwritten Word Recognition based on Bayesian Approach[END_REF] we firstly proposed a Naïve Bayes (NB) which represents the word with a set of random variables and where the probability distribution is factorized on the variables by the product of elementary probabilities of the variable knowing the causes. For that, we extracted 102 structural features and composed 83 classes from the IFN-ENIT database.

With NB, we can look up all the probabilities with a single scan of the database and store them in a small table. Thus, NB is fast to train and to classify. It is not sensitive to irrelevant features. But, one of NB problems is its assumption of features independence. As solutions to alleviate the conditional independence assumption are to extend the structure of NB by considering the relationships between features as proposed in TAN. With NB and TAN, we respectively achieved 78.57% and 81.64% using 83 classes and 7888 samples from the IFN/ENIT database. However, if static BN handles well the multi-dimensionality, it does not handle the temporal aspect. So, we used the DBN which can be seen as a repetition of static BNs called time slices. Transitions between time slices and observations are inside each slice. For that, we proposed to model words by coupling two HMM architectures into a single DBN, each one is for one direction: horizontal and vertical. We added direct links between hidden state nodes to represent dependencies between state variables of both vertical and horizontal HMMs and used two streams for word observations. In a first proposed DBN1 (see Fig. 8(a)), a state of a HMM is connected to the adjacent state in the same time slice t of the other HMM. To enhance the influence of the vertical stream, the edges are directed from the vertical stream to the horizontal one. Experimentally, it has been proved that V-HMM is more reliable than H-HMM, when tested separately. In a second proposed DBN2 (see Fig. 8(b)), we considered diagonal links, instead of vertical ones. Thus, a state of a HMM is connected to the adjacent state in the next time slice of the other HMM. We finally proposed a third DBN3 where both vertical and diagonal dependencies are involved (see Fig. 8(c)), in the attempt to consider all possible correlations between parts of word. We respectively achieved 90.02%, 84.10% and 86.07% recognition rates for DBN1, DBN2 and DBN3 on the same database. An explanation for this may be as follows. The dependencies between current states of the V-HMM and H-HMM in DBN1, seem to be relevant as they reflect the Arabic writing process: top-to-bottom and right-toleft and lead to the best rate: 90.02%. In DBN2, the cross dependencies, instead of vertical ones, lowered the rate to 84.10% due to their redundancy, since they did not express any additional feature in Arabic writing. When considering both vertical and cross-dependencies in DBN3, the rate was improved a little bit: 86.07%, probably thanks to relevance of vertical dependencies, but it remains lower than DBN1 recognition rate.

IV. RULE-BASED RECOGNITION SYSTEM

In [START_REF] Khazri Ayeb | A Syntax Directed System for the Recognition of Printed Arabic Mathematical Formulas[END_REF], we addressed the problem of Arabic mathematical formula recognition. For the formula structure analysis, we proceeded by top-down and bottom-up parsing scheme based on operator dominance. A set of replacement rules is defined by a coordinate grammar based on symbol recognition and symbol arrangement analysis results. In the proposed system, the recognition and parsing modules interact more closely. Thus, we can use the context information collected during structural analysis to help us guess about the symbols, overcoming our incorrect assumption of perfect symbol recognition. The syntax-directed recognition system, described here, has been successfully demonstrated in many types of formulas and achieved satisfactory results. 91% of formulas are correctly recognized.

V. CONCLUSION

We presented research results on off-line Arabic recognition using structural and statistical approaches for the specific tasks of large vocabulary recognition, handwriting recognition, script identification, touching characters segmentation and mathematical formulas recognition. The differences between statistical and structural approaches can be summarized as follows. In the statistical approach, the word is described in a quantitative manner, whereas the structural approach generates a description composed of primitives. The statistical approach discriminates via numeric differences among features from different classes, while grammars are used by the structural approach to define a language which includes the acceptable configurations of primitives for each class. Structural features can be used with either a statistical or structural classifier. Statistical features cannot be used with a structural classifier because they miss relational information, however statistical information can be associated with structural primitives and used to resolve ambiguities, as when parsing with attributed or stochastic grammars. Having divergent theoretical foundations, the two approaches focus on different data characteristics and employ distinctive techniques for the word representation and classification.

Fig. 1 .

 1 Fig. 1. (a) Words, (b) Extracted baseline by our method, (c) Baseline extracted by contour method, (d) Baseline extracted by horizontal projection.

Fig. 2 .

 2 Fig. 2. Upper, central and lower band extraction based on baseline.

Fig. 3 .

 3 Fig. 3. Machine-printed/Handwritten and Arabic/Latin word identification based on the writing orientation.

Fig. 4 .

 4 Fig. 4. A schematic illustration of PHOG at each resolution level.

Fig. 6 .

 6 Fig. 6. (a) Matching between a TC and its most similar model, (b) The pointto-point matching, (c) Matching based on region, (d) Illustration of regionto-region matching.

Fig. 7 .

 7 Fig. 7. TNN Propagation.

Fig. 8 .

 8 Fig. 8. DBN's architectures, from [2]: (a) DBN1, (b) DBN2 and (c) DBN3.

TABLE I SCRIPT

 I IDENTIFICATION ACCURACY USING HOG.

	Cell Number	8
	Features Number (selected)	64 (38)
	SVM Accuracy	80.56%
	k-NN Accuracy	82.87%
	AODEsr Accuracy	93.47%

TABLE II SCRIPT

 II IDENTIFICATION ACCURACY USING PHOG.

	Orientation Bin Number	8
	Features Number (selected)	680 (268)
	Accuracy(%)	97.49


Wei Zhan
email: wzhan@berkeley.edu

Arnaud De

La Fortelle

Yi-Ting Chen
email: ychen@honda-ri.com

Ching-Yao Chan

Masayoshi Tomizuka
email: tomizuka@berkeley.edu

Probabilistic Prediction from Planning Perspective: Problem Formulation, Representation Simplification and Evaluation Metric

Accurate probabilistic prediction for intention and motion of road users is a key prerequisite to achieve safe and high-quality decision-making and motion planning for autonomous driving. Typically, the performance of probabilistic predictions was only evaluated by learning metrics for approximation to the motion distribution in the dataset. However, as a module supporting decision and planning, probabilistic prediction should also be evaluated from decision and planning perspective. Moreover, the evaluation of probabilistic prediction highly relies on the problem formulation variation and motion representation simplification, which lacks a summary in a comprehensive framework. To address such concerns, we provide a systematic and unified framework for the analysis of three under-explored aspects of probabilistic prediction: problem formulation, representation simplification and evaluation metric. More importantly, we address the omitted but crucial problems in the three aspects from decision and planning perspective. In addition to a review of learning metrics, metrics to be considered from planning perspective are highlighted, such as planning consequence of inaccurate and erroneous prediction, as well as violations of predicted motions to planning constraints. We address practical formulation variations of prediction problems, such as decision-maker view and blind view for viewpoint, as well as reactive prediction for interaction, so that decision and planning can be facilitated.

I. INTRODUCTION

The behavior of traffic participants is full of uncertainties in the real world. Autonomous vehicles need to well estimate such uncertainties to increase driving quality (time-efficiency, comfort, etc.) and safety level for the decision-making and motion planning. To drive safely, autonomous vehicles should predict possible intentions and motions of other road participants, and avoid collisions accordingly. To enhance driving quality, autonomous vehicles should take threats of high probability seriously, yet not overreact to threats of low probability. Therefore, probabilistic intention and motion predictions are inevitable for safe and high-quality decisionmaking and motion planning for autonomous vehicles.

A typical structure of probabilistic prediction is shown in Figure 1. Most of the research efforts on probabilistic prediction [START_REF] Lefèvre | A survey on motion prediction and risk assessment for intelligent vehicles[END_REF] were focused on prediction algorithm design CA 94804 (e-mail: cychan@berkeley.edu). Observations are generated via feature extraction of historical motions in the dataset combined with maps from prior knowledge. Prediction algorithm provides predicted distribution according to the observation input by incorporating prior knowledge such as traffic rules, vehicle models and maps. Since the motion representation in the predicted distribution is often simplified, the representation of the future motions in the dataset should be homogenized so that the ground truth can be used to evaluate the performance of the algorithm by appropriate metrics.

for specific scenarios. Some recent works addressed incorporating prior knowledge to construct prediction frameworks which can deal with a variety of scenarios [START_REF] Schreier | An Integrated Approach to Maneuver-Based Trajectory Prediction and Criticality Assessment in Arbitrary Road Environments[END_REF] [START_REF] Geng | A Scenario-Adaptive Driving Behavior Prediction Approach to Urban Autonomous Driving[END_REF]. Arbitrary solutions for other parts in Figure 1 were typically adopted, which lacks sufficient investigation.

A. Evaluation metric

Evaluation metrics are required to measure the performance of predictions. Distance-based trajectory similarity metrics were investigated and employed in [START_REF] Atev | Clustering of Vehicle Trajectories[END_REF] [START_REF] Hardy | Clustering obstacle predictions to improve contingency planning for autonomous road vehicles in congested environments[END_REF] [6] [START_REF] Damerow | Spatio-temporal trajectory similarity and its application to predicting lack of interaction in traffic situations[END_REF]. Comprehensive reviews on distance-based metrics were provided and novel measures were proposed in [START_REF] Besse | Review and Perspective for Distance-Based Clustering of Vehicle Trajectories[END_REF] [START_REF] Quehl | How good is my prediction? finding a similarity measure for trajectory prediction evaluation[END_REF]. Distancebased metrics are well applicable to evaluate deterministic predictions. However, the evaluation of probabilistic prediction cannot be provided by using distance-based metrics directly. A variety of learning metrics were used to evaluate the performance of probabilistic prediction models on whether the distribution in the dataset is well approximated, such as area under the curve (AUC) [START_REF] Klingelschmitt | Probabilistic, discriminative maneuver estimation in generic traffic scenes using pairwise probability coupling[END_REF], root mean square error (RMSE) [START_REF] Lenz | Deep neural networks for markovian interactive scene prediction in highway scenarios[END_REF], likelihood [START_REF] Phillips | Generalizable intention prediction of human drivers at intersections[END_REF], and Kullback-Leibler (KL) divergence [START_REF] Wheeler | Analysis of microscopic behavior models for probabilistic modeling of driver behavior[END_REF].

The executed motion of a vehicle typically satisfies planning constraints on feasibility (vehicle model) and safety (collision avoidance). However, small perturbations making a trajectory infeasible or unsafe, can hardly make a large difference for learning and distance-based metrics. The afore-mentioned problem has not been sufficiently addressed for evaluation. Moreover, the ultimate goal of the probabilistic prediction model is to support decision-making and planning. Several practical aspects should also be considered from such perspective. The potential consequence of inaccurate predictions to safety and driving quality should be taken into account. It is also a concern for the decision and planning module whether accurate prediction is provided timely with sufficient preview horizon. Neither the learning metrics nor distance-based ones can take into account these aspects.

The performance of probabilistic predictions should be evaluated by appropriate metrics so that it can best approximate the distribution in datasets, while avoid infeasible and unsafe motions in the prediction, and desirably provide indications to the subsequent decision and planning modules. Thus our primary motivation is to provide a summary of learning metrics, and address the crucial but omitted aspects on prediction evaluation from the perspective of decisionmaking and planning, so that novel metrics can be inspired.

B. Representation simplification

Indicators are commonly used to simplify the motion representation to enable the probabilistic description of the predictions since the original space of trajectories can be extremely high with continuous variables. As shown in Figure 1, the representation of future motions should be homogenized so that same indicators are used for comparing the predicted distribution and the ground truth to make the evaluation metric meaningful. Motion patterns such as route [START_REF] Klingelschmitt | Using Context Information and Probabilistic Classification for Making Extended Long-Term Trajectory Predictions[END_REF] and pass-yield [START_REF] Dong | Intention estimation for ramp merging control in autonomous driving[END_REF] patterns, as well as spatiotemporal representations such as prototype trajectory [START_REF] Lawitzky | Interactive scene prediction for automotive applications[END_REF] and reachable set [START_REF] Althoff | Model-Based Probabilistic Collision Detection in Autonomous Driving[END_REF], were used as indicators, which need to be summarized.

Intention is one of the most common indicators for simplification. However, the meaning of "intention" can be twofold, namely, original desire and executed motion pattern. In highly interactive scenarios, an entity may not be able to achieve its original desire due to the motion of others. In fact, the decision and planning module checks the potential collision with others according to their possible motions to execute, but not the original desire. Moreover, the original desire cannot be labeled as the ground truth in datasets. Instead, only the executed motion patterns can be labeled. Therefore, the difference between pattern and desire should be clarified. Thus our second motivation is to summarize methods for motion representation simplification, and to clarify the distinction between motion pattern and desire.

C. Problem formulation

The variation of the assumptions and settings for the input and output of the prediction algorithm can significantly change the forms of the observation and predicted distribution in Figure 1. It is hard to compare algorithms with different problem formulations due to the viewpoint and interaction-involvement of the input, as well as the number of predicted entities and motion representation of the output. Such variation can also completely change the problem complexity, as well as model practicability for decisionmaking and planning of the host vehicle.

For instance, NGSIM dataset [START_REF] Alexiadis | The Next Generation Simulation Program[END_REF] provides bird's-eye view of the dynamic scenes so that the surroundings of a predicted vehicle are fully observable. However, autonomous vehicles in the real traffic can only obtain local view, which means that the surroundings of a predicted vehicle are partially observable with uncertainties. Thus our third motivation is to summarize the variations of input and output for the problem formulation of probabilistic prediction from decision and planning perspective so that the difficult but practically significant problems can be addressed.

The main contributions of this paper can be summarized as follows. First, we address the under-explored but crucial aspects to formulate, simplify and evaluate probabilistic prediction from decision-making and planning perspective. Second, we provide a systematic framework to summarize the assumptions and settings for problem formulation, indicators for motion representation simplification, and metrics for performance evaluation. Third, existing probabilistic prediction works are reviewed from the three highlighted aspects, instead of methodologies and scenarios, in order to inspire novel evaluation metrics.

II. PROBLEM FORMULATION

Suppose x i is an input observation in Figure 1, which contains the extracted features from historical motions in the dataset with map context. ŷi denotes representation of the future motion of the predicted entity in the prediction algorithm corresponding to x i . y i is the ground truth of the future motion from dataset homogenized to the same form of ŷi . X and Y are the corresponding random variables. Then the problem is to design prediction algorithms so that the predicted distribution p(Y |X) can best approximate the distribution in the dataset q(Y |X). Note that typically q(Y |X) can only be obtained or represented by ground truth data points (x i , y i ). There are several variations of the original problem by changing the input and output of the model.

A. Input variation 1: viewpoint

An important variation of the observation input is the viewpoint. The main distinction for different viewpoints lies in occlusions, such as whether the surroundings of the predicted entity is occluded to the prediction module, and whether the predicted entity itself is occluded.

1) Bird's-eye view (host prediction):

The viewpoint is a bird's-eye view when the surroundings of a predicted entity are fully observable. An algorithm designed with such viewpoint is actually predicting the motion of a host vehicle (first-person viewpoint), since only the sensors equipped on the predicted vehicle can fully observe its surroundings. The most representative bird's-eye view vehicle motion dataset is the NGSIM, which was utilized by many recent works on probabilistic prediction [11] [12] [15] [START_REF] Morton | Analysis of Recurrent Neural Networks for Probabilistic Modeling of Driver Behavior[END_REF].

2) Local view (surrounding prediction):

The viewpoint is a local view when the surroundings of a predicted object are partially observable due to occlusions. An algorithm designed with such viewpoint can be used to predict the motion of a surrounding vehicle (third-person viewpoint). Although the data used in many existing works were collected in local view, probabilistic prediction with partial occlusion has not been sufficiently investigated by researchers yet.

3) Blind view (occluded entity prediction): The predicted entity can also be partially or fully occluded by vehicles or buildings, which leads to a blind view. Algorithms designed with such viewpoint can provide prediction for blind corner decision-making [START_REF] Hoermann | Entering crossroads with blind corners. A safe strategy for autonomous vehicles[END_REF] [21] [START_REF] Yoshihara | Autonomous Predictive Driving for Blind Intersections[END_REF] or occluded object tracking [START_REF] Galceran | Augmented vehicle tracking under occlusions for decision-making in autonomous driving[END_REF].

B. Input variation 2: interaction

Another input variation is interaction. The main distinction lies in whether the behavior of the predicted vehicle is influenced by the surrounding entities. Another distinction is whether there is a decision-maker asking "what if my motion is like this in the future".

1) Independent prediction: The "maneuver-based" prediction model was defined in [START_REF] Lefèvre | A survey on motion prediction and risk assessment for intelligent vehicles[END_REF] as the behavior of the predicted vehicle is independent from others. Since the word "maneuver" was used in some literatures for behaviors influenced by others, we use independent prediction to describe the same problem.

2) Interdependent prediction: The "interaction-aware" prediction model was defined in [START_REF] Lefèvre | A survey on motion prediction and risk assessment for intelligent vehicles[END_REF] when the behavior of the predicted entity is influenced by others. In this paper we emphasize whether the behavior is impacted by historical or future motions of the surroundings. When only historical surrounding motions are used as the input, the problem can be defined as interdependent prediction, namely, the motions of the entities are only historically interactive.

3) Reactive prediction: From the host vehicle decisionmaking and planning perspective, the most desirable prediction for a highly interactive scenario is an algorithm that can answer the question "what if my motion is like this in the future". Therefore, we define reactive prediction as the problem to obtain the algorithm whose input can take into account the future motion of a host vehicle or a pattern (simplification) of the motion, and provide the distribution of the predicted entity accordingly.

C. Output variation 1: number of predicted entities

The number of predicted entities as the output can change the formulation of the prediction problem.

1) Single-entity prediction: Most of the recent works are focused on single-entity prediction, where the future behavior of only one entity is provided.

2) Situation prediction: The combinatorial decision and planning [START_REF] Bender | The combinatorial aspect of motion planning: Maneuver variants in structured environments[END_REF] of the host vehicle may strongly depend on the possible behavior of several entities as a group in complicated scenarios. However, it is hard to directly combine the predictions of single entities since the future motions may be exclusive. Instead, situation prediction [START_REF] Klingelschmitt | Probabilistic situation assessment framework for multiple, interacting traffic participants in generic traffic scenes[END_REF] [26] can provide the joint distribution of the motions of surroundings.

D. Output variation 2: motion representation

The original and intuitive representation of predicted motion is to use continuous trajectories. However, due to the high dimension and difficulty in describing distribution for continuous random variables, the motion representation is often simplified in order to describe the probability distribution for complicated scenarios. Detailed discussion on representation simplification is provided in Section III.

III. REPRESENTATION SIMPLIFICATION

As discussed in Section II, the representation of longterm motions is usually simplified by indicators since it is intractable to directly use continuous trajectories to describe the distribution of predicted motions in complicated scenarios. In this section, the most commonly used indicators are categorized as continuous motions, motion patterns or spatiotemporal indicators. We also categorize motion patterns according to the hierarchy from decision and planning perspective. Moreover, the spatiotemporal indicators are discussed based on whether motion patterns are considered.

A. Continuous motions

A sequence of positions and yaw angles [START_REF] Xu | Motion planning under uncertainty for on-road autonomous driving[END_REF], as well as velocities [START_REF] Dong | Intention estimation for ramp merging control in autonomous driving[END_REF] and accelerations [START_REF] Morton | Analysis of Recurrent Neural Networks for Probabilistic Modeling of Driver Behavior[END_REF] [START_REF] Lenz | Deep neural networks for markovian interactive scene prediction in highway scenarios[END_REF] are typically used as the continuous motions. Such representation is relatively more applicable in car following [START_REF] Morton | Analysis of Recurrent Neural Networks for Probabilistic Modeling of Driver Behavior[END_REF] [START_REF] Hoermann | Probabilistic long-term prediction for autonomous vehicles[END_REF] [29] and ramp merging [START_REF] Lenz | Deep neural networks for markovian interactive scene prediction in highway scenarios[END_REF] [15] scenarios, where only longitudinal motions need to be considered. When the preview horizon is relatively long, it is intractable for a model to directly output the distribution of long-term motions. Instead, the models can output the distribution for one step look ahead, then structures such as Bayesian filtering [START_REF] Xu | Motion planning under uncertainty for on-road autonomous driving[END_REF] [28] [START_REF] Tran | Modelling of traffic situations at urban intersections with probabilistic non-parametric regression[END_REF] and long short-term memory (LSTM) [START_REF] Morton | Analysis of Recurrent Neural Networks for Probabilistic Modeling of Driver Behavior[END_REF] can be employed to propagate the motion to the long-term future.

B. Motion patterns with hierarchical categorization

For decision-making and planning of the host vehicle, the destination to reach is the first to be considered. A corresponding route can be planned offline, which is typically independent from the situation encountered in real time. Then the local decision-making and planning module can deal with the specific situation, such as whether to pass a conflict region before or after another entity. Such hierarchical architecture also applies for prediction, namely, the route pattern and pass-yield pattern are hierarchical. One example for such hierarchy is predicting potential right turn with pedestrian yielding at an intersection [START_REF] Liebner | Driver intent inference at urban intersections using the intelligent driver model[END_REF], in which route patterns were turn right and go straight, and the passyield patterns were go and stop for straight, and turn and yield for turn right. Another example is predicting routes and right-of-way at a four-way-stop intersection [START_REF] Wyder | A Bayesian filter for modeling traffic at stop intersections[END_REF]. The route patterns were turn left/right and go straight, and the pass-yield pattern was the right-of-way at intersections.

Moreover, there are also subtle motion patterns which cannot be defined as route or pass-yield patterns, such as slow down, go as expected, accelerate, etc. A comprehensive example for the hierarchy of route, pass-yield and subtle patterns is predicting potential left turn with proceeding and oncoming vehicles at an intersection [START_REF] Klingelschmitt | Probabilistic, discriminative maneuver estimation in generic traffic scenes using pairwise probability coupling[END_REF]. The route patterns were go straight and turn left. The pass-yield patterns were go in front and yield for the oncoming vehicle when turning left. The subtle patterns were free drive and influenced for the proceeding vehicle, and full stop and slow down for yielding oncoming vehicle when turning left.

1) Route pattern: Route pattern (intention) denotes the discrete pattern shaped by the spatial road structure, such as road branches, lanes and parking lots. It depicts which parking lot the entity wants to occupy, or which branch of road it wants to take at nodes such as intersections, roundabouts, exit ramp, etc. Dedicated lanes (left/right turn only) at these nodes are decisive to estimate the intention. Route pattern were estimated for vehicle [START_REF] Phillips | Generalizable intention prediction of human drivers at intersections[END_REF] and cyclists [START_REF] Pool | Using road topology to improve cyclist path prediction[END_REF] with probabilistic models. Also, probabilistic models for route patterns of vehicles at intersections were also proposed along with other motion patterns [START_REF] Liebner | Driver intent inference at urban intersections using the intelligent driver model[END_REF] [10] [14] [START_REF] Wyder | A Bayesian filter for modeling traffic at stop intersections[END_REF]. When all the temporal factors are neglected and only the final target lane to change is considered for performance evaluation [START_REF] Sonka | Dual approach for maneuver classification in vehicle environment data[END_REF] [35], lane change intention can be regarded as route pattern since the final execution is not influenced by surroundings.

2) Pass-yield pattern: Pass-yield pattern depicts which entity occupies the conflict region first when the potential routes of two entities have a overlap (conflict). Similar concept was also used in cooperative driving as homotopy class [START_REF] Grégoire | Priority-based intersection management with kinodynamic constraints[END_REF]. Such pattern was predicted for ramp merging [START_REF] Dong | Intention estimation for ramp merging control in autonomous driving[END_REF], pedestrian yielding [START_REF] Liebner | Driver intent inference at urban intersections using the intelligent driver model[END_REF], oncoming vehicle yielding for left turn [START_REF] Klingelschmitt | Probabilistic, discriminative maneuver estimation in generic traffic scenes using pairwise probability coupling[END_REF], four-way-stop right-of-way [START_REF] Wyder | A Bayesian filter for modeling traffic at stop intersections[END_REF], etc. The patterns such as pass or stop during yellow light, red-light violation or stop [START_REF] Jahangiri | Adopting machine learning methods to predict red-light running violations[END_REF], and stop or violate the stop sign [START_REF] Doerzaph | Live stop-controlled intersection data collection[END_REF] [39] can also be categorized as pass-yield pattern.

3) Subtle pattern: Subtle pattern denotes the motion patterns which cannot be explicitly categorized via spatial road structure or conflict region for two entities. For example, there can be several motion patterns for vehicles near stop signs such as conservative/normal stop and rolling/moderate/severe violation [START_REF] Doerzaph | Live stop-controlled intersection data collection[END_REF], which can be clustered via unsupervised learning. The longitudinal motions of vehicles can be simplified as acceleration, deceleration and expected behavior pattern [START_REF] Klingelschmitt | Probabilistic situation assessment framework for multiple, interacting traffic participants in generic traffic scenes[END_REF]. In [START_REF] Klingelschmitt | Probabilistic, discriminative maneuver estimation in generic traffic scenes using pairwise probability coupling[END_REF], the motion of the predicted vehicle impacted by the proceeding one was simplified as free drive and influenced, and the left-turn motion yielding the oncoming vehicle was simplified as full stop and slow down.

C. Distinctions between pattern and desire

In literatures, terminologies such as "intention", "maneuver" and "behavior" are often used for motion clusters. However, the meaning of motion clusters can be twofold. One is "motion pattern", which clusters the motions executed by the entities, and it can be observed or labeled in the motion data to serve as the ground truth. The other is "motion desire", which is the motivation inside the mind of humans, and it cannot be fully observed or labeled in the motion data. In fact, the desire in the human minds can rapidly change from time to time with the dynamic behavior of surroundings.

In previous works, using the terminologies such as "intention" is ambiguous to express the distinctions between pattern and desire. It is acceptable to mix pattern and desire for route since the final desire of the object related to route is typically not influenced by surroundings so that the desire in the data can be time-invariant. However, for pass-yield and subtle patterns, the corresponding desires may jump from one to another rapidly, and the surroundings may restrict the predicted entity to achieve its desire, especially in highly interactive scenarios. Therefore, the ground truth cannot be labeled for such desires in the data, and only motion patterns can be labeled.

D. Spatiotemporal indicators

Motion patterns can be incorporated in the spatiotemporal domain by two kinds of indicators, namely, prototype trajectory and reachable set. The spatiotemporal domain can also be represented without considering any motion patterns and semantic meaning by using occupancy grid.

1) Prototype trajectory: The terminology "prototype trajectory" was defined in [START_REF] Lefèvre | A survey on motion prediction and risk assessment for intelligent vehicles[END_REF] for one or a set of trajectories which can represent a motion pattern. It was employed in [START_REF] Wyder | A Bayesian filter for modeling traffic at stop intersections[END_REF] [40] [START_REF] Lawitzky | Interactive scene prediction for automotive applications[END_REF] to represent possible motions.

2) Reachable set: Reachable set is a widely used motion representation describing the area which may be occupied by the body of an entity. Stochastic reachable set [START_REF] Althoff | Model-Based Probabilistic Collision Detection in Autonomous Driving[END_REF] can represent the probabilistic prediction and take into account information from motion patterns. It is also more direct to indicate drivable area for the planning module.

3) Occupancy grid: Occupancy grid divides the spatial domain [START_REF] Kim | Probabilistic Vehicle Trajectory Prediction over Occupancy Grid Map via Recurrent Neural Network[END_REF] [START_REF] Gruner | Spatiotemporal representation of driving scenarios and classification using neural networks[END_REF], or other domains of motion variables such as velocity [START_REF] Gruner | Spatiotemporal representation of driving scenarios and classification using neural networks[END_REF] [START_REF] Klingelschmitt | Using Context Information and Probabilistic Classification for Making Extended Long-Term Trajectory Predictions[END_REF], into discrete grids evenly. It can provide a uniform representation of the environment regardless of the number of entities in the scene, which is favorable for learning models such as deep neural networks [START_REF] Kim | Probabilistic Vehicle Trajectory Prediction over Occupancy Grid Map via Recurrent Neural Network[END_REF] [42], and for complex scenarios with a number of entities interacting with each other [START_REF] Hoermann | Dynamic Occupancy Grid Prediction for Urban Autonomous Driving: A Deep Learning Approach with Fully Automatic Labeling[END_REF].

IV. EVALUATION METRICS

In many recent works, probabilistic prediction was regarded as a pure machine learning problem, that is, to find a learning model which can best represent the distribution in the dataset in the sense of some training metrics. However, distribution learned from data alone for prediction is not sufficient to support high-quality and safe decision-making and planning. In this section, the most commonly used learning metrics are summarized. Also, we discuss potential metrics based on prior knowledge on planning constraints, and aspects of metric construction which are crucial for decision-making and planning.

A. Learning metrics

Typical classification and regression metrics are widely used to evaluate the performance of learning models for probabilistic prediction. Despite the most intuitive metric, accuracy, the following metrics are also widely used for evaluation of probabilistic predictions.

1) Receiver operating characteristic (ROC) curve: ROC curve is typically used to illustrate the performance of a binary classifier with different thresholds of discrimination. The area under the curve (AUC) is often used as a quantitive metric. ROC and AUC were employed to evaluate the classification performance of intention estimation, such lane change [START_REF] Bahram | A Combined Model-and Learning-Based Framework for Interaction-Aware Maneuver Prediction[END_REF] [35] and intersection maneuvers [START_REF] Klingelschmitt | Probabilistic, discriminative maneuver estimation in generic traffic scenes using pairwise probability coupling[END_REF] [45] [START_REF] Liebner | Driver intent inference at urban intersections using the intelligent driver model[END_REF], as well as situation prediction [START_REF] Klingelschmitt | Probabilistic situation assessment framework for multiple, interacting traffic participants in generic traffic scenes[END_REF].

2) Root mean square error (RMSE): RMSE is one of the most widely used metric for regression evaluation. Some variations in different literatures evaluate the performance from similar perspective, such as root-weighted square error (RWSE) [START_REF] Morton | Analysis of Recurrent Neural Networks for Probabilistic Modeling of Driver Behavior[END_REF] [11] [START_REF] Wheeler | Analysis of microscopic behavior models for probabilistic modeling of driver behavior[END_REF], mean absolute error (MAE) [START_REF] Bahram | A Combined Model-and Learning-Based Framework for Interaction-Aware Maneuver Prediction[END_REF] [41], Mean Error (ME) [START_REF] Pool | Using road topology to improve cyclist path prediction[END_REF]. RMSE is mostly used to represent the errors of continuous motions between the (sampled) prediction and ground truth, such as acceleration [START_REF] Xu | Sceneaware driver state understanding in car-following behaviors[END_REF] [46], velocity [19] [11] [13] [START_REF] Klingelschmitt | Using Context Information and Probabilistic Classification for Making Extended Long-Term Trajectory Predictions[END_REF], as well as position and distance [START_REF] Bahram | A Combined Model-and Learning-Based Framework for Interaction-Aware Maneuver Prediction[END_REF] [13] [START_REF] Klingelschmitt | Using Context Information and Probabilistic Classification for Making Extended Long-Term Trajectory Predictions[END_REF]. A special implementation of RMSE is for evaluating the error of discretized probability weighted by the corresponding occupancy grid distance [START_REF] Kim | Probabilistic Vehicle Trajectory Prediction over Occupancy Grid Map via Recurrent Neural Network[END_REF].

3) Likelihood: Likelihood is commonly used metric for training probabilistic models [19] [11] [41] [START_REF] Dong | Intention estimation for ramp merging control in autonomous driving[END_REF] [47] [START_REF] Tran | Modelling of traffic situations at urban intersections with probabilistic non-parametric regression[END_REF], although it is not used as widely to evaluate the performance of the trained models since the likelihood values are not well interpretable. Likelihood is used as an evaluation metric in [START_REF] Pool | Using road topology to improve cyclist path prediction[END_REF] [13] [START_REF] Phillips | Generalizable intention prediction of human drivers at intersections[END_REF].

4) Kullback-Leibler (KL) divergence: KL divergence is a widely-used metric in machine learning field to measure discrepancies between two probability distributions. In fact, the ultimate goal for probabilistic prediction is to obtain some distribution p(Y |X) which can best describe that of the motions in the dataset q(Y |X). Therefore, metrics aiming at quantifying how much a probability distribution diverges from another is more direct than other metrics in the sense of the ultimate goal. KL divergence is used as an evaluation metric for probabilistic prediction in [START_REF] Morton | Analysis of Recurrent Neural Networks for Probabilistic Modeling of Driver Behavior[END_REF] [START_REF] Wheeler | Analysis of microscopic behavior models for probabilistic modeling of driver behavior[END_REF]. KL divergence is also employed in [START_REF] Wang | How Much Data Are Enough? A Statistical Approach With Case Study on Longitudinal Driving Behavior[END_REF] to assess the similarity of data observation and provide the value of additional motion data.

B. Prior metrics

The decision-making and planning module of the host vehicle need to take into account feasibility constraints according to vehicle kinematics and dynamics, as well as safety constraints for collision avoidance and hard traffic rules. The predicted motions have similar requirements as planned motions, although the requirements are not as strict. A small perturbation of a trajectory may change it from a safe and feasible one to an unsafe or infeasible one, especially when the trajectory is near the constraint boundary. However, such perturbation may not make a large difference on learning metrics or other distance-based metrics. Therefore, in order to achieve a comprehensive evaluation of predicted motion distribution, prior metrics based on planning constraints should also be considered, which is rarely mentioned in existing works.

1) Feasibility violation: Some prediction methods or frameworks can inherently guarantee feasibility. For instance, [START_REF] Aoude | Mobile Agent Trajectory Prediction using Bayesian Nonparametric Reachability Trees[END_REF] incorporated Rapidly-exploring Random Tree (RRT) into the prediction frameworks so that the generated motions can be dynamically feasible. It is an ideal case if the generated motions are sampled from obtained distributions via approaches with feasibility guarantee. Otherwise, violation verification and evaluation are necessary, except for rare cases when one can recognize a driver completely losing control of the vehicle.

2) Safety violation: The requirements on safety are different for prediction and planning. The planned motions for the host vehicle need to consider safety as the top priority, and try its best to guarantee safety if possible. On the contrary, the most important aspect for prediction is to be humanlike. Collisions and hard traffic rule (red light, stop sign, etc.) violations are not common in realistic human driving, but is not extremely rare. Therefore, it is not appropriate to forbid all unsafe motions in predictions, but some obviously unrealistic collisions or violations should not be generated. Values of negative distance headway and negative speed were employed in [START_REF] Morton | Analysis of Recurrent Neural Networks for Probabilistic Modeling of Driver Behavior[END_REF] to evaluate unrealistic motions generated. Collision rate and average distances between the host and the closet merging cars are used as the metric for safety violation and margin of the predicted motions in [START_REF] Dong | Intention estimation for ramp merging control in autonomous driving[END_REF].

C. Decision-related metrics

The learning and prior metrics can help us evaluate how human-like the generated prediction is. There are still several aspects to be considered to evaluate predictions according to the consequences when the prediction is adopted by decisionmaking and planning modules.

1) Fatality: The consequential fatalities of different inaccurate or incorrect predictions can be completely different when they are adopted by the decision and planning module. The inaccuracy and incorrectness should not be treated equally in the metric. Fatality and criticality differences should be revealed.

2) Defensiveness and conservatism: It is crucial for the safety and driving quality of the host autonomous vehicle to survive in the worst case (defensive driving strategy), yet not overreact to threats of low or zero probability (non-conservative strategy) [START_REF] Zhan | A non-conservatively defensive strategy for urban autonomous driving[END_REF]. In order to achieve such a non-conservatively defensive driving strategy, the decision and planning module requires the prediction module to acquire the following two capabilities. One is to enhance defensiveness, namely, to provide all possible future motions (completeness), including possible violations to the traffic rules, and possible careless or dangerous behaviors, so that the host vehicle can drive defensively to potential threats. On the other hand, conservatism should be reduced, that is, to provide zero probability (or a safe to pass indicator) when the corresponding motion is impossible, so that the host vehicle can proceed without hesitation. Similar evaluations were also Representation homogenization aims at homogenizing the representation of the prediction motion and the ground truth by choosing the same the output variations according to the choices for the predicted algorithm. [START_REF] Lefèvre | Intention-aware risk estimation for general traffic situations, and application to intersection safety[END_REF] as miss detection rate corresponding to defensiveness and false alarm rate corresponding to conservatism.

3) Timeliness: Decision and planning module expect correct and accurate predictions to be provided timely, especially for those causing potential fatal accidents. Correct and accurate predictions are meaningless if such motion has already been completed or an accident is inevitable. Therefore, timeto-event (TTE) [START_REF] Pool | Using road topology to improve cyclist path prediction[END_REF] and time-to-intersections (TTI) [START_REF] Klingelschmitt | Probabilistic, discriminative maneuver estimation in generic traffic scenes using pairwise probability coupling[END_REF] variables were used as the horizontal axis with learning metrics as the vertical axis, so that the timeliness of accurate predictions can be revealed. Distance-to-event variables were also employed in [START_REF] Wyder | A Bayesian filter for modeling traffic at stop intersections[END_REF], in which specific quantile, mean and standard deviation of distance until correct classification (DCC) were used as metrics. [START_REF] Lefèvre | Intention-aware risk estimation for general traffic situations, and application to intersection safety[END_REF] also addressed timeliness from threat estimation perspective as time-to-collision when dangerous situation is correctly classified.

4) Preview horizon:

The length of the preview horizon is crucial for a motion planning module. Long-term horizon is preferred for safety and driving quality. Accordingly, the predicted motion should have the same horizon as required by the planning module. Therefore, the ideal case is to provide the distribution of the predicted motion within a long-term horizon, and compare the accuracy over the horizon length, as was illustrated in [START_REF] Bahram | A Combined Model-and Learning-Based Framework for Interaction-Aware Maneuver Prediction[END_REF] [28] [START_REF] Geng | A Scenario-Adaptive Driving Behavior Prediction Approach to Urban Autonomous Driving[END_REF].

5) Computational cost:

When a probabilistic method serves as an online prediction module, the host vehicle requires it to provide results in real time. The computational cost should be considered as a metric, especially when the size of the model is relatively large. Computational time was provided in a few recent works [START_REF] Koenig | Exact inference and learning in hybrid Bayesian Networks for lane change intention classification[END_REF] for comparison.

V. CONCLUSION AND FUTURE WORK

In this paper three under-explored aspects of probabilistic prediction were highlighted for on-road autonomous driving from decision and planning perspective. A systematic and unified framework for analysis of prediction problems and methods was provided (summarized in Figure 2). Practical input and output variations for decision and planning, such as local and blind view, reactive prediction, and situation prediction were addressed for problem formulation. Indicators for motion representation simplification were summarized as continuous motions, motion patterns and spatiotemporal indicators. The distinctions between pattern and desire were clarified based on ground truth existence. In addition to reviewing learning metrics which were commonly used for model evaluation, we also recommended omitted but crucial metrics to be considered according to the prior knowledge and requirements from the decision and planning module. It was emphasized that the predicted motion should avoid feasibility and safety violations, and decision-related factors should be taken into account, such as fatality, defensiveness and conservatism, timeliness and horizon, as well as computational cost.

Our future work is focused on constructing appropriate evaluation metrics and conducting corresponding motion dataset processing by considering the aspects addressed in this paper. For a given observation input, the ground truth is expected as a distribution of some representation of the future motions, although only a single sample can be directly obtained from data. Since the ultimate goal of the evaluation of probabilistic prediction is to compare distributions of the prediction and dataset, we tentatively adopt KL divergence as a baseline for metric construction. The data should be processed to provide appropriate ground truth, and KL divergence is modified to adapt samples and is weighted by the decision-related metrics. Prior knowledge is also incorporated to avoid the bias of the limited data and achieve realistic prediction according to feasibility and safety considerations.

Fig. 1 :

 1 Fig.1: Typical structure and data flow for probabilistic prediction. Observations are generated via feature extraction of historical motions in the dataset combined with maps from prior knowledge. Prediction algorithm provides predicted distribution according to the observation input by incorporating prior knowledge such as traffic rules, vehicle models and maps. Since the motion representation in the predicted distribution is often simplified, the representation of the future motions in the dataset should be homogenized so that the ground truth can be used to evaluate the performance of the algorithm by appropriate metrics.

Fig. 2 :

 2 Fig.2: Summary of highlighted aspects for probabilistic prediction which were under-explored, which is extended from Figure1. Feature extraction module is composed by input variations and feature selection, which determine the form of the observation by combining maps in prior knowledge. The future motion of the host from the dataset is used as the input for reactive prediction (Section II-B.3). Representation homogenization aims at homogenizing the representation of the prediction motion and the ground truth by choosing the same the output variations according to the choices for the predicted algorithm.

*This work was supported by Mines ParisTech Foundation, "Automated Vehciles -Drive for All" Chair.