Research on artificial intelligence, vision and image processing includes work on: reasoning and planning, autonomous agents and robotics, and medical image processing, that has been established for several years. In addition, following the appointment of a new Professor of Information Processing Systems in June of this year, the Department is seeking to establish new areas of research in computer vision and image processing, in particular, in the application of computer vision techniques, statistical methods, data fusion and filtering. Application areas include: the development of intelligent sensor-based systems, for example to surveillance and monitoring, robotic control and computer modelling systems; and the visualisation and processing of medical imagery obtained by magnetic resonance and novel infra-red techniques that are being developed in the Department of Medical Physics and Bioengineering.
Each area of research deals with aspects of the development of computer systems for the processing of real-world sensor data or for the control of complex, autonomous systems. The problems to be overcome thus range from: having to deal with very large data sets, as in magnetic resonance imaging, and those associated with noisy and poorly conditioned imaging systems, as in infra-red medical imaging techniques; to the control of autonomous systems in unknown or only partially known environments, as in mobile robotics, reasoning and planning, and the behaviour of multiple interacting autonomous agents.
In all cases, the development of appropriate architectures and algorithms, robustness and efficient implementation are key issues. Thus, in the research on reasoning and planning described in section 3.1, particular attention is being paid to the development of an architecture in which an autonomous agent can efficiently create appropriate goals in response to changes in its environment. In particular, in order for an autonomous system to operate safely, effectively and efficiently, both reactive and anticipatory goal creation mechanisms are being explored. In addition,techniques for abstraction are used to enable plans to be formed at the appropriate level of detail in order to reduce the impact of uncertainty and the consequences of action failure.
Anticipatory or predictive techniques are also being used in the research on mobile robotics described in section 3.2. In this case, predicting how useful new data acquired by a mobile robot in exploring its environment would be in carrying out some particular task, such as navigating along a wall, is used as a means of evaluating different exploration and sensing strategies. In addition, an effective and efficient implementation is required if a robot is to operate autonomously in real-time. For the example of navigating along a wall, it has been found that this can be accomplished by using Kalman filtering techniques to estimate the robot's position. The filter is used in a structured architecture in which a supervisory process monitors the map-making and interrupts a lower-level wall following mechanism in order to eliminate inefficient movements.
Similarly, the development of an appropriate architecture is a key issue in the control of interacting autonomous agents, whether they be individual intelligent sensor systems, for example in surveillance applications or in factory automation systems, or a swarm of interacting mobile robots. In fact, the latter, in particular in pursuit tasks, has been found to be an excellent testbed for the comparison and evaluation of different design choices in the development of distributed, artificial intelligence systems. Furthermore, use of this testbed has elucidated new architectural features, such as the importance of "boredom" or progress towards satisfaction of some goal or sub-goal, related to the work on reasoning and planning.
Finally, efficiency and robustness are equally important in research on medical image processing. Efficient implementations are required for processing and display of the very large 3D and 4D data sets, for example in magnetic resonance images. Techniques are being developed for segmentation of magnet resonance images for the automatic detection of, for example, lesions in Multiple Sclerosis, or for the study of Epilepsy and Psychosis. Robustness is required in order to produce a correct segmentation in spite of imaging noise and the inevitable variability of data from different patients. These aspects are of even greater importance, however, in the processing of infra-red imaging data, where regularisation and iterative reconstruction methods are utilised.
Tim Norman (supervised by Derek Long)
The focus of planning research has principally been concerned with the creation of good plans to satisfy a conjunction of goals in an efficient way. These systems typically assume that neither the goals of the agent, nor their importance change as time passes. This assumption cannot be justified for an autonomous agent acting in a real-world domain (i.e., a domain that can neither be completely nor correctly modelled). The domain may change at any time such that pursuing the current goal may no longer be realistic or even possible. Furthermore, the agent will typically need to satisfy various goals, some maybe more than once, at various times as part of an on-going activity; the agent must have the ability to create goals "on the fly" in response to a changing environment.
A real-world domain changes over time presenting a continuous flow of situations to an agent acting in the domain. An effective autonomous agent must be capable of identifying changes that are relevant to its purposes and creating appropriate goals in response to these changes. Goals are created in reaction to perceived changes in the domain. It is essential for an agent to create goals in reaction to certain environmental conditions because of the uncertain nature of a real-world domain. However, typically there are aspects of any domain that can be predicted to a degree. So, by using predictions about how the domain will change over time, an agent can create goals in anticipation of some situations. If an agent is capable of creating good anticipatory goals in an efficient way, the undesirable situations that can be predicted by the agent may be avoided through purposeful action.
A goal creation mechanism that produces both reactive and anticipatory goals through the influence of motivation is under development. This motivated agent is influenced by various, maybe conflicting factors - multiple motives. These motives characterise the purposes of the agent, reflect the context within which the agent is acting, and serve to drive it towards certain types of activity by triggering the creation of goals. Within different situations, the agent may be motivated towards the creation of different goals. In this way, the behaviour of the agent (governed by its goals) is founded in the domain, and changes as the domain (as perceived by the agent) changes.
Maria Fox and Derek Long
The planning group at UCL is concerned with several key issues in the development and application of planners to a range of problems. In particular, the problem of efficiency is paramount, and the group has, for some time, been researching a technique for combatting this problem, based on the use of abstraction in a hierarchical structure. The development of a planner based on this idea has progressed through the complete and detailed formal specification of the system and is currently in prototype. The system will provide an essential platform on which to build further mechanisms with which to treat other problems of concern to the group. These include the problems of planning in open environments in which uncertainty, potential for error and uncontrolled processes and events all complicate the usual simple model of the planning domain. The problems entailed by connecting planning agents to environments in which planned actions are actually executed are also of considerable interest within the group, in several application areas.
A key theme which underlies much of this work is the idea of abstraction. Efficiency is sought through the exploitation of abstraction, in constructing abstract plans at a level of detail where the problem becomes sufficiently simple to solve it quickly, then using this abstract solution as a guide to the construction of detailed plans at a suitable level of detail for execution. It is believed that the problems of interacting with an environment (physical or abstract) can be tackled through the careful employment of abstraction, in order to reduce the impact of uncertainty and action-failure at the strategic planning level.
A further aspect of interacting with an environment, particularly an uncertain environment, is the ability of the planning agent to generate its own goals. This, too, is related to abstraction: we wish to provide high-level abstractions of whole classes of behaviours and the goals they are designed to satisfy, and it is hoped that this can be achieved through the use of motivations .
Recent directions in the work include investigation of the application of the planning techniques in the domain of dialogue-planning and consideration of the consequences of a newly observed link between the approach to planning being pursued by this group and work in cognition and cognitive modelling being pursued in the field of psychology.
An important element in the work is a concern with the theoretical foundations for the developments that are being made. Planning has a long history of close ties with researchers interested in keeping a tight rein on the theoretical underpinnings. However, more recent developments have been increasingly ad hoc and this makes it very difficult to predict their behaviour, effectiveness, or limitations. The group has adopted a formal style for the majority of its work and sees this as an important discipline. The continued analysis and development of the planning framework will progress in a similar style, and it is expected that this will contribute important material to the overall theory of planning.
Mark Levene and T. Fenner (Birkbeck College)
Random minimaxing is the process of using a random static evaluation function for scoring the leaf nodes of a full width game tree and then computing the best move using the standard minimax procedure. Experiments carried out by Beal and Smith at QMW using random minimaxing in chess have shown that the strength of play increases as the depth of the lookahead is increased. We are investigating random minimaxing from a combinatorial point of view in order to obtain a theoretical justification for Beal and Smith's experiments. In particular we have already shown that with respect to chess, random minimaxing with a depth of lookahead equal to two is stronger than random minimaxing with a depth of lookahead equal to one, under the assumption that the more a move made by the first player restricts the second player's choice of moves (i.e. the second player's mobility) the better a move is. We are currently generalising this result for depths of lookahead greater than two.
John Campbell and Mauro Manela
While there are many applications of distributed artificial intelligence, e.g. for potential commercial applications (where vehicle control is a popular field) and as demonstrations that the writers' design choices for the architectures of their cooperating agents are sound, it is difficult to compare different design choices if one is looking for a means of rating alternatives. Because of this, good testbed problems are in some demand - but the nominations of such problems are rather subjective, and they often lack built-in methods of assessment.
We have previously developed a scheme both for evaluation of so-called Pursuit Problems, in which agents of one type cooperate in capturing agents of another type by surrounding them after pursuit on a square grid, as testbeds, and for tuning of the basic design features of autonomous agents that should be able to tackle cooperative pursuits of moving targets (a description that covers a wide variety of problems, e.g. involving optimisation in the widest sense of that word). The suggestion from this work, that a problem in which nine agents pursue five target agents is a good testbed for alternative architectures, has been taken up elsewhere, and our observations are now that this is indeed the case.
Architectural features that we have found to be significant are boredom (a convenient name for an agent's observation that a current situation or the recent progress towards a goal, or both, has not produced anything new, and that something should be done to generate some new activity), how and what an agent does with the communications that it "hears", and multi-agent "bonding" to form superagents. These features are now being exploited in two areas where dynamic control of complex systems is involved.
David Lee (supervised by Michael Recce)
There is a continuing debate in mobile robotics about the value of environment maps. Recent research has generated a surprising amount of useful behaviour from robots with very little, if any, internal representation of their environment. Since a world model is useful only if it captures predictable features of the environment, the value of a map depends strongly on the proposed application of the robot.
This research selects an indoor delivery application in which the robot needs a metric map in order to plan its movements. Two key issues are then examined by practical experimentation:
To get the maximum information from the sonar sensor, adjacent similar returns are grouped to decrease directional and range uncertainty. These grouped returns are used to determine the position and properties of environmental features such as walls and corners. This feature-based map is finally converted into a grid-based free-space map suitable for path planning.
Before we can evaluate an exploration strategy, we need to be able to measure the quality of the generated maps. We define a set of quality metrics which predict the results if the robot were to use its map to perform a number of test tasks. These metrics are then used to monitor map quality during exploration.
Although the robot's target is such that it needs a map, how useful is the partial map during exploration? First we test a wall-following strategy. This is a completely reactive navigation technique which does not use the map at all. The map quality is shown to climb to a peak
and then to decrease as the robot begins to lose track of its position on the map. This loss of quality is overcome by identifying recognisable features and using a Kalman filter to estimate the robot's position.
Wall-following, although robust, can be inefficient. If it does not consult the developing map, the robot may re-examine areas about which no further information is needed. With this in mind, a strategy of Supervised Wall-Following (see Figure) has been implemented in which a supervisory process monitors the map and interrupts the wall-follower to make additional movements or to adjust wall-following parameters to eliminate inefficient movements. This method of exploration has been shown to be significantly more effective than simple wall-following.
Danny Alexander (( supervised by Bernard Buxton)
Over the past decade or so, there has been much research on developing ways of using camera systems for the guidance of land vehicles, either as a driver's assistant, in teleoperation of un-manned vehicles or for the control of autonomous systems. Several systems have been developed for the guidance of road vehicles, often by the close integration of the image processing and computer vision in the vehicle control loop. However, control of vehicles in open terrain is much more difficult and it is widely accepted that a number of machine vision algorthims or modules should be employed and that image data should be fused with other sensor data wherever possible, for example: from odometry, from laser or ultrasonic scanners, radar systems, and from reference maps and global positioning systems.
The aim of this CASE research project with DRA Chertsey which commenced in October 1994 is therefore to develop and evaluate methods for the fusion of data from different image processing modalities and levels, especially from low-level processes such as texture and colour classification and higher level 3D data from motion or stereo systems. By utilizing the data and systems available at the DRA and those being ported to UCL and the results of new techniques under development, fusion processes will be explored at several levels, for example;
In the first two levels of data fusion, information could explicitly be made available to a human operator, either as a driver's assistant in conditions of poor visibility when, for example, IR and other imaging sensors might be employed, or for remote teleoperation. In contrast, in the third level (iii), fused data is not explicitly available in a form that is expected to be useful for viewing by a human operator, but could be used, for example, for providing haptic feedback to a human operator.
Miles Pebody (supervised by John Campbell with John Gilby from Sira Ltd)
This work is a continuing project being jointly supervised by members of the UCL Department of Computer Science and the Postgraduate Centre, Sira Ltd. It aims to examine the nature of building reliable, robust and flexible distributed multi-agent control architectures for systems that must act in the real world and in real time. For example mobile robots or, in our case, an industrial inspection system.
Experimental work is based around the control of a functionally and physically distributed active laser scanning sensor device. It is used in industry for detecting defects in products such as glass, plastic film, metal and painted surfaces which are moved through its laser beam. Reflected laser light is detected by a number of different sensors and information interpreted to locate and identify defects. Each sensor is an individually controlled subsystem that must perform reliably despite external disturbances such as changing ambient light, changing objects and changing sensor to surface distance to name a few. Initial work involved the development of an experimental test bed that incorporated a single sensory subsystem.
Following the bottom-up development pattern that is a characteristic of Behaviour Based Artificial Intelligence, the first stages of the experimental work concentrated on the low level control of an individual sensory subsystem. Methods of enhancing the flexibility and robustness of the sensor using forms of learning and adaptive control based on artificial neural networks have been tested. One of the main working assumptions here was that for maximal robustness the system would be required to autonomously update its operating parameters or learn as it operates on line. Also the system should be effective to some degree from power up and the learning aspect subsequently used to provide constant adjustment.
Work has now turned to the higher level control of multiple sensor channels using the recently completed, two channel inspection system test-bed. Issues that become significant at this level concern aspects of autonomous identification of the system state or situation. For example is the current state of the system the result of an internal fault or failure or the result of some external environmental disturbance? If an external effect, is this a repeating pattern of activity that may be used as a cue in order to anticipate future changes in the environment? These questions are being addressed in the context of the distributed control of the laser scanning inspection test-bed. Architectures of distributed control processes, or software agents are being constructed and experimented with that deal with specific and local aspects of the wider control problem. Again, as in the lower level work, aspects of on line adaptation and learning are of central importance. This time the requirement is for the software agents to adapt in order to more effectively interact with one another.
Simon Arridge and Julia Schnabel with A. Simmons (Institute of Psychiatry, de Crespigny Park), P.S. Tofts and L. Wang (Institute of Neurology, Queen Square) and D. Rückert (Department of Computing, Imperial College London)
With the growth of 3D MRI, and the popularity of 4D functional MRI, there is a considerable need for advanced post-processing software to handle the extremely large volumes of data and to extract meaningful analyses. The primary analysis of such information is visualisation - the images are viewed by experts who can often judge immediately the significance of certain complex relationships. With very large datasets three problems arise - firstly the optimum method of visualisation is difficult to ascertain, secondly there is an inherent observer dependency, leading to problems in reproducibility and inter-observer variation, and thirdly there is a large demand on expert time.
To deal with the first and third problems together, it is desirable to extract quantitative information such as volumetric measurements, and shape descriptions. This information is usually obtained manually by analysis of the images at a computer terminal. Segmentation that partitions the image data into anatomical compartments is the linking step between data acquisition, and quantitative measurement :
A collaboration between University College London and the Institute of Neurology has been established for about five years on the automation of MR brain image segmentation. The original focus was on analysis of Multiple Sclerosis (MS) lesions, but we have now expanded to include applications in Epilepsy, and Psychosis.
Simon Arridge with A. Simmons (Institute of Psychiatry, de
Crespigny Park) and P.S. Tofts (Institute of
Neurology, Queen Square)
The successful segmentation of magnetic resonance images is dependent upon the success of three seperate stages. Initially attention must be paid to the image acquisition in choosing appropriate spin-sequences to enhance neurological contrast. Secondly, the images must be preprocessed to compensate for non-
Isolation of intra-cranial region by edge-focussing using recursive filters: a) original T2-weighted image, b) at =20 c) edge-focused to =2.
uniformities and noise, possibly using non-linear iterative techniques. The third stage is the actual segmentation processing. These may be low-level : such as image enhancement, smoothing, and resolution changes; medium-level such as region-growing, clustering, edge-detection etc.; or high-level : incorporating knowledge-based approaches. The work in this project has concentrated on low and medium level techniques.
Work is being carried out using C and C++ programming under Unix and making use of subroutines and software tools developed as part of the /usr/image package of the University of North Carolina, the SPIDER package, and Synoptics programming language Semper 6+. The Mayo Clinic ANALYZE package is used for fast 3D visualisation. Three main methods are being compared : Multi-resolution segmentation by detection of extremal regions in scale space, edge-based processing, and multi-spectral clustering.
Scale space is a purely data-driven method for segmentation and image description. In this scheme an n-dimensional image is used as the =0 plane of an n+1 dimensional space. The image is allowed to diffuse into the > 0 half space so that any plane of constant represents a lower resolution version of the original. At large enough the image is effectively blurred to a Gaussian shaped blob. If the space is continuous than each element in the original image can be tracked through an iso-intensity path along increasing in a manner thought to emulate the multi-resolution mechanism in the human eye. Each level of scale has its maxima and minima (extrema) determined and the loci of these points with changing scale are called extremal paths. Non-extremal points are associated with iso-intensity curves which are also lines in scale space. At certain points iso-intensity paths merge with an extremal path. The set of paths that merge to a given extremal path represent a natural decomposition of the image. An improved description uses higher order differential invariants of scale space, which involves convolution with (spatial) derivatives of a Gaussian kernel. For example convolution with the Laplacian of a Gaussian implements the well-known Marr-Hildreth operator at a range of scales and would form the asis for edge-focusing. Discrete implementations of scale space are complex and very intensive in both memory and computing time. Normally a fixed discretisation of scale space is made e.g. 128 intervals in . and the blurring carried out by an FFT of the oiginal image followed by multiplication by a Gaussian of standard deviation 2/ and inverse FFT. Progress in this direction is severely limited by spatial and temporal computational complexity, but we have successively used recursive algorithms in place of their counterparts in the spatial or Fourier domain.
Since the data acquisition routinely provides multi-spectral information (early and late echo, and Magnetisation Transfer) an obvious possibility is a clustering approach, using intensity in each image as a feature dimension. In addition many other features may be derived such as scale-space invariants, and texture. The compactness of the resulting clusters is crucially dependent on acquisition protocol and on preprocessing steps such as anisotropic diffusion. The classification step is performed by standard methods such as probabilistic Neural Networks, although we are considering more advanced methods.
Fractional Brownian Feature Vectors for different types of tissue
within a large
range of scales overlap for very small and very large scales.
Fractional Brownian Feature Vectors for different types of tissue
medium range of scales show a clear seperation.
Julia Schnabel (supervised by Simon Arridge ) with L. Wang (Institute of Neurology, Queen Square), and D. Rückert (Department of Computing, Imperial College)
Classifying and extracting multiple sclerosis (MS) lesions in magnetic resonance images is a challenging task, since the shape, position and intensity of the lesions vary considerably. Commonly used feature detectors therefore perform badly in the absence of any predictable patterns in the MS lesions. Fractal dimension estimation proved to be a promising classifier, not only in terms of its actual value, but more importantly because of the fractional Brownian feature vector involved in the dimension's estimation. This feature vector represents the average absolute intensity differences, I, of pixel pairs on an image surface at different scales and is therefore a statistical tool to classify not only the texture but the human perception of roughness of a given surface. Being insensitive to noise and linear image transformation makes it even more applicable for medical imaging, as the image acquisition is frequently subject to high frequency noise and intensity variation.
The fractal dimension, which is estimated by a linear regression technique over the components of the fractional Brownian feature vector, was able to distinguish between white matter, grey matter, CSF and lesions, but showed no big improvement in comparison with other more commonly used detectors. However, further examination of the feature vector itself showed that there was a clear separation possible within a special set of scales. This is due to the fact that the intensity differences for some textures like lesions and white matter are much higher than for grey matter and CSF yet they have a similar degree of roughness. Hence the slope of the linear regression curve correlated to the fractal dimension is almost the same, but the offset shows a clear difference. This offset and the distance of the feature plots can be used as a feature detector in order to do a texture based segmentation. However, figure 3.3 shows that for very small and very large scales some of the feature vectors are overlapping because the image surface is not fractal over all scales. Thus only a medium scale range as in figure 3.4 can be selected. Another drawback is the fact that not all regions have sufficient sizes for a reliable feature estimation. Future work is concentrated on composing virtual regions of all different kinds of textures by region merging routines in order to get statistically reliable segmentation results.
Julia Schnabel (supervised by Simon Arridge )
For the interpretation of MRI images of the brain, it is desirable to analyse the images in order to extract quantitative information such as volumetric measurements, and shape descriptions. The first step to shape analysis is to segment the image, which subdivides an image into its constituent objects and thus provides a higher semantic description of the image. The next step is to describe the found object by the length of its boundary, its area, its compactness, or by other descriptors to obtain a quantitative measure. The goal of this work is to incorporate shape description into the segmentation step, as the shape description metrics provide a method to distinguish between normals and abnormals, a topic of central importance. The recently developed model of active contours proves to be an adequate method for this task.
Active contours are a method for segmentation based on minimising the energy of a continuous spline contour subject to constraints on both its autonomous shape and external forces derived from a superposed image that pull the active contour toward image features such as lines and edges. The contour is initially placed near an edge under consideration, then image forces and the user-defined external constraints draw the contour to the edge in the image. In subsequent iterations of the algorithm, the energy terms can be adjusted by higher level processes to obtain an appropriate local minimum. For example, by using scale space continuation as described in section 3.3.2, the capture region surrounding the feature can be enlargened by making the energy constraints a function of differential invariants in scale. The most promising aspect for a medical application of the presented active contour model is the derivation of a quantifying measure for the rate of change of the model's shape when modifying its energy constraints in order to describe and classify object deformations in medical images.We have been able to produce quantitative descriptions of shape at any scale and are now investigating their correlation with clinical evaluations.
Simon Arridge with M. Schweiger and D.T. Delpy (Department of Medical Physics and BioEngineering, UCL)
Infra-Red Imaging (IRI) is a new technique being developed for visualising the oxygenation state of tissue, in particular the brain. It is based on the discovery that human tissue has a relative transparency to infra red light in the region 700-1000nm over the highly attenuated visible spectrum. Relative is used carefully : it is found that light is attentuated by about one Optical Density (OD) for each centimetre of tissue. Nevertheless using high peak power pulsed laser diodes and low-light sensitive photodetectors, clinical instruments have been developed that continuously monitor absorption changes of selected frequencies over time in premature babies in intensive care.
The development of an imaging modality requires a method of reconsructing the distribution of absorption coefficient throughout a domain based on the measurement of light intensity over the boundary . This requires two seperate problems :
A simple analysis shows that the Inverse Problem is ill-posed , but a regularised problem may be derived.
We have developed an iterative solution of the Inverse Problem that computes the Frechet derivative of the Forward operator for any given and inverts this to produce a multi-dimensional Newton-Raphson step. The operator inversion takes into account the ill-posed nature of the problem. The non-linearity of the problem is incorporated by using the Levendburg-Marquandt non-linear minimisation procedure. In addition regularisation can be included by adding Lagrangian multiples of the Sobolev norm of the solution vector. A topic of interest is to investigate the use of a priori knowledge in the regularisation procedures using anatomical structure derived from other modalities. We are also investigating alternative inverse methods such as ART (Algebraic Reconstruction Technique), POCS (Projection Onto Convex Sets), and Conjugate Gradients.
In order to carry out this algorithm in realistic times requires fast computation of the Forward Problem. Several possibilities exist for the Forward Problem, the most commonly used being Monte-Carlo modelling and Photon Diffusion. The former is a standard interaction modelling procedure, following the path of each photon as it is scattered and attenuated. It is very successful in terms of accuracy, but prohibitively expensive in terms of time. The second method models Photon density as the solution of a time-dependent equation:
In simple geometries this can be solved analytically by deriving the Green's Function of the differential operator. In more complex cases a Finite Element solver is used. The current project is developing a fast accurate Finite Element model and adapting it for solution of the Inverse Problem.
An interesting result that has emerged from an analysis of the Forward and Inverse problems is that the accuracy and stability of solutions depends greatly on the type of data g. In particular, the most useful images seem to derive by using the average time of arrival:
The Finite Element method accomodates this easily by producing the output flux as a function of time, and performing a numerical integration. Furthermore we have developed FEM methods for directly constructing other measures of the time-dependent flux such as higher order ments, early-weighted integrals, phase and modulation depth of the Fourier Transform of the signal. This allows us a rich variety of data types. We have demonstrated successful reconstructions of both absorption and scatter images simultaneously provided that sufficiently uncorrelated data sets are available. Another recent advance is an accurate predictor of the statistical properties of each of these data types in a real photon counting device. This allows the usage of non-stationary data norms (e.g. the Malanhobis distance) in the optimisation procedure implicit in the Inverse Problem.
When manipulating volumetric data such as occurs in Medical imaging, an appropriate representation is a voxel array. Because of the large size of such data sets (typically at least 16MB), hierarchical representations such as octrees , with commensurate recursive traversal algorithms have received a great deal of attention in the literature. Generally such structures and associated algorithms show a reduction in complexity from 0(n3) to 0(n2) where n is the resolution in one dimension. For visualisation of the data the most complete method is known as Volume Rendering and is based essentially on the principles of ray tracing, a well established technique that is known to be computationally intensive.
Octree structures have the property that only regions of interest are subdivided, resulting in variable sized nodes which cannot be traversed very efficiently using existing ray tracing algorithms Previously, solutions have been based on one of two methods. Kaufmann 's method, using integer and shift arithmetic only, operates on the full voxel structure (i.e. not octree encoded) to find the set of voxels intersected by a ray by an incremental algorithm based on Bresenham's algorithm for finding the pixels representing a straight-line. Conversely Glassner's algorithm was originally developed to trace a ray through the octree of a continuous (e.g. CSG) representation (known as a vector octree) rather than a discrete (e.g. voxel) representation (known as raster octree), and uses real intersection arithmetic.
We have developed a robust and efficient way for traversing hierarchically subdivided space, (quadtrees in two dimensions and octrees in three dimensions), that marries up these wo approaches. We adapted Bresenham with great success (in 2D and 3D) to traverse nodes of quadtrees and octrees and Glassner's algorithm to traverse raster quadtrees instead of vector ones. Our new algorithm uses integer and shift arithmetic like the Bresenham line-drawer, and so can be easily implemented in hardware, yet operates on the hierarchical representation to exploit coherence in the data. The use of integer arithmetic and the logarithmic complexity behaviour it presents also, makes the algorithm independent of the type of machine on which it runs.
Generally the actual timing performance of the algorithm is far better than Kaufman's method, and Glassner's algorithm can only compete ours in very powerful machines that handle real arithmetic at least efficiently. Currently this algorithm is being incorporated in a ray tracing algorithm producing a very efficient ray tracing method. Using real medical images for testing, we have shown that the algorithm makes possible the ray tracing of complex scenes by medium and small scale computers.
Volume Rendered Image of MRI Data Set.