Near sets

In mathematics, near sets are either spatially close or descriptively close. Spatially close sets have nonempty intersection. In other words, spatially close sets are not disjoint sets, since they always have at least one element in common. Descriptively close sets contain elements that have matching descriptions. Such sets can be either disjoint or non-disjoint sets. Spatially near sets are also descriptively near sets.
The underlying assumption with descriptively close sets is that such sets contain elements that have location and measurable features such as colour and frequency of occurrence. The description of the element of a set is defined by a feature vector. Comparison of feature vectors provides a basis for measuring the closeness of descriptively near sets. Near set theory provides a formal basis for the observation, comparison, and classification of elements in sets based on their closeness, either spatially or descriptively. Near sets offer a framework for solving problems based on human perception that arise in areas such as image processing, computer vision as well as engineering and science problems.
Near sets have a variety of applications in areas such as topology, pattern detection and classification, abstract algebra, mathematics in computer science, and solving a variety of problems based on human perception that arise in areas such as image analysis, image processing, face recognition, ethology, as well as engineering and science problems. From the beginning, descriptively near sets have proved to be useful in applications of topology, and visual pattern recognition , spanning a broad spectrum of applications that include camouflage detection, micropaleontology, handwriting forgery detection, biomedical image analysis, content-based image retrieval, population dynamics, quotient topology, textile design, visual merchandising, and topological psychology.
As an illustration of the degree of descriptive nearness between two sets, consider an example of the Henry colour model for varying degrees of nearness
between sets of picture elements in pictures (see, "e.g.", §4.3). The two pairs of ovals in Fig. 1 and Fig. 2 contain coloured segments. Each segment in the figures corresponds to an equivalence class where all pixels in the class have similar descriptions, "i.e.", picture elements with similar colours. The ovals in Fig.1 are closer to each other descriptively than the ovals in Fig. 2.
History.
It has been observed that the simple concept of "nearness" unifies various concepts of topological structures inasmuch as the category Near of all nearness spaces and nearness preserving maps contains categories sTop (symmetric topological spaces and continuous maps), Prox (proximity spaces and formula_1-maps), Unif (uniform spaces and uniformly continuous maps) and Cont (contiguity spaces and contiguity maps) as embedded full subcategories. The categories formula_2 and formula_3 are shown to be full supercategories of various well-known categories, including the category formula_4 of symmetric topological spaces and continuous maps, and the category formula_5 of extended metric spaces and nonexpansive maps. The notation formula_6 reads "category" formula_7 "is embedded in category" formula_8. The categories formula_9 and formula_10 are supercategories for a variety of familiar categories shown in Fig. 3. Let formula_2 denote the category of all formula_12-approach nearness spaces and contractions, and let formula_9 denote the category of all formula_12-approach merotopic spaces and contractions.
Among these familiar categories is formula_4, the symmetric form of formula_16 (see category of topological spaces), the category with objects that are topological spaces and morphisms that are continuous maps between them. formula_17 with objects that are extended metric spaces is a subcategory of formula_18 (having objects formula_12-approach spaces and contractions) (see also). Let formula_20 be extended pseudometrics on nonempty sets formula_21, respectively. The map formula_22 is a contraction if and only if formula_23 is a contraction. For nonempty subsets formula_24 , the distance function formula_25 is defined by
Thus formula_27AP is embedded as a full subcategory in formula_2 by the functor formula_29 defined by formula_30 and formula_31. Then formula_22 is a contraction if and only if formula_23 is a contraction. Thus formula_34 is embedded as a full subcategory in formula_2 by the functor formula_29 defined by formula_30 and formula_38 Since the category formula_5 of extended metric spaces and nonexpansive maps is a full subcategory of formula_34, therefore, formula_2 is also a full supercategory of formula_5. The category formula_2 is a topological construct.
The notions of near and far in mathematics can be traced back to works by Johann Benedict Listing and Felix Hausdorff. The related notions of resemblance and similarity can be traced back to J.H. Poincaré, who introduced sets of similar sensations (nascent tolerance classes) to represent the results of G.T. Fechner's sensation sensitivity experiments and a framework for the study of resemblance in representative spaces as models of what he termed physical continua. The elements of a physical continuum (pc) are sets of sensations. The notion of a pc and various representative spaces (tactile, visual, motor spaces) were introduced by Poincaré in an 1894 article on the mathematical continuum, an 1895 article on space and geometry and a compendious 1902 book on science and hypothesis followed by a number of elaborations, "e.g.". The 1893 and 1895 articles on continua (Pt. 1, ch. II) as well as representative spaces and geometry (Pt. 2, ch IV) are included as chapters in. Later, F. Riesz introduced the concept of proximity or nearness of pairs of sets at the International Congress of Mathematicians (ICM) in 1908.
During the 1960s, E.C. Zeeman introduced tolerance spaces in modelling visual perception. A.B. Sossinsky observed in 1986 that the main idea underlying tolerance space theory comes from Poincaré, especially. In 2002, Z. Pawlak and J. Peters considered an informal approach to the perception of the nearness of physical objects such as snowflakes that was not limited to spatial nearness. In 2006, a formal approach to the descriptive nearness of objects was considered by J. Peters, A. Skowron and J. Stepaniuk in the context of proximity spaces. In 2007, descriptively near sets were introduced by J. Peters followed by the introduction of tolerance near sets. Recently, the study of descriptively near sets has led to algebraic, topological and proximity space foundations of such sets.
Nearness of sets.
The adjective "near" in the context of near sets is used to denote the fact that observed feature value differences of distinct objects are small enough to be
considered indistinguishable, "i.e.", within some tolerance.
The exact idea of closeness or 'resemblance' or of 'being within tolerance' is universal enough to appear, quite naturally, in almost any mathematical setting
(see, "e.g.",). It is especially natural in mathematical applications: practical problems, more often than not, deal with approximate input data and only require viable results with a tolerable level of error.
The words "near" and "far" are used in daily life and it was an incisive suggestion of F. Riesz that these intuitive concepts be made rigorous. He introduced the concept of nearness of pairs of sets at the ICM in Rome in 1908. This concept is useful in simplifying teaching calculus and advanced calculus. For example, the passage from an intuitive definition of continuity of a function at a point to its rigorous epsilon-delta definition is sometime difficult for teachers to explain and for students to understand. Intuitively, continuity can be explained using nearness language, "i.e.", a function formula_44 is continuous at a point formula_45, provided points formula_46 near formula_45 go into points formula_48 near formula_49. Using Riesz's idea, this definition can be made more precise and its contrapositive is the familiar definition.
Generalization of set intersection.
From a spatial point of view, nearness (a.k.a. proximity) is considered a generalization of set intersection. For disjoint sets, a form of nearness set intersection is defined in terms of a set of objects (extracted from disjoint sets) that have similar features within some
tolerance (see, "e.g.", §3 in). For example, the ovals in Fig. 1 are considered near each other, since these ovals contain pairs of classes that display similar (visually indistinguishable) colours.
Efremovič proximity space.
Let formula_50 denote a metric topological space that is endowed with one or more proximity relations and let formula_51 denote the collection of all subsets of formula_50. The collection formula_51 is called the power set of formula_50.
There are many ways to define Efremovič proximities on topological spaces (discrete proximity, standard proximity, metric proximity, Čech proximity, Alexandroff proximity, and Freudenthal proximity), For details, see § 2, pp. 93–94 in.
The focus here is on "standard proximity" on a topological space. For formula_55, formula_56 is near formula_57 (denoted by formula_58), provided their closures share a common point.
The "closure" of a subset formula_59 (denoted by formula_60) is the usual Kuratowski closure of a set, introduced in § 4, p. 20, is defined by
"i.e." formula_60 is the set of all points formula_63 in formula_50 that are close to formula_56 (formula_66 is the Hausdorff distance (see § 22, p. 128, in) between formula_63 and the set formula_56 and formula_69 (standard distance)). A "standard" proximity relation is defined by
Whenever sets formula_56 and formula_57 have no points in common, the sets are "far"from each other (denoted formula_73).
The following EF-proximity space axioms are given by Jurij Michailov Smirnov based on what Vadim Arsenyevič Efremovič introduced during the first half of the 1930s. Let formula_74.
The pair formula_93 is called an EF-proximity space. In this context, a space is a set with some added structure. With a proximity space formula_50, the structure of formula_50 is induced by the EF-proximity relation formula_1. In a proximity space formula_50, the closure of formula_56 in formula_50 coincides with the intersection of all closed sets that contain formula_56.
Visualization of EF-axiom.
Let the set formula_50 be represented by the points inside the rectangular region in Fig. 5. Also, let formula_106 be any two non-intersection subsets ("i.e." subsets spatially far from each other) in formula_50, as shown in Fig. 5. Let formula_108 (complement of the set formula_90). Then from the EF-axiom, observe the following:
Descriptive proximity space.
Descriptively near sets were introduced as a means of solving classification and pattern recognition problems arising from disjoint sets that resemble each other. Recently, the connections between near sets in EF-spaces and near sets in descriptive EF-proximity spaces have been explored in.
Again, let formula_50 be a metric topological space and let formula_112 a set of probe functions that represent features of each formula_103. The assumption made here is formula_50 contains non-abstract points that have measurable features such as gradient orientation. A non-abstract point has a location and features that can be measured (see § 3 in ).
A "probe function" formula_115 represents a feature of a sample point in formula_50. The mapping formula_117 is defined by formula_118, where formula_119 is an n-dimensional real Euclidean vector space. formula_120 is a feature vector for formula_63, which provides a description of formula_103. For example, this leads to a proximal view of sets of picture points in digital images.
To obtain a descriptive proximity relation (denoted by formula_123), one first chooses a set of probe functions. Let formula_124 be a mapping on a subset of formula_51 into a subset of formula_126. For example, let formula_24 and formula_128 denote sets of descriptions of points in formula_106, respectively. That is,
The expression formula_131 reads formula_56 "is descriptively near" formula_57. Similarly, formula_134 reads formula_56 "is descriptively far from" formula_57. The descriptive proximity of formula_56 and formula_57 is defined by
The "descriptive intersection" formula_140 of formula_56 and formula_57 is defined by
That is, formula_144 is in formula_145, provided formula_146 for some formula_147. Observe that formula_56 and formula_57 can be disjoint and yet formula_145 can be nonempty.
The descriptive proximity relation formula_123 is defined by
Whenever sets formula_56 and formula_57 have no points with matching descriptions, the sets are "descriptively far" from each other 
(denoted by formula_155).
The binary relation formula_123 is a "descriptive EF-proximity", provided the following axioms are satisfied for formula_157.
The pair formula_179 is called a descriptive proximity space.
Proximal relator spaces.
A "relator" is a nonvoid family of relations formula_180 on a nonempty set formula_50. The pair formula_182 (also denoted formula_183) is called a relator space. Relator spaces are natural generalizations of ordered sets and uniform spaces}. With the introduction of a family of proximity relations formula_184 on formula_50, we obtain a proximal relator space formula_186. For simplicity, we consider only two proximity relations, namely, the Efremovič proximity formula_1 and the descriptive proximity formula_123 in defining the "descriptive relator" formula_189. The pair formula_190 is called a "proximal relator space ". In this work, formula_50 denotes a metric topological space that is endowed with the relations in a proximal relator. With the introduction of formula_190, the traditional closure of a subset ("e.g.", ) can be compared with the more recent descriptive closure of a subset.
In a proximal relator space formula_50, the "descriptive closure of a set" formula_56 (denoted by formula_195) is defined by
That is, formula_103 is in the descriptive closure of formula_56, provided the closure of formula_120 and the closure of formula_200 have at least one element in common.
In a proximal relator space, EF-proximity formula_1 leads to the following results for descriptive proximity formula_123.
formula_230
formula_236
Descriptive formula_1-neighbourhoods.
In a pseudometric proximal relator space formula_50, the neighbourhood of a point formula_103 (denoted by formula_240), for formula_241, is defined by
The interior of a set formula_56 (denoted by formula_244) and boundary of formula_56 (denoted by formula_246) in a proximal relator space formula_50 are defined by
A set formula_56 has a "natural strong inclusion" in a set formula_57 associated with formula_1} (denoted by formula_253), provided formula_254, "i.e.", formula_255 (formula_56 is far from the complement of formula_257). Correspondingly, a set formula_56 has a "descriptive strong inclusion" in a set formula_57 associated with formula_123 (denoted by formula_261), provided formula_262, "i.e.", formula_263 (formula_264 is far from the complement of formula_257).
Let formula_266 be a descriptive formula_1-neighbourhood relation defined by
That is, formula_261, provided the description of each formula_270 is contained in the set of descriptions of the points formula_271. Now observe that any formula_106 in the proximal relator space formula_50 such that formula_155 have disjoint formula_123-neighbourhoods, "i.e.",
A consideration of strong containment of a nonempty set in another set leads to the study of hit-and-miss topologies and the Wijsman topology.
Tolerance near sets.
Let formula_12 be a real number greater than zero. In the study of sets that are proximally near within some tolerance, the set of proximity relations formula_189 is augmented with a pseudometric tolerance proximity relation (denoted by formula_281) defined by
Let formula_283. In other words, a nonempty set equipped with the proximal relator formula_284 has underlying structure provided by the proximal relator formula_189 and provides a basis for the study of tolerance near sets in formula_50 that are near within some tolerance. Sets formula_106 in a descriptive pseudometric proximal relator space formula_288 are tolerance near sets ("i.e.", formula_289), provided
Tolerance classes and preclasses.
Relations with the same formal properties as similarity relations of sensations considered by Poincaré are nowadays, after Zeeman, called "tolerance relations". A "tolerance formula_291 on a set formula_292" is a relation formula_293 that is reflexive and symmetric. In algebra, the term "tolerance relation" is also used in a narrow sense to denote reflexive and symmetric relations defined on universes of algebras that are also compatible with operations of a given algebra, "i.e.", they are generalizations of congruence relations (see "e.g.",). In referring to such relations, the term "algebraic tolerance" or the term "algebraic tolerance relation" is used.
Transitive tolerance relations are equivalence relations. A set formula_292 together with a tolerance formula_291 is called a "tolerance space" (denoted formula_296). A set formula_297 is a "formula_291-preclass" (or briefly "preclass" when formula_291 is understood) if and only if for any formula_300, formula_301.
The family of all preclasses of a tolerance space is naturally ordered by set inclusion and preclasses that are maximal with respect to set inclusion are called "formula_291-classes" or just "classes", when formula_291 is understood. The family of all classes of the space formula_296 is particularly interesting and is denoted by formula_305. The family formula_305 is a covering of formula_292.
The work on similarity by Poincaré and Zeeman presage the introduction of near sets and research on similarity relations, "e.g.". In science and engineering, tolerance near sets are a practical application of the study of sets that are near within some tolerance. A tolerance formula_308 is directly related to the idea of closeness or resemblance ("i.e.", being within some tolerance) in comparing objects.
By way of application of Poincaré's approach in defining visual spaces and Zeeman's approach to tolerance relations, the basic idea is to compare objects such as image patches in the interior of digital images.
Examples.
Simple Example
The following simple example demonstrates the construction of tolerance classes from real data. Consider the 20 objects in the table below with formula_309.
Let a tolerance relation be defined as
Then, setting formula_311 gives the following tolerance classes:
Observe that each object in a tolerance class satisfies the condition formula_313, and that almost all of the objects appear in more than one class. Moreover, there would be twenty classes if the indiscernibility relation was used since there are no two objects with matching descriptions.
Image Processing Example
The following example provides an example based on digital images. Let a subimage be defined as a small subset of pixels belonging to a digital image such that the pixels contained in the subimage form a square. Then, let the sets formula_314 and formula_315 respectively represent the subimages obtained from two different images, and let formula_316. Finally, let the description of an object be given by the Green component in the RGB color model. The next step is to find all the tolerance classes using the tolerance relation defined in the previous example. Using this information, tolerance classes can be formed containing objects that have similar (within some small formula_12) values for the Green component in the RGB colour model. Furthermore, images that are near (similar) to each other should have tolerance classes divided among both images (instead of a tolerance classes contained solely in one of the images). For example, the figure accompanying this example shows a subset of the tolerance classes obtained from two leaf images. In this figure, each tolerance class is assigned a separate colour. As can be seen, the two leaves share similar tolerance classes. This example highlights a need to measure the degree of nearness of two sets.
Nearness measure.
Let formula_318 denote a particular descriptive pseudometric EF-proximal relator space equipped with the proximity relation formula_281 and with nonempty subsets formula_320 and with the tolerance relation formula_321 defined in terms of a set of probes formula_322 and with formula_323, where
Further, assume formula_325 and let formula_326 denote the family of all classes in the space formula_327.
Let formula_328. The distance formula_329 is defined by
where
The details concerning formula_332 are given in. The idea behind formula_332 is that sets that are similar should have a similar number of objects in each tolerance class. Thus, for each tolerance class obtained from the covering of formula_334, formula_332 counts the number of objects that belong to formula_50 and formula_315 and takes the ratio (as a proper fraction) of their cardinalities. Furthermore, each ratio is weighted by the total size of the tolerance class (thus giving importance to the larger classes) and the final result is normalized by dividing by the sum of all the cardinalities. The range of formula_332 is in the interval [0,1], where a value of 1 is obtained if the sets are equivalent (based on object descriptions) and a value of 0 is obtained if they have no descriptions in common.
As an example of the degree of nearness between two sets, consider figure below in which each image consists of two sets of objects, formula_50 and formula_315. Each colour in the figures corresponds to a set where all the objects in the class share the same description. The idea behind formula_332 is that the nearness of sets in a perceptual system is based on the cardinality of tolerance classes that they share. Thus, the sets in left side of the figure are closer (more near) to each other in terms of their descriptions than the sets in right side of the figure.
Near set evaluation and recognition (NEAR) system.
The Near set Evaluation and Recognition (NEAR) system, is a system developed to demonstrate practical applications of near set theory to the problems of image segmentation evaluation and image correspondence. It was motivated by a need for a freely available software tool that can provide results for research and to generate interest in near set theory. The system implements a Multiple Document Interface (MDI) where each separate processing task is performed in its own child frame. The objects (in the near set sense) in this system are subimages of the images being processed and the probe functions (features) are image processing functions defined on the subimages. The system was written in C++ and was designed to facilitate the addition of new processing tasks and probe functions. Currently, the system performs six major tasks, namely, displaying equivalence and tolerance classes for an image, performing segmentation evaluation, measuring the nearness of two images, performing Content Based Image Retrieval (CBIR), and displaying the output of processing an image using a specific probe function.
Proximity System.
The Proximity System is an application developed to demonstrate descriptive-based topological approaches to nearness and proximity within the context of digital image analysis. The Proximity System grew out of the work of S. Naimpally and J. Peters on Topological Spaces. The Proximity System was written in Java and is intended to run in two different operating environments, namely on Android smartphones and tablets, as well as desktop platforms running the Java Virtual Machine. With respect to the desktop environment, the Proximity System is a cross-platform Java application for Windows, OSX, and Linux systems, which has been tested on Windows 7 and Debian Linux using the Sun Java 6 Runtime. In terms of the implementation of the theoretical approaches, both the Android and the desktop based applications use the same back-end libraries to perform the description-based calculations, where the only differences are the user interface and the Android version has less available features due to restrictions on system resources.