Genetic algorithms for clustering in machine vision

The paper presents a genetic algorithm for clustering objects in images based on their visual features. In particular, a novel solution code (named Boolean Matching Code) and a correspondent reproduction operator (the Single Gene Crossover) are defined specifically for clustering and are compared with other standard genetic approaches. The paper describes the clustering algorithm in detail, in order to show the suitability of the genetic paradigm and underline the importance of effective tuning of algorithm parameters to the application. The algorithm is evaluated on some test sets and an example of its application in automated visual inspection is presented. Received: 6 August 1996 / Accepted: 11 November 1997     

Edge-preserving texture filtering for real-time rendering

Texture filtering is essential in enhancing the visual quality of real-time rendering. Conventional schemes do not consider the characteristics of texture content, thus the sharpness of edges in texture images cannot be retained. This paper proposes a novel texture-filtering algorithm, which consists of edge-preserving interpolation and edge-preserving MIP-map prefiltering. The memory bandwidth requirement is kept the same as in conventional schemes by dynamically adjusting the interpolation kernel. Hardware implementation is also provided to show the real-time processing capability. Published online: 28 January 2003     

A real-time vision module for interactive perceptual agents

Abstract. Interactive robotics demands real-time visual information about the environment. Real-time vision processing, however, places a heavy load on the robot's limited resources, which must accommodate multiple other processes running simultaneously. This paper describes a vision module capable of providing real-time information from ten or more operators while maintaining at least a 20-Hz frame rate and leaving sufficient processor time for a robot's other capabilities. The vision module uses a probabilistic scheduling algorithm to ensure both timely information flow and a fast frame capture. In addition, it tightly integrates the vision operators with control of a pan-tilt-zoom camera. The vision module makes its information available to other modules in the robot architecture through a shared memory structure. The information provided by the vision module includes the operator information along with a time stamp indicating information relevance. Because of this design, our robots are able to react in a timely manner to a wide variety of visual events.     

SymGeons: A Prototype Model of Visual Complexity with Implications For Visual Control Tasks

The way in which humans perceive and react to visual complexity is an important issue in many areas of research and application, particularly because simplification of complex matter can lead to better understanding of both human behaviour in visual control tasks as well as the visual environment itself. One area of interest is how people perceive their world in terms of complexity and how this can be modelled mathematically and/or computationally. A prototype model of complexity has been derived using subcomponents called ‘SymGeons’ (Symmetrical Geometric Icons) based on Biederman’s original Geon Model for human perception. The SymGeons are primitive shapes which constitute foreground objects. This paper outlines the derivation and ongoing development of the ‘SymGeon’ model and how it compares to human perception of visual complexity. The application of the model to understanding complex human-in-the-loop problems associated with visual remote control operations, e.g. control of remotely operated vehicles, is discussed.     

Self-stabilization with r-operators

This paper describes a parameterized distributed algorithm applicable to any directed graph topology. The function parameter of our algorithm is instantiated to produce distributed algorithms for both fundamental and high level applications, such as shortest path calculus and depth-first-search tree construction. Due to fault resilience properties of our algorithm, the resulting protocols are self-stabilizing at no additional cost. Self-stabilizing protocols can resist transient failures and guarantee system recovery in a finite time. Since the condition on the function parameter (being a strictly idempotent r-operator) permits a broad range of applications to be implemented, the solution presented in our paper can be useful for a large class of distributed systems. Received: August 1999 / Accepted: January 2001     

Performing tasks on synchronous restartable message-passing processors

Summary. This work considers the problem of performing t tasks in a distributed system of p fault-prone processors. This problem, called do-all herein, was introduced by Dwork, Halpern and Waarts. The solutions presented here are for the model of computation that abstracts a synchronous message-passing distributed system with processor stop-failures and restarts. We present two new algorithms based on a new aggressive coordination paradigm by which multiple coordinators may be active as the result of failures. The first algorithm is tolerant of stop-failures and does not allow restarts. Its available processor steps (work) complexity is and its message complexity is . Unlike prior solutions, our algorithm uses redundant broadcasts when encountering failures and, for p =t and largef, it achieves better work complexity. This algorithm is used as the basis for another algorithm that tolerates stop-failures and restarts. This new algorithm is the first solution for the do-all problem that efficiently deals with processor restarts. Its available processor steps is , and its message complexity is , wheref is the total number of failures. Received: October 1998 / Accepted: September 2000     

Extension of the Nicholls-Lee-Nichols algorithm to three dimensions

A new algorithm for clipping a line segment against a pyramid in E ³ is presented. This algorithm avoids computation of intersection points that are not end points of the output line segment. It also solves all cases more effectively. The performance of this algorithm is shown to be consistently better than that of existing algorithms, including the Cohen–Sutherland, Liang–Barsky, and Cyrus–Beck algorithms.     

Foundation for improved interaction by individuals with visual impairments through multimodal feedback

Through an investigation of how the performance of people who have normal visual capabilities is affected by unimodal, bimodal, and trimodal feedback, this research establishes a foundation for presenting effective feedback to enhance the performance of individuals who have visual impairments. Interfaces that employ multiple feedback modalities, such as auditory, haptic, and visual, can enhance user performance for individuals with barriers limiting one or more channels of perception, such as a visual impairment. Results obtained demonstrate the effects of different feedback combinations on mental workload, accuracy, and performance time. Future, similar studies focused on participants with visual impairments will be grounded in this work. Published online: 6 November 2002     

Block-based manipulations on transform-compressed images and videos

This paper addresses the problem of direct image and video manipulation in compressed domain. The capability to perform such manipulations has become attractive in recent years, as more and more visual information is being captured, stored, and moved in compressed form. Our solution to direct manipulation of compressed images and video is based on a set of block-level transforms, called the inner block transforms (IBTs). Each IBT requires a minimal computation effort in compressed domain to yield a regular geometric transformation on an image block. The paper shows how the IBTs can be used to perform many image and video manipulations. This is done by describing the application of IBTs to image subtitling, shearing, and arbitrary angle rotation. The paper also discusses the application of IBT to M-JPEG and MPEG video. The benefits of the proposed direct compressed domain manipulation approach include faster speed, preservation of image quality, and less computing resources.     

Wood inspection with non-supervised clustering

Abstract. The appearance of sawn timber has huge natural variations that the human inspector easily compensates for mentally when determining the types of defects and the grade of each board. However, for automatic wood inspection systems these variations are a major source for complication. This makes it difficult to use textbook methodologies for visual inspection. These methodologies generally aim at systems that are trained in a supervised manner with samples of defects and good material, but selecting and labeling the samples is an error-prone process that limits the accuracy that can be achieved. We present a non-supervised clustering-based approach for detecting and recognizing defects in lumber boards. A key idea is to employ a self-organizing map (SOM) for discriminating between sound wood and defects. Human involvement needed for training is minimal. The approach has been tested with color images of lumber boards, and the achieved false detection and error escape rates are low. The approach also provides a self-intuitive visual user interface. Received: 16 December 2000 / Accepted: 8 December 2001 Correspondence to: O. Silvén     

Packet audio playout delay adjustment: performance bounds and algorithms

In packet audio applications, packets are buffered at a receiving site and their playout delayed in order to compensate for variable network delays. In this paper, we consider the problem of adaptively adjusting the playout delay in order to keep this delay as small as possible, while at the same time avoiding excessive “loss” due to the arrival of packets at the receiver after their playout time has already passed. The contributions of this paper are twofold. First, given a trace of packet audio receptions at a receiver, we present efficient algorithms for computing a bound on the achievable performance of any playout delay adjustment algorithm. More precisely, we compute upper and lower bounds (which are shown to be tight for the range of loss and delay values of interest) on the optimum (minimum) average playout delay for a given number of packet losses (due to late arrivals) at the receiver for that trace. Second, we present a new adaptive delay adjustment algorithm that tracks the network delay of recently received packets and efficiently maintains delay percentile information. This information, together with a “delay spike” detection algorithm based on (but extending) our earlier work, is used to dynamically adjust talkspurt playout delay. We show that this algorithm outperforms existing delay adjustment algorithms over a number of measured audio delay traces and performs close to the theoretical optimum over a range of parameter values of interest.     

The BG distributed simulation algorithm

We present a shared memory algorithm that allows a set of f+1 processes to wait-free “simulate” a larger system of n processes, that may also exhibit up to f stopping failures. Applying this simulation algorithm to the k-set-agreement problem enables conversion of an arbitrary k-fault-tolerant{\it n}-process solution for the k-set-agreement problem into a wait-free k+1-process solution for the same problem. Since the k+1-processk-set-agreement problem has been shown to have no wait-free solution [5,18,26], this transformation implies that there is no k-fault-tolerant solution to the n-process k-set-agreement problem, for any n. More generally, the algorithm satisfies the requirements of a fault-tolerant distributed simulation.\/ The distributed simulation implements a notion of fault-tolerant reducibility\/ between decision problems. This paper defines these notions and gives examples of their application to fundamental distributed computing problems. The algorithm is presented and verified in terms of I/O automata. The presentation has a great deal of interesting modularity, expressed by I/O automaton composition and both forward and backward simulation relations. Composition is used to include a safe agreement\/ module as a subroutine. Forward and backward simulation relations are used to view the algorithm as implementing a multi-try snapshot\/ strategy. The main algorithm works in snapshot shared memory systems; a simple modification of the algorithm that works in read/write shared memory systems is also presented. Received: February 2001 / Accepted: February 2001     

{\cal SMDP}: minimizing buffer requirements for continuous media servers

Excessive buffer requirement to handle continuous-media playbacks is an impediment to cost- effective provisioning for on-line video retrieval. Given the skewed distribution of video popularity, it is expected that often there are concurrent playbacks of the same video file within a short time interval. This creates an opportunity to batch multiple requests and to service them with a single stream from the disk without violating the on-demand constraint. However, there is a need to keep data in memory between successive uses to do this. This leads to a buffer space trade-off between servicing a request in memory mode vs. servicing it in disk-mode. In this work, we develop a novel algorithm to minimize the buffer requirement to support a set of concurrent playbacks. One of the beauties of the proposed scheme is that it enables the server to dynamically adapt to the changing workload while minimizing the total buffer space requirement. Our algorithm makes a significant contribution in decreasing the total buffer requirement, especially when the user access pattern is biased in favor of a small set of files. The idea of the proposed scheme is modeled in detail using an analytical formulation, and optimality of the algorithm is proved. An analytical framework is developed so that the proposed scheme can be used in combination with various existing disk-scheduling strategies. Our simulation results confirm that under certain circumstances, it is much more resource efficient to support some of the playbacks in memory mode and subsequently the proposed scheme enables the server to minimize the overall buffer space requirement.     

Geometric fusion for a hand-held 3D sensor

Abstract. This article presents a geometric fusion algorithm developed for the reconstruction of 3D surface models from hand-held sensor data. Hand-held systems allow full 3D movement of the sensor to capture the shape of complex objects. Techniques previously developed for reconstruction from conventional 2.5D range image data cannot be applied to hand-held sensor data. A geometric fusion algorithm is introduced to integrate the measured 3D points from a hand-held sensor into a single continuous surface. The new geometric fusion algorithm is based on the normal-volume representation of a triangle, which enables incremental transformation of an arbitrary mesh into an implicit volumetric field function. This system is demonstrated for reconstruction of surface models from both hand-held sensor data and conventional 2.5D range images. Received: 30 August 1999 / Accepted: 21 January 2000     

Automated delineation of individual tree crowns in high spatial resolution aerial images by multiple-scale analysis

This paper presents an automatic multiple-scale algorithm for delineation of individual tree crowns in high spatial resolution infrared colour aerial images. The tree crown contours were identified as zero-crossings, with convex grey-level curvature, which were computed on the intensity image for each image scale. A modified centre of curvature was estimated for every edge segment pixel. For each segment, these centre points formed a swarm which was modelled as a primal sketch using an ellipse extended with the mean circle of curvature. The model described the region of the derived tree crown based on the edge segment at the current scale. The sketch was rescaled with a significance value and accumulated for a scale interval. In the accumulated sketch, a tree crown segment was grown, starting at local peaks, under the condition that it was inside the area of healthy vegetation in the aerial image and did not trespass into a neighbouring crown segment. The method was evaluated by comparison with manual delineation and with ground truth on 43 randomly selected sample plots. It was concluded that the performance of the method is almost equivalent to visual interpretation. On the average, seven out of ten tree crowns were the same. Furthermore, ground truth indicated a large number of hidden trees. The proposed technique could be used as a basic tool in forest surveys. Received: 24 June 1997 / Accepted: 28 April 1998     

Fast prototyping of parallel-vision applications using functional skeletons

We present a design methodology for real-time vision applications aiming at significantly reducing the design-implement-validate cycle time on dedicated parallel platforms. This methodology is based upon the concept of algorithmic skeletons, i.e., higher order program constructs encapsulating recurring forms of parallel computations and hiding their low-level implementation details. Parallel programs are built by simply selecting and composing instances of skeletons chosen in a predefined basis. A complete parallel programming environment was built to support the presented methodology. It comprises a library of vision-specific skeletons and a chain of tools capable of turning an architecture-independent skeletal specification of an application into an optimized, deadlock-free distributive executive for a wide range of parallel platforms. This skeleton basis was defined after a careful analysis of a large corpus of existing parallel vision applications. The source program is a purely functional specification of the algorithm in which the structure of a parallel application is expressed only as combination of a limited number of skeletons. This specification is compiled down to a parametric process graph, which is subsequently mapped onto the actual physical topology using a third-party CAD software. It can also be executed on any sequential platform to check the correctness of the parallel algorithm. The applicability of the proposed methodology and associated tools has been demonstrated by parallelizing several realistic real-time vision applications both on a multi-processor platform and a network of workstations. It is here illustrated with a complete road-tracking algorithm based upon white-line detection. This experiment showed a dramatic reduction in development times (hence the term fast prototyping), while keeping performances on par with those obtained with the handcrafted parallel version. Received: 22 July 1999 / Accepted: 9 November 2000     

Long lived adaptive splitter and applications

Summary. Long-lived and adaptive implementations of mutual exclusion and renaming in the read/write shared memory model are presented. An implementation of a task is adaptive if the step complexity of any operation in the implementation is a function of the number of processes that take steps concurrently with the operation. The renaming algorithm assigns a new unique id in the range to any process whose initial unique name is taken from a set of size N, for an arbitrary N and where k is the number of processes that actually take steps or hold a name while the new name is being acquired. The step complexity of acquiring a new name is , while the step complexity of releasing a name is 1. The space complexity of the algorithm is where n is an upper bound on the number of processes that may be active at the same time (acquiring or holding new names), which could be N in the worst case. Both the system response time and the worst case number of operations per process in the presented mutual-exclusion algorithm are adaptive. Both algorithms rely on the basic building block of a long-lived and adaptive splitter. While the adaptive-splitter satisfies a slightly different set of properties than the Moir-Anderson splitter [MA95], it is adaptive and long-lived. In addition, the new splitter properties enable the construction of a non-blocking long-lived (2k-1)-renaming algorithm (which is optimal in the size of the new name space). We believe that the mechanisms introduced in our splitter implementation are interesting on their own, and might be used in other adaptive and long-lived constructions. Received: March 2000 / Accepted July 2001     

Using 3D Sound to Improve the Effectiveness of the Advanced Driver Assistance Systems

Future generation cars will be characterized by a wide range of Information Technology (IT) services providing safety and infotainment. This makes the car an information intensive environment where the visual channel is overloaded, putting the safety of drivers and passengers in jeopardy. We propose the use of a 3D auditory display to provide information from the Advanced Driver Assistance Systems. This reduces the eye-off-road time, exploiting the human capability to associate sounds with positions in space. Preliminary lab tests reveal the suitability of this approach. The system still has to be carefully tuned and personalized to achieve usability and reliability, but we think that it provides a complementary channel that is specially useful in low visibility conditions.     

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