Mixed Heuristic Search for Sketch Prediction on Chemical Structure Drawing

Aus de_evolutionary_art_org
Wechseln zu: Navigation, Suche

Reference

Bo Kang, Hao Hu and Joseph LaViola Jr.: Mixed Heuristic Search for Sketch Prediction on Chemical Structure Drawing. In: Computational Aesthetics 2014.

DOI

http://dx.doi.org/10.1145/2630407.2630408

Abstract

Sketching is a natural way to input chemical structures that can be used to query information from a large chemical structure database. Based on a user's incomplete sketch of a chemical structure, sketch prediction becomes a challenging problem not only due to arbitrary drawings orders among users but also similarities among chemical structure layouts. In this paper, we present a graph-based approach to handle the sketch prediction problem. We use multisets as the data representation of hand-drawn chemical structures and create an undirected graph to handle data in all multisets. This approach transforms the sketch prediction problem into a search problem to find a hamiltonian path in the corresponding sub-graph with polynomial time complexity. We introduce mixed heuristics to guide the search procedure. Through an initial experiment on a hand-drawn chemical structure dataset, we demonstrate that in comparison with a baseline method, the proposed approach improves the prediction accuracy and efficiently predicts chemical structures from only partially sketched drawings.

Extended Abstract

Bibtex

@inproceedings{Kang:2014:MHS:2630407.2630408,
author = {Kang, Bo and Hu, Hao and LaViola,Jr., Joseph J.},
title = {Mixed Heuristic Search for Sketch Prediction on Chemical Structure Drawing},
booktitle = {Proceedings of the 4th Joint Symposium on Computational Aesthetics, Non-Photorealistic Animation and Rendering, and Sketch-Based Interfaces and Modeling},
series = {SBIM '14},
year = {2014},
isbn = {978-1-4503-3018-3},
location = {Vancouver, British Columbia, Canada},
pages = {27--34},
numpages = {8},
url = {http://doi.acm.org/10.1145/2630407.2630408 http://de.evo-art.org/index.php?title=Mixed_Heuristic_Search_for_Sketch_Prediction_on_Chemical_Structure_Drawing },
doi = {10.1145/2630407.2630408},
acmid = {2630408},
publisher = {ACM},
address = {New York, NY, USA},
keywords = {Hamiltonian path, chemical structure sketch prediction, graph search, heuristics},
}

Used References

Gennaro Costagliola , Mattia De Rosa , Vittorio Fuccella, Technical Section: Recognition and autocompletion of partially drawn symbols by using polar histograms as spatial relation descriptors, Computers and Graphics, 39, p.101-116, April, 2014 http://dx.doi.org/10.1016/j.cag.2013.12.003

Hal Daumé, Iii , John Langford , Daniel Marcu, Search-based structured prediction, Machine Learning, v.75 n.3, p.297-325, June 2009 http://dx.doi.org/10.1007/s10994-009-5106-x

Doppa, J. R., Fern, A., and Tadepalli, P. 2013. Hc-search: Learning heuristics and cost functions for structured prediction. In AAAI, AAAI Press, M. desJardins and M. L. Littman, Eds.

Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979 http://dl.acm.org/citation.cfm?id=578533&CFID=588525319&CFTOKEN=29804931

Leslie Gennari , Levent Burak Kara , Thomas F. Stahovich , Kenji Shimada, Combining geometry and domain knowledge to interpret hand-drawn diagrams, Computers and Graphics, v.29 n.4, p.547-562, August, 2005 http://dx.doi.org/10.1016/j.cag.2005.05.007

Tracy Hammond , Randall Davis, Automatically transforming symbolic shape descriptions for use in sketch recognition, Proceedings of the 19th national conference on Artifical intelligence, p.450-456, July 25-29, 2004, San Jose, California http://dl.acm.org/citation.cfm?id=1597222&CFID=588525319&CFTOKEN=29804931

Joseph J. LaViola Jr. , Robert C. Zeleznik, A Practical Approach for Writer-Dependent Symbol Recognition Using a Writer-Independent Symbol Recognizer, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.29 n.11, p.1917-1926, November 2007 http://dx.doi.org/10.1109/TPAMI.2007.1109

J. Mas , G. Sanchez , J. Llados , B. Lamiroy, An Incremental On-line Parsing Algorithm for Recognizing Sketching Diagrams, Proceedings of the Ninth International Conference on Document Analysis and Recognition, p.452-456, September 23-26, 2007 http://dl.acm.org/citation.cfm?id=1304767&CFID=588525319&CFTOKEN=29804931

Tom Y. Ouyang , Randall Davis, Recognition of hand drawn chemical diagrams, Proceedings of the 22nd national conference on Artificial intelligence, p.846-851, July 22-26, 2007, Vancouver, British Columbia, Canada http://dl.acm.org/citation.cfm?id=1619781&CFID=588525319&CFTOKEN=29804931

Tom Y. Ouyang , Randall Davis, ChemInk: a natural real-time recognition system for chemical drawings, Proceedings of the 16th international conference on Intelligent user interfaces, February 13-16, 2011, Palo Alto, CA, USA http://doi.acm.org/10.1145/1943403.1943444

Peterson, E. J., Stahovich, T. F., Doi, E., and Alvarado, C. 2010. Grouping strokes into shapes in hand-drawn diagrams. In AAAI, AAAI Press, M. Fox and D. Poole, Eds.

Lawrence R. Rabiner, A tutorial on hidden Markov models and selected applications in speech recognition, Readings in speech recognition, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990 http://dl.acm.org/citation.cfm?id=108253&CFID=588525319&CFTOKEN=29804931

Sadawi, N. M., Sexton, A. P., and Sorge, V. 2012. Chemical structure recognition: a rule-based approach. In DRR, SPIE, C. Viard-Gaudin and R. Zanibbi, Eds., vol. 8297 of SPIE Proceedings.

Tevfik Metin Sezgin , Randall Davis, HMM-based efficient sketch recognition, Proceedings of the 10th international conference on Intelligent user interfaces, January 10-13, 2005, San Diego, California, USA http://doi.acm.org/10.1145/1040830.1040899

Shatabda, S., Newton, M. A. H., and Sattar, A. 2013. Mixed heuristic local search for protein structure prediction. In AAAI, AAAI Press, M. desJardins and M. L. Littman, Eds.

Caglar Tirkaz , Berrin Yanikoglu , T. Metin Sezgin, Sketched symbol recognition with auto-completion, Pattern Recognition, v.45 n.11, p.3926-3937, November, 2012 http://dx.doi.org/10.1016/j.patcog.2012.04.026

Radu-Daniel Vatavu , Lisa Anthony , Jacob O. Wobbrock, Gestures as point clouds: a $P recognizer for user interface prototypes, Proceedings of the 14th ACM international conference on Multimodal interaction, October 22-26, 2012, Santa Monica, California, USA http://doi.acm.org/10.1145/2388676.2388732

A. Wolin , B. Eoff , T. Hammond, ShortStraw: a simple and effective corner finder for polylines, Proceedings of the Fifth Eurographics conference on Sketch-Based Interfaces and Modeling, June 11-13, 2008, Annecy, France http://dx.doi.org/10.2312/SBM/SBM08/033-040

Yiyan Xiong , Joseph J. LaViola, Jr., Revisiting ShortStraw: improving corner finding in sketch-based interfaces, Proceedings of the 6th Eurographics Symposium on Sketch-Based Interfaces and Modeling, August 01-02, 2009, New Orleans, Louisiana http://doi.acm.org/10.1145/1572741.1572759


Links

Full Text

[extern file]

intern file

Sonstige Links