11
$\begingroup$

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 ([email protected])

Improve this question
$\endgroup$
4
  • $\begingroup$ So an $n$-point digitization is roughly speaking a set of cells from an $n \times n$ grid ? $\endgroup$
    – Suresh Venkat
    Commented Mar 29, 2011 at 6:42
  • 1
    $\begingroup$ 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. $\endgroup$
    – Joe Fitzsimons
    Commented Mar 29, 2011 at 9:10
  • $\begingroup$ 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? $\endgroup$
    – Mitch
    Commented Mar 29, 2011 at 20:54
  • $\begingroup$ Sorry, Mitch; I forgot to explain what $n$ was! I've added that to the original post. - Jim $\endgroup$
    – Jim Propp
    Commented Mar 30, 2011 at 4:32

4 Answers 4

Reset to default
1
$\begingroup$

See Random Generation of Finite Sturmian Words 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.

Improve this answer
$\endgroup$
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

  • 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$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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! $\endgroup$
    – Jim Propp
    Commented Mar 30, 2011 at 4:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.