A comprehensive human computation framework: with application to image labeling

ABSTRACT

Image and video labeling is important for computers to understand images and videos and for image and video search. Manual labeling is tedious and costly. Automatically image and video labeling is yet a dream. In this paper, we adopt a Web 2.0 approach to labeling images and videos efficiently: Internet users around the world are mobilized to apply their "common sense" to solve problems that are hard for today's computers, such as labeling images and videos. We first propose a general human computation framework that binds problem providers, Web sites, and Internet users together to solve large-scale common sense problems efficiently and economically. The framework addresses the technical challenges such as preventing a malicious party from attacking others, removing answers from bots, and distilling human answers to produce high-quality solutions to the problems. The framework is then applied to labeling images. Three incremental refinement stages are applied. The first stage collects candidate labels of objects in an image. The second stage refines the candidate labels using multiple choices. Synonymic labels are also correlated in this stage. To prevent bots and lazy humans from selecting all the choices, trap labels are generated automatically and intermixed with the candidate labels. Semantic distance is used to ensure that the selected trap labels would be different enough from the candidate labels so that no human users would mistakenly select the trap labels. The last stage is to ask users to locate an object given a label from a segmented image. The experimental results are also reported in this paper. They indicate that our proposed schemes can successfully remove spurious answers from bots and distill human answers to produce high-quality image labels.

REFERENCES

• 1: Douglas B. Lenat, CYC: a large-scale investment in knowledge infrastructure, Communications of the ACM, v.38 n.11, p.33-38, Nov. 1995 [doi>10.1145/219717.219745]
• 2: Paul A. Boxer, Towards Learning Naive Physics by Visual Observation: Qualitative Spatial Representations, Proceedings of the 14th Australian Joint Conference on Artificial Intelligence: Advances in Artificial Intelligence, p.62-70, December 10-14, 2001
• 3: The Open Mind project. http://www.openmind.org/.
• 4: Luis von Ahn , Laura Dabbish, Labeling images with a computer game, Proceedings of the SIGCHI conference on Human factors in computing systems, p.319-326, April 24-29, 2004, Vienna, Austria [doi>10.1145/985692.985733]
• 5: Luis von Ahn , Ruoran Liu , Manuel Blum, Peekaboom: a game for locating objects in images, Proceedings of the SIGCHI conference on Human Factors in computing systems, April 22-27, 2006, Montréal, Québec, Canada [doi>10.1145/1124772.1124782]
• 6: Luis von Ahn , Mihir Kedia , Manuel Blum, Verbosity: a game for collecting common-sense facts, Proceedings of the SIGCHI conference on Human Factors in computing systems, April 22-27, 2006, Montréal, Québec, Canada [doi>10.1145/1124772.1124784]
• 7: Luis von Ahn , Shiry Ginosar , Mihir Kedia , Ruoran Liu , Manuel Blum, Improving accessibility of the web with a computer game, Proceedings of the SIGCHI conference on Human Factors in computing systems, April 22-27, 2006, Montréal, Québec, Canada [doi>10.1145/1124772.1124785]
• 8: Luis von Ahn, Games with a Purpose, Computer, v.39 n.6, p.92-94, June 2006 [doi>10.1109/MC.2006.196]
• 9: Luis Von Ahn , Manuel Blum, Human computation, Carnegie Mellon University, Pittsburgh, PA, 2005
• 10: Google Image Labeler (Beta, published in August, 2006). http://images.google.com/imagelabeler/.
• 11: Luis von Ahn. CAPTCHA: Using Hard AI Problems For Security. Eurocrypt 2003.
• 12: reCAPTCHA. http://recaptcha.net/.
• 13: Internet Archive. http://www.archive.org/index.php.
• 14: Wikipedia item on Human-Based Computation. http://en.wikipedia.org/wiki/Human-based_computation.
• 15: Google AdSense. https://www.google.com/adsense/.
• 16: A. Kosorukoff. Human Based Genetic Algorithm. IEEE Int. Conf. on Systems, Man, and Cybernetics, vol. 5, pp. 3464--3469, 2001.
• 17: Karl Sims, Artificial evolution for computer graphics, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.319-328, July 1991
• 18: Xian-Sheng Hua , Guo-Jun Qi, Online multi-label active annotation: towards large-scale content-based video search, Proceeding of the 16th ACM international conference on Multimedia, October 26-31, 2008, Vancouver, British Columbia, Canada [doi>10.1145/1459359.1459379]
• 19: J. Ruderman. The Same Origin Policy. http://www.mozilla.org/projects/security/components/same-origin.html.
• 20: Web Hypertext Application Technology Working Group. HTML 5 - Cross-document messaging. http://www.whatwg.org/specs/web-apps/current-work/#crossDocumentMessages.
• 21: Helen J. Wang , Xiaofeng Fan , Jon Howell , Collin Jackson, Protection and communication abstractions for web browsers in MashupOS, Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles, October 14-17, 2007, Stevenson, Washington, USA
• 22: Rui Guo , Bin B. Zhu , Min FENG , Aimin PAN , Bosheng ZHOU, Compoweb: a component-oriented web architecture, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367571]
• 23: Collin Jackson , Helen J. Wang, Subspace: secure cross-domain communication for web mashups, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242655]
• 24: Craig Gentry , Zulfikar Ramzan , Stuart Stubblebine, Secure distributed human computation, Proceedings of the 6th ACM conference on Electronic commerce, p.155-164, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064026]
• 25: George A. Miller, WordNet: a lexical database for English, Communications of the ACM, v.38 n.11, p.39-41, Nov. 1995 [doi>10.1145/219717.219748]
• 26: WordNet::Similarity, a Perl module for computing measures of semantic relatedness based on WordNet. http://www.d.umn.edu/~tpederse/similarity.html.
• 27: EDISON: the Edge Detection and Image Segmentation system. http://www.caip.rutgers.edu/riul/research/code/EDISON/index.html.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Knowledge acquisition

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Retrieval models
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.3 Group and Organization Interfaces
          Subjects: Collaborative computing

General Terms:
Design, Human Factors, Security

Keywords:
common sense problems, distributed knowledge acquisition, human computation, humansense, image labeling