In the context of the NAVIDOMASS project, the problematic of this paper concerns the clustering of historical document images. We propose a structural-based framework to handle the ancient ornamental letters data-sets. The contribution, firstly, consists of examining the structural (i.e. graph) representation of the ornamental letters, secondly, the graph matching problem is applied to the resulted graph-based representations. In addition, a comparison between the structural (graphs) and statistical (generic Fourier descriptor) techniques is drawn.