Measuring the sizes of concavities

A concavity in a region R is a simply-connected region S whose boundary is composed of a boundary B to R and the chord K of B. Three measures of the size of S are studied: the area of S; the maximum distance of B from K; and the maximum distance of K from B. Relationships among these measures are established. It is shown that only the last measure guarantees (when its value is high) that S contains a large ‘block’ of the complement of R, so that S is ‘detectable’ if R is coarsely digitized. Similarly, if the last measure is large relative to the length of K, S is ‘locally detectable’ if R is digitized to a suitable degree of coarseness. Local detectability of S at a coarse level of digitization corresponds, intuitively, to S being visually conspicuous.     

Some notes on digital triangles

This note discusses some simple properties of digital triangles, whose vertices are lattice points and whose side lengths are measured using city block distance. Many of the familiar theorems of geometry break down in this situation.     

Multi-resolution relaxation

Several types of iterative methods can be used to segment the pixels in an image into light and dark regions; these include “relaxation” methods of probability adjustment and steepest-descent methods of cost function minimization. Conventionally, these methods operate on the image at a single resolution. This paper investigates the possibility of using these approaches at two (or more) resolutions in order to reduce their computational cost—e.g. first obtain an approximate solution by iterating at low resolution, then refine the solution using a few iterations at high resolution.     

Two heads are better than one

A class of multihead automata in which the heads operate in parallel is defined. Deterministic two-head automata are described that accept the languages aⁿbⁿ (or, more generally, the strings on a,b having the same number of a's as b's; and similarly for aⁿbⁿcⁿ, etc.); ww; ww^R; and a^kn, for any fixed k.