P Schläfer
email: schlaefer@eit.uni-kl.de

V Rybalkin
email: rybalkin@eit.uni-kl.de

N Wehn
email: wehn@eit.uni-kl.de

M Alles

T Lehnigk-Emden

E Boutillon
email: emmanuel.boutillon@univ-ubs.fr

A new Architecture for High Speed, Low Latency NB-LDPC Check Node Processing

Non-binary low-density parity-check codes have superior communications performance compared to their binary counterparts. However, to be an option for future standards, efficient hardware architectures must be developed. State-of-theart decoding algorithms lead to architectures suffering from low throughput and high latency. The check node function accounts for the largest part of the decoders overall complexity. In this paper a new hardware aware check node algorithm and its architecture is proposed. It has state-of-the-art communications performance while reducing the decoding complexity. The presented architecture has a 14 times higher area efficiency, increases the energy efficiency by factor 2.5 and reduces the latency by factor of 3.5 compared to a state-of-the-art architecture.

I. INTRODUCTION

Upcoming standards like 5G will increase the demands on throughput and latency of communication systems. Especially applications like the Tactile Internet [START_REF] Fettweis | The Tactile Internet: Applications and Challenges[END_REF] require a significantly reduced latency. At the same time, error free transmission has to be guaranteed, which requires forward error correction schemes. Low-Density Parity-Check (LDPC) codes where first proposed by R.G. Gallager in 1963 [START_REF] Gallager | Low-Density Parity-Check Codes[END_REF] and rediscovered by D. Mackay and others in 1996 [START_REF] Mackay | Near Shannon limit performance of Low-Density Parity-Check Codes[END_REF]. In the following almost two decades a lot of research has been carried out in this field. Today many commercial standards (WiMAX, WiFi, DVB-C2, DVB-S2, DVB-T2) make use of LDPC codes. Very long binary LDPC codes have been proven to perform close to the Shannon limit. However when considering short blocks of only some hundred bit length for low latency applications, they suffer under degradation in communications performance of more than 0.5 dB. The extension of binary LDPC codes to Galois Fields (GF(q)s) with q > 2 is a promising approach to solve this problem. Moreover the symbols of high-order modulation schemes can be directly mapped to the decoders input symbols. Thus an additional gain in communications performance is observed for systems combining high-order modulation and Non-Binary Low-Density Parity-Check (NB-LDPC) codes [START_REF] Pfletschinger | Getting Closer to MIMO Capacity with Non-Binary Codes and Spatial Multiplexing[END_REF]. The performance gain of NB-LDPC codes comes at the cost of significantly increased decoding complexity. The decoding can be performed by message passing algorithms like Belief Propagation (BP), however the complexity increases with the size of the GF(q). A straightforward implementation of the BP algorithm has a complexity of O(q 2 ) [START_REF] Davey | Low-Density Parity Check Codes over GF(q)[END_REF]. In the last years several approaches have been proposed to reduce the decoding complexity without sacrificing the communications performance. Algorithms working in the Fourier domain [START_REF] Barnault | Fast decoding algorithm for LDPC over GF(2q)[END_REF] [7] have an excellent communications performance, but are still too complex for efficient hardware architectures. Symbol flipping algorithms [START_REF] Lu | An efficient majoritylogic based message-passing algorithm for non-binary LDPC decoding[END_REF] [START_REF] Garcia-Herrero | Non-Binary LDPC Decoder Based on Symbol Flipping with Multiple Votes[END_REF] in general have low complexity but suffer from heavily degraded communications performance. Approaches based on stochastic decoding [START_REF] Ciobanu | Adaptive Multiset Stochastic Decoding of Non-Binary LDPC Codes[END_REF] [START_REF] Yang | Area-efficient TFM-based stochastic decoder design for nonbinary LDPC codes[END_REF] have been presented as an alternative decoding method but introduce very high decoding latency. An extension of the well known binary Min-Sum algorithm to the non-binary domain, called Extended Min-Sum (EMS) algorithm [START_REF] Declercq | Decoding Algorithms for Nonbinary LDPC Codes Over GF[END_REF] [13] [START_REF] Li | Trellis-Based Extended Min-Sum Algorithm for Non-Binary LDPC Codes and its Hardware Structure[END_REF] gives the best compromise between hardware complexity and communications performance. Therefore in this paper we will focus on the EMS algorithm which is the most promising starting point for efficient architectures.

To achieve the required throughput of today's applications, executing the algorithms in software is not sufficient. Dedicated hardware architectures become mandatory. The largest complexity in the EMS algorithm is the computation of the Check Node (CN). State-of-the-art architectures apply a so called Forward-Backward (FWBW) scheme [START_REF] Wymeersch | Log-domain decoding of LDPC codes over GF(q)[END_REF] to process the CN. A serial calculation is carried out to reduce the hardware cost and to allow for reuse of intermediate results during the computation. However this scheme introduces high latency and degrades the throughput. This effect increases significantly when the size of the GF(q) or the CN degree grows.

The Syndrome-Based (SYN) CN algorithm, previously presented in [START_REF] Schläfer | Syndrome Based Check Node Processing of High Order NB-LDPC Decoders[END_REF] is the first approach allowing for efficient parallel computation of the CN function for higher-order Galois fields (q ≥ 16). In this paper we present modifications of the original algorithm leading to the first hardware implementation of the SYN CN algorithm. For a GF(64) we observed an increase in area efficiency of factor 14 and a latency reduction of factor 5 compared to state-of-the-art CN architectures.

The paper is structured as follows. In Section II we review the decoding of NB-LDPC codes making use of the EMS algorithm. The SYN CN algorithm is presented in Section III and further optimizations for the hardware implementation are discussed in Section IV. The novel architecture is described in Section V. Finally Section VI presents a comparison with other CN architectures in means of area and energy efficiency, latency and communications performance. Section VII concludes the paper.

II. EMS DECODING

This section reviews the EMS algorithm to give an overview of the complete decoding process.

Let us consider an (N, K) NB-LDPC code over GF(q) where N is the codeword length and K the number of information symbols. The code is defined by a sparse parity check matrix H with N columns, M = N -K rows and elements h m,n . The transmitted codeword consists of the codeword symbols c = (c 1 , c 2 , . . . , c N ), c i ∈ GF(q). The decoder receives the noisy representation of the codeword symbols, y = (y 1 , y 2 , . . . , y N ).The decoding process can be partitioned in four main parts, the initialisation, the Variable Node (VN) update, the CN update and the permutations in the Permutation Nodes (PNs). It is important to mention that in contrast to a binary LDPC decoder instead of a single Logarithmic Likelihood Ratio (LLR) a set of q LLRs is exchanged between the nodes on each edge. This fact accounts for the significant increase in complexity compared to binary LDPC decoding.

The first step in the EMS algorithm is the calculation of the symbol LLRs for the received codeword. For each received symbol y i , a set of q LLR values is calculated. Under the assumption that all GF(q) symbols are equiprobable, the initialization LLRs for VN v are calculated as follows:

∀x ∈ GF(q) L v [x] = ln P (y v |c v = xv ) P (y v |c v = x) with xv = max ∀x∈GF(q) {P (y v |c v = x)} . (1)
Given this definition it follows that L v [x v ] = 0 and L v [x] ≥ 0 with an increasing LLR representing a decreasing symbol reliability. For simplified reading, in the following we use an array to represent the message sets. Messages from VN to PN are denoted as U vp , messages from PN to CN as U pc . Respectively messages from CN to PN are called V cp and messages from PN to VN as V pv .

In the first iteration the VNs simply forward the channel values (Eq. ( 1)) to the according CNs. The VN outputs are calculated as

U vp [x] = L v [x]
. In all other iterations the VN operation is to combine the channel values L v with the d v incoming message sets V pv , where d v is the VN degree. The updated extrinsic messages U vp of VN v are calculated as follows:

U vp [x] = L v [x] + dv t=1,t =p V tv [x], ∀x ∈ GF(q), p = 1 . . . d v .
(2) The VN function is to sum up all values for a certain Galois field element x received from the connected CNs and the according channel information L v [x]. This however has to be performed for all q elements of the GF(q). To achieve the same message structure as before (LLR = 0 for the most reliable symbol, increasing LLR values for less reliable symbols), a normalisation of the U vp messages with respect to the most reliable symbol has to be applied at the output of the VN. The next step in the decoding is the permutation according to the parity check matrix H. The permutation of the VN v outputs U vp is defined as:

U pc [x] = U vp [h -1 c,v • x], ∀x ∈ GF(q), p = 1 . . . d v , (3)
where h c,v is the Galois field element at row c and column v of H, U pc represents the input for CN c.

In the CN update d c edges from U pc are processed. The outputs of CN c are calculated as follows:

V cp [x] = min ∀ permutations of xt dc t=1;t =p U tc [x t ] with dc t=1;t =p x t = x, ∀x ∈ GF(q), p = 1 . . . d c . (4)
For every Galois field element x all possible input permutations fulfilling the parity check constraint are evaluated. The parity check constraint is given by the sum of the according Galois field elements. From all valid combinations the one with the highest reliability (smallest LLR) is chosen. Again, this task has to be performed for all q elements of the Galois field.

The CN computation is the most complex part of the decoding and has a complexity of O(q 2 ) when calculated straightforward with the FWBW scheme [START_REF] Wymeersch | Log-domain decoding of LDPC codes over GF(q)[END_REF].

Before one iteration is completed the outputs of CN c must be reverse permuted.

V pv [x] = V cp [h c,v • x], ∀x ∈ GF(q), p = 1 . . . d c . (5)
This closes the loop and another iteration starts. The processing of a block is stopped as soon as a valid codeword is detected.

To make this decision the estimated symbols x need to be computed for each VN v:

xv = min x∈GF(q) L v [x] + dv p=1 V pv [x] . (6)
In state-of-the-art EMS decoding one important simplification is applied. It has been shown in [START_REF] Declercq | Decoding Algorithms for Nonbinary LDPC Codes Over GF[END_REF], that the sets of q messages exchanged between VNs and CNs can be truncated to carry only the n m most reliable values per edge without sacrificing the communications performance. This approach significantly reduces the implementation complexity and is used for the algorithms presented in the following sections.

III. SYNDROME-BASED CN PROCESSING

For the sake of clarity we review the basic SYN CN algorithm, earlier presented in [START_REF] Schläfer | Syndrome Based Check Node Processing of High Order NB-LDPC Decoders[END_REF], before architecture specific modifications are introduced in Section IV.

The state-of-the-art way of CN processing with the FWBW scheme [START_REF] Boutillon | Bubble check: a simplified algorithm for elementary check node processing in extended min-sum non-binary LDPC decoders[END_REF] [18] has several drawbacks. Architectures making use of the FWBW scheme suffer from low throughput and high latency. Todays approaches to solve these issues are limited to small GF(q)s with q ≤ 16 which have only small gain in Frame Error Rate (FER) compared to their binary counterparts [START_REF] Li | Trellis-Based Extended Min-Sum Algorithm for Non-Binary LDPC Codes and its Hardware Structure[END_REF]. Only with Galois fields of high-order significantly higher communications gains can be achieved. Therefore in [START_REF] Schläfer | Syndrome Based Check Node Processing of High Order NB-LDPC Decoders[END_REF] we proposed a new algorithm, the so called SYN CN processing which can also be applied to Galois field sizes of practical interest (q ≥ 64).

The basic structure of the SYN CN processing is depicted in Fig. 1. In the first step of the algorithm the syndromes are calculated. In contrast to the classical use of the term syndrome, we define a syndrome as the sum of one GF(q), Syndrome Calculator Sorter Decorrelat.

... ... ...

Sorter

Decorrelat.

Fig. 1: Syndrome-based CN processing LLR tuple from each input set. Each input U carries n m messages, which allows for the calculation of a set of different syndromes called S. Individual syndromes are distinguished by the input elements which are chosen for the sum. Let K ic be the set of n m most reliable field elements from the ith edge of CN c. The syndrome reliability R(x 1 . . . x dc ) and according Galois field element G(x 1 . . . x dc ) for CN c are calculated as follows:

R(x 1 . . . x dc ) = dc t=1 U tc [x t ], x t ∈ K tc (7) G(x 1 . . . x dc ) = dc t=1 x t , x t ∈ K tc (8)
One syndrome SYN is then defined as follows:

SYN(x 1 . . . x dc ) = R(x 1 . . . x dc ), G(x 1 . . . x dc ) (9)
The syndrome set S contains all valid syndromes:

S = SYN(x 1 . . . x dc ) : ∀x 1 . . . x dc ∈ K tc (10)
Calculating the syndromes in S as the sum of elements over all input edges (Eq. ( 7) and Eq. ( 8)), disregards one of the basic concepts of BP algorithms: In-and output of the same edge must not be correlated. Thus an additional step in the SYN CN processing is the decorrelation of in-and output:

R i (x 1 . . . x dc ) = R(x 1 . . . x dc ) -U ic [x i ], x i ∈ K ic (11) G i (x 1 . . . x dc ) = G(x 1 . . . x dc ) -x i , x i ∈ K ic ( 12
)
The result is a dedicated syndrome set S i for every output i, which has no correlation with input i.

SYN i (x 1 . . . x dc ) = R i (x 1 . . . x dc ), G i (x 1 . . . x dc ) (13)
S i = SYN i (x 1 . . . x dc ) : ∀x 1 . . . x dc ∈ K tc (14)
Once the S i sets are computed, they are sorted by their syndrome reliability, represented by the LLRs. This gives direct access to the n m most reliable syndromes which constitute the CN output sets V cp .

The algorithm we proposed is an alternative to the conventional FWBW processing. It is the first approach for high-order Galois field decoding, allowing for massive parallel implementations and thus high throughput and low latency. However, without special treatment the calculation of the syndrome set S and the sorting of S i introduce a high complexity. It has to be reduced to make the algorithm attractive for hardware implementations.

LLR GF LLR GF LLR GF LLR GF Index ... 0 1 2 reliability U 1 U 2 U 3 U 4

IV. COMPLEXITY REDUCTION OF THE SYNDROME-BASED CN PROCESSING

In this section we are presenting an approach to reduce the complexity of the afore introduced SYN CN algorithm. The target is to allow the algorithm to be implemented efficiently in hardware. Therefore we discuss algorithmic modifications for simplifications of the syndrome set generation and the sorting while maintaining the communications performance.

A. Reducing the syndrome set cardinality:

The first point to optimize is the calculation of the syndrome set S. For the output computation only the most reliable values of S are used which makes the computation of all other syndromes superfluous. Thus a smart reduction of the cardinality of S, |S| can significantly reduce the overall complexity of the algorithm without sacrificing the communications performance.

The first step for a reduction of |S| is the separation of syndromes with high reliability from ones with low reliability. In the following, a concept similar to the configuration sets introduced in [19] [START_REF] Li | Trellis based Extended Min-Sum for decoding nonbinary LDPC codes[END_REF] is applied to the computation of S. Therefore we define d c + 1 deviation sets D i with i ∈ 0 . . . d c . This procedure is just a separation of the syndrome set in subsets:

S = dc i=0 D i . ( 15
)
Each set contains only syndromes deviating in exactly i elements from the most reliable element as shown in Fig. 2.

The subset D 0 contains only one syndrome, which is the sum of the most reliable elements from all inputs. These sub-sets structure the data in a way that allows for easier access to syndromes with high reliability. Figure 3 shows the average LLR values of the syndromes in the sorted deviation sets D i . One can observe, that the distribution of reliable LLRs depends on the Signal-to-Noise Ratio (SNR). However, syndromes with more than two deviations e.g. D i for i > 2 have such a low reliability that they rarely contribute to the generation of the outputs. Thus we can limit the calculation of sub-sets D i to the ones with a low amount of deviations.

Another parameter for reduction of |S| is the maximum allowed distance d i of elements contributing to deviation D i . The distance describes the position of the element in the input set relative to the most reliable element. The most reliable element has the index zero. Less reliable elements have higher indices which describe their rank in the sorted list of LLRs. For the calculation of D i only elements with indices less or equal to d i are considered. The maximum allowed distance for a certain deviation can be set dynamically based on the LLR value of the elements or it is fixed, as a predefined parameter. For each deviation a different maximum distance can be set, see Fig. 2, e.g. the higher the number of allowed deviations, the lower the maximum distance of the deviations,

d 1 ≥ d 2 ≥ • • • ≥ d dc .
Using this scheme implicitly keeps the best syndromes in each D i and removes the less reliable ones. The cardinality of the subsets D i can be calculated as follows:

|D i | =        d c i • (d i ) i if d i ≥ 1; i > 0 1 if i = 0 0 else (16)
Combining both proposed techniques strictly reduces the cardinality of S and thus the computational complexity. The

B. Simplifying sorting:

One big drawback of the original SYN CN algorithm presented in Section III is that every syndrome set S i must be sorted separately to output the n m most reliable syndromes. This is the case because of the decorrelation step applied before. To avoid the sorting of the decorrelated syndrome sets S i , a simple but effective approach can be chosen. Instead of decorrelating every value, only syndromes using the most reliable element from the currently handled edge (LLR = 0) are considered. All other syndrome are not used for the current edge output. By this approach the order of the syndromes is not changed and it is sufficient to sort S instead of the d c S i sets. In addition, the LLR values are not modified in the decorrelation step which saves a real valued subtraction for every output message. Finally only the most reliable input element and not the complete input sets must be stored for the decorrelation. The proposed algorithmic modifications result in a slightly different data flow, see Fig. 5. Figure 4 shows the schematic operations of one decorrelator. Each syndrome is denoted with the additional information about which of the input edges contributed to the syndrome with a deviation. SRC in Fig. 4 stores the edges where deviations occurred and ADDR i represents the current edge. A simple comparison evaluates if a deviation from the current edge was involved in the syndrome calculation and thus if the syndrome is valid for the current edge or not. Only if no deviation occurred on the current edge, the decorrelated message is marked as valid and used for the output V i .

Even though the sorting has been reduced to the syndrome set S, there is more potential for simplification. Sorting S can be divided into sorting the deviation sets D i and merging them. Especially for D 1 the sorting can be further simplified. This is achieved due to the previous knowledge we have of the input data. We implicitly know that the sets U pc are sorted according to their LLRs. The sorting of D 1 thus is limited to merging d c sorted sets. For the higher-order deviations D i for i ≥ 2, the sorting can also be simplified because of the sorted input sets. Sorted sub-sets are generated with little effort which only have to be merged to achieve the final set. An example of the sub-set generation for D 2 with d 2 = 2 is given in Fig. 6 which can be extended easily to other deviations and distances. Once the sub-sets are sorted, the outputs can be generated by merging them iteratively. However, considering the NB-LDPC decoder as a whole, it can be observed, that an exact sorting of the CN outputs is not required. When the VN has calculated the a posteriori probability (APP) messages as the sum of the channel values and messages from the CNs (Eq. ( 2)), they have to be resorted anyway. Thus an approximately sorted CN output is sufficient and does not impair the decoder's communications performance. In the following we present a scheme which uses the robustness against approximately sorted CN outputs to further reduce the algorithms complexity.

To allow for this approximate sorting, so called probes are chosen and sorted according to their LLR. Figure 7 shows the distribution of probes within the input set U 1 used for D 1 . In this paper we assume that the probes are equally distributed in the input sets which works well for the investigated configuration. The considered probe positions are 3, 6, 9 and 12. However, for other parameters of d c and n m other distributions are beneficial. Each probe is connected to a set of neighbouring syndromes, seee Fig. 7. The probes LLR value is considered to be representative for the whole group of syndromes. In the following, instead of iteratively merging the sub-sets syndrome by syndrome, the probes and their neighbouring syndromes are merged on set basis. This means that three neighbouring syndromes are chosen at a time, based on the reliability of the according probe. Only the LLR value of the probe has an impact on the sorting, the LLRs of the neighbouring syndromes are not considered. This scheme leads to some uncertainty in the merged set but is close enough to the exact solution not to degrade the decoders communications performance. Figure 8 shows the LLR values of the approximately sorted syndromes used for the CN output calculation. The approximation works well for low LLRs (high reliability) and only for the less reliable outputs there is a difference compared to the optimal sorting results.

Summarized, three notable benefits arise from the algorithmic transformations introduced in this section:

• Significant reduction of |S|.

• Approximated sorting of S instead of exact sorting of S i .

• No subtractions and no storage for U i in the decorrelation step.

V. ARCHITECTURE

In this section we present a hardware implementation of the algorithm proposed before. The architecture is independent of the actual used NB-LDPC code, only the parameters d c = 4, q = 64 and n m = 13 are given. As we are working with truncated sets, we have to redefine U i (j), j ∈ 0...n m -1 as the jth GF(q), LLR tuple from edge i. We use the LLR(. . . ) and GF(. . . ) notation to distinguish between the GF(q) and LLR part of one of these tuples respectively.

Figure 9 shows an overview of the CN hardware. To achieve low latency and high throughput, the input parallelism of the CN was chosen to be six GF(q), LLR tuples and an additional GF(q) input for the most reliable element. All input messages can thus be read within two clock cycles. The evaluation of the probes can be processed in parallel with the actual calculation of the syndrome set. The selection of the sub-sets is performed in dedicated units, the syndrome selectors, based on the result of the probe evaluators. Once S is calculated and the probes are evaluated, the most reliable sub-sets are used for the decorrelation. The parallelism with which the syndromes are process has significant impact on the overall throughput. It has been chosen to be three times three syndromes. In each clock cycle two sets of neighbouring syndromes from D 1 and one set from D 2 , overall nine syndromes are processed. Thus, after a maximum of four clock cycles all output edges are filled with n m valid messages. The output parallelism of the CN chosen symmetrically the inputs to six GF(q), LLR tuples and one GF(q) message for D 0 . The design is constructed from four main building blocks which will be explained in detail in the following sections.

A. Probe Evaluator

The probe evaluator for D 1 processes two probes per edge in each clock cycle. For d c = 4 overall eight LLRs have to be sorted, which is performed by a latency optimized sorting network. As each two messages are implicitly sorted already because they belong to the same edge, some simplifications on the network can be applied. The final sorting network is depicted in Fig. 10. The result of the sorting is not a sorted list of LLRs but rather the positions of the inputs where they come from. They are stored in a register and the same task is Once a probe is used for an output generation, it is removed by shifting the register content accordingly. The probe evaluator for D 2 is a simplified version of the one for D 1 as it considers only four inputs. Moreover it needs to generate only one output per clock cycle. The output of the probe evaluators is used as control signal for the syndrome selector components.

B. Syndrome Calculator

The syndrome calculation is carried out fully parallel. Due to the restrictions on the deviation distances (d 0 = 0,

d 1 = n m -1, d 2 = 2)
, the required hardware is strictly limited. A sophisticated scheme for the calculation allows for further reduced hardware cost, see Fig. 11. Instead of calculating each syndrome as a sum of d c inputs, intermediate results are used to minimize the number of explicit calculations. The calculation of D 0 involves d c -1 GF(q) additions, for D 1 overall d c • n m GF(q) additions are required. Thus for D 0 and D 1 only GF(q) calculations are required. For D 2 the processing scheme of D 1 can easily be extended and requires only one real valued addition per syndrome in addition to the GF(q) operations. Compared with state-of-the-art processing, there is a significant saving in computational complexity. The output of the syndrome calculator is a number of sorted subsets used as input for the syndrome selectors.

C. Syndrome Selector

The syndrome selector receives the addresses of the most reliable syndrome sets from the probe evaluator and the syndromes D i sorted in sub-sets from the syndrome generator. The complete hardware consists of a multiplexer tree choosing a set of the three most reliable syndromes from the subsets. To achieve six messages from D 1 , the multiplexer tree is duplicated in this unit, see Fig. 12. For D 2 a single tree choosing between the six sub-sets of D 2 suffices.

D. Decorrelator

Decorrelation has to be performed individually for each edge of the CN. output parallelism of the decorrelator is six messages per clock cycle. Two times three syndromes from D 1 and another three from D 2 are processed per clock cycle. By construction the messages of a set always have deviations on the same edges. Thus it is sufficient to check for one of the messages in a set if it is valid or not, which is indicated with a valid flag. If only a part of the received sets is valid, they are rearranged by multiplexers in such a way, that only valid messages are used for the output. In the best case all syndromes received in one clock cycles are valid. As the output parallelism is only six, the surplus syndromes are stored in an additional register and reused in the next clock cycle. Before the messages are sent to the VN, the actual decorrelation is applied which is a subtraction of the most reliable GF(q) value of the current edge.

VI. RESULTS

The architectures presented in this section are based on a code which has a code word length N of 16 GF(64) symbols (96 bits), a Code Rate (CR) of 0.5, d v = 2 and d c = 4. Code generation has been performed based on the approach presented in [START_REF] Poulliat | Design of regular (2,dc)-LDPC codes over GF(q) using their binary images[END_REF]. The SYN CN makes use of truncated vectors of size n m = 13. The architecture is implemented on a 65nm low power bulk CMOS library from ST Microelectronics. We considered the following PVT parameters: Worst Case (WC, 1.1V, 125 The final design reaches a Worst Case frequency of 400 MHz. After P&R approximately 0.07 mm 2 are required for the core. An area utilization (cell/core area ratio) of 84 % is achieved. We also evaluated the power consumption of the physical design using Synopsys PrimeTime-PX. The average power consumption at a clock frequency of 400 MHz is 30 mW for the Nominal Case. The physical layout of the CN can be seen in Fig. 13. Compared to a state-of-the-art CN based on the FWBW architecture presented in [START_REF] Boutillon | Design of a GF(64)-LDPC Decoder Based on the EMS Algorithm[END_REF] and implemented in the same technology, the SYN CN achieves a 14 times higher area efficiency and 2.5 times higher energy efficiency. At the same time the latency (processing time for one CN update) is reduced from 21 clock cycles to only 6 clock cycles. A comparison of achieved communications performance shows the difference with respect to the state-of-the-art hardware aware FWBW decoding, see Fig. 14. The syndrome based CN computation has a superior performance compared to the FWBW implementation.

Our next target is the design of a high throughput decoder based on the presented CN. Future challenges are the extension of the presented design to higher edge degrees and even higherorder Galois fields (q ≥ 256).

VII. CONCLUSION

We have presented a new algorithm and architecture for the CN processing of NB-LDPC decoders. The SYN CN algorithm is the first hardware aware CN processing, allowing for low latency and high throughput decoder architectures using high-order Galois fields. A hardware implementation is presented which underlines the potential of the proposed algorithm. A 14 times higher area efficiency and 2.5 times higher energy efficiency is achieved compared to a state-ofthe-art CN architecture while the latency is reduced by factor 3.5. This is a big step into the direction of efficient NB-LDPC decoders with sufficient throughput for future applications.

Fig. 2 :

 2 Fig. 2: Exemplary syndromes with two (filled circles) and three deviations (open circles) and maximum distances d 2 and d 3 .

Fig. 3 :

 3 Fig. 3: Averaged LLR values of D i for a GF(64), d c = 4 code. D i for i > 1 are truncated and show only the 48 most reliable syndromes.

Fig. 4 :Fig. 5 :

 45 Fig. 4: Decorrelator for edge i.

Fig. 6 :

 6 Fig. 6: Sub-set generation for D 2 with d 2 = 2, and SRC denoting the deviation positions.

Fig. 7 :

 7 Fig. 7: Probes distribution for approximate sorting. The probes and related syndromes are highlighted in same color.

Fig. 8 :

 8 Fig. 8: Approximately sorted output LLRs for different SNR points.

Fig. 9 :

 9 Fig. 9: Top-level architecture of the SYN CN.

Fig. 10 :

 10 Fig. 10: Probe evaluator for D 1 .

Fig. 11 :

 11 Fig. 11: Syndrome calculator for D 0 and D 1 .

Fig. 12 :

 12 Fig. 12: Syndrome selector for D 1 .

Fig. 13 :

 13 Fig. 13: SYN CN chip layout.

Fig. 14 :

 14 Fig. 14: Communications performance of the SYN CN compared to the state-of-the-art FWBW scheme.

  • C), Nominal Case (NOM, 1.2V, 25 • C) and Best Case (BC, 1.3V, -40 • C). Synthesis was performed with Synopsys Design Compiler in topographical mode, Placement & Routing (P&R) with Synopsys IC Compiler. Synthesis as well as P&R were performed with the Worst Case PVT settings of the 65nm library.

TABLE I :

 I State-of-the-art NB-LDPC CN comparison, with parameters d c = 4, q = 64 and n m = 13.

	Decoder	SYN CN	FWBW CN
	CMOS Technology	65nm SVT	65nm SVT
	Supply Voltage [V]	1.2	1.2
	Frequency [MHz]	400	250
	Quantization	8 bit	8 bit
	Post P&R Area [mm 2 ]	0.067	0.112
	Area Utilization	84%	70%
	Throughput [Mel/s] a	5200	620
	Energy Eff. [pJ/el]	5.7	13.8
	Area Eff. [Gel/s/mm 2 ]	77.5	5.5
	Decoding Latency [CC] b	6	21
			a el = elements
			b CC = Clock Cycles


Romain Gallen
email: romain.gallen@developpement-durable.gouv.fr

Aurélien Cord
email: aurelien.cord@ifsttar.fr

Member, IEEE Nicolas Hautière
email: nicolas.hautiere@ifsttar

Éric Dumont
email: eric.dumont@ifsttar.fr

Didier Aubert
email: didier.aubert@ifsttar.fr

E Dumont

Nighttime Visibility Analysis and Estimation Method in the Presence of Dense Fog

Keywords: Advanced driver assistance systems (ADASs), advanced lighting systems, camera, fog characterization, fog detection, night fog, visibility

Compared with daytime, a larger proportion of road accidents happens during nighttime. The altered visibility for drivers partially explains this situation. It becomes worse when dense fog is present. In this paper, we first define a standard night visibility index, which allows specifying the type of fog that an advanced driver assistance system should recognize. A methodology to detect the presence of night fog and characterize its density in images grabbed by an in-vehicle camera is then proposed. The detection method relies on the visual effects of night fog. A first approach evaluates the presence of fog around a vehicle due to the detection of the backscattered veil created by the headlamps. In this aim, a correlation index is computed between the current image and a reference image where the fog density is known. It works when the vehicle is alone on a highway without external light sources. A second approach evaluates the presence of fog due to the detection of halos around light sources ahead of the vehicle. It works with oncoming traffic and public lighting. Both approaches are illustrated with actual images of fog. Their complementarity makes it possible to envision a complete night-fog detection system. If fog is detected, its characterization is achieved by fitting the different correlation indexes with an empirical model. Experimental results show the efficiency of the proposed method. The main applications for such a system are, for instance, automation or adaptation of vehicle lights, contextual speed computation, and reliability improvement for camera-based systems.

I. INTRODUCTION

W HILE night driving only represented 10% of total traf- fic, it represented 47% of fatalities in 2011 in France. Moreover, accident severity during nighttime increases by a factor of 1.7 as compared with daytime [START_REF]Statistiques d'accidentalité Routière: Résultats Définitifs de l'année 2011[END_REF]. Among the factors that explain these figures, drowsiness [START_REF] Friedrichs | Camera-based drowsiness reference for driver state classification under real driving conditions[END_REF], speed [START_REF] Gallen | Supporting drivers in keeping safe speed in adverse weather conditions by mitigating the risk level[END_REF], and reduced visibility [START_REF] Plainis | Road traffic casualties: Understanding the night-time death toll[END_REF] are frequently cited. To address this issue, emphasis is put on the development of smarter lighting strategies for vehicles [START_REF] Tideman | A simulation environment for developing intelligent headlight systems[END_REF]. Advanced systems are being developed to automate and adjust the operation of vehicle lights to maximize visibility while preventing glare for oncoming drivers.

Among the embedded sensors that drive these systems, video cameras are most promising since they have low cost and serve different purposes. In particular, adverse weather conditions, such as rain or fog, are major concerns. First, they directly affect the safety of a driver by reducing his safety margin, i.e., low visibility distance or low friction. Second, they reduce the reliability of camera-based systems by altering image quality. For these two reasons, detecting, characterizing, and mitigating the effects of adverse weather conditions, particularly fog, is a challenge for camera-based advanced driver assistance systems (ADASs). The automatic adaptation of the intensity of lights in fog is still an open issue, although regulations allow it [START_REF]for Europe, Type-Approval Requirements for the General Safety of Motor Vehicles[END_REF]. Fog is known for its effects on visibility, but the visual effects of fog differ between night and day [START_REF] Dumont | Extended photometric model of fog effects on road vision[END_REF], which explains why different camera-based detection methods are needed. Onboard daytime fog detection was pioneered in [START_REF] Hautière | Automatic fog detection and estimation of visibility distance through use of an onboard camera[END_REF] and further tackled in [START_REF] Bronte | Fog detection system based on computer vision techniques[END_REF] and [START_REF] Lenor | An improved model for estimating the meteorological visibility from a road surface luminance curve[END_REF]. The mitigation of daytime fog was addressed by restoring the contrast of images reduced by fog [START_REF] Hautière | Mitigation of visibility loss for advanced camera based driver assistances[END_REF]. The case of heterogeneous daytime fog was also addressed in [START_REF] Tarel | Vision enhancement in homogeneous and heterogeneous fog[END_REF] and [START_REF] Caraffa | Markov random field model for single image defogging[END_REF].

In this paper, the problem of onboard night-fog detection and characterization by camera is addressed. Contrary to daytime, the visual appearance of a road scene in fog at night strongly depends on the presence of artificial light sources in the environment. If a vehicle is alone on the road and there are no lighting fixtures, the fog is only noticeable through the backscattering of light from the headlamps. If there are oncoming vehicles or if there is a road lighting installation, the backscattered veil is no longer noticeable, but the presence of fog can be still noticed by the presence of halos around the light sources. Based on these visual effects, a night-fog detection method has been proposed in [START_REF] Gallen | Towards night fog detection through use of in-vehicle multipurpose cameras[END_REF]. Using spectral features and a simple linear classifier, a classification of images in fog and fog-free scenes is proposed in [START_REF] Pavlic | Classification of images in fog and fogfree scenes for use in vehicles[END_REF]. Among the existing ADASs, some systems use the blurring of the tail lamps of a leading vehicle to determine the presence of fog, such as in patent JP 11-278182A. This only works when there is a vehicle ahead of the equipped vehicle. The two patented camera-based systems [START_REF] Leleve | Method for detecting night fog and system implementing said method[END_REF], [START_REF] Kawasaki | Visibility condition determining device for vehicle[END_REF] rely on the backscattered light from the headlamps in order to detect the presence of fog. They both proceed by analyzing the evolution of pixel intensities along a vertical or horizontal line in the image. Those local methods are impaired by the presence of obstacles or markings in the scene, and because the backscattered luminous level is quite low, their behavior is also impaired when there are multiple light sources in the environment, such as streetlights or headlights from oncoming traffic. For night-fog characterization, some static camera-based systems rely on the temporal comparison of images containing light sources [START_REF] Narasimhan | Vision and the atmosphere[END_REF]- [START_REF] Gallen | Static estimation of the meteorological visibility distance in night fog with imagery[END_REF]. These methods cannot be adjusted to dynamic conditions.

In this paper, we extend the night-fog detection algorithm presented in [START_REF] Gallen | Towards night fog detection through use of in-vehicle multipurpose cameras[END_REF] by adding a novel characterization step, and we assess the method using actual video sequences and reference sensors. This method is original since it is the first method to attempt the characterization of the fog density in night driving scenarios with an onboard camera. In addition, unlike patent JP 11-278182A, the method does not require other cars or obstacles to be in front of the equipped vehicle in order to work. Unlike the patents in [START_REF] Leleve | Method for detecting night fog and system implementing said method[END_REF] and [START_REF] Kawasaki | Visibility condition determining device for vehicle[END_REF] that do not work in strongly lit environments, the system is able to deal with all sorts of lighting environments and does not use a local or photometric approach but a global image analysis process. To specify the class of the fog density that needs to be characterized by our system, we propose to use a nighttime visibility index that is based on the visibility level (VL) of a small target [START_REF] Dumont | Night-time visibility as a function of headlamp beam pattern and pavement reflection properties[END_REF].

This paper is organized as follows. A conventional scenario to derive a standard nighttime visibility index is first proposed. The detection of the backscattered veil is then described. The detection of halos around light sources follows. Then, the fog characterization step is presented. Finally, experimental results are discussed, and perspectives for potential applications are given.

II. DESIGN OF CONVENTIONAL SCENARIO FOR STANDARD NIGHTTIME VISIBILITY INDEX

A. Adrian's Model

The ability to detect an achromatic object in a traffic situation mainly depends on four parameters, i.e., object size and luminance, background luminance, and adaptation luminance. The luminance difference required to detect an object on its background increases with the overall light level to which a driver is adapted. The luminance difference threshold was investigated by Blackwell in laboratory conditions [START_REF] Blackwell | Contrast threshold of the human eye[END_REF]. He later proposed to use the ratio between the actual contrast and the threshold contrast as a visibility descriptor, and this socalled VL was adopted by the International Commission on Illumination (CIE) to evaluate a lighting design in terms of visual performance as follows [START_REF]A Unified Framework of Methods for Evaluating Visual Performance Aspects of Lighting[END_REF]:

VL = C C th = (L -L b )/L b (L th -L b )/L b = ΔL ΔL th ( 1
)
where C is the actual contrast, C th is the threshold contrast, L is the actual object luminance, L th is the object luminance at the threshold contrast, L b is the background luminance, ΔL is the actual luminance difference, and ΔL th is the threshold luminance difference. The most convenient method to calculate the threshold contrast is to use analytic functions fitted to Blackwell's laboratory data. One of the most popular among such empirical models was proposed by Adrian as follows [START_REF] Adrian | Visibility of targets: A model for calculation[END_REF]:

ΔL th = φ 1/2 α + L 1/2 2 • F p • F c • F t • F a (2)
with the φ and L functions depending on the background luminance given by Adrian, α as the angular size of the target (in minutes of arc), and F p depending on the detection rate needed (1 for 50%, 2.6 for 99.9%). F c , F t , and F a are correction factors applied to take into account the contrast polarity, the presentation time, and the age of the observer, respectively. Adrian provided some threshold VL values accounting for field conditions (as opposed to laboratory conditions) [START_REF] Adrian | Visibility levels under night-time driving conditions[END_REF].

B. VL in Nighttime Driving Conditions

The luminance is needed to calculate the VL results from the illuminance generated by the headlamps and from the reflective properties of the illuminated surface. Because contrast determines visibility, two surfaces must be considered for the purpose of evaluating the visibility distance, i.e., that of the object to detect and that of the background. The illuminance E that reaches a target at distance d given a pair of headlamps, for which we know the left and right luminous intensities I L and I R , respectively, emitted toward the target, is given by

E = E L + E R ≈ I L + I R d 2 = I d 2 . ( 3
)
Under headlamp illumination, the relevant parameter to characterize the reflective properties of a vertical object (when its surface is not specular or retroreflective) is the diffuse reflection factor ρ as

L ≈ ρE π ≈ ρ π I d 2 (4)
where L is the target luminance, E is the illuminance generated by the headlamps on the object, I is the intensity of the headlamps in the direction of the object, and d is the distance between the headlamps and the object. In headlamp visibility studies, the targets are usually considered dark, with reflection factor values between 5% and 10%, although values up to 25% are sometimes considered [START_REF] Olson | Development of a Headlight System Performance Evaluation Tool[END_REF]. Horizontal objects (markings) and the pavement are characterized by means of the retroreflected luminance coefficient for headlight illumination

R L (cd • m -2 • lx -1 ) as L = R L E ⊥ ≈ R L • I d 2 (5)
where E ⊥ is the illuminance generated by the headlamps on a surface perpendicular to the lighting direction at the position of the target. The R L of the pavement depends on the illumination and the observation geometry, but it has been shown to be independent of the distance beyond a few tens of meters, with values ranging between 5 and 30 mcd • m -2 • lx -1 for dry pavements [START_REF]Road Surfaces and Lighting[END_REF]. With the previous information, it is possible to calculate the luminance of a small target on the road illuminated by headlamps, as well as the luminance of the pavement at the base of the target, which serves for both the background luminance and the adaptation luminance [START_REF] Farber | Development of a Headlight Evaluation Model[END_REF]. For the headlamp evaluation, the exposure interval is set to 200 ms, and a young driver is considered (age 25). These settings are used to assess the photometric visibility distance as a function of the pavement reflectivity and the headlamp beam pattern [START_REF] Dumont | Night-time visibility as a function of headlamp beam pattern and pavement reflection properties[END_REF].

C. Impact of Fog on Apparent Luminance

The effects of fog on light propagation at night are illustrated in Fig. 1. Two major effects should be accounted for when the only source of illumination is the front-lighting system of the observer's vehicle, i.e., attenuation and backscattering. We estimate the attenuation of light along its path from the headlamps to the target and back to the driver using classical models of light scattering in disperse media. Then, we estimate the luminance of the backscattered veil with an empirical model based on Monte Carlo simulations.

1) Scattering of Light Depending on Distance: Fog is known for its effects on visibility. The droplets composing the fog scatter light in all directions with proportions depending on the size and number of particles per unit volume. Simpler models describe the effects of fog on perceived luminance solely based on the extinction coefficient k of the Beer-Lambert exponential attenuation law, whereas more complex models take into account the distribution of droplet sizes [START_REF] Dumont | A semi-analytic model of fog effects on vision[END_REF]. The Beer-Lambert law describes the amount of luminous energy transmitted through a slab of fog of depth d and extinction coefficient k such that

L = L 0 e -kd ( 6
)
where L 0 denotes the intrinsic luminance of the considered object. Considering the visibility of a black object against the sky, the CIE has related extinction coefficient k to meteorological visibility distance V met , i.e.,

V met = 3 k . ( 7
)
Knowing the contrast threshold necessary for the detection of a target with Adrian's model and the attenuation of contrast by fog with a given extinction coefficient, we are able to compute the distance at which this minimal contrast is still perceived and, thus, the photometric visibility distance in fog. Fog induces a double attenuation of light for night driving conditions: The Beer-Lambert law first applies on the path from the headlamps to a surface in the scene and, then, back to the driver's eyes. We compose ( 4) and ( 5) with ( 6) in order to model this phenomenon as

L ≈ R • I d 2 e -kd • e -kd = R • I d 2 e -2kd (8)
with reflectance R being equal to R L or ρ/π, depending if we consider the pavement or the target.

2) Backscattered Veil From Headlamps: Another phenomenon that contributes to the loss of contrast in the scene is linked to backscattering. Although most of the energy is scattered forward, some is scattered backward toward the driver, generating a permanent veiling effect in front of the car. The luminance of the backscattered veil L v has been studied with Monte Carlo light-tracing software [START_REF] Dumont | Semi-monte-carlo light tracing for the study of road visibility in fog[END_REF]. It has been shown to depend on both the fog type (radiation or advection [START_REF] Dumont | A semi-analytic model of fog effects on vision[END_REF]) and the meteorological visibility distance, and to follow this model (see Fig. 2):

L v = 1 aV met + b . ( 9
)
Parameters (a, b) depend on the fog type, i.e., (0.0089, 0.1241) for radiation fog and (0.0288, 0.2591) for advection fog. This luminance is overimposed on the driving scene, setting the driver's visual adaptation and increasing the apparent luminance of all surfaces; thus, [START_REF] Hautière | Automatic fog detection and estimation of visibility distance through use of an onboard camera[END_REF] becomes

L = R • I d 2 e -2kd + L v . ( 10
)

D. VL Computation

We propose to implement a photometric nighttime visibility metering tool proposed earlier [START_REF] Dumont | Night-time visibility as a function of headlamp beam pattern and pavement reflection properties[END_REF], which we adapt for fog. The idea is to predict the VL of a small object on the roadway at any point along the road under headlight illumination based on the beam pattern, pavement retroreflectivity, and fog parameters. All geometric and photometric parameters are set conventionally: The eyes of the driver are 1.5 m above the ground, the headlamps' mounting height is 0.65 m, the small target is a gray 0.18-m side square with a reflection factor of 8%, the headlamps' beam pattern is the average European high beam from the University of Michigan Transportation Research Institute [START_REF] Schoettle | Highbeam and Low-Beam Headlighting Patterns in the US and Europe at the Turn of the Millennium[END_REF], and the pavement R L is set between 10 and 15 cd • m -2 • lx -1 . The VL of the target is calculated using Adrian's model, as detailed in Section II-A. Since Adrian's model cannot be inverted to compute a distance from a VL value, visibility distance V is iteratively obtained by setting the target closer and closer to the headlamps starting at 150 m, until the VL reaches 7, which is the adopted threshold value.

E. User Needs and Systems Requirements

In order to define the range of the meteorological visibility distance that needs to be considered by the designed system, we define three different classes of fog.

The first class is the most critical class and happens when the nighttime visibility distance using high beams V high is lower than the nighttime visibility distance using low beams V low in the presence of fog. Based on our standard scenario, we are able to compute the corresponding V met threshold as

V met | V high|fog =V low|fog ≈ 100 m. ( 11
)
The second class happens when the nighttime visibility distance using high beams with fog becomes lower than the nighttime visibility distance using low beams without fog. Based on our standard scenario, we are able to compute the corresponding V met threshold as

V met | V high|fog =V low|nofog ≈ 300 m. ( 12
)
We deduce the three classes of fog, which are detailed in Table I. These classes are relevant with regard to the classes proposed in [START_REF] Pavlic | Classification of images in fog and fogfree scenes for use in vehicles[END_REF]. Our in-vehicle system mainly addresses fog classes 2 and 3, which correspond to the most dangerous situations. These thresholds are critical for driver assistance and decision making in terms of lighting automation. They link physical quantities (V met ) to practical user needs. For instance, below V met = 100 m, it is recommended to switch from high beams to low beams, bearing in mind that the visibility is much reduced as compared with clear weather. Between 100 and 300 m, high beams are still preferable, but the visibility distance is inferior to that in clear weather with low beams. When V met is above 300 m, high beams are preferred, although their range is lowered as compared with clear weather.

A. Detection of Backscattered Veil

The first system is based on the fact that the light emitted from the headlamps of a vehicle is scattered backward toward the driver in the presence of fog. The idea that is investigated to detect it is to compare different reference images with the input images grabbed by the camera using a correlation index.

The reference image represents the front of the vehicle with lighting on, as can be seen in fog on a dark road. It is either a real image taken with the same camera in real or artificial fog [see Fig. 3(a)], or a synthetic image. The process allowing to generate such an image can be of any type. In our case, it relies on a Monte Carlo method allowing the synthesis of images in fog in 3-D scenes [see Fig. 3(b)] [START_REF] Dumont | Semi-monte-carlo light tracing for the study of road visibility in fog[END_REF]. When generating a reference image, the photometry and position of the headlamps, the position of the camera inside the car (including its relative angle as compared with the axis of the car), the focal length, and the image resolution of the camera should be all known in order to generate an image as close as possible to a real image acquired with the camera. The synthetic images are luminance maps. Conversion into 8-bit images is done by normalizing the luminance data between 0 and 255. A γ function is also applied to the synthetic images in order to match the γ of the camera. Six reference images are produced in this way for different meteorological visibility distances (see samples in Fig. 4).

Due to the temporal stability of the backscattered veil with time, the input image is a composition of n successive images grabbed by the in-vehicle camera. The composition is computed by taking the mean of successive pixel values or by applying a rank filter such as the median (see Fig. 5). As one can see, the backscattered veil remains in the image, whereas other objects such as lane markings mostly disappear.

The input image is then compared with the six reference images using an image correlation index. Since the exposure settings of the camera are unknown, the synthetic and real images have different dynamics. Among available correlation distances, zero-mean normalized cross correlation (ZNCC) has invariant properties regarding the mean and scale of the illumination level. For these reasons the ZNCC has been used. Since both images are dark outside of the backscattering veil, it adds a bias in the ZNCC score and decreases its discrimination power (see Fig. 4). To overcome this problem, a mask image matching the shape of the backscattered veil in the reference image is computed using Otsu's binarization method [START_REF] Otsu | A threshold selection method from gray-level histograms[END_REF]. The ZNCC score is only computed inside this mask. By applying a threshold on the correlation score, the presence of fog is assessed. When using the six reference images, six ZNCC scores with the input image are obtained; the highest score among them is selected for fog detection.

B. Detection of Halos Around Light Sources

When light sources appear in the road environment, the backscattered veil is no longer noticeable because of the limited dynamic range of the camera. However, fog induces the presence of halos around light sources. A halo is the consequence of light scattering produced by water droplets. In the image, it appears as a luminous shape around light sources, the intensity of which slowly decreases away from the source center. Its expanse and its intensity decrease mainly depend on the fog density and droplet sizes. The algorithm aiming at detecting and characterizing halos is decomposed into the following steps.

1) Light source detection. It is based on an image thresh-

olding at a high intensity level, which is close to the maximum value of image pixels. Each connected component is extracted, and several geometrical parameters are evaluated, i.e., the position of the center of gravity (CoG), the surface, the compactness, the elongation. Relying on these parameters, connected components that do not correspond to isolated sources are discarded. For instance, lane markings are excluded based on their shape; some sources that are agglomerated due to their proximity in the image are discarded based on their large surface or their complex shape. The remaining connected components are called "potential sources." As illustrated in Fig. 6, we start building a tree, in which the leaves are the potential sources associated with their geometrical parameters. 2) Halo segmentation. Progressively decreasing the threshold results in the connected components encompassing larger parts of each source halo in addition to the source itself. At each threshold decrement, the connected components are extracted using the potential sources as seeds.

A new node is added to the tree, under the corresponding potential source's leaf, containing the same geometrical parameters. When two or more potential sources belong to the same connected component, their branches are merged into a single node. We continue decrementing the threshold until all the potential sources merge. Notice that we do not add new leaves to the tree during this process. 3) Halo selection. Based on the geometrical parameters calculated at each step, we exclude the branches for which the following are true. a) The size growth between successive decrements is large, typically more than five times; it corresponds to the fusion of the potential source with a bright object present in the scene. b) The gravity center drastically evolves between successive decrements without a preferred direction; it generally does not correspond to light sources. c) Determination of halo direction. Each branch of the tree is independently studied, and the CoG of the segmented shapes is computed for each node. A linear regression on the successive positions of the CoG along a branch gives the direction of the halo. When a source is isotropic (all CoGs are merged), a direction is chosen arbitrarily. d) Halo intensity profile extraction. The intensity profile is extracted along the direction estimated in the previous step, beginning at the CoG of the source segmented during Step 1 (Light source detection). Fig. 7 illustrates how crucial the direction choice is: For directional light sources, the halo is only present in the lighting direction (the green direction in this case). e) Characterization of the intensity profile of the halo.

In the presence of fog, the decrease in intensity along a source direction is smoother than in the absence of fog. This feature enables to detect fog presence. The choice of the curve characteristic is crucial. A large set of characteristics was explored and statistically Finally, if Br 50 is smaller than a given threshold, fog is detected. Otherwise, no fog is detected. The optimal threshold on Br 50 in our database was estimated to be 9. The detection process is illustrated in Fig. 8.

C. Combination of Both Approaches

As detailed previously, fog creates two main visual effects during nighttime. First, the headlamps produce a backscattered veil in the driver's field of view. Second, the external light sources, such as public lighting or other vehicles' lights, generate a halo effect. Moreover, the backscattered veil becomes invisible when external light sources illuminate the scene, which is due to automatic camera settings and the reduced dynamic range of the camera. Two detection algorithms were presented in the previous section. The first algorithm aims at detecting the presence of a backscattered veil. The second algorithm aims at detecting the presence of halos around artificial light sources in the environment. Their combination is achieved by running them alternatively. Halo detection is run first. It starts with the detection of light sources in the field of view. If at least one source is detected, the halo detection algorithm carries on to evaluate the presence of fog based on the shape of the halo around the source(s). If no source is detected, the halo detection algorithm is interrupted, and a signal is sent to the backscattered veil detection algorithm. Without any external light source in the environment, the veil is detectable, and the correlation with reference images is relevant for evaluating the fog presence. Fig. 9 presents a scheme that summarizes this approach.

D. Fog Characterization Through Backscattered Veil

Both the halo and backscattered veil detection algorithms may be used to characterize the fog density and to estimate the meteorological visibility. Since the halos around light sources depend on the distance from the camera (which is unknown) and on the type and density of fog, Br 50 does not suffice to accurately characterize fog and, thus, to estimate the meteorological visibility: It is an ill-posed problem. On the other hand, the algorithm to detect fog through the backscattered veil is based on the comparison between the current camera image and a set of reference images, which were produced under different fog densities. The correlation score serves to evaluate the fog presence. We propose to implement it to characterize the fog density. The initial fog characterization comes from the reference image with the strongest correlation score. The fog density corresponding to this reference image gives a first approximation of the actual fog density. However, this characterization is quite unstable, particularly when the density is between two reference images. It does not take into account all available information. When using several reference images, we get several comparison scores with the initial image. Combining all the scores produces a more accurate estimate of the observed fog density. For the combination, we fit the curve of the correlation score S c versus meteorological visibility distance V met with the following function:

S c = e aV 2 met +bV met +c (13)
where a, b, and c are the fitting parameters. Relying on the previous equation, it is possible to estimate the current visibility distance using

Ṽmet = -b 2a . ( 14
)
Since ( 14) does not depend on the c fitting parameter, the proposed method allows detecting and characterizing the fog density without any hard threshold on the ZNCC score. Indeed, the ZNCC score depends on the type of input image and reference image; thus, we consider its variation instead of its actual value.

IV. EXPERIMENTAL EVALUATION

A. Materials

Weather centers are unable to forecast fog presence, which makes it very difficult to obtain experimental data. Nevertheless, different kinds of materials have been progressively collected between 2008 and 2012 to assess the performance of the presented methods. For qualitative evaluation, different short videos were acquired with an experimental vehicle in the area of Versailles (France) during successive winters; in one of these videos, a prototype LIDAR was used to provide a rough estimate of the meteorological visibility distance. For quantitative evaluation, two video sequences were produced in the fog chamber of Clermont-Ferrand (France), which is equipped with reference transmissometers [START_REF] Colomb | An innovative artificial fog production device improved in the European project FOG[END_REF]; however, due to fog inhomogeneity inside the chamber, these measurements cannot be considered absolute ground truth data. The whole process from fog detection to fog characterization is performed in real time using a video of resolution 1280 × 800 at 10 frames/s. The hardware used for the experiments is an Intel Core i7 at 3 GHz. The program runs on the Intempora RT-Maps platform and is compiled with the Microsoft Visual C++ 2005 framework.

B. Night-Fog Detection

First, we illustrate the results obtained using the halo detection algorithm. We remind that a value Br 50 lower than 9 corresponds to the presence of fog. To assess the ability of the halo detection algorithm to detect foggy weather, four video sequences were produced using an embedded camera on the same location at night, i.e., two of them during clear nights and the other two during foggy nights. They present 2130 images that contain an average of ten light sources per image. Fig. 8 illustrates the source and halo detection process on two images extracted from the database. Considering each frame independently, the proposed algorithm produced a fog detection rate of 98.4%. By producing a sliding average of the characteristic of the halo profile on 1 s of video (25 images), the fog detection rate reached 99.86%. In Fig. 10, the halo detection algorithm is further illustrated on other different driving scenarios. In the top-left image, a single source is detected. The propagation direction, which is plotted in green, corresponds to the direction of the halo. A value smaller than 9 indicates the presence of fog. Notice that the road sign, which could have been detected as a source, is discarded due to the source filtering process. In the top-right image, the detection of multiple sources is illustrated. The propagation directions are different for each source, but the Br 50 values are close (3.57, 3.91, and 4.05). In the bottomleft image, the headlamps of an oncoming vehicle are detected. The lane separation disturbs the detection, but the Br 50 value is stable enough and is relevant to confirm the presence of fog whenever detection is possible. In the bottom-right image, no external light source is detected, but the backscattered veil is strongly present. To illustrate the halo detection algorithm, a video of the same street with and without fog is attached in this paper.

To validate the backscattered veil algorithm, we have used a recorded video in the Clermont-Ferrand (France) fog chamber. Sample results are given in Fig. 11. A high correlation score (greater than 0.6) is obtained when the measured and reference images correspond to dense fog (see Table I). In the presence of fog, this score becomes smaller (around 0.4). In the presence of light fog, it becomes very small (less than 0.2). Consequently, the confidence in fog detection based on the backscattered veil increased with the fog density. In Fig. 12, the results of the backscattered veil algorithm are presented on openroad fog images. The signal-to-noise ratio is strongly increased by averaging successive frames. The highest correlation score corresponds to the reference image having a visibility of 500 m, which is quite consistent with the output of the dedicated LIDAR of 368 m. However, using all correlation scores will improve the fog characterization.

C. Night-Fog Characterization

To validate the night-fog characterization process, we have used a video from the Clermont-Ferrand (France) fog chamber [START_REF] Colomb | An innovative artificial fog production device improved in the European project FOG[END_REF]. First, we have selected six frames as reference images; they correspond to the following measured visibility distances: 12.6, 51.4, 91.8, 167.8, 415.6, and 2000 m. Then, we have computed the correlation of the 50 frames sampled from the video with the six reference frames; for each of these test frames, we have used the six correlation scores to fit the curve based on (13), and we have used that curve to estimate the meteorological visibility distance. The results for three test frames are presented in Fig. 13 with the fitted curve in green. For comparison purposes, we have also computed the correlation scores of these three test frames with the other 50 frames sampled from the video; the resulting curves are plotted in blue in Fig. 13. The similarity between both curves is satisfactory, meaning that the choice of the model and of the six reference frames to fit the curve is adapted to the problem while limiting the computing load. Moreover, as shown in the title of each graph in Fig. 13, the estimated visibility is rather close to the reference visibility. Finally, the estimated visibility distance is Notice that this method is clearly better than choosing the best correlation score to infer the visibility distance. However, the accuracy is not high enough to be used directly. Nevertheless, according to these results, the designed process meets the requirements expressed in Section II-E and is able to classify the fog density in the proposed categories.

V. CONCLUSION AND PERSPECTIVES

In this paper, the problem of night visibility in the presence of fog has been tackled. An original approach allows us to propose a standard night visibility index inspired by literature on public lighting. Based on this index, three classes of fog density directly related to user needs are presented, two of which concern the safety of drivers and should be required in the safety systems that will equip vehicles in the future. To this aim, we propose a methodology to detect the presence of night fog and to estimate the resulting meteorological visibility distance. The detection is carried out by detecting the presence of a backscattered veil or halos around external light sources. The characterization is obtained by fitting an empirical model with the correlation scores computed between the current image and the reference images with known meteorological visibility distance. The experimental results, which are both qualitative and quantitative, demonstrate the capacity of the proposed method to meet the proposed requirements in terms of accuracy. In the future, night-fog characterization will be done using halo characteristics. In this aim, we plan to collect a larger database of fog images with the associated meteorological visibility. The proposed methodology has been patented [START_REF] Gallen | Method and device for detecting fog at night[END_REF] and will potentially allow the development of different applications. First, it enables novel intelligent speed adaptation strategies, which are able to take into account a reduction of the visibility distance, e.g., see [START_REF] Gallen | Supporting drivers in keeping safe speed in adverse weather conditions by mitigating the risk level[END_REF]. Second, it allows developing new adaptation strategies for vehicle front-lighting and signaling systems [START_REF] Gallen | A conventional approach to nighttime visibility in adverse weather conditions[END_REF]. Finally, such a method may be used to detect and characterize fog from a fixed roadway camera [START_REF] Hautière | Meteorological conditions processing for vision-based traffic monitoring[END_REF].

Fig. 1 .

 1 Fig. 1. Different effects of fog on light propagation in a driving scene.

Fig. 2 .

 2 Fig. 2. Headlight backscattered veil luminance as a function of the meteorological visibility distance for two types of fog (radiation and advection).

Fig. 3 .

 3 Fig. 3. Backscattered veil. (a) Actual image grabbed in the Clermont-Ferrand fog chamber [33]. (b) Simulated image using semi-Monte Carlo ray-tracing software [31].III. DETECTION OF FOG AND ESTIMATION OF METEOROLOGICAL VISIBILITY INDEXBased on two visual effects of night fog, a system composed of two detection algorithms has been developed. The first algorithm detects the presence of a backscattered veil. The second algorithm detects the presence of halos around artificial light sources in the environment.

Fig. 4 .

 4 Fig. 4. Database of simulated images with different meteorological visibility distances. Color scale goes from blue to red in order to bring out luminance variations. From these luminance maps, a mask matching the shape of the backscattered veil is extracted.

Fig. 5 .

 5 Fig. 5. Video sequence grabbed in actual fog during a test drive. (a) Sample frame. (b) Mean of successive frames. The objects in the scene are suppressed, whereas the backscattered veil remains due to its temporal stability.

Fig. 6 .

 6 Fig. 6. Detection of light sources and associated halos. (Left) Original image. (Middle) Segmented images with decreasing thresholds and associated connected components. (Right) Tree of potential sources built using the segmented images.

Fig. 7 .

 7 Fig. 7. Intensity profile across the halo of a directional light source. The successive positions of the CoG (in red) and the linear regression in the direction of lighting (in green) and in the opposite direction (in purple).compared in order to select the most relevant characteristic for distinguishing between the presence and absence of fog. As illustrated in Fig.7, the following curve characteristic is chosen: Br 50 = H 50 /W r 50 , with H 50 as half the height of the decrease, and W r 50 as the width between the end of the sensor saturation and the curve point corresponding to the half of the height. Br 50 decreases in the presence of fog. f) Br 50 combination. Each frame of a video sequence contains several potential light sources. For each frame, the Br 50 characteristics of the different halos are averaged to compute their mean value Br 50 .

Fig. 8 .

 8 Fig. 8. Illustration of source halos' detection. (Left) Without fog. (Right) With fog. Expanding blue boxes represent the bounding boxes of the connected components at each step.

Fig. 9 .

 9 Fig. 9. Scheme of the method for combining both algorithms. The light source detection algorithm triggers the halo detection algorithm and, ultimately, the backscattered veil detection algorithm.

Fig. 10 .

 10 Fig. 10. Illustration of the results obtained using the halo detection algorithm. In each image, the value of the Br 50 criterion averaged over 50 sources is presented in red in the top-left corner. A value smaller than 9 corresponds to the presence of fog. For each detected source, the halo direction is plotted in green, the Br 50 criterion is written in pink, and the intensity profile is plotted in violet. (a) Br 50 = 4.473. (b) Br 50 = 3.889. (c) Br 50 = 6.859. (d) Br 50 = 5.599.

Fig. 11 .

 11 Fig. 11. ZNCC correlation score of different reference images with fog images grabbed as fog dissipates in the Clermont-Ferrand fog chamber.

Fig. 12 .

 12 Fig. 12. Illustration of results obtained using the backscattered veil detection algorithm. (Top left) Current image. (Top right) Mean of successive images (the background image). (Bottom) Value of the ZNCC correlation scores between the background image and the six simulated reference images (15, 50, 100, 200, 500 m, and ∞). The meteorological visibility distance measured by the dedicated LIDAR is 368 m.

Fig. 13 .

 13 Fig. 13. Correlation scores versus the visibility distance for three different frames (a), (b), and (c) of the video acquired in the fog chamber of Clermont-Ferrand. The plot of the correlation score between each test frame and the 50 other frames is in blue. The fitting of the curve only using six points of the curve (reference frames) is in green.

Fig. 14 .

 14 Fig. 14. Measured and estimated visibility distances obtained on a video sequence acquired in the fog chamber of Clermont-Ferrand. (a) Curve for the whole range of meteorological distances. (b) Zoom of the red square for the low meteorological visibility distances. presented in Fig. 14 as a function of the reference visibility distance for each frame sampled from the video. The accuracy of the estimation is as follows: • about 10 m of accuracy when V met < 50 m; • about 20 m of accuracy when V met < 100 m; • about 40 m of accuracy when V met < 200 m; • Less than 100 m of accuracy when V met > 200 m.Notice that this method is clearly better than choosing the best correlation score to infer the visibility distance. However, the accuracy is not high enough to be used directly. Nevertheless, according to these results, the designed process meets the requirements expressed in Section II-E and is able to classify the fog density in the proposed categories.

TABLE I CLASSES

 I OF FOG THAT NEED TO BE DETECTED BY THE DESIGNED IN-VEHICLE CAMERA SYSTEM

This work was supported in part by Agence Nationale de la Recherche through the Dialogue Infrastructure Véhicules pour Améliorer la Sécurité Project and the Improved CAmera based Detection under Adverse Conditions (ICADAC) Project under Grant 6866C0210 projects. R. Gallen is with the Information Processing Unit, Direction technique Eau, mer et fleuves (DTecEMF), Centre d'Etudes et d'Expertises (CEREMA), 29280

Aurélien Cord received the Ph.D. degree in image processing for planetary surfaces from Toulouse University, Toulouse, France, in 2003.

In