Gui-Song Xia
email: xia@enst.fr

Julie Delon
email: delon@enst.fr

Yann Gousseau
email: gousseau@enst.fr

Accurate Junction Detection and Characterization in Natural Images

Keywords: Junction detection, scale characterization, a-contrario method, contrast invariance

Accurate junction detection and characterization are of primary importance for several aspects of scene analysis, including depth recovery and motion analysis. In this work, we introduce a generic junction analysis scheme. The first asset of the proposed procedure is an automatic criterion for the detection of junctions, permitting to deal with textured parts in which no detection is expected. Second, the method yields a characterization of L-, Y-and X-junctions, including a precise computation of their type, localization and scale. Contrary to classical approaches, scale characterization does not rely on the linear scale-space, therefore enabling geometric accuracy. First, an a contrario approach is used to compute the meaningfulness of a junction. This approach relies on a statistical modeling of suitably normalized gray level gradients. Then, exclusion principles between junctions permit their precise characterization. We give implementation details for this procedure and evaluate its efficiency through various experiments.

Introduction

Junctions are of primary importance for visual perception and scene understanding. They are parts of the well known primal sketch, the schematic representation of images introduced by D. Marr [START_REF] Marr | Vision. A Computational Investigation into the Human Representation and Processing of Visual Information[END_REF]. Recent approaches to the computational computation of this sketch, as proposed by [START_REF] Guo | Primal sketch: Integrating structure and texture[END_REF], show the key role played by junctions. Depending on the number of edges they connect, junctions are often classified into L-, Y-(or T-) and X-junctions. In particular, the role of T-junctions as cues for the perception of occlusions has been thoroughly studied by G. Kanisza [START_REF] Kanizsa | Organization in vision : essays on gestalt perception[END_REF]. Later, it has been shown in [START_REF] Rubin | The role of junctions in surface completion and contour matching[END_REF] that junctions are essential local cues to initiate contour completion and that their specific configuration (e.g. T-or Y-junction) has to be taken into account in this process. The distinct roles of L-and T-junctions for the perception of motion, in particular through the aperture phenomenon, has been known for long [START_REF] Wallach | Ueber visuell whargenommene bewegungrichtung[END_REF]. Junction types and positions are also shown to have a strong impact on the perception of brightness and transparency, as investigated in [START_REF] Metelli | The perception of transparency[END_REF][START_REF] Adelson | Lightness perception and lightness illusions[END_REF].

Junctions are therefore naturally used as important cues for various computer vision tasks. Since they reveal important occlusion relationships between objects, they are involved in figure/ground separation [START_REF] Geiger | Visual organization for figure/ground separation[END_REF][START_REF] Ren | Figure/ground assignment in natural images[END_REF][START_REF] Leichter | Boundary ownership by lifting to 2.1d[END_REF][START_REF] Dimiccoli | Exploiting t-junctions for depth segregation in single images[END_REF]. Junctions are also used for grouping edges and regions to achieve image segmentations [START_REF] Fuchs | Polymorphic grouping for image segmentation[END_REF][START_REF] Lindeberg | Segmentation and classification of edges using minimum description length approximation and complementary junction cues[END_REF][START_REF] Ishikawa | Segmentation by grouping junctions[END_REF]. The role of junction for object recognition has been studied since the early works on automatic scene analysis, see [START_REF] Guzmán | Decomposition of a visual scene into three-dimensional bodies[END_REF][START_REF] Bolles | Recognizing and locating partially visible objects: The localfeature-focus method[END_REF][START_REF] Lin | An empirical study of object category recognition: sequential testing with generalized samples[END_REF].

In the present work, we propose a principled and automatic method for the detection, localization and characterization of junctions. We define junctions as local or semi-local structures at the center of which at least two dominant and different edge directions meet. Junctions are defined locally, and not for instance as a by-product of a global image segmentation, mostly to achieve precise description of the junction. Following observations from psychophysics [START_REF] Mcdermott | Psychophysics with junctions in real images[END_REF], we nevertheless consider large regions for the assessment of a junction. This is made possible by an automatic scale selection rule. It should be noticed that not all perceived junctions enter this framework, and that some of them are only detected while performing scene analysis [START_REF] Mcdermott | Psychophysics with junctions in real images[END_REF]. Nevertheless, as advocated above, we believe that a precise and accurate description of junction makes them valuable information in view of a more global scene analysis.

More precisely, we take interest in a junction detection method meeting several requirements. First, junctions have to be clearly related to the geometry of the image. In particular, the description of the junction branches should be accurate. This is in strong contrast with the classical corner detectors such as Harris, that are commonly used a keypoint detectors. Second, an automatic validation rule will be derived. For this, we rely on the a contrario methodology [START_REF] Desolneux | Meaningful alignments[END_REF], in which structures are validated by controlling the number of false detections. A key advantage of this approach is the automatic setting of detection parameters in a way that will prevent the numerous junctions that are usually detected in textured areas. Third, the position and scale of the junctions should be detected precisely and be closely related to the image geometry. This will be achieved thanks to a competition between junctions relying on a sound quality measure, the number of false alarms associated with a junction.

Related works

Corner detectors Automatic junction detection has been a very active research field over the last four decades. One of the earliest methods was introduced by [START_REF] Moravec | Towards automatic visual obstacle avoidance[END_REF], considering corners as points which are not self-similar in an image. The similarity of two points is measured by using the sum of squared differences (SSD) between their associated image patches. Harris and Stephens [START_REF] Harris | A combined corner and edge detection[END_REF] then proposed to approximate the SSD by the autocorrelation in a patch. The resulted cornerness measure is isotropic and has an analytic expansion, called the Harris matrix, and is widely used in practice. A large number of detectors rely on this idea, the detection of corners boiling down to the analysis of the eigenvalues of this matrix, see e.g. [START_REF] Forstner | A feature based correspondence algorithm for image matching[END_REF][START_REF] Shi | Good features to track[END_REF][START_REF] Kovesi | Phase congruency detects corners and edges[END_REF][START_REF] Kenney | An axiomatic approach to corner detection[END_REF]. In particular, in order to achieve contrast invariance, Kovesi [START_REF] Kovesi | Phase congruency detects corners and edges[END_REF] uses phase congruency to derive cornerness measurement. In this work, the image gradient is normalized over small wedges. Alternative measurements of self-similarity have also been proposed, such as the univalue segment assimilating nucleus (USAN) [START_REF] Smith | SUSAN: A new approach to low level image processing[END_REF] and its variants [START_REF] Trajkovic | Fast corner detection[END_REF][START_REF] Rosten | Fusing points and lines for high performance tracking[END_REF][START_REF] Rosten | Faster and better: A machine learning approach to corner detection[END_REF]. Observe that such methods relying on a measure of cornerness actually do not distinguish between different types of junctions. They are therefore usually used to compute generic interest points but their use as local cues for occlusion analysis or figure/ground separation is less clear. Also observe that in order to identify the characteristic scale of a corner, corner detectors usually make use of the linear scale-space [START_REF] Deriche | A computational approach for corner and vertex detection[END_REF][START_REF] Lindeberg | Junction detection with automatic selection of detection scales and localization scales[END_REF][START_REF] Schmid | Evaluation of interest point detectors[END_REF][START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF][START_REF] Mikolajczyk | Scale and affine invariant interest point detectors[END_REF]. One of the main shortcomings of such approaches is that they quickly lose precision both in localization and scale. An alternative approach is to rely on some contrast invariant multi-scale analysis. In this direction, Alvarez et. al. [START_REF] Alvarez | Affine morphological multiscale analysis of corners and multiple junctions[END_REF] analyze junctions in images using an affine morphological scale space.

Boundary based methods A second popular and efficient way to detect corners relies on explicit boundaries in images. Corners are interpreted as points in the image where a boundary changes direction rapidly and points with high curvature are selected. Many works have concentrated on different and efficient ways to compute the curvature of curves for detecting corners, see [START_REF] Rosenfeld | Angle detection on digital curves[END_REF][START_REF] Teh | On the detection of dominant points on digital curves[END_REF][START_REF] Rattarangsi | Scale-based detection of corners of planar curves[END_REF][START_REF] Wang | Real-time corner detection algorithm for motion estimation[END_REF][START_REF] Mokhtarian | Robust image corner detection through curvature scale space[END_REF][START_REF] Mohammad | An improved curvature scale-space corner detector and a robust corner matching approach for transformed image identification[END_REF]. In a different way, it has been proposed in [START_REF] Beymer | Finding junctions using the image gradient[END_REF] to detect junctions by extending disconnected edges and by filling gaps at junctions. Junction detection can also rely on the grouping of edges in the neighborhood of a candidate junction [START_REF] Freeman | Steerable filters and local analysis of image structure[END_REF][START_REF] Rohr | Recognizing corners by fitting parametric models[END_REF][START_REF] Perona | Steerable-scalable kernels for edge detection and junction analysis[END_REF]. Several works have proposed to rely on the contrast invariant level lines of images to detect junctions. Caselles et. al. [START_REF] Caselles | Junction detection and filtering: A morphological approach[END_REF] have proposed a method based on a level-set representation, detecting junctions as points where two level lines meet. Cao [START_REF] Cao | Good continuations in digital image level lines[END_REF] detects corners as breaking points under a good continuation criterion on image level lines. Corners are detected as points where the curvature along a level line is abnormally high, in an a contrario framework. In other approaches, a global segmentation of the image is first performed, followed by a heuristic grouping of edges to form junctions [START_REF] Wu | Compositional boosting for computing hierarchical image structures[END_REF][START_REF] Maire | Using contours to detect and localize junctions in natural images[END_REF]. It should there be emphasized that the segmentation process in itself is a very challenging task. For instance, before detecting junctions, Maire et. al. [START_REF] Maire | Using contours to detect and localize junctions in natural images[END_REF] finds contours by the global probability of boundary (gPb) detector learned from a human-annotated database. Such approaches permit to benefit from global image interpretation to find junctions. On the other hand, boundary are often imprecise in the neighborhood of a junction, so that such approaches do not enable an accurate characterization of junctions, that in turn can be used to refine edges.

Template-based methods Among existing approaches, the model-based or template-based ones are the most suitable for accurate local junction detection. In [START_REF] Deriche | Recovering and characterizing image features using an efficient model based approach[END_REF], Deriche and Blaszka present computational approaches for a model-based detection of junctions. A junction model is a 2D intensity function depending on several parameters. Starting from a poorly localized initialization (e.g. from the Harris detector) parameters are then optimized in view of a precise localization. Parida et al. [START_REF] Parida | Junctions: Detection, classification, and reconstruction[END_REF] suggest a region-based model for simultaneously detecting, classifying and reconstructing junctions. A junction is defined as an image region containing piecewise constant wedges meeting at the central point. This work relies on a template deformation framework and uses minimum description length principle and dynamic programming to obtain the optimal parameters describing the model. This work also involves junction candidates provided by a preliminary corner detector. Ruzon and Tomasi [START_REF] Ruzon | Edge, junction, and corner detection using color distributions[END_REF] model junctions as points in images where two or more image regions meet. Regions are described by their color distributions, which allows textured objects with the same mean color to be distinguished. Following the model of Parida, Cazorla and Escolano [START_REF] Cazorla | Two Bayesian methods for junction classification[END_REF][START_REF] Cazorla | Junction detection and grouping with probabilistic edge models and Bayesian A*[END_REF] propose both a region-based and an edge-based model for junction classification by using Bayesian methods. The region-based one formalizes junction detection as a radial image segmentation problem under region competition framework and the edge-based one detects junctions as radial edges minimizing some Bayesian classification error. In this work, the edge-based approach is shown to yields more accurate junction detection, but at the price of a large number of false detections, especially in textured regions. More recently, the work of Sinzinger [START_REF] Sinzinger | A model-based approach to junction detection using radial energy[END_REF] first detects a set of junction candidates by using a preliminary detector (for instance the Harris detector) and then refines those candidates by relying on a radial edge energy.

Method

Cornerness-based Contour-based Template-based our approach (template-based) Some representative works [START_REF] Harris | A combined corner and edge detection[END_REF][START_REF] Lindeberg | Junction detection with automatic selection of detection scales and localization scales[END_REF][START_REF] Smith | SUSAN: A new approach to low level image processing[END_REF][START_REF] Trajkovic | Fast corner detection[END_REF][START_REF] Mikolajczyk | Scale and affine invariant interest point detectors[END_REF][START_REF] Rosten | Faster and better: A machine learning approach to corner detection[END_REF][START_REF] Kovesi | Phase congruency detects corners and edges[END_REF] [ [START_REF] Rohr | Recognizing corners by fitting parametric models[END_REF][START_REF] Caselles | Junction detection and filtering: A morphological approach[END_REF][START_REF] Wu | Compositional boosting for computing hierarchical image structures[END_REF][START_REF] Maire | Using contours to detect and localize junctions in natural images[END_REF][START_REF] Mohammad | An improved curvature scale-space corner detector and a robust corner matching approach for transformed image identification[END_REF] [50, 51, 53, 55] --

Junction detection cues

Cornerness measurements, such as Harris matrix.

Edge map

Gradients or piecewise region consistence Amplitudes and phases of gradients Scale of junctions Possibility of scale detection relying on the linear scale space ( [START_REF] Lindeberg | Junction detection with automatic selection of detection scales and localization scales[END_REF][START_REF] Mikolajczyk | Scale and affine invariant interest point detectors[END_REF]).

No scale definition.

Junctions are detected at a given scale (except : scale selection by MDL in [START_REF] Parida | Junctions: Detection, classification, and reconstruction[END_REF]) The different approaches for junction detection, as well as their properties, are summarized in Table 1.

Contributions and outline

As explained earlier in the introduction, the goal of this paper is to design a junction detection procedure involving an automatic decision step and permitting a geometrically accurate description of junction properties, including type, localization and scale. This is made possible thanks to the use of an a contrario methodology [START_REF] Desolneux | Meaningful alignments[END_REF]. The resulting detection method will be coined ACJ (for a contrario junction detection). In short, we first define (in Section 2) junctions as geometrical structures in discrete images and we associate to each candidate junction a quantity called strength, which is designed to be high at locations where several edges (called branches) meet in the image. This strength relies on a well chosen normalization of the gradient, which makes the whole approach robust to local contrast changes. We then rely in Section 3 on a statistical framework in order to decide automatically which junctions deserve to be detected or not in a given image. More precisely, meaningful junctions are detected as those which could not occur by chance under some null hypothesis H 0 . This detection step is followed by several exclusion criteria, designed to rule out redundant junctions and to identify precisely the correct scales, positions and complexities (number of branches) of junctions. As a by-product of the scale estimation, the whole approach is robust to resolution changes. Finally, in Section 4, details about implementation and parameter settings are provided. Section 5 analyzes the proposed algorithm experimentally.

Contrast Invariant Junctions

The aim of this section is to define junctions in discrete images (Section 2.2) and to associate to each candidate junction a strength (Section 2.3). The strength of a junction is defined through both the gradient orientation and magnitude. Robustness to local contrast changes is achieved by normalizing the gradient magnitude, as explained in Section 2.1. The strength of junctions will be used in Section 3 to decide whether junctions are meaningful or not in a given image.

Gradient normalization

Let us start with some definitions and vocabulary that will be used throughout the paper. A discrete image is a function I : Ω → R, where Ω is a rectangular subset of Z×Z. We write ∇I = (I x , I y ) for the discrete gradient of the image I. For a pixel q in Ω, we define φ(q) = (arctan Iy(q) Ix(q) + π/2)modulo(2π), the direction perpendicular to the gradient at q (and set φ(q) = π when I x (q) = 0). We call this angle the direction of the pixel q.

In order to be robust to local contrast changes, we locally normalize the gradient magnitude by dividing it by its average on a small neighborhood. That is, for q = (x, y), we define ∇I = ( I x , I y ) as

I x (q) = I x (q) I 2 x + I 2
y Nq and I y (q) = I y (q)

I 2 x + I 2 y Nq , (1)
where N q is a small neighborhood around q and . Nq is the average operator on N q . The resulting gradient is robust to contrast changes that can be approximated by affine transformations on each neighborhood N q . An example of the gradient and normalized gradient of an image, obtained with a square neighborhood of size 5 × 5 around each pixel, is shown in Figure 1. Observe that the phase of the normalized gradient is the same as the phase of the plain gradient.

In Section 3, we will rely on the empirical distribution of the gradient to detect meaningful junctions. More precisely, we will consider the globally normalized gradient

I x = I x -µ x σ x and I y = I y -µ y σ y , (2)
where µ x (resp. µ y ) and σ x (resp. σ y ) are the empirical mean and standard deviation of I x (resp. I y

) over the whole image. The norm ∇I = I x 2 + I y 2 will be used in the following paragraphs to define the strength of a junction. As we will see, the distribution of this norm in natural images is well approximated by a standard Rayleigh distribution.

Discrete junction definition

A junction is defined as a discrete image structure  : p, r, {θ m } M m=1 , characterized by its center p, its scale r ∈ N and a set of branch directions {θ 1 , . . . θ M } around p. The number M of branches

D(r) := 2πk K(r) ; k ∈ {1, . . . K(r)} , (3)
where K(r) is the number of possible discrete directions permitting a one pixel precision, that is

K(r) = ⌊2πr⌋.
For a given scale r and a given direction θ in D(r), we define the branch of direction θ at p as the disk sector S p (r, θ) := q ∈ Ω; q = p, -→ pq ≤ r,

d 2π (α( -→ pq), θ) ≤ ∆(r) , (4)
where ∆(r) is a precision parameter, α( -→ pq) is the angle of the vector -→ pq in [0, 2π] and where d 2π is the distance along the unit circle, defined as d 2π (α, β) = min(|α -β|, 2π -|α -β|). We note J(r, θ) the number of pixels in a sector of direction θ at scale r. This size depends on the scale r but also slightly changes with the direction θ since the image is defined on a discrete grid.

Finally, we require that two branches of a given junction do not intersect. It follows that the angle between two directions in a junction  must be larger than 2∆(r). As a consequence, the number of possible directions in a junction at scale r is smaller than π ∆(r) . An example of a junction with three branches is shown on Figure 2.

Junction strength

The strength of a junction will be defined from the strength of its branches. The strength of a branch is a measure of how well the corresponding angular sector agrees with the pixels it contains. A pixel q contributes all the more to the strength as its direction φ(q) is in agreement with the direction α( -→ pq) and as the normalized gradient ∇I(q) is large. Precisely, the strength of a branch is defined as Definition 1 (Strength of a branch) Let p be a pixel, r a positive scale and θ a direction in D(r). The strength of the branch S p (r, θ) is defined as the quantity

ω p (r, θ) = q∈Sp(r,θ) γ p (q), (5)
Figure 2: A junction with three branches. Each branch is represented by a disk sector S p (r, θ) with an angular aperture of 2∆(r).

where

γ p (q) = ∇I(q) • max | cos(φ(q) -α( -→ pq)|- | sin(φ(q) -α( -→ pq))|, 0 . (6)
The max operator has been chosen so that the contribution of the pixel is equal to zero if the difference between α and φ is larger than π/4. Other choices could be made. The larger the strength of a branch, the more likely it is that the branch corresponds to an edge. Figure 3 (c) shows the values of γ p (q) for the image patch shown in Figure 3 (a).

The strength of a junction is then derived from the strength of its branches as follows:

Definition 2 (Strength of a junction) The strength of a junction  : p, r, {θ m } M m=1 is defined as t() := min m=1...M ω p (r, θ m ). (7)
Starting from this definition, a first naive algorithm for junction detection can be developed. The idea is to detect, for a fixed scale r and a given threshold t, all the junctions in I having a strength greater than t. In practice, testing all possible junctions for every point p in Ω is computationally heavy. Among all the potential branches at a given point p, we restrict ourselves to the directions θ in the discrete set D(r) where the periodic function ω p (r, .) reaches a local maximum. Moreover, in order for branches not to intersect, we impose that the local maximality holds over a length 2∆(r), that is ω p (r, θ) is greater than ω p (r, θ ′ ) for θ -∆(r) ≤ θ ′ ≤ θ + ∆(r). The set of these local maxima can be computed quickly, for instance by using a non-maximum suppression (NMS) procedure (see [START_REF] Kitchen | Non-maximum suppression of gradient magnitudes makes them easier to threshold[END_REF][START_REF] Neubeck | Efficient non-maximum suppression[END_REF]). In practice, if two local maxima are equal and located at a distance smaller than ∆(r), one of them is discarded.

The case of L-junctions In order not to detect all edge points as L-junctions, junctions for which M = 2 and whose branches are opposite (that is, with two directions θ 1 and θ 2 such that

d 2π (θ 1 , θ 2 + π) ≤ 2∆(r)) are discarded.
The overall detection procedure is summarized in Algorithm 1.

Algorithm 1 Junction detection in an image I at a given scale r. Input: A discrete image I, an order M , a positive scale r, a number K of discrete directions, a precision ∆ and a threshold t.

1: compute ∇I at each pixel using Equation (1);

2: set D = 2πk K ; k = 1, . . . K 3: for each pixel p do 4:
(1) compute ω p (r, θ) for each θ in D, using Equations ( 5) and ( 6); (2) use a NMS procedure to only keep directions θ such that ω p (r, θ) is locally maximum on [θ -∆, θ + ∆]; call Θ the set of these directions; 6:

(3) find all the subsets Θ ′ of size M in Θ such that min θ∈Θ ′ ω p (r, θ) ≥ t ; for each of these subsets, mark The first parts of the procedure are illustrated in Figure 3. In this example, the pixel p is chosen as the center of Figure 3 (a). Figure 3 (d) shows in blue the values of ω p (r, θ) when the angle θ spans the periodic set D(r) and shows in red the semi-local maxima kept after the NMS procedure (step (2) of the loop in Algorithm 1). Figures 3 (e) represent respectively a candidate L-junction, a candidate Y -junction and a candidate X-junction at p.

 : p, r, Θ ′ as a junction if M = 2, or if M = 2 and Θ ′ = {θ 1 , θ 2 } with d 2π (θ 1 , θ 2 + π) ≤ 2∆.
The main drawback of this detection algorithm is that the threshold t on the junction strength remains the same whatever the junction scale and order and whatever the image size. Setting such a threshold globally is not easy and can lead to over-detect at some scales and under-detect at others. The goal of the next section is to provide detection thresholds that adapt to the junction scale and order, as well as to the image size. For this purpose, we resort to an a contrario methodology.

An a contrario Approach for Junction Detection

The a contrario detection theory has been primarily proposed by Desolneux et. al. [START_REF] Desolneux | Meaningful alignments[END_REF]. This methodology is inspired by geometric grouping laws governing low-level human vision, known as Gestalt laws [START_REF] Kanizsa | Organization in vision : essays on gestalt perception[END_REF], and states that meaningful structures in images are structures which are very unlikely under some hypothesis of randomness. The method has been extensively tested and successfully applied to various problems in image processing and computer vision, see e.g. [START_REF] Cao | Good continuations in digital image level lines[END_REF][START_REF] Moisan | A probabilistic criterion to detect rigid point matches between two images and estimate the fundamental matrix[END_REF][START_REF] Musé | An a contrario decision method for shape element recognition[END_REF][START_REF] Gioi | LSD: A fast line segment detector with a false detection control[END_REF]. A complete overview of these methods can be found in [START_REF] Desolneux | From Gestalt Theory to Image Analysis: A Probabilistic Approach[END_REF]. In this section, this methodology is adapted to the detection of meaningful junctions in images.

Null hypothesis

The goal of the following sections is to set detection thresholds on junction strengths in such a way that no junction will be detected in a "generic random image". Let us precise what "generic random image" stands for here. Let I be a random image. For each pixel q, we write ∇I(q) and φ I (q) the random variables corresponding to the value and orientation at this pixel. We say that these variables follow the null hypothesis H 0 if 1. ∀q ∈ Ω, ∇I(q) follows a Rayleigh distribution with parameter 1 ; 2. ∀q ∈ Ω, φ I (q) is uniformly distributed over [0, 2π] ; 3. the family { ∇I(q) , φ I (q)} q∈Ω is made of independent random variables.

Let us comment on the first assumption. In [START_REF] Ruderman | Statistics of natural images: Scaling in the woods[END_REF], Ruderman et al. observe that if we normalize the logarithm of an image intensity by its local mean and standard deviation in a neighborhood N p around each pixel, "the histogram of pixel values has Gaussian tails, and the distribution of gradients in the'variance-normalized' image is almost exactly the Rayleigh distribution". This result can be extended to our modified derivatives I x and I y : except on a small neighborhood around 0, their distribution is well approximated by a Gaussian distribution. This is illustrated for a particular image I in Figure 4. In this Figure, the empirical distributions of I x and I y are drawn in blue, and the best Gaussian fits are drawn in red. If we except a peak around 0, the fit is excellent. This approximation is of particular interest for junction detection since the gradients around a junction usually take large values. Observe that this Gaussian approximation is not valid for the classical gradient (I x , I y ), whose distribution is quite heavy tailed. It follows that the distributions of I x and I x are usually well approximated by the standard normal distribution (that is, a Gaussian distribution with zero mean and unit variance) and the norm ∇I in natural images approximately follows a central chidistribution with 2 degrees of freedom (also known as the Rayleigh distribution of parameter 1). This is confirmed experimentally by the example shown in

Distribution of t() under H 0

Let  : p, r, {θ m } M m=1 be a junction in I and assume that the normalized gradients and directions of I follow the null hypothesis H 0 . Then the strengths ω p (r, θ m ) of the different branches S p (r, θ m ) are independent random variables (since branches do not intersect). Recall also that the strength of a junction is the minimum of the strengths of its branches. Thus, if we note t() the random variable measuring the strength of , Now, the strength of each branch, ω p (r, θ m ), is itself a sum (over the angular sector S p (r, θ m )) of i.i.d. random variables γ p (q). For two given points p and q in Ω, the direction α( -→ pq) is a constant in [0, 2π]. This implies that under the hypothesis H 0 , the random angle φ I (q)α( -→ pq) is still uniformly distributed on [0, 2π]. As a consequence, each γ p (q) can be written as a product X • max(| cos θ| -| sin θ|, 0), where X and θ are independent, X follows a Rayleigh distribution and θ is uniformly distributed on [0, π]. Finally, the distribution of each γ p (q) under H 0 can be written

P H0 [t() ≥ t] = P H0 [∀m, ω p (r, θ m ) ≥ t] = M m=1 P H0 [ω p (r, θ m ) ≥ t]. (8)
µ(z) = 1 2 δ 0 (z) + H(z) • 1 √ π e -z 2 4 • erfc( z 2 )dz, (9)
where δ 0 is a Dirac mass at 0, H is the Heaviside function (H(z) = 1, for z ≥ 0, and H(z) = 0 otherwise) and erfc is the complementary error function, erfc(z) = 2 √ π ∞ z e -s 2 ds. The empirical distribution of γ p (q) on 50 natural images is displayed in Figure 5b, along with its theoretical distribution µ, showing excellent fit to the model. Under the hypothesis H 0 , the law of the strength of a branch ω p (r, θ m ) (that is, of the sum of pixel contributions given by Formula ( 5)) is obtained by convolving J(r, θ m ) times with itself the distribution µ, where J(r, θ m ) is the size of a sector of orientation θ m at scale r. Finally, Proposition 1 Let  : p, r, {θ m } M m=1 be a junction and suppose that the hypothesis H 0 is satisfied, then the probability that the random variable t() is larger than a given threshold t is

F  (t) := P H0 [t() ≥ t] = M m=1 +∞ t J(r,θm) ⋆ j=1 µ(dz), ( 10
)
where J(r, θ m ) is the size of a sector of orientation θ m at scale r.

Meaningful junctions

Thanks to the previous computations, we are now in a position to automatically fix detection thresholds on junction strengths. Indeed, thresholds are set so that the average number of false detections under the null hypothesis is controlled. This is obtained by thresholding the probability [START_REF] Leichter | Boundary ownership by lifting to 2.1d[END_REF] and by taking into account the number of possible discrete junctions in the image.

Number of tests

In this paragraph, we assume that the order M is fixed, and we call J (M ) the set of all possible junctions of order M in the discrete image I. The size of J (M ) depends on several parameters: the minimum and maximum authorized scales r min and r max , the size N (number of pixels) of I and the precision ∆(r) of branches at each scale r. The practical setting of these parameters will be discussed in Section 4.1. At a given location p, once the first branch is chosen among the K(r) possible directions, the second direction must be chosen in such a way that the two branches of width 2∆(r) do not intersect, which means that only K(r)(1 -2 ∆(r) π ) directions are authorized. Therefore, at each location p ∈ Ω, and for a given scale r, the number of possible junctions of order M is always smaller than

1 M ! M m=1 K(r) 1 -2(m -1) ∆(r) π .
It follows that the size of the set J (M ) is upper bounded by

#J (M ) = N M ! • rmax r=rmin M m=1 K(r) 1 -2(m -1) ∆(r) π . (11)
ǫ-meaningful junctions The next definition and the following proposition explain how to fix thresholds on junctions strengths in order to control the average number of false detections.

Definition 3 (ǫ-meaningful junction) Let I be a discrete image. For ǫ > 0, a junction  of order M and at scale r is said to be ǫ-meaningful if

NFA() := #J (M ) • F  (t()) ≤ ǫ. (12)
The quantity NFA() is a measure of the meaningfulness of the junction: the smaller it is, the more meaningful the junction . A junction of order M and scale r is detected as ǫ-meaningful in I if its strength t() is larger than the threshold

t(r, ǫ) := min t; F  (t) ≤ ǫ #J (M ) . ( 13
)
Notice that for a fixed ǫ, this formula yields a different threshold on t() for each value of the scale r. The value ǫ is easy to interpret: it corresponds to an expected number of false detections in I.

Indeed,

Proposition 2 Let I be a discrete random image and assume that the null hypothesis H 0 is satisfied. Let M be a positive integer. The expectation of the number of ǫ-meaningful junctions of order M in I is smaller than ǫ.

Proof 1 First, observe that if X is a random variable and if we define

F (t) = P[X ≥ t], then for all β in [0, 1], P[F (X) ≤ β] ≤ β.
Thus, if  is a junction of scale r in J (M ), Formula (10) yields

P H0 NFA() ≤ ǫ = P H0 F  (t()) ≤ ǫ #J (M ) ≤ ǫ #J (M ) . ( 14
)
Finally,

E H0 #{ ∈ J (M ); NFA() ≤ ǫ} = ∈J (M ) P H0 NFA() ≤ ǫ ≤ ∈J (M ) ǫ #J (M ) ≤ ǫ. ( 15
)
Observe that in the definition of the NFA, the correcting factor #J (M ) is independent of the scale r. We could have used different correcting factors, depending on the junction scale r, in order to favor some particular scales in the detection, and still have a result similar to Proposition 2.

Junctions or nearby edges?

In images, some structures may appear as junctions at large scales without being detected as such when the scale is small. For instance, when three straight edges have close endpoints and are supported by concurring lines, an Y -junction may be detected even if the actual edges do not physically meet, when the possible junction contains a gap at its center. Deciding between a real junction and interacting edges is actually far from trivial. Psychophysical experiments [START_REF] Rubin | The role of junctions in surface completion and contour matching[END_REF] suggest that human may find junctions although there is a small gap at the center. In practice, we observed that detections were visually more satisfying when removing junctions with large gaps at their center. This restriction is imposed by computing for each ǫ-meaningful junction  : {p, r, {θ m } m∈{1,...,M } } a minimum scale of detection, defined as (see Figure 7)

r d [] = min r ′ ≤ r; ∀s ∈ [r ′ , r], ∃ ′ : {p, s, {θ ′ m } M m=1 } s.t.  ′ is ǫ-meaningful. , (16)
and by removing all ǫ-meaningful junctions such that r d [] > r gap . In practice and within the scope of this paper, this threshold is chosen as r gap = 12. In order to be fully scale invariant, this threshold could be replaced by a value proportional to the junction scale r.

Redundant detections and maximality

Redundancy: scale and location As it is common when analyzing geometrical structures in images, junctions are usually detected in a redundant way. A single structure in the image may yield many detections. First, junctions are detected over a range of scale. For a single ideal junction in the image, meaningful junctions will be detected for scales both smaller and larger than the one of the underlying structure, see Figure 6, middle, where several junctions having the same center but different scales, and corresponding to the same ideal Y -junctions, are displayed. Second, several junctions with slightly different locations are detected for a single underlying structure. This is all the more strong as there is blur in the image. An example of such redundant detections is displayed in Figure 6, right. Moreover, both type of over-detections (multiple scales and multiple locations) are usually combined in images. These redundancies are addressed in the next paragraph thanks to an exclusion principle. Maximal junctions In order to choose the right representative among all redundant detections, we use an exclusion principle, called maximality. We assign to each junction  a neighborhood N ′  . For a given order M , we only keep the junctions not containing any more meaningful junction in its neighborhood. That is, we only keep junctions that are maximal in the following sense.

Definition 4 (Maximal ǫ-meaningful junction of order M ) A junction  : {p, r, {θ m } M m=1 } is said to be a maximal ǫ-meaningful junction of order

M if  is ǫ-meaningful and if NFA() ≤ NFA( ′ ) for any junction  ′ : {p ′ , r ′ , {θ ′ m } M m=1 }, with p ′ ∈ N ′  .
Observe that in this definition the use of the NFA is the keypoint. Indeed, it permits to compare structures at different scales. Using the strengths t() to carry out this comparison would require a well chosen normalization depending on the scale.

In order to select maximal meaningful junctions, the most meaningful junction is first considered. All junctions having it as a neighbor are then removed. Then we proceed to the next most meaningful junction and iterate the same procedure until all junctions have been treated. A result of these selection rules is illustrated in Figure 8 for M = 3. In practice, the spatial neighborhood N ′ p used for maximality is chosen as a disk centered at p, with a radius r d [], the minimum scale of detection of  as defined by Formula ( 16).

Masking and junction order When a Y -junction is perceived in a image, the underlying Ljunctions are usually not perceived and we decided not to detect them. This masking phenomenon (for a given junction, no junction made of a subset of its branches should be detected) is easily implemented by the following second exclusion principle: locally, only the more complex junction (the one with the largest order) is kept.

Definition 5 (Maximal ǫ-meaningful junction) A junction  : {p, r, {θ m } M m=1 } is said to be a maximal ǫ-meaningful junction if  is a maximal ǫ-meaningful junction of order M and if there is no maximal ǫ-meaningful junction of order M ′ located at p ′ with M ′ > M and p ′ ∈ N ′  .

The three algorithmic steps for junction detection

The different steps of the junction detection procedure are summarized in Algorithms 2 (the a contrario detection), 3 (maximality of order M ) and 4 (maximality). The complete algorithm pipeline includes a speed-up step and an optional precision refinement and will be described in Section 4 and summarized in Algorithm 7.

Algorithm 2 A contrario junction detection

Input: An image I, a maximal order M ′ and parameters ǫ, r min , r max , r gap .

Output: A list of junctions Jlist and the corresponding list of minimum detection scales r d [Jlist].

1: Compute ∇I at each pixel using Equation (1); 2: For each value of M between 2 and M ′ , compute #J (M ) by using Equation ( 11); 3: for each pixel p do

4:

Let ρ be a M ′ × r max matrix (used to record the values r d ), and fill it with zeros.

5:

for r = 1 to r max do 6:

Compute the branch strength ω p (r, θ) for each direction θ in D(r), using Equations ( 5) and ( 6).

7:

Use a NMS procedure to only keep semi-local maxima of ω p (r, .); call Θ = {θ m } #Θ m=1 the set of these directions.

8:

Sort the vector ω p (r, Θ) in a descending order (index, υ) ← sort(ω p (r, Θ)). Compute log NFA() by using Equation [START_REF] Kovesi | Phase congruency detects corners and edges[END_REF] 13:

if log NFA() ≤ log ǫ then end for 25: end for Algorithm 2 does not include the two maximality steps (described in Algorithms 3 and 4). Notice however that line 11 of Algorithm 2 is a first step towards maximality, since only the best junction of a given order M is tested at each point. This permits to speed-up the algorithm by excluding junctions that will obviously not be maximal. If we wish to compute all ǫ-meaningful junctions in an image, and not only maximal junctions, lines 11 to 22 should be replaced by Procedure 5.

Algorithm 3 Maximality for junctions of order M Input: Jlist: the list of L ǫ-meaningful junctions of order M detected in I and the list r d [Jlist].

1: Sort Jlist in a descending order according to the NFA of junctions: Jlist ← Sort(Jlist, NFA) 2: Remove non-maximal meaningful junctions 3: for j = 1 to L do

for k = j + 1 to L do 6:  2 ← location of junction Jlist[k] 7: if p 1 -p 2 2 ≤ r d [ 1 ] then 8:
remove Jlist[j], then break;  1 ← location of junction Jlist[j];

3:

for k = 1 to L do 4:  2 ← location of junction Jlist[k] 5: if p 1 -p 2 2 ≤ r d [ 1 ] and M 1 < M 2 then 6:
remove Jlist[j], then break;

Implementation

The goal of this section is to provide all necessary informations for the practical implementation of junction detection. First, the setting of parameters is addressed in Section 4.1. An optional refinement step to improve the accuracy of the detected branch directions is described in Section 4.2. A preselection of the junction candidates for speeding up the method is detailed in Section 4.3. Eventually, the complete detection algorithm pipeline is given in Section 4.4. A practical issue regarding the numerical computation of the NFA is also given in Appendix A.

Parameter choices

Recall that in the definition of discrete junctions, K(r), the number of possible directions for junction branches as defined by Formula (3), was chosen as K(r) = ⌊2πr⌋, in order to have a precision of roughly one pixel along the circle of radius r. The choice of the precision ∆(r) relies on similar considerations. Visual experiments show that the perceived precision of an angle between two crossing segments in an image is better for long segments than short ones. Now, recall that 2∆(r) is the angle of a branch (or sector) in a junction at scale r. We consider that the length of the arc defined by this sector should be a constant w and should not depend on r. This length is exactly 2∆(r) × r, which implies that ∆(r) should be chosen as inversely proportional to r. In practice, we choose w = 5. Thus

2∆(r) = w r = 5 r . ( 17
)
Figure 9 illustrates the corresponding angular sectors for two different scales.

It follows that for a given order M , the number of tests #J (M ) can be computed as

#J (M ) = N M ! rmax r=rmin M m=1 ⌊2πr⌋ 1 - 5(m -1) rπ , ( 18
)
where N is the total number of pixels in the image. In the experimental section, the maximum order of junctions will be M = 4 and the smallest possible radius is r min = 3 for all experiments. The maximal scale r max is chosen as 5% of the diagonal of the image. The threshold on the minimum scale of detection is set to r gap = 12 for all experiments in this paper.

Figure 9: ∆(r) = ω/r for two distinct r values. Observe that the length of the arc defined by a sector, w, is a constant and does not depend on r

Optional direction refinement

Since directions in a junction are bisectors of angular sectors (see Equation ( 4) for the definition of S p (r, θ)) and since the set of possible directions is discrete, it may happen that the directions of some branches in a detected junction remain slightly imprecise. In the following, we describe a simple refinement in the computation of junction directions.

For a branch of direction θ centered at p, a refined direction θ is computed as follows

θ = arctan O y O x , (19)
with

O x = q∈Sp(r,θ) γ p (q) cos ψ q ; O y = q∈Sp(r,θ)
γ p (q) sin ψ q ;

and

ψ q = φ q if d 2π (φ q , θ) < π 2 φ q + π otherwise. ( 20
)
Notice that after this refinement, two branches in a given junction may intersect. If this happens, the detected junction is removed. The refinement process is described in Algorithm 6.

Algorithm 6 Direction refinement

Input: A junction  : (p, r, {θ k } M k=1 ) 1:
(1) Refinement of junction branches:

2: for k = 1 to M do 3: O x = 0, O y = 0; 4:
for q ∈ S p (r, θ k ) do 5:

Compute γ p (q) using Equation ( 6);

6:

Compute ψ q using Equation (20);

O x ← O x + q∈S B k γ p (q) cos ψ q ; 9:
O y ← O y + q∈S B k γ p (q) sin ψ q ; 10:

Update the branch direction θ k = arctan Oy Ox . 11: end for 12: (2) Check that branches are still disjoint. 13: for m = 1 to M do 14:

for k = m + 1 to M do 15: if d 2π (θ m , θ k ) < ∆(r) then 16:
Remove , then break;

Speed up

In order to speed-up the algorithm, and following [START_REF] Parida | Junctions: Detection, classification, and reconstruction[END_REF][START_REF] Cazorla | Junction detection and grouping with probabilistic edge models and Bayesian A*[END_REF][START_REF] Cazorla | Two Bayesian methods for junction classification[END_REF][START_REF] Sinzinger | A model-based approach to junction detection using radial energy[END_REF], we propose to apply a pre-processing step to select potential junction candidates.

We take advantage of a fast segment detector, the Line Segment Detector (LSD) as introduced in [60]1 , whose complexity is linear in the size of the image. In order to make sure that we won't miss some junction candidates, the detection threshold λ of the LSD is set to a large value. The value λ = 10 4 has been used for all experiments in this paper. Once all possible line segments have been found, potential junction locations are restricted to a small neighborhood around each endpoint of those line segments. Figure 10 displays all line segments detected with λ = 10 4 for a given image and shows the corresponding junction candidates in red.

Table 2 shows the number of detections and the running time of the complete junction detection procedure, with and without use of the LSD preprocessing. The comparisons are implemented on three types of images: images containing both geometry and texture, images containing mostly textures and photographs of abstract paintings (see Figure 11). Using candidates from LSD clearly reduces the computing time, while the quantity of detections is not affected. Notice that this reduction strongly depends on image structures. The simpler the structures contained within the images, the larger the achieved reduction.

Algorithm pipeline

The pipeline of the whole a contrario junction detection algorithm is summarized in Algorithm 7.

Remark that the parameters to be set in this algorithm are: the detection threshold ǫ, the maximum order of junctions M ′ and the radiuses r min , r max , r gap (see Section 4.1).

Algorithm 7 Complete junction detection procedure

Input: Image I, threshold ǫ, maximal order M ′ , parameters r min , r max , r gap .

(1) Use LSD to preselect junction candidates C;

(2) Detect ǫ-meaningful junctions for all orders smaller than M ′ and for all scales between r min and r max by using Algorithm 2. Store junctions of order M in a list Jlist(M ).

(3) For each M ≤ M ′ , refine all junctions in Jlist(M ) by using Algorithm 6.

(4) Keep only maximal junctions in the lists Jlist(M ) by using Algorithm 3 and 4.

In the rest of the paper, we refer to this algorithm by the acronym ACJ (for A Contrario Junction detection).

Experimental Analysis

This section gathers experiments illustrating the performances of the a contrario junction detection (ACJ). When possible, performances will be compared with the classical Harris detector [START_REF] Harris | A combined corner and edge detection[END_REF] and the recent "Pj on gPb" method [START_REF] Maire | Using contours to detect and localize junctions in natural images[END_REF]. For Harris, the cornerness is defined as det(H)k • T r(H) 2 , where H is the Harris matrix and the default value k = .04 is chosen. For "Pj on gPb", the code kindly provided by M. Maire is used.

Section 5.1 illustrates the stability of the detection for different images. We then investigate the invariance properties of the method: scale and contrast changes are respectively studied in Sections 5.2 and 5.3. In particular, we show the ability of the method to accurately detect both the scale and the position of a junction. Evaluation on a benchmark is given and discussed in Section 5.4 and some more results are displayed in Section 5.5.

Stability and choice of ǫ

One great quality of a contrario detection methods relies in the fact that the threshold ǫ has an intuitive meaning: it is an upper bound of the average number of false detections in an image following H 0 . This makes the setting of ǫ quite easy in practice: by default, and unless otherwise indicated, ǫ is set to 1 in all experiments. We checked that, on the average, less than one false detection occur in a Gaussian white noise image. This could be expected since such images almost follow the hypothesis H 0 . Now, the real strength of the ACJ approach comes from the fact that the value ǫ = 1 also yields very satisfying detections in natural images, whatever their content, size or resolution. In contrast, other approaches such as Harris or "Pj on gPb" tend to strongly over-detect in textured areas when using a fixed parameter, see Figure 12. This stability property is all the more interesting as it remains valid through scales. For a given choice of ǫ, Formula (13) yields different thresholds t(r, ǫ) that adapt to the scales of the junctions. As a consequence, by choosing ǫ = 1, results are simultaneously satisfying at all scales. This would not be possible with a fixed threshold on junction strengths.

Figure 12: Junctions obtained by ACJ (top row), Harris (mid row) and "Pj on gPb" (bottom row). Parameters are fixed for the three images, yielding the same number of detections on the house image (this correspond to ǫ = 1). Observe that only ACJ prevent from over-detection in textured areas. The color of the junction depends on the NFA value (red corresponds to small values, i.e. very meaningful junctions and blue corresponds to high values).

Scale Invariance

This section focus on the behavior of our approach with respect to scale changes. Recall that the scale of a junction is defined as the scale at which the junction is most meaningful and therefore strongly differs from classical approaches relying on the linear scale space. In Section 5.2.1, we show that such scales change linearly with the resolution of images, a clearly desirable property. In Section 5.2.2, we discuss the interpretation of these scales in images. Finally, Section 5.2.3 demonstrates that the ACJ approach has a better spatial precision through resolution changes than other classical approaches.

Scale and resolution

In order to investigate the coherence of detections through scale changes, we apply the proposed junction detection algorithm to a sequence of images with different resolutions. An original image I is resized with 8 different zoom factors s 0 > • • • > s 7 , using a bilinear interpolation. The set of factors is chosen as {1, 0.9, 0.8, 0.7, 0.6, 0.5, 0.4, 0.3}. Algorithm 7 is then applied to each image s i I of the sequence and yields a junction list J si . Then, each junction  0 of J s0 is tracked through resolutions. For this purpose, we define an angular distance between two junctions:

S(,  0 ) = max θ∈{θm} M m=1 min θ ′ ∈{θ 0 m } M 0 m=1 d 2π (θ, θ ′ ). (21)
A junction  0 in J s0 is then matched with j i in J si if they have the same order M 0 , if their centers are close enough, in the sense that ps i • p 0 2 < 3, and if their angular distance S( 0 , ) is smaller than π 20 . If several junctions in J si satisfy these properties,  0 is matched with the one minimizing the angular distance S( 0 , ). If there is no junction in J si satisfying these properties, no junction in J si is matched with  0 . For each junction  0 in the original image, we call trajectory the list of its corresponding junctions through the different resolutions.

Several such trajectories are shown on Figure 13 (b). In this experiment, we only consider junctions potentialy having complete trajectories in the scale space. Therefore, the maximal scale considered in the coarsest image is r max × 0.3 = 30 × 0.3 = 9. The red curves show the scales of junctions along all the trajectories as functions of s i /0.3. The baselines {y = r • s i }, where r changes from 1 to 90, are displayed in blue. These correspond to an ideal behavior with respect to resolution changes. Notice that the red curves remain close to the baselines: this implies that the scales of maximal meaningful junctions are quite robust to resolution changes. Figure 14 (a) gives some concrete examples of junctions detected by the ACJ algorithm along their trajectories. Once more, their scales increase linearly with resolution. To the best of our knowledge, the only approaches which permit to obtain a similar coherence between scale detection and resolution are those which rely on linear scale-spaces [START_REF] Lindeberg | Feature detection with automatic scale selection[END_REF][START_REF] Luo | Resolution-independent characteristic scale dedicated to satellite images[END_REF]. However, it should be underlined that the use of linear scale-space inevitably leads to poor location precisions at large scales. This aspect will be further developed in Section 5.2.3. Figure 14 (b) illustrates the aforementioned dilemma (see Section 3.4) to detect or not a junction in the presence of nearby edges. In these examples, junctions are not detected at large scale because of the constraint r gap (see Section 3.5). This behavior seems consistent with human perception: when several edges meet around a large gap, we probably disregard it as a junction.

In a second experiment, shown on Figure 13 (c), we compute the repeatability rate of detections with respect to image resolution. More precisely, if we note J s0 (s 0 I → s i I) the list of junctions that are matched for all intermediate resolutions between s 0 I and s i I, the repeatability rate is defined as

R(s i ) = #J s0 (s 0 I → s i I) #J s0 . ( 22
)
Observe that, for the three images, the repeatability rate always remains above 60%.

How to interpret the detected scales ?

Most of the junction detection approaches in the literature do not provide characteristic scales for their junctions. One notable exception is the Harris-Laplace interest point detector, which makes The second row shows the scales of junctions detected by ACJ along all the trajectories (curves in red) as a function of the zoom factor s i (the abscissa is s i /0.3). The baselines {y = r • s i }, where r changes from 1 to 90, are displayed in blue. The bottom row presents the repeatability rate of the junctions as a function of the zoom factor. use of a linear scale space in order to detect keypoints at different scales. Detected points are those which maximize the Laplacian of Gaussian (LoG) in the scale-space and the Harris corner measure in a local space neighborhood. Some results of this detector on a synthetic and a real image are given in Figure 15 (b) and(d). Observe that the scales of junctions do not have a clear interpretation in these images. In contrast, the scales detected by ACJ (see Figure 15 (a) and(c)) arguably correspond to the optimal size at which one can observe the junction in the image. For instance, the scale of the L-junctions located at the corner of a rectangle is generally chosen as the length of the smaller side of the rectangle, see Figure 15 (a). More generally, we observed that the scale of a junction usually corresponds to the length of its shortest branch. The fact that the use of the N F A as a tool to select the most proheminent scale yields such simple geometric behavior is a strong asset of the proposed approach. The same coherence between the characteristic scales of junctions and the sizes of local structures can be observed in the examples of Figure 14.

Scale and spatial precision

We have shown that the ACJ approach permits to detect scales that behave correctly when images are zoomed. We now show that the location of the junction is accurate and stable when performing such resolution changes, in contrast to linear scale space approaches. We compare ACJ with two classical methods, Harris-Laplace and the "Pj on gPb" detector proposed by Maire et al. [START_REF] Maire | Using contours to detect and localize junctions in natural images[END_REF]. To this aim, we build in the same way as before a sequence of images composed of one image at full resolution (the one displayed on Figure 15 (a)) and 7 sub-sampled versions with zoom factors {0.9, 0.8, 0.7, 0.6, 0.5, 0.4, 0.3}. The original image is made of simple geometrical patterns, which permit to easily create a ground-truth of junctions. Gaussian noise and blur are added to the original image before creating the sequence. For a given image and a given method, the detected junctions are matched to the junctions of the ground truth in the same way as in Section 5.2.1. The average location error is then defined (for this image and this method) as the average squared Euclidean distance between detected junctions and their corresponding groundtruth junctions.

The average location errors of the different methods are shown in Figure 16 (b). We can see that ACJ has the smallest errors, followed by the Laplace-Harris detector and "Pj on gPb".

Contrast Invariance

The goal of this section is to evaluate the robustness to contrast changes of different junction detection approaches. To this aim, we create a sequence of images by applying different gamma corrections to an original image I, with γ in { 1 4 , 1 3 , 2 5 , 1 2 , 2 3 , 1, 1.5, 2, 2.5, 3, 4}. For each image in the sequence, we detect junctions with

• our ACJ approach, with ǫ = 1,

• Harris corner detector, with a threshold 0.06 on local maxima, • Maire's approach using "Pj on gPb" [START_REF] Maire | Using contours to detect and localize junctions in natural images[END_REF],

• a totally contrast invariant version of ACJ (denoted TACJ), obtained by removing the normalized gradient amplitudes in the definitions ( 5),( 6) of the branch strength 2 .

In order to evaluate the different results, we compute the repeatability rate of each method on the image sequence. More specifically, if J 0 is the list of junctions in the original image (γ = 1), and J i the list of junctions in the i-th image, we note J 0 ∩ J i the set of junctions in J i that can be matched with junctions in J 0 , where the matching criterion is the one defined in Section 5.2.1. Following the same protocol as in [START_REF] Schmid | Evaluation of interest point detectors[END_REF], the repeatability rate of the i-th image is then calculated as

Repeat(i) = #{J 0 ∩ J i } #J 0 . ( 23
)
The curves of repeatability rates for the different methods are shown on Figure 17. We can see that the Harris detector has the worst performance with respect to contrast changes, which could be expected since it is the most contrast dependent. Maire's approach [START_REF] Maire | Using contours to detect and localize junctions in natural images[END_REF] gives better results, possibly because it relies on an detector that is tuned to match boundaries annotated by humans, which may somehow eliminates contrast variations. Both ACJ and TACJ perform better than the other ones, TACJ providing (as could be expected) slightly better results than ACJ. This could advocate for the choice of TACJ in practice. However, we observed that this totally contrast invariant approach appears to be less robust than ACJ to small image modifications, such as those created by JPEG compression. The choice of ACJ results in a compromise between contrast invariance requirements and robustness. 11.

2 This boils down to replace the distribution of the strength at a pixel with µ = [START_REF] Leichter | Boundary ownership by lifting to 2.1d[END_REF].The resulting junction detection algorithm is similar to Algorithm 7.

1 2 δ 0 + 2 π 1 √ 2-z 2 H(z)dz in Equa- tion

Junction benchmark

A practical way to evaluate the consistency of our approach with human perception would be to rely on a human annotated junction database. To the best of our knowledge, such a database does not exist. Nevertheless, the well known Berkeley segmentation dataset3 has been used by the authors of [START_REF] Maire | Using contours to detect and localize junctions in natural images[END_REF] in order to evaluate different junction detectors. In their paper, Maire et al. use the human annotated boundaries to create a ground truth of junctions in the following way: L-junctions are locations of high curvature along these boundaries and Y -junction are locations where more than three regions intersect. As mentioned before, they also propose a procedure called Pj to detect junctions from any given set of boundaries. This procedure is applied to the results of different edge detectors, including their detectors Pb and gPb. The quality of the resulting junctions is assessed by comparing them to the previously created ground truth. We applied the same protocol to the ACJ method proposed in this paper. In order to overcome the strong compression artifacts of the Berkeley database, to which we are sensitive because of strong contrast robustness, we apply a small amount of blur and noise to images before proceeding. Figure 18 presents the results for several junction detection algorithms on the benchmark. The ACJ approach yields a performance of F= 0.38 4 , which is better than the baseline Harris detector (F=0.28) and Pj on Canny (F=0.35) but remains below the performance of Pj on Pb (F=0.38) and Pj on gPb (F=0.41). The human agreement on the database yields F=0.47. The performance of our approach in comparison to Pj on gPb has to be tempered by two facts. First the junctions of the ground truth stem from a set of human annotated boundary, and the junctions detected by Pj stem from a computer segmentation. Therefore, both are boundary-based. It is likely that any detector using a more local junction definition (including ACJ or even Harris) will be penalized in the benchmark. As explained in the introduction and shown by psychophysical studies [START_REF] Rubin | The role of junctions in surface completion and contour matching[END_REF], both local and global cues are at play for the perception of junctions. Second, and most important, the parameters of Pb and gPb are optimized in order to match human detected edges on the same database, which introduces a bias in favor of these methods.

More Results

This last section aims at illustrating the proposed approach with several more visual experiments. Figure 19 presents all the junction detected on a synthetic image. We can observe that the junctions are found with high accuracy and are mostly correctly classified. Figures 20 and21 present the results on two natural images. Observe that junctions are accurately characterized through their type, localization and scale. Again, we emphasize that the proposed ACJ algorithm yields very litlle detections in textured areas, see Figure 21.

Conclusion and perspectives

In this work, we have introduced a generic and principled approach for the detection and characterization of junctions in digital images. The proposed procedure is able to inhibit junction detection in textured areas, in contrast with classical approaches. Junctions are accurately characterized through their type, localization and scale. In particular, the method does not rely on the linear scale-space for scale computation, permitting geometric precision.

This works opens several perspectives. First, the accuracy of junction characterization is of importance for depth recovery or motion interpretation. The characterization of junction's type, the difference between T-and Y-junctions or their precise localization claim to be tested in the framework of such applications. Second, and as advocated in the introduction, several psychophysical studies show that the perception of junctions relies on both local and global cues. Therefore the proposed, local, procedure for junction detection could benefit from more global image analysis schemes. The modeling of interactions between junction detection and segmentation procedures is far from trivial, but similar principled approaches could be applied to junction definitions building from color and textured-based region analysis. In the opposite direction, segmentation methods can benefit from meaningful junction detections. Preliminary tests show that the boundary saliency, as for instance defined in [START_REF] Golubchyck | Improving the saliency algorithm by cue optimization[END_REF], can benefit from a meaningful detection of junctions, in particular by solving ambiguities in boundary connections near these junctions.

Figure 1 :

 1 Figure 1: Gradient ∇I and normalized gradient ∇I on an image patch

7: end for 8 :

 8 return The set of detected junctions.

  (a) original image (b) f ∇I and φ (c) γp(q), the contributions of pixels to the junction strength branch strength ωp(r, θ) in blue and semilocal maxima in red; (e) From left to right, a potential L-junction, a potential Y-junction and a potential X-junction respectively;

Figure 3 :

 3 Figure 3: Computation of junction candidates at scale r = 12, when p is the center of the original image (a). The blue curve in (d) shows the strength ω p (r, θ) as a function of the direction θ along the circle. The directions that remain after the NMS procedure are shown in red. For r = 12, K(r) = 75, and 2∆(r) = 0.289 (see Section 4.1).

Figure 4 .

 4 Moreover, we performed a small scale experiment whose results are shown on Figure5a. In blue are displayed the empirical distributions of ∇I for 50 different natural images, as well as the density of the Rayleigh distribution of parameter 1 (in red).

2 (Figure 4 :

 24 Figure 4: Approximations of the distributions of I x , I y and ∇I (given by Equations (1) and (2)). The blue curves are the empirical histograms and the red curves are the approximated distributions. (e) and (f) are Gaussian distributions and (g) is a Rayleigh distribution of parameter 1.

Figure 5 :

 5 Figure 5: Distributions of ∇I (blue curves in (a)) and γ p (q) (blue curves in (b)) for 50 different natural images. Rayleigh(1) density (red curve in (a)) and the corresponding strength distribution µ(z) (red curve in (b)) are displayed for comparison.

Figure 6 :

 6 Figure 6: Redundancy of junction detection. For the sake of clarity, each junction is represented by a circle and its center, the radius of the circle is equal to the scale of the junction, and the color of the circle depends on the NFA value (red corresponds to small values, i.e. very meaningful junctions and blue corresponds to high values). Left: a junction  : {p, r, {θ m } m∈{1,...,3} }, with r = 20. Mid: all junctions detected at the same point p, with different scales. Right: all Y -junctions detected in the neighborhood of p, with the same directions and scale.

Figure 7 :

 7 Figure 7: Scale of a junction. Left: image I. The point p is chosen as the center of I. Middle: for each scale r (in abscissa) is displayed the smallest NFA() observed for a junction  of order 3 centered at p. Right: the smallest scale of detection r d = 8 in magenta and the scale corresponding to the smallest NFA in red (found for r = 13), represented on top of the strength γ p (q).

Figure 8 :

 8 Figure 8: Maximal meaningful junctions of order 3. Each Y -junction is represented by a circle and its center. The radius of the circle indicates the junction scale r, and the color of the circle corresponds to the NFA of the junction (the cooler the color, the larger the NFA). Left: all ǫ-meaningful Yjunctions, with ǫ = 1. Mid: the maximal meaningful Y -junctions. Right: the maximal meaningful Y -junctions displayed over the image.

9 : 11 :

 911 Suppression of alignments:ifM = 2 and d 2π (θ index(1) , θ index(2) + π) ≤ 2∆(r) θ index(2) = θ index(3) end if 10: for M = 2 to M ′ do Define the junction  : {p, r, {θ m } index(M )m=index(1) }, with strength t() = υ(index(M ))12:

14 :

 14 if ρ(M, r -1) = 0 then 15: ρ(M, r) = ρ(M, r -1) and r d [] = ρ(M, r -1) 16:

20 :

 20 r) = r and r d [] = r if r d [] < r gap thenAccept the junction proposal : Jlist ← 

4 : 1 ←

 41 location of junction Jlist[j];5:

4 1 :

 41 Maximality Input: A maximum order M ′ . The list Jlist of maximal ǫ-meaningful junctions of all orders smaller than M ′ in I and the list r d [Jlist]. L is the size of Jlist. for j = 1 to L do 2:

Figure 10 :

 10 Figure 10: Junction candidates using LSD. Left: the input image; Mid: all line segments detected with λ = 10 4 ; Right: all junction candidates.

Figure 11 :

 11 Figure 11: Test images for the speed up evaluation. Top: house, Lena and window; Mid: autumn, park and branches; Right: images of geometric paintings: Geometric by John Cooper, Composition by Charmion von Wiegand, and Suprematism by Kazimir Severinovich Malevich.

Figure 13 :

 13 Figure13: Illustration of the scale invariance along the scale space. The first row shows the tested images. The second row shows the scales of junctions detected by ACJ along all the trajectories (curves in red) as a function of the zoom factor s i (the abscissa is s i /0.3). The baselines {y = r • s i }, where r changes from 1 to 90, are displayed in blue. The bottom row presents the repeatability rate of the junctions as a function of the zoom factor.

Figure 14 :

 14 Figure 14: Examples of detected junctions along several junction trajectories: each row shows a list of junctions detected at the same relative locations in images, from the coarsest to the finest resolution. (a) In these examples, junctions can be followed along complete trajectories, and their scales remain roughly proportional to the image resolution. (b) These two examples illustrate the difficulty of junction detection in the presence of nearby edges.

Figure 15 :

 15 Figure 15: Scale selection. (a) shows the characteristic scale of L-, Y-and X-junctions given by the proposed approach, and (b) shows the characteristic scale of junctions given by Harris-Laplace on a synthetic image. (c) and (d) show the same comparison on the house image. The location of each junctions is indicated by a red cross and circles have a radius equal to the corresponding scale. Refer to the text for more explanations.

Figure 16 :

 16 Figure 16: Average location error for different approaches: the proposed ACJ, "Pj on gPb" and the Harris detector. The comparison is led on a sequence of images with different resolutions, starting from the image displayed in Figure 15 (a).

  Pj on Canny [F=0.35] Harris on Pb [F=0.34] Harris [F=0.28] (a) Precision-Recall curves of different methods

Figure 18 :

 18 Figure 18: The precision-recall curves of different methods on the BSDS-based junction benchmark.

Figure 19 :

 19 Figure 19: Some results of the proposed ACJ approach, with ǫ = 1. From left to right: L-, Y-and X-junctions. On this simple synthetic image (from E. H. Adelson), junctions are well detected and classified. The color of the junction depends on the NFA value (red corresponds to small values, i.e. very meaningful junctions and blue corresponds to high values).

AF

  Appendix: Computing NFA in practiceThe NFA of a junction  : p, r, {θ m } M m=1 has been defined as NFA() := #J (M )• F  (t()), where z) + H(z) • 1 √ π e -z24 • erfc( z 2 )dz.

  Detailed junctions ranked according to their NFA

Figure 20 :

 20 Figure 20: Specific junction detections on a natural image. The color of the junction depends on the NFA value (red corresponds to small values, i.e. very meaningful junctions and blue corresponds to high values).

  Detailed junctions ranked according to their NFA

Figure 21 : 2 k

 212 Figure 21: Specific junction detections on a natural image. The color of the junction depends on the NFA value (red corresponds to small values, i.e. very meaningful junctions and blue corresponds to high values).

Table 1 :

 1 Different approaches for junction detection.

	Each junction is
	associated with
	an adaptive scale

Table 2 :

 2 Number of detections and running time when using or not the LSD pre-selection. The comparisons are implemented on three types of images: images with a strong geometrical content, images containing mostly textures and photographs of abstract paintings. Num (L/T/X) stands for the numbers of detected L/T/X junctions respectively. The experiments are implemented on a computer with a 2.0GHz Intel Core 2 Duo Processor and 2 GB RAM.

		Image		Using LSD candidates	Using all candidates
	class	name	size	Num (L/T/X) Time (s) Num (L/T/X) Time (s)
	geometry and texture Lena house window texture autumn park branches geometry geometric composition 413 × 300 3/60/36 256 × 256 28/21/3 256 × 256 79/44/12 768 × 576 120/224/51 576 × 768 52/25/8 576 × 768 97/98/15 536 × 819 78/100/18 655 × 518 27/17/2 suprematism 400 × 640 40/33/5	2.17 3.90 10.36 38.52 37.20 35.97 1.48 1.94 1.57	29/21/3 81/44/12 122/230/52 54/27/8 100/100/15 80/101/19 28/17/2 3/62/37 42/34/5	8.16 9.77 64.72 62.07 62.18 62.08 44.19 17.46 34.66

The code of LSD can be downloaded from the IPOL website: http://www.ipol.im/pub/algo/gjmr_line_segment_ detector/.

The Berkeley segmentation dataset can be downloaded from www.eecs.berkeley.edu/Research/Projects/CS/vision/bsds/.

F is defined as the highest value of the quantity 2 P recision•Recall P recision+Recall along the curve.

This formula is used in practice and compared to log(ǫ) in order to select ǫ-meaningful junctions.