Structure theorem of solutions for flat dilation and flat erosion equations

WANG Yuqing，GUO Qi

（School of Mathematics and Physics，SUST，Suzhou 215009，China）

Structure theorem of solutions for flat dilation and flat erosion equations

WANG Yuqing，GUO Qi*

（School of Mathematics and Physics，SUST，Suzhou 215009，China）

In this article,we studied the flat dilation equations and the flat erosion equations.Necessary and sufficient conditions for the existence of solutions for these equations were given.In addition,we presented the structure theorem of solutions for these equations.Finally,we generalized the results for binary dilation equations and binary erosion equations.

flat dilation；flat erosion；dilation equation；structure of solution

1 Introduction

Let（G，+）be an abelian group and P（G）denote the power set of G，i.e.P（G）:＝{A|A⊂G}.Clearly P（G）is a（complete）lattice under the usual inclusion order of sets.In mathematical morphology，each A∈P（G）is called a binary（or black-white）image and so P（G）is just the collection of all binary images（[1]）.

For a fixed B∈P（G），two well-known morphological operators（image trans-formations）:δB（·）and εB（·）on P（G），called the dilation and the erosion（with respect to the Minkowski addition）respectively，are defined respectively by

where A+B:＝{a+b|a∈A，b∈B}，the Minkowski addition of sets，and we take the convention that φ+B＝φ，A+φ＝φ for all A，B∈P（G）（see[2]）.

It is known that δBand εBare adjunctive with each other in the sense that δB（A1）≤A2iff A1≤εB（A2），and also that the composition operator η：＝δB◦εBis an opening，i.e.it is increasing（A≤B⇒η（A）≤η（B）），anti-extensive（η（A）≤A）and idempotent（η◦η＝η）（see[2－3]）.

For the application of mathematical morphology，in particular，in image processing and analysis，the so-called（binary）dilation equation

is of great significance since it concerns the way to find all the pre-images from a known image，where B，C∈P（G）and X∈P（G）is the unknown variable.

Equation（1）was carefully studied in[4]by J.E.S.Castro，R.F.Hashimoto and J.Barrera.Under the assumption that G is finite，they provided a necessary and sufficient condition for（1）to have solutions and more importantly they gave the structure of all solutions.

In this paper，we are going to extend the study to gray-scale flat dilation equations and gray-scale flat erosion equations（see below for definitions）.Even though the task here is obviously more complicated，we have luckily obtained the same results as those in[4].

2 Preliminaries

Given an abelian group（G，+），denote by L（G）the family of gray-scale images on G，namely

（where the interval[0，1]can be replaced by any other intervals，finite or not）.Each f∈L（G）is called a grayscale image.L（G）is a（complete）lattice under the usual pointwise order of functions（[5]）.

For A⊂G，denote by χAits characteristic function，i.e.χA（x）＝1（if x∈A）or 0（if x∉A）.Clearly χA∈L（G）for any A⊂G.Thus，if identifying a set A with its characteristic function χA，we have P（G）⊂L（G）.

For a fixed χB∈L（G），we define the flat-dilationand the flat-erosionon L（G）respectively by，for any f∈L（G），

where χBis called the structure element of（see[6-7]for another sort of definitions of flat dilation and flat erosion）.It is easy to check that bothare increasing operators on L（G）.

Observe that if f＝χA（A∈P（G）），then it is easy to check that

which goes back equivalently to the binary dilation δB（A）＝A+B.Similarly，we have thatgoes back equivalently to εB（A）for characteristic functions.

Let χB，h∈L（G）.In this paper，we study the flat-dilation equation

where f∈L（G）is unknown variable.From the discussion above，we know that when h＝χCand f is restricted to the black-white images，i.e.f＝χXfor some X⊂G，then equation（2）reduces to（1）.

The following result will be needed later，which shows that the relation betweenis similar to that betweenare adjunctive pair.

Theorem 1For any f，h∈L（G）,δχB（f）≤h iff f≤εχB（h）.

Then，for any x∈G，y∈B，f（x-y）≤h（x），or equivalently by setting z＝x-y，for any y∈B，z∈G，

Thus，by the arbitrariness of y∈B，we get，for each z∈G，

i.e.f≤εχB（h）.

Conversely，if f≤εχB（h），i.e.f（x）≤εχB（h）（x）for all x∈G，or

Hence，for any x∈G，y∈B，f（x）≤h（x+y），or equivalently by setting z＝x+y，for any y∈B，z∈G，

which，by the arbitrariness of y，leads to，for each z∈G，

3 The existence and the structure of solutions

In this section，we give first a necessary and sufficient condition for the existence of solution and then the structure of solutions of equation（2）.

We start with a simple but useful proposition.

Proposition 1If f∈L（G）is a solution of（2），then f≤εχB（h）.

Proof.Suppose that f∈L（G）is a solution of（2），i.e（f）＝h，then（viewing（f）＝h as（f）≤h，f≤ εχB（h）by Theorem 1.□

Next theorem gives a necessary and sufficient condition for the existence of solution.

Theorem 3Let h，χB∈L（G）.Then（2）has solution iff εχB（h）is its solution.

Proof.The sufficiency is trivial.Now，suppose that（2）has a solution f，then，（h）by Proposition 1， from which and Theorem 2，it follows that

Remark 1Proposition 1 and Theorem 3 imply that if（2）has solution，thenmust be the largest one.

Now，we consider the structure of solutions of（2）.To make things easier，from now on we assume that

Such an assumption looks somehow restrictive，but it is practical：what we get in this paper under this assumption is enough for applications.In fact，in image processing or image analysis，the functions representing image are often assumed to admit finitely many values（e.g.integers form 0 to 255，see[8]）.

Under the assumption（*），we see that，for any f，χB∈L（G）and x∈G，

i.e.the supremum in the definition of dilations is attainable.Thus，if f is a solution of（2），then for any x∈G，

is not empty since h＝δχB（f）.We write simply Ω（x）instead of ΩεχB（h）（x）.It is easy to check that

The following proposition shows the connection between Ω（x）and the general Ωf（x）.

Proposition 2Let f be a solution of（2）.Then we have，for any x∈G，

The following theorem shows that if（2）has solution，then all the elements in Φ（χB，h）are solutions.

Theorem 4Let χB，h∈L（G）.If（2）has solution，then all φw∈Φ（χB，h）are solutions，i.e.

Proof.Since（2）has solution，Ω（x）≠φ for all x∈G.

Finally，we present the structure theorem for solutions of（2）.

Theorem 5Let χB，h∈L（G）.Suppose that（2）has solution，then f∈L（G）is a solution iff φw≤f≤εχB（h）for some φw∈Φ（χB，h）.

Proof.We start with the sufficiency.If φw≤f≤εχB（h），then

So δχB（f）＝h.

Conversely，if f is a solution of（2），then（h）by Proposition 1.Then，we choose yx*∈Ωf（x）for each x∈G and denote w*:＝（yx*）x∈G.By Proposition 2，，so φw*∈Φ（χB，h）.By the definition of φw*and Proposition 2 again，we have φw*≤f.□

Remark 21oWhen h＝χC，then

from which it is easy to see that Theorem 5 reduces to the Theorem 3 in[1].

2oLet Φ*（χB，h）denote the set of minimal elements in Φ（χB，h）.Then Theorem 4 and 5 state actually that f is a solution of（2）iff f locates between a minimal element（in Φ*（χB，h））and the largest solution εχB（h）.

At the end，we point out that with an analogical argument，we have similar results for the erosion equation

where χB，h∈L（G）and f∈L（G）is unknown variable.More precisely，we have the following theorems.

Theorem 6Erosion equation（3）has solution iff δχB（h）is（the smallest）solution.

Furthermore，suppose that（3）has solution and（*）holds，then writing，for x∈G，

Theorem 7Let χB，h∈L（G）.Suppose that（3）has solution，then f∈L（G）is a solution iff（h）≤f≤ψwfor some ψw∈ψ（χB，h）.

Final RemarkProbably，the assumption（*）can be omitted so that the conclusions in this paper still hold.We leave this work to another paper.

[1]SERRA J.Image Analysis and Mathematical Morphology[M].London：Academic Press，1982.

[2]KISELMAN C O.Digital geometry and mathematical morphology[EB/OL].[2013-03-16].http：//www2.math.uu.se/kiselman/dgmm2004.pdf.

[3]SERRA J.A lattice approach to image segmentation[J].J MathImaging Vis，2006，24（1）：83-130.

[4]CASTRO J E S，Hashimoto R F，Barrera J.Analytical solutions for the minkowski addition equation[J].LNCS，2013，7883：61-72.

[5]BIRKHOFF G.Lattice Theory[M].Providence：American Mathematical Society，1948.

[6]MOLCHNOVIS，TERAN P.Distance transforms for real-valued functions[J].J Math Anal Appl，2002，278（2）：472-484.

[7]DENG T Q，HEIJMANS H.Grey-scale morphology based on fuzzy logic[J].Journal of MathematicalImaging and Vision，2002，16（2）：155-171.

[8]SOILLE P.形态学图像分析原理与应用[M].王小鹏，译.北京：清华大学出版社，2008.

平坦膨胀和平坦腐蚀方程解的结构定理

王宇青，国起
（苏州科技大学数理学院，江苏苏州215009）

研究平坦膨胀方程和平坦腐蚀方程，给出了这两类方程解存在的充分必要条件，并建立了相应的解的结构定理。推广了有关二值膨胀方程和二值腐蚀方程的相应结论。

平坦膨胀；平坦腐蚀；膨胀方程；解的结构

2015－04－01

国家自然科学基金资助项目（11271282）

王宇青（1988-），女，河南洛阳人，硕士研究生，研究方向：数学形态学。

O29；O153.1MR（2000）Subject Classification：16H99；52C99；54A99

A

1672－0687（2016）04－0018－05

责任编辑：谢金春

*通信联系人：国起（1957－），男，教授，博士，硕士生导师，E-mail：guoqi@mail.usts.edu.cn。