Maximizing Inter-Marker Distance in Square Fiducial Marker Dictionary Generation

Square fiducial markers provide a robust and efficient way to establish visual references in camera localization tasks, combining reliable detection with unique identification through an embedded binary code. The robustness of these systems depends largely on the minimum distance between valid codes: larger distances enable the correction of more bit errors and reduce the risk of marker misidentification. This paper presents two approaches for generating square-marker dictionaries with large inter-marker distances. The first is an exact approach that formulates the dictionary-generation problem as a maximum-clique problem. It finds optimal solutions for a broader range of cases than the previous exact method, although its memory and computational requirements still restrict its practical applicability to small marker sizes (3×3 and 4×4 bits). The second is a packing-based suboptimal approach that constructs the dictionary incrementally and scales to larger code and dictionary sizes. Experimental results demonstrate that the proposed approach improves upon existing dictionary-generation methods, enabling the construction of larger dictionaries with enhanced error-detection and error-correction capabilities. The source code and generated dictionaries are publicly available.