<p>See <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.49.9480&amp;rep=rep1&amp;type=pdf" rel="nofollow">Random Generation of Finite Sturmian Words</a> by Berstel and Pocchiola for a proof that the feasible region of your LP has only three or four sides, as well as a simple algorithm for finding the polygon given slope and intercept.  (They are dealing with recognizing Sturmian Words, but the problems are strongly related.)</p>

<p>They also give an explicit enumeration of the polygons, so it may be possible to enumerate the areas of the polygons and the ranges of the slopes, so you may be able to get the expected value of the range of slopes (as well as higher moments)  as an explicit sum.</p>

CC BY-SA 2.5
2011-04-07T14:59:31.090Z
2011-04-07T14:59:31.090Z
deinst
<p>The computational geometry approach would replace each pixel (i,j) with vertical segment (i, j+[-1/2,1/2]), take the convex hulls of the upper and lower sets of endpoints, and compute the inner common tangents -- these delimit the range of slopes that produce this digital line. This is just the geometric interpretation of the linear program that you mention in your slides.  O(n) time suffices for the LP by Meggiddo, or for the hulls and tangents by Graham-Yao.  </p>

CC BY-SA 2.5
2011-03-31T13:18:41.833Z
2011-03-31T13:18:41.833Z
Jack
<p>What about the standard Hough transform method that is used for line detection in image processing: <a href="http://en.wikipedia.org/wiki/Hough_transform" rel="nofollow">http://en.wikipedia.org/wiki/Hough_transform</a> ?</p>

<p>If you want to gain some speed then you can use the randomized version of HT.</p>

CC BY-SA 2.5
2011-03-29T07:25:34.097Z
2011-03-29T07:25:34.097Z
Marzio De Biasi
<ul>
<li><p>I don't know of any work in cg (or any other group for that matter) on deriving slope from the set of discrete points, but that's more a reflection of my lack of knowledge.</p></li>
<li><p>Rather than cg, this seems more like number theory. In addition to the simplifying assumptions in my comment, assume that the real slope is between 0 and 1. Since your set is contiguous, the number of points is the max denominator of the slope. The pattern of the unit rises is determined by the GCD of the actual $\Delta y$ and $\Delta x$ (an extension of the Euclidean GCD computes the same points as the Bresenham line drawing algorithm). So computing the (augmented) gcd of the number of points (for the $x$) and the last $y$ minus the first, will get you the closest rational to the slope with the largest denominator (see the Stern-Brocot tree). So in some sense, you hardly need the pattern of points at all, just the change in $x$ and $y$.</p></li>
</ul>

CC BY-SA 2.5
2011-03-30T04:35:28.443Z
Mitch, your proposal for looking at just the first and last points only lets you reconstruct the slope to within $O(1/n)$.  One can do considerably better by looking at the points in between.  But you're right about this being a very number-theoretic problem!
Jim Propp
CC BY-SA 2.5
2011-03-29T20:52:35.667Z
2011-03-29T20:52:35.667Z
Mitch
<p>Has there been any work on recovering the slope of a line segment from its digitization?
One can't do this with perfect accuracy, of course; what one wants is a method of deriving from a digitized line an interval of possible slopes.</p>

<p>(The notion of a digitized line that I am using is Rosenfeld's: the set of pairs $(i,nint(ai+b))$ where $i$ ranges over the integers (or a block of consecutive integers) and $nint(x)$ denotes the integer nearest to $x$ (if $x=k+1/2$, we take $nint(x)=k$).)</p>

<p>I've done some work on this on my own (see <a href="http://jamespropp.org/SeeSlope.nb" rel="nofollow">http://jamespropp.org/SeeSlope.nb</a>) but I have
no formal background in computational geometry so I suspect I may be reinventing the wheel, since the question seems like such a basic one.</p>

<p>In fact, I know that the linear regression method of estimating the slope is in the 
literature, but I haven't been able to find my $O(1/n^{1.5})$ result anywhere.  (This
result says that if one chooses $a$ and $b$ uniformly at random in $[0,1]$, then the 
difference between the slope $a$ of the line $y=ax+b$ and the slope $\overline{a}$ of
the regression line approximating the $n$ points $(i,nint(ai+b))$ ($1 \leq i \leq n$) 
has standard deviation $O(1/n^{1.5})$.)</p>

<p>Any leads or pointers to relevant literature will be greatly appreciated.</p>

<p>Jim Propp (JamesPropp@ignorethis.gmail.com)</p>

CC BY-SA 2.5
2011-03-29T06:42:45.543Z
So an $n$-point digitization is roughly speaking a set of cells from an $n \times n$ grid ?
Suresh Venkat
CC BY-SA 2.5
2011-03-29T09:10:32.353Z
What exactly do you mean by digitized line? I assumed you meant something like a straight line in a photo or a rasterized image, but from the talk of linear regression it sounds more like you are interested in finding a line of best fit for some sampled data.
Joe Fitzsimons
CC BY-SA 2.5
2011-03-29T20:54:06.790Z
So the model you're interested in is not an exact solution of $a$ and $b$, but just an approximation to them? I'd simplify the problem by not considering $b$ (it's just an annoying shift), and by sticking with $\lfloor a x \rfloor $ (turns out this is just another shift). Also, what is $n$ here?
Mitch
CC BY-SA 2.5
2011-03-30T04:32:40.070Z
Sorry, Mitch; I forgot to explain what $n$ was!  I've added that to the original post. - Jim
Jim Propp
<reference-request><cg.comp-geom><cv.computer-vision><image-processing>
Recovering the slope of a digitized line
Jim Propp
# Recovering the slope of a digitized line

(Asked by: username_0 on 2011-03-29)

Has there been any work on recovering the slope of a line segment from its digitization?
One can't do this with perfect accuracy, of course; what one wants is a method of deriving from a digitized line an interval of possible slopes.

(The notion of a digitized line that I am using is Rosenfeld's: the set of pairs $(i,nint(ai+b))$ where $i$ ranges over the integers (or a block of consecutive integers) and $nint(x)$ denotes the integer nearest to $x$ (if $x=k+1/2$, we take $nint(x)=k$).)

I've done some work on this on my own (see <http://jamespropp.org/SeeSlope.nb>) but I have
no formal background in computational geometry so I suspect I may be reinventing the wheel, since the question seems like such a basic one.

In fact, I know that the linear regression method of estimating the slope is in the
literature, but I haven't been able to find my $O(1/n^{1.5})$ result anywhere. (This
result says that if one chooses $a$ and $b$ uniformly at random in $[0,1]$, then the
difference between the slope $a$ of the line $y=ax+b$ and the slope $\overline{a}$ of
the regression line approximating the $n$ points $(i,nint(ai+b))$ ($1 \leq i \leq n$)
has standard deviation $O(1/n^{1.5})$.)

Any leads or pointers to relevant literature will be greatly appreciated.

Jim Propp (JamesPropp@ignorethis.gmail.com)

**Tags:** reference-request, cg.comp-geom, cv.computer-vision, image-processing
> **Comments:**
> **username_1**: So an $n$-point digitization is roughly speaking a set of cells from an $n \times n$ grid ?  
> **username_2**: What exactly do you mean by digitized line? I assumed you meant something like a straight line in a photo or a rasterized image, but from the talk of linear regression it sounds more like you are interested in finding a line of best fit for some sampled data.  
> **username_3**: So the model you're interested in is not an exact solution of $a$ and $b$, but just an approximation to them? I'd simplify the problem by not considering $b$ (it's just an annoying shift), and by sticking with $\lfloor a x \rfloor $ (turns out this is just another shift). Also, what is $n$ here?  
> **username_0**: Sorry, Mitch; I forgot to explain what $n$ was!  I've added that to the original post. - Jim  

---

## 4 answers

### Answer by username_4 on 2011-04-07. Score: 1 | Accepted answer

See [Random Generation of Finite Sturmian Words](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.49.9480&rep=rep1&type=pdf) by Berstel and Pocchiola for a proof that the feasible region of your LP has only three or four sides, as well as a simple algorithm for finding the polygon given slope and intercept. (They are dealing with recognizing Sturmian Words, but the problems are strongly related.)

They also give an explicit enumeration of the polygons, so it may be possible to enumerate the areas of the polygons and the ranges of the slopes, so you may be able to get the expected value of the range of slopes (as well as higher moments) as an explicit sum.


---

### Answer by username_5 on 2011-03-31. Score: 4

The computational geometry approach would replace each pixel (i,j) with vertical segment (i, j+[-1/2,1/2]), take the convex hulls of the upper and lower sets of endpoints, and compute the inner common tangents -- these delimit the range of slopes that produce this digital line. This is just the geometric interpretation of the linear program that you mention in your slides. O(n) time suffices for the LP by Meggiddo, or for the hulls and tangents by Graham-Yao.


---

### Answer by username_6 on 2011-03-29. Score: 2

What about the standard Hough transform method that is used for line detection in image processing: <http://en.wikipedia.org/wiki/Hough_transform> ?

If you want to gain some speed then you can use the randomized version of HT.


---

### Answer by username_3 on 2011-03-29. Score: 1

* I don't know of any work in cg (or any other group for that matter) on deriving slope from the set of discrete points, but that's more a reflection of my lack of knowledge.
* Rather than cg, this seems more like number theory. In addition to the simplifying assumptions in my comment, assume that the real slope is between 0 and 1. Since your set is contiguous, the number of points is the max denominator of the slope. The pattern of the unit rises is determined by the GCD of the actual $\Delta y$ and $\Delta x$ (an extension of the Euclidean GCD computes the same points as the Bresenham line drawing algorithm). So computing the (augmented) gcd of the number of points (for the $x$) and the last $y$ minus the first, will get you the closest rational to the slope with the largest denominator (see the Stern-Brocot tree). So in some sense, you hardly need the pattern of points at all, just the change in $x$ and $y$.

> **Comments:**
> **username_0**: Mitch, your proposal for looking at just the first and last points only lets you reconstruct the slope to within $O(1/n)$.  One can do considerably better by looking at the points in between.  But you're right about this being a very number-theoretic problem!  

---

