logo

SCIENTIA SINICA Informationis, Volume 50 , Issue 3 : 424-437(2020) https://doi.org/10.1360/SSI-2019-0181

An alpha matting algorithm based on collaborative swarm optimization for high-resolution images

More info
  • ReceivedAug 25, 2019
  • AcceptedSep 17, 2019
  • PublishedFeb 27, 2020

Abstract

High-resolution image matting is one of the challenges in image composition and foreground extraction. It is essentially a large-scale combinatorial optimization problem for foreground/background pixel pairs. However, little attention has been paid to this issue. A multiclass collaborative optimization strategy based on RGB color clustering is proposed to reduce the dimension of this problem, addressing the issues caused by its ultrahigh dimension. This paper presents a collaborative feedback grouping strategy to solve this large-scale combinatorial optimization problem. Based on these two strategies, a competitive swarm optimization algorithm based on group collaboration (GC-CSO) is proposed. Its performance is verified experimentally by using an alpha matting dataset, showing that it can significantly reduce the dimension of the image matting problem and outperform the existent large-scale optimization algorithms with grouping strategies in the alpha matte comparison.


Funded by

国家自然科学基金(61772233,61876207,61772225)

广东省自然科学杰出青年基金(2014A030306050)

广东省重点领域研发计划项目(2018B010109003)

贵州省科技计划项目([2019]1164)

广州市科学技术局项目(201802010007)

广州市对外合作项目(201807010047)

贵州省教育厅青年科技人才成长项目([2016]165)


References

[1] Kim S H, Tai Y W, Park J. Multi-View Object Extraction With Fractional Boundaries. IEEE Trans Image Process, 2016, 25: 3639-3654 CrossRef PubMed ADS Google Scholar

[2] Chen T, Cheng M M, Tan P. Sketch2Photo. ACM Trans Graph, 2009, 28: 1 CrossRef Google Scholar

[3] Gong M L, Qian Y M, Cheng L. Integrated Foreground Segmentation and Boundary Matting for Live Videos. IEEE Trans Image Process, 2015, 24: 1356-1370 CrossRef PubMed ADS Google Scholar

[4] Cho D, Kim S, Tai Y W. Automatic Trimap Generation and Consistent Matting for Light-Field Images.. IEEE Trans Pattern Anal Mach Intell, 2017, 39: 1504-1517 CrossRef PubMed Google Scholar

[5] Liang Y H, Huang H, Cai Z Q. Deep infrared pedestrian classification based on automatic image matting. Appl Soft Computing, 2019, 77: 484-496 CrossRef Google Scholar

[6] Wu H, Li Y L, Miao Z J. A new sampling algorithm for high-quality image matting. J Visual Communication Image Representation, 2016, 38: 573-581 CrossRef Google Scholar

[7] Yao G L, Zhao Z J, Liu S H. A Comprehensive Survey on Sampling-Based Image Matting. Comput Graphics Forum, 2017, 36: 613-628 CrossRef Google Scholar

[8] Fan Z, Lu J W, Wei C M. A Hierarchical Image Matting Model for Blood Vessel Segmentation in Fundus Images. IEEE Trans Image Process, 2019, 28: 2367-2377 CrossRef PubMed ADS Google Scholar

[9] Wang Y, Niu Y, Duan P Y, et al. Deep propagation based image matting. In: Proceedings of the 27th International Joint Conference on Artificial Intelligence, Stockholm, 2018. 999--1006. Google Scholar

[10] Porter T, Duff T. Compositing digital images. In: Proceedings of ACM Siggraph Computer Graphics. New York: ACM, 1984. 253--259. Google Scholar

[11] Xu N, Price B, Cohen S, et al. Deep image matting. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Honolulu, 2017. 2970--2979. Google Scholar

[12] Levin A, Lischinski D, Weiss Y. A closed-form solution to natural image matting.. IEEE Trans Pattern Anal Mach Intell, 2008, 30: 228-242 CrossRef PubMed Google Scholar

[13] Yao G L. A Survey on Pre-Processing in Image Matting. J Comput Sci Technol, 2017, 32: 122-138 CrossRef Google Scholar

[14] Chen Q F, Li D Z Y, Tang C K. KNN Matting.. IEEE Trans Pattern Anal Mach Intell, 2013, 35: 2175-2188 CrossRef PubMed Google Scholar

[15] Wang J, Cohen M F. Optimized color sampling for robust matting. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Minnesota, 2007. 1--8. Google Scholar

[16] He B, Wang G J, Shi C B, et al. Iterative transductive learning for alpha matting. In: Proceedings of the IEEE International Conference on Image Processing, Melbourne, 2013. 4282--4286. Google Scholar

[17] He K, Rhemann C, Rother C, et al. A global sampling method for alpha matting. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Colorado, 2011. 2049--2056. Google Scholar

[18] Feng X X, Liang X H, Zhang Z L. A cluster sampling method for image matting via sparse coding. In: Proceedings of European Conference on Computer Vision, Amsterdam, 2016. 204--219. Google Scholar

[19] Shahrian E, Rajan D, Price B, et al. Improving image matting using comprehensive sampling sets. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Portland, 2013. 636--643. Google Scholar

[20] Johnson J, Varnousfaderani E S, Cholakkal H. Sparse Coding for Alpha Matting. IEEE Trans Image Process, 2016, 25: 3032-3043 CrossRef PubMed ADS arXiv Google Scholar

[21] Huang H, Liang Y H, Yang X W. Pixel-Level Discrete Multiobjective Sampling for Image Matting. IEEE Trans Image Process, 2019, 28: 3739-3751 CrossRef PubMed ADS Google Scholar

[22] Cai Z Q, Lv L, Huang H. Improving sampling-based image matting with cooperative coevolution differential evolution algorithm. Soft Comput, 2017, 21: 4417-4430 CrossRef Google Scholar

[23] Liang Y H, Huang H, Cai Z Q, et al. Particle swarm optimization with convergence speed controller for sampling-based image matting. In: Proceedings of International Conference on Intelligent Computing, Wuhan, 2018. 656--668. Google Scholar

[24] Liang Y H, Huang H, Cai Z Q. Multiobjective Evolutionary Optimization Based on Fuzzy Multicriteria Evaluation and Decomposition for Image Matting. IEEE Trans Fuzzy Syst, 2019, 27: 1100-1111 CrossRef Google Scholar

[25] Duan H B, Zhang D F, Fan Y M. From wolf pack intelligence to UAV swarm cooperative decision-making. Sci Sin-Inf, 2019, 49: 112-118 CrossRef Google Scholar

[26] Duan H B, Qiao P X. Pigeon-inspired optimization: a new swarm intelligence optimizer for air robot path planning. Int Jnl Intel Comp Cyber, 2014, 7: 24-37 CrossRef Google Scholar

[27] Cheng R, Jin Y C. A competitive swarm optimizer for large scale optimization.. IEEE Trans Cybern, 2015, 45: 191-204 CrossRef PubMed Google Scholar

[28] Rhemann C, Rother C, Wang J, et al. A perceptually motivated online benchmark for image matting. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Miami, 2009. 1826--1833. Google Scholar

[29] Gu S K, Cheng R, Jin Y C. Feature selection for high-dimensional classification using a competitive swarm optimizer. Soft Comput, 2018, 22: 811-822 CrossRef Google Scholar

[30] Mohapatra P, Nath Das K N, Roy S. A modified competitive swarm optimizer for large scale optimization problems. Appl Soft Computing, 2017, 59: 340-362 CrossRef Google Scholar

[31] Li X D, Yao X. Cooperatively Coevolving Particle Swarms for Large Scale Optimization. IEEE Trans Evol Computat, 2012, 16: 210-224 CrossRef Google Scholar

[32] Li X D, Yao X. Tackling high dimensional nonseparable optimization problems by cooperatively coevolving particle swarms. In: Proceedings of the IEEE Congress on Evolutionary Computation, Trondheim, 2009. 1546--1553. Google Scholar

[33] Yin F, Hu W, Hu J. Unification and simplification for position updating formulas in particle swarm optimization. Sci Sin-Inf, 2016, 46: 1676-1692 CrossRef Google Scholar

[34] Omidvar M N, Li X D, Mei Y. Cooperative Co-Evolution With Differential Grouping for Large Scale Optimization. IEEE Trans Evol Computat, 2014, 18: 378-393 CrossRef Google Scholar

[35] Shi Y J, Teng H F, Li Z Q. Cooperative co-evolutionary differential evolution for function optimization. In: Proceedings of International Conference on Natural Computation, Changsha, 2005. 1080--1088. Google Scholar

[36] Huang H, Lv L, Ye S J. Particle swarm optimization with convergence speed controller for large-scale numerical optimization. Soft Comput, 2019, 23: 4421-4437 CrossRef Google Scholar

  • Figure 1

    An example of trimap

  • Figure 2

    Group optimization strategy based on collaborative target feedback

  • Figure 3

    (Color online) Alpha matting comparison between GC-CSO and CSO algorithms in GT27. (a) Original image with calibration area; (b) calibration area; (c) alpha matting with CSO algorithm; (d) alpha matting with GC-CSO algorithm

  • Figure 4

    (Color online) Comparison of alpha matting results on high-resolution images. (a) Original image with calibration area; (b) trimap of calibration area; (c) alpha matting with GC-CSO algorithm; (d) alpha matting with CC-PSO algorithm; (e) alpha matting with CC-DE-S algorithm

  •   

    Algorithm 1 Competitive swarm optimization algorithm based on group collaboration

    Input:High-resolution image and trimap;

    //A multi-class collaborative optimization strategy based on RGB color clustering;

    Cluster the unknown region $U$ through RGB color space to generate class $C$;

    $i~\Leftarrow~1$;

    while $i~\le~C$ do

    $X' \Leftarrow X' \cup $ $\left\{ {} \right.$selecting an unknown pixel ${x'_i}$$\left. {} \right\}$ from $X'$ randomly;

    $i~\Leftarrow~i~+~1$;

    end while

    According to the dimension value $\left| {X'} \right|$ of $X'$, the initial population ${P_0}$ is generated randomly;

    Operate competitive swarm optimization algorithm to optimize target $X'$;

    The optimal ${X'_{\rm best}}$ is obtained;

    //Grouping optimization strategy based on collaboration objective feedback;

    ${X_{\rm~best}}~\Leftarrow~{\overrightarrow~0~_{\left(~{1~\times~\left|~U~\right|}~\right)}}$;

    $i~\Leftarrow~1$;

    while{$i \le C$} do

    ${X_i} \Leftarrow {X'_{\rm best}}\left( i \right)$, where ${X'_{\rm best}}\left( i \right)$ represents the $i$th element in ${X'_{\rm best}}$;

    According to the dimension value $\left|~{{X_i}}~\right|$ of ${X_i}$, the initial population ${P_0}$ is generated randomly, and ${X'_i} \in {P_0}$;

    Operate competitive swarm optimization algorithm to optimize target ${X_i}$;

    Get the solution ${X_{i,{\rm~best}}}$ of sub-problem $i$;

    $i~\Leftarrow~i~+~1$;

    end while

    Output:${X_{\rm~best}}~=~\left(~{{X_{1,{\rm~best}}},{X_{2,{\rm~best}}},~\ldots~,{X_{C,{\rm~best}}}}~\right)$;

  • Table 1   Problem dimension comparison between the original image matting problem and the clustered image matting problem$^{\rm~a)b)}$
    GT01 GT02 GT03 GT04 GT05 GT06 GT07 GT08 GT09
    Dimensions of $X$ 1051874 1871217 1602223 3681622 879551 1220458 1182974 1872160 1309282
    Dimensions of ${X'}$ 367432 191294 276900 824993 141777 226212 181320 481223 243405
    GT10 GT11 GT12 GT13 GT14 GT15 GT16 GT17 GT18
    Dimensions of $X$ 1309983 1202842 768659 3411227 877021 994511 1682771 1146322 1064989
    Dimensions of ${X'}$ 175371 288977 234301 215929 175579 120159 298514 179987 243954
    GT19 GT20 GT21 GT22 GT23 GT24 GT25 GT26 GT27
    Dimensions of $X$ 725149 1167945 2992362 1285129 1203427 1318789 1712779 2573636 2577680
    Dimensions of ${X'}$ 242952 278184 472514 254230 186337 266761 407020 500700 752028

    a $X$: the decision variable of the original high-resolution image matting problem.$X'$: the decision variable of the high-resolution image matting problem with multi-classes collaborative optimization strategy based on RGB color clustering.

  • Table 2   MSE comparison between GC-CSO and CSO algorithms$^{\rm~a)}$
    Algorithm GT01 GT02 GT03 GT04 GT05 GT06 GT07 GT08 GT09
    GC-CSO 2.251E$-$2 3.847E$-$2 3.350E$-$2 6.423E$-$2 3.233E$-$2 5.971E$-$2 1.961E$-$2 8.116E$-$2 6.639E$-$2
    CSO [27] 2.340E$-$2 3.915E$-$2 3.526E$-$2 7.835E$-$2 3.362E$-$2 6.144E$-$2 1.986E$-$2 7.761E$-$2 6.899E$-$2
    Algorithm GT10 GT11 GT12 GT13 GT14 GT15 GT16 GT17 GT18
    GC-CSO 6.887E$-$2 9.832E$-$2 9.214E$-$3 9.514E$-$2 4.112E$-$2 5.865E$-$2 2.946E$-$1 2.800E$-$2 8.400E$-$2
    CSO [27] 6.754E$-$2 9.861E$-$2 9.110E$-$3 1.085E$-$1 4.465E$-$2 6.030E$-$2 3.141E$-$1 2.875E$-$2 8.661E$-$2
    Algorithm GT19 GT20 GT21 GT22 GT23 GT24 GT25 GT26 GT27
    GC-CSO 8.385E$-$2 2.171E$-$2 7.367E$-$2 3.569E$-$2 4.167E$-$2 1.546E$-$1 2.254E$-$1 1.365E$-$1 1.938E$-$1
    CSO [27] 8.433E$-$2 2.226E$-$2 7.370E$-$2 3.622E$-$2 4.230E$-$2 1.605E$-$1 2.442E$-$1 1.411E$-$1 1.966E$-$1

    a The boldface values indicate the best results.

  •   

    Algorithm 2 Multi-class collaborative optimization strategy based on RGB color clustering

    Input:Pixel set ${{\cal~P}_U}$ of unknown region;

    //RGB clustering part;

    $i~\Leftarrow~1$; $j~\Leftarrow~1$;

    while $i~\le~\eta~$ do

    while $j~\le~N$ do

    if $I_j^U~=~~=~{R_i}$ then

    ${X_i}~\Leftarrow~{X_i}~\cup~\left\{~{{x_j}}~\right\}$;

    end if

    end while

    end while

    while $i~\le~\eta~$ do

    $X' \Leftarrow X' \cup $ $\left\{ {} \right.$selecting an unknown pixel ${x'_i}$$\left. {} \right\}$ from $X'$ randomly;

    $i~\Leftarrow~i~+~1$;

    end while

    //The initial population ${P_0}$ is generated randomly with the population size of $n$;

    while $i~\le~n$ do

    while $j~\le~\eta~$ do

    $x_{i,j}^F~\Leftarrow~1~+~\left(~{\left|~{{{\cal~P}_F}}~\right|~-~1}~\right)~\cdot~{\rm~rand}\left(~{}~\right)$;

    $x_{i,j}^B~\Leftarrow~1~+~\left(~{\left|~{{{\cal~P}_B}}~\right|~-~1}~\right)~\cdot~{\rm~rand}\left(~{}~\right)$;

    ${X'_i} \Leftarrow {X'_i} \cup ( {x_{i,j}^F,x_{i,j}^B} )$;

    end while

    ${P_0} \Leftarrow {P_0} \cup {X'_i}$;

    end while

    //Collaborative optimization part;

    while terminate condition is not met do

    Evaluate all individuals in ${P_t}$ with formula (4);

    $P' \Leftarrow {P_t}$; ${P_{t + 1}} \Leftarrow \emptyset $;

    while$P' \ne \emptyset $do

    Two individuals $X_{r1}^t$ and $X_{r2}^t$ are selected randomly from ${P_t}$;

    if $f\left(~{X_{r1}^t}~\right)~\le~f\left(~{X_{r2}^t}~\right)$ then

    $X_w^t~\Leftarrow~X_{r1}^t;~X_l^t~\Leftarrow~X_{r2}^t$;

    else

    $X_w^t~\Leftarrow~X_{r2}^t;~X_l^t~\Leftarrow~X_{r1}^t$;

    end if

    $V_l^{t~+~1}~\Leftarrow~R_1^t~\cdot~V_l^t~+~R_2^t~\cdot~\left(~{X_w^t~-~X_l^t}~\right)~+~\varphi~~\cdot~R_3^t~\cdot~(~{\overline~{{X^t}}~~-~X_l^t}~)$;

    $X_l^{t~+~1}~\Leftarrow~X_l^t~+~V_l^{t~+~1}$;

    while $i~\le~\eta~$ do

    $x_{l,j}^F~\Leftarrow~\min~(~{x_{l,j}^F,\left|~{{{\cal~P}_F}}~\right|}~)$; $x_{l,j}^F~\Leftarrow~\max~(~{x_{l,j}^F,1}~)$;

    $x_{l,j}^B~\Leftarrow~\min~(~{x_{l,j}^F,\left|~{{{\cal~P}_B}}~\right|}~)$; $x_{l,j}^B~\Leftarrow~\max~(~{x_{l,j}^B,1}~)$;

    end while

    Add $X_l^{t + 1}$ and $X_w^t$ to the new generation population ${P_{t + 1}}$ and remove $X_{r1}^t$ and $X_{r2}^t$ from $P'$;

    end while

    $t~\Leftarrow~t~+~1$;

    end while

    Output:${X'_{\rm best}}$

  • Table 3   MSE comparison of GC-SCO and typical optimization algorithms with grouping strategies$^{\rm~a)}$
    Algorithm GT01 GT02 GT03 GT04 GT05 GT06 GT07 GT08 GT09
    GC-CSO 2.251E$-$2 3.847E$-$2 3.350E$-$2 6.423E$-$2 3.233E$-$2 5.971E$-$2 1.961E$-$2 8.116E$-$2 6.639E$-$2
    CC-PSO [36] 1.959E$-$2 4.012E$-$2 3.120E$-$2 7.591E$-$2 4.326E$-$2 6.458E$-$2 2.593E$-$2 8.714E$-$2 6.830E$-$2
    CC-DE-S [22] 1.527E$-$2 3.881E$-$2 3.659E$-$2 7.944E$-$2 4.190E$-$2 5.678E$-$2 2.981E$-$2 9.418E$-$2 7.406E$-$2
    Algorithm GT10 GT11 GT12 GT13 GT14 GT15 GT16 GT17 GT18
    GC-CSO 6.887E$-$2 9.832E$-$2 9.214E$-$3 9.514E-02 4.112E$-$2 5.865E$-$2 2.946E$-$1 2.800E$-$2 8.400E$-$2
    CC-PSO [36] 7.179E$-$2 1.227E$-$1 1.411E$-$2 9.281E$-$2 5.564E$-$2 6.538E$-$2 3.035E$-$1 5.206E$-$2 8.427E$-$2
    CC-DE-S [22] 6.639E$-$2 9.844E$-$2 1.819E$-$2 7.343E$-$2 5.055E$-$2 6.113E$-$2 1.879E$-$1 4.423E$-$2 8.695E$-$2
    Algorithm GT19 GT20 GT21 GT22 GT23 GT24 GT25 GT26 GT27
    GC-CSO 8.385E$-$2 2.171E$-$2 7.367E$-$2 3.569E$-$2 4.167E$-$2 1.546E$-$1 2.254E$-$1 1.365E$-$1 1.938E$-$1
    CC-PSO [36] 8.318E$-$2 2.315E$-$2 7.085E$-$2 3.898E$-$2 6.251E$-$2 1.577E$-$1 2.084E$-$1 1.577E$-$1 2.060E$-$1
    CC-DE-S [22] 8.414E$-$2 2.189E$-$2 5.745E$-$2 3.835E$-$2 3.400E$-$2 8.465E$-$1 2.001E$-$1 1.400E$-$1 1.226E$-$1

    a The boldface values indicate the best results.

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备17057255号       京公网安备11010102003388号