Fig. 1 Left: Example of a target image and lines. Solid lines mean foreground. Dotted lines mean background. Right: Example of an output mask i

Size: px

Start display at page:

Download "Fig. 1 Left: Example of a target image and lines. Solid lines mean foreground. Dotted lines mean background. Right: Example of an output mask i"

かずきはかまや
5 years ago
Views:

1 Vol. 50 No (Dec. 2009) 1, 1 2, 2 1, Seeded Region Growing Seeded Region Growing Seeded Region Growing Seeded Region Growing Proposal and Evaluation of Fast Image Cutout Based on Improved Seeded Region Growing Tatsuya Kiyono, 1, 1 Takahiro Hayashi, 2, 2 Rikio Onai, 1, 2 Masahiro Sanjo 3 and Masaya Mori 3 In this paper, we propose and evaluate a method for Fast Image Cutout using improved Seeded Region Growing. The starting point for the method is Seeded Region Growing, which divides an image into foregrounds and backgrounds by growing the initial foregrounds and backgrounds represented by user drawing lines to the neighbor pixels. To improve the precision of Seeded Region Growing for images including enclaves, the method adopts a threshold condition. In addition, to improve the precision of Seeded Region Growing for images including texture patterns, the method estimates foreground colors and background colors from initial foregrounds and backgrounds and decides growing-priorities for each neighbor pixel depending on the esimimated colors. We propose a new data structure for the method, and could achieve speed up. The experimental results have shown the method has the same processing speed as traditional methods and has better precision than traditional methods, when we input small area of initial foregrounds and backgrounds such as user drawing lines. 1. 1) Intelligent Scissors 2) Image Snapping 3) Lazy Snapping 4) Random Walks 5) SIOX 6) 1 1 Graduate School of Electro-Communications, The University of Electro-Communications 2 Faculty of Electro-Communications, The University of Electro-Communications 3 Rakuten Institute of Technology, Rakuten Inc. 1 Presently with Google Japan Inc. 2 Presently with Faculty of Engineering, Niigata University 3233 c 2009 Information Processing Society of Japan

3234 1 Fig. 1 Left: Example of a target image and lines. Solid lines mean foreground. Dotted lines mean background.

Seeded Region Growing 7) Seeded Region Growing Seeded Region Growing 2 3 Seeded Region Growing 4 5 6 7 2.

White region means initial foreground. Black region means initial background. Grey region means unknown region.

2 Fig. 1 Left: Example of a target image and lines. Solid lines mean foreground. Dotted lines mean background. Right: Example of an output mask image. White region means foreground. Black region means background. Seeded Region Growing 7) Seeded Region Growing Seeded Region Growing 2 3 Seeded Region Growing GrabCut 8) Alpha Matting Trimap Trimap 2 2 Trimap Fig. 2 Left: Example of a target image. Right: Example of Trimap. White region means initial foreground. Black region means initial background. Grey region means unknown region Hard Segmentation Hard Segmentation 2 9) Alpha Matting Alpha Matting Bayesian Matting 10) Poisson Matting 11) Robust Matting 12) Spectral Matting 13) Alpha Matting Hard Segmentation Alpha Matting Hard Segmentation Trimap Trimap Alpha Matting 14) Hard Segmentation Alpha Matting Alpha Matting 3. Seeded Region Growing

3 F 0 V B 0 V F 0 B 0 = 2 F B N t Q 3 Fig. 3 Expression of an image by a graph Seeded Region Growing Seeded Region Growing 3 G =< V, E > V E v V e =(s, t) E(s, t V) 4 Seeded Region Growing F B t N F B F B t N F F = F {t} N = N {t} B B = B {t} N = N {t} t t C(t) C(t) F = F 0 B = B 0 N = V (F B) Q = {t N e(t) (F B) } e(t) t e(t) ={s (F B) (s, t) E} (1) 3 t m =argmin{c(t)} t Q 4 s e(t m) R(s) R(s) =F B t m R(s) =R(s) {t m} N = N {t m} 5 Q Q = Q {t m} Q = Q {t n(t m)} 6 n(t) t n(t) ={u N (u, t) E} (2) Q = C(t) C(t) =W 1(s, t) D(s, t)+w 2(s, t) C s (3) s s = e(t) D(s, t) s t RGB s t C s F B s 4 C s = C(t m) s F 0 s B 0 C s =0 C s

4 Fig. 4 Example of enclave. Seeded Region Growing 3.4 W 1(s, t) W 2(s, t) D(s, t) C s Seeded Region Growing Seeded Region Growing 4 D f D b D n D n D b D n D b D n D n D f C(t) T 4 R(s) =F B t C(t) T F 0 B 0 T = w max{d(f b,b d ),D(f d,b b )} (4) f b =argmax{y (c v)} (5) v F 0 f d =argmin{y (c v)} (6) v F 0 (a) (b) (c) 5 (a) (b) (a) (c) (a) Fig. 5 (a): Target image. (b): The enlarged image of the rectangle in (a), without cost accumulation. (c): The enlarged image of the rectangle in (a), with cost accumulation. b b =argmax{y (c v)} (7) v B 0 b d =argmin{y (c v)} (8) v B 0 Y (c v)=0.299r v g v b v (9) w w T w =1.5 w w = c v =(r v,g v,b v) r v g v b v v R G B Y (c v) v c v 15) s t D(s, t) T 5 (b) D(s, t) (3) C s 5(c) 3.5 Seeded Region Growing

5 3237 Lazy Snapping K-means SIOX Color Signature kd W 1(s, t) W 2(s, t) RGB c =(r, g, b) 256 s q(c) ( ) r g b q(c) =q(r, g, b) = 256 s, 256 s, 256 s (10) x x s =16 1 K F K B K F = q(c v) (11) v F 0 K B = q(c v) (12) v B 0 W 1(s, t) W 2(s, t) s t c t K F K B 1 q(x) q s q t q(x) =q t/q s x q(x) =(q t 1)/(q s 1) x q t/q s ( ) R(s) =F,q(c t) K F K B 1 R(s) =B,q(c t) K B K F ( ) W 1(s, t) = R(s) =F,q(c t) K B K F 4 R(s) =B,q(c t) K F K B 2 (otherwise) ( ) R(s) =F,q(c t) K F 0 W 2(s, t) = R(s) =B,q(c t) K B 1 (otherwise) W 1(s, t) D(s, t) t c t R(s) K F K B t R(s) 1 t c t R(s) (R(s) =F B R(s) =B F) t R(s) 4 t c t K F K B t 2 W 2(s, t) C s t c t R(s) 0 c K F K B F i,j,k B i,j,k { 1(q(i, j, k) K F ) F i,j,k = (15) 0(otherwise) { 1(q(i, j, k) K B ) B i,j,k = (16) 0(otherwise) O(1) (13) (14)

6 Seeded Region Growing 4.1 Priority Queue Q min{c(t)} t Priority Queue t Q Priority Queue t Priority Queue C(t) Priority Queue PQ t PQ.push(t) PQ.top() PQ.pop() Priority Queue Binary Heap PQ.push(t) O(log( PQ )) PQ.top() O(1) PQ.pop() O(log( PQ )) PQ PQ PQ.push(t) PQ.pop(t) O(log N) N PQ.push(t) PQ.pop(t) n N O(N log N) 4.2 Priority Queue Queue PQ.push(t) PQ.pop(t) n N Priority Queue Priority Queue Queue Priority Queue Queue FIFO Queue DQ t DQ.push(t) DQ.top() DQ.pop() DQ.push(t) DQ.top() DQ.pop() O(1) Priority Queue Queue HQ PQ DQ HQ.push(t) HQ.top() HQ.pop() { DQ.push(t)(PQ,C(t) C(PQ.top())) HQ.push(t) = PQ.push(t)(otherwise) HQ.top() = HQ.pop() = { { DQ.top()(DQ ) PQ.top()(otherwise) DQ.pop()(DQ ) PQ.pop()(otherwise) Q PQ HQ.top() HQ.pop() Queue Queue C(t) C(PQ.top()) PQ.top() Queue Priority Queue push pop HQ.top() Priority Queue Queue Priority Queue (3) C s PQ HQ.push(t) PQ.push(t) t C(t) >C(PQ.top()) PQ.top() PQ.top() PQ Radix Heap 16) Radix Heap PQ.push(t) PQ.top() PQ.pop() O(1) Priority Queue Queue Priority Queue Radix Heap O(N) 5. Vision at MSR Cambridge: Ground truth database 1 50 Seeded Region Growing Lazy Snapping SIOX Random Walks 1 segmentation/grabcut.htm

3239 (a) (b) (c) (d) 6 (a) (b) (c) 1 (d) 2 Fig. 6 (a): Target image. (b): Correct image. White region mean foreground.

1 2 Trimap 2 Trimap( 1 2) 6 1 Benchmarking SIOX 1 Trimap 2 1 Trimap F r F c F r F c p r F f N c F r F c N c p r F f p = r = Fr Fc F r Fr

html (17) (18) (19) F F Priority Queue Queue Priority Queue (Hybrid Queue) Priority Queue (Priority Queue) (Hybrid Queue) (Priority

7 3239 (a) (b) (c) (d) 6 (a) (b) (c) 1 (d) 2 Fig. 6 (a): Target image. (b): Correct image. White region mean foreground. Black region means background. Grey region means mixed region. (c): Input method 1. (d): Input method Trimap 2 Trimap( 1 2) 6 1 Benchmarking SIOX 1 Trimap 2 1 Trimap F r F c F r F c p r F f N c F r F c N c p r F f p = r = Fr Fc F r Fr Fc F c f = 2 1 p + 1 r = 2 Fr Fc F r + F c 1 (17) (18) (19) F F Priority Queue Queue Priority Queue (Hybrid Queue) Priority Queue (Priority Queue) (Hybrid Queue) (Priority Queue) (Hybrid Queue) ( ) ( ) Seeded Region Growing Lazy Snapping SIOX Random Walks Lazy Snapping Random Walks λ β 2 F Lazy Snapping λ Random Walks β (Hybrid Queue) T w w w 2 Lazy Snapping λ F 7 7 λ F λ 12000

8 Lazy Snapping λ Fig. 7 Accuracy of Lazy Snapping by changing parameter: λ. 9 (Hybrid Queue) w Fig. 9 Accuracy of our method (Hybrid Queue) by changing parameter: w. 8 Random Walks β Fig. 8 Accuracy of Random Walks by changing parameter: β. Lazy Snapping λ Random Walks β F 8 8 β 105 F β 105 Random Walks β 105 (Hybrid Queue) w F 9 9 w 1.5 F 1.5 w (e) (j) w C(t) T T w (4) w w 13 (e) (j) (Hybrid Queue) F w (Hybrid Queue) w = (h) w 5.3 F

9 Table 1 Accuracy comparison of Input method 1. F (Hybrid Queue) (Priority Queue) ( ) ( ) Seeded Region Growing Lazy Snapping SIOX Random Walks Table 2 Accuracy comparison of Input method 2. F (Hybrid Queue) (Priority Queue) ( ) ( ) Seeded Region Growing Lazy Snapping SIOX Random Walks (a) (b) (c) (d) (e) (f) p r (a) (b) 11 (a) (b) (Hybrid Queue) (Priority Queue) (g) (h) 10 1 (a) (Hybrid Queue) (b) (Priority Queue) (c) ( ) (d) ( ) (e) Seeded Region Growing. (f) Lazy Snapping (g) SIOX (h) Random Walks Fig. 10 Result of Input method 1. (a): our method (Hybrid Queue). (b): our method (Priority Queue). (c): our method (without dealing with enclave). (d): our method (without dealing with texture). (e): Seeded Region Growing. (f): Lazy Snapping. (g): SIOX. (h): Random Walks.

10 3242 (a) (b) (c) (d) (e) (f) (g) (h) 11 2 (a) (Hybrid Queue) (b) (Priority Queue) (c) ( ) (d) ( ) (e) Seeded Region Growing. (f) Lazy Snapping (g) SIOX (h) Random Walks Fig. 11 Result of Input method 2. (a): our method (Hybrid Queue). (b): our method (Priority Queue). (c): our method (without dealing with enclave). (d): our method (without dealing with texture). (e): Seeded Region Growing. (f): Lazy Snapping. (g): SIOX. (h): Random Walks. (Hybrid Queue) (Priority Queue) C s Priority Queue Queue Priority Queue C s (14) W 2(s, t) t R(s) F 10 (e) (h) 11 (e) (h) 11 (e) (h) 1 2 Trimap (Hybrid Queue) (Priority Queue) F 10 (a) (b) 11 (a) (b) C(t) (13) W 1(s, t) 2 ( ) (Hybrid Queue) 11 (c) ( ) 11 (a) (Hybrid Queue)

3243 (a) (b) (c) (d) (a) (b) (c) (d) (e) (f) (g) (h) (i) (j) (e) (f) (g) (h) 12 (a) (b) (c) 1 (d) 1 (Hybrid Queue)

(c): Input method 1. (d): Result of Input method 1. (e): Input method 2. (f): Result of Input method 2.

13 (Hybrid Queue) (a) (b) (c) Trimap (d) ( ) (e) (Hybrid Queue) w =0 (f) (Hybrid Queue) w =0.

13 Exapmle of dealing with enclave. (a): Target image. (b): Corecct image. (c): Trimap.

(f): our method(hybrid Queue) w =0.5. (g): our method (Hybrid Queue) w =1.0. (h): our method (Hybrid Queue) w =1.5. (i): our method (Hybrid Queue) w =2.

11 3243 (a) (b) (c) (d) (a) (b) (c) (d) (e) (f) (g) (h) (i) (j) (e) (f) (g) (h) 12 (a) (b) (c) 1 (d) 1 (Hybrid Queue) (e) 2 (f) 2 (Hybrid Queue) (g) Lazy Snapping (h) Siox Fig. 12 (a): Target image. (b): Correct image. (c): Input method 1. (d): Result of Input method 1. (e): Input method 2. (f): Result of Input method 2. (g): Result by Lazy Snapping. (h): Result by Siox. 13 (Hybrid Queue) (a) (b) (c) Trimap (d) ( ) (e) (Hybrid Queue) w =0 (f) (Hybrid Queue) w =0.5 (g) (Hybrid Queue) w =1.0 (h) (Hybrid Queue) w =1.5 (i) (Hybrid Queue) w =2.0 (j) (Hybrid Queue) w =3.0 Fig. 13 Exapmle of dealing with enclave. (a): Target image. (b): Corecct image. (c): Trimap. (d): our method (without dealing with enclave). (e): our method (Hybrid Queue) w =0. (f): our method(hybrid Queue) w =0.5. (g): our method (Hybrid Queue) w =1.0. (h): our method (Hybrid Queue) w =1.5. (i): our method (Hybrid Queue) w =2.0. (j): our method (Hybrid Queue) w = (d) 13 (a) 13 (c) ( ) 13 (d) (Hybrid Queue) w = (h) (Hybrid Queue) ( ) 1 ( ) (Hybrid Queue) 10 (c) 11 (c) 50 1 Trimap 1 2 ( ) F (Hybrid Queue) F 10 (d) 11 (d) ( ) 10 (a) 11 (a) (Hybrid Queue) (d) 14 (a) 14 (c) (

) 14 (d) (d) (e) (Hybrid Queue) 14 (e) 1 2 Seeded Region Growing 10 (a) (b) (e) 11 (a) (b) (e) Seeded Region Growing 15 15 (d) 15 (a) 15 (c) Seeded Region Growing 15 (a) Seeded Region Growing 15

12 3244 (a) (b) (c) (a) (b) (c) (d) (e) 14 Fig. 14 (Hybrid Queue) (a) (b) (c) Trimap (d) ( ) (e) (Hybrid Queue) Exapmle of dealing with texture. (a): Target image. (b): Correct image. (c): Trimap. (d): our method (without dealing with texture). (e): our method (Hybrid Queue). ) 14 (d) (d) (e) (Hybrid Queue) 14 (e) 1 2 Seeded Region Growing 10 (a) (b) (e) 11 (a) (b) (e) Seeded Region Growing (d) 15 (a) 15 (c) Seeded Region Growing 15 (a) Seeded Region Growing 15 Seeded Region Growing (a) (b) (c) Trimap (d) Seeded Region Growing (e) (Hybrid Queue) Fig. 15 Example of failed Seeded Region Growing. (a): Target image. (b): Correct image. (c): Trimap. (d): Seeded Region Growing. (e): our method (Hybrid Queue). Seeded Region Growing Seeded Region Growing C (t) C (t) =D(mean(R(s)),t) (20) mean(r(s)) R(s) ( 15 (e)) 1 2 Lazy Snapping (f) Lazy Snapping

3245 10 (f) 12 (g) 12 (g) 12 (a) 12 (e) Lazy Snapping 12 (g) Lazy Snapping 12 (f) 1 2 SIOX 1 2 11 (g) SIOX 0 12 (h) 12 (h) 12 (a) 12 (e) SIOX 12 (h) SIOX SIOX SIOX Color Signature SIOX 12 (f) 2 2

13 (f) 12 (g) 12 (g) 12 (a) 12 (e) Lazy Snapping 12 (g) Lazy Snapping 12 (f) 1 2 SIOX (g) SIOX 0 12 (h) 12 (h) 12 (a) 12 (e) SIOX 12 (h) SIOX SIOX SIOX Color Signature SIOX 12 (f) 2 2 Random Walks F (Hybrid Queue) F 11 (h) Random Walks 10 (h) (d) 16 (a) 16 (c) Random Walks 16 (d) Random Walks Random Walks Random Walks 3 (a) (b) (c) (d) (e) 16 Random Walks (a) (b) (c) Trimap (d) Random Walks (e) (Hybrid Queue) Fig. 16 Example of failed Random Walks. (a): Target image. (b): Correct image. (c): Trimap. (d): Random Walks. (e): our method (Hybrid Queue). 16 (e) 2 6. Seeded Region Growing Lazy Snapping SIOX Random Walks N

3246 (a) (b) (c) 17 (a) 1 (b) 2 (c) 3 Fig. 17 (a): Target image 1. (b): Target image 2.

512 512 256 256 128 128 Cubic 17) 2 1 Trimap 10 1 10 (Hybrid Queue) Radix Heap Dell XPS 730x CPU:

NET 2003 Random Walks MATLAB 1 MATLAB 7.6.0 6.

14 3246 (a) (b) (c) 17 (a) 1 (b) 2 (c) 3 Fig. 17 (a): Target image 1. (b): Target image 2. (c): Target image Cubic 17) 2 1 Trimap (Hybrid Queue) Radix Heap Dell XPS 730x CPU: Core i GHz Seeded Region Growing Lazy Snapping SIOX Microsoft Visual C++.NET 2003 Random Walks MATLAB 1 MATLAB (Hybrid Queue) ( ) ( ) (Hybrid Queue) Seeded Region Growing Lazy Snapping SIOX 1 lgrady/ 18 1 Fig. 18 Performance comparison using Target Image 1. O(1) (Hybrid Queue) (Priority Queue) 1.5

15 Fig. 19 Performance comparison using Target Image Fig. 20 Performance comparison using Target Image 3. (Priority Queue) Priority Queue (Hybrid Queue) Queue (Hybrid Queue) (Priority Queue) (Hybrid Queue) (Priority Queue) Radix Heap Queue 7. Seeded Region Growing Seeded Region Growing Lazy Snapping SIOX Random Walks

16 3248 Seeded Region Growing Priority Queue Queue N O(N) Seeded Region Growing Lazy Snapping SIOX Random Walks Seeded Region Growing 1) Wang, J. and Cohen, M.F.: Image and Video Matting, Now Publishers Inc., Hanover, MA, USA (2008). 2) Mortensen, E.N. and Barrett, W.A.: Interactive Segmentation with Intelligent Scissors, Graphical Models and Image Processing, Vol.60, No.5, pp (1998). 3) Gleicher, M.: Image snapping, SIGGRAPH 95: Proc. 22nd Annual Conference on Computer Graphics and Interactive Techniques, New York, NY, USA, ACM, pp (1995). 4) Li, Y., Sun, J., Tang, C.-K. and Shum, H.-Y.: Lazy snapping, ACM Trans. Graph., Vol.23, No.3, pp (2004). 5) Grady, L.: Random Walks for Image Segmentation, IEEE Trans. Pattern Analysis and Machine Intelligence, Vol.28, No.11, pp (2006). 6) Friedland, G., Jantz, K. and Rojas, R.: SIOX: Simple Interactive Object Extraction in Still Images, ISM 05: Proc. 7th IEEE International Symposium on Multimedia, Washington, DC, USA, IEEE Computer Society, pp (2005). 7) Adams, R. and Bischof, L.: Seeded Region Growing, IEEE Trans. Pattern Analysis and Machine Intelligence, Vol.16, No.6, pp (1994). 8) Rother, C., Kolmogorov, V. and Blake, A.: GrabCut : interactive foreground extraction using iterated graph cuts, ACM Trans. Graph., Vol.23, No.3, pp (2004). 9) Ruzon, M.A. and Tomasi, C.: Alpha Estimation in Natural Images, IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Vol.1, p.1018 (2000). 10) Chuang, Y.-Y., Curless, B., Salesin, D.H. and Szeliski, R.: A Bayesian Approach to Digital Matting, Proc. IEEE CVPR 2001, Vol.2, IEEE Computer Society, pp (2001). 11) Sun, J., Jia, J., Tang, C.-K. and Shum, H.-Y.: Poisson matting, ACM Trans. Graph., Vol.23, No.3 (2004). 12) Wang, J. and Cohen, M.F.: Optimized Color Sampling for Robust Matting, IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Vol.0, pp.1 8 (2007). 13) Levin, A., Rav-Acha, A. and Lischinski, D.: Spectral Matting, IEEE Trans. Pattern Analysis and Machine Intelligence, Vol.30, No.10, pp (2008). 14) Sindeyev, M. and Konushin, V.: A Novel Interactive Image Matting Framework, Proc. Graphicon 2008, pp (2008). 15) International Telecommunications Union: Recommendation ITU-R BT.601, Encoding Parameters of Digital Television for Studios, Geneva (1992). 16) Ahuja, R.K., Mehlhorn, K., Orlin, J. and Tarjan, R.E.: Faster algorithms for the shortest path problem, J. ACM, Vol.37, No.2, pp (1990). 17) Keys, R.: Cubic convolution interpolation for digital image processing, IEEE Trans. Acoustics, Speech and Signal Processing, Vol.29, No.6, pp (1981). ( ) ( )

17 IEEE NTT ICOT RWC 2000 ACM DBS IPA Ruby WG WG Ruby BP

IPSJ SIG Technical Report 1,a) 1,b) 1,c) 1,d) 2,e) 2,f) 2,g) 1. [1] [2] 2 [3] Osaka Prefecture University 1 1, Gakuencho, Naka, Sakai,

IPSJ SIG Technical Report 1,a) 1,b) 1,c) 1,d) 2,e) 2,f) 2,g) 1. [1] [2] 2 [3] Osaka Prefecture University 1 1, Gakuencho, Naka, Sakai, 1,a) 1,b) 1,c) 1,d) 2,e) 2,f) 2,g) 1. [1] [2] 2 [3] 1 599 8531 1 1 Osaka Prefecture University 1 1, Gakuencho, Naka, Sakai, Osaka 599 8531, Japan 2 565 0871 Osaka University 1 1, Yamadaoka, Suita, Osaka