SCIENTIA SINICA Informationis, Volume 49 , Issue 2 : 188-203(2019) https://doi.org/10.1360/N112018-00205

Co-optimization of ethnic-pattern segmentation based on hierarchical patch matching

More info
  • ReceivedAug 2, 2018
  • AcceptedOct 29, 2018
  • PublishedFeb 20, 2019


Funded by






[1] Kanungo T, Mount D M, Netanyahu N S. An efficient k-means clustering algorithm: analysis and implementation. IEEE Trans Pattern Anal Machine Intell, 2002, 24: 881-892 CrossRef Google Scholar

[2] Comaniciu D, Meer P. Mean shift: a robust approach toward feature space analysis. IEEE Trans Pattern Anal Machine Intell, 2002, 24: 603-619 CrossRef Google Scholar

[3] Cheng X, Zeng M, Liu X. Feature-preserving filtering with L0 gradient minimization. Comput Graphics, 2014, 38: 150-157 CrossRef Google Scholar

[4] Xu L, Lu C, Xu Y, et al. Image smoothing via $L_0$ gradient minimization. ACM Trans Graph, 2011, 30: 1--12. Google Scholar

[5] Girshick R, Donahue J, Darrell T, et al. Rich feature hierarchies for accurate object detection and semantic segmentation. In: Proceedings of the IEEE conference on computer vision and pattern recognition, Columbus, 2014. 580--587. Google Scholar

[6] Long J, Shelhamer E, Darrell T. Fully convolutional networks for semantic segmentation. In: Proceedings of the IEEE conference on computer vision and pattern recognition, Santiago, 2015. 3431--3440. Google Scholar

[7] Boykov Y, Kolmogorov V. An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision.. IEEE Trans Pattern Anal Machine Intell, 2004, 26: 1124-1137 CrossRef PubMed Google Scholar

[8] Rother C, Kolmogorov V, Blake A. Grabcut: Interactive foreground extraction using iterated graph cuts. ACM Trans Graph, 2004, 23: 309-314 CrossRef Google Scholar

[9] Wang X Y, Xiang J, Pan R R, et al. Automatic extraction on embroidered patterns of traditional costumes. J Textile Res, 2017, 38: 120--126. Google Scholar

[10] Wang Y J, Zhou J X, Xu T W. Application of improved fuzzy c-means algorithm for ethnic costume image segmentation. Comput Eng, 2017, 43: 261--267. Google Scholar

[11] Han H M, Yao L, Wan Y. Fiber image segmentation based on K-means and GVF snake model. J Donghua Univ (Nat Sci), 2011, 37: 66--71. Google Scholar

[12] Bay H, Tuytelaars T, Gool L V. Surf: speeded up robust features. In: Proceedings of European Conference on Computer Vision, Graz, 2006. 404--417. Google Scholar

[13] Lowe D G. Object recognition from local scale-invariant features. In: Proceedings of the 7th IEEE International Conference on Computer Vision, Fort Collins, 1999. 1150--1157. Google Scholar

[14] Rublee E, Rabaud V, Konolige K, et al. Orb: An efficient alternative to sift or surf. In: Proceedings of IEEE International Conference on Computer Vision, Barcelona, 2011. 2564--2571. Google Scholar

[15] Igarashi T, Moscovich T, Hughes J F. As-rigid-as-possible shape manipulation. ACM Trans Graph, 2005, 24: 1134-1141 CrossRef Google Scholar

[16] Brown M, Lowe D G. Automatic Panoramic Image Stitching using Invariant Features. Int J Comput Vision, 2007, 74: 59-73 CrossRef Google Scholar

[17] Belongie S, Malik J, Puzicha J. Shape context: A new descriptor for shape matching and object recognition. In: Advances in Neural Information Processing Systems. 2001. 831--837. Google Scholar

[18] Ling H B, Jacobs D W. Shape classification using the inner-distance.. IEEE Trans Pattern Anal Mach Intell, 2007, 29: 286-299 CrossRef PubMed Google Scholar

[19] Cheng M M, Zhang F L, Mitra N J, et al. Repfinder: finding approximately repeated scene elements for image editing. ACM Trans Graph, 2010, 83: 1--8. Google Scholar

[20] Barnes C, Shechtman E, Finkelstein A. PatchMatch. ACM Trans Graph, 2009, 28: 1 CrossRef Google Scholar

[21] Barnes C, Shechtman E, Goldman D B, et al. The generalized patchmatch correspondence algorithm. In: Proceedings of European Conference on Computer Visio, Crete, 2010. 29--43. Google Scholar

[22] Lukáč M, Sýkora D, Sunkavalli K. Nautilus: recovering regional symmetry transformations for image editing. ACM Trans Graph, 2017, 36: 1-11 CrossRef Google Scholar

  • Figure 1

    (Color online) The drawbacks of existing segmentation methods for ethnic cultural patterns and our improvement based on segmentation co-optimization. The optimizing objects are surrounding petal patterns, different colors indicate different primitive regions in (b), (c), (d), and color correspondence between the left and right zoom-in sub-figures indicates the consistency of our segmentation in (d). (a) Input image; (b) mean-shift [1]; (c) $L_0$ segmentation [2]; (d) our result

  • Figure 2

    (Color online) The overall framework of our method. (a) User interaction; (b) object detection; (c) is a dense matching map of a partial region; (d) pre-segmentation; (e) our result

  • Figure 3

    (Color online) Comparison of single target selection methods. The top sub-figure in (c) shows the result of the traditional Grabcut method, the bottom sub-figure in (c) shows our result. The local background area makes our method avoid the interference of similar patterns in the background. (a) Input image with user interaction; (b) region partition; (c) segmentation comparison

  • Figure 4

    (Color online) The iterative automatic detection for multiple objects. (a) User interaction; (b) first global patch matching; (c) second global patch matching; (d) initial segmentation; (e) first segmentation; (f) second segmentation

  • Figure 5

    (Color online) Our dense match results based on rotation angle alignment. (a) Matching ambiguity; (b) dominating direction estimation; (c) our improvement

  • Figure 6

    (Color online) The illustration of our co-optimization effect, arrows represent the correspondence between the primitives before and after co-optimization. (a) Primitive correspondence before co-optimization; (b) primitive correspondence after co-optimization

  • Figure 7

    (Color online) Compared with the state-of-the-art segmentation methods. Our method has much less under-segmentation and over-segmentation issues, thus is closest to ground truth. (a) Input image; (b) $L_0$ segmentation [2]; (c) color threshold merge; (d) mean-shift [1]; (e) our result using Mean-shift; (f) our result using $L_0$ segm.; (g) ground truth

  • Figure 8

    (Color online) Comparison of the segmentation results on the ethnic carpet, arrows point out the advantages of our method. (a) Input image; (b) $L_0$ segmentation [2]($\lambda=0.06$); (c) $L_0$ segmentation [2]($\lambda=0.08$); (d) our result

  • Figure 9

    (Color online) Comparison of the segmentation results on the national costumes, arrows point out the advantages of our method. (a) Input image; (b) segmentation without co-optimization; (c) segmentation with co-optimization

  • Figure 10

    (Color online) Comparison of segmentation co-optimization results on natural images, arrows point the advantages of our method. (a) Input image; (b) $L_0$ segmentation; (c) our result; (d) mean-shift [1]($h_s$, $h_r$)=(31, 18); (e) mean-shift [1]($h_s$, $h_r$)=(20, 12); (f) failure cases

  • Figure 11

    (Color online) Comparison of segmentation co-optimization accuracy. Arrows point out drawbacks of the segmentation method based on $L_0$ gradient minimization. Error maps emphasize the accuracy of our method. (a) Input image; (b) $L_0$ segmentation; (c) our result; (d) ground truth; (e) $L_0$ segmentation [2]error map; (f) our error map

  • Figure 12

    (Color online) Our vectorization results and comparison with VectorMagic vectorization, the blue dots and lines are the corresponding vector graphics. (a) Four similar patterns from the input image; (b) vectorization based on our segmentation results; (c) vectorization of a commercial software VectorMagic

  • 1   Table 1Experimental data statistics
    Image information Time (s) Accuracy (%)
    Images Size Number of Multi-target Pre- Collaborative Pre- Our
    patterns selection segmentation optimization segmentation result
    Petal (Figure 1) 1000$\times$1000 16 8.629 3.436 12.465 83.2 90.2
    Disc (Figure 3) 1000$\times$936 6 70.512 2.91 26.431 87.9 92.4
    Ethnic clothing (Figure 7)
    1001$\times$945 2 60.068 3.368 12.603 80.1 86.5
    Carpet (Figure 8) 1025$\times$827 20 31.307 2.807 17.564 86.6 91.8
    Ethnic clothing (Figure 9)
    894$\times$726 2 46.532 2.506 11.352 82.8 90.3
    Butterfly (Figure 10) 1024$\times$727 2 127.157 2.327 15.234 82.3 93.6

    Algorithm 1 分割图元的协同优化

    Require:输入: 相似图案$\{E^k\},~k\in~[1,N]$, 图元$\{E^k_i\},~i\in[1,N_k]$ 和相似图案之间的稠密对应$\Psi(E^k)\to~E^s$;



    while $k~\neq~N$ do


    while $i~\neq~N_k$ do


    if $E^k_j~\neq~\emptyset$ then

    if $\bigcup_{s=1,s\neq~k}^{s=N}~\Big(\Omega(E^k_i,~\Psi(E^k)\to~E^s)~\bigcap~\Omega(E^k_j,~\Psi(E^k)\to~E^s)\Big)~\neq~\emptyset$ then


    end if

    end if


    end while


    输出: 新的$\{E^k_i\}$

    end while