A nearly optimal sensor placement algorithm for boundary coverage

Locating visual sensors in 2D can be often modeled as an Art Gallery problem. Tasks such as surveillance require observing or “covering” the interior of a polygon with a minimum number of sensors or “guards”. For other tasks, such as inspection and image based rendering, observing the boundaries of the environment is sufficient. As Interior Covering (IC), also Edge Covering (EC) is NP-hard, and no finite algorithm is known for its exact solution. Approximate EC solutions are provided by many heuristic algorithms, but their performances with respect to optimality (minimum number of sensors) is unknown. In this paper, we propose a new EC sensors location technique. The algorithm is incremental, and converges toward the optimal solution. It refines an initial approximation provided by an integer covering algorithm (IEC) where each edge is observed entirely by at least one sensor. A lower bound for the number of sensors, specific of the polygon considered, is used at each step for evaluating the quality of the current solution, and a set of rules are provided for performing a local refinement to reduce the computational burden. The algorithm has been implemented, and tests over hundreds of random polygons show that it supplies solutions very close to and often coincident with the lower bound, and then suboptimal or optimal. In addition, the approximate starting solutions provided by the IEC algorithms are, on the average, close to optimum. The tight lower bound can also be used for testing other EC sensor location algorithms. Running times allow dealing with polygons with up to a few hundreds of edges, which appears adequate for many practical cases. An enhanced version of the algorithm, also taking into account range and incidence constraints, has also been implemented and tested.     

ATM layouts with bounded hop count and congestion

Summary. In this paper we introduce and analyze two new cost measures related to the communication overhead and the space requirements associated with virtual path layouts in ATM networks, that is the edge congestion and the node congestion. Informally, the edge congestion of a given edge e at an incident node u is defined as the number of VPs terminating at or starting from u and using e, while the node congestion of a node v is defined as the number of VPs having v as an endpoint. We investigate the problem of constructing virtual path layouts allowing to connect a specified root node to all the others in at most h hops and with maximum edge or node congestion c, for two given integers h and c. We first give tight results concerning the time complexity of the construction of such layouts for both the two congestion measures, that is we exactly determine all the tractable and intractable cases. Then, we provide some combinatorial bounds for arbitrary networks, together with optimal layouts for specific topologies such as chains, rings and grids. Received: December 1997 / Accepted: August 2000     

A nearly optimal algorithm for covering the interior of an Art Gallery

The problem of locating visual sensors can be often modelled as 2D Art Gallery problems. In particular, tasks such as surveillance require observing the interior of a polygonal environment (interior covering, IC), while for inspection or image based rendering observing the boundary (edge covering, EC) is sufficient. Both problems are NP-hard, and no technique is known for transforming one problem into the other. Recently, an incremental algorithm for EC has been proposed, and its near-optimality has been demonstrated experimentally. In this paper we show that, with some modification, the algorithm is nearly optimal also for IC. The algorithm has been implemented and tested over several hundreds of random polygons with and without holes. The cardinality of the solutions provided is very near to, or coincident with, a polygon specific lower bound, and then suboptimal or optimal. In addition, our algorithm has been compared, for all the test polygons, with recent heuristic sensor location algorithms. In all cases, the cardinality of the set of guards provided by our algorithm was less than or equal to that of the set computed by the other algorithms. An enhanced version of the algorithm, also taking into account range and incidence constraints, has also been implemented.     

Appearance-based visual learning and object recognition with illumination invariance

This paper describes a method for recognizing partially occluded objects under different levels of illumination brightness by using the eigenspace analysis. In our previous work, we developed the “eigenwindow” method to recognize the partially occluded objects in an assembly task, and demonstrated with sufficient high performance for the industrial use that the method works successfully for multiple objects with specularity under constant illumination. In this paper, we modify the eigenwindow method for recognizing objects under different illumination conditions, as is sometimes the case in manufacturing environments, by using additional color information. In the proposed method, a measured color in the RGB color space is transformed into one in the HSV color space. Then, the hue of the measured color, which is invariant to change in illumination brightness and direction, is used for recognizing multiple objects under different illumination conditions. The proposed method was applied to real images of multiple objects under various illumination conditions, and the objects were recognized and localized successfully.     

Optimistic parallel Delaunay triangulation

The paper describes a new parallel algorithm of Delaunay triangulation based on randomized incremental insertion. The algorithm is practical, simple and can be modified also for constrained triangulation or tetrahedralization. It was developed for architectures with a lower degree of parallelism, such as several-processor workstations, and tested on up to 8 processors. Published online: November 20, 2002 This work was supported by the Ministry of Education of The Czech Republic, project MSM 235 200 005     

Disk placement for arbitrary-rate playback in an interactive video server

Multimedia data, especially continuous media including video and audio objects, represent a rich and natural stimulus for humans, but require large amount of storage capacity and real-time processing. In this paper, we describe how to organize video data efficiently on multiple disks in order to support arbitrary-rate playback requested by different users independently. Our approach is to segment and decluster video objects and to place the segments in multiple disks using a restricted round-robin scheme, called prime round-robin (PRR). Its placement scheme provides uniform load balance of disks for arbitrary retrieval rate as well as normal playback, since it eliminates hot spots. Moreover, it does not require any additional disk bandwidth to support VCR-like operations such as fast-forward and rewind. We have studied the various effects of placement and retrieval schemes in a storage server by simulation. The results show that PRR offers even disk accesses, and the failure in reading segment by deadline occurs only at the beginning of new operations. In addition, the number of users admitted is not decreased, regardless of arbitrary-rate playback requests.     

Implicit modeling using subdivision curves

C ¹ continuity everywhere. Moreover, they can be used to generate representations at different levels of detail, enabling the interactive display of at least a coarse version of the objects, whatever the performance of the workstation. We also present a practical solution to the unwanted-blending problem, used to avoid blending between parts of the surface that do not correspond to neighboring skeletal elements. Published online: 22 May 2003     

Multicriteria-optimized triangulations

Published online: 2 August 2001     

Searching a polygonal region by a group of stationary k-searchers

We study the problem of searching for mobile intruders in a polygonal region by stationary searchers having various levels of vision given by the number of flashlights that a searcher carries. We show that (2g−1) 1-searchers (i.e., 2g−1 searchers with one flashlight each) are always sufficient, and sometimes necessary, to search a simple polygonal region having a guard number g, which is the size of a minimum guard set. We also show that g(h+1)-searchers (i.e., g searchers with h+1 flashlights each), and consequently g(h+1) 1-searchers as well, can always search a polygonal region with h?1 holes having a guard number g.     

A method for inspecting industrial parts surfaces based on an optics model

A new method based on an optics model for highly reliable surface inspection of industrial parts has been developed. This method uses multiple images taken under different camera conditions. Phong's model is employed for surface reflection, and then the albedo and the reflection model parameters are estimated by the least squares method. The developed method has advantages over conventional binarization in that it can easily determine the threshold of product acceptability and cope with changes in light intensity when detecting defects.     

Image feedback path tracking control using an uncalibrated CCD camera

Abstract. Image feedback path tracking (IFPT) control of a laser light point (LLP) using a CCD camera is studied in this paper. The tracking path and the LLP are assumed clearly focused in the scene, but no camera calibration is needed. A modified version of the thinning algorithm SPTA is proposed to skeletonize the path in a piecewise manner. The proposed thinning algorithm takes less computer time than the original SPTA and makes the real-time skeletonization possible. Included in the paper is also the development of a control algorithm with image feedback to assure LLP tracking along the required path, as well as an experimental study to demonstrate how IFPT control can be realized in practice. Received: 10 November 1999 / Accepted: 9 March 2000     

A bin picking system based on depth from defocus

It is generally accepted that to develop versatile bin-picking systems capable of grasping and manipulation operations, accurate 3-D information is required. To accomplish this goal, we have developed a fast and precise range sensor based on active depth from defocus (DFD). This sensor is used in conjunction with a three-component vision system, which is able to recognize and evaluate the attitude of 3-D objects. The first component performs scene segmentation using an edge-based approach. Since edges are used to detect the object boundaries, a key issue consists of improving the quality of edge detection. The second component attempts to recognize the object placed on the top of the object pile using a model-driven approach in which the segmented surfaces are compared with those stored in the model database. Finally, the attitude of the recognized object is evaluated using an eigenimage approach augmented with range data analysis. The full bin-picking system will be outlined, and a number of experimental results will be examined. Received: 2 December 2000 / Accepted: 9 September 2001 Correspondence to: O. Ghita     

Constant time permutation: an efficient block allocation strategy for variable-bit-rate continuous media data

To provide high accessibility of continuous-media (CM) data, CM servers generally stripe data across multiple disks. Currently, the most widely used striping scheme for CM data is round-robin permutation (RRP). Unfortunately, when RRP is applied to variable-bit-rate (VBR) CM data, load imbalance across multiple disks occurs, thereby reducing overall system performance. In this paper, the performance of a VBR CM server with RRP is analyzed. In addition, we propose an efficient striping scheme called constant time permutation (CTP), which takes the VBR characteristic into account and obtains a more balanced load than RRP. Analytic models of both RRP and CTP are presented, and the models are verified via trace-driven simulations. Analysis and simulation results show that CTP can substantially increase the number of clients supported, though it might introduce a few seconds/minutes of initial delay. Received June 9, 1998 / Accepted January 21, 1999     

A compact algorithm for rectification of stereo pairs

Abstract. We present a linear rectification algorithm for general, unconstrained stereo rigs. The algorithm takes the two perspective projection matrices of the original cameras, and computes a pair of rectifying projection matrices. It is compact (22-line MATLAB code) and easily reproducible. We report tests proving the correct behavior of our method, as well as the negligible decrease of the accuracy of 3D reconstruction performed from the rectified images directly. Received: 25 February 1999 / Accepted: 2 March 2000     

Cost-effective shadowing method using the ED-buffer on an adaptive light cube

Z -buffer approach, which takes full advantage of the resources already provided in current graphics hardware. We employ a modified data structure on the light screen's Z-buffer, which dramatically increases the shadowing accuracy. This data structure, the ED-buffer, also simplifies the shadow testing calculations considerably, needing only a couple of fixed-point multiplications and additions per shadow test. This is ideal for hardware implementation. We also present a technique for optimizing the use of the fixed memory resource in order to maximize the accuracy of shadowing when the scene is projected from the lighting point of view on the six faces of a cube surrounding the light source.     

Co-ordinating Distributed Knowledge: A Study into the Use of an Organisational Memory

This paper presents an ethnographically informed investigation into the use of an organisational memory, focusing in particular on how information was used in the performance of work. We argue that understanding how people make use of distributed knowledge is crucial to the design of an organisational memory. However, we take the perspective that an ‘organisational memory’ is not technology dependent, but is an emergent property of group interaction. In this sense, the technology does not form the organisational memory, but provides a novel means of augmenting the co-ordination of collaborative action. The study examines the generation, development and maintenance of knowledge repositories and archives. The knowledge and information captured in the organisational memory enabled the team members to establish a common understanding of the design and to gain an appreciation of the issues and concerns of the other disciplines. The study demonstrates why technology should not be thought of in isolation from its contexts of use, but also how designers can make use of the creative flexibility that people employ in their everyday activities. The findings of the study are therefore of direct relevance to both the design of knowledge archives and to the management of this information within organisations.     

Robust online detection of pipeline corrosion from range data

We present the Finite-Window Robust Sequential Estimator for the detection and analysis of corrosion in range images of gas pipelines. This statistically robust, real-time technique estimates the pipeline surface range function in the presence of noise, surface deviations, and changes in the underlying model. Deviations from the robust surface fit, corresponding to statistical outliers, represent potential areas of corrosion. Because the algorithm estimates surface parameters over a finite, sliding window of data, it can track moderately high-order surfaces using lower order models. The system is consistent, objective, and non-destructive and can be used with the pipeline in service. Received: 7 September 1999 / Accepted: 2 November 2000     

Restoration by path concatenation: fast recovery of MPLS paths

A new general theory about restoration of network paths is first introduced. The theory pertains to restoration of shortest paths in a network following failure, e.g., we prove that a shortest path in a network after removing k edges is the concatenation of at most k+1 shortest paths in the original network. The theory is then combined with efficient path concatenation techniques in MPLS (multi-protocol label switching), to achieve powerful schemes for restoration in MPLS based networks. We thus transform MPLS into a flexible and robust method for forwarding packets in a network. Finally, the different schemes suggested are evaluated experimentally on three large networks (a large ISP, the AS graph of the Internet, and the full Internet topology). These experiments demonstrate that the restoration schemes perform well in actual topologies. Received: December 2001 / Accepted: July 2002 RID="*" ID="*" This research was supported by a grant from the Ministry of Science, Israel