Smooth parametrization of a family of lines

mathematics

Mon, Dec 27, 21

The problem

Let $L=\{L_i\mid i\in ⟦1,N⟧\}$ be a set of $N$ lines $L_i$ in the plane ${\mathbb{R}}^2$, which seem to obey a certain rule as $i$ progresses. For instance, $L_{i+1}$, as compared to $L_i$ could be translated and rotated a bit, by some functions of $i$. These lines are known by the values $a_i$ and $b_i$ of their slope and y-intercept respectively, so they all have the following slope-intercept form:

Moreover, the slope is unconstrained, and can very well change sign from one line to the next. We would like to find a smooth parametrization $L(s)$, such that each line $L_i\in L$ is generated by a specific value $s_i$ of the parameter $s$:

Then $L(s)$ forms a continuous family of lines, and $L\subset L(s)$. Note that I will use the same symbol $L(s)$ to refer to either the continuous family of lines, or the line generated by a given value $s$ of the parameter. The context will be sufficient to distinguish between both uses.

Solution

Obviously, as both the slope $a(s)$ and the y-intercept $b(s)$ of the line $L(s)$ are discontinuous functions of $s$, a very high-order series expansion would be needed to approximate $a$ and $b$ as functions of $s$, if we were to use a slope-intercept form. But let’s not go there. The discontinuity, akin to coordinate singularities, originates from choosing this form in the first place, and can be removed by choosing a different one.

The Hesse normal form

When I began solving this problem, I remembered that the same singularity issue was circumvented by Duda and Hart in their implementation of the Hough transform, by the use of the Hessian normal form (see [1]). Any line $l$ admits two parameters $r$ and $\theta$ such that for every point $(x,y)\in l$ the following equation must hold:

This is called the Hesse normal form, and is an alternative to the slope-intercept form to represent a line. A bit of algebraic manipulation gives:

Then, by identification of the coefficients, we deduce the following formulas to transform a Hesse normal form to a slope-intercept form and back:

Fitting $L$

Using $\text{6}$ we can transform the pairs $(a_i,b_i)$ describing the lines $L_i$ into pairs $(r_i,{\theta }_i)$ parametrizing their respective Hesse normal forms:

Then, all is left to do is to fit the $r_i$ and ${\theta }_i$ using an $n$-th order polynomial regression for example:

The values of the ${\alpha }_j$ and ${\beta }_j$ are computed by the regression algorithm as functions of the $r_i$ and ${\theta }_i$ respectively. So we have the following continuous parametrization in Hesse normal form:

Then of course, we can go back to a slope-intercept form using $\text{5}$, giving:

And as long as $a(s)$ and $b(s)$ are defined, we have the following parametrization in slope-intercept form:

The advantage of going down this route is that, because $r(s)$ and $\theta (s)$ are continuous functions of $s$, there is a chance that only a low-order polynomial fit will be required to have good enough precision. So $a(s)$ and $b(s)$, as functions of these two, will be good estimators by design, at a low cost.

Implementation

Let’s do this in Python, with numpy and matplotlib:

import numpy as np
from matplotlib import pyplot as plt

Suppose we have a function get_data() that returns a $3$-tuple containing multiple values $s_i$ of the parameter $s$, followed by the slopes $a_i$ and the y-intercepts $b_i$ of the lines $L_i$ for each value of $s_i$. In the full code (link below), I implemented such a function featuring the same exact experimental data I was fiddling with when this parametrization problem first came up. I also added a bit of context for those of you who are interested! Now, let’s write two functions to convert coefficients from the slope-intercept form to coefficients of the Hesse normal form and vice versa:

def to_hesse_normal_form(a, b):
    r = - b / (a * np.sqrt(1 + 1 / np.power(a, 2)))
    theta = np.arctan(-1 / a)
    return r, theta

def to_slope_intercept_form(r, theta):
    a = - 1 / np.tan(theta)
    b = r / np.sin(theta)
    return a, b

These are direct implementations of $\text{6}$ and $\text{5}$. And now, we can import some lines using the get_data() function mentioned above, convert them to Hessian form, fit polynomials on $r_i$ and ${\theta }_i$, get our $a(s)$ and $b(s)$ and do some plotting:

def main():
    s, a, b = get_data()
    # Fit the Hesse normal form parameters using 2nd order polynomials
    r, theta = to_hesse_normal_form(a, b)
    r_coeffs = np.polyfit(s, r, 2)
    theta_coeffs = np.polyfit(s, theta, 2)
    r_fit = np.poly1d(r_coeffs)
    theta_fit = np.poly1d(theta_coeffs)

    # For multiple values of the parameter s, calculate slope and y-intercept
    sp = np.linspace(np.min(s), np.max(s), 100)
    a_fit, b_fit = to_slope_intercept_form(r_fit(sp), theta_fit(sp))

    # Plot stuff
    # ...

Finally we can plot our fits. The code for this task is a bit lengthy so it was omitted, but you can check the full source code if needed.

Notice how -given the data that I use- only second order polynomials suffice to capture the dependency in $s$ of both $r$ and $\theta$. There is no way a second order would be enough if we were to fit $a$ and $b$ directly! The discontinuity of $a$ and $b$ is quite visible, but was captured effortlessly by this method. Let’s also display a few lines of our smooth parametrized family $L(s)$, together with the original lines $L_i$:

That’s pretty convincing, if I may say so myself! So it appears you can use this method to interpolate between lines of a discrete set… My Google-fu is not so strong, but the only similar result I could find was this article on Cross-Linear Interpolation, so I guess that’s the name of the problem we solved here? It seems elementary enough that a myriad of applications could exist, but I’m quite the unimaginative type as far as applications go. Maybe you have some ideas to share?

Sources

• [1] Richard O. Duda and Peter E. Hart (April 1971). “Use of the Hough Transformation to Detect Lines and Curves in Pictures”. Artificial Intelligence Center.