
To address the limitation of narrow field-of-view in local oral cavity images that fail to capture large-area targets at once, this paper designs a method for generating natural dental panoramas based on oral endoscopic imaging that consists of two main stages: the anti-perspective transformation feature extraction and the coarse-to-fine global optimization matching. In the first stage, we increase the number of matched pairs and improve the robustness of the algorithm to viewpoint transformation by normalizing the anti-affine transformation region extracted from the Gaussian scale space and using log-polar coordinates to compute the gradient histogram of the octagonal region to obtain the set of perspective transformation resistant feature points. In the second stage, we design a coarse-to-fine global optimization matching strategy. Initially, we incorporate motion smoothing constraints and improve the Fast Library for Approximate Nearest Neighbors (FLANN) algorithm by utilizing neighborhood information for coarse matching. Then, we eliminate mismatches via homography-guided Random Sample Consensus (RANSAC) and further refine the matching using the Levenberg-Marquardt (L-M) algorithm to reduce cumulative errors and achieve global optimization. Finally, multi-band blending is used to eliminate the ghosting due to unalignment and make the image transition more natural. Experiments show that the visual effect of dental panoramas generated by the proposed method is significantly better than that of other methods, addressing the problems of sparse splicing discontinuities caused by sparse keypoints, ghosting due to parallax, and distortion caused by the accumulation of errors in multi-image splicing in oral endoscopic image stitching.
Citation: Ning He, Hongmei Jin, Hong'an Li, Zhanli Li. A global optimization generation method of stitching dental panorama with anti-perspective transformation[J]. Mathematical Biosciences and Engineering, 2023, 20(9): 17356-17383. doi: 10.3934/mbe.2023772
[1] | Pannathon Kreabkhontho, Watchara Teparos, Thitiya Theparod . Potential for eliminating COVID-19 in Thailand through third-dose vaccination: A modeling approach. Mathematical Biosciences and Engineering, 2024, 21(8): 6807-6828. doi: 10.3934/mbe.2024298 |
[2] | Cheng-Cheng Zhu, Jiang Zhu . Spread trend of COVID-19 epidemic outbreak in China: using exponential attractor method in a spatial heterogeneous SEIQR model. Mathematical Biosciences and Engineering, 2020, 17(4): 3062-3087. doi: 10.3934/mbe.2020174 |
[3] | Fang Wang, Lianying Cao, Xiaoji Song . Mathematical modeling of mutated COVID-19 transmission with quarantine, isolation and vaccination. Mathematical Biosciences and Engineering, 2022, 19(8): 8035-8056. doi: 10.3934/mbe.2022376 |
[4] | Rahat Zarin, Usa Wannasingha Humphries, Amir Khan, Aeshah A. Raezah . Computational modeling of fractional COVID-19 model by Haar wavelet collocation Methods with real data. Mathematical Biosciences and Engineering, 2023, 20(6): 11281-11312. doi: 10.3934/mbe.2023500 |
[5] | Xinyu Bai, Shaojuan Ma . Stochastic dynamical behavior of COVID-19 model based on secondary vaccination. Mathematical Biosciences and Engineering, 2023, 20(2): 2980-2997. doi: 10.3934/mbe.2023141 |
[6] | Xiaojing Wang, Yu Liang, Jiahui Li, Maoxing Liu . Modeling COVID-19 transmission dynamics incorporating media coverage and vaccination. Mathematical Biosciences and Engineering, 2023, 20(6): 10392-10403. doi: 10.3934/mbe.2023456 |
[7] | A. Q. Khan, M. Tasneem, M. B. Almatrafi . Discrete-time COVID-19 epidemic model with bifurcation and control. Mathematical Biosciences and Engineering, 2022, 19(2): 1944-1969. doi: 10.3934/mbe.2022092 |
[8] | Fen-fen Zhang, Zhen Jin . Effect of travel restrictions, contact tracing and vaccination on control of emerging infectious diseases: transmission of COVID-19 as a case study. Mathematical Biosciences and Engineering, 2022, 19(3): 3177-3201. doi: 10.3934/mbe.2022147 |
[9] | Beatriz Machado, Liliana Antunes, Constantino Caetano, João F. Pereira, Baltazar Nunes, Paula Patrício, M. Luísa Morgado . The impact of vaccination on the evolution of COVID-19 in Portugal. Mathematical Biosciences and Engineering, 2022, 19(1): 936-952. doi: 10.3934/mbe.2022043 |
[10] | Saima Akter, Zhen Jin . A fractional order model of the COVID-19 outbreak in Bangladesh. Mathematical Biosciences and Engineering, 2023, 20(2): 2544-2565. doi: 10.3934/mbe.2023119 |
To address the limitation of narrow field-of-view in local oral cavity images that fail to capture large-area targets at once, this paper designs a method for generating natural dental panoramas based on oral endoscopic imaging that consists of two main stages: the anti-perspective transformation feature extraction and the coarse-to-fine global optimization matching. In the first stage, we increase the number of matched pairs and improve the robustness of the algorithm to viewpoint transformation by normalizing the anti-affine transformation region extracted from the Gaussian scale space and using log-polar coordinates to compute the gradient histogram of the octagonal region to obtain the set of perspective transformation resistant feature points. In the second stage, we design a coarse-to-fine global optimization matching strategy. Initially, we incorporate motion smoothing constraints and improve the Fast Library for Approximate Nearest Neighbors (FLANN) algorithm by utilizing neighborhood information for coarse matching. Then, we eliminate mismatches via homography-guided Random Sample Consensus (RANSAC) and further refine the matching using the Levenberg-Marquardt (L-M) algorithm to reduce cumulative errors and achieve global optimization. Finally, multi-band blending is used to eliminate the ghosting due to unalignment and make the image transition more natural. Experiments show that the visual effect of dental panoramas generated by the proposed method is significantly better than that of other methods, addressing the problems of sparse splicing discontinuities caused by sparse keypoints, ghosting due to parallax, and distortion caused by the accumulation of errors in multi-image splicing in oral endoscopic image stitching.
Topological indices have become an important research topic associated with the study of their mathematical and computational properties and, fundamentally, for their multiple applications to various areas of knowledge (see, e.g., [2,3,4,5,6,7,8,9]). Within the study of mathematical properties, we will contribute to the study of the optimization problems involved with topological indices (see, e.g., [10,11,12,13,14,15,16,17,18]).
In [19,20] several degree-based topological indices, called adriatic indices, were presented; one of them is the inverse sum indeg index ISI. It is important to note that this index was selected as one of the most predictive, in particular associated with the total surface area of the isomers of octane.
Let G be a graph and E(G) the set of all edges in G, denote by uv the edge of the graph G with vertices u,v and dz is the degree of the vertex z. the ISI index is defined by
ISI(G)=∑uv∈E(G)11du+1dv=∑uv∈E(G)dudvdu+dv. |
Nowadays, this index has become one of the most studied from the mathematical point of view (see, e.g., [21,22,23,24,25,26,27]). We study, here, the mathematical properties of the variable inverse sum deg index defined, for each a∈R, as
ISDa(G)=∑uv∈E(G)1dau+dav. |
Note that ISD−1 is the inverse sum indeg index ISI.
This research is motivated, in general, by the theoretical-mathematical importance of the topological indices and by their applicability in different areas of knowledge (see [28,29,30]). Additionally, in particular, by the work developed by Vukičević entitled "Bond Additive Modeling 5. Mathematical Properties of the Variable Sum Exdeg Index" (see [1]), where several open problems on the topological index ISDa were proposed. The novelty of this work is given in two main directions. The first one is associated with the solution of some of the problems posed in [1]. The second one is associated with the development of new optimization techniques and procedures related to the monotony and differentiation of symmetric functions, which allowed us to solve extremal problems and to present bounds for ISDa. Although, these techniques can be extended or applied in a natural way to obtain new relations and properties of other topological indices, it should be noted that their applicability requires the monotony of the function that determines the index to be studied.
In Section 2, we find optimal bounds and solve extremal problems associated with the topological index ISDa, with a<0, for several families of graphs. In Proposition 4, we solve the extremal problems for connected graphs with a given number of vertices. Theorem 6 and Remark 1 solve these problems for graphs with a given number of vertices and minimum degree; similarly, Theorems 8 and 9 present solutions to extremal problems in connected graphs with a given number of vertices and maximum degree. In this direction, in Theorem 5, Proposition 7 and Theorem 10, we present optimal bounds for the studied index.
In Section 3 of this research, a QSPR study related to the ISDa index in polyaromatic hydrocarbons is performed using experimental data. First, we determine the value of a that maximizes the Pearson's correlation coefficient between this index, and each of the studied physico-chemical properties. Finally, models for these properties are constructed using the simple linear regression method. A discussion of the results obtained is presented in Section 4, and some open problems for future research on this topic are raised.
In this research, G=(V(G),E(G)) denotes an undirected finite simple graph without isolated vertices. By n, m, Δ and δ, we denote the cardinality of the set of vertices of G, the cardinality of the set of edges of G, its maximum degree and its minimum degree, respectively. Thus, we have 1≤δ≤Δ<n. We denote by N(u) the set of neighbors of the vertex u∈V(G).
Suppose δ<Δ, we say that a graph G is (δ,Δ)-quasi-regular if it contains a vertex w, such that δ=dw and Δ=dz for every z∈V(G)∖{w}; G is (δ,Δ)-pseudo-regular if it contains a vertex w, such that Δ=dw and δ=dz for every z∈V(G)∖{w}.
In [31] appears the following result.
Lemma 1. Let k be an integer, such that 2≤k<n.
(1) If nk is even, then there exists a k-regular graph that is connected and has n vertices.
(2) If nk is odd, then there exist a (k,k−1)-quasi-regular and a connected (k+1,k)-pseudo-regular graphs, which are connected and have n vertices.
The following result is basic to the development of this work.
Lemma 2. For each a<0, the function f:R+×R+→R+ given by
f(x,y)=1xa+ya |
is strictly increasing in each variable.
Proof. Since a<0, we have
∂f∂x(x,y)=−axa−1(xa+ya)2>0. |
Then, f is a strictly increasing function in x, and since f is symmetric, it is also strictly decreasing in y.
Using Lemma 2, we obtain the following result.
Proposition 3. If G is a graph, u,v∈V(G) with uv∉E(G), and a<0, then ISDa(G∪{uv})>ISDa(G).
Given an integer number n≥2, let G(n) (respectively, Gc(n)) be the set of graphs (respectively, connected graphs) with n vertices.
Next, given integer numbers 1≤δ≤Δ<n, we are going to define the following classes of graphs: let H(n,δ) (respectively, Hc(n,δ)) be the graphs (respectively, connected graphs) with n vertices and minimum degree δ, and let I(n,Δ) (respectively, Ic(n,Δ)) be the graphs (respectively, connected graphs) with maximum degree Δ and n vertices.
First, let us state an optimization result for the ISDa index on Gc(n) and G(n) (see [32]).
Proposition 4. Consider a<0 and an integer n≥2.
(1) The graph that maximizes the ISDa index on Gc(n) or G(n) is unique and given by the complete graph Kn.
(2) If a graph minimizes the ISDa index on Gc(n), then it is a tree.
(3) If n is even, then the graph that minimizes the ISDa index on G(n) is unique and given by the union of n/2 paths P2. If n is odd, then the graph that minimizes the ISDa index on G(n) is unique and given by the union of (n−3)/2 paths P2 with a path P3.
Proof. Let G be a graph with n vertices, m edges and minimum degree δ.
Items (1) and (2) follow directly from Proposition 3.
For the proof of item (3), we first assume that n is even. For any graph G∈G(n) Lemma 2 gives
ISDα(G)=∑uv∈E(G)1dau+dav≥∑uv∈E(G)11a+1a=m2, |
and the equality is attained if, and only if, {du,dv}={1} for each uv∈E(G), i.e., G is the union of n/2 path graphs P2.
Now, we assume that n is odd. If du=1 for each u∈V(G), handshaking lemma gives 2m=n, a contradiction. So, there exists w∈V(G), such that dw≥2. Let N(w) be the set of neighbors of the vertex w, from Lemma 2, we obtain
ISDα(G)=∑uv∈E(G),u,v≠w1dau+dav+∑u∈N(w)1dau+daw≥∑uv∈E(G),u,v≠w11a+1a+∑u∈N(w)11a+2a≥m−22+21+2a, |
and the equality is attained if, and only if, du=1 for each u∈V(G)∖w and dw=2. Hence, G is the union of (n−3)/2 path graphs P2 and a path graph P3.
Proposition 4 allows to obtain the following inequalities.
Theorem 5. Consider a graph G with n vertices and a negative constant a.
(1) Then,
ISDa(G)≤14n(n−1)1−a, |
and equality holds if, and only if, G is the complete graph Kn.
(2) If n is even, then
ISDa(G)≥14n, |
and equality holds if, and only if, G is the union of n/2 path graphs P2.
(3) If n is odd, then
ISDa(G)≥14(n−3)+21+2a, |
and equality holds if, and only if, G is the union of a path graph P3 and (n−3)/2 path graphs P2.
Proof. Proposition 4 gives
ISDa(G)≤ISDa(Kn)=∑uv∈E(Kn)1dau+dav=n(n−1)212(n−1)a=14n(n−1)1−a. |
This argument gives that the bound is attained if, and only if, G is the complete graph Kn. Hence, item (1) holds.
Suppose G has minimum degree δ. If n is even, handshaking lemma gives 2m≥nδ≥n, using this and the proof of Proposition 4, we have
ISDa(G)≥m2≥n4, |
and equality holds if, and only if, G is the union of n/2 path graphs P2. This gives item (2).
If n is odd, handshaking lemma gives 2m≥(n−1)δ+2≥n+1, using this and the proof of Proposition 4, we have
ISDa(G)≥m−22+21+2a≥n+12−22+21+2a=n−34+21+2a, |
and equality holds if, and only if, G is the union of a path graph P3 and (n−3)/2 path graphs P2. This gives item (3).
Fix positive integers 1≤δ<n. Let Kδn be the n-vertex graph with minimum and maximum degrees δ and n−1, respectively, obtained from Kn−1 (the complete graph with n−1 vertices) and an additional vertex w, as follows: If we fix δ vertices v1,…,vδ∈V(Kn−1), then the vertices of Kδn are w and the vertices of Kn−1, and the edges of Kδn are {v1w,…,vδw} and the edges of Kn−1.
We consider now the optimization problem for the ISDa index on Hc(n,δ) and H(n,δ).
Theorem 6. Consider a<0 and integers 1≤δ<n.
(1) Then, the graph in Hc(n,δ) that maximizes the ISDa index is unique and given by Kδn.
(2) If δ≥2 and nδ is even, then all the graphs in Hc(n,δ) that minimize ISDa are the connected δ-regular graphs.
(3) If δ≥2 and nδ is odd, then all the graphs in Hc(n,δ) that minimize ISDa are the connected (δ+1,δ)-pseudo-regular graphs.
Proof. Given a graph G∈Hc(n,δ)∖{Kδn}, fix any vertex u∈V(G) with du=δ. Since
G≠G∪{vw:v,w∈V(G)∖{u} and vw∉E(G)}=Kδn, |
Proposition 3 gives ISDa(Kδn)>ISDa(G). This proves item (1).
Handshaking lemma gives 2m≥nδ.
Since du≥δ for every u∈V(G), Lemma 2 gives
ISDa(G)=∑uv∈E(G)1dau+dav≥∑uv∈E(G)12δa=m2δa≥nδ/22δa=14nδ1−a, |
and the bound is attained if, and only if, δ=du for all u∈V(G).
If δn is even, then Lemma 1 gives that there is a connected δ-regular graph with n vertices. Hence, the unique graphs in Hc(n,δ) that minimize the ISDa index are the connected δ-regular graphs.
If δn is odd, then handshaking lemma gives that there is no regular graph. Hence, there exists a vertex w with dw≥δ+1. Since du≥δ for every u∈V(G), handshaking lemma gives 2m≥(n−1)δ+δ+1=nδ+1. Lemma 2 gives
ISDa(G)=∑u∈N(w)1dau+daw+∑uv∈E(G),u,v≠w1dau+dav≥∑u∈N(w)1δa+(δ+1)a+∑uv∈E(G),u,v≠w12δa≥δ+1δa+(δ+1)a+m−δ−12δa≥δ+1δa+(δ+1)a+(nδ+1)/2−δ−12δa, |
and the bound is attained if, and only if, du=δ for all u∈V(G)∖{w}, and dw=δ+1. Lemma 1 gives that there is a connected (δ+1,δ)-pseudo-regular graph with n vertices. Therefore, the unique graphs in Hc(n,δ) that minimize the ISDa index are the connected (δ+1,δ)-pseudo-regular graphs.
Remark 1. If we replace Hc(n,δ) with H(n,δ) everywhere in the statement of Theorem 6, then the argument in its proof gives that the same conclusions hold if we remove everywhere the word "connected".
Theorem 6 and Remark 1 have the following consequence.
Proposition 7. Consider a graph G with minimum degree δ and n vertices, and a negative constant a.
(1) Then,
ISDa(G)≤(n−δ−1)(n−δ−2)4(n−2)a+δδa+(n−1)a+δ(δ−1)4(n−1)a+δ(n−δ−1)(n−2)a+(n−1)a, |
and the bound is attained if, and only if, G is isomorphic to Kδn.
(2) If δ≥2 and δn is even, then
ISDa(G)≥14nδ1−a, |
and the bound is attained if, and only if, G is δ-regular.
(3) If δ≥2 and nδ is odd, then
ISDa(G)≥δ(n−2)−14δa+δ+1δa+(δ+1)a, |
and the bound is attained if, and only if, G is (δ+1,δ)-pseudo-regular.
Let us deal with the optimization problem for the ISDa index on Ic(n,Δ).
Theorem 8. Consider a<0 and integers 2≤Δ<n.
(1) If nΔ is even, then all the graphs that maximize ISDa on Ic(n,Δ) are the connected Δ-regular graphs.
(2) If nΔ is odd, then all the graphs that maximize ISDa on Ic(n,Δ) are the connected (Δ,Δ−1)-quasi-regular graphs.
(3) If a graph minimizes ISDa on Ic(n,Δ), then it is a tree.
Proof. Handshaking lemma gives 2m≤nΔ. Since du≤Δ for every u∈V(G), Lemma 2 gives
ISDa(G)=∑uv∈E(G)1dau+dav≤∑uv∈E(G)12Δa=m2Δa≤nΔ/22Δa=14nΔ1−a, |
and the bound is attained if, and only if, Δ=du for all u∈V(G).
If nΔ is even, then Lemma 1 gives that there is a connected Δ-regular graph with n vertices. Hence, the unique graphs in Ic(n,Δ) that maximize the ISDa index are the connected Δ-regular graphs.
If nΔ is odd, then handshaking lemma gives that there is no regular graph in Ic(n,Δ). Let G∈Ic(n,Δ). Hence, there exists a vertex w with dw≤Δ−1. Then, 2m≤Δ(n−1)+Δ−1=Δn−1. Lemma 2 gives
ISDa(G)=∑u∈N(w)1dau+daw+∑uv∈E(G),u,v≠w1dau+dav≤∑u∈N(w)1Δa+(Δ−1)a+∑uv∈E(G),u,v≠w12Δa≤Δ−1Δa+(Δ−1)a+m−Δ+12Δa≤Δ−1Δa+(Δ−1)a+(Δn−1)/2−Δ+12Δa, |
and the bound is attained if, and only if, du=Δ for all u∈V(G)∖{w}, and dw=Δ−1. Lemma 1 gives that there is a connected (Δ,Δ−1)-quasi-regular graph with n vertices. Therefore, the unique graphs in Ic(n,δ) that maximize the ISDa index are the connected (Δ,Δ−1)-quasi-regular graphs.
Given any graph G∈Ic(n,Δ) which is not a tree, fix any vertex u∈V(G) with du=Δ. Since G is not a tree, there exists a cycle C in G. Since C has at least three edges, there exists vw∈E(G)∩C, such that u∉{v,w}. Since vw is contained in a cycle of G, then G∖{vw} is a connected graph. Thus, G∖{vw}∈Ic(n,Δ) and Proposition 3 gives ISDa(G)>ISDa(G∖{vw}). By iterating this argument, we obtain that if a graph minimizes the ISDa index on Ic(n,Δ), then it is a tree.
The following result deals with the optimization problem for the ISDa index on I(n,Δ).
Theorem 9. Consider a<0 and integers 2≤Δ<n.
(1) If nΔ is even, then all the graphs that maximize the ISDa index on I(n,Δ) are the Δ-regular graphs.
(2) If nΔ is odd, then all the graphs that maximize the ISDa index on I(n,Δ) are the (Δ,Δ−1)-quasi-regular graphs.
(3) If n−Δ is odd, then the graph that minimizes the ISDa index on I(n,Δ) is unique and given by the union of the star graph SΔ+1 and (n−Δ−1)/2 path graphs P2.
(4) If n=Δ+2, then the graph that minimizes the ISDa index on I(n,Δ) is unique and given by the star graph SΔ+1 with an additional edge attached to a vertex of degree 1 in SΔ+1.
(5) If n≥Δ+4 and n−Δ is even, then the graph that minimizes the ISDa index on I(n,Δ) is unique and given by the union of the star graph SΔ+1, (n−Δ−4)/2 path graphs P2 and a path graph P3.
Proof. The argument in Theorem 8 gives directly items (1) and (2).
Let G∈I(n,Δ) and w∈V(G) a vertex with dw=Δ.
Assume first that n−Δ is odd. Handshaking lemma gives 2m≥n−1+Δ. Note that n−1+Δ=n−Δ+2Δ−1 is even. Lemma 2 gives
ISDa(G)=∑u∈N(w)1dau+daw+∑uv∈E(G),u,v≠w1dau+dav≥∑u∈N(w)11a+Δa+∑uv∈E(G),u,v≠w11a+1a=Δ1+Δa+m−Δ2≥Δ1+Δa+(n−1+Δ)/2−Δ2=Δ1+Δa+n−Δ−14, |
and the bound is attained if, and only if, 1=du for all u∈V(G)∖{w}, i.e., G is the union of the star graph SΔ+1 and (n−Δ−1)/2 path graphs P2.
Assume now that n=Δ+2. Let z∈V(G)∖N(w) be the vertex with V(G)={w,z}∪N(w). Choose p∈N(z); since z∉N(w), we have p∈N(w) and so, dp≥2. Handshaking lemma gives 2m≥(n−2)+Δ+2=n+Δ. Lemma 2 gives
ISDa(G)=∑u∈N(w)1dau+daw+∑uv∈E(G),u,v≠w1dau+dav≥Δ−11+Δa+12a+Δa+11+2a, |
and the bound is attained if, and only if, 1=du for all u∈V(G)∖{w,p} and dp=2, i.e., G is the star graph SΔ+1 with an additional edge attached to a vertex of degree 1 in SΔ+1.
Assume that n≥Δ+4 and n−Δ is even. If du=1 for every u∈V(G)∖{w}, then handshaking lemma gives 2m=n−1+Δ, a contradiction since n−1+Δ=n−Δ+2Δ−1 is odd. Thus, there exists a vertex p∈V(G)∖{w} with dp≥2. Handshaking lemma gives 2m≥(n−2)+2+Δ=n+Δ.
If p∉N(w), then Lemma 2 gives
ISDa(G)=∑u∈N(w)1dau+daw+∑u∈N(p)1dau+dap+∑uv∈E(G),u,v∉{w,p}1dau+dav≥∑u∈N(w)11a+Δa+∑u∈N(p)11a+2a+∑uv∈E(G),u,v∉{w,p}11a+1a≥Δ1+Δa+21+2a+m−Δ−22≥Δ1+Δa+21+2a+(n+Δ)/2−Δ−22=Δ1+Δa+21+2a+n−Δ−44, |
and the bound is attained if, and only if, du=1 for all u∈V(G)∖{w,p}, and dp=2, i.e., G is the union of the star graph SΔ+1, (n−Δ−4)/2 path graphs P2 and a path graph P3.
If p∈N(w), then
ISDa(G)=∑u∈N(w)∖{p}1dau+daw+∑u∈N(p)∖{w}1dau+dap+1dap+daw+∑uv∈E(G),u,v∉{w,p}1dau+dav≥∑u∈N(w)∖{p}11a+Δa+∑u∈N(p)∖{w}11a+dap+1dap+Δa+∑uv∈E(G),u,v∉{w,p}11a+1a≥Δ−11+Δa+11+2a+12a+Δa+m−Δ−12≥Δ−11+Δa+11+2a+12a+Δa+(n+Δ)/2−Δ−12=Δ−11+Δa+11+2a+12a+Δa+n−Δ−24. |
Hence, in order to finish the proof of item (5), it suffices to show that
Δ−11+Δa+11+2a+12a+Δa+n−Δ−24>Δ1+Δa+21+2a+n−Δ−44. |
We have
(1−2a)(1−Δa)>0,1+2aΔa>2a+Δa,2aΔa+Δa+2a+1>2(2a+Δa),(Δa+1)(1+2a)(2+2a+Δa)>2(2a+Δa)(2a+Δa+2),12a+Δa+12>11+Δa+11+2a,Δ−11+Δa+11+2a+12a+Δa+n−Δ−24>Δ1+Δa+21+2a+n−Δ−44, |
and so, (5) holds.
Remark 2. Note that the case Δ=1 in Theorem 9 is trivial: if Δ=1, then G is a union of isolated edges.
Also, we can state the following inequalities.
Theorem 10. Consider a graph G with maximum degree Δ and n vertices, and a negative constant a.
(1) If nΔ is even, then
ISDa(G)≤14nΔ1−a, |
and the bound is attained if, and only if, G is a regular graph.
(2) If nΔ is odd, then
ISDa(G)≤Δ−1Δa+(Δ−1)a+Δ(n−2)+14Δa, |
and the bound is attained if, and only if, G is a (Δ,Δ−1)-quasi-regular graph.
(3) If n−Δ is odd, then
ISDa(G)≥Δ1+Δa+n−Δ−14, |
and the bound is attained if, and only if, G is the union of the star graph SΔ+1 and (n−Δ−1)/2 path graphs P2.
(4) If n=Δ+2, then
ISDa(G)≥Δ−11+Δa+12a+Δa+11+2a, |
and the bound is attained if, and only if, G is the star graph SΔ+1 with an additional edge attached to a vertex of degree 1 in SΔ+1.
(5) If n≥Δ+4 and n−Δ is even, then
ISDa(G)≥Δ1+Δa+21+2a+n−Δ−44, |
and the bound is attained if, and only if, G is the union of the star graph SΔ+1, (n−Δ−4)/2 path graphs P2 and a path graph P3.
Proof. The argument in the proof of Theorem 8 gives items (1) and (2), since the variable inverse sum deg index of a regular graph is
14nΔ1−a, |
and the ISDa index of a (Δ,Δ−1)-quasi-regular graph is
Δ−1Δa+(Δ−1)a+Δ(n−2)+14Δa. |
The argument in the proof of Theorem 9 gives directly items (3)–(5).
The variable inverse sum deg index ISD−1.950 was selected in [33] as a significant predictor of standard enthalpy of formation for octane isomers. In this section, we will test the predictive power of the ISDa index using experimental data on three physicochemical properties of 82 polyaromatic hydrocarbons (PAH). The properties studied are the melting point (MP), boiling point (BP) and octanol-water partition coefficient (LogP) (the experimental data were obtained from [34]). In order to obtain the values of the ISDa index, we constructed the hydrogen-suppressed graph of each molecule, then we use a program of our own elaboration to compute the index for each value of a analyzed.
We calculated the Pearson's correlation coefficient r between the three analyzed properties and the ISDa index, for values of a in the interval [−5,5] with a spacing of 0.01; the results are shown in Figure 1. The dashed red line indicates the value of a that maximizes r.
Figure 2 shows the ISDa index (for values of a that maximize r) vs. the studied properties of PAH. In addition, in Figure 2, we test the following linear regression models (red lines)
MP=31.54ISD0.15−121.15BP=58.94ISD0.39−13.35LogP=0.68ISD0.63+1.55. |
Table 1 summarizes the statistical and regression parameters of these models.
Property | a | r | c | m | SE | F | SF |
MP | 0.15 | 0.856 | −122.15 | 31.54 | 54.61 | 214.47 | 4.31×10−24 |
BP | 0.39 | 0.989 | −13.35 | 58.94 | 12.42 | 2272.86 | 5.69×10−44 |
LogP | 0.63 | 0.943 | 1.55 | 0.68 | 0.34 | 282.04 | 2.53×10−18 |
Motivated by a paper of Vukičević [1], and based on the practical applications found for the variable inverse sum deg index ISDa, we focus our research on the study of optimal graphs associated with ISDa, when a<0. In this direction, it is wise to study the extremal properties of ISDa, when a<0 in general graphs. Specifically, in this paper, we characterize the graphs with extremal values in the following significant classes of graphs with a fixed number of vertices:
● graphs with a fixed minimum degree;
● connected graphs with a fixed minimum degree;
● graphs with a fixed maximum degree;
● connected graphs with a fixed maximum degree.
From the QSPR study performed on polyaromatic hydrocarbons, it can be concluded that the ISDa index presents a strong correlation with the boiling point and octanol-water partition coefficient properties, with maximum values of r higher than 0.98 and 0.94, respectively. Further, the melting point property presents some correlation with the ISDa index with maximum value of r close to 0.85.
For future research, we suggests:
● To study the extreme problems for the ISDa index for values of a>0.
● To consider the problem of finding which tree/trees with n vertices (with a fixed maximum degree or not) minimize the index ISDa (a<0).
● To analyze the behavior of the ISDa index in other important families of graphs, such as graph products and graph operators.
● To explore the mathematical properties and possible applications of the exponential extension of the ISDa index.
● To study the predictive power of this index on other physicochemical properties of PAH, and on other classes of molecules.
The authors were supported by a grant from Agencia Estatal de Investigación (PID2019-106433GB-I00 / AEI / 10.13039/501100011033), Spain.
The authors declare there are no conflicts of interest.
[1] |
Y. Yan, L. Xu, Y. Y. Liu, X. Su, J. L. Gao, M. X. Wan, Larynx ultrasound image stitching based on multiconstraint super-pixel feature, IEEE Trans. Instrum. Meas., 72 (2023), 1–11. https://doi.org/10.1109/TIM.2023.3243675 doi: 10.1109/TIM.2023.3243675
![]() |
[2] | M. Ghanoum, A. M. Ali, S. Elshazly, I. Alkabbany, A. A. Farag, Frame stitching in human oral cavity environment using intraoral camera, in IEEE International Conference on Image Processing (ICIP), (2019), 1327–1331. https://doi.org/10.1109/ICIP.2019.8803071 |
[3] | M. Ghanoum, A. M. Ali, S. Elshazly, I. Alkabbany, A. A. Farag, Panoramic view of human jaw under ambiguity intraoral camera movement, in IEEE 17th International Symposium on Biomedical Imaging (ISBI), (2020), 1–4. https://doi.org/10.1109/ISBI45749.2020.9098562 |
[4] |
T. Jin, F. Z. Li, H. J. Peng, B. Li, D. P. Jiang, Uncertain barrier swaption pricing problem based on the fractional differential equation in Caputo sense, Soft Comput., 27 (2023), 11587–11602. https://doi.org/10.1007/s00500-023-08153-5 doi: 10.1007/s00500-023-08153-5
![]() |
[5] |
T. Jin, H. X. Xia, Lookback option pricing models based on the uncertain fractional-order differential equation with Caputo type, J. Ambient Intell. Human. Comput. (JAIHC), 14 (2023), 6435–6448. https://doi.org/10.1007/s12652-021-03516-y doi: 10.1007/s12652-021-03516-y
![]() |
[6] |
C. W. Shen, X. Y. Ji, C. L. Miao, Real-Time image stitching with convolutional neural networks, 2019 IEEE International Conference on Real-time Computing and Robotics (RCAR), (2019), 192–197. https://doi.org/10.1109/RCAR47638.2019.9044010 doi: 10.1109/RCAR47638.2019.9044010
![]() |
[7] |
L. Nie, C. Y. Lin, K. Liao, M. Q. Liu, Y. Zhao, A view-free image stitching network based on global homography, J. Vis. Comun. Imag. R, 73 (2019), 102950. https://doi.org/10.1016/j.jvcir.2020.102950 doi: 10.1016/j.jvcir.2020.102950
![]() |
[8] |
L. Nie, C. Y. Lin, K. Liao, Y. Zhao, Learning edge-preserved image stitching from multi-scale deep homography, Neurocomputing, 491 (2022), 533–543. https://doi.org/10.1016/j.neucom.2021.12.032 doi: 10.1016/j.neucom.2021.12.032
![]() |
[9] |
D. Y. Song, G. M. Um, H. K. Lee, D. Cho, End-to-end image stitching network via multi-homography estimation, IEEE Signal Process Lett., 28 (2021), 763–767. https://doi.org/10.1109/LSP.2021.3070525 doi: 10.1109/LSP.2021.3070525
![]() |
[10] |
D. Y. Song, G. Lee, H. K. Lee, G. M. Um, D. Cho, Weakly-Supervised stitching network for real-world panoramic image generation, Lect. Notes Comput. Sci., 13676 (2022), 54–71. https://doi.org/10.1007/978-3-031-19787-1_4 doi: 10.1007/978-3-031-19787-1_4
![]() |
[11] |
L. Nie, C. Y. Lin, K. Liao, S. C. Liu, Y. Zhao, Unsupervised deep image stitching: Reconstructing stitched features to images, IEEE Trans. Image Process, 30 (2021), 6184–6197. https://doi.org/10.1109/TIP.2021.3092828 doi: 10.1109/TIP.2021.3092828
![]() |
[12] |
J. R. Zhang, C. Wang, S. C. Liu, L. P. Jia, N. J. Ye, J. Wang, et al., Content-Aware unsupervised deep homography estimation, Lect. Notes Comput. Sci., 12346 (2020), 653–669. https://doi.org/10.1007/978-3-030-58452-8_38 doi: 10.1007/978-3-030-58452-8_38
![]() |
[13] |
S. C. Liu, N. J. Ye, C. Wang, J. R. Zhang, L. P. Jia, K. M. Luo, et al., Content-Aware unsupervised deep homography estimation and its extensions, IEEE Trans. Pattern Anal. Mach. Intell., 45 (2022), 2849–2863. https://doi.org/10.1109/TPAMI.2022.3174130 doi: 10.1109/TPAMI.2022.3174130
![]() |
[14] |
R. Huang, Q. Chang, Y. Zhang, Unsupervised oral endoscope image stitching algorithm, J. Shanghai Jiaotong University (Science), (2022), 1–10. https://doi.org/10.1007/s12204-022-2513-7 doi: 10.1007/s12204-022-2513-7
![]() |
[15] | S. Wang, F. Y. Yuan, B. Chen, H. F. Jiang, W. Q. Chen, Y. Wang, Deep homography estimation based on attention mechanism, in 2021 7th International Conference on Systems and Informatics (ICSAI), (2021), 1–6. https://doi.org/10.1109/ICSAI53574.2021.9664027 |
[16] |
L. David, Distinctive image features from scale-invariant keypoints, Int. J. Comput. Vis., 60 (2004), 91–110. https://doi.org/10.1023/B:VISI.0000029664.99615.94 doi: 10.1023/B:VISI.0000029664.99615.94
![]() |
[17] |
H. Bay, T. Tuytelaars, L. Van Gool, SURF: speeded up robust features, Lect. Notes Comput. Sci., 3951 (2006), 404–417. https://doi.org/10.1007/11744023_32 doi: 10.1007/11744023_32
![]() |
[18] | E. Rublee, V. Rabaud, K. Konolige, ORB: An efficient alternative to SIFT or SURF, in 2011 International Conference on Computer Vision (ICCV), (2011), 2564–2571. https://doi.org/10.1109/ICCV.2011.6126544 |
[19] |
G. F. Zhang, Y. He, W. F. Chen, J. Y. Jia, H. J. Bao Multi-viewpoint panorama construction with wide-baseline images, IEEE Trans. Image Process, 25 (2016), 3099–3111. https://doi.org/10.1109/TIP.2016.2535225 doi: 10.1109/TIP.2016.2535225
![]() |
[20] | J. W. Bian, W. Y. Lin, Y. Liu, L. Zhang, S. K. Yeung, M. M. Cheng, et al., GMS: Grid-Based motion statistics for fast, ultra-robust feature correspondence, in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), (2017), 4181–4190. https://doi.org/10.1109/CVPR.2017.302 |
[21] | R. Sprengel, K. Rohr, H.S. Stiehl, Thin-plate spline approximation for image registration, in Proceedings of 18th Annual International Conference of the IEEE Engineering in Medicine and Biology Society, (1996), 1190–1191. https://doi.org/10.1109/IEMBS.1996.652767 |
[22] |
K. Rohr, H. S. Stiehl, R. Sprengel, W. Beil, T. M. Buzug, J. Weese, et al., Point-based elastic registration of medical image data using approximating thin-plate splines, Lect. Notes Comput. Sci., 1131 (1996), 297–306. https://doi.org/10.1007/BFb0046967 doi: 10.1007/BFb0046967
![]() |
[23] |
J. Li, Z.M. Wang, S.M. Lai, Y. P. Zhai, M. J. Zhang, Parallax-tolerant image stitching based on robust elastic warping, IEEE Trans. Mult., 20 (2018), 1672–1687. https://doi.org/10.1109/TMM.2017.2777461 doi: 10.1109/TMM.2017.2777461
![]() |
[24] |
L. Nie, C. Y. Lin, K. Liao, S. C. Liu, Y. Zhao, Learning Thin-Plate spline motion and seamless composition for parallax-tolerant unsupervised deep image stitching, Comput. Vision Pattern Recogn. (CVPR), (2023), https://doi.org/10.48550/arXiv.2302.08207 doi: 10.48550/arXiv.2302.08207
![]() |
[25] |
M. Brown, D. G. Lowe, Automatic panoramic image stitching using invariant features, Int J Comput Vis, (2007), 59–73. https://doi.org/10.1007/s11263-006-0002-3 doi: 10.1007/s11263-006-0002-3
![]() |
[26] |
J. H. Gao, S. J. Kim, M. S. Brown, Constructing image panoramas using dual-homography warping, Comput. Vision Pattern Recogn. (CVPR), (2011), 40–56. https://doi.org/10.1109/CVPR.2011.5995433 doi: 10.1109/CVPR.2011.5995433
![]() |
[27] |
W. Y. Lin, S. Y. Liu, Y. Matsushita, T. T. Ng, L. F. cheong, Smoothly varying affine stitching, Comput. Vision Pattern Recogn. (CVPR), (2011), 345–352. https://doi.org/10.1109/CVPR.2011.5995314 doi: 10.1109/CVPR.2011.5995314
![]() |
[28] |
J. Zaragoza, T. J. Chin, M. S. Brown, D. Suter, As-projective-as-possible image stitching with moving DLT, Comput. Vision Pattern Recogn. (CVPR), (2013), 2339–2346. https://doi.org/10.1109/CVPR.2013.303 doi: 10.1109/CVPR.2013.303
![]() |
[29] |
C. H. Chang, Y. Sato, Y. Y. Chuang, Shape-preserving half-projective warps for image stitching, Comput. Vision Pattern Recogn. (CVPR), (2014), 3254–3261. https://doi.org/10.1109/CVPR.2014.422 doi: 10.1109/CVPR.2014.422
![]() |
[30] |
C. C. Lin, S. Pankanti, K. Ramamurthy, A. Aravkin, Adaptive as-natural-as-possible image stitching, Comput. Vision Pattern Recogn. (CVPR), (2015), 1155–1163. https://doi.org/10.1109/CVPR.2015.7298719 doi: 10.1109/CVPR.2015.7298719
![]() |
[31] |
Y. S. Chen, Y. Y. Chuang, Natural Image Stitching with the Global Similarity Prior, Lect. Notes Comput. Sci., 9909 (2016), 186–201. https://doi.org/10.1007/978-3-319-46454-1_12 doi: 10.1007/978-3-319-46454-1_12
![]() |
[32] | T. Z. Xiang, G. S. Xia, L. P. Zhang, N. N. Huang, Locally warping-based image stitching by imposing line constraints, in 2016 23rd International Conference on Pattern Recognition (ICPR), (2016), 4178–4183. https://doi.org/10.1109/ICPR.2016.7900289 |
[33] |
C. He, J. Zhou, Mesh-based image stitching algorithm with linear structure protection, J. Image Graph., (2018), 973–983. https://doi.org/10.11834/jig.170653 doi: 10.11834/jig.170653
![]() |
[34] | P. Du, J. F. Ning, J. G. Cui, S. L. Huang, X. C. Wang, J. X. Wang, Geometric Structure Preserving Warp for Natural Image Stitching, in 2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), (2022), 3688–3696 https://doi.org/10.1109/CVPR52688.2022.00367 |
1. | Shuo Li, Saif Ullah, Salman A. AlQahtani, Sayed M. Tag, Ali Akgül, Mathematical assessment of Monkeypox with asymptomatic infection: Prediction and optimal control analysis with real data application, 2023, 51, 22113797, 106726, 10.1016/j.rinp.2023.106726 | |
2. | Yuzhen Wang, Saif Ullah, Ihsan Ullah Khan, Salman A. AlQahtani, Ahmed M. Hassan, Numerical assessment of multiple vaccinations to mitigate the transmission of COVID-19 via a new epidemiological modeling approach, 2023, 52, 22113797, 106889, 10.1016/j.rinp.2023.106889 | |
3. | Rehana Naz, Andrew Omame, Mariano Torrisi, Cost-effectiveness analysis of COVID-19 vaccination: A review of some vaccination models, 2024, 11, 26668181, 100842, 10.1016/j.padiff.2024.100842 | |
4. | Yan Li, Laique Zada, Emad A. A. Ismail, Fuad A. Awwad, Ahmed M. Hassan, Assessing the Impact of Time-Varying Optimal Vaccination and Non-Pharmaceutical Interventions on the Dynamics and Control of COVID-19: A Computational Epidemic Modeling Approach, 2023, 11, 2227-7390, 4253, 10.3390/math11204253 | |
5. | Laiquan Wang, Arshad Alam Khan, Saif Ullah, Nadeem Haider, Salman A. AlQahtani, Abdul Baseer Saqib, A rigorous theoretical and numerical analysis of a nonlinear reaction-diffusion epidemic model pertaining dynamics of COVID-19, 2024, 14, 2045-2322, 10.1038/s41598-024-56469-5 | |
6. | Y. Sudha, V. N. Deiva Mani, K. Murugesan, On the Solvability of Time-Fractional Spatio-Temporal COVID-19 Model with Non-linear Diffusion, 2024, 48, 2731-8095, 1281, 10.1007/s40995-024-01663-3 | |
7. | Wafa F. Alfwzan, Mahmoud H. DarAssi, F.M. Allehiany, Muhammad Altaf Khan, Mohammad Y. Alshahrani, Elsayed M. Tag-eldin, A novel mathematical study to understand the Lumpy skin disease (LSD) using modified parameterized approach, 2023, 51, 22113797, 106626, 10.1016/j.rinp.2023.106626 | |
8. | Changtong Li, Saif Ullah, Rashid Nawaz, Salman A AlQahtani, Shuo Li, Mathematical modeling and analysis of monkeypox 2022 outbreak with the environment effects using a Cpauto fractional derivative, 2023, 98, 0031-8949, 105239, 10.1088/1402-4896/acf88e | |
9. | Abdeldjalil Kadri, Ahmed Boudaoui, Saif Ullah, Mohammed Asiri, Abdul Baseer Saqib, Muhammad Bilal Riaz, A comparative study of deterministic and stochastic computational modeling approaches for analyzing and optimizing COVID-19 control, 2025, 15, 2045-2322, 10.1038/s41598-025-96127-y | |
10. | Manal Almuzini, Farah A. Abdullah, Matthew O. Adewole, Shaher Momani, S. A. Khuri, Generalized Mathematical Model of Infectious Disease During Medicinal Intervention by Employing Fractional Differential Equations, 2025, 0170-4214, 10.1002/mma.11019 |
Property | a | r | c | m | SE | F | SF |
MP | 0.15 | 0.856 | −122.15 | 31.54 | 54.61 | 214.47 | 4.31×10−24 |
BP | 0.39 | 0.989 | −13.35 | 58.94 | 12.42 | 2272.86 | 5.69×10−44 |
LogP | 0.63 | 0.943 | 1.55 | 0.68 | 0.34 | 282.04 | 2.53×10−18 |