More Web Proxy on the site http://driver.im/

article

Free access

An application of heuristic search methods to edge and contour detection

Author:

Alberto MartelliAuthors Info & Claims

Communications of the ACM, Volume 19, Issue 2

Pages 73 - 83

https://doi.org/10.1145/359997.360004

Published: 01 February 1976 Publication History

Abstract

This paper presents a method for detecting edges and contours in noisy pictures. The properties of an edge are embedded in a figure of merit and the edge detection problem becomes the problem of minimizing the given figure of merit. This problem can be represented as a shortest path problem on a graph and can be solved using well-known graph search algorithms. The relations between this representation of the minimization problem and a dynamic programming approach are discussed, showing that the graph search method can lead to substantial improvements in computing time. Moreover, if heuristic search methods are used, the computing time will depend on the amount of noise in the picture. Some experimental results are given; these show how various information about the shape of the contour of an object can be embedded in the figure of merit, thus allowing the extraction of contours from noisy pictures and the separation of touching objects.

References

[1]

Rosenfeld, A. Picture Processing by Computer. Academic Press, New York, 1969.

Digital Library

[2]

Hueckel, M.H. A local visual operator which recognizes edges and lines. J. ACM 20, 4 (Oct. 1973), 634-647.

Digital Library

[3]

Rosenfeld, A., Thurston, M., and Lee, Y.-H. Edge and curve detection: further experiments. IEEE Trans. on Computers C-21, 7 (July 1972), 677-715.

Digital Library

[4]

Pingle, K.K., and Tenenbaum, J.M. An accommodating edge follower. In Proc. 2nd Int. Joint Conf. on Artificial Intelligence, London, Sept. 1971, pp. 1-7.

Digital Library

[5]

Kovalewsky, V.A. Sequential optimization in pattern recognition and pattern description. Proc. IFIP Congress, 68, North- Holland Pub. Co., Amsterdam, 1968 pp. 146-151.

[6]

Montanari, U. On the optimal detection of curves in noisy pictures. Comm. ACM 14, 5 (May 1971), 335-345.

Digital Library

[7]

Martelli, A., and Montanari, U. Optimal smoothing in picture processing: An application to fingerprints. Proc. IFIP Congress 71, North-Holland Pub. Co., Amsterdam, 1971 pp. 173-178.

[8]

Fischler, M.A., and Elschlager, R.A. The representation and matching of pictorial structures. IEEE Trans. on Computers C-22, 1 (Jan. 1973), 67-92.

Digital Library

[9]

Martelli, A. Edge detection using heuristic search methods. Computer Graphics and Image Processing 1, 2 (Aug. 1972), 169- 182.

[10]

Martelli, A. Contour detection in noisy pictures using heuristic search methods. Proc. 1st Int. Joint Conf. on Pattern Recognition, Washington, 1973, pp. 375-388.

[11]

Ramer, U. Computer edge extraction from photographs of curved objects. Ph,D. dissertation, Tech. Rep. CRL-34, New York U., Dec, 1973.

Digital Library

[12]

Ballard, D.H., and Sklansky, J. Hierarchic recognition of tumors in chest radiographs. Proc. Second Int. Joint Conf. on Pattern Recognition, Copenhagen, August 1974, pp. 258-263.

[13]

Kaufmann, A., and Cruon, R. Dynamic Programming. Academic Press, New York, 1967.

[14]

Bellman, R., and Dreyfus, S. Applied Dynamic Programming. Princeton U. Press, Princeton, N.J., 1962.

[15]

Nilsson, N.J. Problem-Solving Methods in Artificial bttelligence. McGraw-Hill, New York, 1971.

Digital Library

[16]

Hart, P., Nilsson, N., and Raphael, B. A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. on System Science and Cybernetics SSC-4, 2 (July 1968), 100-107.

[17]

Dijkstra, E. A note on two problems in connection with graphs. Numer. Math. 1 (1959), 269-271.

Digital Library

[18]

Bertel, U., and Brioschi, F. Nonserial Dynamic Programming. Academic Press, New York, 1973.

Digital Library

[19]

Martelli, A., and Montanari U. Nonserial Dynamic Programming: on the optimal strategy of variable elimination for the rectangular lattice. J. Math. Analysis Appl. 40, 1 (Oct. 1972), 226-242.

[20]

Martelli, A., and Montanari, U. Additive AND/OR graphs. Proc. 3rd Int. Joint Conf. on Artificial Intelligence, Stanford, Calif. 1973, pp. 1-11.

Digital Library

[21]

Pingle, K.K. Visual perception by a computer. In Automatic Interpretation and Classification of Images, A. Grasselli (Ed.), Academic Press, New York, 1969, pp. 277-284.

Cited By

Riedel MGrauwin SLaffay PReniaud C(2023)La confiance : nouvel horizon social ?La confiance : nouvel horizon social ?10.3917/chaso.obert.2023.01.0119(119-139)Online publication date: 30-Sep-2023
https://doi.org/10.3917/chaso.obert.2023.01.0119
Maglogiannis IKarpouzis KWallace MMaglogiannis IKarpouzis KWallace M(2022)Signal Processing for Telemedicine ApplicationsImage and Signal Processing for Networked eHealth Applications10.1007/978-3-031-01609-7_2(3-9)Online publication date: 8-Mar-2022
https://doi.org/10.1007/978-3-031-01609-7_2
Senapati DSarkar AKarfa C(2021)HMDS: A Makespan Minimizing DAG Scheduler for Heterogeneous Distributed SystemsACM Transactions on Embedded Computing Systems10.1145/347703720:5s(1-26)Online publication date: 17-Sep-2021
https://dl.acm.org/doi/10.1145/3477037
Show More Cited By

An application of heuristic search methods to edge and contour detection
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

An experimental comparison of superpixels detection methods for contour detection

Recently, many superpixels detection methods have been proposed and used in various applications. We are interested in which method is more suitable for the application of contour detection. In this paper, superpixels are evaluated on BSDS500 dataset in ...
Contour Detection and Hierarchical Image Segmentation

This paper investigates two fundamental problems in computer vision: contour detection and image segmentation. We present state-of-the-art algorithms for both of these tasks. Our contour detector combines multiple local cues into a globalization ...
Efficient local and global contour detection based on superpixels

Superpixels are applied to contour detection to improve the efficiency.Based on superpixels, an efficient local contour detection method is introduced.Based on superpixels, an efficient global contour detection method is introduced. In this paper, two ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Communications of the ACM

Communications of the ACM Volume 19, Issue 2

Feb. 1976

53 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/359997

Editor:
Robert L. Ashenhurst
Univ. of Chicago, Chicago, IL

Issue’s Table of Contents

Copyright © 1976 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 February 1976

Published in CACM Volume 19, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

193
Total Citations
View Citations
2,050
Total Downloads

Downloads (Last 12 months)224
Downloads (Last 6 weeks)63

Reflects downloads up to 25 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Riedel MGrauwin SLaffay PReniaud C(2023)La confiance : nouvel horizon social ?La confiance : nouvel horizon social ?10.3917/chaso.obert.2023.01.0119(119-139)Online publication date: 30-Sep-2023
https://doi.org/10.3917/chaso.obert.2023.01.0119
Maglogiannis IKarpouzis KWallace MMaglogiannis IKarpouzis KWallace M(2022)Signal Processing for Telemedicine ApplicationsImage and Signal Processing for Networked eHealth Applications10.1007/978-3-031-01609-7_2(3-9)Online publication date: 8-Mar-2022
https://doi.org/10.1007/978-3-031-01609-7_2
Senapati DSarkar AKarfa C(2021)HMDS: A Makespan Minimizing DAG Scheduler for Heterogeneous Distributed SystemsACM Transactions on Embedded Computing Systems10.1145/347703720:5s(1-26)Online publication date: 17-Sep-2021
https://dl.acm.org/doi/10.1145/3477037
Asim MShah MAli MNaseem R(2020)Decision Support System for Dental Clinics: A Systematic Literature Review ProtocolIntelligent Technologies and Applications10.1007/978-981-15-5232-8_22(250-257)Online publication date: 9-May-2020
https://doi.org/10.1007/978-981-15-5232-8_22
Farreny H(2020)Heuristically Ordered Search in State GraphsA Guided Tour of Artificial Intelligence Research10.1007/978-3-030-06167-8_1(1-26)Online publication date: 8-May-2020
https://doi.org/10.1007/978-3-030-06167-8_1
Imran ALi JPei YYang JWang Q(2019)Comparative Analysis of Vessel Segmentation Techniques in Retinal ImagesIEEE Access10.1109/ACCESS.2019.29359127(114862-114887)Online publication date: 2019
https://doi.org/10.1109/ACCESS.2019.2935912
Yang JXie YLiu LXia BCao ZGuo C(2018)Automated Dental Image Analysis by Deep Learning on Small Dataset2018 IEEE 42nd Annual Computer Software and Applications Conference (COMPSAC)10.1109/COMPSAC.2018.00076(492-497)Online publication date: Jul-2018
https://doi.org/10.1109/COMPSAC.2018.00076
Condori MMansilla LMiranda P(2017)Bandeirantes: A Graph-Based Approach for Curve Tracing and Boundary TrackingMathematical Morphology and Its Applications to Signal and Image Processing10.1007/978-3-319-57240-6_8(95-106)Online publication date: 12-Apr-2017
https://doi.org/10.1007/978-3-319-57240-6_8
Singhal PVerma A(2016)A review on graph based segmentation techniques2016 10th International Conference on Intelligent Systems and Control (ISCO)10.1109/ISCO.2016.7727008(1-6)Online publication date: Jan-2016
https://doi.org/10.1109/ISCO.2016.7727008
Vadlamudi SAine SChakrabarti P(2016)Anytime pack searchNatural Computing: an international journal10.1007/s11047-015-9490-915:3(395-414)Online publication date: 1-Sep-2016
https://dl.acm.org/doi/10.1007/s11047-015-9490-9
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents