Automatic programming of binary morphological machines by PAC learning

Junior Barrera; Nina Sumiko Tomita; Flavio Soares Correa da Silva; Routo Terada

doi:10.1117/12.216356

11 August 1995 Automatic programming of binary morphological machines by PAC learning

Junior Barrera, Nina Sumiko Tomita, Flavio Soares Correa da Silva, Routo Terada

Proceedings Volume 2568, Neural, Morphological, and Stochastic Methods in Image and Signal Processing; (1995) https://doi.org/10.1117/12.216356
Event: SPIE's 1995 International Symposium on Optical Science, Engineering, and Instrumentation, 1995, San Diego, CA, United States

Abstract

Binary image analysis problems can be solved by set operators implemented as programs for a binary morphological machine (BMM). This is a very general and powerful approach to solve this type of problem. However, the design of these programs is not a task manageable by nonexperts on mathematical morphology. In order to overcome this difficulty we have worked on tools that help users describe their goals at higher levels of abstraction and to translate them into BMM programs. Some of these tools are based on the representation of the goals of the user as a collection of input-output pairs of images and the estimation of the target operator from these data. PAC learning is a well suited methodology for this task, since in this theory 'concepts' are represented as Boolean functions that are equivalent to set operators. In order to apply this technique in practice we must have efficient learning algorithms. In this paper we introduce two PAC learning algorithms, both are based on the minimal representation of Boolean functions, which has a straightforward translation to the canonical decomposition of set operators. The first algorithm is based on the classical Quine-McCluskey algorithm for the simplification of Boolean functions, and the second one is based on a new idea for the construction of Boolean functions: the incremental splitting of intervals. We also present a comparative complexity analysis of the two algorithms. Finally, we give some application examples.

Citation Download Citation

Junior Barrera, Nina Sumiko Tomita, Flavio Soares Correa da Silva, and Routo Terada "Automatic programming of binary morphological machines by PAC learning", Proc. SPIE 2568, Neural, Morphological, and Stochastic Methods in Image and Signal Processing, (11 August 1995); https://doi.org/10.1117/12.216356

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available