加藤 直樹

Separating an object in an image from its background is a central problem (called segmentation) in pattern recognition and computer vision. In this paper, we study the computational complexity of the segmentation problem, assuming that the sought object forms a connected region in an intensity image. We show that the optimization problem of separating a connected region in a grid of M x N pixels is NP-hard under the interclass variance, a criterion that is often used in discriminant analysis. More importantly, we consider the basic case in which the object is bounded by two x-monotone curves (i.e., the object itself is x-monotone), and present polynomial-time algorithms for computing the optimal segmentation. Our main algorithm for exact optimal segmentation by two x-monotone curves runs in O(N(4)) time; this algorithm is based on several techniques such as a parametric optimization formulation, a hand-probing algorithm for the convex hull of an unknown planar point set, and dynamic programming using fast matrix searching. Our efficient approximation scheme obtains an epsilon -approximate solution in O(epsilon (-1)N(2) log L) time, where epsilon is any fixed constant with 1 > epsilon > 0, and L is the total sum of the absolute values of the brightness levels of the image.

We present a unified scheme for detecting digital components of various planar curves in a binary edge image. A digital component of a curve is the set of input edge points from each of which the horizontal or vertical distance to the curve is at most 0.5. Our algorithm outputs all curve components containing at least k points (k is a given threshold) in O(n(d)) time (if d greater than or equal to 2) and linear space, where n is the number of points, and d is a measure that reflects the complexity of a family of curves; for example, d = 2, 3 and 5 for lines, circles and ellipses, respectively. For most of the popular families of curves, our only primitive operations are algebraic operations of bounded degree and comparisons. We also propose an approximate algorithm for computing an approximation solution with error ratio epsilon = 1 - alpha (called an or-sensitive solution), whose time complexity is O((t/epsilon)(d-1) n), which is very efficient if the threshold-ratio t = n/k is small. (C) 2001 Elsevier Science B.V. All rights reserved.

Analyzing purchase history of customers enables us to discover valuable knowledge that is helpful for developing effective sales promotion. In this respect, we shall introduce a new notion, association strength among brand loyalties, which is defined for every ordered pair of brands. If the association strength between loyalties of brands A and B is high, it represents that purchase of brand A is highly correlated to that of brand B. Conventional method for discovering associative purchasing is usually applied for one purchase opportunity (one receipt), i.e., it reveals how often two commodities are purchased at the same time, On the other hand, we are interested in discovering relationship among customers' loyalties to certain brands or manufacturers by investigating long-term purchase history of customers. By computing association strengths from customers' purchase history of drugstore chain in Japan, we could produce several interesting rules that will be useful for sales promotion planning.

Population heuristics present native abilities for solving optimization problems with multiple objectives The convergence to the efficient frontier is improved when the population contains 'a good genetic information'. In the context of combinatorial optimization problems with two objectives, the supported solutions are used to elaborate such information, defining a resolution principle in two phases. First the supported efficient solution set, or an approximation, is computed. Second this information is used to improve the performance of a population heuristic during the generation of the efficient frontier. This principle has been experimented on two classes of problems the 1\ \ (SigmaC(i), T-max) permutation scheduling problems, and the biobjective 0-1 knapsack problems. The motivations of this principle are developed. The numerical experiments are reported and discussed.

Proceedings of the Seventeenth Annual Symposium on Computational Geometry, (SCG '01), June 3-5, 2001, Medford, Massachusetts, USAsponsored by the ACM Special Interest Group for Graphics and Algorithms and Computation TheoryProc. of 17th Annual ACM Symposium on Computational GeometryWe give an algorithm to compute all the local peaks in the $k$-level o f an arrangement of $n$ lines in $O(n log n) + tilde{O}((kn)^{2/3})$ time. We can also find $tau$ largest peaks in $O(n log ^2 n) + tilde{O}((tau n)^{2/3})$ time. Moreover, we consider the longest edge in a parametric minimum spanning tree (in other words, a bottleneck edge for connectivity), and give an algorithm to compute the parameter value (within a given interval) maximizing/minimizing the length of the longest edge in MST. The time complexity is $tilde{O}( n^{8/7}k^{1/7} + n k^{1/3})$.

We present a method for detecting vanishing points of an architectural image, which consists of mainly parallel and orthogonal lines, and reconstructing a 3D architectural model. For this, we implement an algorithm for line detection from an architectural image, based on the Hough Transform employing the plane sweep technique and test its efficiency and ability of the line detection from digital images. We then apply it to architectural images in order to see the practical usefulness of the proposed method.

An algorithm based on Semi-Definite Programming (SDP) is proposed for the truss topology optimization problem for specified linear buckling load factor, and optimal topologies of trusses are computed by using the Semi-Definite Programming Algorithm (SDPA). It is well known that optimizing structures for specified buckling load factor is difficult because of non-differentiability of the buckling load factor for the case of multimodal solutions. It is shown, in the examples, that the proposed algorithm is applicable to multimodal cases, and an optimal topology with five-fold buckling load factors is found without any difficulty.

We consider the problem of triangulating a convex polygon on spheres using n Steiner points that minimizes the overall edge length ratio. We establish a relation of this problem to a certain extreme packing problem. Based on this relationship, we develop a heuristic producing 6-approximation for spheres (provided n is chosen sufficiently large). That is, the produced triangular mesh is uniform in this respect. The method is easy to implement and runs in O(n(3)) time and O(n) space.

Given a planar point set, we consider three classes of optimal triangulations: (1) the minimum weight triangulation with angular constraints (constraints on the minimum angle and the maximum angle in a triangulation), (2) the angular balanced triangulation which minimizes the sum of the ratios of the maximum angle to the minimum angle for each triangle, and (3) the area balanced triangulation which minimizes the variance of the areas of triangles in the triangulation. With appropriate definition of local optimality for each class, a simple unified method is established for the computation of the subgraphs of optimal triangulations. Computational experiments demonstrate that the method successfully identifies large portion of edges of the optimal triangulations of each class for all problem instances tested, and hence optimal triangulations for each class can be obtained from them by applying dynamic programming. (C) 2000 Elsevier Science B.V. All rights reserved.

In this paper we consider the k-clustering problem for a set S of n points p(i) = (x(i)) in the d-dimensional space with variance-based errors as clustering criteria, motivated from the color quantization problem of computing a color lookup table for frame buffer display. As the inter-cluster criterion to minimize, the sum of intra-cluster errors over every cluster is used, and as the intra-cluster criterion of a cluster S-j, \Sj\(alpha-1) Sigma(Pi is an element of Sj)(\\Xi) (- (x) over bar (Sj)\\2) is considered, where \\.\\ is the L-2 norm and (x) over bar(S-j) is the centroid of points in S-j, i.e., (1/ \S-j\) Sigma(Pi is an element of Sj) (Xi) The cases of alpha = 1, 2 correspond to the sum of squared errors and the all-pairs sum of squared errors, respectively. The k-clustering problem under the criterion with alpha = 1, 2 are treated in a unified manner by characterizing the optimum solution to the k-clustering problem by the ordinary Euclidean Voronoi diagram and the weighted Voronoi diagram with both multiplicative and additive weights. With this framework, the problem is related to the generalized primary shatter function for the Voronoi diagrams. The primary shatter function is shown to be O(n(O(kd))), which implies that, for fixed k, this clustering problem can be solved in a polynomial time. For the problem with the most typical intra-cluster criterion of the sum of squared errors, we also present an efficient randomized algorithm which, roughly speaking, finds an E-approximate 2-clustering in O(n(1/epsilon)(d)) time, which is quite practical and may be used to real large-scale problems such as the color quantization problem.

This paper proposes a new method for finding an optimal floor layout iti a possibly non-rectangular site, based on an orthogonal graph drawing algorithm. With the proposed method, we can obtain a floor layout that allows the existence of non-rectangular rooms, by which we resolve the drawbacks of the existing methods that admit only rectangular rooms. Introducing two types of criteria concerning area and shape for each room, we design an interactive multi-objective optimization algorithm that produces a number of satisfactory solutions. We have implemented the algorithm and tested it for several practical cases.

Given N real weights w(1),w(2),..., w(N) stored in one-dimensional array, we consider the problem for finding an optimal interval I subset of [1, N] under certain criteria. We shall review efficient algorithms developed for solving such problems under several optimality criteria. This problem can be naturally extended to two-dimensional case. Namely, given a N x N two-dimensional array of N-2 reals, the problem seeks to find a subregion of the array (e.g., rectangular subarray R) that optimizes a certain objective function. We shall also review several algorithms for such problems. We shall also mention applications of these problems to region segmentation in image processing and to data mining.

The discovery of Loyal Customers at an early stage is extremely important in highly competitive market in order to increase business chance. Loyal Customer is defined as the customer who has brought high profit to the particular shop for a long period of time. Loyal Customer has been identified in the conventional approach by measuring sales volume or sales quantity for a certain period. However, such an approach is not effective to discover the Loyal Customer with high confidence and at an early stage. The purpose of this paper is to find an effective and robust rule to discover the future Loyal Customer from newcomers at an early stage with higher confidence, using the data-mining tool, C 5.0. The proposed approach is implemented by using real purchase data to observe the effectiveness.

The problem of optimizing the sum of m linear fractional functions (SOLF) in a fixed dimension d, subject to n linear constraints, arises in a number of theoretical and applied areas. This paper presents an improved algorithm for solving the SOLF problem in 2-D. A key subproblem to our solution is the off-line ratio query (OLRQ) problem, which computes the optimal values of a sequence of m linear fractional functions(called ratios), with the ratios subject to a dynamically changing feasible domain defined by O(n) linear constraints. Based on useful geometric properties and the parametric linear programming technique, we develop an algorithm that solves the 2-D OLRQ problem in O((m + n)log(m. + n)) time. Our OLRQ algorithm can be easily implemented and is robust. More importantly, it enables us to speed up every iteration of a known iterative SOLF algorithm in 2-D, from O(m(m + n)) time to O((m + n) log(m + n)). Implementation results of our improved SOLF algorithm have shown that in most cases our algorithm outperforms the commonly-used approaches for the SOLF problem. We also show that several geometric optimization problems can be formulated as 2-D SOLF problems, and hence are solvable by our algorithm.

This paper presents a new approximation algorithm for a vehicle routing problem on a tree-shaped network with a single depot. Customers are located on vertices of the tree. Demands of customers are served by a fleet of identical vehicles with limited capacity. It is assumed that the demand of a customer is splittable, i.e., it can be served by more than one vehicle. The problem we are concerned with in this paper asks to find a set of tours of the vehicles with minimum total lengths. Each tour begins at the depot, visits a subset of the customers and returns to the depot. We propose a 1.35078-approximation algorithm for the problem (exactly, root 41 - 1)/4), which is an improvement over the existing 1.5-approximation.

Topology optimization problem of trusses for specified eigenvalue of vibration is formulated as Semi-Definite Programming (SDP), and an algorithm is presented based on the Semi-Definite Programming Algorithm (SDPA) which utilizes extensively the sparseness of the matrices. Since the sensitivity coefficients of the eigenvalues with respect to the design variables are not needed, the SDPA is especially useful for the case where the optimal design has multiple fundamental eigenvalues, Global and local modes are defined and a procedure is presented for generating optimal topology from the practical point of view. It is shown in the examples, that SDPA has advantage over existing methods in view of computational efficiency and accuracy of the solutions, and an optimal topology with fivefold fundamental eigenvalue is found without any difficulty. (C) 1999 Elsevier Science S.A. All rights reserved.

We give an optimal bound on the number of transitions of the minimum weight base of an integer valued parametric polymatroid. This generalizes and unifies Tamal Dey's O(k(1/3)n) upper bound on the number of k-sets (and the complexity of the k-level of a straight-line arrangement), David Eppstein's lower bound on the number of transitions of the minimum weight base of a parametric matroid, and also the circle minus(kn) bound on the complexity of the at-most-le level (the union of i-levels for i = 1,2,.., k) of a straight-line arrangement. As applications, we improve Welzl's upper bound on the sum of the complexities of multiple levels, and apply this bound to the number of different equal-sized-bucketings of a planar point set with parallel partition lines. We also consider an application to a special parametric transportation problem.

We consider the problem of finding a set of k vertices in a graph that are in some sense remote. Stated more formally, given a graph G and an integer k, find a set P of k vertices for which the total weight of a minimum structure on P is maximized. In particular, we are interested in three problems of this type, where the structure to be minimized is a spanning tree (Remote-MST), Steiner tree, or traveling salesperson tour. We study a natural greedy algorithm that simultaneously approximates all three problems on metric graphs. For instance, its performance ratio for Remote-MST is exactly 4, while this problem is NP-hard to approximate within a factor of less than 2. We also give a better approximation for graphs induced by Euclidean points in the plane, present an exact algorithm for graphs whose distances correspond to shortest-path distances in a tree, and prove hardness and approximability results for general graphs.

Pharma, a drugstore chain in Japan, has been remarkably successful in the effective use of data mining. From over one tera bytes of sales data accumulated in databases, it has derived much interesting and useful knowledge that in turn has been applied to produce profits. Tn this paper, we shall explain several interesting cases of knowledge discovery at Pharma. We then discuss the innovative features of the data mining system developed in Pharma that led to meaningful knowledge discovery.

This paper treats an allocation of a fixed amount of discrete resources to a set of activities so that the performances of activities resulted from the allocation are balanced as much as possible. However, the perfect balanced allocation is not possible, in general, due to the discreteness of resources. So, our aim is to minimize imbalance among the performances. We consider the variance of the performances among activities as a measure of the imbalance. Thus, our problem is formulated as a minimum-variance resource allocation problem. We propose a branch-and-bound algorithm whose experimental computer program was run on 12, 000 examples.

平面上の点集合について次のような二種類の角度制約付き最適な三角形分割を考える。(）三角形の最大角と最小角に制約を有する辺長の総和を最小にする三角形分割;(）三角形の最大角と最小角の比の総和を最小にする三角形分割。それぞれの最適な三角形分割について極小最適性を定義する。その定義にもとづいて最適な三角形分割の部分グラフを求める多項式時間アルゴリズムを与える。Given a planar point set, we consider two classes of optimal triangulations: (1) the minimum weight triangulation with angular constraints (constraints on the minimum angle and the maximum angle in the triangulation) and (2) the angular balanced triangulation which minimizes the sum of the ratios of the maximum angle to the minimum angle for each triangle. With the appropriate definition of local optimality for each class, we establish a simple unified method for the computation of the subgraphs of the optimal triangulations.

Recently Karger proposed a new randomized algorithm for finding a minimum cut of an n-vertex graph (weighted or unweighted) with probability Omega(n(-2)). In this paper we present a new probabilistic analysis of Karger's randomized algorithm for a few classes of unweighted graphs. For random graphs whose edges are selected with a given probability p, (log n)/n less than or equal to p less than or equal to 1, we show that the expectation of success probability of the algorithm is Omega(p/n). We also investigate a class of graphs with special structure that consists of two n-cliques and gamma(n - 1) edges between the two cliques, Here gamma is a parameter satisfying 0 < gamma < 1 that makes these gamma(n - 1) edges a unique minimum cut. We show that the algorithm finds the unique minimum cut with probability n(gamma/n(gamma)). (C) 1997 Elsevier Science B.V.

In this paper, we consider a bicriteria two-machine flow-shop scheduling problem which is to simultaneously minimize both C_max and T_max criteria, and we propose a new genetic algorithm for enumerating all nondominated solutions for this problem. Our algorithm is constructed by incorporating several existing strategies developed for multi-objective optimization problems together with a new strategy which we call seeding strategy that seeds some good individuals in the initial population. We perform computational experiments in order to compare our algorithm with other existing methods.We observe from our computational results that our algorithm produces nondominated solutions very close to exact ones, and outperforms other existing heuristics.