| Popis: |
We show that the newly developed homology al- gorithms are helpful in imaging problems on the example of an algorithm extracting one dimensional features from a noisy image. We indicate that in some situations the global nature of this algorithm may become advantageous when compared with the standard algorithms based on skeletonization and pruning. The algorithm works in every dimension. I. INTRODUCTION The topological technique commonly used in image seg- mentation is the extraction of connected components of a black and white image. In the language of homology theory (1) this may be viewed as constructing the zeroth homology group of the image. Higher homology groups, which measure the presence of cycles, tunnels, and cavities in the image, are also used in computer vision and image processing (2), (1), (3), (4), (5), (6) but so far their usage is limited in part because the cycles, tunnels and cavities are not so frequent in images and in part because the classical algorithm for higher homology groups has cubical complexity which is in contrast to the linear time needed to construct connected components (7). In this paper we show that higher homology groups are useful in image analysis even if the image itself and/or the features to be extracted contain no tunnels or holes. This is because holes may appear when the image is superimposed over some pattern (mask) and the appearance (or lack of appearance) of holes may be used to test certain features of the image via the study of homology generators. Moreover, image analysis based on higher homology groups may be performed quickly due to the recently developed reduction homology algorithms (8), (9), (10), which offer speed comparable to the speed of the algorithms constructing connected components. The first four authors supported by Polish MNSzW, Grant N201 037 31/3151. The implementations of these algorithms are available from (11) (see also (12), (13)). To present the method we discuss a sample problem, which consists in the extraction of linear structures from the image under the presence of other features and noise. We became interested in the problem when studying two concrete issues: the analysis of 2D colonoscope images of blood vessels in colon mucosa (14), (15) and the analysis of 3D reconstituted confocal microscopy images of type I collagen fibrils (16). Similar issues are studied in the analysis of blood vessel images in various other settings (17), (18), (19)), as well as in the detection of roads on satellite images ((20), (21)) and many other problems. |
