Home   >   CSC-OpenAccess Library   >    Manuscript Information
Role Model of Graph Coloring Application in Labeled 2D Line Drawing Object
A. A. Samah, M. Z. Matondang, H. Haron, H. A. Majid, N. K. Ibrahim
Pages - 82 - 91     |    Revised - 01-11-2011     |    Published - 15-12-2011
Volume - 2   Issue - 3    |    Publication Date - November / December 2011  Table of Contents
MORE INFORMATION
KEYWORDS
Engineering Sketch, Line Labeling, Graph Coloring
ABSTRACT
Several researches had worked on the development of sketch interpreters. However, very few of them gave a complete cycle of the sketch interpreter which can be used to transform an engineering sketch to a valid solid object. In this paper, a framework of the complete cycle of the sketch interpreter is presented. The discussion in this paper will stress on the usage of line labeling and graph coloring application in the validation of two dimensional (2D) line drawing phase. Both applications are needed to determine whether the given 2D line drawing represent possible or impossible object. In 2008, previous work by Matondang et al., has used line labeling algorithm to validate several 2D line drawings. However, the result shows that line labeling algorithm is not sufficient, as the algorithm does not have a validation technique for the result. Therefore, in this research study, it is going to be shown that if a 2D line drawing is valid as a possible object by using the line labeling algorithm, then it can be colored using graph coloring concept with a determine-able minimum numbers of color needed. This is equal in vice versa. The expected output from this phase is a valid-labeled of 2D line drawing with different colors at each edge and ready for the reconstruction phase. As a preliminary result, a high programming language MATLAB R2009a and several primitive 2D line drawings has been used and presented in this paper to test the graph coloring concept in labeled 2D line drawing.
CITED BY (1)  
1 Prasanna, N. L., & Sudhakar, N. (2015). Algorithm for Edge Antimagic Labeling for Specific Classes of Graphs.
1 Google Scholar 
2 CiteSeerX 
3 refSeek 
4 Scribd 
5 SlideShare 
6 PdfSR 
Baase S. and Van Gelder A., Computer Algorithms: Introduction to Design and Analysis, 3rd Edn., Addison Wesley. 2000.
Clowes M. B. “On seeing things,” Artificial Intelligent, vol. 2, pp. 79-116, 1971.
Cooper M. C., “Constraint Between Distant Lines in the Labeling of Line Drawings of Polyhedral Scene,” Intl. Journal of Computer Vision. vol. 73, no. 2, ACM Portal, pp. 195- 212, 2007.
Cowan T. M., “Organizing the Properties of Impossible Figures,” Perception, vol. 2, pp. 41-56, 1977.
Dobrolowski T., Dereniowski D., and Kuszner L., Koala Graph Coloring Library: An Open Graph Coloring Library for Real World Applications, IT, Gdansk, Poland, May 2008.
Gaceb D., Eglin V., Lebourgeois F., and Emptoz H., “Application of Graph Coloring in Physical Layout Segmentation,” IEEE 19th Intl. Conf. on Pattern Recognition (ICPR 2008), pp. 1-4, 2008.
Grimstead I. J., Interactive Sketch Input of Boundary Representation Solid Models, PhD Thesis, Univ. of Cardiff, UK. 1997.
Grimstead J. and Martin R. R., “Creating Solid Model From Single 2D Sketches”. Proceedings Third Symp. On Solid Modeling Applications. ACM SIGGRAPH. pp. 233- 337, 1995.
Haron H., Shamsuddin S. M. and Mohamed D., “Chain Code Algorithm in Deriving Tjunction and Region of a Freehand Skecth,” Jurnal Teknologi. vol. 40D, pp. 25-36, 2004.
Huffman D. A. “Impossible Object as Nonsense Sentences,” Machine Intelligence. Newyork: American Elsevier, vol. 6, pp. 295-323, 1971.
Iturriaga-Velazquez C. C., Map Labeling Problems,”PhD Thesis, University of Waterloo, Ontorio: Canada, 1999.
Jenkins D. L. and R. R. Martin, “The importance of Free-hand Sketching in Conceptual Design: Automatic Sketch Input,” In T.K. High and L. A. Stauffe
Jensen T. R. and Toft, B. Graph Coloring Problems. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons Inc., New York. A Wiley Interscience Publication. 1995.
Malik J, “Interpreting Line Drawings of Curved Objects,” Int'l J. Computer Vision, vol. 1, pp. 73-103, 1987.
Marx D., “Graph Coloring Problems and Their Applications in Schedulling,” Periodica of Polytechnica Ser. El. Eng. vol. 489, no. 1, pp. 11-16, 2004.
Matondang M. Z., Mardzuki, S. and Haron, H., “Transformation of engineering sketch to valid solid object,” Proc. of Intl. Conf. of The 9th Asia Pacific Industrial Engineering & Management Systems (APIEMS 08) Conference and The 11th Asia Pacific Regional Meeting of International Foundation for Production Research, Dec. 2008, pp. 2707– 2715, 2008.
Matondang M. Z., Samah A. A., Mardzuki S., Haron H., Majid H. A. and Ibrahim N. K., “A Hybrid Framework for Validation of Two Dimensional Line Drawing based on Line Labeling and Graph Coloring Algorithm”. 2010 International Conference on Intelligent Network and Computing (ICINC 2010). Kuala Lumpur, Malaysia. 26 - 28 November, 2010. Edt. Ms. Zhang Yushu. IEEE Catalog Number: CFP1076K-PRT. ISBN: 978-1- 4244-8270-2. Institute of Electrical and Electronics Engineers, Inc. vol. 2. pp. V2-49, 2010.
Myers R. and Hancock E. R., “Genetic Algorithm Parameter Sets for Line Labeling,” Pettern Recognition Letters, ACM Portal, vol. 18. No. 11-13, pp. 1363-1371, 1997.
Redl T.A., University Timetabling Via Graph Coloring: an alternative approach, University of Houston, Houston, 2007.
Robinson L. A., Graph Theory for the Middle School, Master Thesis. Faculty of the Department of Mathematics. East Tennessee State University. UMI Number: 1436267. 2006.
Salem G. J. and Young T. Y., “Interpreting Line Drawings with Higher Order Neural Network,” IEEE Intl. Joint Conf. on Neural Network (IJCNN 91), vol. 1, pp. I-713 – I-721, 1991.
Sugihara K., Machine Interpretation of Line Drawings. Cambridge, Massachusetts: MIT Press. 1986.
Varley P. A. C. and Martin R. R., “A System for Constructing Boundary Representation Solid Models from a Two-Dimensional Sketch,” IEEE Proc. Geometri Modelling and Processing, pp. 13-32, 2000.
Varley P. A. C. and Martin R. R., “Estimating Depth from Line Drawing. In Edt. K.Lee and Patrikalakis”. Proc. 7th ACM Symposium on Solid Modeling and Applications, SM’02. ACM Press. pp. 180-191, 2002.
Varley P. A. C., Martin R. R. and Suzuki H., “Making the Most of using Depth Reasoning to Label Line Drawings of Engineering Objects,” ACM Symposium on Solid Modeling and Application, pp. 13-32, 2004.
Waltz D. L. Understanding Line Drawings of Scenes with Shadows, In P. Winston, editor, The Physicology of Computer Vision, Mc Graw Hill, Newyork, pp.19-91, 197
Dr. A. A. Samah
- Malaysia
Mr. M. Z. Matondang
- Malaysia
muhammadzaini@gmail.com
Associate Professor H. Haron
- Malaysia
Mr. H. A. Majid
- Malaysia
Miss N. K. Ibrahim
- Malaysia


CREATE AUTHOR ACCOUNT
 
LAUNCH YOUR SPECIAL ISSUE
View all special issues >>
 
PUBLICATION VIDEOS