Combinatorial structure of rigid transformations in 2D digital images

Rigid transformations are involved in a wide range of digital image processing applications. When applied on discrete images, rigid transformations are usually performed in their associated continuous space, requiring a subsequent digitization of the result. In this article, we propose to study rigid transformations of digital images as fully discrete processes. In particular, we investigate a combinatorial structure modelling the whole space of digital rigid transformations on arbitrary subset of Z2Z2 of size N × N  . We describe this combinatorial structure, which presents a space complexity O(N9)O(N9) and we propose an algorithm enabling to construct it in linear time with respect to its space complexity. This algorithm, which handles real (i.e., non-rational) values related to the continuous transformations associated to the discrete ones, is however defined in a fully discrete form, leading to exact computation.

► We propose to study rigid transformations of digital images in a fully discrete process.
► We model the parameter space of digital rigid transformations on any subset of Z2 of size N × N by a combinatorial structure.
► We describe this structure which has a space complexity O(N9).
► We propose an (exact computation) algorithm to build this structure in linear time with respect to its size.