Double-sided probing by map of Asplund's distances using Logarithmic Image Processing in the framework of Mathematical Morphology
Guillaume Noyel Michel Jourlin











Map of Asplund's metrics & Mathematical Morphology  





Guillaume Noyel et al. 


Guillaume Noyel, and Michel Jourlin

International Prevention Research Institute,	95 cours Lafayette,	69006 Lyon, France
Lab. H. Curien, UMR CNRS 5516,	18 rue Pr. B. Lauras,	42000 St-Etienne, France

<www.i-pri.org>

Double-sided probing by map of Asplund's distances using Logarithmic Image Processing in the framework of Mathematical Morphology
    Guillaume Noyel1 Michel Jourlin1,2
    December 30, 2023
=================================================================================================================================




We establish the link between Mathematical Morphology and the map of Asplund's distances between a probe and a grey scale function, using the Logarithmic Image Processing scalar multiplication. We demonstrate that the map is the logarithm of the ratio between a dilation and an erosion of the function by a structuring function: the probe. The dilations and erosions are mappings from the lattice of the images into the lattice of the positive functions. Using a flat structuring element, the expression of the map of Asplund's distances can be simplified with a dilation and an erosion of the image; these mappings stays in the lattice of the images. We illustrate our approach by an example of pattern matching with a non-flat structuring function.













§ INTRODUCTION




Asplund's metric is a useful method of pattern matching based on a double-sided probing, i.e. a probing by a greatest lower bound probe and a least upper bound probe. It was originally defined for binary shapes, or sets <cit.>, by using the smallest homothetic shape (probe) containing the shape to be analysed and the greatest homothetic probe contained by the shape. Jourlin et al. <cit.> have extended this metric to functions and to grey-level images in the framework of the Logarithmic Image Processing (LIP) <cit.> using a multiplicative or an additive LIP law <cit.>. Then, Asplund's metric has been extended to colour and multivariate images by a marginal approach in <cit.> or by a spatio-colour (i.e. vectorial <cit.>) approach in <cit.>.

Other approaches of double-sided probing have been previously defined in the framework of Mathematical Morphology <cit.>. The well-known hit-or-miss transform <cit.> allows to extract all the pixels such that the first set of a structuring element fits the object while the second set misses it (i.e. fits its background). An extension based on two operations of dilation (for grey level images) has been proposed in <cit.>. It consists of a unique structuring element, which is used in the two dilations in order to match the signal from above and from below.

Banon et al. <cit.> use two structuring elements obtained by two translations of a unique template along the grey level axis. They use an erosion and an anti-dilation to count the pixels whose values are in between the two structuring elements.

Odone et al. <cit.> use an approach inspired by the computation of the Hausdorff distance. They consider a grey level image as a tridimensional (3D) graph. They dilate by a 3D ball a template in order to compute a 3D “interval”. Then, for any point of the image, they translate vertically the “interval” in order to contain the maximum number of points of the function and they count this number.

Barat et al. <cit.> present a unified framework for these last three methods. They show that they correspond to a neighbourhood of functions (i.e. a tolerance tube) with a different metric for each method. Their topological approach is named virtual double-sided image probing (VDIP) and they defined it as a difference between a grey-scale dilation and an erosion. For pattern matching, only the patterns which are in the tolerance tube are selected. It is a metric defined on the equivalence class of functions according to an additive grey level shift.

In <cit.>, Jourlin et al. have introduced the logarithmic homothetic defined according to the LIP multiplication. This makes a compensation of the lighting variation due to a multiplicative effect, i.e. a thickening or a thinning of the object crossed by the light.

In the current paper, the important novelty introduced is the link between the map of Asplunds' metrics defined in the LIP multiplicative framework and the operations of Mathematical Morphology. We will show that the map of Asplunds' distances in the LIP multiplicative framework is the logarithm of the ratio between a dilation and an erosion.

This gives access to many other notions well defined in the corpus of Mathematical Morphology.

The paper is organised as follows: 1) a reminder of the main notions (LIP, Asplund's metrics, fundamental operations and framework of Mathematical Morphology), 2) the demonstration of the link between the map of Asplund's distances and Mathematical Morphology for flat structuring element (se) and for non-flat ones and 3) an illustration of pattern matching with Asplund's metric.









§ PREREQUISITES


In the current section, we remind the different mathematical notions and frameworks to be used: LIP model, Asplund's metric and the basis of Mathematical Morphology.






 §.§ Logarithmic Image Processing (LIP)


The LIP model, created by Jourlin et al. <cit.>, is a mathematical framework for image processing based on the physical law of transmittance. It is perfectly suited to process images acquired with transmitted light (when the object is located between the source and the sensor) but also with reflected light, due to the consistency of the model with human vision <cit.>.
The mathematical operations performed using the LIP model are consistent with the physical principles of image formation. Therefore the values of an image defined in [0, M[ stay in this bounded domain. For 8 bits images M=256 and the 256 grey levels are in the range of integers [0, ..., 255]. 

A grey scale image f is a function defined on a domain D ⊂^N with values in = [0,M[, M ∈. f is a member of the space  = ^D.

Due to the link with the transmittance law: T_f = 1-f/M, the grey-scale is inverted in the LIP framework, 0 corresponds to the white extremity of the grey scale, when no obstacle is located between the source and the sensor, while the other extremity M corresponds to the black value, when the source cannot be transmitted through the obstacle.


In the LIP sense, the addition of two images corresponds to the superposition of two obstacles (objects) generating f and g:

    f  g = f + g - f.g/M


From this law, we deduce the LIP multiplication of f by a scalar ∈:

    λ f = M - M ( 1 - f/M)^λ


It corresponds to a thickness change  of the observed object in the ratio λ. If λ>1, the thickness is increased and the image becomes darker than f, while if λ∈ [0,1[, the thickness is decreased and the image becomes brighter than f.

The LIP laws satisfy strong mathematical properties. Let ℱ(D,[-∞,M[) be the set of functions defined on D with values in ]-∞,M[. We equipped it with the two logarithmic laws and (ℱ(D,[-∞,M[),,) becomes a real vector space. (,,) is the positive cone of this vector space <cit.>.

There exists a colour version of the LIP model <cit.>.

The LIP framework has been successfully applied to numerous problems for industry, medical applications, digital photography, etc. It gives access to new notions of contrast and metrics which take into account the variation of light, for example the Asplund's metric for functions.






 §.§ Asplund's metric for functions using the LIP multiplicative law


Let us remind the novel notion of Asplund's metric defined in <cit.> for functions in place of sets. It consists of using the logarithmic homothetic f.

Let ^* = ]0,M[ and the space of positive images be ^*=^*^D.

Asplund's metric
Given two images f, g ∈^*, g is chosen as the probing function for example, and we define the two
numbers: λ = inf{α, f ≤α g } and μ = sup{β, β g ≤ f}. 
The corresponding “functional Asplund's metric” d_As^ (with the LIP multiplication) is:

    d_As^(f,g) = ln( λ / μ)



From a mathematical point of view <cit.>, d_As^ is a metric if the images f, g ∈^*  are replaced by their equivalence classes f^={g / ∃ k >0,  k  g = f  } and g^. 

The relation (∃ k >0,  k  g = f) is clearly an equivalence relation written fRg, because it satisfies the three properties: i) reflexivity ∀ f ∈, fRf, ii) symmetry ∀ (f,g) ∈^2, fRg ⇔ gRf and iii) transitivity ∀ (f,g,h) ∈^3, (fRg and gRh) ⇒ fRh. Let us now give a rigorous definition of the multiplicative Asplund's metric using the space of equivalence  classes ^

    ∀ (f^,g^) ∈ (I^)^2 ,    d_As^(f^,g^) = d_As^(f_1,g_1)

d_As^(f_1,g_1) is defined by eq. <ref> between two elements f_1 and g_1 of the equivalence classes f^ and g^.

The demonstration of the metric properties are in the appendix (section <ref>). 

Several examples have shown the interest of using Asplund's metric for pattern matching between a template function t: D_t → and the function f. For each point x of D, the distance d_As^ (f_|D_t(x).,t) is computed in the neighbourhood D_t(x) centred in x, with f_|D_t(x). being the restriction of f to D_t(x).  Therefore, one can define a map of Asplund's distances <cit.>.

Map of Asplund's distances
Given a grey-level image f ∈^* and a probe t ∈ (^*)^D_t, t>0, their map of Asplund's distances is:

    As_t^ f : {[                     ^* × (^*)^D_t                                 →                            (^+)^D;                             (f,t)                                 → As_t^ f(x) = d_As^ (f_|D_t(x).,t);                                   ].

D_t(x) is the neighbourhood associated to D_t centred in x ∈ D.

One can notice that the template t is acting like a structuring element.






 §.§ Short reminder on Mathematical Morphology


In this subsection we give a reminder of the basis notions used in Mathematical Morphology (MM) <cit.>.
MM is defined in complete lattices <cit.>.

Complete lattice
Given a set  and a binary relation ≤ defining a partial order on , we say that (,≤) is a partially ordered set or poset.  is a complete lattice if any non empty subset 𝒳 of  has a supremum (a least upper bound) and an infimum (a greatest lower bound). The infimum and the supremum will be denoted, respectively, by ∧𝒳 and ∨𝒳. Two elements of the complete lattice  are important: the least element O and the greatest element I.

 The set of images from D to [0,M], =[0,M]^D, is a complete lattice with the partial order relation ≤, by inheritance of the complete lattice structure of [0,M]. The least and greatest elements are the constant functions f_0 and f_M whose values are equal respectively to 0 and M for all elements of D. The supremum and infimum are respectively, for any 𝒳⊂

    [                      (∧_𝒳)(x)                             =   ∧_[0,M]{ f(x):f ∈𝒳,  x∈ D };                      (∨_𝒳)(x)                             = ∨_[0,M]{ f(x):f ∈𝒳,  x∈ D  }.;                               ]

The set of functions ^D is also a complete lattice with = ∪{-∞ , +∞} with the usual order ≤, like the set of all subsets of D, written 𝒫(D), with the set inclusion ⊂.

Erosion, dilation, anti-erosion, anti-dilation <cit.>
Given _1 and _2 two complete lattices, a mapping ψ∈_2^_1 is


	
  * an erosion iff 				 	∀𝒳⊂_1, ψ( ∧𝒳 ) =  ∧ψ( 𝒳 ), then we write ε = ψ;
	
  * a dilation iff 				 	∀𝒳⊂_1, ψ( ∨𝒳 ) =  ∨ψ( 𝒳 ), then we write δ = ψ;
	
  * an anti-erosion  iff 	 	∀𝒳⊂_1, ψ( ∧𝒳 ) =  ∨ψ( 𝒳 ), then we write ε^a = ψ;
	
  * an anti-dilation iff 	 			∀𝒳⊂_1, ψ( ∨𝒳 ) =  ∧ψ( 𝒳 ), then we write δ^a = ψ.

As the definitions of these mappings apply even to the empty subset of _1, we have: ε(I)=I, δ(O)=O, ε^a(I)=O and δ^a(O)=I.


Erosions and dilations are increasing mappings: ∀𝒳, 𝒴⊂_1, 𝒳≤𝒴⇒ψ(𝒳) ≤ψ(𝒴) while anti-erosions and anti-dilations are decreasing mappings: ∀𝒳, 𝒴⊂_1, 𝒳≤𝒴⇒ψ(𝒴) ≤ψ(𝒳).

Structuring element <cit.>
Let us define a pulse function i_x,t∈ of level t at the point x: 

    i_x,t(x)=t;      i_x,t(y)=0  if  x ≠ y.


The function f can be decomposed into the supremum of its pulses f = ∨{i_x,f(x),x ∈ D }.
It is easy to define dilations and erosions which are not translation-invariant (in the domain D). Let W be a map → associating to each pulse function i_x,t∈ a (functional) “window” W(i_x,t). Then the operator δ_W: → defined by:

    δ_W(f) = ∨{ W(i_x,f(x)) , x ∈ D }

is a dilation. When all `windows” W(i_x,f(x)) are translation invariant (in D), they take the form W(i_x,f(x))=B(x) with B(x)=B_x being a structuring element (or structuring function).

In this case the previously defined dilation δ and erosion ε, in the same lattice (,≤), can be simplified:

    [                                 (δ_B(f))(x)                                           = ∨{ f(x - h) + B(h), h ∈ D_B } = (f ⊕ B) (x);                                 (ε_B(f))(x)                                           = ∧{ f(x + h) - B(h), h ∈ D_B } = (f ⊖ B) (x);                                             ]

D_B ⊂ D is the definition domain of the structuring function B: D_B →. The symbols ⊕ and ⊖ represent the extension to functions <cit.> of Minkowski operations between sets <cit.>.
Notice: in the case of a flat structuring element with its values equal to zero (i.e. ∀ x ∈ D_B, B(x)=0), we have δ_B(f)(x) = ∨{ f(x - h) , h ∈ D_B }= δ_D_B(f)(x) and ε_B(f)(x) = ∧{ f(x + h) , h ∈ D_B }= ε_D_B(f)(x).




















§ MAP OF APLUND'S DISTANCES AND MATHEMATICAL MORPHOLOGY


We now link the map of Asplund's distances with Mathematical Morphology.


Given ^+=[0,+∞] a complete lattice with the natural order ≤, the map of the least upper bounds _B between the probe B ∈ (^*)^D_B and the function f ∈ is defined as:

    _B f : {[                                        × (^*)^D_B                                                 →                                            (^+)^D;                                             (f,B)                                                 → _B f(x) =  ∧{α(x), f(x+h) ≤α(x)  B(h), h ∈ D_B }.;                                                   ].


The map of the greatest lower bounds μ_B between the probe B ∈ (^*)^D_B and the function f ∈ is defined as:

    μ_B f : {[                                           × (^*)^D_B                                                    →                                               (^+)^D;                                                (f,B)                                                    → μ_B f(x) =  ∨{β(x), β(x)  B(h) ≤ f(x+h) , h ∈ D_B }.;                                                      ].

The two mappings _B and μ_B are defined between two complete lattices _1 = ( , ≤) and _2 = ((^+)^D,≤) with the natural order ≤.
 

	
	


Therefore, the least element of (_1 , ≤) corresponds to the constant function equal to zero, O = f_0 and the greatest element is the constant function equal to M, I = f_M.

Using the equations <ref> and <ref> the map of Asplund's distances (eq. <ref>) can be simplified:

    As_B^f = ln( _B f /μ_B f ),  with  f > 0.


In addition, ∀ x ∈ D, ∀ h ∈ D_B, ∀α∈^+, we have:

    [                                                     α(x)  B(h) ≥ f(x+h)                                                                       ⇔                    M - M ( 1 - B(h)/M )^α(x)≥ f(x+h),  (from eq. <ref>);                                                                                                                                               ⇔ α(x) ≥ln( 1 - f(x+h)/M)/ln( 1 - B(h)/M), because ( 1 - B(h)/M) ∈ ]0,1[. ]


We assume that f= ln( 1 - f/M ). Using equation <ref>, equation <ref> becomes:

    _B f = ∧{α(x), α(x) ≥f(x+h) /B(h) , h ∈ D_B } 
    	= ∨{f(x+h) /B(h) , h ∈ D_B }.

In a similar way:

    μ_B f = ∨{β(x), β(x) ≤f(x+h) /B(h) , h ∈ D_B }
    = ∧{f(x+h) /B(h) , h ∈ D_B }.








 §.§ Case of a flat structuring element


In the case of a flat structuring element B=B_0 ∈^* (∀ x ∈ D_B, B(x) = B_0), the equations <ref> and <ref> can be simplified. 

    [                                         _B_0 f                                              = 1/B_0∧{f(x+h) ,  h ∈ D_B },    because B_0 < 0;                                                                                             =      1/B_0ln( 1 - ∨{ f(x-h) ,  -h ∈ D_B }/ M );                                                                                             =                     1/B_0ln( 1 - δ_D_B f / M ) ]

Notice: the infimum ∧ is changed into a supremum ∨ because the function f: x →ln(1-x/M) is a continuous decreasing mapping.
The reflected (or transposed) domain D_B is D_B = {-h, h∈ D_B } and the reflected structuring function B is defined by the reflection of its definition domain ∀ x ∈D_B, B(x)=B(-x) <cit.>.
Similarly: 

    [                                        μ_B_0 f                                              = 1/B_0∨{f(x+h) ,  h ∈ D_B },    because B_0 < 0;                                                                                             =       1/B_0ln( 1 - ∧{ f(x+h) ,  h ∈ D_B }/ M );                                                                                             =                   1/B_0ln( 1 - ε_D_B f / M ) . ]




With the equations <ref> and <ref>, the map of Asplund's distances (eq. <ref>) becomes:

    As_B_0^f = ln[ ln( 1 - δ_D_B f / M ) /ln( 1 - ε_D_B f / M ) ] ,  with  f > 0.


This important result shows that, with a flat probe, the map of Aplünd's distances can be computed using logarithms and operations of morphological erosion and dilation of an image. From an implementation point of view, the programming of the map of Aplünd's distances becomes easier, because the majority of image processing libraries contains morphological operations.

Notice: by replacing the dilation and erosion by rank-filters <cit.> one can compute the map of Asplund's distances with a tolerance <cit.>.






 §.§ General case: a structuring function


Using a general structuring function in the equations <ref> and <ref>, the map of Asplund's distances is expressed as:

    As_B^f = ln( _B f /μ_B f ) = 
    	ln( ∨{f(x+h) /B(h) , h ∈ D_B }/∧{f(x+h) /B(h) , h ∈ D_B }) ,  with  f > 0.


Let us study the properties of mappings _B, μ_B∈_2^_1, ∀ f, g ∈

    [                                                 _B ( f ∨ g )                                                            =                              ∨{f ∨ g (x+h) /B(h) , h ∈ D_B };                                                                                                                         =  ∨{f(x+h) ∧g(x+h) /B(h) , h ∈ D_B }, because f is decreasing;                                                                                                                         =     ∨{f(x+h)/B(h) ∨g(x+h) /B(h) , h ∈ D_B }, because B(h) <0;                                                                                                                         = [ ∨{f(x+h) /B(h) , h ∈ D_B }] ∨[ ∨{g(x+h) /B(h) , h ∈ D_B }];                                                                                                                         =                                          _B ( f ) ∨_B ( g ). ]

According to definition <ref>, 2 (p. pre:def_morpho_base), _B is a dilation.
In addition, 

    _B(O) = _B(f_0) = ∧{α(x), α(x) ≥0(x+h) /B(h) , h ∈ D_B } = 0 = O.

Similarly, we have:

    [                                                                 μ_B ( f ∧ g )                                                                             =                                               ∧{f ∧ g (x+h) /B(h) , h ∈ D_B };                                                                                                                                                           =                   ∧{f(x+h) ∨g(x+h) /B(h) , h ∈ D_B }, because f is decreasing;                                                                                                                                                           = [ ∧{f(x+h) /B(h) , h ∈ D_B }] ∧[ ∧{g(x+h) /B(h) , h ∈ D_B }], because B(h) <0;                                                                                                                                                           =                                                         μ_B ( f ) ∧μ_B ( g ). ]

According to definition <ref>, 1  (p. pre:def_morpho_base), μ_B is an erosion.
In addition, 

    μ_B(I) = μ_B(f_M) = ∨{β(x), β(x) ≤M(x+h) /B(h) , h ∈ D_B } = + ∞ = I.


Therefore, the map of Asplund's distances is the logarithm of the ratio between a dilation and an erosion of the function f by the structuring function B. The  map of the least upper bounds _B is a dilation and the map of the greatest lower bounds μ_B is an erosion. The two maps are defined from the lattice (_1 =  , ≤) and the lattice (_2 = (^+ )^D,≤) with their respective natural orders.










§ ILLUSTRATION


In figure <ref> (a), we extract a tile (i.e. the probe or the structuring function) in an image f and we look for the similar ones in a darken image, f^d, by means of a LIP multiplication of 0.3. Physically, it corresponds to an object with a stronger light absorption. Importantly, the probe has a non convex domain shape and is not flat. We compute the map of Asplund's distances between the probe B and the image f^d with a tolerance, As_B,p^ f^d, as introduced in <cit.>. This  metric, robust to noise, is computed by discarding p = 30 % of the points which are the closest to the least upper bounds and to the greatest lower bounds. The tiles are located at the local minima of the distance map which are extracted by a threshold of 0.7 (fig. <ref> (b)). The tiles similar to the probe, according to the Asplund's distance, have been correctly detected (fig. <ref> (c)). Notice that the domain of the probe is slightly smaller than the domain of the tiles.












§ CONCLUSION


In the current paper, we have shown that the map of Asplund's distances between a probe and a function using the LIP multiplication is linked with morphological operations. The probe corresponds to a structuring function and the map of Asplund's distances is the logarithm of the ratio between a dilation and an erosion of the function by the structuring function into the lattice of positive functions ((^+ )^D,≤). The dilation is the map of the least upper bounds _B f, between the function f and the probe B, while the erosion is the map of the greatest lower bounds μ_B f. 

The dilation and the erosion are mappings between the complete lattices of the images ( , ≤) and the lattice ((^+ )^D,≤) with the natural order. When using a flat structuring element, the expression of the map of Asplund's distances can be simplified with a dilation and an erosion of the image into the same lattice of the images ( , ≤). An example of pattern matching has been presented with a non-flat structuring function.  

The obtained results set the pattern matching approach by Asplund's distances in the well established framework of Mathematical Morphology. The current reasoning can be extended to the double-sided probing by Asplund's distances for colour and multivariate images using the LIP multiplicative or the LIP additive framework <cit.>. This will be presented in a coming paper. 









§ APPENDIX



Le us demonstrate that the Aplünd's metric d_As^ is a metric in the space of equivalence classes ^. In order to be a metric on (×) →^+, d_As^ must satisfy the four following properties:



	
  * (positivity): 
	∀≠∈, ∀ x ∈ D, (x) > μ(x) (def. <ref>, p. def:asplund_metric), because  >0
	
	⇒ > μ because  is an ordered set with the order ≤
	
	⇒∀≠∈, d_As^(,)>0. 
	
	
	

	
  * (Axiom of separation): 

    [ .
    [ d_As^(,) = 0 ⇒ = μ;  (def. <ref>) ⇒≥≥μ ]}                                           ⇒ =                                       ⇒ =  in;                                               ]
	
Reciprocally:

    [ .
    [     ∀, ∈,  = ⇒ =; (def. <ref>) ≥≥μ ]}                                   ⇒ = = μ;                                          ;                       ⇒ = μ⇒ d_As^(,) = 0 ]
	

Eq. <ref> and <ref> ⇒ {∀, ∈., . d_As^(,) = 0 ⇔ = }.


	
  * (Triangle inequality): 
Let us define: d_As^(,) = ln(_1/μ_1), d_As^(,) = ln(_2/μ_2) and d_As^(,) = ln(_3/μ_3).
We have 

    d_As^(,) + d_As^(,) = ln( _1 _2/μ_1 μ_2)




    [                                                                                                                                           Def. <ref>                                                                                                                                                    ⇒ {[   _1 = inf{k_1: ∀ x, k_1 (x) ≥(x)}; _2 = inf{k_2: ∀ x, k_2 _j(x) ≥(x)}; _3 = inf{k_3: ∀ x, k_3 _j(x) ≥(x)};                                    ].;                                                                                                                                                      ]



    [                                                         ⇒                                                     _1 _2                                                         ≤ inf_k_1{inf_k_2{∀ x, k_1  ( k_2 _j(x)) ≥ k_1 (x) }≥(x)  };                                                                                                                   ≤        inf{ k': ∀ x, k' _j(x) ≥(x)}, with  k' = k_1 × k_2;                                                         ⇒                                                     _1 _2                                                         ≤                                 _3 ,  with _1, _2, _3 > 0;                                                           ]



In the same way:

    μ_1 μ_2 ≥μ_3 ,  with μ_1, μ_2, μ_3 > 0


Eq. <ref>, <ref> <ref> ⇒ _1 _2/μ_1 μ_2≥_3/μ_3

⇒∀, , ∈, d_As^(,) ≤ d_As^(,) + d_As^(,).


	
  * (Axiom of symmetry): 
Let us define: d_As^(,) = ln(_1/μ_1), d_As^(,) = ln(_2/μ_2).

Def. <ref> ⇒
_1 = inf{ k: ∀ x, ≥1/k}, because k>0

⇒1/_1 = sup{ k': ∀ x, ≥ k' }
⇒1/_1 = μ_2.

In the same way, we have 1/μ_1 = _2.

Therefore, ∀, ∈, d_As^(,) = ln(_1/μ_1) = ln(_2/μ_2) = d_As^(,).










splncs03


