PERBANDINGAN ALGORITMA SHORTEST PATH DALAM PEMROSESAN CITRA DIGITAL SEAM CARVING

Florentinus Alvin Sebastian, R. Gunawan Santosa, Theresia Herlina R.

Abstract


Seam carving is a method of content aware image resizing. As solutions shortest path algorithms are used to find images seams. Seam is a horizontal or vertical path of an image that has minimum energy. There are two (2) shortest path algorithms that will be discussed in this paper. This paper contains the results of shortest path algorithms comparison between Dijkstra and Directed Acyclic Graph to see which one is better than another in case of efficiency. The precomputed and recomputed methods will be compared to find the more efficient method for executing the seam carving transformation. A web application has been built for this purpose. This web app is capable of transforming image size with seam carving method. The complexity of Dijkstra and Acyclic will be compared to find which one is better. The result is Dijkstra has been won, with the O(4V) with Acyclicis O(5V). The use of precomputed and recomputed is evaluated by the conditions. If the preparation is evaluated then recomputed is more efficient, but if the preparation is not evaluated then the precomputed method is the better one and has faster performance. 


Keywords


seam carving, shortest path, minimum energy, gradient magnitude, perbandingan algoritma, Dijkstra, acyclic

Full Text:

PDF

References


Avidan, S., & Shamir, A. (2007). Seam Carving for Content-Aware Image Resizing.

Danziger, P. (n.d.). Big O Notation. Retrieved January 19, 2015, from Department of Computer Science - Ryerson University: http://www.scs.ryerson.ca/~mth110/Handouts/PD/bigO.pdf

David, J. (2005). Image Gradients . Retrieved 4 1, 2014, from http://www.cs.umd.edu/: http://www.cs.umd.edu/~djacobs/CMSC426/ImageGradients.pdf

Even, S. (1979). Graph Algorithms. Rockville, Maryland: Computer Science.

Gacs, P., & Lovasz, L. (1999). Complexity of Algorithm Lecture Notes.

Low, A. (1991). Introductory Computer Vision and Image Processing. Singapore: McGraw- Hill Book Company (UK) Limited.

MIT. (n.d.). http://web.mit.edu/16.070/www/lecture/big_o.pdf. Retrieved January 19, 2015, from MIT - Massachusetts Institute of Technology:

http://web.mit.edu/16.070/www/lecture/big_o.pdf

Sarkar, A., Nataraj, L., & Manjunath, B. S. (2009). Detection of Seam Carving and Localization of Seam. Proceedings of the 11th ACM workshop on Multimedia and Security, 107-116.

Sedgewick, R., & Wayne, K. (2011). Algorithms. Massachusetts: Pearson Education, Inc. Teuber, J. (1993). Digital Image Processing. Hempstead: Prentice Hall International (UK) Ltd.

Thilagam, K., & Karthikeyan, S. (2012). Optimized Image Resizing using Piecewise Seam Carving. International Journal of Computer Applications, 24-30.




DOI: http://dx.doi.org/10.21460/inf.2015.112.449

Refbacks

  • There are currently no refbacks.


Bookmark and Share