An algebraic approach to Hough transforms (Q1952166)

The purpose of this paper is to lay the foundations for a theory which extends the classical Hough transform to algebraic objects such as affine schemes. This generalization has proved highly effective; the method of the authors has already been implemented to detect special curves in images of solar flares [\textit{M. C. Beltrametti} et al., SIAM J. Imaging Sci. 6, No. 1, 391--412 (2013; Zbl 1279.94007)]. The Hough transform was originally introduced by P.V.C. Hough in the form of a patent [\textit{P. V. C. Hough}, ``Method and means for recognizing complex patterns'', US Patent No. 3069654 (1962)] and was used in physics to identify lines and arcs in photographs obtained in particle detectors. To achieve this identification one starts with a parameterized family of lines and a discretization of the parameter space into cells. One then associates to every point in the source space its \textit{Hough transform}, which is the set of all parameters in the parameter space corresponding to lines in the source space containing that point. If many points in the source space are contained in the same line, then the Hough transforms of these points will all contain the corresponding cell in the parameter space. This parameter can be identified as a maximal value in an \textit{accumulator matrix} whose entries count the number of lines passing through each cell in the parameter space. Details can be found in [\textit{O. Duda} and \textit{P. E. Hart}, Commun. ACM 15, No. 1, 11--15 (1972; Zbl 1296.94027)]. To extend this notion to more general algebraic objects, the authors assume in Section 2 that the parametrization has the form of a free family of affine schemes over an affine space, a property which can be detected via a Gröbner basis computation with respect to a degree-compatible term ordering \(\sigma\) (Proposition 2.3). The fibers of this family are assumed to be irreducible for purposes of identifiability. In Section 3 the \textit{Hough transform} of a point is defined and the notion of \textit{Hough \(\sigma\)-regularity}, where \(\sigma\) is the term order, is introduced. The Hough transform of a point is the subscheme of the parameter space consisting of all parameters corresponding to affine schemes in the given family which pass through that point in the source space. In order for the Hough transform to be implemented as effectively, it is necessary that the intersection of Hough transforms of all points on a member of the family is a single parameter. If this is satisfied for `most' members of the given family of schemes, where `most' is determined by the term order \(\sigma\), then this family is said to be \textit{Hough \(\sigma\)-regular}. In Corollary 3.12, the authors prove that this is equivalent to equality of fibers implying equality of corresponding parameters. In applications this is typically referred to as the problem of identifiability [\textit{L. García-Puente, S. Spielvogel} and \textit{S. Sullivant} ``Identifying causal effects with computer algebra'', in: Proceedings of the 26th Conference of Uncertainty in Artificial Intelligence. Corvallis, Oregon: AUAI Press. 193--200 (2010); \textit{N. Meshkat} et al., Math. Biosci. 222, No. 2, 61--72 (2009; Zbl 1179.93066)]. Section 4 contains the heart of the paper, which is a method for detecting Hough \(\sigma\)-regularity. This is recorded in Theorem 4.6 and extended in Theorem 4.10 to detection of generic Hough regularity. The technique relies on showing the injectivity of a certain map obtained from the coefficients of the reduced Gröbner basis of the generic fiber. Theorem 4.3 contains criteria for injectivity of this map, which can be checked using a computer algebra system. The authors conclude in Section 5 with several examples of families where Hough regularity is ascertained using CoCoA-5 [\textit{CoCoATeam}, CoCoA: a system for doing computations in commutative algebra, available at \url{http://cocoa.dima.unige.it}].