Digital straightness: a review
---
paper_title: Spirograph Theory: A Framework for Calculations on Digitized Straight Lines

paper_content:

Using diagrams called ``spirographs'' a general theory is developed with which one can easily perform calculations on various aspects of digitized straight lines. The mathematics of the theory establishes a link between digitized straight lines and the theory of numbers (Farey series, continued fractions). To show that spirograph theory is a useful unification, we derive two previously known advanced results within the framework of the theory, and new results concerning the accuracy in position of a digitized straight line as a function of its slope and length.
---
paper_title: Digital Straight Line Segments

paper_content:

It is shown that a digital arc S is the digitization of a straight line segment if and only if it has the "chord property:" the line segment joining any two points of S lies everywhere within distance 1 of S. This result is used to derive several regularity properties of digitizations of straight line segments.
---
paper_title: Linguistic Methods for the Description of a Straight Line on a Grid

paper_content:

This paper describes the construction of strings representing straight lines in an arbitrary direction on a grid and compares some grammatical systems that generate these strings. An algorithm is given that constructs a string representing a straight line on a grid in Freeman's coding scheme. Some number-theoretical aspects of this algorithm are treated (Euclid's algorithm, Farey series, continued fractions). This algorithm is based on. structural properties of the string. Strings generated in this way can also be produced with a programmed grammar. Lindenmayer grammars are also very powerful for this kind of problem, because of the simultaneous applications of production rules. Another method for constructing strings representing straight lines, where the generation is essentially sequential, for instance when noise is added, is treated. In this case Lindenmayer grammars are quite useless, but programmed grammars are still very convenient. Rule-labeled programs are less convenient for both kinds of problems.
---
paper_title: Discrete Representation of Straight Lines

paper_content:

If a continuous straight line segment is digitized on a regular grid, obviously a loss of information occurs. As a result, the discrete representation obtained (e.g., a chaincode string) can be coded more conveniently than the continuous line segment, but measurements of properties (such as line length) performed on the representation have an intrinsic inaccuracy due to the digitization process. In this paper, two fundamental properties of the quantization of straight line segments are treated. 1) It is proved that every ``straight'' chaincode string can be represented by a set of four unique integer parameters. Definitions of these parameters are given. 2) A mathematical expression is derived for the set of all continuous line segments which could have generated a given chaincode string. The relation with the chord property is briefly discussed.
---
paper_title: The Discrete Equation of the Straight Line

paper_content:

A new method of description of a straight line defined on a square grid is presented. The discrete equation of the straight line (desl) is introduced as an extension of the classical Cartesian equation, and applies to straight lines quantized on a grid by the grid intersect method. The desl includes a set of intercepts which can be scanned in proper order to generate the chain for the given straight line.
---
paper_title: Digital Computer Transformations for Irregular Line Drawings

paper_content:

Abstract : The report describes a parametric quantization scheme for irregular line drawings. With this scheme, different quantized versions of the same drawing can be obtained by changing the values of the parameters. Three figures of noise are proposed for evaluating the quality of quantized drawings and design formulae are developed for the parameters of the quantization scheme as functions of bounds on the figures of noise. The degradation of the quality of a quantized drawing resulting from a coordinate transformation and requantization is studied in terms of transformed figures of noise. Also, it is shown theoretically and by means of a number of examples how to choose the parameters of the quantization scheme in order to meet the requirements on the transformed figures of noise. This enables one to quantize a preprocessed satellite picture so that after computation of a Mercator projection, the resulting geographic map will have the required quality. The theory presented in this report is applicable to any irregular line drawing and to any transformation defined by a pair of functions that are continuous together with their partial derivatives.
---
paper_title: Digital Straight Line Segments

paper_content:

It is shown that a digital arc S is the digitization of a straight line segment if and only if it has the "chord property:" the line segment joining any two points of S lies everywhere within distance 1 of S. This result is used to derive several regularity properties of digitizations of straight line segments.
---
paper_title: Linguistic Methods for the Description of a Straight Line on a Grid

paper_content:

This paper describes the construction of strings representing straight lines in an arbitrary direction on a grid and compares some grammatical systems that generate these strings. An algorithm is given that constructs a string representing a straight line on a grid in Freeman's coding scheme. Some number-theoretical aspects of this algorithm are treated (Euclid's algorithm, Farey series, continued fractions). This algorithm is based on. structural properties of the string. Strings generated in this way can also be produced with a programmed grammar. Lindenmayer grammars are also very powerful for this kind of problem, because of the simultaneous applications of production rules. Another method for constructing strings representing straight lines, where the generation is essentially sequential, for instance when noise is added, is treated. In this case Lindenmayer grammars are quite useless, but programmed grammars are still very convenient. Rule-labeled programs are less convenient for both kinds of problems.
---
paper_title: Languages of encoded line patterns

paper_content:

By treating patterns as statements in a two-dimensional language, it is possible to apply linguistic theory to pattern analysis and recognition. In this paper, line patterns are encoded into string form using the chain code developed by Freeman. A class of patterns, or pattern language, encodes to a set of strings that is examined using theory that exists for string languages and automata. Pattern languages formed on the basis of equations in two variables and various pattern properties are related to the hierarchy of string language classes. The known relationships between classes of string languages and classes of automata can then be applied to determine bounds on the time and memory required to recognize the various patterns. Results can be extended to other forms of pattern encoding provided that a suitable translator can be constructed.
---
paper_title: Regular Arcs in Digital Contours

paper_content:

Abstract The concept of regularity plays an important role in the study of the arcs of a digital contour. In this paper, the structure of regular digital arcs is investigated and, once given a general definition of straightness for digital contour arcs, a necessary and sufficient condition for the straightness of regular arcs is given. This condition only depends on parameters characterizing the macrodescription of the regular digital arc; its equivalence with the chord property is also shown. The knowledge of the structure of regular digital arcs can be a good starting point for the study of nonregular digital arcs, so that it could be possible to formulate a general algorithm to detect both concavity and convexity.
---
paper_title: A simple proof of Rosenfeld's characterization of digital straight line segments

paper_content:

A digital straight line segment is defined as the grid-intersect quantization of a straight line segment in the plane. Let S be a set of pixels on a square grid. Rosenfeld [8] showed that S is a digital straight line segment if and only if it is a Digital arc having the chord property. Then Kim and Rosenfeld [3,6] showed that S has the chord properly if and if for every p, q@eS there is a digital straight line segment C @? S such that p and q are the extremities of C. We give a simple proof of these two results based on the Transversal Theorem of Santalo. We show how the underlying methodology can be generalized to the case of (infinite) digital straight lines and to the quantization of hyperplanes in an n-dimensional space for n >= 3.
---
paper_title: A compact chord property for digital arcs

paper_content:

Abstract Rosenfeld ( IEEE Trans. Comput. C-23 (12), 1264–1269 (1974)) defined the chord property and proved that a digital arc is a digital straight segment if and only if it satisfies the chord property. A new property is defined, which we call the compact chord property, and the two properties are proved to be equivalent. The compact chord property offers a useful alternative for testing a digital arc for straightness by exploiting the notion of visibility in computational geometry.
---
paper_title: Digital Straight Line Segments

paper_content:

It is shown that a digital arc S is the digitization of a straight line segment if and only if it has the "chord property:" the line segment joining any two points of S lies everywhere within distance 1 of S. This result is used to derive several regularity properties of digitizations of straight line segments.
---
paper_title: On the parallel generation of straight digital lines

paper_content:

Several procedures have been devised to generate strainght digital lines; among others an algorithm has been proposed in the literature which accomplishes the generation in a parallel fashion. The main purpose of this paper is to show that the constructed digital line possesses the chord property, and therefore is really straight. To reach this goal the geometrical properties of the generated digital line have been investigated and advantage has been taken of a theory developed in the past to study regular arcs of digital contours. A comparison between the performances of the parallel algorithm and of a sequential one, showing the convenience of the parallel approach, is also included.
---
paper_title: Spirograph Theory: A Framework for Calculations on Digitized Straight Lines

paper_content:

Using diagrams called ``spirographs'' a general theory is developed with which one can easily perform calculations on various aspects of digitized straight lines. The mathematics of the theory establishes a link between digitized straight lines and the theory of numbers (Farey series, continued fractions). To show that spirograph theory is a useful unification, we derive two previously known advanced results within the framework of the theory, and new results concerning the accuracy in position of a digitized straight line as a function of its slope and length.
---
paper_title: Discrete images, objects, and functions in Z[n]

paper_content:

Content.- 1 Neighborhood Structures.- 1.1 Finite Graphs.- 1.1.1 Historical Remarks.- 1.1.2 Elementary Theory of Sets and Relations.- 1.1.3 Elementary Graph Theory.- 1.2 Neighborhood Graphs.- 1.2.1 Graph Theory and Image Processing.- 1.2.2 Points, Edges, Paths, and Regions.- 1.2.3 Matrices of Adjacency.- 1.2.4 Graph Distances.- 1.3 Components in Neighborhood Structures.- 1.3.1 Search in Graphs and Labyrinths.- 1.3.2 Neighborhood Search.- 1.3.3 Graph Search in Images.- 1.3.4 Neighbored Sets and Separated Sets.- 1.3.5 Component Labeling.- 1.4 Dilatation and Erosion.- 1.4.1 Metric Spaces.- 1.4.2 Boundaries and Cores in Neighborhood Structures.- 1.4.3 Set Operations and Set Operators.- 1.4.4 Dilatation and Erosion.- 1.4.5 Opening and Closing.- 2 Incidence Structures.- 2.1 Homogeneous Incidence Structures.- 2.1.1 Topological Problems.- 2.1.2 Cellular Complexes.- 2.1.3 Incidence Structures.- 2.1.4 Homogeneous Incidence Structures.- 2.1.5 Zn as Incidence Structure.- 2.2 Oriented Neighborhood Structures.- 2.2.1 Orientation of a Neighborhood Structure.- 2.2.2 Euler Characteristic of a Neighborhood Structure.- 2.2.3 Border Meshes and Separation Theorem.- 2.2.4 Search in Oriented Neighborhood Structures.- 2.2.5 Coloring in Oriented Neighborhood Structures.- 2.3 Homogeneous Oriented Neighborhood Structures.- 2.3.1 Homogeneity in Neighborhood Structures.- 2.3.2 Toroidal Nets.- 2.3.3 Curvature of Border Meshes in Toroidal Nets.- 2.3.4 Planar Semi-Homogeneous Graphs.- 2.4 Objects in N-Dimensional Incidence Structures.- 2.4.1 Three-Dimensional Homogeneous Incidence Structures.- 2.4.2 Objects in Zn.- 2.4.3 Similarity of Objects.- 2.4.4 General Surface Formulas.- 2.4.5 Interpretation of Object Characteristics.- 3 Topological Laws and Properties.- 3.1 Objects and Surfaces.- 3.1.1 Surfaces in Discrete Spaces.- 3.1.2 Contur Following as Two-Dimensional Boundary Detection.- 3.1.3 Three-Dimensional Surface Detection.- 3.1.4 Curvature of Conturs and Surfaces.- 3.2 Motions and Intersections.- 3.2.1 Motions of Objects in Zn.- 3.2.2 Count Measures and Intersections of Objects.- 3.2.3 Applications of Intersection Formula.- 3.2.4 Count Formulas.- 3.2.5 Stochastic Images.- 3.3 Topology Preserving Operations.- 3.3.1 Topological Equivalence.- 3.3.2 Simple Points.- 3.3.3 Thinning.- 4 Geometrical Laws and Properties.- 4.1 Discrete Geometry.- 4.1.1 Geometry and Number Theory.- 4.1.2 Minkowski Geometry.- 4.1.3 Translative Neighborhood Structures.- 4.1.4 Digitalization Effects.- 4.2 Straight Lines.- 4.2.1 Rational Geometry.- 4.2.2 Digital Straight Lines in Z2.- 4.2.3 Continued Fractions.- 4.2.4 Straight Lines in Zn.- 4.3 Convexity.- 4.3.1 Convexity in Discrete Geometry.- 4.3.2 Maximal Convex Objects.- 4.3.3 Determination of Convex Hull.- 4.3.4 Convexity in Zn.- 4.4 Approximative Motions.- 4.4.1 Pythagorean Rotations.- 4.4.2 Shear Transformations.- 4.3.3 General Affine Transformations.- 5 Discrete Functions.- 5.1 One-Dimensional Periodical Discrete Functions.- 5.1.1 Functions.- 5.1.2 Space of Periodical Discrete Function.- 5.1.3 LSI-Operators and Convolutions.- 5.1.4 Products of Linear Operators.- 5.2 Algebraic Theory of Discrete Functions.- 5.2.1 Domain of Definition and Range of Values.- 5.2.2 Algebraical Structures.- 5.2.3 Convolution of Functions.- 5.2.4 Convolution Orthogonality.- 5.3 Orthogonal Convolution Bases.- 5.3.1 General Properties in OCB's.- 5.3.2 Fourier Transform.- 5.3.3 Number Theoretical Transforms.- 5.3.4 Two-Dimensional NTT.- 5.4 Inversion of Convolutions.- 5.4.1 Conditions for Inverse Elements.- 5.4.2 Deconvolutions and Texture Synthesis.- 5.4.3 Approximative Computation of Inverse Elements.- 5.4.4 Theory of Approximative Inversion.- 5.4.5 Examples of Inverse Filters.- 5.5 Differences and Sums of Functions.- 5.5.1 Differences of One-Dimensional Discrete Functions.- 5.5.2 Difference Equations and Z-Transform.- 5.5.3 Sums of Functions.- 5.5.4 Bernoulli's Polynomials.- 5.5.5 Determination of Moments.- 5.5.6 Final Comments.- 6 Summary and Symbols.- 7 References.- 8 Index.
---
paper_title: Geometry of Continued Fractions

paper_content:

MICHAEL CHARLES IRWIN wrote his Ph.D. thesis (Cambridge University, U.K., 1962) on "Embeddings of Polyhedral Manifolds," and his early papers were concerned with piecewise linear topology, but from about 1970 onwards his research was mainly on dynamical systems. His most recent publications included work on invariant paths for Anosov diffeomorphisms. He was the author of the book Smooth Dynamical Systems published by Academic Press in 1980. He taught at the University of Liverpool, U.K., from 1961 until his death on March 11, 1988.
---
paper_title: On the number of digital straight line segments

paper_content:

A closed-form expression has been reported in the literature for L/sub N/, the number of digital line segments of length N that correspond to lines of the form y=ax+ beta , O >
---
paper_title: Linguistic Methods for the Description of a Straight Line on a Grid

paper_content:

This paper describes the construction of strings representing straight lines in an arbitrary direction on a grid and compares some grammatical systems that generate these strings. An algorithm is given that constructs a string representing a straight line on a grid in Freeman's coding scheme. Some number-theoretical aspects of this algorithm are treated (Euclid's algorithm, Farey series, continued fractions). This algorithm is based on. structural properties of the string. Strings generated in this way can also be produced with a programmed grammar. Lindenmayer grammars are also very powerful for this kind of problem, because of the simultaneous applications of production rules. Another method for constructing strings representing straight lines, where the generation is essentially sequential, for instance when noise is added, is treated. In this case Lindenmayer grammars are quite useless, but programmed grammars are still very convenient. Rule-labeled programs are less convenient for both kinds of problems.
---
paper_title: The Discrete Equation of the Straight Line

paper_content:

A new method of description of a straight line defined on a square grid is presented. The discrete equation of the straight line (desl) is introduced as an extension of the classical Cartesian equation, and applies to straight lines quantized on a grid by the grid intersect method. The desl includes a set of intercepts which can be scanned in proper order to generate the chain for the given straight line.
---
paper_title: On the number of factors of Sturmian words

paper_content:

Abstract We prove that for m ⩾1, card( A m ) = 1+∑ m i =1 ( m − i +1) ϕ ( i ) where A m is the set of factors of length m of all the Sturmian words and ϕ is the Euler function. This result was conjectured by Dulucq and Gouyou-Beauchamps (1987) who proved that this result implies that the language (∪ m ⩾0 A m ) c is inherently ambiguous. We also give a combinatorial version of the Riemann hypothesis.
---
paper_title: Spirograph Theory: A Framework for Calculations on Digitized Straight Lines

paper_content:

Using diagrams called ``spirographs'' a general theory is developed with which one can easily perform calculations on various aspects of digitized straight lines. The mathematics of the theory establishes a link between digitized straight lines and the theory of numbers (Farey series, continued fractions). To show that spirograph theory is a useful unification, we derive two previously known advanced results within the framework of the theory, and new results concerning the accuracy in position of a digitized straight line as a function of its slope and length.
---
paper_title: Compression of chain codes using digital straight line sequences

paper_content:

Abstract Compression of chain codes is achieved by breaking the sequence into strings of digital straight lines whose representation is stored in a table. It is shown that the number of table entries is ( 1 4π 2 )N 4 + O (N 3 log N) . A computational method is given for an exact determination which shows that the asymptotic approximation is accurate.
---
paper_title: The number of digital straight lines on an N×N grid

paper_content:

The number of digital straight lines on an N*N grid is shown. A digital straight line is equivalent to a linear dichotomy of points on a square grid. The result is obtained by determining a way of counting the number of linearly separable dichotomies of points on the plane that are not necessarily in general position. The analysis is easily modified to provide a simple solution to a similar problem considered by C. Berenstein and D. Lavine (1988) on the number of digital straight lines from a fixed starting point. >
---
paper_title: A Method for Obtaining Skeletons Using a Quasi-Euclidean Distance

paper_content:

The problem of obtaining the skeleton of a digitized figure is reduced to an optimal policy problem. A hierarchy of methods of defining the skeleton is proposed; in the more complicated ones, the skeleton is relatively invariant under rotation. Two algorithms for computing the skeleton are defined, and the corresponding computer programs are compared. A criterion is proposed for determining the most significant skeleton points.
---
paper_title: On the number of digital straight line segments

paper_content:

A closed-form expression has been reported in the literature for L/sub N/, the number of digital line segments of length N that correspond to lines of the form y=ax+ beta , O >
---
paper_title: Linguistic Methods for the Description of a Straight Line on a Grid

paper_content:

This paper describes the construction of strings representing straight lines in an arbitrary direction on a grid and compares some grammatical systems that generate these strings. An algorithm is given that constructs a string representing a straight line on a grid in Freeman's coding scheme. Some number-theoretical aspects of this algorithm are treated (Euclid's algorithm, Farey series, continued fractions). This algorithm is based on. structural properties of the string. Strings generated in this way can also be produced with a programmed grammar. Lindenmayer grammars are also very powerful for this kind of problem, because of the simultaneous applications of production rules. Another method for constructing strings representing straight lines, where the generation is essentially sequential, for instance when noise is added, is treated. In this case Lindenmayer grammars are quite useless, but programmed grammars are still very convenient. Rule-labeled programs are less convenient for both kinds of problems.
---
paper_title: Digital Straight Lines and Convexity of Digital Regions

paper_content:

It is shown that a digital region is convex if and only if every pair of points in the region is connected by a digital straight line segment contained in the region. The midpoint property is shown to be a necessary but not a sufficient condition for the convexity of digital regions. However, it is shown that a digital region is convex if and only if it has the median-point property.
---
paper_title: Fast polygonal approximation of digitized curves

paper_content:

Abstract We describe a new technique for fast “scan-along” computation of piecewise linear approximations of digital curves in 2-space. Our method is derived from earlier work on the theory of minimum-perimeter polygonal approximations of digitized closed curves. We demonstrate the specialization of this technique to the case where the error is measured as the largest Hausdorff-Euclidean distance between the approximation and the given digitized curve. We illustrate the application of this procedure to the boundaries of the images of a lung and a rib in chest radiographs.
---
paper_title: On recursive, O(N) partitioning of a digitized curve into digital straight segments

paper_content:

A simple online algorithm for partitioning of a digital curve into digital straight-line segments of maximal length is given. The algorithm requires O(N) time and O(1) space and is therefore optimal. Efficient representations of the digital segments are obtained as byproducts. The algorithm also solves a number-theoretical problem concerning nonhomogeneous spectra of numbers. >
---
paper_title: A note on minimal length polygonal approximation to a digitized contour

paper_content:

A method for extracting a smooth polygonal contour from a digitized image is illustrated. The ordered sequence of contour points and the connection graph of the image are first obtained by a modified Ledley algorithm in one image scan. A minimal perimeter polygon subjected to specified constraints is then chosen as the approximating contour. The determination of the minimal polygon can be reduced to a nonlinear programming problem, solved by an algorithm which takes into account the weak bonds between variables. Some examples are presented, and the corresponding computing times are listed.
---
paper_title: A new method of analysis for discrete straight lines

paper_content:

Abstract The problem of finding the set of all continuous straight lines which lead to the same digitization is quite well known and has been studied in [1, 2, 3]. In this paper, we propose a new method of analysis which is simple and straightforward but is shown to be as powerful as the other techniques. Moreover, our scheme, being algebraic in nature, can be generalized to more complex shapes and figures and thus has a wider applicability.
---
paper_title: A comparative evaluation of length estimators

paper_content:

The paper compares previously published length estimators having digitized curves as input. The evaluation uses multigrid convergence (theoretical results and measured speed of convergence) and further measures as criteria. The paper also suggests a new gradient-based method for length estimation.
---
paper_title: Discrete Representation of Straight Lines

paper_content:

If a continuous straight line segment is digitized on a regular grid, obviously a loss of information occurs. As a result, the discrete representation obtained (e.g., a chaincode string) can be coded more conveniently than the continuous line segment, but measurements of properties (such as line length) performed on the representation have an intrinsic inaccuracy due to the digitization process. In this paper, two fundamental properties of the quantization of straight line segments are treated. 1) It is proved that every ``straight'' chaincode string can be represented by a set of four unique integer parameters. Definitions of these parameters are given. 2) A mathematical expression is derived for the set of all continuous line segments which could have generated a given chaincode string. The relation with the chord property is briefly discussed.
---
paper_title: Length estimation of digital curves

paper_content:

The paper details two linear-time algorithms, one for the partition of the boundary line of a digital region into digital straight segments, and one for calculating the minimum length polygon within an open boundary of a digital region. Both techniques allow the estimation of the length of digital curves or the perimeter of digital regions due to known multigrid convergence theorems. The algorithms are compared with respect to convergence speed and number of generated segments.© (1999) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.
---
paper_title: Digital Convexity, Straightness, and Convex Polygons

paper_content:

New schemes for digitizing regions and arcs are introduced. It is then shown that under these schemes, Sklansky's definition of digital convexity is equivalent to other definitions. Digital convex polygons of n vertices are defined and characterized in terms of geometric properties of digital line segments. Also, a linear time algorithm is presented that, given a digital convex region, determines the smallest integer n such that the region is a digital convex n-gon.
---
paper_title: Analysis and modeling of digitized straight-line segments

paper_content:

A general formula for the slope and mathematical models of digitized straight-line segments are derived and discussed in detail. The models are parametric and the parameters are calculated uniquely and in closed form from the slope without the need for recursion or interaction. The modeling is information-preserving and explicitly uses the slope. The models are in a form convenient for plotting, detecting, and recognizing digitized straight-line segments. >
---
paper_title: An optimal O(n) algorithm for identifying line segments from a sequence of chain codes

paper_content:

Abstract An optimal algorithm for identifying straight lines in chain codes is described. The algorithm turns the complicated problem of determining the straightness of digital arcs into a simple task by constructing a passing area around the pixels. It also solves the problem of detecting all straight segments from a sequence of chain codes in O ( n ) time, where n is the length of the sequence. It has been found that this algorithm is not only simple and intuitive, but also highly efficient.
---
paper_title: Recognizing arithmetic straight lines and planes

paper_content:

The problem of recognizing a straight line in the discrete plane ℤ2 (resp. a plane in ℤ3) is to find an algorithm deciding wether a given set of points in ℤ2 (resp. ℤ3) belongs to a line (resp. a plane). In this paper the lines and planes are arithmetic, as defined by Reveilles [Rev91], and the problem is translated, for any width that is a linear function of the coefficients of the normal to the searched line or plane, into the problem of solving a set of linear inequalities. This new problem is solved by using the Fourier's elimination algorithm. If there is a solution, the family of solutions is given by the algorithm as a conjunction of linear inequalities. This method of recognition is well suited to computer imagery, because any traversal algorithm of the given set is possible, and also because any incomplete segment of line or plane can be recognized.
---
paper_title: Characterizing Digital Convexity and Straightness in Terms of "Length" and "Total Absolute Curvature"

paper_content:

By using the anisotropic version of “length” and “total absolute curvature” proposed by K. Kishimoto and M. Iri (Jpn. J. Appl. Math.6, 1989, 179?207), this paper characterizes digital convexity and digital straightness as follows:1.a bounded digital figureFis digitally convex if and only if the “total absolute curvature” of its boundary is 2?;2.a digital arcs(F) is digitally straight if and only if either of the following conditions is satisfied:(a)the “total absolute curvature” ofs(F) is 0;(b)the “length” ofs(F) is “sufficiently” small.These characterizations indicate that the presented definitions may serve as a bridge between the continuous and digital worlds.
---
paper_title: Discrete Convexity, Straightness, and the 16-Neighborhood

paper_content:

In this paper, we extend some results in discrete geometry based on the 8-neighborhood to that of the 16-neighborhood, which now includes the chessboard and the knight moves. We first present some analogies between an 8-digital arc and a 16-digital arc as represented by shortest paths on the grid. We present a transformation which uniquely maps a 16-digital arc onto an 8-digital arc (and vice versa). The grid-intersect-quantization (GIQ) of real arcs is defined with the 16-neighborhood. This enables us to define a 16-digital straight segment. We then present two new distance functions which satisfy the metric properties and describe the extended neighborhood space. Based on these functions, we present some new results regarding discrete convexity and 16-digital straightness. In particular, we demonstrate the convexity of a 16-digital straight segment. Moreover, we define a new property for characterizing a digital straight segment in the 16-neighborhood space. In comparison to the 8-neighborhood space, the proposed 16-neighborhood coding scheme offers a more compact representation without any loss of information.
---
paper_title: Some aspects of the accuracy of the approximated position of a straight line on a square grid

paper_content:

In a digitized scan of a picture on a square grid the grid spacing (sampling distance) and the number of gray levels can be varied. The influence of these variables on the maximum error of approximation of the position of a black straight line with rectangular profile on a white background is determined. From the results the grid spacing required to get an error below a given value is determined as a function of the number of equidistant gray levels used. With some assumptions about the storage of the data the corresponding amount of memory space is determined. The latter has a minimum for a certain number of gray levels which depends on the specified maximum error.
---

Title: Digital Straightness: A Review

Section 1: Introduction
Description 1: Introduce the topic of digital straightness, its historical context, and its significance in pattern recognition and related disciplines.

Section 2: Tangential lines and connectivity
Description 2: Discuss alternative definitions of digital rays, focusing on the concepts of tangential lines and connectivity within the grid system.

Section 3: Self-similarity studies in pattern recognition
Description 3: Review self-similarity properties of digital rays and their applications in pattern recognition, detailing the geometric characterizations and efficient algorithms.

Section 4: Periodicity studies in the theory of words
Description 4: Explore the periodicity and structure of digital rays in the context of the theory of words, including basic definitions, properties, and related theorems.

Section 5: Number-theoretical studies
Description 5: Examine the number-theoretical aspects of digital straightness, including algorithms and the role of continuous fractions and Farey series in modeling digital rays.

Section 6: Algorithms for DSS recognition
Description 6: Provide an overview of various algorithms developed for the recognition of digital straight segments (DSSs), detailing their methodologies, efficiencies, and applications.

Section 7: Conclusions
Description 7: Summarize the findings of the review, highlight remaining challenges, and propose areas for future research in the study of digital straightness.