Elamur Research⌕
☰
home / papers / 2014 / TreeTalk: Composition and Compression of Trees for Image Descriptions

TreeTalk: Composition and Compression of Trees for Image Descriptions

Paper · 2014 · Polina Kuznetsova, Vicente Ordonez, Tamara L. Berg et al.

Summary

The paper addresses automatic image captioning. Instead of limiting descriptions to what vision detectors can recognize, it draws on the expressive language people write about photos online. Given a query image, the system retrieves visually similar photos from the collection of captioned images assembled by Ordonez et al. (2011) and extracts parse-tree fragments from their captions. These fragments are noun phrases about objects, verb phrases about actions, and prepositional phrases about "stuff" and scenes. It then builds a new sentence by selecting and ordering at most one fragment per type.

This composition step is cast as constraint optimization with Integer Linear Programming. It jointly considers PCFG tree structure and n-gram cohesion at phrase boundaries, using a CKY-style formulation. As an optional preprocessing step, a tree compression method prunes caption branches that are unlikely to transfer to other images (caption generalization).

Human evaluations show clear gains over sequence-only and earlier approaches. The work is the first to show that automatically generalized captions help generation, and it releases the improved, generalized caption corpus publicly.

Key points

  • Phrase harvesting relies on deformable part model detectors run for 89 object classes with a high confidence threshold. Visual similarity is measured with color, texture and shape features, and four phrase types are used: object, action, stuff and scene.
  • Composition selects and reorders phrases, which makes the problem NP-hard. It is encoded as an ILP and solved with CPLEX.
  • In human judgments, SEQ+TREE beat SEQ for grammaticality 83% of the time and for relevance 72% of the time.
  • Composing from pruned fragments raised relevance preference to 68–72%, at a small cost in grammar (38–41%). System captions were preferred over the original owner-written captions 19–24% of the time.
  • The generalized caption corpus and system outputs are available at ilp-cky.appspot.com.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓University of WashingtonSeattle · United States353 works · 200,043 citations🎓University of North Carolina at Chapel HillChapel Hill · United States67 works · 16,474 citations🎓Stony Brook UniversityStony Brook · United States43 works · 2,571 citations

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 worksComputer Vision and Pattern Recognition · 2,869 works

🧭 Topics 1Research subjects and languages the work is about.Efficient models & compression · 242 works

Cite

Cite as Polina Kuznetsova, Vicente Ordonez, Tamara L. Berg and Yejin Choi. 2014. TreeTalk: Composition and Compression of Trees for Image Descriptions. Transactions of the Association for Computational Linguistics.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.1162/tacl_a_00188

@article{kuznetsova2014treetalk,
  title = {{TreeTalk: Composition and Compression of Trees for Image Descriptions}},
  author = {Polina Kuznetsova, Vicente Ordonez, Tamara L. Berg and Yejin Choi},
  journal = {Transactions of the Association for Computational Linguistics},
  year = {2014},
  doi = {10.1162/tacl\_a\_00188},
  url = {https://doi.org/10.1162/tacl_a_00188}
}

References

42 references, 9 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Regina Barzilay and Kathleen McKeown. 2005. Sentence fusion for multidocument news summarization. Computational Linguistics, 31(3):297–328.
  2. Tamara L. Berg, Alexander C. Berg, and Jonathan Shih. 2010. Automatic attribute discovery and characterization from noisy web data. In Proceedings of the 11th European Conference on Computer Vision: Part I, ECCV’10, pages 663–676, Berlin, Heidelberg. find
  3. Springer-Verlag. Thorsten Brants and Alex Franz. 2006. Web 1t 5-gram version 1. In Linguistic Data Consortium. find
  4. James Clarke and Mirella Lapata. 2008. Global inference for sentence compression an integer linear programming approach. Journal of Artificial Intelligence Research, 31:399–429. find
  5. Trevor Cohn and Mirella Lapata. 2007. Large margin synchronous generation and its application to sentence compression. In Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL), pages 73–82, Prague, Czech… find
  6. Trevor Cohn and Mirella Lapata. 2008. Sentence compression beyond word deletion. In Proceedings of the 22nd International Conference on Computational Linguistics (Coling 2008), pages 137–144, Manchester, UK, August.
  7. Coling 2008 Organizing Committee. find
  8. Navneet Dalal and Bill Triggs. 2005. Histograms of oriented gradients for human detection. In Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’05) - Volume 1 - Volume 01, CVPR ’05, pages 886–893, Washington, DC, USA. find
  9. IEEE Computer Society. Jia Deng, Alexander C. Berg, Kai Li, and Fei-Fei Li. 2010. What does classifying more than 10,000 image categories tell us? In ECCV. find
  10. Jia Deng, Alexander C. Berg, Sanjeev Satheesh, Hao Su, Aditya Khosla, and Fei-Fei Li. 2012a. Large scale visual recognition challenge. In http://www.imagenet.org/challenges/LSVRC/2012/index. ↗
  11. Jia Deng, Jonathan Krause, Alexander C. Berg, and L. Fei-Fei. 2012b. Hedging your bets: Optimizing accuracy-specificity trade-offs in large scale visual recognition. In Conference on Computer Vision and Pattern Recognition. find
  12. Michael Denkowski and Alon Lavie. 2011. Meteor 1.3: Automatic Metric for Reliable Optimization and Evaluation of Machine Translation Systems. In Proceedings of the EMNLP 2011 Workshop on Statistical Machine Translation.
  13. Jesse Dodge, Amit Goyal, Xufeng Han, Alyssa Mensch, Margaret Mitchell, Karl Stratos, Kota Yamaguchi, Yejin Choi, Hal Daume III, Alexander C. Berg, and Tamara L. Berg. 2012. Detecting visual text. In Proceedings of the 2012 Conference of the North American Chapter of the Association for Computational… find
  14. Desmond Elliott and Frank Keller. 2013. Image description using visual dependency representations. In EMNLP, pages 1292–1302. find
  15. Desmond Elliott and Frank Keller. 2014. Comparing automatic evaluation measures for image description. In ACL (2), pages 452–457. Ali Farhadi, Mohsen Hejrati, Mohammad Amin Sadeghi, Peter Young1, Cyrus Rashtchian, Julia Hockenmaier, and David Forsyth. 2010. Every picture tells a story: generating se… find
  16. Pedro F. Felzenszwalb, Ross B. Girshick, David McAllester, and Deva Ramanan. 2010. Object detection with discriminatively trained part based models. IEEE Transactions on Pattern Analysis and Machine Intelligence, 32(9):1627–1645. find
  17. Yansong Feng and Mirella Lapata. 2013. Automatic caption generation for news images. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(4):797–812. find
  18. Katja Filippova and Yasemin Altun. 2013. Overcoming the lack of parallel data in sentence compression. In EMNLP, pages 1481–1491.
  19. ILOG, Inc. 2006. ILOG CPLEX: High-performance software for mathematical programming and optimization. See http://www.ilog.com/products/ cplex/. ↗
  20. Michael Jamieson, Afsaneh Fazly, Suzanne Stevenson, Sven J. Dickinson, and Sven Wachsmuth. 2010. Using language to learn structured appearance models for image annotation. IEEE Trans. Pattern Anal. Mach. Intell., 32(1):148–164. find
  21. Dan Klein and Christopher D. Manning. 2003. Accurate unlexicalized parsing. In Proceedings of the 41st Annual Meeting on Association for Computational Linguistics, pages 423–430. Association for Computational Linguistics.
  22. Kevin Knight and Daniel Marcu. 2000. Statistics-based summarization - step one: Sentence compression. In AAAI/IAAI, pages 703–710. find
  23. Atsuhiro Kojima, Takeshi Tamura, and Kunio Fukunaga. 2002. Natural language description of human activities from video images based on concept hierarchy of actions. IJCV, 50. find
  24. Niveda Krishnamoorthy, Girish Malkarnenkar, Raymond J. Mooney, Kate Saenko, and Sergio Guadarrama. 2013. Generating natural-language video descriptions using text-mined knowledge. In AAAI. find
  25. Alex Krizhevsky, Ilya Sutskever, and Geoffrey Hinton. 2012. Imagenet classification with deep convolutional neural networks. In NIPS.
  26. Girish Kulkarni, Visruth Premraj, Sagnik Dhar, Siming Li, Yejin Choi, Alexander C. Berg, and Tamara L. Berg. 2011. BabyTalk: Understanding and generating simple image descriptions. In Conference on Computer Vision and Pattern Recognition. find
  27. Polina Kuznetsova, Vicente Ordonez, Alexander C. Berg, Tamara L. Berg, and Yejin Choi. 2012. Collective generation of natural image descriptions. In Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 359–368, Jeju Island, Korea, Jul… find
  28. Polina Kuznetsova, Vicente Ordonez, Alexander C. Berg, Tamara L. Berg, and Yejin Choi. 2013. Generalizing image captions for image-text parallel corpus. In The 51st Annual Meeting of the Association for Computational Linguistics - Short Papers, Sofia, Bulgaria, August. Association for Computational… find
  29. Thomas K. Leung and Jitendra Malik. 1999. Recognizing surfaces using three-dimensional textons. In ICCV, pages 1010–1017. find
  30. Siming Li, Girish Kulkarni, Tamara L. Berg, Alexander C. Berg, and Yejin Choi. 2011. Composing simple image descriptions using web-scale n-grams. In Proceedings of the Fifteenth Conference on Computational Natural Language Learning, pages 220–228, Portland, Oregon, USA, June. Association for Computa… find
  31. David G. Lowe. 2004. Distinctive image features from scale-invariant keypoints. Int. J. Comput. Vision, 60:91–110, November. find
  32. Rebecca Mason and Eugene Charniak. 2013. Annotation of online shopping images without labeled training examples. In Proceedings of Workshop on Vision and Language, Atlanta, Georgia, June. Association for Computational Linguistics. find
  33. Rebecca Mason. 2013. Domain-independent captioning of domain-specific images. In Proceedings of the 2013 NAACL HLT Student Research Workshop, pages 69–76, Atlanta, Georgia, June. Association for Computational Linguistics. Margaret Mitchell, Jesse Dodge, Amit Goyal, Kota Yamaguchi, Karl Stratos, Xufe… find
  34. Vicente Ordonez, Girish Kulkarni, and Tamara L. Berg. 2011. Im2text: Describing images using 1 million captioned photographs. In Neural Information Processing Systems (NIPS). Kishore Papineni, Salim Roukos, Todd Ward, and Wei jing Zhu. 2002. Bleu: a method for automatic evaluation of machine transla… find
  35. Florent Perronnin, Zeynep Akata, Zaid Harchaoui, and Cordelia Schmid. 2012. Towards good practice in large-scale learning for image classification. In CVPR. Dan Roth and Wen tau Yih. 2004. A linear programming formulation for global inference in natural language tasks. In Proc. of the Annual Confere…
  36. Rion Snow, Brendan O’Connor, Daniel Jurafsky, and Andrew Y. Ng. 2008. Cheap and fast—but is it good?: Evaluating non-expert annotations for natural language tasks. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, EMNLP ’08, pages 254–263, Stroudsburg, PA, USA. As…
  37. Richard Socher, Andrej Karpathy, Quoc V. Le, Christopher D. Manning, and Andrew Y. Ng. 2014. Grounded compositional semantics for finding and describing images with sentences. In Transactions of the Association for Computational Linguistics, pages 207 – 218, April.
  38. Jenine Turner and Eugene Charniak. 2005. Supervised and unsupervised learning for sentence compression. In Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL’05), pages 290–297, Ann Arbor, Michigan, June. Association for Computational Linguistics. find
  39. Jianxiong Xiao, James Hays, Krista A. Ehinger, Aude Oliva, and Antonio Torralba. 2010. Sun database: Large-scale scene recognition from abbey to zoo. In CVPR. find
  40. Yezhou Yang, Ching Teo, Hal Daume III, and Yiannis Aloimonos. 2011. Corpus-guided sentence generation of natural images. In Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, pages 444–454, Edinburgh, Scotland, UK., July. Association for Computational Linguistics… find
  41. Benjamin Z. Yao, Xiong Yang, Liang Lin, Mun Wai Lee, and Song-Chun Zhu. 2010. I2T: Image parsing to text description. Proc. IEEE, 98(8). find
  42. Haonan Yu and Jeffrey Mark Siskind. 2013. Grounded language learning from video described with sentences. In Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 53–63, Sofia, Bulgaria, August. Association for Computational Linguistic… find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/kuznetsova-2014-treetalk-composition-compression-trees-image/