Hierarchical Singular Value Decomposition for Halftone Images

This work is devoted to one new approach for decomposition of images represented by matrices of size 2 n 2 n , based on the multiple application of the Singular Value Decomposition (SVD) over image blocks of relatively small size (22), obtained after division of the original image matrix. The new decomposition, called Hierarchical SVD, has tree structure of the kind binary tree of n hierarchical levels. Its basic advantages over the famous SVD are: the reduced computational complexity, the opportunity for parallel and recursive processing of the image blocks, based on relatively simple algebraic relations, the high concentration of the image energy in the first decomposition components, and the ability to accelerate the calculations through cutting-off the tree branches in the decomposition levels, where the corresponding eigen values are very small. The HSVD algorithm is generalized for images of unspecified size. The new decomposition opens numerous opportunities for fast image processing in various application areas: image compression, filtration, segmentation, merging, digital watermarking, extraction of minimum number of features sufficient for the objects recognition, etc.