Rectangular Decomposition of Binary Images

详细信息    查看全文

• 作者：Tomá? Suk (1) suk@utia.cas.cz
  Cyril H?schl IV (1) hoschl@utia.cas.cz
  Jan Flusser (1) flusser@utia.cas.cz
• 关键词：Binary image decomposition – generalized delta ; method – distance transformation – quadtree – bipartite graph – image compression – fast convolution
• 刊名：Lecture Notes in Computer Science
• 出版年：2012
• 出版时间：2012
• 年：2012
• 卷：7517
• 期：1
• 页码：213-224
• 全文大小：368.7 KB
• 参考文献：1. Borgefors, G.: Distance transformations in digital images. Computer Vision, Graphics, and Image Processing 34(3), 344–371 (1986)
  2. Department of Image Processing: Tree leaf database, http://zoi.utia.cas.cz/tree_leaves
  3. Edmonds, J., Karp, R.M.: Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the Association for Computing Machinery 19(2), 248–264 (1972)
  4. Eppstein, D.: Graph-Theoretic Solutions to Computational Geometry Problems. In: Paul, C., Habib, M. (eds.) WG 2009. LNCS, vol. 5911, pp. 1–16. Springer, Heidelberg (2010)
  5. Fernandes, A.: FFTPACK translated to pure iso c/c++, http://www.fernandes.org/txp/article/4fftpack-translated-to-pure-iso-cc
  6. Ferrari, L., Sankar, P.V., Sklansky, J.: Minimal rectangular partitions of digitized blobs. Computer Vision, Graphics, and Image Processing 28(1), 58–71 (1984)
  7. Flusser, J., Suk, T., Zitová, B.: Moments and Moment Invariants in Pattern Recognition. Wiley, Chichester (2009)
  8. Imai, H., Asano, T.: Efficient algorithms for geometric graph search problems. SIAM Journal on Computing 15(2), 478–494 (1986)
  9. Kawaguchi, E., Endo, T.: On a method of binary-picture representation and its application to data compression. IEEE Transactions on Pattern Analysis and Machine Intelligence 2(1), 27–35 (1980)
  10. Keil, J.M.: Polygon decomposition. In: Handbook of Computational Geometry, pp. 491–518. Elsevier (2000)
  11. Levin, A., Fergus, R., Durand, F., Freeman, W.T.: Image and depth from a conventional camera with a coded aperture. In: Special Interest Group on Computer Graphics and Interactive Techniques Conference, SIGGRAPH 2007. ACM, New York (2007)
  12. Lipski Jr., W., Lodi, E., Luccio, F., Mugnai, C., Pagli, L.: On two-dimensional data organization II. In: Fundamenta Informaticae. Series IV, vol. II, pp. 245–260 (1979)
  13. Ohtsuki, T.: Minimum dissection of rectilinear regions. In: Proceedings of the IEEE International Conference on Circuits and Systems, ISCAS 1982, pp. 1210–1213. IEEE (1982)
  14. Schouten, T.E., van den Broek, E.L.: Incremental distance transforms (IDT). In: 20th International Conference on Pattern Recognition, ICPR 2010, pp. 237–240. IEEE Computer Society (August 2010)
  15. Seaidoun, M.: A Fast Exact Euclidean Distance Transform with Application to Computer Vision and Digital Image Processing. Ph.D. thesis, Northeastern University, Boston, USA (September 1993) advisor John Gauch
  16. Sossa-Azuela, J.H., Yá?ez-Márquez, C., Díaz de León Santiago, J.L.: Computing geometric moments using morphological erosions. Pattern Recognition 34(2), 271–276 (2001)
  17. Spiliotis, I.M., Mertzios, B.G.: Real-time computation of two-dimensional moments on binary images using image block representation. IEEE Transactions on Image Processing 7(11), 1609–1615 (1998)
  18. Zakaria, M.F., Vroomen, L.J., Zsombor-Murray, P., van Kessel, J.M.: Fast algorithm for the computation of moment invariants. Pattern Recognition 20(6), 639–643 (1987)
• 作者单位：1. Institute of Information Theory and Automation of the ASCR, Pod vodárenskou vě?í 4, 182 08 Praha 8, Czech Republic
• ISSN：1611-3349

文摘

The contribution deals with the most important methods for decomposition of binary images into union of rectangles. The overview includes run-length encoding and its generalization, decompositions based on quadtrees, on the distance transformation, and a theoretically optimal decomposition based on maximal matching in bipartite graphs. We experimentally test their performance in binary image compression and in convolution calculation and compare their computation times and success rates.