Two approaches to measuring the similarity between symbolically notated musical rhythms are compared with each other and with human judgments of perceived similarity. The first is the edit-distance, a popular transformation method, applied to the symbolic rhythm sequences. The second approach employs the histograms of the inter-onset-intervals (IOIs) calculated from the rhythms. Furthermore, two methods for dealing with the histograms are also compared. The first utilizes the Mallows distance, a transformation method akin to the Earth-Movers distance popular in computer vision, and the second extracts a group of standard statistical features, used in music information retrieval, from the IOI-histograms. The measures are compared using four contrastive musical rhythm data sets by means of statistical Mantel tests that compute correlation coefficients between the various dissimilarity matrices. The results provide evidence from the aural domain, that transformation methods such as the edit distance are superior to feature-based methods for predicting human judgments of similarity. The evidence also supports the hypothesis that IOI-histogram-based methods are better than music-theoretical structural features computed from the rhythms themselves, provided that the rhythms do not share identical IOI histograms.

Several methods for reducing the running time of support vector machines (SVMs) are compared in terms of speed-up factor and classification accuracy using seven large real world datasets obtained from the UCI Machine Learning Repository. All the methods tested are based on reducing the size of the training data that is then fed to the SVM. Two probabilistic methods are investigated that run in linear time with respect to the size of the training data: blind random sampling and a new method for guided random sampling (Gaussian Condensing). These methods are compared with k-Nearest Neighbour methods for reducing the size of the training set and for smoothing the decision boundary. For all the datasets tested blind random sampling gave the best results for speeding up SVMs without significantly sacrificing classification accuracy.

In the manufacturing industry, finding a suitable location for the pin gate (the point from which liquid is poured or injected into a mould) is a difficult problem when viewed from the fluid dynamics of the moulding process. However, experience has shown that a suitable pin gate location possesses several geometric characteristics: the distance from the pin gate to any point in the mould should be small, and the number of turns on the path from a point in the mould to the pin gate should be small. We address the problem of computing locations that possess these geometric characteristics. Given a mould M (modelled by an n-vertex simple polygon), we show how to compute the Euclidean centre of M, when it is constrained to lie in the interior of M or on the boundary of M, in O(n log n + k) time, where k is the number of intersections between M and the furthest-point Voronoi diagram of the vertices of M. We show how to compute the geodesic centre of M, when it is constrained to the boundary, in O(n log n) time, and the geodesic centre of M, when it is constrained to lie in a polygonal region, in O[n(n+k)] time. Finally, we show how to compute the link centre of M, when it is constrained to the boundary of M, in O(n log n) time.

No abstract available.

Results of neighborhood graphs are surveyed. Properties, bounds on the size, algorithms, and variants of the neighborhood graphs are discussed. Numerous applications including computational morphology, spatial analysis, pattern classification, and databases for computer vision are described.>

Given a family of objects in the plane, the line transversal problem is to compute a line that intersects every member of the family.In this paper we examine a variation of the line transversal problem that involves computing a shortest line segment that intersects every member of the family.In particular, we give O(n log n) time algorithms for computing a shortest transversal of a family of n lines and of a family of n line segments.We also present an O(n log2 n) time algorithm for computing a shortest transversal of a family of polygons with a total of n vertices.In general, finding a line transversal for a family of n objects takes fl(n log n) time.This time bound holds for a family of n line segments thus our shortest transversal algorithm for this family is optimal.

We consider a generalization of notions of external visibility of simple polygons, namely weak external visibility, weak external visibility from a line and monotonicity, that we call sector visibility. Informally, sector visibility addresses the question of external visibility along rays (or sight lines) whose angles are restricted to a sector (wedge) of specified width σ. This provides an interesting measure of the degree of external visibility of a polygon. Our framework also permits a unification and extension of a number of previously unrelated results. Finally, our results uncover a curious complexity discontinuity in this family of problems; algorithms are Θ(n) when σ ≤ π or σ = 2π, but require Ω(n log n) time (at least), when π < σ < 2π.

For a set of points P in three-dimensional space, the width of P, W (P), is defined as the minimum distance between parallel planes of support of P. It is shown that W(P) can be computed in O(n log n+I) time and O(n) space, where I is the number of antipodal pairs of edges of the convex hull of P, and n is the number of vertices; in the worst case, I=O(n/sup 2/). For a convex polyhedra the time complexity becomes O(n+I). If P is a set of points in the plane, the complexity can be reduced to O(nlog n). For simple polygons, linear time suffices.>

The link center of a simple polygon P is the set of points x inside P at which the maximal link-distance from x to any other point in P is minimized, where the link distance between two points x, y inside P is defined as the smallest number of straight edges in a polygonal path inside P connecting x to y. We prove several geometric properties of the link center and present an algorithm that calculates this set in time Ο (n2), where n is the number of sides of P. We also give an Ο(n log n) algorithm for finding a point x in an approximate link center, namely the maximal link distance from x to any point in P is at most one more than the value attained from the link center.

Given a set of non-intersecting line segments in the plane, we are required to connect the line segments such that they form a simple circuit (a simple polygon).However, not every set of segments can be so connected.Figure 1 shows a set of segments that does not admit a simple circuit.This leads to the challenging problem of determining when a set of segments admits a simple circuit, and if it does, then find such a circuit.It has been shown [Rappaport] that in general, to determine whether a set of segments admits a simple circuit is NP-complete.In this paper an optimal algorithm is presented to determine whether a simple circuit exists, and deliver a simple circuit, on a set of line segments, where each segment has at least one endpoint on the convex hull of the segments (a CHconnected set of segments).Furthermore this technique can be used to determine a simple circuit of minimum length, or a simple circuit that bounds the minimum area, with no increase in computational complexity.The rest of the paper is summarized.In section 2 cf this paper, the preliminary definitions and notation are introduced.In section 3, the geometric properties of the set, of segments are used to transform the segments into an associated graph.

Given a set of points P = {p1,p2,…,pn} in three dimensions, the width of P, W (P), is defined as the minimum distance between parallel planes of support of P. It is shown that W(P) can be computed in Ο(n log n + I) time and Ο(n) space, where I is the number of antipodal pairs of edges of the convex hull of P, and in the worst case I - Ο(n2). If P is a set of points in the plane, this complexity can be reduced to Ο(n log n). Finally, for simple polygons linear time suffices.

Recently, Snyder and Tang [1] proposed an algorithm for finding the diameter of a convex polygon. In this note a family of convex polygons is described for which their algorithm fails. It is also pointed out that the diameter of an arbitrary simple n-vertex polygon can be computed in O(n) time.

In many computer applications areas such as graphics, automated cartography, image processing, and robotics the notion of visibility among objects modeled as polygons is a recurring theme. This paper is concerned with the visibility of a simple polygon from one of its edges. Three natural definitions of the visibility of a polygon from an edge are presented. The following computational problem is considered. Given an n-sided simple polygon, is the polygon visible from a specified edge? An O(n), and thus optimal, algorithm is exhibited for determining edge visibility under any of the three definitions. The paper closes with an interesting characterization of visibility and some open problems in this area.

The modified Viterbi algorithm is a powerful, and increasingly used, tool for using contextual information in text recognition in its various forms. As yet, no known studies have been published concerning its robustness with respect to source statistics. This paper describes experiments performed to determine the sensitivity of the algorithm to variations in source statistics. The results of the experiments show that a character-recognition machine incorporating the modified Viterbi algorithm, using N-gram statistics estimated from source A does not deteriorate in performance when operating on a passage from source B even if A and B differ significantly in N-gram distributions or entropy.

This paper, in two parts, describes some novel algorithms for pattern recognition research and a framework for efficient development, maintenance, and sharing of Interactive software amongst several users and diverse application areas. This modular interactive software system (MISS) forms the basis of a general purpose image analysis and pattern recognition research system (IPS) implemented in the Macdonald Stewart Biomedical Image Processing Laboratory at McGill University. The first part of the paper discusses the algorithms and some preliminary results. Two algorithms are singled out. The first is an interactive approach to nouparametric feature selection via two-dimensional mapping of the multidimension al minimal spanning tree of the features in pattern space. Some preliminary results of the performance of the algorithm, in the automatic mode, applied to feature selection for cervical cell classification, are presented. The second algorithm is an exact procedure for condensing the training data, in the nearest neighbor decision rule, which yields a minimal set of points that implements precisely the original nearest neighbor decision boundary. The second part of the paper describes the MISS and IPS software systems. The MISS software implementation framework insures software colbpati bility and sharing among many individuals and diverse applications, provides safeguard against software loss, and supports an extendable high level interactive language with on-line document ation. MISS language support includes a BASE LAN GUAGE interpreter (implementing a variant of FORTRAN) plus an EXTENDED LANGUAGE interpreter that facilitates addition of new groups of language statements. Each group of statements is associated with a particular function, application area, or programmer. A-11 IPS software has been implemented within the MISS framework. The present IPS implementation includes over 300 EXTENDED LANGUAGE statements in twenty groups facilitating such functions as: image acquisition and display, simulation of a hardware image processor, data management, image manipulation and filtering, graphics, image segmentation and feature extraction, feature selection, classification, and classification per formance measurement. The overall design philosophy of the MISS and IPS software systems and the ease with which new software can be added and documented are described.

In this part of the paper, the design philosophy of two software systems is discussed. The first, the Modular Interactive Software System MISS (1) is a general purpose interactive software system implementation framework within which purpose specific interactive software systems can be implemented. In addition to providing a framework within which to implement interactive software systems, the MISS system includes a software kernel which supports a high level interactive language plus several utility programs which facilitate the addition and documentation of new software modules implementing new statements in the interactive language. The second software system described here is a general purpose image analysis and pattern recognition research system IPS [1,2]. The IPS system is written within the MISS framework and consists of close to 300 extensions to the base level interactive language supported by the MISS system. Prior to a more detailed description of MISS and IPS, let us examine some of the requirements these software system are designed to meet.

In this paper a modification of the Viterbi algorithm is formally described, and a measure of its complexity is derived. The modified algorithm uses aheuristic to limit the search through a directed graph or trellis. The effectiveness of the algorithm is investigated via exhaustive experimentation on an input of machine-printed text. The algorithm assumes language to be a Markov chain and uses transition probabilities between characters. The results empirically answer the long-standing question of what is the benefit, if any, of using transition probabilities that depend on the length of a word and their position in it.

Recently, Devijver [1] has written an excellent paper on the Bayesian distance and its relation to various measures of distance and information found in the literature.

The lower bound for discrimination information in terms of variation, derived recently by Kullback [7] for the distribution-free case, is sharpened. Furthermore, under a restriction, a lower bound is derived that is sharper than all other existing bounds.

In a recent note1 C. C. Babu derives an upper bound on the probability of misclassification for the case when part of the training data is incorrectly labeled. Using this notation the bound is given by

Articles, books, and technical reports on the theoretical and experimental estimation of probability of misclassification are listed for the case of correctly labeled or preclassified training data. By way of introduction, the problem of estimating the probability of misclassification is discussed in order to characterize the contributions of the literature.

The number of black points in each of the 25 nonoverlapping square regions of a size-normalized character matrix were used to recognize the 3822 uppercase handprinted alphabetic characters from Munson's multiauthor data set. The recognition accuracy obtained using a Bayes' classifier, which assumes statistically independent features, compares favorably with earlier results obtained using recognition systems having complexity comparable to ours. Included are results and a recommendation regarding system evaluation procedures.

It is shown that for n-valued conditionally independent features a large family of classifiers can be expressed as an (n-1)st-degree polynomial discriminant function. The usefulness of the polynomial expansion is discussed and demonstrated by considering the first-order Minkowski metric, the Euclidean distance, and Bayes' classifiers for the ternary-feature case. Finally, some interesting side observations on the classifiers are made with respect to optimality and computational requirements.

Some inequalities are derived between the Kullback divergence, the Bhattacharyya coefficient, the Matusita distance, and the Kolmogorov variational distance.

An upper bound on the probability of error for the general pattern recognition problem is obtained as a functional of the pairwise Kolmogorov variational distances. Evaluation of the bound requires knowledge of a priori probabilities and of the class-conditional probability density functions. A tighter bound is obtained for the case of equal a priori probabilities, and a further bound is obtained that is independent of the a priori probabilities.

Given a set of conditionally independent binary-valued features, a counter example is given to a possible claim that the best subset of features must contain the best single feature.

A contour-tracing technique described in an earlier paper [9] was used along with monogram, bigram, and trigram contextual constraints to recognize handprinted characters. Error probabilities decreased by factors ranging from two to four over those which resulted when contextual constraints were ignored. A simple technique for searching over only the most probable bigrams and trigrams was used to significantly reduce the computation without reducing the recognition accuracy.

A contour-tracing technique originally devised by Clemens and Mason was modified and used with several different classifiers to recognize upper case handprinted characters. Recognition accuracies obtained compare favorably with other published results, particularly when additional simple tests are performed to differentiate commonly confused characters. One suboptimum classifier, in addition to yielding near optimum performance when tested on training data, uses much less statistical information than the optimum Bayes classifier and is significantly better than the optimum classifier when training and test data are limited.