Документ взят из кэша поисковой машины. Адрес оригинального документа : http://imaging.cs.msu.ru/pub/2013.PRIA.Levashov_Yurin.RidgeAndTree.en.pdf Дата изменения: Mon Nov 18 12:04:22 2013 Дата индексирования: Thu Feb 27 20:27:34 2014 Кодировка:

RIDGE AND TREE FEATURE DETECTION ON IMAGES
A. Levashov 2, D. Yurin3
2, 3

1

Laboratory of Mathematical Methods of Image Processing Faculty of Computational Mathematics and Cybernetics Lomonosov Moscow State University Leninskie Gory, Moscow 119991, Russia 2 alexeylevashov89@gmail.com , 3yurin@cs.msu.ru

In this article a new ridge detector with improved non-maxima suppression procedure in scale-space is proposed. Using the results of scale space ridge detection as primary markup the lines are prolonged up to branch points and restored in places where they are not detected. In our method the adaptive choice of threshold and flood fill are used. The algorithm is tested on synthetic, landscape and medical images. Introduction There are several major algorithms for ridge detection. Apparently the first of them was the approach [2] that does not use scale-space analysis and therefore its disadvantage is that it detects only thin lines. The approach [5] is based on the scale-space analysis, but it represents the theoretical basis for it and not practically effective algorithm. For the last 15 years there have been only a few cases where it was used in scientific researches. The detector [3] based on generalization of NMS for the case of 3d scale space (x, y, t) can been seen as more effective for ridge detection. However one of this approach`s disadvantages is that it does not detect the branch points on the lines and in the adjacent areas. It interrupts the lines connection and significantly complicates the tree structure analysis on images. The examples of such tasks are masking of tree branches and wires on the non-professional photos for retouching, road and river net finding on aerospace images for the cartographic information updating, selection of blood veins on medical images and processing of 3D images of computer tomography for medical diagnostic. The branch points are essential for such tasks, but often the lines are not detected in the adjacent areas for several reasons. First, there is an ambiguity in choosing the direction for NMS procedure, because the eigenvalues are almost equal. Second, in the adjacent areas two or more ridges lie closely and, as a result, Laplace operator can give a maximal response on
1

bigger scale (two times or more which leads to lines breakdown). Third, the filter response can diminish due to inconsistency between actual image structure and ridge mathematical model, which implies: the solid color line in the range of central lobe of the second derivative of Gaussian function and background with another color on the sidelobes. This article is devoted to suppression of disadvantages described above. The ridge detection In this section we shortly recall the algorithm [3], let I x, y is the intensity of input grayscale image. Scale space [6] is defined as convolution of the image I x, y with Gaussian kernel: L x, y, t G x, y, t I ( x, y ),
x y (1) 1 2t G x, y , t e , t 2, 2t We denote smoothed image L x, y, t derivatives with subscripts as Lx , L y , Lxx , Lxy , L yy ,... . Such derivatives are equivalent to original image I x, y convolution with appropriate derivatives of Gauss function G x, y, t . By direct differentiation it is easy to check [6] that scale-space representation of image L x, y, t is satisfied to diffusion equation: 1 Lt Lxx Lyy , (2) 2 where derivatives are computed at scale t .
2 2





The research was supported by the RFBR grant 13-07-00584.


Consider the algorithm [3] for ridge detection with branch points missing. Let the thickness of lines is fixed and equal 2 , then filter for ridge lines finding can be the Laplace operator or maximal eigenvalue of Hessian H 22 in point x, y

scales. Processing such layers triplets sequentially under i increasing, the local maximum points are collected.
False detection suppression

eigenvectors: v1 , v 2 , where v

L Lxy , H 22 xx (3) L L yy xy where the derivatives are computed on scale t 2 . In each point x, y we have a pair of
1

corresponds
2

to eigenvalue 1 such that 1

and v 1 is

normal to ridge. On this basis we obtain the algorithm of ridge lines detection as local maxima finding task (we find directional local maxima and minima of values 1 in direction v 1 ), i.e. we use the Non Maxima Supression (NMS) procedure with 3x3 window from Canny edge detector. If the detection scale t does not equal to thickness of line, the response of Laplacian (which is equal to L L xx L yy 1 2 ) or eigen value 1 is less than that of for scale is equal to thickness. Then if we analyze the response on neighborhoods scales we can choose the optimal scale. In scale-space the 3D Hessian is: Lxx Lxy Lxt H 33 Lxy L yy L yt , where using (2) L xt L yt Ltt (4) 1 1 L xt L xxx L xyy , L yt Lxxy L yyy , 2 2 1 Ltt L xxxx 2 Lxxyy L yyyy . 4

The method [3] outlined above detects also such features as blobs and some edges. In our approach the final results are presented in vector form instead of bitmap. After detection of ridges their spine pixel chains are collected in lists and the lists are united in a graph. For excluding blobs, the lists with small count of pixels are discarded. It is important that the minimal count of pixels in list is proportional to the ridge (or thick line) width. That is we impose a constraint for minimum elongation of the blobs, which are considered as ridges. This approach is differ from [3] where separation of ridges and blobs is based on ratio of eigen values of (3). For suppression of edges in [3] in NMS procedure the points are discarded if next dot product is negative: gx v1 , gx v1 0 . (5) Our experiments show that condition (5) can lead to erroneous discarding true ridge centers for example in cases when different side's backgrounds relatively to ridge have a different average intensity. We propose the modification of this condition: gx i v1 , gx i v1 Tg (6) where i corresponds to current scale, the threshold constant satisfied the inequality: 1 Tg 0 , (7)
g ( Lx , L y )T is the image intensity gradient.













In [3] the NMS procedure was modified as follows: the suppression is performed simultaneously in 2 directions of 3D scale space (x,y,t) using 3x3x3 window. The directions are selected as projections of 2 eigenvectors corresponding to 2 maximal eigenvalues of (4) on the plane normal to eigenvector v 2 of 2D Hessian (3). The discrete step on scales 0 ,..., i ,..., n in [3] are chosen as in [7]:

Adaptive flood-fill

After the previous step we obtains the set of detected ridges represented as set of points S x j , j , l j , where x j ­ the coordinates of center points of ridge lines, j ­ the scale, at which we detect ridge point with coordinates x j , l j ­ the response value in this point (the response of Laplacian convolution computed on scale j ). Using this data, we build 3 images M , I
min

i 4 2 . For 3D NMS procedure implementation it is sufficient to hold in memory only 3 layers corresponding to 3 sequential
i 1

0 1,

,I

max

. We set M x 1 if pixel


belongs to ridges, and M x 0 elsewhere. I min , I max ­ additional images showing the available ridges points intensity range. Let initially in all points M x 0 . Then for each points x j S we set
M x j 1,

described, for example, in [1], and can easy be modified for our problem by including additional conditions for pixel filling (9), (10).
Ridge skeletization



I I

max min

x I x x I x
j j j j

0.5 l j , 0.5 l j .

(8)

As shown in [3], the Laplacian value on scale corresponding to ridge thickness is equal to difference of average intensities of background and of ridge. Then we make flood fill of image M . The proposed algorithm is similar to [1], but we use additional conditions for pixel filling. Consider two neighborhood pixels y k and y j M y
k



1, M y I
min k

y I y
j

j



0 . If the condition I
max

y
k
min max

,

(9)

is satisfied, we modify the pixel y j as:
My


j

1,

I I

min max

y y
j j

I I

y , y .
k k

(10)

Now we can describe the algorithm of adaptive flood fill: AdaptiveFloodFill( x , d ) 1. if M x 1 return 2. if NOT I min x I x d I max x return 3. M x d 1
I max d I 4. AdaptiveFloodFill ( x d , 5. AdaptiveFloodFill ( x d , 6. AdaptiveFloodFill ( x d , 7. AdaptiveFloodFill ( x d , I
min

The binary image M after the previous step will segment the image into the pixels belonging to the ridges and the background pixels. When at branch points the ridges change their color slightly in comparison with the background, the junction points will be added to the ridges, even if they were not found by the scale-space detector. Further the continuous skeletization of binary image can be applied and the skeleton can be used as the result. We use the algorithm [9], because in our approach it is desirable to retain the ridge points found by scale-space detector and only add junction and junction neighborhood ridge points as a result of thinning. The algorithm of skeletization via line thinning is based on step-by-step removing of the points which are not the centers in lines under additional condition that it is not ridge point obtained with scale-space detector. Each algorithm iteration includes two passes through all the pixels. On each pass the non-skeleton points are marked but removed only after the end of the pass. Around each point x of the image M the window 3x3 is selected. We can enumerate pixels P1 , P2 ,..., P9 is the window in order shown on the Fig.1. Descriptors B ( x)

x x

d I

min

x max x


i2

9

Pi

and A(x) which is

0 1T ) 1 0T ) 0 1T 1 0T

equal to the number of patterns 01 in the sequence P2 ,..., P9 , P2 are calculated.

) ) Figure 1: pixel`s order in 3x3 window On the first pass the pixel x is marked to be removed from image M if all four next conditions are satisfied: a) 2 B(x) 6 c) M P2 M P4 M P6 1 b) A(x) 1

In the beginning of the algorithm for each points x i : M ( x i ) 0 and for each neighborhoods x i d we invoke the algorithm AdaptiveFloodFill( x i , d ), which differs from [1] by 2 and 3 lines. For near border pixels we additionally check when coordinates x d are outside of image rectangle. This is the scheme of simple and not optimal realization of the flood filling algorithm. The faster algorithm is

d) M P4 M P6 M P8 1


On the second pass clauses c) and d) are changed to the following: c') M P2 M P4 M P8 1 d') M P2 M P6 M P8 1

[5]

The iterations are being done until no pixels are removed during two passes. As we don't remove pixels detected by the scale-space algorithm, all the lines found initially retains and only the junction points between them are appended.
Results and conclusion

[6]

[7]

The ridge detection algorithm without brakes near branch points is proposed. We make some improvements in algorithm [3] and restore breaks in ridges near branch points with adaptive flood fill algorithm. We test our approach on synthetic and medical images. Some results for medical retina images are shown on Fig. 2. The ridges in the Fig. 2b have brakes near branch points while in the Fig. 2c most of these brakes are restored and shown in red. One of the disadvantages of the proposed algorithm is that our method does not detect the accurate ridge edges. But after we restore the ridges interconnections, the problem simplifies to finding edges between object (ridges united in tree) and the background. The task becomes bipolar labeling problem and can be solved via graph minimal cut between source (the set of connected ridge central points) and sink (background, or the points lying far from ridges longer than the ridge width).
References

[8]

[9]

nected Component Labeling of Streamed Images" // Field-Programmable Technology, Int. Conf, -P. 159-165, 2012 T. Lindeberg, "Edge detection and ridge detection with automatic scale selection" // International Journal of Computer Vision, V. 30, -No. 2, -P. 117­154, 1998 T. Lindeberg "Scale-Space Theory in Computer Vision" // Kluwer Academic Publishers/Springer, Dordrecht, Netherlands, 1994. D.G. Lowe. "Distinctive image features from scale-invariant keypoints" // Int. Journal of Computer Vision, -V. 60, -No. 2, -P. 91-110, 2004 M.B. Dillencourt, H. Samet, M. Tamminen (1992). "A general approach to connectedcomponent labeling for arbitrary image representations" // Journal of the ACM, -V. 39, -N. 2, -P. 253-280, 1992 T.Y. Zhang, C.Y. Suen "A fast parallel algorithm for thinning digital patterns" // Communications of the ACM, -V. 27, -No. 3, -P. 236-239, 1984.

a)

b)

[1] S.V. Burtsev, Y.P. Kuzmin. "An efficient flood-filling algorithm" // Computers & graphics, Elsevier, -V. 17, -No 5, -P. 549­ 561, 1993 [2] R. Haralick, "Ridges and Valleys on Digital Images" // Computer Vision, Graphics, and Image Proc., -V. 22, -No. 10, 1983 [3] N. A. Khanina, E. V. Semeikina, D. V. Yurin. "Scale-space color blob and ridge detection" // Pattern Recognition and Image Analysis, -No. 1, -P. 221-227, 2012 [4] M. Klaiber, L. Rockstroh, Z. Wang, Y. Baroud, S. Simon. "A Memory-Efficient Parallel Single Pass Architecture for Con-

c) Figure 2: a) Input image, b) scale-space ridge detection, c) the result of line connection