Developing tools and algorithms in digital geometry

Chowdhury, Iffat Sharmin
Journal Title
Journal ISSN
Volume Title

Image segmentation plays an important role in medical imaging, pattern recognition, computer vision and many other applications. It is a process of segmenting objects from an image which is used for image analysis. If the geometric shape of the desired object is known, then incorporating this information in the image segmentation algorithm can improve the results. A non-trivial issue is to determine how to model objects from a precise Euclidean space in an imprecise but implementable discrete array of pixels. One of the big challenges in digital geometry is to develop the correct definition of the digital representation of Euclidean objects, and then give algorithms based on these definitions.

One of the most fundamental and important digital objects is the digital line segment as the definition of many different digital objects depends on the definition of digital line segments (such as digital convex objects). The majority of digital line segments considered in previous research are such that the intersection of two segments may be disconnected. This is a major drawback as Euclidean line segments do not behave in this manner. It is not feasible to have digital line segments intersect in at most one point, and thus we are interested in digital segment systems such that every pair of segments has a connected intersection. A system of digital line segments is called a consistent digital line segments system (CDS) if it satisfies this connected intersection property as well as some other properties satisfied by Euclidean line segments in continuous space. Two previous results on CDSes have provided constructions with optimal Hausdorff distance in two dimensions but left open the problem of characterizing two-dimensional CDSes. Unfortunately, there is very little known about CDSes in higher dimensions. Several new results on CDSes are presented in this thesis. We answer the most important remaining open question by giving the desired characterization in two dimensions. We also take the first significant steps towards obtaining a CDS with optimal Hausdorff distance for d-dimensional line segments coming from two different “slope types” for any fixed d ≥ 3. We then give the first non-trivial framework for computing CDSes (for all segments) in d-dimensions. Finally, we show that if we want to relax some of those Euclidean properties, then systems of digital segments with O(1) Hausdorff distance can be obtained.

The image segmentation problem has a lot of practical applications, so it is important to have algorithms which are very fast in practice. Previous researchers gave efficient algorithms for solving rectilinear convex object which is an object such that the intersection of the object with any horizontal line or any vertical line is always connected. We investigate which geometric objects have image segmentation algorithms that can be solved via reduction to maximum flow, which is very fast in practice. We give a maximum flow-based algorithm that can partition the image into foreground and background such that the foreground can be decomposed into multiple rectilinear convex objects.

This item is available only to currently enrolled UTSA students, faculty or staff.
Consistent Digital Line Segments, Digital Geometry, Image Segmentation
Computer Science