From Picture Processing to Diagrammatics Selected contributions of Zenon Kulpa

Recently I had to prepare several presentations concerning my main contributions to diagrammatics and some related subjects like computer image processing. With a hope that they may be of interest to a wider audience of researchers in diagrammatics, I am making them available on the web, with appropriate explanations. To that I have added some other of my works on these subjects, like preprints of some my papers (when available), information about my two recent books on these subjects and excerpts from one of them. For full list of my publications concerning diagrammatics and related issues, see the list of publications, especially its diagrammatic section. ATTENTION: Some of the items included here are currently available only in Polish. They are marked with the  icon. Fortunately, in most cases they contain small amounts of text but are full of diagrams instead, allowing for general browsing also by those that do not know Polish. In case you would like to read them in English anyway, plesase let me know about that by e-mail . I will consider making English versions of them when the demand will make it worth the effort. The same applies also to availability of some other material, e.g., electronic versions of preprints of some old papers.

§1. Discrete images * §2. Areas and perimeters * §3. Impossible figures §4. What is diagrammatics * §5. Main problems * §6. Interval diagrams

1. Formal model of discrete image procesing This formal model defines discrete pictures and operations on them using mostly the formalism of algebra of relations. A discrete picture is a function from a raster to some finite alphabet of symbols, such that the number of points with the assigned symbol which is different than a special "blank symbol" is bounded. The alphabet can be also a subset of integers, most commonly an initial interval of natural numbers {0, 1, ... , vmax}, with 0 playing the role of the blank symbol. In computer images usually vmax = 2n-1, n > 0). For such number-valued pictures, arithmetic (or modulo vmax+1 arithmetic) operations are extended to operate pixelwise on pictures. A convenient mechanism of specifying local picture operations, both in parallel mode (as in many basic image processing operations) and in sequential mode (as in pictorial grammars) is provided in the formalism. The formalism allows, among others, for compact, yet precise and rigorous specification of operations needed to implement the algorithms of area and perimeter measurement described further on in §2. It is also shown that the popular "mathematical morphology" operations are a simple special case of the local parallel picture operations and can be easily and simply specified with this formalism. Section I.3: Discrete picture processing, pages 1-8 and 14-28 (a PDF file, 1263 KB) of my older book, containing a considerably extended and improved formalism first proposed already in 1980 in my Ph.D. thesis (unpublished). Literature references ocurring in the text are listed in the separate Bibliography (a PDF file, 1059 KB).

§1. Discrete images * §2. Areas and perimeters * §3. Impossible figures §4. What is diagrammatics * §5. Main problems * §6. Interval diagrams

2. Measurement of areas and perimeters Here some of my old but still useful picture analysis ideas are presented. They concern the problem of correct measurement of various geometrical parameters (in particular, areas and perimeters) of objects given to us as discrete computer images on a raster. The computer images are obtained from optical images of the objects as a result of a digitization followed by various object extraction algorithms. Therefore, naive approaches to calculate geometrical parameters of the regions on the resulting image (like various versions of "pixel counting") usually lead to systematic errors because the distortions caused by digitization and object extraction are not taken properly into account. My analysis led to the observation that most of effects of these digitization and extraction processes can be grouped into two classes. One of them leads to the so-called edge-based representation of the object, while the other produces the so-called region-based representation. I have derived the algorithms free of systematic erors for the edge-based representation (using Pick's theorem and Freeman digitization of the "internal" 8-connected contour). I had also shown that the usual "pixel counting" area measurement method and the "between pixels" 4-connected contour perimeter measurement (proposed by other authors) are best suited for the region-based representation. Using a pictorial example, I have shown that when the proper methods are used for a proper representation the results are very near to the correct ones (with some small random error due to digitization noise), while applying the methods to wrong representations leads to severe systematic errors. A recent, mostly diagrammatic and improved presentation of the problem and its solutions: "Pomiary pol i obwodow na obrazach dyskretnych" ["Measurement of areas and perimeters in discrete images," in Polish] (a PDF file, 357 KB). It does not contain formal definitions of the developed algorithms. Addition of them (using the discrete picture model described in §1 above) is planned for later. You can accelerate that with your e-mail requests. Section I.4: Discrete image analysis, pages 1-8 and 29-38 (a PDF file, 918 KB) from my older book, containing an integrated and shortened material from the original papers (see below). Literature references ocurring in the text are listed in the separate Bibliography (a PDF file, 1059 KB). My two old papers on the subject (they cover the whole problem area summarized above only when taken together): 1. Z. Kulpa: Area and perimeter measurement of blobs in discrete binary pictures. Computer Graphics and Image Processing, 6: 434-451, 1977. [An electronic preprint will be prepared on sufficient demand, pester me with your e-mail requests.] 2. Z. Kulpa: More on areas and perimeters of quantized objects. Computer Vision, Graphics and Image Processing, 22: 268-276, 1983 [An electronic preprint will be prepared on sufficient demand, pester me with your e-mail requests.]

§1. Discrete images * §2. Areas and perimeters * §3. Impossible figures §4. What is diagrammatics * §5. Main problems * §6. Interval diagrams

3. Impossible figures Impossible figures are illusions of spatial (three-dimensional) interpretation of flat pictures. The interpretation process is called also monocular depth perception. Investigated by psychology of vision and computer image processing researchers, the figures were used as test pictures for research in visual perception and the development of computer scene analysis programs. Recently I have found that they also constitute good examples of some class of diagrammatic errors - namely so-called impossible cases due to insufficient analogicity (or limited expressiveness) of the representation, see also §5 below. A recent presentation of the general theory of impossible figures: "Figury niemozliwe - zludzenia interpretacji przestrzennej" ["Impossible figures - illusions of spatial interpretation," in Polish]:   Czesc I: Interpretacje i kategorie. [Part I: Interpretations and categories, in Polish.] [a PDF file, 845 KB]   Czesc II: Zastosowania i konstrukcja. [Part II: Applications and construction, in Polish.] [a PDF file, 432 KB] [An English version will be prepared on sufficient demand, pester me with your e-mail requests.] Section I.5: Scene interpretation and understanding, pages 1-8 and 39-48 (a PDF file, 898 KB) from my older book, containing an integrated and shortened material from the two old papers (see below). Literature references ocurring in the text are listed in the separate Bibliography (a PDF file, 1059 KB). My two old papers on the subject: 1. Z. Kulpa: Are impossible figures possible? Signal Processing, 5: 201-220, 1983. [An electronic preprint will be prepared on sufficient demand, pester me with your e-mail requests.] 2. Z. Kulpa: Putting order in the impossible. Perception, 16(2): 201-214, 1987. [Electronic preprint: a PDF file, 237 KB]. A recent paper, showing, among others, the relevance of impossible figures to diagrammatics: 3. Z. Kulpa: Self-consistency, imprecision, and impossible cases in diagrammatic representations. Machine GRAPHICS & VISION, 12(1): 147-160, 2003. [Electronic preprint: a PDF file, 366 KB], see also §5 below. More about impossible figures can be found on the Impossible World site.

§1. Discrete images * §2. Areas and perimeters * §3. Impossible figures §4. What is diagrammatics * §5. Main problems * §6. Interval diagrams

4. What is diagrammatics? The question above is often asked by people confronted by this new discipline. To answer that question I have prepared a short presentation as well as a series of semi-popular articles. Presentation sheets of the lecture: "What is diagrammatics?" (a PDF file, 302 KB). A series of semi-popular articles on various aspects of diagrammatics. My older survey paper: Z. Kulpa, Diagrammatic representation and reasoning. Machine GRAPHICS & VISION, Vol. 3, Nos. 1/2, 1994, 77-103. [PDF file, 431KB]

§1. Discrete images * §2. Areas and perimeters * §3. Impossible figures §4. What is diagrammatics * §5. Main problems * §6. Interval diagrams

5. Main problems: Particularity and imprecision of diagrams Diagrammatic reasoning is often blamed by its critics as unreliable, leading easily to various errors. This situation is caused mostly by the lack of proper rules and guidelines for reliable reasoning with diagrams. Considerable effort has been expended on making reasoning with formulae rigorous, causing it much less error-prone. Since diagrams and diagrammatic reasoning differ significantly from formulae and corresponding propositional reasoning, these rules usually do not transfer directly to diagrams. Moreover, serious attempts to find rigorous ways of diagrammatic reasoning started only recently. There are many sources of diagrammatic errors, still poorly unerstood, with few, if any, systematic investigations and reliable methods of avoiding these errors. It seems that there are two main groups of problems with diagramatic reasoning, responsible for most of the serious diagrammatic reasoning errors reported in the literature. They are differently called and formulated by different authors. I propose to call these groups the universal quantification problem and the existential quantification problem. The first of them is usually known under the names of generalization problem or diagram particularity. This covers also the questions of representation of variables and representation of quantifiers in diagrams. The second group of problems is better known under the name imprecision of diagrams. Another aspect of this problem is called diagram perception problem. Closely related problems of impossible cases (including impossible figures, see §3 above) and limited expressiveness also belong here. A recent presentation of the problem and some its solutions: "Nieprecyzyjnosc i niemozliwe przypadki we wnioskowaniu diagramowym" ["Imprecision and imposible cases in diagrammatic reasoning," in Polish] (a PDF file, 482 KB). [An English version will be prepared on sufficient demand, pester me with your e-mail requests.] My older paper on the subject: 1. Z. Kulpa: Self-consistency, imprecision, and impossible cases in diagrammatic representations. Machine GRAPHICS & VISION, 12(1): 147-160, 2003. [Electronic preprint: a PDF file, 366 KB]. My recent paper on main causes of problems with diagrammatic reasoning, especially the generalization problem (particularity), with a short section on imprecision too: 2. Z. Kulpa: Main problems of diagrammatic reasoning. Part I: The generalization problem. Foundations of Science, 14(1-2): 75-96, 2009. [Electronic preprint: a PDF file, 390 KB]. My planned paper on main causes of problems with diagrammatic reasoning, especially the imprecision (impossible cases) problem: 3. Z. Kulpa: Main problems of diagrammatic reasoning. Part II: The imprecision problem. (In preparation.) [Will appear here when ready.]

§1. Discrete images * §2. Areas and perimeters * §3. Impossible figures §4. What is diagrammatics * §5. Main problems * §6. Interval diagrams

6. Diagrammatic interval analysis My main work in recent years was the development of the practical system of diagrammatic representation for interval algebra and computations. Various parts of the system and its applications were described in several journal papers and conference proceedings, see the list of my papers (diagrammatics section). Interval computations concern the theory and use in numerical computation of the notion of intervals and arithmetic calculations with them. The use of interval computations is gaining popularity because they allow for calculation of quaranteed bounds (called also reliable computations), as they take into account all possible sources of error, from imprecise data to rounding errors during computer calculations. Albeit various simple diagrams appeared in the literature of the field, they played no significant role in its development. This stays in marked contrast to the development of complex number theory and analysis long ago, where the diagrammatic representational system based on the complex plane diagram (Argand diagram) played an important role in the acceptance of complex numbers and in the development of their theory. The diagrammatic system for interval algebra is based on the diagrammatic representation of the space of intervals, called an MR-diagram, where intervals are represented as two-dimensional points in the midpoint-radius coordinate system. The system has been applied to several subareas of interval algebra, namely interval relations, interval arithmetic, and interval linear equations. To meet specific needs of these subareas, additional diagrammatic tools have been developed and used. Z. Kulpa: From Picture Processing to Interval Diagrams. IFTR PAS Reports (ISSN 0208-5658), No. 4/2003, Warsaw 2003 (ix+313 pp., 152+12 figs, 16 tables). Chapter III of the report contains the first integrated account of the system of diagrammatic representation for interval algebra and computations. Chapter II contains an introduction to diagrammatics (partially obsolete). Relevant fragments of Chapter I are available online through this page, see §1 (discrete images), §2 (areas and perimeters) and §3 (impossible figures). Z. Kulpa: Diagrammatic Interval Analysis with Applications. IFTR PAS Reports (ISSN 0208-5658), No. 1/2006, Warsaw 2006 (xvi+232 pp., 143+4 figs., 13+10 tables). The report contains updated and extended description of the diagrammatic system, with some applications. It constitutes a basis for the forthcoming book on the subject. A recent presentation of selected issues presented in the second of the above reports (Diagrammatic Interval Analysis with Applications):   Czesc I: Algebra przedzialow [Part I: Interval algebra] [a PDF file, 2.3 MB].   Czesc II: Liniowe rownania przedzialowe [Part II: Linear interval equations] [a PDF file, 1.76 MB]. [An English version will be prepared on sufficient demand, pester me with your e-mail requests.]

§1. Discrete images * §2. Areas and perimeters * §3. Impossible figures §4. What is diagrammatics * §5. Main problems * §6. Interval diagrams

See also:

Professional interests

Selected publications

Professional biography

Qualitative Analysis

Diagrammatics

Intervals

Personal interests

my Institute

my Department

my Home