Petra Bosilj

Ewa Kijak

Michael H F Wilkinson

Sébastien Lefèvre

Sébastien Lefèvre Short Local

Short Local Descriptors from 2D Connected Pattern Spectra

Keywords: local region descriptors, pattern spectra, maxtree, CBIR

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

The goal of content based image retrieval (CBIR) is retrieving images describing the same object or scene as the query from the database. Standard systems consist of keypoint detection, descriptor calculation and storage in an index. Different indexing schemes are used for database search [START_REF] Datar | Locality-sensitive Hashing Scheme Based on P-stable Distributions[END_REF][START_REF] Sivic | Video Google: Efficient visual search of videos[END_REF][START_REF] Lejsek | NV-Tree: Nearest Neighbors at the Billion Scale[END_REF]. The detection step either selects interest points or interest regions.We focus here on the description part of the system which benefits from powerful local descriptors [START_REF] Schmid | Object recognition using local characterization and semi-local constraints[END_REF], and use the well-established SIFT descriptors [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] to obtain a baseline CBIR performance on a database. Future work will include comparisons with SIFT extensions which improve performance [START_REF] Ke | PCA-SIFT: A more distinctive representation for local image descriptors[END_REF][START_REF] Bay | Speeded-up robust features (SURF)[END_REF][START_REF] Arandjelović | Three things everyone should know to improve object retrieval[END_REF].

The proposed local descriptors are based on pattern spectra, commonly used in image analysis and classification [START_REF] Maragos | Pattern spectrum and multiscale shape representation[END_REF] and previously used in CBIR as global descriptors [START_REF] Urbach | Connected shape-size pattern spectra for rotation and scaleinvariant classification of gray-scale images[END_REF][START_REF] Tushabe | Content-based image retrieval using combined 2D attribute pattern spectra[END_REF]. They can be efficiently computed using a mathematical morphology technique known as granulometry [START_REF] Breen | Attribute openings, thinnings, and granulometries[END_REF] on a max-tree hierarchy [START_REF] Salembier | Antiextensive connected operators for image and sequence processing[END_REF]. This makes them well suited for description of MSER regions [START_REF] Matas | Robust widebaseline stereo from maximally stable extremal regions[END_REF] which can be detected using the same structure. Extending [START_REF] Urbach | Connected shape-size pattern spectra for rotation and scaleinvariant classification of gray-scale images[END_REF], we compute 2D size-shape pattern spectra locally, and combine them with normalized central moments for the regions of interest. This produces a rotation invariant descriptor half the size of SIFT which achieves competitive precision.

We begin by explaining the detection and description parts of the CBIR system, with the focus on how the max-tree is used for both tasks, in Sec. 2. The experimental setup and the database used for performance evaluation are detailed in Sec. 3 with the results analysis offered in Sec. [START_REF] Schmid | Object recognition using local characterization and semi-local constraints[END_REF]. Possible directions for future work are provided in Sec. 5. The collaboration between the authors was supported by mobility grants from the Université européenne de Bretagne (UEB), French GdR ISIS from CNRS, and an excellence grant EOLE from the Franco-Dutch Network.

3 3 3 3 3 3 3 3 2 2 2 3 0 3 3 2 1 2 3 0 3 3 2 2 2 3 0 3 3 2 4 2 3 3 3 3 2 2 2 3 3 3 3 3 3 3 3 3 3 (a) L 4,1 L 3,1 L 2,1 L 1,1 L 0,1 (b)
Fig. 1: The max-tree for (a) is shown on (b). Nodes are labeled with upper level sets they correspond to, and the regions of the upper level sets are displayed besides the nodes.

KEYPOINT DETECTION AND DESCRIPTION

Max-tree

Max-tree and min-tree hierarchies [START_REF] Salembier | Antiextensive connected operators for image and sequence processing[END_REF][START_REF] Jones | Component trees for image filtering and segmentation[END_REF] of images were used for keypoint detection as well as the feature description. The upper level set at level k of an image I is a set of image pixels p with gray level values f (p) higher than a threshold k, L k = {p ∈ I|f (p) ≥ k}, where each level set can comprise several connected components.

All the connected components, or the peak components L k,i (i from some index set) of the upper level set L k are nested. They form a hierarchy represented by a max-tree (cf. Fig. 1), in which a node n k,i corresponds to the peak component L k,i at level k.

The min-tree can be obtained by considering the lower level sets {L k } of the image or by constructing a max-tree of the inverted image -I. These trees are constructed first, after which they are used both for selecting the regions of interest among all the tree regions, and then for calculating the descriptors for the selected regions.

MSER detection

The Maximally Stable Extremal Regions (MSER) detector was first introduced by Matas et al. [START_REF] Matas | Robust widebaseline stereo from maximally stable extremal regions[END_REF]. It responds to bright and dark "blobs" in the image, and is as such complementary to other commonly used detectors [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF][START_REF] Bay | Speeded-up robust features (SURF)[END_REF].

Extremal regions (maximal and minimal) correspond to the peak components of upper and lower level sets {L k,i } and {L k,i }, which allows for their detection concurrently with the construction of the max-tree and the min-tree [START_REF] Nistér | Linear time maximally stable extremal regions[END_REF]. As such, they are nested, and the local minima of the stability function q(L k,i ), calculated for elements of a nested sequence (i.e. nodes on a single path in the tree), correspond to maximally stable regions. This function indicates the rate of growth of the region L k,i with the decrease of the threshold level k. A simplification used by many computer vision libraries (e.g. VLFeat [START_REF] Vedaldi | VLFeat: An Open and Portable Library of Computer Vision Algorithms[END_REF]) for lowering the computation time is used:

q(L k,i ) = |L k-∆,i \L k,i | |L k,i | , (1)
where | • | denotes cardinality, with ∆ being a detector parameter.

Attributes and filtering

To every node (region) in the tree, we can assign attributes pertaining to the characteristics of that node. An attribute K(•) is increasing if, for two nested regions L k,i ⊆ L l,j , its value is always greater for the larger region: K(L l,j ) ≥ K(L k,i ). Consequently, the attribute value of a node, K(n k,i ) = K(L k,i ), will be smaller than any of the values of its ancestors. If this property does not hold, the attribute is nonincreasing. Out of all nonincreasing attributes, we are here interested in the strict shape attributes, which respond only to region shape and are thus invariant to scaling, rotation, and translation [START_REF] Breen | Attribute openings, thinnings, and granulometries[END_REF].

We use here only the attributes that can be computed incrementally, that is the attribute values of the parent nodes can be calculated based on the attribute values of their children, with only examining the new pixels in a region. We use the following attributes:

• Area: A(L k,i ), the size of the region in pixels, which is an increasing attribute. • Binary region moments: based on raw region moments, we can derive center of mass, covariances, skewness or kurtosis [START_REF] Wilkinson | Generalized pattern spectra sensitive to spatial information[END_REF]. We will use normalized central moments n1,1, n2,0, n0,2, n0,4 and n4,0.

• Corrected noncompactness: 2π( I(L k,i ) A(L k,i ) 2 + A(L k,i ) 6
), an elongation measure used as the (nonincreasing) shape attribute, where I(L k,i ) is the moment of inertia of the region.

Without the correction factor, [START_REF] Hu | Visual pattern recognition by moment invariants[END_REF]. Processing a tree, where we decide either to preserve or reject a node by comparing its attribute value to a threshold K(n k,i ) > t (or using a more complex criterion), is called a filtering. The reader is referred to [START_REF] Urbach | Connected shape-size pattern spectra for rotation and scaleinvariant classification of gray-scale images[END_REF][START_REF] Breen | Attribute openings, thinnings, and granulometries[END_REF][START_REF] Salembier | Antiextensive connected operators for image and sequence processing[END_REF] for more details on the filtering strategies, and attribute filtering based on increasing and nonincreasing attributes.

I(L k,i ) A(L k,i ) 2 is equal to the first moment invariant I = µ2,0 + µ0,2 of Hu

Granulometries and pattern spectra

When using an increasing attribute, the resulting attribute filtering is an attribute opening (i.e. anti-extensive, increasing and idempotent). A set of such openings for increasing values of the threshold t is called a size granulometry and satisfies the absorption property: after an attribute opening, another opening with a lower threshold will have no effect. We can consider a size granulometry as a set of sieves of increasing grades, each passing only details of certain sizes [START_REF] Urbach | Connected shape-size pattern spectra for rotation and scaleinvariant classification of gray-scale images[END_REF].

If we note the amount of detail removed between pairs of consecutive openings, we obtain a size pattern spectrum. Introduced by Maragos [START_REF] Maragos | Pattern spectrum and multiscale shape representation[END_REF], size pattern spectra are 1D histograms containing the number of pixels or the sum of gray levels for a range of size classes. Rather than repeatedly filtering an image and computing the difference, a connected pattern spectrum can be calculated in a single pass over a max-tree [START_REF] Urbach | Connected shape-size pattern spectra for rotation and scaleinvariant classification of gray-scale images[END_REF][START_REF] Breen | Attribute openings, thinnings, and granulometries[END_REF]. More importantly for our purposes, it is also possible to compute a histogram over different shape classes (i. e. ranges of shape attribute values), called a shape-spectrum [START_REF] Urbach | Connected shape-size pattern spectra for rotation and scaleinvariant classification of gray-scale images[END_REF].

Combining shape and size pattern spectra, we obtain shape-size pattern spectra [START_REF] Urbach | Connected shape-size pattern spectra for rotation and scaleinvariant classification of gray-scale images[END_REF] corresponding to 2D histograms where every bin contains the information about the amount of image detail for a certain size-shape class. A 2-D size-shape global pattern spectrum (GPS) is calculated for the whole image. Calculating it for a node Previous work [START_REF] Urbach | Connected shape-size pattern spectra for rotation and scaleinvariant classification of gray-scale images[END_REF][START_REF] Tushabe | Content-based image retrieval using combined 2D attribute pattern spectra[END_REF] and our own experiments suggest that the lower attribute values carry more information; thus, a logarithmic binning is used for both attributes. However, determining the bin c corresponding to the value v of an attribute is not trivial, and depends on several parameters:

c = log N bins √ SV (v SV UB ), (2)
where N bins is the number of bins used, and SV the scale value at which the LPS is computed. Attribute values higher than the upper bound UB are discarded (both attributes used have a minimal value of 1). An in-depth discussion of Eq. ( 2) and the experiments supporting parameter choice is offered in [START_REF] Bosilj | Local connected 2D pattern spectra descriptors applied to CBIR systems[END_REF],while we only give the final parameter choices here. We set N bins = 10 for the area attribute, and N bins = 6 for noncompactness, yielding a 60-bin spectrum. We also found that using a 9 × 6 spectrum causes only a slight decrease in performance (cf. Sec. 3 for the comparison), so a smaller spectrum can be used if an even shorter descriptor is required.

For the noncompactness, UB = 53 (or 56 for the 9 × 6 version) is also used for SV . These values are similar to the ones used for GPS in CBIR (52 in [START_REF] Urbach | Connected shape-size pattern spectra for rotation and scaleinvariant classification of gray-scale images[END_REF] and 53 in [START_REF] Tushabe | Content-based image retrieval using combined 2D attribute pattern spectra[END_REF]). The area of each MSER is used as UB for the area attribute. In case of GPS, the image area can be used for SV [START_REF] Urbach | Connected shape-size pattern spectra for rotation and scaleinvariant classification of gray-scale images[END_REF][START_REF] Tushabe | Content-based image retrieval using combined 2D attribute pattern spectra[END_REF]. To keep the scale invariance property of GPS, a same SV should be used for all LPS. However, it is hard to find an optimal SV , which would work well for all selected regions. By using a relative SV equal to the region area, we lose scale invariance but achieve better precision in all performed experiments (see [START_REF] Bosilj | Local connected 2D pattern spectra descriptors applied to CBIR systems[END_REF] for a discussion). The LPS remain both rotation and translation invariant, like in [START_REF] Urbach | Connected shape-size pattern spectra for rotation and scaleinvariant classification of gray-scale images[END_REF][START_REF] Tushabe | Content-based image retrieval using combined 2D attribute pattern spectra[END_REF].

Algorithm

The system was implemented in C++. The max-tree structure was used for both MSER detection and keypoint description. The nonrecursive max-tree algorithm of [START_REF] Nistér | Linear time maximally stable extremal regions[END_REF] was used. This allows concurrent computation of the MSER stability function (Eq. ( 1)), the area attribute and the moment of inertia, and the MSER. In order to distinguish between descriptors based on dark and light pattern spectra, an indicator value 2 is appended to every maximal MSER descriptor, and 0 for the minimal MSERs. The complete method is as follows:

• Compute the max-tree and min-tree according to [START_REF] Nistér | Linear time maximally stable extremal regions[END_REF].

• As the tree is built, compute the area A(•), moment of inertia I(•) and the stability function q(•) for each node n k,i . • During the tree computation, select the local minima of q(L k,i ) and q(L k,i ), forming the sets of maximal and minimal MSER regions {maxMser } and {minMser }. LPS MAP@5 LPS P@1 SIFT MAP@5 SIFT P@1 (f)

Fig. 2:

The mean average precision at 5 (MAP@5) and precision at 1 (P@1) for ucid5-ucid1 datasets for varying category weights are shown in (a)-(e). These results are summarized in (f), with only the results for the optimal weight displayed for every dataset.

• For each node n k,i ∈ {maxMser } and the corresponding region L k,i , examine all the nodes m l,j in the subtree:

-Set the pattern spectra matrix Sn k,i to zero * Compute size class r from the area. * Compute shape class s from the corrected noncompactness. * Compute the gray level difference δ h between the node m l,j and its parent, and add δ h A(L k,i ) to Sn k,i (r, s). -Interpret the matrix Sn k,i as a descriptor vector D(n k,i ),

and append the values of A(L k,i ), n1,1(L k,i ), n2,0(L k,i ), n0,2(L k,i ), n0,4(L k,i ) and n4,0(L k,i ) to D(n k,i ).

-Append an indicator value 2 to the descriptor D(n k,i ).

• Do the same for all the nodes n k,j ∈ {minMser } (appending indicator value 0). • In addition to all the MSER descriptors, add both global pattern spectra [START_REF] Tushabe | Content-based image retrieval using combined 2D attribute pattern spectra[END_REF] corresponding to the whole image in the collection of descriptors for the image.

The resulting descriptors will have the length of 66, as we are combining a pattern spectrum of length 60, an indicator value depending on if the feature came from the max-tree or the min-tree, and 5 different normalized central moments.

DATABASE AND EXPERIMENTAL SETUP

Since the large collections of high dimensional data suffer from the "curse of dimensionality", it is needed to use approximate search and indexing schemes such as [START_REF] Datar | Locality-sensitive Hashing Scheme Based on P-stable Distributions[END_REF][START_REF] Sivic | Video Google: Efficient visual search of videos[END_REF][START_REF] Lejsek | NV-Tree: Nearest Neighbors at the Billion Scale[END_REF] in large scale CBIR. Here, we want to evaluate the performance of the new descriptor without the sideeffects of approximate search, so we designed an experimental setup performing exact search and evaluating descriptor performance. The performance of LPS descriptors is compared to SIFT [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]. Different subsets of the UCID database [START_REF] Schaefer | UCID: An Uncompressed Colour Image Database[END_REF] were used in the experiments. The whole database contains 1338 images of size 512 × 384 pixels in 262 categories of different sizes. To equalize the database entry sizes as much as possible, the number of examples per category is constant for each database subset. The chosen subsets allow observing the effects of increased database size and decreasing number of example images (subsets used datailed in Tab. 1). Only the required number of database images was taken from larger categories in order provided by the ground truth.

For all the database images, the MSER keypoint detection is performed followed by descriptor calculation (LPS or SIFT). The descriptors from all the images of the same category make the database entry for that category, with no difference made between descriptors coming from different images. A KD-Tree index [START_REF] Friedman | An algorithm for finding best matches in logarithmic expected time[END_REF] is built based on the category descriptors, and saved for performing the queries using the FLANN library [START_REF] Muja | Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration[END_REF].

We then perform a query with 1 image for every database category. Keypoints are detected and their descriptors calculated for the query image. The index performs a kNN search (k = 7) with each descriptor from the query image. All of the neighbors will cast a vote for the category they belong to as:

vote(cat (di)) = 100 (L1(di, qj ) + 0.1) × |cat (di)| w . (3)
Here, qj is the j-th query descriptor and di the i-th nearest neighbor for that descriptor. L1(di, qj ) refers to the distance between these two descriptors and cat (di) to the database category of di, with |cat (di)| being the number of descriptors. Finally, w determines the weight with which the category size will contribute.

Five categories with the highest vote scores are examined in order to evaluate descriptor performance. The measures we used are LPS ucid5 MAP@5 SIFT ucid5 MAP@5 LPS ucid4 MAP@5 SIFT ucid4 MAP@5 LPS ucid3 MAP@5 SIFT ucid3 MAP@5 Only the highest precision per dataset is shown.

-4 % -2 % 0 % 2 % 4 % 6 % 8 % 1 2 3 4 5 Precision difference

Example images per category

Performance difference for 10x06 and 09x06 ucid1--ucid5 (high) ucid1--ucid5 (low) ucid5_1--ucid5 (high) ucid5_1--ucid5 (low) Fig. 4: A comparison between LPS using 10 × 6 and 9 × 6 binning. The difference in highest and lowest achieved precision (for w ∈ [0.0, 1.0]) between the two descriptor versions is shown for the examined datasets (positive difference in favor of 10 × 6, and negative for 9 × 6).

mean average precision at 5 (MAP@5) and precision at one (P@1). All experiments were performed for a w from range [0.0, 1.0] (like in Fig. 2(a)), but to carry out an unbiased comparison, only the highest MAP@5 and P@1 are taken into account for each descriptor when the results are summarized.

ANALYSIS OF THE RESULTS

We compared the performance of SIFT with that of our LPS descriptor. The results for ucid5 through ucid1 for a (reduced) range of weights w and the best LPS and MSER parameters are shown in Fig. 2, with a summary in Fig. 2(f). Note that the category weight w disappears as a parameter when the descriptors are aggregated.

Both the number of categories and the number of examples per category influence the performance. To investigate the influence of decreasing only the number of examples, we repeated the experiments on subsets of ucid5-ucid3, using less examples per category. These results are shown in Fig. 3. As expected, the performance of both descriptors declines both for increasing the number of categories, and decreasing the number of examples while keeping the category number constant. However, the rate of precision decline w. r. t. number of examples per category looks moderately lower for the LPS than for SIFT, indicating that using less examples with LPS than with SIFT may be sufficient to achieve desired performance.

Based only on Fig. 2(f), our descriptors give comparable results to the SIFT descriptors for ucid5 -ucid3, and perform slightly worse for ucid2. However, these results should be considered jointly with the experiments summarized in Fig. 3. When we decrease the number of examples in the ucid5 and ucid4 datasets (making the classification problem harder), the LPS descriptors clearly outperform SIFT on these datasets. On the last subset, ucid1, our method is significantly outperformed by SIFT descriptors. However, this is the dataset with the largest number of categories but only one example per category. It is known that a certain minimal number of examples (growing with the increase in the number of categories) is required, otherwise the results of classification using such a model can depend on chance. Because of this, the results on this subset are not as reliable as the results on ucid5-ucid2, and further testing on larger databases (including varying the number of categories for a constant number of examples) has to be done.

We also looked into an alternate set of parameters, producing a shorter descriptor. The performance comparison of a LPS using a 10 × 6 and a 9 × 6 binning is shown in Fig. 4. The comparison is shown for varying number of example images, on ucid5-ucid1 datasets as well as on the ucid5 dataset with a varying number of examples. It can be seen that the best performance achieved is very close for both descriptors (the full lines), not being clearly in favor of any choice of parameters. This justifies using a shorter version of the descriptor, if performance speed (caused e. g. by a large number of regions used) is an issue. However, the dashed lines indicate that the larger descriptor is more stable for varying category weights. Even if this is no longer a parameter in an approximate search setup, we expect it to be beneficial to descriptor performance and thus chose to work with the larger, 10 × 6 version.

Apart from their performance, the proposed LPS descriptors have another advantage. In addition to the description calculation process being slightly faster for the pattern spectra than for the SIFT descriptors, our descriptors length is only 52% of the length of SIFT (47% in case the shorter descriptor is used). Using the LPS descriptors gives roughly a 4 times gain in query speed over the SIFT descriptors on an index of the size 262 (ucid1 dataset). This suggests that (especially in large scale CBIR systems), we can use more example images in order to enhance the precision, while still performing faster than SIFT.

CONCLUSIONS AND FUTURE WORK

LPS outperforms SIFT on two datasets while keeping comparable results on the others, all with a descriptor half the size of SIFT. It is probable that better results could be achieved by combining the current pattern spectrum with pattern spectra based on other shape attributes, like in [START_REF] Tushabe | Content-based image retrieval using combined 2D attribute pattern spectra[END_REF].

As the current LPS is only rotation and translation invariant, we are working on improving the scale-invariant LPS to reach the performance of the current descriptor. Further experiments have to be carried out to compare the performance of the scale-invariant and scale-variant LPS on a database with a focus on scale change. Algorithmic improvements are also being considered [START_REF] Bosilj | Local connected 2D pattern spectra descriptors applied to CBIR systems[END_REF].

Due to the promising results on the subsets of the UCID dataset, we want to perform more extensive testing, with a large scale CBIR system using approximate search. Comparing LPS using a different distance, or even a divergence (e.g. [START_REF] Mwebaze | Divergencebased classification in learning vector quantization[END_REF]), should be considered as the L1 distance was designed to compare vectors of scalar values.

Fig. 3 :

 3 Fig. 3: Summarized experimental results on ucid5 (using 5-1 examples per category), ucid4 (4-1 examples) and ucid3 (3-1 examples). Only the highest precision per dataset is shown.

Table 1 :

 1 Subsets of the UCID database used in experiments.

		# categories /	categories
		examples	selected
	ucid5	31 / 5	all UCID categories
			with ≥ 5 examples
	ucid4	44 / 4	all UCID categories ≥ 4
	ucid3	77 / 3	all UCID categories ≥ 3
	ucid2	137 / 2	all UCID categories ≥ 2
	ucid1	262 / 1	all UCID categories
	will produce a local pattern spectrum (LPS), containing only infor-
	mation derived from the region represented by that node.

preprint at people.irisa.fr/Ewa.Kijak/preprint/ismm. pdf


ELICO, EA Thierry Lafouge

Abdelatif Agouzal

The Source--effort Coverage of an Exponential Informetric Process

Keywords: Inverse power distribution, mathematical adjustment, effort function, entropy, exponential distribution

published or not. The documents may come

The source-effort coverage of an exponential informetric process

INTRODUCTION

Many statistical methods exist to model problems in humanities and social sciences, depending on the available quantitative information. One of the traditional models consists in adjusting different types of theoretical distributions to the empirical distributions that are being studied, as long as the empirical data allows it. The values of the parameters for the adjusted distributions then provide all the elements needed for a comparison. The adjustment method is implemented in three stages: --choosing a theoretical model (exponential, inverse power, inverse power with cutoff, stretched exponential…) --choosing a method to calculate the adjustment parameters (method of moments, linear least squares method, maximum likelihood estimation method…) -- choosing a statistical test to validate the theoretical model (the khi2 test, the Kolmogorov--Smirnov test…). For the adjustment to be completely relevant, the theoretical model's parameters must be easy to interpret, allowing users to gain a better understanding of the observed phenomenon.

In the field of informetrics, we have come to observe many statistical regularities in the production and usage of information. These regularities have led researchers to work on models, using the steps described above. In practice, the characteristics of the production function don't vary much. The observed distributions are generally asymmetric, strongly decreasing with a long tail. The inverse power model, known as the lotkaian model (Egghe,

! = ! ! !" ! =
If we consider that S and I are known ! > ! > 0 and that f is a known theoretical model, then creating a mathematical source--item adjustment consists in finding a necessary and sufficient condition for f to fulfil the condition (3). The term 'mathematical adjustment' used here designates a method introduced by Egghe within the field of informetrics to characterize inverse power distributions. It carries a different meaning from the adjustment method that is commonly used in statistics, as we mentioned in our introduction This problem was solved within the framework of Lotkaian informetrics [START_REF] Egghe | The source--item coverage of the lotka function[END_REF]. We can review the obtained results by distinguishing one case -where N, the maximum item per source density, is infinite -from the more realistic case that interests us -where N is finite, for both distributions (1) and ( 2). (i) Exponential Distributions [START_REF] Lafouge | The source--item coverage of the exponential function[END_REF] (a) N is infinite The adjustment conditions (3) are met by (2) if and only if:

! = ! !!! (5) ! = ! ! !!! (6)
α depends only on the ratio !, unlike C which depends on S and µ. (b) N is finite

The adjustment conditions (3) are met by (2), ! > 1, if and only if:

! < ! !!! (7)
We therefore construct f by first calculating ! ≠ 1, obtained by solving a numerical equation with one unknown.

! ! ! - !"# !! !!! !!!!.! !!!! !!!"# (!! !!! ) ( 8
)
Where α is the parameter that verifies the inequality (7), with:

! = !.! !!!"# (!!. !!! ) (9)
We can find equations ( 5) and ( 6) by making N tend toward ∞ in ( 8) and ( 9). (ii)

Inverse Power distributions [START_REF] Egghe | The source--item coverage of the lotka function[END_REF]

) (a) N is infinite When ! ≤ 2 I doesn't exist.
If α is greater than 2, then the adjustment conditions (3) are met if and only if:

! = 1 + ! !!! = 2 + ! !!! (10) ! = !.! !!! (
11) α depends only on the ratio !, unlike C which depends on S and ! The value 2 of ! plays a pivotal role since the moment of order 1 can't exist if

! ≤ 2. (b) N is finite
Two cases exist: --N ≥ 1 always exists when α ≤ 2, thus (1) meets condition (3).

--if α ˃ 2, the previous conclusion is valid if and only if:

2 < ! < 1 + ! !!! = 2 + ! !!! (12)
We then construct f by calculating N, which is obtained by solving a numerical equation with one unknown. Two cases are possible:

1. ! ≠ 2 !!! ! ! (!!!) ! !!! -! !!! + 1 - !!! ! ! !!! = 0 (13)
Where α is a parameter verifying condition (12) with:

! = !.(!!!) ! !!! !! 2. ! = 2 !" ! + ! !.! - ! ! = 0 (

(iii) Discussion

The calculation of α, when N is infinite -as seen in formulas ( 5) and (10) -is obtained through an adjustment done with the famous method of moments. This method can be used for an adjustment with an exponential distribution, but it is not suitable for an adjustment with an inverse power distribution, since the latter doesn't always have a moment of order 1. The most interesting case is when N is finite. It should be noted that equations ( 8) and ( 13) - where N is the unknown and α is the parameterdepend only on the average number of items produced by a source. In the Inverse power distribution case, when N is finite or infinite, the α = 2 case is a breaking point. In these two examples, an existence theorem is used to solve the finite case -see section II.3.1.1, "the Theorem of Existence for the Size--frequency Function" in [START_REF] Egghe | Power Laws in the Information Production Process: Lotkaian Informetrics[END_REF]. This paper aims to provide additional elements to add to this important result. We will then recall the previous approach: the mathematical exponential (or power) adjustment of an IPP.

The Exponential Informetric Process and the Effort Amount

General Definition of an EIP

In this section, we assume that N (maximal item per source density) is infinite. We henceforth assume that each produced item requires a certain amount of effort. The difference between the IPP diagram (see figure 1) and the EIP diagram (see figure 2) is shown through the valuation of the arcs -for example, in order for item i 3 to be produced, source s 3 must have an effort quantified by value 3. The amount of effort needed to produce a source is generally unknown and difficult to quantify. We therefore introduce the effort function h, where h(i) is designated as the average amount of effort from a source needed to produce i items, with i= 1, 2, …. [START_REF] Lafouge | Links between entropy and production of information, characterization of informetric distribution ising the effort function, exponential informetric process[END_REF]. As previously, we work in continuous mode and define an exponential informetric process where F denotes the average quantity of effort supplied by sources to produce all the items. This paper develops the theory by using the size--frequency function ! !!! where α is a positive number and h is an effort function. More precisely, we have a set of functions called EF: !" = ℎ: 1, ∞ → ℝ ! strictly increasing and unbounded.

exp -!. ℎ ! . ℎ ! !" < ∞ ! !
We can recall results obtained in previous studies [START_REF] Agouzal | On the relation between the maximum entropy principle and the principle of least effort : The continuous case[END_REF]: with h being an admissible effort function, there exists a real !(ℎ) ≥ 0, so that:

∀ ! > ! ℎ exp -!. ℎ ! . ℎ ! !" < ∞ ! !
We thus call the size frequency function f an 'exponential informetric process':

! ! = !. exp -!. ℎ ! ! ∈ 1, ∞ , ! ∈ ℝ ! , ℎ ∈ !", ! > ! ℎ
(15) The corresponding probability density function v is:

! ! = !.!"# (!!.! ! ) ! , ! ∈ 1, ∞ (16) S is the number of sources: ! = !. exp -!. ℎ ! !"
! ! And F is the average amount of effort produced by the exponential informetric process:

! = !. exp -!. ℎ ! . ℎ(!) !" ! ! (17)
The amount of effort F is necessarily finite, since ! > !(ℎ). It is entirely determined by the density function !, which governs the process. The amount of produced items is written as:

! = !. exp -!. ℎ ! . ! !" ! ! (18)
The amount of items is not necessarily finite. There can therefore be an infinite amount of items produced by a finite amount of effort.

In the mathematical theory of information, the amount of effort and entropy are linked [START_REF] Weaver | Théorie mathématique de la communication[END_REF]. When we calculate the ! ! entropy of the v process, we can prove that:

! ! = -!" ! ! + ! ! !
(19) An exponential informetric process therefore has a finite entropy. We would have been able to define an admissible function with entropy. m is defined as the average amount of effort produced by a source:

! = ! !
(20) The average number of items produced by a source, when this number exists, is characteristic of an IPP. Similarly, the amount of effort needed to produce a source is characteristic of an EIP. Unlike for IPPs, this average exists, for EIPs, as soon as α is higher than 1, the latter being always verified for inverse power distributions.

Examples 3.2.1 Exponential Case

In this case, according to equation ( 2), the effort function is ℎ ! = ! -1, ! ℎ = 0 and the amount of effort is:

! = ! -! (21)
This formula is valid whether N is finite or infinite.

3.2.2: Inverse Power Case

In this case, according to equation (1), the effort function is ℎ ! = !" ! , ! ℎ = 1. We now assume that ! > 1 The amount of effort is:

1. When N is infinite: So, following the integration:

! = !. exp (-!. ! ! Ln(!))!" = ! !!! ! !" (! !!! ! !
). !"(!)!" (22) But, according to equation ( 16):

! = ! (!!!) ! (23) ! = !. (! -1) (24)
The amount of effort is therefore:

! = ! (!!!)
(25) Hence the result:

! = 1 + ! ! = 1 + ! ! (26)
The pivotal role of 2 as a value of α is shown through the following implications: --! < 2 implies that the amount of effort needed to produce all the items is higher than the number of sources, --! = 2 implies that the amount of effort needed to produce all items is equal to the number of sources, -- ! > 2 implies that the amount of effort needed to produce all items is lower than the number of sources. According to ( 24) and ( 25), entropy ( 19) is written as:

! ! = -ln ! -1 + ! !!!
(27) We find the Lotka function's [START_REF] Yablonsky | On fundamental regularities of the distribution of scientific productivity[END_REF] expected result - the decrease of entropy, according to α. When α ≥ 2, according to (10), the amount of effort ( 25) is:

! = ! ! . (! -!) (28)
The amount of effort is calculated according to I and S in the same way as for the exponential case. In this case, we have:

! < ! -! The amount of effort needed during the production of an EIP that is governed by an inverse power (with α ˃ 2) is therefore smaller than an EIP governed by an exponential. This characteristic fits with the properties of informetric inverse powers distributions, as in: the more items a source has, the higher the probability that it will produce a new item.

2. N is finite Equation ( 22) is written as:

! = ! !!! . !" ! . ! !!! + ! !!!
(29) Application: calculating the amount of effort needed to produce words in a text. To illustrate this notion, we use the typical case of a text's word production, well known in informetrics as Zipf's law. In this case, the number of S sources corresponds to the size of the lexicon. The total number of words in the text is the number of produced items, known as I. In (29), N designates the maximal frequency of a word in a text and is generally very high (often consisting of grammatical words such as "the" in the English language). Furthermore, we know that the distribution (frequency rank) of words in a text obeys Zipf's law:

! ! = ! ! ! ! ∈ 1, ! , ! > 0, ! ∈ ℝ !
! and ! are linked by the following well--known relation (see, for example, II. 2.2.1 in [START_REF] Egghe | Power Laws in the Information Production Process: Lotkaian Informetrics[END_REF]

): ! = ! !!!
if N tends towards infinity and If it obeys the Zipf law, then, according to (29), the amount of effort needed to produce a text is: ! ≈ !. ! In the ideal case where β =1, the amount of effort is equal to the number of sources, i.e., to the size of the lexicon. β is generally slightly higher than 1; the effort needed to produce a text is therefore generally slightly higher than the lexicon's size. As to avoid any possible confusion, we must clarify certain points linked to the effort function when discussing this application to the production of words in a text.

Discussion on the Effort Function

The effort function supposes that each used (or produced) item has a certain "cost". In his statistic theory of language (Mandelbrot, 1953), Mandelbrot introduced a cost function. Although he doesn't mention effort functions directly, the intention remains the same:

ℎ ! = !" (!) !" (!)
(a) where V is the amount of different characters in the text and r is the word's rank (words are ranked by decreasing frequency). This function is based on the following hypothesis: the longer a word is, the higher the cost to produce it is.

This effort function has the following characteristics:

--As the number of different characters is reduced, the number of characters in words increases, and, according to (a), the amount of effort needed to produce them increases.

--The higher the rank is, the more words tend to have a large amount of characters and the rarer they are. According to (a), more effort amount is needed to produce them as the rank increases. Knowing the entropy ! and the amount of effort !, Mandelbrot then calculated the probability !(!) of a word by minimizing the average cost of information, ! = ! ! (see for example the proof in [START_REF] Mitzenmacher | A brief history of generative models for power law and lognormal distribution[END_REF]).

In this case, the effort function depends on the ranking of the frequency of words and it contributes to prove Zipf's law. An inefficient solution would have been to say that the cost of producing a word was proportional to the logarithm of a word's length.

An effort function partly defines an EIP . The result in section 4 legitimizes this introduction.

The Necessary and Sufficient Condition for the Existence of an Exponential Informetric Process

The exponential informetric process is defined by 4 parameters: --! > 0 as the number of sources, --! > 0 as the amount of effort needed to produce the process, --h as the effort function that characterizes the process, --! > 1, as the maximum item per source density. We are looking for a necessary and sufficient condition, so that C ˃ 0 and ! > 0 can exist as: 30) play the same role as equations (3) in section 2. This is why we can talk about a generalisation. Unlike section 2, N is a parameter that is supposedly known and that characterizes the process. It measures what is often referred to as the long tail of inverse power distributions. Here, the amount of effort F is what's supposedly known, whereas the number of produced items, I, is not. At first glance, the posed problem seems unrealistic since F, unlike I, is not observable. However, studying the existence of an EIP remains interesting since it allows us to add to the previous results and to develop the notion of the amount of effort needed to produce a process, itself governed by an exponential or power--law distribution. Comment Since the effort function h is a strictly increasing positive function, with ! > 0, this implies that !. exp (-ℎ ! ) is a decreasing distribution. At first, we do not need to consider h as being admissible.

! = !. exp -!. ℎ ! !" ! = !. exp -!. ℎ ! . ℎ(!)!" (30) Equations (
1. N is finite With m to solve problem, (30) equates to finding a necessary and sufficient condition where ! > 0 exist and solves the following equation: 30) are indeed equivalent to:

! = !"# !!.! ! .! ! !" ! ! !"# !!.! ! !" ! ! (31) Equations (
exp -!. ℎ ! . ℎ ! !" ! ! ! = exp (-!. ℎ ! !" ! ! ! = 1 ! Let N>1, for ! > 0 we define function ! ! as: ! ! ! = ℎ ! -! . exp -!. ℎ ! -! !" ! ! (
32) Solving equation ( 31) means finding α ˃ 0 so that E N (α)= 0:

! ! ! = 0 ⇔ ℎ ! -! . exp (-! ℎ ! !" = 0 ! ! ⇔ ! = exp -!. ℎ ! ℎ ! !" ! ! exp -!. ℎ ! !" ! !
To conclude, α is the solution of equation ( 33), which depends on N, h and

! = ! ! : ! ! ! = 0 ⇔ ℎ ! -! . exp (-!. ℎ ! !" -! exp -!. ℎ ! !" = 0 ! ! ! !

Proof

The Equality of (31) and the fact that h strictly increases allows us to write: exp (-!. ℎ ! ℎ 1 !"

! ! exp -!. ℎ ! !" ! ! < exp (-!. ℎ ! ℎ ! !" ! ! exp -!. ℎ ! !" ! ! < exp (-!. ℎ ! ℎ ! !" ! ! exp -!. ℎ ! !" ! ! Thus, when simplifying: ℎ 1 < ! < ℎ(!)
The calculation of the derivative is:

!! ! !" = - ℎ ! -! ! ! !
. exp -!. ℎ ! -! !" therefore, the E N function is strictly decreasing. This result highlights the fact that the average amount of effort needed to produce a source falls between the effort function's minimum and maximum. We shall now demonstrate the main result of this article. For the adjustment problem (30) to have a solution -i.e. ! existing as the unique solution to the equation E N (α) = 0 -we must give a necessary and sufficient condition, linking the effort function h, the average effort amount m and the maximal item per source density, N. Theorem 4.1 For any N ˃ 1, then there exists α ˃ 0 as unique solution so as to have E N (α) = 0, if and only if:

! = ! ! ∈ ℎ 1 , ℎ ! !" ! ! ! -1 Proof (i) Necessary Condition
According to the 4.2 lemma, E N is a strictly decreasing function, so ! > 0 implies that:

0 = ! ! ! < ! ! 0 = ℎ ! -! !" ! ! Then: ℎ 1 < ! < ℎ ! !" ! ! ! -1 (ii) Sufficient Condition
The inequality of the 4.1 lemma and the intermediate value theorem implies that there exist ! ∈ 1, ! (unique solution, since h is strictly increasing) so that m = h(y); when u ˂ y, then ℎ ! -! < 0 and ! -! > 0 when u ˃ y, then:

! ! ! = ℎ ! -! . exp (-!. ℎ ! -! !" + ! ! ℎ ! -! . exp (-!. ℎ ! -! !" ! ! so we can write: lim !→! ! ! ! = -∞ . Since E N is strictly decreasing and ! ! 0 = ℎ ! -! > 0 ! !
we can therefore conclude that ! > 0, with E N (α) = 0 as the unique solution 2. N is infinite Although we aren't covering this case as a whole, two comments can be made. First, when N is infinite, we must assume that the effort function h is admissible for F and m to be finite. An important property then completes the theorem.

Lemma 4.2 If N tends towards infinity, then the function

! ! = ! ! !" ! ! !!!

tends towards infinity and is an increasing function. Proof

Since h isn't bounded, ∀ ! > 0 N so that ∀! > !, ℎ ! > ! then ℎ ! !" > ! -1 ! ! ! therefore ! ! !" ! ! !!! > ! therefore g is not bounded. The calculation of the derivative !"(!) !" = ℎ ! . ! -1 - ℎ ! !" ! ! (! -1) ! is positive, therefore g is increasing.
Discussion Before working on examples, we must think about the significance of such a result. First of all, we notice that, in the same way as for an IPP, the normalizing factor C doesn't play a part in this problem. It is entirely determined by α. Lemma 4.2 allows us to precise the results of theorem 4.1. Supposing that we are in a stable process in which the number of sources is mostly fixed, the amount of effort increases slightly. Let's suppose that the necessary condition for the existence of an EIP is verified. Then, if N -the maximum number of items a source can produce -increases over time, then the condition of existence is always verified. Let's take, as an example, the case where a relatively long text is produced. Let's suppose that the text is lengthened over time by its author. We can suppose that the size of the lexicon doesn't change very much. If the amount of effort increases slightly, the condition of theorem 4.1 remains true because of the fact that a word's maximal frequency, generally a grammatical word, becomes very high.

Examples of Processes

This theorem is now applied to the two types of distributions seen above in the context of IPPs.

Exponential Process

We shall call this method as follows: the mathematical exponential adjustment of an EIP.

1. N is finite ! = ! -! and the effort function is ℎ ! = ! -1. According to theorem 4.1, for any ! > 1, and

! = ! ! ∈ 0, !!! !
(34) α exists as unique solution to (33) :

!. exp (-!. ! -1 !" -(1 + !) exp -!. ! -1 !" = 0 ! ! ! !
According to (21), we have ! + 1 = ! ! Following calculations, we then find, the same equation ( 8) as for the mathematical exponential adjustment of an IPP. Hence (30) implies that:

! = !.! !!!"# (! !!! .!)

Remarks

Equations for IPPs and EIPs are identical, but the solved problems are different. If we call this equation Fe, it depends on three values, α, m and N, which all play different roles in each equation. If we call the unknown x, then: -- In the case of an IPP, we find a necessary and sufficient condition for the equation Fe (x, α, m) = 0 (here, x = N) to have a unique solution:

! < 1 ! -- In the case of an EIP, we find a necessary and sufficient condition for the equation Fe(N, x, m) = 0 (here x= α) to have a unique solution :

! < ! -1 2
We therefore proved the following result. Where ! > 1, ! > ! > 0, a necessary and sufficient condition for ! > 0 and ! > 0 to exist, verifying :

! = !. exp !. ! -1 !" ! = !. exp !. ! -1 (! -1) !" ! ! ! ! (36) is ! < ! !!! !!! ! < !!! ! (37)
We can illustrate this result with a numerical example. 2. Numerical example N°1 --The mathematical exponential adjustment of an EIP Let S = 5,000 F= 15,000 and N= 10 , then I = 20,000 and m= 3, we have equation ( 8) that takes the form of (38) (replacing α by x):

4! - !"# (!!!))(!!!!"!)!!!! !!!"# (!!!)
(38) Which can be solved (since (34) is true) by using the MAPPLE 17 software, for e.g. we find x≈ 0.239=α (35) implies that C ≈ 1, 352. To conclude, the exponential distribution is:

! ! ≈ 1,352. exp -0.239. ! -1 ! ∈ 1,10 (39)
The result is coherent since the condition (7) of the mathematical exponential adjustment of an IPP is verified:

0.239 = ! < ! !!! = ! ! = 0.33 --
The mathematical exponential adjustment of an IPP We use the same values as the previous example. Let S= 5,000, I= 20,000 and α = 0.239 then equation ( 8) takes the form of (40) (replacing N by x):

0.956 - !"# !!.!"#!!!.!"# !!.!"#!!! !!.!"# !!!"# !!.!"#!!!.!"# = 0
(40) Which can be solved (since ( 7) is true) by using the MAPPLE 17 software, for e.g. we find the expected result, which is x≈ 10 = N. The result is coherent since the condition (34) of the mathematical exponential adjustment of an EIP is verified:

! = !!! ! = 3 < !!! ! = 4.5 3. N is infinite
If N tends towards infinity, then the equation is written as:

! ! . ! -! -1 = 0
With the value of α being:

! = ! ! = ! ! = ! !!! (41)
We also have:

! = ! !
!!! We obtain the same result (see 5 and 6) as for the mathematical exponential adjustment of an IPP. This result was expected since the effort function in the exponential model is the identity function. The mathematical exponential adjustment of an IPP and the mathematical exponential adjustment of an EIP are identical.

Discussion Conditions (37) for the existence of an IPP that is governed by an exponential process are complete. For the exponential case, the amount of effort does not need to be known. All that needs to be known are the 3 essential characteristics of a distribution. The inverse power case is very different, as we are about to see.

Inverse Power Process

We shall call this method as follows: the mathematical inverse power adjustment of an EIP.

1. N is finite The effort function is log u. According to theorem 4.1, for any N˃1, and

! = ! ! ∈ 0, !.!" ! !!!! !!! (
42) There exists α, solution of (33):

ln (!) ! ! ! ! !" -! 1 ! ! ! !
!" = 0 Therefore the equation to be solved is:

! !!! ! ! !!! !" ! ! . ln ! !" -!. ! !! ! ! !" = 0 Following calculations: ! !!! Ln N . ! !!! + 1 -! !!! ! !!! + ! !!! ! = 0
(43) We also have, according to (30), the normalizing coefficient:

! = !.(!!!) !!! !!! (44) 2. Numerical example N°2
Let S =10,000, F=6,000 and N = 10; we have and ! = ! ! and: 43) takes the following form (replacing α by x): 42) is verified, this equation can be solved by using the MAPPLE 17 software, for e.g. we find x ≈ 2.47 = α. (44) implies that C ≈ 15,215. To conclude, the power distribution is:

!.!" ! !!!! !!! = 1.5584 Equation (
!" !" .!" !!! !!! + 1 -10 !!! . ( !.! !!! + ! (!!!) ! ) = 0 (45) Since condition (
! ! ≈ 15,215. ! ! !.!" ! ∈ 1,10 (46)
Numerical example N°3: Let S=5,000, F=7,000 and N=50 we have m=1.4 !. !" ! -! + 1 ! -1 = 2.991 Equation ( 43) takes the following form (replacing α with x): 42) is verified, this equation can be solved by using the MAPPLE 17 software, for e.g. we find x ≈ 1.46 = α. (44) implies that C ≈2,679. To conclude, the power distribution is:

!" !" .!" !!! !!! -1 -50 !!! . !.! !!! + ! !!! ! = 0 (47) Since condition (
! ! ≈ !,!"# ! !.!" ! ∈ 1,50 (48
) 4. N is infinite If N tends towards infinity, then ( 43) is written as follows:

! 1 -! + 1 (1 -!) ! = 0 With the value of α being: ! = 1 + ! ! = 1 + ! !
(49) We find the expected result (see ( 26)) for the value of α. Furthermore, we deduce, based on (30), that: ! = !. (! -1) If α ˃ 2, then, according to (28), the equation ( 49) is written as follows:

! = 1 + ! ! -! and ! = !. ! ! -! i.
e., the same result (see ( 10) and ( 11)) as for a mathematical inverse power distribution adjustment.

Discussion

In the case where N is infinite, we demonstrated the formula ! = 1 + ! ! . This formula is true, whatever α's value. The more the effort amount F decreases (or, the more entropy decreases), the more α increases. This means that the gap widens between a large number of sources that produce little and a small number of sources that produce a lot. Unlike in the case of an (IPP), the value α =2 is not a breaking point. In the two numerical examples that were considered, when we compare the value of α, solution to the equation, it is roughly equal to 1 + ! ! Example 2: exact calculation of α , 2.47, rough formula α ≈ 2.67 Example 3: exact calculation of α , 1.46, rough formula α ≈ 1.7 We can compare the necessary and sufficient conditions for the existence of an exponential process and of an inverse power process. For N ˃ 1, the inequality is as follows:

!.!" ! !!!! !!! ≤ !!! !
This inequality implies that if the mathematical power adjustment of an EIP is verified, then the same applies for a mathematical exponential adjustment. This result concurs with the mathematical adjustment of an IPP (see theorem 5 [START_REF] Lafouge | The source--item coverage of the exponential function[END_REF]). If N is infinite, it is worth making a parallel between the coefficient α of the exponential (41) and of the inverse power (49).

! =

Discussion: Limits and Contributions

The numerical examples used in this article weren't drawn from real situations. It is currently difficult for us to present such real results. The crucial problem lies in knowing the amount of effort -which is unknown and tied to the effort function, itself also unknown, as was shown above. We would need to perform calculations in a real life setting and choose a realistic value for F. We could then compare it with results obtained using the classic Lotkaian case.

The main contribution in creating an EIP lies in the fact that the EIP highlights the connectionthough already known -between the amount of effort (or entropy (see ( 19)) as understood by Shannon) and informetric distributions. Lotkaian distributions serve to explain many statistical regularities. It therefore seems important to draw attention to two points:

--the role of the logarithm effort function. In a previous article (lafouge T and Smolczewska 2006), we showed that, if h is an effort function -positive, strictly increasing and unbounded -that verifies the relation

lim !→! ℎ(!) ln (!) = ! ! > 1
then h is admissible and the amount of effort is finite. Unfortunately, such a condition is not necessary.

--We also want to highlight the pivotal point of ! = 2, since it corresponds to the case where the amount of effort is equal to the number of sources.

Conclusion

Both models are compared: the mathematical adjustment of an IPP initiated by Egghe, and the mathematical adjustment of an EIP, presented in this article. This is relevant only if the distribution is of the power or exponential type.

When N is infinite, the mathematical exponential adjustments of an IPP and of an EIP is identical.

When N is infinite and α ˃ 2, the mathematical power adjustment of an IPP and of an EIP are identical.

Results differ in a realistic case, when N is finite. In the exponential case, the mathematical adjustment of an EIP completes the result previously found for an IPP. This is due to the fact that the effort function is the identity, therefore ! = ! -! whatever the value of N. In the power case, the value α = 2 is not a breaking point for an EIP, whereas it is for an IPP. It would be interesting to study other effort functions [START_REF] Lafouge | An interpretation of the effort function trough the mathematical formalism of exponential informetric process[END_REF] in order to expand on the notion of EIP adjustments.

  14)Where α is a parameter verifying condition (12) with: ! = ! !" (!)

Figure 2 :

 2 Figure 2: Diagram of an Information Production Process with an effort function: the EIP. ℎ ∈ !" is called an admissible effort function if ! exists as a real positive number verifying the condition:


Nicolas Boutry

Thierry Géraud

Laurent Najman
email: l.najman@esiee.fr

How to make nD images Well-composed without interpolation

Keywords: Digital Topology, nD images, Well-Composed Sets, Mathematical Morphology

  L'archive ouverte pluridisciplinaire

INTRODUCTION

Well-composedness has been proposed as a practical way to deal with the well-known connectivities paradox encountered with the 4and 8-connectivities [START_REF] Rosenfeld | Sequential operations in digital picture processing[END_REF][START_REF] Kong | Digital topology: Introduction and survey[END_REF][START_REF] Latecki | Wellcomposed sets[END_REF]: the 2nand (3 n -1)connectivities are equivalent in a well-composed image [START_REF] Rosenfeld | Connectivity in digital pictures[END_REF][START_REF] Tustison | Topological well-composedness and glamorous glue: A digital gluing algorithm for topologically constrained front propagation[END_REF]. Furthermore, well-composed images enjoy many more properties: the Jordan Separation theorem [START_REF] Latecki | Wellcomposed sets[END_REF] holds true, we can design much simpler thinning algorithms [START_REF] Marchadier | Thinning grayscale well-composed images[END_REF], make the Euler characteristic locally computable [START_REF] Latecki | 3D well-composed pictures[END_REF], simplify graph structures resting from skeleton algorithms [START_REF] Latecki | Wellcomposed sets[END_REF], and simplify the algorithm of the marching cubes [START_REF] Tustison | Topological well-composedness and glamorous glue: A digital gluing algorithm for topologically constrained front propagation[END_REF][START_REF] Etiene | Topology verification for isosurface extraction[END_REF].

Two approaches exist to make binary images well-composed. The first one is to keep the original space of the image and to change some of the values of the initial image in such a way that the modified image becomes well-composed [START_REF] Siqueira | Topological repairing of 3D digital images[END_REF]. The second is to make an interpolation to preserve the topology of the original image [START_REF] Latecki | Well-composed sets[END_REF][START_REF] Stelldinger | 3D object digitization: Majority interpolation and marching cubes[END_REF]. However this second approach needs a subdivision of the original space and measurably increases the computational costs of the algorithms.

In this paper, we propose a fast method that produces a well-composed image by modifying the original values. The plan of the paper is the following. Section 2 is a short reminder on well-composedness in nD for sets, binary images, and gray-valued images. Section 3 describes an algorithm producing well-composed images. Before concluding the paper, we illustrate with a 2D application to text detection.

STATE-OF-THE-ART

Latecki et al. introduced in [START_REF] Latecki | Wellcomposed sets[END_REF] the notion of well-composedness for 2D sets. A 2D set is well-composed iff it does not contain any critical configuration 0 1 1 0 or 1 0 0 1 . Then Latecki extended the well-composedness to 3D sets in [START_REF] Latecki | 3D well-composed pictures[END_REF]. A 3D set is well-composed iff it does not contain any critical configuration ot type 1: 0 1 1 0 , or of type 2: 1 0 0 0 0 0 0 1 and 0 1 1 1 1 1 1 0 , modulo rotations and axial symmetries.

We have proposed in [START_REF] Boutry | How to make well-composed images in nD in a self-dual way with a front propagation algorithm[END_REF] an extension to dimension n of the notion of well-composed sets and images. Let us now recall this extension. With z a point in Z n and F = {f 1 , . . . , f k } a subset of the canonical basis B of Z n , we define the block associated to the couple (z, F) by:

S(z, F) =    z + card(F ) j=1 λ j .f j with λ j ∈ {0, 1}    , (1)
Moreover, we call a block of D ⊆ Z n any element of the set:

B(D) = S(z, F) ∃z ∈ D, ∃F ⊆ B, S(z, F) ⊆ D .
(2) Finally, two points p and p are said antagonist in a block S iff they maximize the Euclidian distance between two points in the block S.

A set X ⊆ Z n contains a primary critical configuration of dimension k iff there exists a block S of dimension k ∈ [2, n] such as X ∩ S = {p, p } where p and p are antagonist in S. A set X ⊆ Z n contains a secondary critical configuration of dimension k iff there exists a block S of dimension k ∈ [2, n] such as X c ∩ S = {p, p } where p and p are antagonist in S. Then a set is said well-composed iff it does not contain any critical configuration.

Let D ⊆ Z n be the domain of the image. For n = 2, Latecki et al. defined in [START_REF] Latecki | Wellcomposed sets[END_REF] a well-composed image u : D → Z as an image whose for any λ ∈ R, the upper threshold sets

[u ≥ λ] = {x ∈ D u(x) ≥ λ} and the lower threshold sets [u ≤ λ] = {x ∈ D u(x) ≤ λ} are well-composed.
This definition can straightforwardly be extended in nD [START_REF] Boutry | How to make well-composed images in nD in a self-dual way with a front propagation algorithm[END_REF]. Latecki also introduced a characterization of a well-composed

2D image u = a b c d : u is well-composed iff iv(a, d) ∩ iv(b, c) = ∅, where the interval between a and b is denoted by iv(a, b) = [min(a, b), max(a, b)].
We have extended in [START_REF] Boutry | On making nD images well-composed by a self-dual local interpolation[END_REF][START_REF] Boutry | How to make well-composed images in nD in a self-dual way with a front propagation algorithm[END_REF] this characterization to nD images: u is well-composed iff for any block S and for any p ∈ S:

iv(u(p), u(p )) ∩ span(u(p ) p ∈ S \{p, p }) = ∅, (3) with p = antag S (p) and span(A) = [min(A), max(A)], ∀A ⊆ R.
Several methods have been proposed to obtain wellcomposed images: the interpolation methods [START_REF] Boutry | How to make well-composed images in nD in a self-dual way with a front propagation algorithm[END_REF][START_REF] Stelldinger | 3D object digitization: Majority interpolation and marching cubes[END_REF][START_REF] Gonzalez-Diaz | Well-composed cell complexes[END_REF] which increase the size of the domain of the original image, and the repairing method of Siqueira [START_REF] Siqueira | Topological repairing of 3D digital images[END_REF], i.e., a method which selects an image close to the original one and which is defined on the same domain. However, the method of Siqueira works only on binary images and is restricted to the 2D and the 3D cases. The goal of this paper is to extend on this previous work, and we propose a method that produces, without any interpolation, well-composed gray-valued images in nD.

AN INCREASING PROCESS PRODUCING

WELL-COMPOSED IMAGES

Principle

Let u : D → Z be a given image. We want to find a wellcomposed image u * which minimizes the deformation of u,

u * = arg min v { ||v -u|| 1 v is W.C. } (4)
However, to the best of our knowledge, such a combinatorial problem does not have a solution reachable in a reasonable time. To find an approximate solution to this problem, we propose to iteratively select critical configurations and correct them, one by one. To prevent oscillation, we impose that, at each step of the algorithm, the current solution is greater than the previous one. Our process is thus increasing.

As we modify a critical configuration, our algorithm is local, in the sense that we only need to look at a block and modify the pixel in the block. However, the modification of the value of a given pixel can create a novel critical configuration in its neighborhood. Hence, there is potentialy a propagation effect, and thus several passes on the image are in principle necessary to achieve convergence.

Due to this propagation effect, the convergence of the algorithm is only ensured if the process is increasing. Indeed, if we allow the modifications to either decrease or increase the image, then oscillation effects could appear.

Correction Step

We want to correct a given critical configuration in the block S ∈ B(D). By definition of a critical configuration, there exists two points p ∈ S, p ∈ S with p = antag S (p), verifying:

iv(u(p), u(p )) ∩ span{ u(q) q ∈ S \ {p, p } } = ∅. (5)
Then two cases are possible. Either we have: max(u(p), u(p )) < min{ u(q) q ∈ S \ {p, p } }, [START_REF] Marchadier | Thinning grayscale well-composed images[END_REF] and we set p * ← arg max q { u(q) q ∈ {p, p } } and u(p * ) ← min{ u(q) q ∈ S \ {p, p } }, or we have: max{ u(q) q ∈ S \ {p, p } } < min(u(p), u(p )), [START_REF] Latecki | 3D well-composed pictures[END_REF] then we set p * ← arg max q { u(q) q ∈ S \ {p, p } } and u(p * ) ← min(u(p), u(p )). In both cases, u has been made well-composed on S.

m 1 ← min(u(p), u(p )) M 1 ← max(u(p), u(p )) m 2 ← min{ u(p ) p ∈ S \ {p, p } } M 2 ← max{ u(p ) p ∈ S \ {p, p } } /* Primary case: */ if M1 < m2 then p * ← arg max{ u(q) q ∈ {p, p } } u(p * ) ← m2 /* Secondary case: */ if M2 < m1 then p * ← arg max{ u(p ) p ∈ S \ {p, p } } u(p * ) ← m1
return p *

Convergence

The convergence of the method is easy to prove. Indeed

Proposed Algorithm

Given the correction step, the algorithm is straightforward, it is detailed in Algorithm 2. It proceeds in two steps. First, the initialization step detects all the critical configurations of the threshold sets {[u ≥ λ]} λ on D and enqueue them into Q. Second, the correction step solves one by one the critical configurations listed into Q using Algorithm 1 and enqueue the new critical configurations which appeared in the neighborhood of the modified value. This algorithm iterates until there is no longer any critical configuration in D; the resulting image u is then well-composed.

Experimental Results and Complexity of the 2D Case

We used the test set of 100 natural images of the Berkeley image database [START_REF] Martin | A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics[END_REF]. Their sizes are (sx, sy) with sx = 481 and sy = 321 pixels or the converse. We cropped each image with ten different windows (for each image) to obtain images of various sizes. The size (newsx, newsy) of the crop window is randomly chosen into 2, sx × 2, sy and its position is randomly chosen into We experimentally assessed the percentage of critical configurations contained in a given image. Fig. 2 shows that between 0.88% and 24.84% of the domain of the original images are covered by critical configurations. From a statistical point of view, a image contains on average 0.1246(±0.036) critical configuration by pixel. It is rare to have a wellcomposed image.

Queue initialization. To initialize the queue of critical configurations, we simply have to detect among the (newsx -1) × (newsy -1) blocks which one contains a critical configuration, and in this case we insert it in the queue Q. Each detection and each insertion in the queue is in constant time. This implies that the initialization step in linear time relatively to the size of the image.

Correction process. Concerning the correction step, we had to proceed to c corrections by pixel, with c ∈ [9.10 -3 , 0.2386]. From a statistical point of view, an average number of 0.1203(±0.0348) corrections by pixel has been observed. Numerical experiments show that the correction step is linear on average with respect to the image size. The number of corrections by initial critical configuration is not a constant: it can be seen on Fig. 3 that the number of corrections is between m = 80% and M = 104% of the number of initial critical configurations. Indeed, a given correction can repair several critical configurations at the same time, which explains that m is less than 100%. Conversely, the propagation effect is responsible for M being greater than 100%. Statistically, we obtain a mean ratio of 0.965764(±0.014) corrections by initial critical configuration.

Detection of the direction of the propagation. For each processed correction, there exists only one position p ∈ D such as u(p) is modified in the image, and then the propagation is possible in a bounded number of blocks, i.e., in the blocks containing p. This means that the number of blocks processed in the detection step is proportional to the total number of corrections. Since the correction step is in linear time, so is the detection step.

Complexity. Since the 3 steps of the algorithm are in linear time with respect to the initial number of critical configurations, the complete algorithm is in linear time with respect to the size of the image (in number of pixels).

ILLUSTRATION AND CONCLUSION

We illustrate the interest of well-composedness to text detection with the morphological Laplacian in 2D. Let us recall that the morphological Laplacian L of a given image u is defined as L se (u) = δ se (u) + ε se (u) -2u where se is a given structuring element. The contours of u are the zero-crossing of the Laplacian. As they are boundaries of level-sets of the grayscale image, the zero-crossing are closed curves. We can set the gray-level of a given contour to the mean of the gradient of the original image along the contour.

Without correction of the well-composedness, it can be seen on Fig. 4b and Fig. 4d that some characters are broken into several connected components. If we apply the proposed process on the Laplacian image, we observe that the contours are simple. In practice, it can be seen on Fig. 4c and Fig. 4e that the correction repairs many contours. In conclusion, we have presented a new algorithm that produces well-composed images without interpolation. Compare to the interpolation methods, the proposed algorithm is faster and less memory consuming. It can be seen as a natural extension of the algorithm of topological repair of Siqueira et al. [START_REF] Siqueira | Topological repairing of 3D digital images[END_REF] to gray-valued images.

Future work will apply the methods to segmentation problems, including text detection in natural images, where first tests are encouraging. Another research direction is to take advantage of the natural hierarchy provided by the closed contours of the zero-crossing of the Laplacian. This hierarchy is yet another promising tree-based image representation that fits into the morphological framework [START_REF] Najman | A graph-based mathematical morphology reader[END_REF].

The source code of the proposed algorithm has been implemented using our image processing C++ library "Milena" [START_REF] Levillain | Why and how to design a generic and efficient image processing framework: The case of the Milena library[END_REF][START_REF] Levillain | Writing reusable digital topology algorithms in a generic image processing framework[END_REF], which is free software under the GNU Public Licence v2. Since we advocate reproducible research, this source code will be released on our web site as supplementary material (if this paper is accepted).

Fig. 1 :

 1 Fig. 1: Hierarchical representation of an image: since component boundaries are simple closed curves on well-composed images, two boundaries are either disjoint or in an inclusion relationship; thus, the delimited regions naturally form a tree.

Algorithm 1 :

 1 The correction process. SOLVECC (u, S) : p begin p ← antag S (p)

Algorithm 2 :

 2 , let us define u min = min{ u(p) | u(p) ∈ D } and u max = max{ u(p) | p ∈ D }. As the algorithm increases the function u by at least one, we have a maximum of (u max -u(p)) corrections for each p ∈ D. The total number of corrections is then inferior or equal to p∈D (u max -u(p)) ≤ (u max -u min ) × card(D). This ensures the convergence of the algorithm, since the domain of u is finite. The increasing nD algorithm. INCREASING (u) : Image /* Makes the image W.C. */ begin /* Initialization of the queue: */ for all S ∈ B(D) do if CRITICALCONFIGURATION(S, u) then PUSH(Q, S) while Q = ∅ do S ← POP(Q) /* Correction process: */ p ← SOLVECC(u, S) /* Detection of the direction of the propagation: */ for all S ∈ B(D) s.t. p ∈ S do if CRITICALCONFIGURATION(S , u) then PUSH(Q, S )

Fig. 2 :

 2 Fig. 2: Number of critical configurations as a function of the size of the image given in number of pixels.

Fig. 3 :

 3 Fig. 3: Number of corrections as a function of the number of initial critical configurations.

  (a) Original image u. (b) Zero-crossings of the original Laplacian. (c) Zero-crossings of the Laplacian modified by the increasing process. (d) Crop of (b).(e) Crop of (c).

Fig. 4 :

 4 Fig. 4: Results obtained without and with the algorithm; in (d) and (e) the connected components have been colorized.


Han Yan

Fabrice Fontaine

Olivier Bouchet

Jean-Paul Vuichard

Jean-Philippe Javaudin

Maryline Lebouc

Marie-Helene Hamon

Cedric Gueguen

Bernard Cousin

HOPE: HOme Power Efficiency System for a Green Network

Keywords: Efficient energy saving, Green networking, ZigBee, UPnP Low Power, UPnP Audio Video, Heterogeneous network, Convergence layer, Green path selection, Digital home

A home network represents an increasingly large portion of a household's electrical consumption due to the increasing number of digital home devices and the increasing complexity of the underlying communication infrastructure. Limiting a home network's power consumption is a priority for large institutions as witnessed by evolving regulation, and a priority for individual consumers wishing to reduce their electric bills. In this demonstration, we proposed a solution that aims at reducing power consumption at both the device and network level. At the device level, our system can turn the devices off when they are not in operation and quickly turn them on when they are needed. At the network level, the solution is based on a new convergence layer denoted inter-MAC, which provides a common infrastructure to the different home network paths. In particular, the inter-MAC can be used to choose a greener path. Our solution on both levels is compatible and complementary to home network energy saving.

I. INTRODUCTION

In the last decade, there has been a proliferation of connected devices in the home environment. The number of connected devices has led to a sharp increase in energy consumption. A home network [START_REF] Rose | Home networks: a standards perspective[END_REF] is a complex environment which can contain several different types of devices: Set-Top Box (STB), Home GateWay (HGW), network attached storage (NAS), laptop, power line communication (PLC) plugs and so on; which are interconnected with different kinds of connections: Wi-Fi, Ethernet and power line communication. These home network devices represent an increasingly large portion of a homes electric consumption, which in turn generates greater carbon emissions and the costs consumers more.

For these two reasons, environmental and economical, it is essential to provide an effective means of reducing power consumption, which is also transparent for the user. To do so, we propose a technical solution on two levels. The first device level solution uses an overlay control network which switches existing devices on or off according to their usage. The second network level solution allows for selecting the least amount of energy to be consumed or least radiating a data path among the available links (Wi-Fi, Ethernet, PLC etc.).

These two phases are compatible and could be combined into a single offering. The standardization process is underway, with initial contributions proposed by standards bodies (HGI [2], IEEE P1905 [3]).

II. SYSTEM ARCHITECTURE

Our HOPE system proposes two solutions for energy saving. The solution at the device level could change the power levels of each device depending on its usage in a simple network. Since our home network connections are becoming increasingly complex, one device could accommodate several connections. This is why the second solution works at the network level: it selects the greener path.

A. The device-level system

The device-level system for reducing power consumption is based on an energy control layer overlaying the home network. This energy control layer can turn off the devices or switch the devices to a very low power consumption mode when they are not in operation. Moreover, the system can automatically wake up the devices when the user needs them. During this process, all energy control messages are sent on a low-power consumption network like ZigBee [START_REF]Zigbee Specifications[END_REF] or by using a low-power consumption protocol like UPnP Low Power [START_REF]UPnP Low Power Architecture, UPnP Forum Std[END_REF].

All the different home network devices are considered HOPE nodes in our system. As shown in Fig. 1, a HOPE system is composed of two kinds of functional blocks: service blocks and low power consumption connection blocks. Service functional blocks intercept the service request required by the actual device, and then send this request through the low power consumption control layer. In our demonstration, the system is able to satisfy basic services such as an IPTV or Internet connection. Furthermore, there are several enriched multimedia services, such as audio/video sharing, which are implemented by UPnP AV [START_REF]UPnP Audio Video Architecture, UPnP Forum Std[END_REF], which demonstrates the efficiency of our energy saving system for collaborative services. Since these sharing services are collaborative services, the actual device requires more than a network connection service on the HGW: it also requires turning on a second device and activating the audio/video sharing services on the second device.

B. The network-level system

The proposed network-level system for reducing power consumption is based on a technology-independent layer, called an inter-MAC, from the Omega project [7], [START_REF] Suraci | Convergence in home gigabit networks: Implementation of the inter-mac layer as a pluggable kernel module[END_REF].

This inter-MAC convergence layer is positioned above the different MAC layer of the different technologies. The inter-MAC layer is composed of three functional planes (Fig. 2): the control plane, the data plane and the management plane. The data plane is responsible for frame forwarding. The control plane is responsible for short-term decisions related to the establishment and release of paths and the processing of upper layer requests. It is divided into several engines: QoS, Monitoring, Inter-MAC Adapter and Green Path Selection. The green path selection protocol takes into account the following three metrics: Available bandwidth, energy consumption, and radio frequency. More technical details are presented in [START_REF] Bouchet | Inter-mac green path selection for heterogeneous networks[END_REF].

III. DESCRIPTION OF DEMONSTRATIONS

In the first part of our demonstration shown in Fig. 3, the HOPE system aims to maintain the devices in a low-power consumption state when the devices are not in use. Meanwhile, if the devices are required by a service, it can be woken up by our HOPE system. For example, in the IPTV scenario, a user wants to watch IPTV on his STB. The STB is connected to the HGW through a pair of PLC plugs. When the user turns the STB on to watch IPTV, the requirement of establishing a network connection through the PLC plugs is intercepted by our system. The PLC plugs are woken up and a network connection for the IPTV service is established. When the user turns the STB off, the PLC plugs are also turned off since the connection from the HGW to the STB is not needed.

Several scenarios are presented in this section to demonstrate the efficiency of our system on enriched services.

Fig. 4 represents a heterogeneous home network configuration with Ethernet, PLC and WiFi links. The second part of our demonstration contains 4 mini PCs, which play the role of extenders; they implement the green path selection protocol. The end devices (including a PC, NAS, TV, tablet and mobile phone) are connected to these extenders. The Home Gateway connects the home network to the Internet. The idea is to highlight energy consumption reduction while maintaining satisfactory QoS for different flows, due to the green path selection protocol introduced in section II. Users can benefit from enriched home multimedia services and efficiently manage their power consumption. Our future work will study the reduction of power consumption combining both the device component level and the network level in different services in order to further reduce the total power consumption of the home network.

Fig. 1 .

 1 Fig. 1. Device-level HOPE node architecture

Fig. 2 .

 2 Fig. 2. Network-level HOPE inter-MAC architecture

Fig. 3 .

 3 Fig. 3. Device-level HOPE demonstration

Fig. 4 .

 4 Fig. 4. Network level HOPE demonstration

ACKNOWLEDGMENT

This work was supported by the French government in the framework of the FUI10 Econhome project.