Complexity-Preserving Transposition of Summing Algorithms: A Data Flow Graph Approach

This paper introduces a novel method for transposing summing algorithms, which eliminates the need for an explicit matrix representation of a direct summing operator. Unlike the approach previously proposed in the literature, which relies on decomposing the direct operator matrix into simpler factors, our method leverages a graph-based interpretation using directed acyclic graphs (DAGs). By focusing on the analysis of structure of the DAG associated with the summing algorithm, we avoid the complex and often cumbersome task of operator matrix factorization. The proposed method maintains the asymptotic computational efficiency of the original algorithm while offering a more accessible and flexible framework for transposition. In this paper, capabilities of graph interpretation are demonstrated by analyzing fast algorithms for computing forward and backward projection operators for a 2D low-angle reconstruction problem for circular-orbit parallel-beam CT. As a key component, these algorithms incorporate the transposition of classical fast Hough transform (HT) operators, including that realized by the Brady–Yong algorithm. Moreover, we apply the proposed transposition method to the novel $\mathit{FHT}2\mathit{DT}$ algorithm for fast and substantially accurate computation of the HT. The transposed $\mathit{revFHT}2\mathit{DT}$ algorithm offers a computationally efficient approach for calculating the transposed HT for images of arbitrary size. This overcomes the limitations of the transposed Brady–Yong algorithm, which is restricted to images with power-of-two widths.