×

Determinantal point processes for image processing. (English) Zbl 1474.60134

Summary: Determinantal point processes (DPPs) are probabilistic models of configurations that favor diversity or repulsion. They have recently gained influence in the machine learning community, mainly because of their ability to elegantly and efficiently subsample large sets of data. In this paper, we consider DPPs from an image processing perspective, meaning that the data we want to subsample are pixels or patches of a given image. To this end, our framework is discrete and finite. First, we adapt their basic definition and properties to DPPs defined on the pixels of an image, that we call determinantal pixel processes (DPixPs). We are mainly interested in the repulsion properties of such a process and we apply DPixPs to texture synthesis using shot noise models. Finally, we study DPPs on the set of patches of an image. Because of their repulsive property, DPPs provide a strong tool to subsample discrete distributions such as that of image patches.

MSC:

60G55 Point processes (e.g., Poisson, Cox, Hawkes processes)
62M40 Random fields; image analysis
68U10 Computing methodologies for image processing
94A08 Image processing (compression, reconstruction, etc.) in information and communication theory

Software:

spatstat
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R. H. Affandi, E. B. Fox, R. P. Adams, and B. Taskar, Learning the parameters of determinantal point process kernels, in ICML, JMLR Workshop Conf. Proc., 32 (2014), pp. 1224-1232.
[2] A. Agarwal, A. Choromanska, and K. Choromanski, Notes on using Determinantal Point Processes for Clustering with Applications to Text Clustering, https://arxiv.org/abs/1410.6975 (2014).
[3] C. C. Aggarwal, Outlier Analysis, 2nd ed., Springer, Cham, Switzerland, 2016. · Zbl 1353.68004
[4] F. Baccelli and B. Blaszczyszyn, Stochastic geometry and wireless networks: Vol. I Theory, Found. Trends Netw., 3 (2009), pp. 249-449, https://doi.org/10.1561/1300000006. · Zbl 1184.68015
[5] R. Bardenet and M. Titsias, Inference for determinantal point processes without spectral knowledge, in Advances in Neural Information Processing Systems 28, C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett, eds., Curran Associates, Red Hook, NY, 2015, pp. 3393-3401.
[6] S. Barthelmé, P.-O. Amblard, and N. Tremblay, Asymptotic equivalence of fixed-size and varying-size determinantal point processes, Bernoulli, 25 (2019), pp. 3555-3589, https://doi.org/10.3150/18-BEJ1102. · Zbl 1428.62095
[7] A. Belhadji, R. Bardenet, and P. Chainais, A determinantal point process for column subset selection, J. Mach. Learn. Res., 21 (2020), pp. 1-62. · Zbl 07307477
[8] C. Biscio and F. Lavancier, Quantifying repulsiveness of determinantal point processes, Bernoulli, 22 (2016), pp. 2001-2028, https://doi.org/10.3150/15-BEJ718. · Zbl 1343.60058
[9] C. Biscio and F. Lavancier, Contrast estimation for parametric stationary determinantal point processes, Scand. J. Stat., 44 (2017), pp. 204-229. · Zbl 1361.60034
[10] C. A. Biscio and J.-F. Coeurjolly, Standard and robust intensity parameter estimation for stationary determinantal point processes, Spat. Stat., 18 (2016), pp. 24-39, https://doi.org/10.1016/j.spasta.2016.04.007.
[11] S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, Cambridge, 2004. · Zbl 1058.90049
[12] V. Brunel, Learning signed determinantal point processes through the principal minor assignment problem, in Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, 3-8 December 2018, Montréal, Canada, 2018, pp. 7376-7385.
[13] V. Brunel, A. Moitra, P. Rigollet, and J. Urschel, Rates of estimation for determinantal point processes, in COLT, Proc. Mach. Learn. Res., (PMLR), 65 (2017), pp. 343-345.
[14] E. Celis, V. Keswani, D. Straszak, A. Deshpande, T. Kathuria, and N. Vishnoi, Fair and diverse DPP-based data summarization, in Proceedings of the 35th International Conference on Machine Learning, J. Dy and A. Krause, eds., Proc. Mach. Learn. Res. (PMLR), 80 (2018), pp. 716-725.
[15] W. Chen, Z. Yang, F. Cao, Y. Yan, M. Wang, C. Qing, and Y. Cheng, Dimensionality reduction based on determinantal point process and singular spectrum analysis for hyperspectral images, IET Image Process., 13 (2019), pp. 299-306, https://doi.org/10.1049/iet-ipr.2018.5419.
[16] M. Combescure, Block-circulant matrices with circulant blocks, Weil sums, and mutually unbiased bases. II. The prime power case, J. Math. Phys., 50 (2009), 032104. · Zbl 1187.15041
[17] N. Cressie, Statistics for spatial data, Wiley, Hoboken, NJ, 2015. · Zbl 1347.62005
[18] K. Dabov, A. Foi, V. Katkovnik, and K. Egiazarian, Image denoising by sparse \(3\)-D transform-domain collaborative filtering, IEEE Trans. Image Process., 16 (2007), pp. 2080-2095.
[19] P. J. Davis, Circulant Matrices, American Mathematical Society, Providence, RI, 2013. · Zbl 0418.15017
[20] S. Descamps, X. Descombes, A. Béchet, and J. Zerubia, Automatic flamingo detection using a multiple birth and death process, in 2008 IEEE International Conference on Acoustics, Speech and Signal Processing, IEEE, Piscataway, NJ, 2008, pp. 1113-1116.
[21] G. M. Engel and H. Schneider, Matrices diagonally similar to a symmetric matrix, Linear Algebra Appl., 29 (1980), pp. 131-138, https://doi.org/10.1016/0024-3795(80)90234-7. · Zbl 0432.15014
[22] B. Galerne, Y. Gousseau, and J.-M. Morel, Random phase textures: Theory and synthesis, IEEE Trans. Image Process., 20 (2011), pp. 257-267, https://doi.org/10.1109/TIP.2010.2052822. · Zbl 1372.94086
[23] B. Galerne, A. Lagae, S. Lefebvre, and G. Drettakis, Gabor noise by example, ACM Trans. Graph., 31 (2012), 73, https://doi.org/10.1145/2185520.2185569.
[24] B. Galerne, A. Leclaire, and L. Moisan, Texton noise, in Comput. Graph. Forum, 36 (2017), pp. 205-218.
[25] M. Gartrell, U. Paquet, and N. Koenigstein, Low-rank factorization of determinantal point processes, in Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, AAAI’17, AAAI Press, Palo Alto, CA, 2017, pp. 1912-1918.
[26] B. Gong, W. Chao, K. Grauman, and F. Sha, Diverse sequential subset selection for supervised video summarization, in Advances in Neural Information Processing Systems 27 (NIPS 2014), Montreal, Quebec, Canada, Curran Associates, Red Hook, NY, 2014, pp. 2069-2077.
[27] D. J. Hartfiel and R. Loewy, On matrices having equal corresponding principal minors, Linear Algebra Appl., 58 (1984), pp. 147-167, https://doi.org/10.1016/0024-3795(84)90209-X. · Zbl 0541.15005
[28] M. Held, P. Wolfe, and H. P. Crowder, Validation of subgradient optimization, Math. Program., 6 (1974), pp. 62-88, https://doi.org/10.1007/BF01580223. · Zbl 0284.90057
[29] A. Houdard, C. Bouveyron, and J. Delon, High-dimensional mixture models for unsupervised image denoising (HDMI), SIAM J. Imaging Sci., 11 (2018), pp. 2815-2846. · Zbl 1475.94018
[30] J. B. Hough, M. Krishnapur, Y. Peres, and B. Virág, Determinantal processes and independence, Probab. Surv., 3 (2006), pp. 206-229. · Zbl 1189.60101
[31] J. B. Hough, M. Krishnapur, Y. Peres, and B. Virág, Zeros of Gaussian Analytic Functions and Determinantal Point Processes, Univ. Lect. Ser. 51, American Mathematical Society, Providence, RI, 2009. · Zbl 1190.60038
[32] A. Kulesza, Learning with Determinantal Point Processes, PhD thesis, University of Pennsylvania, Philadelphia, 2012. · Zbl 1278.68240
[33] A. Kulesza and B. Taskar, k-DPPs: Fixed-size determinantal point processes, in Proceedings of the 28th International Conference on Machine Learning, ICML’11, International Machine Learning Society, Madison, WI, 2011, pp. 1193-1200.
[34] A. Kulesza and B. Taskar, Learning determinantal point processes, in Proceedings of the Twenty-Seventh Conference on Uncertainty in Artificial Intelligence, AUAI Press, 2011, pp. 419-427. · Zbl 1278.68240
[35] A. Kulesza and B. Taskar, Determinantal point processes for machine learning, Found. Trends Mach. Learn., 5 (2012), pp. 123-286, https://doi.org/10.1561/2200000044. · Zbl 1278.68240
[36] A. Lagae, S. Lefebvre, G. Drettakis, and P. Dutré, Procedural noise using sparse Gabor convolution, ACM Trans. Graph., 28 (2009), pp. 54-64.
[37] C. Launay and A. Leclaire, Determinantal patch processes for texture synthesis, in GRETSI 2019, Lille, France, Aug 2019.
[38] F. Lavancier, J. Møller, and E. Rubak, Determinantal point process models and statistical inference, J. R. Stat. Soc. Ser. B Stat. Methodol., 77 (2015), pp. 853-877, https://www.jstor.org/stable/24775312. · Zbl 1414.62403
[39] F. Lavancier, A. Poinas, and R. Waagepetersen, Adaptive estimating function inference for nonstationary determinantal point processes, Scand. J. Stat., to appear, https://doi.org/10.1111/sjos.12440.
[40] R. Loewy, Principal minors and diagonal similarity of matrices, Linear Algebra Appl., 78 (1986), pp. 23-64, https://doi.org/10.1016/0024-3795(86)90015-7. · Zbl 0591.15005
[41] R. Lyons and J. E. Steif, Stationary determinantal processes: Phase multiplicity, Bernoullicity, entropy, and domination, Duke Math. J., 120 (2003), pp. 515-575, https://doi.org/10.1215/S0012-7094-03-12032-3. · Zbl 1068.82010
[42] O. Macchi, The coincidence approach to stochastic point processes, Adv. Appl. Probab., 7 (1975), pp. 83-122. · Zbl 0366.60081
[43] B. Mahasseni, M. Lam, and S. Todorovic, Unsupervised video summarization with adversarial LSTM networks., in CVPR, IEEE Computer Society, Los Alamitos, CA, 2017, pp. 2982-2991.
[44] J. Møller and R. Waagepetersen, Statistical Inference and Simulation for Spatial Point Process, Mongr. Statist. Appl. Probab., 100, Chapman and Hall/CRC, Boca Raton, FL, 2003, https://doi.org/10.1201/9780203496930. · Zbl 1039.62089
[45] B. J. Olson, S. W. Shaw, C. Shi, C. Pierre, and R. G. Parker, Circulant matrices and their application to vibration analysis, Appl. Mech. Rev., 66 (2014), 040803.
[46] G. Pagès, Introduction to vector quantization and its applications for numerics, ESAIM Proc. Surveys, 48 (2015), pp. 29-79, https://doi.org/10.1051/proc/201448002. · Zbl 1338.60114
[47] G. Perrin, X. Descombes, and J. Zerubia, Point Processes in Forestry: An Application to Tree Crown Detection, Research report RR-5544, INRIA, 2006.
[48] A. Poinas, B. Delyon, and F. Lavancier, Mixing properties and central limit theorem for associated point processes, Bernoulli, 25 (2019), pp. 1724-1754. · Zbl 1466.60101
[49] J. Rising, A. Kulesza, and B. Taskar, An efficient algorithm for the symmetric principal minor assignment problem, Linear Algebra Appl., 473 (2015), pp. 126-144. · Zbl 1314.65050
[50] J. Salmon and Y. Strozecki, From patches to pixels in non-local methods: Weighted-average reprojection, in 2010 IEEE International Conference on Image Processing, IEEE, Piscataway, NJ, 2010, pp. 1929-1932.
[51] B. D. Saunders and H. Schneider, Flows on graphs applied to diagonal similarity and diagonal equivalence for matrices, Discrete Math., 24 (1978), pp. 205-220, https://doi.org/10.1016/0012-365X(78)90200-5. · Zbl 0393.94046
[52] T. Shirai and Y. Takahashi, Fermion process and Fredholm determinant, in Proceedings of the Second ISAAC Congress, Springer, Boston, MA, 2000, pp. 15-23, https://doi.org/10.1007/978-1-4613-0269-8_3. · Zbl 1036.60045
[53] T. Shirai and Y. Takahashi, Random point fields associated with certain Fredholm determinants. I. Fermion, Poisson and boson point processes, J. Funct. Anal., 205 (2003), pp. 414-463. · Zbl 1051.60052
[54] T. Shirai and Y. Takahashi, Random point fields associated with certain Fredholm determinants II: Fermion shifts and their ergodic and Gibbs properties, Ann. Probab., 31 (2003), pp. 1533-1564, https://doi.org/10.1214/aop/1055425789. · Zbl 1051.60053
[55] A. Soshnikov, Determinantal random point fields, Russian Math. Surveys, (2000), pp. 923-975. · Zbl 0991.60038
[56] A. Soshnikov, Gaussian limit for determinantal random point fields, Ann. Probab., 30 (2002), pp. 171-187. · Zbl 1033.60063
[57] M. Stevens, Equivalent Symmetric Kernels of Determinantal Point Processes, arXiv e-prints, https://arxiv.org/abs/1905.08162, 2019.
[58] N. Tremblay, S. Barthelmé, and P.-O. Amblard, Optimized Algorithms to Sample Determinantal Point Processes, CoRR, abs/1802.08471 https://arxiv.org/pdf/1802.08471.pdf, 2018.
[59] N. Tremblay, S. Barthelmé, and P.-O. Amblard, Determinantal point processes for coresets, J. Mach. Learn. Res., (2019). · Zbl 1446.62351
[60] J. Urschel, V. Brunel, A. Moitra, and P. Rigollet, Learning determinantal point processes with moments and cycles, in ICML, Proc. Mach. Learn. Res. PMLR 70, 2017, pp. 3511-3520.
[61] J. J. van Wijk, Spot noise texture synthesis for data visualization, in SIGGRAPH ’91, New York, 1991, ACM, pp. 309-318, https://doi.org/10.1145/122718.122751.
[62] M. Wilhelm, A. Ramanathan, A. Bonomo, S. Jain, E. H. Chi, and J. Gillenwater, Practical diversified recommendations on Youtube with determinantal point processes, in Proceedings of the 27th ACM International Conference on Information and Knowledge Management, CIKM ’18, New York, NY, 2018, ACM, pp. 2165-2173, https://doi.org/10.1145/3269206.3272018.
[63] K. Zhang, W. Chao, F. Sha, and K. Grauman, Video summarization with long short-term memory, in Computer Vision - ECCV 2016 - 14th European Conference, Amsterdam, The Netherlands, October 11-14, 2016, Proceedings, Part VII, 2016, pp. 766-782, https://doi.org/10.1007/978-3-319-46478-7_47.
[64] D. Zoran and Y. Weiss, From learning models of natural image patches to whole image restoration, in Proceedings of the 2011 International Conference on Computer Vision, ICCV ’11, 2011, IEEE Computer Society, pp. 479-486, https://doi.org/10.1109/ICCV.2011.6126278.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.