Alisa Rahim
Grade 11
Queens High School for the Sciences at York College
Mentor: Dr. Rishi Nath of York College
Peer Reviewer: Cole Johnson
Abstract
Some of the uses of Ring Theory in the modern world involve cryptography, computer vision, and image segmentation. As of now, finite cyclic rings have been incorporated into performing image segmentations for the Mean Shift Iterative Algorithm. This paper analyzes the Mean Shift Iterative Algorithm and devises an improved algorithm and stopping criterion using finite cyclic rings and matrices in Ring Theory that perform high-quality image segmentations for images that can be used in computer vision and possibly the segmentation(s) of grayscale (d = 1), colored (d = 3), and multispectral (d ? 3) images. By honing in on the various factors that play into the segmentation process and incorporating Ring Theory in altering the Mean Shift Iterative Algorithm, the Improved Mean Shift function aims to resolve the issue of low- resolution, continuous iterations of image processing.
Introduction
Based on the concepts of Group Theory and the field of abstract algebra, Ring Theory is a concept where a ”ring” is a set of elements with two binary factors: addition and multiplication. To subtract within a ring would essentially mean to add an element to its additive inverse. Likewise, to divide would mean to multiply an element by its multiplicative inverse. Doing so would bring the element back to the additive identity zero and the multiplicative identity one, respectively. A ring also satisfies the following axioms:
- The ring, under addition, is an abelian group.
- The multiplication operation is associative, and therefore closed.
- All operations satisfy the distributive law of multiplication over addition. An example of a ring includes the set of real polynomials. The set of real polynomials can be denoted as:
Within this ring, you can freely add, subtract, and multiply one polynomial, essentially an element within the ring, to get another polynomial – another element. The additive identity is presented as zero. Since zero is a constant polynomial, this value is also considered to be an element in the ring of real polynomials. The multiplicative identity is presented as one. Since multiplication is commutative among all polynomials, the ring of real polynomials is deduced as a commutative ring with an identity element. However, not all rings follow these guidelines. Some rings are finite, meaning that the amount and type of elements may be limited. An example of this would be a ring Z with the integers modulo n. Additionally, some rings may not have the additive identity zero or the multiplicative identity one. An example of such a ring includes the set of even integers, denoted as 2Z. Upon adding, subtracting, or multiplying two even numbers, the result is always another even number. The value of 1 does not fall within the set of even numbers. Therefore, the set of even integers does not have the multiplicative identity of one – and is only a commutative ring.
The term ”elements” is used rather than ”numbers” because rings can be used to generalize complex concepts in mathematics; such concepts include integers, polynomials with coefficients, and matrices.
Image segmentation is the practice of breaking a picture up into pixels and assigning each pixel a value based on a given class. The purpose of image segmentation is to partition images into more meaningful, easy to examine, sections. The pixels in each partition share a common property; an example of one of these properties is pixel intensity. The segmentation of images is primarily applied to image editing/compression, as well as the recognition of certain objects or another relevant aspects of a taken image. Some existing methods used for image segmentation are the K-Means Algorithm, the Mean Shift Iterative Algorithm, graph-based segmentation, region growing, and the Epanechnikov kernel function. The Mean Shift Iterative Algorithm uses finite cyclic rings to detect specific features of an image (i.e. eyes of a face, abnormalities in an MRI scan of a heart, tumors in a brain) and the probability of there being a specific part of an image. A finite cyclic ring is any ring where the elements derive from a single element (hence, they are limited in regards to what elements may be present within the ring and, when brought back within range of said ring, the elements repeat in a cycle).
For the sake of the research at hand, rings were used to summarize pixel values given to images when performing an image segmentation. In gray-scale images, pixels are given a value from 0 to 1. These values indicate the presence of the shades along the gray scale. For instance, a pixel with a value of 0.1 will have a lighter presence, while a pixel with a value of 9.8 will have a drastically darker appearance. The pixels as a group all satisfy the axioms of a finite, commutative ring. These axioms are as such:
- The number of elements within a ring is finite, or limited in terms of included values.
- When adding two elements in the ring, the sum is another element in the ring.
When discussing Ring Theory in image zoning, Professor D. Aruna of the Chalapathi Institute of Engineering and Technology notes the following: ”Entropy is an essential function in information theory and this has had a special uses for images data, e.g., restoring images, detecting contours, segmenting images and many other applications [12,15]. However, in the field of images the range of properties of this function could be increased if the images are defined in rings. The inclusion of the ring theory to the spatial analysis is achieved considering images as a matrix in which the elements belong to the cyclic ring n. From this point of view, the images present cyclical properties associated to gray level values. ” (D. Aruna) Here, Aruna elaborates on the significance of entropy within the process of image segmentation, as well as the use of cyclic rings (see definition above). However, there is no present discussion of a stopping criterion being used for Mean Shift; therefore, entropy substitutes as the stopping criterion for MSHi. Aruna additionally remarks the following: ”Also, it is defined the quotient space of strongly equivalent images and some properties of entropy are proved. The experimental results, comparisons and discussion are presented. Taking in consideration the good properties that, in general, the NED definition has, one sees logical to take this new similarity index as the new stopping criterion of MSHi.” (D. Aruna) Within this section, it is mentioned that the Natural Entropy Distance can also be used as the stopping criterion for the Mean Shift Iterative Algorithm since the two factors hold similar properties.
Ali Asghar Heidari defines the stopping criterion of a segmentation algorithm as ”a condition that forces [an]algorithm to terminate the process. It can be any meaningful condition that [you] wish, such as: number of iterations, quality of solutions, statistical values, an external or internal condition, a [possible] random termination key, etc.” A primary factor in determining the stopping criteria for a segmentation algorithm is the entropy, or number of consistent microscopic configurations, of an image. The number of consistent microscopic configurations is significant to constructing a stopping criterion for an algorithm for image segmentation because while images may interchangeably be weakly and strongly equivalents, images that are strongly equivalent are not weakly equivalent. Images are defined in a finite cyclic ring when the Mean Shift Iterative Algorithm is used for image segmentation. However, an established stopping criterion for the Mean Shift Iterative Algorithm has not been formulated thus far; instead, the entropy formula has been in place as the stopping criterion for Mean Shift for stability purposes.
In terms of practicality, the practice of image segmentation relates heavily to cancer screenings, and inaccuracy thereof. An autopsy study conducted by Louisiana State University examined 250 bodies that had all died as a result of cancer. From that set of 250, nearly 44 percent of said cancers were either never detected or falsely diagnosed, and therefore left to continue attacking the victims. A primary culprit for this is a faulty screening, caused by a poorly processed image. The stopping criterion plays a major role here in that it would stop the process of image breakdown. After a certain number of iterations, the segmentation should stop altogether with the help of a stopping criterion. However, due to the absence of said factor especially with the Mean Shift Iterative Algorithm, the image processing continues, ultimately causing an inaccurate image. As the iterations continue, the area classified as the ”region of interest” (in this case, it would be the cancer, tumor, or sarcoma in focus of the patient) would expand beyond its real parameters, potentially leading to doctors misdiagnosing their clients and classifying healthy cells as ill, or vice versa. The goal in devising a new algorithm and stopping criterion is, when implemented, to reduce the number of misdetected and undetected cancer cases, or any other ailment indicated through image processing, as much as possible.
Related Work
Ring Theory is used in many fields of computer science, including image segmentation. Yasel Garces et al. discusses the significance of rings in segmentation in his paper, ”Application of the Ring Theory in the Segmentation of Digital Images”. In his paper, the following is remarked regarding Ring Theory: ”However, in the field of images the range of properties of this function could be increased if the images are defined in Zn rings. The inclusion of the ring theory to the spatial analysis is achieved considering images as a matrix in which the elements belong to the cyclic ring Zn.” Garces indicates the presence of rings in image segmentation through stating that finite cyclic rings can be used to represent matrices in the sense that both have a limited set of elements, and these elements repeat in a cycle when brought back to range (i.e. added or subtracted to bring the elements within the range of the ring or modulus in use). The following is also remarked in Garces’ publication: ”The ring theory for the Mean Shift Iterative Algorithm was employed by defining images in a ring Zn. A good performance of this algorithm was achieved. Therefore, the use of the ring theory could be a good structure when one desires to compare images, due to that the digital images present cyclical properties associated with the pixel values. This property will allow to increase or to diminish the difference among pixels values, and will make possible to find the edges in the analyzed images.” In his work, Garces proves the Mean Shift Iterative Algorithm to be an efficient method of image segmentation as a result of the cyclical aspects that come with the integration of a finite cyclic ring. Finally, Garces et al. iterates the following about entropy being incorporated as the stopping criterion for the Mean Shift Iterative Algorithm: ”Within a totally uniform region, entropy reaches the minimum value. Theoretically speaking, the probability of occurrence of the gray-level value, within a uniform region is always one. In practice, when one works with real images the entropy value does not reach, in general, the zero value. This is due to the existent noise in the image. Therefore, if we consider entropy as a measure of the disorder within a system, it could be used as a good stopping criterion for an iterative process, by using MSHi.” As of now, the entropy function has been set to also serve as the stopping criterion for Mean Shift. The reasoning behind this is that the image after segmentation will hold a certain stability in comparison to the image before.
One of the many important theoretical aspects of the Mean Shift Iterative Algorithm is entropy. Yasel Garces Suarez quotes the following in his publication entitled ”Stopping Criterion for the Mean Shift Iterative Algorithm”: ”Entropy is an essential function in information theory and this has had a special uses for images data, e.g., restoring images, detecting contours, segmenting images and many other applications [12, 15]. However, in the field of images the range of properties of this function could be increased if the images are defined in rings. The inclusion of the ring theory to the spatial analysis is achieved considering images as a matrix in which the elements belong to the cyclic ring Zn. From this point of view, the images present cyclical properties associated to gray level values. It is natural to think that two images are close if their subtraction is close to zero. The problem of this idea is that, in general, when the rest have negative values many authors consider to truncate this elements. This consideration in general not describe the difference between two images, and in some cases is possible to lost important information. For this reason is necessary to define a structure such that the operations between two images are intern.” Within this work, Garces indicates a primary flaw in segmentation research.
Theoretical Aspects
Mean Shift Iterative Algorithm
The algorithm of which will be analyzed has previously been stated to be the Mean Shift Iterative Algorithm. For any given point x, we denote the Mean Shift Iterative Algorithm as follows:
where n represents the amount of points in a picture xi, and i=1, …, n represents the picture as a whole with an unknown density.
Entropy
The entropy function for the Mean Shift Iterative Algorithm is as follows:
where B represents the total number of pixels generated by image A, while p(x) represents the probability of the presence of a grayscale value.
Natural Entropy Distance
The function for the natural entropy distance for MSHi is denoted as such:
where ? and k are the parameters of which will be used to stop the iterations and count thereof.
Weak Equivalence in Images
Two images, A and B, are weakly equivalent if:
Strong Equivalence in Images
In this example, S is used to represent the scalar image. Images A and B are strongly equivalent if A = S+B if images A and B ? Gk?m (Zn)(+, ·).
Criteria for a New Stopping Criterion
The improved Mean Shift Iterative Algorithm will be outlined as such:
- The input will be a set of data points represented by Xk where k serves as the index starting at 1.
- We use the value of 1 because while every ring has the additive identity of zero, not all rings contain the multiplicative identity of 1. Starting the ring with the element of 1 ensures that the ring being used has both the additive and multiplicative identities. To minimize errors in segmentation, we want to include any and all possible elements for the course of this research.
- The output will result in a clustered set of points represented by XIMS.
The steps to use this method of image segmentation are the following:
- Select one data point xik ? Xk whose movement may result in the loss of energy or values.
- Move xik according to xk+2i = xki + IMSkx.
- If satisfies the stopping criterion, then stop. Otherwise, set k = k + 2 and repeat. While other improvements to the Mean Shift Iterative Algorithm (refer to Qi Zhao’s ”Evolved Mean Shift” algorithm) have been previously conceived, the criteria for a new algorithm differs in this paper in the sense that we start the index at 1 and not 0.
Definition 1
While every ring has the additive identity of zero, not every ring has the multiplicative identity of one. Additionally, we move the selected data point X i k according to x k i +2 rather than x k i +1 since the ring of matrices is commutative.
Remark 1
In any commutative ring, any element can be added, subtracted, or multiplied and the result will be another element within the ring.
Definition 2
Image segmentation is the process of partitioning an image into multiple portions as a means of simplifying the process of finding a region of interest for further analysis within that image.
Remark 2
By partitioning an image for segmentation, the values produced represent an array or a matrix of gray-scale presences.
Stopping Criterion
The stopping criterion for the improved Mean Shift will be denoted as such:
- If the value of x, any given pixel value within an image, is greater than Mhx , then the stopping criterion is denoted as KB(x) = K(x), and 0 if x > Mhx where M is a positive constant satisfying that Mhx can cover a large portion or the entire space. At any early stage of improved iterations where a clear configuration of clusters has not been formed, the kernel KB is similar to a broad kernel.
Definition 3
A kernel in image segmentation refers to a broad section of an image that can be categorized under a certain set of values. For instance, a predominantly light section of an image can be classified as a kernel, as each pixel within this area shares the similar characteristic of low (from zero to one) pixel values on a given gray scale.
Remark 3
The number of iterations depends on the construction of the ring and the number of times a certain stopping criterion must be entered in order for the function to come to a complete stop.
Remark 4
Since an iterative method computes successive approximations to the solution of a linear system, a practical test is needed to determine when to stop the iteration. Likewise, since the Mean Shift Iterative Algorithm is capable of performing multiple segmentations on an image (depending on the region of interest), a stopping criterion is defined as the function or coding sequence that can be entered into the segmentation algorithm for the process of an iteration to come to a complete stop.
Remark 5
In the original Mean Shift Iterative Algorithm, the entropy formula takes the place of the stopping criterion for the purpose of maintaining stability along the course of the segmentation of an image. By constructing a new stopping criterion along with an improved version of the Mean Shift Iterative Algorithm, we allow the function to come to a complete stop rather than remaining stable while continuing to perform iterations.
Conclusion
The improved Mean Shift Iterative Algorithm compares to the original Mean Shift Iterative Algorithm in the sense that the stopping criteria differs for each respective method of segmentation. When using the Mean Shift Iterative Algorithm, the functions for the entropy and stopping criterion show no difference, therefore lacking efficiency in commanding the segmentation to stop altogether. In the improved version of the Mean Shift Iterative Algorithm, the stopping criterion is set as an individual function. The reason for this is that we want the function to stop entirely as opposed to maintaining stability. Therefore, if the function using the improved Mean Shift algorithm is able to stop entirely, we will know that the improved Mean Shift algorithm works in a more efficient manner than the original Mean Shift algorithm.
The improved Mean Shift Iterative Algorithm can be used for the segmentation of grayscale, colored, and multispectral images by substituting the d values in the original Mean Shift Iterative Algorithm for 1, 3, and a value greater than 3, respectively. In doing so, a set of pixel values arises. Therefore, a ring can be constructed from said elements. By using this ring, the number of iterations can be measured in order to force the improved Mean Shift Iterative Algorithm by following the newly formed stopping criterion for the IMS.
Suggestions for Further Research
- Expand on the variables listed in the ”Criteria for a New Clustering Algorithm” and explain how each differs from the criteria for the original Mean Shift Iterative Algorithm in a more elaborate manner.
- Locate a platform to test the newly devised algorithm to uncover whether or not the criteria works for both gray-scale and colored images.
- Learn more about the process of image segmentation. as well as other segmentation models (for example, the Epanechnikov kernel function).
- Discuss how other factors can or cannot help the improved Mean Shift Iterative Algorithm. Examples of these factors include vectors, energy convergence, and adaptive bandwidth.
- Devise a coding sequence for the improved Mean Shift Iterative Algorithm, as one is present for the unabridged Mean Shift Iterative Algorithm.
Acknowledgements
- I would like to thank Dr. Rishi Nath of York College for his assistance in learning Ring Theory, enlightenment on writing different forms of research papers, and overall contributions to this research project.
- I would also like to thank Professor Yasel Garces Suarez of the Institute of Cybernetics for reaching out to aid in the learning of image segmentation, as well as for his interest in advancing this research project to greater heights.
References
I. International. The Ring Theory in the Zoning of Images: An Application. Academia.edu – Share Research, www.academia.edu/35503499/The-Ring-Theoryin-the-Zoning-of-Images-An-Application.
Chapter 2: Ring Theory. NTU, www3.ntu.edu.sg/home/Frederique/chap2.pdf.
Chapter 4: Segmentation. BioSS, www.bioss.ac.uk/people/chris/ch4.pdf.
Garces Suarez, Yasel. Application of the Ring Theory in the Segmentation of Digital Images. Arxiv, arxiv.org/pdf/1402.4069.pdf .
Garces, Yasel. EDGE DETECTION IN SEGMENTED IMAGES THROUGH MEAN SHIFT ITERATIVE GRADIENT USING RING. International Journal of Soft Computing, Mathematics and Control , wireilla.com/ns/maths/Papers/4215ijscmc05.pdf.
Garces, Yasel. Stopping Criterion for the Mean Shift Iterative Algorithm. ResearchGate, www.researchgate.net/publication/237092309-Stopping-Criterion-for-theMean-Shift-Iterative-Algorithm.
Goyal, Mokshi. Duadic Negacyclic Codes over a Finite Non-Chain Ring and Their Gray Images. Arxiv, arxiv.org/pdf/1805.09678.pdf.
Hashimoto, Sachi. Introduction to Ring Theory. Boston University, math.bu.edu/people/svh/RingTheoryMathcamp.pdf.
Huynh, Dinh Van. Ring Theory and Its Applications. Ohio State University, www.ams.org/books/conm/609/conm609-endmatter.pdf.
Kaur, Dilpreet. Various Image Segmentation Techniques: A Review. International Journal of Computer Science and Mobile Computing, ijcsmc.com/docs/papers/May2014/V3I5201499a84.pdf.
Liu, Dingding. A Review of Computer Vision Segmentation Algorithms. University of Washington, courses.cs.washington.edu/courses/cse576/12sp/notes/remote.pdf.
Martin, Paul. Notes in Ring Theory. Leeds University, www1.maths.leeds.ac.uk/ ppmartin/LEARN/rings/pdf/lecturesLeedsRPF.pdf.
Palus, Henryk. Color Image Segmentation. ResearchGate, www.researchgate.net/profile/Henryk-Palus.
Pantofaru, Caroline. A Comparison of Image Segmentation Algorithms. Carnegie Mellon University, www.ri.cmu.edu/pub-files/pub4/pantofaru-caroline-2005-1/pantofarucaroline-2005-1.pdf.
Rodrguez, Roberto, et al. A Segmentation Algorithm Based on an Iterative Computation of the Mean Shift Filtering. SpringerLink, Springer Netherlands, 1 Dec. 2010, link.springer.com/article/10.1007/s10846-010-9503-y.
Shimodaira, Hisashi. Automatic Color Image Segmentation Using a Square Elemental Region-Based Seeded Region Growing and Merging Method . Arxiv, arxiv.org/pdf/1711.09352.pdf.
Torres, Esley. Edge Detection in Segmented Images Through the Mean Shift Iterative Algorithm by Using Ring Zn. ResearchGate, file:///C:/Users/rahim/Downloads/ papertheorygroups.pdf
Yuheng, Song. Image Segmentation Algorithms Overview. Arxiv, arxiv.org/pdf/1707.02051.pdf.
