Search Results

1 - 10 of 23 items :

  • "connected components" x
Clear All

The paper presents the algorithm for text line segmentation based on the oriented anisotropic Gaussian kernel. Initially, the document image is split into connected components achieved by bounding boxes. These connected components are cleared from redundant fragments. Furthermore, the binary moments are applied to each of these connected components evaluating local text skewing. According to this information the orientation of the anisotropic Gaussian kernel is set. After the algorithm application the boundary growing areas around connected components are established. These areas are of major importance for the evaluation of text line segmentation. For testing purposes, the algorithm is evaluated under different text samples. Comparative analysis between algorithm with and without orientation based on the anisotropic Gaussian kernel is made. The results show the improvement in the domain of text line segmentation.

Abstract

A set SV (G) is a vertex k-cut in a graph G = (V (G), E(G)) if GS has at least k connected components. The k-connectivity of G, denoted as κk(G), is the minimum cardinality of a vertex k-cut in G. We give several constructions of a set S such that (G□H) − S has at least three connected components. Then we prove that for any 2-connected graphs G and H, of order at least six, one of the defined sets S is a minimum vertex 3-cut in G□H. This yields a formula for κ 3(G□H).

Abstract

Data matrix codes are two-dimensional (2D) matrix bar codes, which are the descendants of the well known 1D bar codes. However, compared to 1D bar codes, they allow to store much more information in the same area. Comparing data matrix codes with QR codes, for example, we find them much more effective in marking small objects or in the case that you have only a very small area for placing a code in. Their capacity and ability of decoding also a code that is partly damaged make them an appropriate solution for industrial applications. In the following paper we compare the impact of various cameras on the detection and decoding of data matrix codes in real scene images. The location of the code is based on the fact that typical bordering of a data matrix code forms a region of connected points which create “L”, the so-called finder pattern, and the parallel dotting, the so-called timing pattern. In the first step, we try to locate the finder pattern using adaptive thresholding and connecting neighbouring points to continuous regions. Then we search for the regions where 3 outer boundary points form a isosceles right triangle that could represent the finder pattern. In the second step, we have to verify the timing pattern. We look for an even number of crossings between the background and foreground. Experimental results show that the algorithm we have proposed provides better results than competitive solutions.

Abstract

A cut-vertex in a graph G is a vertex whose removal increases the number of connected components of G. An end-block of G is a block with a single cut-vertex. In this paper we establish upper bounds on the numbers of end-blocks and cut-vertices in a 4-regular graph G and claw-free 4-regular graphs. We characterize the extremal graphs achieving these bounds.

Abstract

A total-colored graph G is rainbow total-connected if any two vertices of G are connected by a path whose edges and internal vertices have distinct colors. The rainbow total-connection number, denoted by rtc(G), of a graph G is the minimum number of colors needed to make G rainbow total-connected. In this paper, we prove that rtc(G) can be bounded by a constant 7 if the following three cases are excluded: diam() = 2, diam() = 3, contains exactly two connected components and one of them is a trivial graph. An example is given to show that this bound is best possible. We also study Erdős-Gallai type problem for the rainbow total-connection number, and compute the lower bounds and precise values for the function f(n, k), where f(n, k) is the minimum value satisfying the following property: if |E(G)| ≥ f(n, k), then rtc(G) ≤ k.

Abstract

Data Matrix codes can be a significant factor in increasing productivity and efficiency in production processes. An important point in deploying Data Matrix codes is their recognition and decoding. In this paper is presented a computationally efficient algorithm for locating Data Matrix codes in the images. Image areas that may contain the Data Matrix code are to be identified firstly. To identify these areas, the thresholding, connected components labelling and examining outer bounding-box of the continuous regions is used. Subsequently, to determine the boundaries of the Data Matrix code more precisely, we work with the difference of adjacent projections around the Finder Pattern. The dimensions of the Data Matrix code are determined by analyzing the local extremes around the Timing Pattern. We verified the proposed method on a testing set of synthetic and real scene images and compared it with the results of other open-source and commercial solutions. The proposed method has achieved better results than competitive commercial solutions.

Abstract

Let ℱ be a family of graphs. The Turán number of ℱ, denoted by ex(n, ℱ), is the maximum number of edges in a graph with n vertices which does not contain any subgraph isomorphic to some graph in ℱ. A star forest is a forest whose connected components are all stars and isolated vertices. Motivated by the results of Wang, Yang and Ning about the spanning Turán number of linear forests [J. Wang and W. Yang, The Turán number for spanning linear forests, Discrete Appl. Math. 254 (2019) 291–294; B. Ning and J. Wang, The formula for Turán number of spanning linear forests, Discrete Math. 343 (2020) 111924]. In this paper, let 𝒮n,k be the set of all star forests with n vertices and k edges. We prove that when 1 ≤ kn − 1, ex(n, 𝒮n,k) = ex(n,𝒮n,k)=k2-12.

Abstract

The global eradication of rinderpest in 2010 ranked as the second in history after the eradication of smallpox in humans in 1980. Rinderpest (in recent history included also among biological weapons of mass destruction) recurred throughout history causing hundreds of millions of animal deaths. It was recorded in 114 countries of all continents. After the World War II it was still reported from 66 countries in Africa and Asia. After all necessary knowledge about rinderpest virus and its circulation became available, along with excellent vaccine as well as enough experience with anti-rinderpest measures, the global eradication programme was launched in 1986 after a long preparatory period. It was composed of three new regional projects including all national anti-rinderpest programmes. The main method consisted in active search, isolation and stamping out of all outbreaks combined with mass prophylactic vaccinations and followed by years-long risk-based surveillance. The transfer of research results into practical reality required an extraordinary complex of a highly demanding system of managerial measures. It included analyses of rinderpest occurrence, identification of objectives/ deadlines and control methods, planning, ensuring necessary manpower, material and funds, organizing and implementation of coordinating programmes etc. This complex was represented by a managerial pyramid structure of inter-connected components having the basis at rinderpest affected localities and countries and its top at the Animal Health Service, Food and Agriculture Organization of the United Nations as executive agency responsible for technical assistance and global leadership/coordination.

Summary

Let us recall that a topological space M is a topological manifold if M is second-countable Hausdorff and locally Euclidean, i.e. each point has a neighborhood that is homeomorphic to an open ball of E n for some n. However, if we would like to consider a topological manifold with a boundary, we have to extend this definition. Therefore, we introduce here the concept of a locally Euclidean space that covers both cases (with and without a boundary), i.e. where each point has a neighborhood that is homeomorphic to a closed ball of En for some n.

Our purpose is to prove, using the Mizar formalism, a number of properties of such locally Euclidean spaces and use them to demonstrate basic properties of a manifold. Let T be a locally Euclidean space. We prove that every interior point of T has a neighborhood homeomorphic to an open ball and that every boundary point of T has a neighborhood homeomorphic to a closed ball, where additionally this point is transformed into a point of the boundary of this ball. When T is n-dimensional, i.e. each point of T has a neighborhood that is homeomorphic to a closed ball of En, we show that the interior of T is a locally Euclidean space without boundary of dimension n and the boundary of T is a locally Euclidean space without boundary of dimension n − 1. Additionally, we show that every connected component of a compact locally Euclidean space is a locally Euclidean space of some dimension. We prove also that the Cartesian product of locally Euclidean spaces also forms a locally Euclidean space. We determine the interior and boundary of this product and show that its dimension is the sum of the dimensions of its factors. At the end, we present several consequences of these results for topological manifolds. This article is based on [14].

References [1] W.T. Tutte, Connectivity in Graphs (Univ. Toronto Press, 1966). [2] W. Hohberg, The decomposition of graphs into k-connected components , Discrete Math. 109 (1992) 133–145. doi: 10.1016/0012-365X(92)90284-M [3] W. Mader, On vertices of degree n in minimally n-connected graphs and digraphs , Combinatorics, Paul Erdős is Eighty 2 (1996) 423–449. [4] W. McCuaig and K. Ota, Contractible triples in 3- connected graphs , J. Comb. Theory Ser. B 60 (1994) 308–314. doi: 10.1006/jctb.1994.1022 [5] M. Kriesell, Contractible subgraphs in 3