This code is supplementary material for the article

PLMP -- Point-Line Minimal Problems for Projective SfM

that can be found on arXiv.

We use Julia for the computations. If you intend to read the source code, make sure that your editor is able to display UTF-8 characters as it will otherwise not be able to display all characters in the file.

The required packages for running this software with Julia are:

• AbstractAlgebra.jl,
• Oscar.jl,
• HomotopyContinuation.jl

All functions lie within minimal_plps.jl. In Julia, run

include("minimal_plps.jl")

to get all functionalities.

To compute all classes of balanced point-line problems, that is, all tuples $(m, p^f, p^d, l^f, l^a)$, run

calculate_balanced_classes()

The result is always computed during startup, and is stored in balanced_classes.

To compute all candidates of point-line minimal problems where $p^f + p^d < 7$, run

calculate_candidate_problems()

The result is always computed during startup, and is stored in candidate_problems.

All candidates of point-line minimal problems where $p^f + p^d = 7$ is stored in candidate_problems_7pts, and is enumerated by hand.

To check whether a problem pb is minimal, run

is_minimal(pb)

this runs a check of minimality by computing the rank of the Jacobian matrix over a finite field 1000 number of times; see Remark 4.6 in article. To explicitly set the number of evaluations to n used in is_minimal, run is_minimal(pb, numevals=n).

All minimal problems for $p^f + p^d < 7$ and $p^f + p^d = 7$ are stored in minimal_problems and minimal_problems_7pts, respectively. To check that these are correct, run

assert_minimal_problems_is_correct()

and

assert_minimal_problems_7pts_is_correct()

respectively. These also accept an optional argument numevals, just like is_minimal.

We also enumerate all candidates of minimal problems that turned out to be non-minimal, and list the criteria that makes them non-minimal. These are listed in the variable nonminimal_candidate_problems, and the criteria are listed in the comments in the code.

All point-line minimal problems along with their degrees as given by monodromy are given as tuples (pb, deg) in the variables pb_degs and pb_degs_7pts for $p^f + p^d < 7$ and $p^f + p^d = 7$, respectively. These are not calculated during startup, so to assure that these are correct according to monodromy, run

assert_degs_is_correct()

and

assert_degs_7pts_is_correct()

Recall that monodromy yields a lower bound for the degree. To verify that this lower bound is actually the degree, we calculate the degree using Gröbner basis to get an upper bound of the degree, and verify that this is the same as the lower bound.

To assert that the degrees for an array of problems pbs are correct, run

assert_degrees_are_correct_gb(pbs)

If no argument is given, pbs will default to all minimal point-line problems with three views.

For modern mid-end computers, this is expected to terminate within an hour or so for all problems with three to four views. The most computationally heavy problem in four views (the one in the class $(m, p^f, p^d, l^f, l^a) = (4, 1, 0, 3, 6)$ ) is factorized into subproblems as a special case in order to make it computationally feasible, and this code can be found in the function degree_m4_l9, which corresponds to Example D.1 in the article.

While it is expected to be able to verify some problems for higher views, the memory consumption and run time grows very fast, in particular for higher line counts.

To run Example 4.12 in the article, open Julia and run

include("example_4-12.jl")

As mentioned under the section about Gröbner basis computations, Example D.1 corresponds to the function degree_m4_l9. Hence, simply run

degree_m4_l9()

to get the degree of this problem.