Wolfson College, Oxford: Advanced Computational Science and Engineering

As an extension to the Centre of Excellence activities a joint affiliate centre between CCSE and Wolfson College of Oxford University was set up in Oxford with the state of the art cluster-computing facilities and started its activities with two full time researcher concentrating on Advanced Computational Science and Engineering (ACSE).

The research of ACSE is collaborative effort with scientists in Theoretical Physics (Professors Sir Roger Elliott, Douglas Abraham and Robin Stinchcombe) of the Department of Physics, in Information Engineering (Professor Mike Brady) of the Department of Engineering Sciences, in Materials Sience Department (Professor: Adrian Sutton), and in Mathematical Biology (Professor Philip Maini) of Mathematics Institute of the University of Oxford.

In addition ACSE operates a visitors programme for LCE researchers to spend 1-4 months in Oxford to collaborate with scientists there.

Numerical Estimation of the Asymptotic Behaviour of Solid Partitions of an Integer

Researchers: Ville Mustonen1,2 and R. Rajesh1
1 Department of Physics - Theoretical Physics, University of Oxford
2 Laboratory of Computational Engineering, Helsinki University of Technology

Combinatorial enumeration problems arise naturally in many problems of statistical physics. The number of partitions of an integer (see [1,2] for an introduction) is one such enumeration problem with a history dating back to Euler. Examples of applications to physical problems include the q -->oo Potts model, compact lattice animals, crystal growth, lattice polygons, Bose-Einstein statistics, dimer coverings and rhombus tilings.

The solution to the integer partitioning problem is known for 1-dimensional and 2-dimensional partitions. However, not much is known about higher dimensional partitions. Numerical estimation of the asymptotic behaviour of these higher dimensional partitions could lead to theoretical insights. In this study, we determine numerically the leading asymptotic behaviour of 3-dimensional partitions by exact enumeration and Monte Carlo techniques.

[1] Andrews G E 1976 The Theory of Partitions Encyclopedia of Mathematics and its Applications Vol 2 (Reading: Addison-Wesley)

[2] Stanley R P 1999 Enumerative Combinatorics, Vol.2 (Cambridge: Cambridge University Press)

Filling Transition

Researchers: D. B. Abraham1, Ville Mustonen1,2 and A. J. Wood1
1 Department of Physics - Theoretical Physics, University of Oxford
2 Laboratory of Computational Engineering, Helsinki University of Technology

The problem of filling (see Fig. 41), that is of wetting on grooved and pitted substrates, has been a subject of considerable recent work motivated by potential practical applications, The key intellectual interest is that interfaces between coexisting phases display spatial fluctuations about their mean position which diverge with the system size. Below some temperature say TF, interface is bound to the substrate and when T --> TF interface unbinds from the substrate. This transition is studied using transfer matrix method and Monte-Carlo simulations in the context of planar Ising model.

Figure 41

Figure 41: Wetting and filling (corner wetting) transitions can be studied using planar Ising model with surface fields that bind the interface into the substrate in low temperatures (blue interfaces). When temperature T -->TW,F interface unbinds (red interfaces). Then system is said to go through wetting or filling transition depending on the studied geometry.

Pattern Recognition, Medical Imaging

Researchers: Veit U B Schenk1,2 and Mike Brady1
1 Department of Engineering Sciences, University of Oxford
2 Laboratory of Computational Engineering, Helsinki University of Technology

The aim of this project is to detect the intersections of curvi-linear structures in breast-mammograms and to distinguish them from microcalcifications. The increased attenuation at the intersections of curvilinear structures CLS in mammograms leads to speck-like responses which - on a micro-scale - resemble microcalcifications. We have developed a novel technique for distinguishing between the CLS intersections and true microcalcifications. Our method is based on a multiresolution, oriented local energy analysis. Local energy enables the detection of features of several different kinds in a unified framework using local phase to distinguish between the different types. Since CLS occur over a wide range of sizes, we decompose the signal in a multiresolution framework which not only helps detect CLS over a range of scales but also lets us estimate at each location the local width of a CLS. Orientation information computed from steerable filters is used in a clustering algorithm to distinguish between curvilinear structures and other responses. By combining scale, phase and orientation information we can distinguish the CLS from non-CLS locally linear features and thus identify positively CLS in a mammogram. Location where these CLS intersect can then be used to validate the responses of a calcification detector.

The left image of Fig. 42 shows a section of a mammogram with a bright spot in the centre which is being picked up by our calcification detector. The image on the right shows overlaid onto the left image a number lines corresponding to CLS detected using our method.

Our calcification detector responded to the features marked B and C, but not A which is probably too broad and D which was correctly rejected as image-speckle. If the calcification detector were to pick up feature A, this would be classified as an intersection and therefore rejected. Feature C was identified as being the intersection of a number of CLS and could therefore be rejected as a false positive in the calcification detection stage. Feature B on the other hand only has one CLS traversing it and would therefore be accepted.

Figure 42a Figure 42b

Figure 42: Left: Contrast enhanced section of a mammogram. Right: A,C identified as intersections, B rejected.

Another example is given in Fig. 43. The left image shows three bright spots, all of which were detected using our calcification detector. Overlaid onto the same section of mammogram, the right image shows the CLS detected. Feature A was identified as being an intersection of CLS and should therefore be rejected as a false positive, whereas features B and C only have a single CLS traversing them and should therefore be accepted as a true positive.

Figure 43a Figure 43b

Figure 43: Left: Contrast enhanced section of a mammogram. Right: A identified as intersections, B,C rejected.

Pattern Recognition, Ancient Documents

Researchers: Veit U B Schenk1,2 and Mike Brady1
1 Department of Engineering Sciences, University of Oxford
2 Laboratory of Computational Engineering, Helsinki University of Technology

The aim of this project is to detect incisions in the surface of 4th century AD incised wooden stilus tablets such as shown in Fig. 44. Through the use of controlled lighting and a model of the expected luminance-response, our method distinguishes in a single image between the intrinsically three-dimensional features of interest and two-dimensional features such as surface-discolorations. The model-based approach lets us use neighbourhood-processing in order to distinguish relevant responses from noise. Our method is based on a multi-resolution, oriented local energy decomposition of the image, implemented in a steerable filter framework.

Figure 44a Figure 44b
Figure 44c

Figure 44: Top, left: Section of a stilus tablet. Top, right: The result of searching for a valley, step-up,ridge combination from left to right (shown in red) or a ridge,step-down,valley combination from right to left (shown in green). Bottom: Output of Canny-implementation.

Through the use of controlled lighting, we can use an idealized model as the basis of an incision: we expect to 'see' a highlight (a positive ridge) followed by a significant step-down followed by a shadow (a valley), where both the ridge as well as the valley can be of variable width.

The main idea of neighbourhood processing is to treat each point as part of something larger, rather than looking at each point individually without taking into account its neighbours. Since we are looking for locally linear features, we can use the orientation of each candidate point and search along a line of edge/ridge points. If within a certain neighbourhood a large proportion of points are of the same feature-type as the candidate point and have the same or similar orientation, then the candidate point can be assumed to be part of a general edge. Similarly, by looking perpendicularly to a line of edge/ridge points and verifying that e.g. a ridge is bordered by a step-up and a step-down on either side, we can compute a confidence measure indicating how well a set of points corresponds to our 'incision' model.

Using this methods, we obtain the results shown in Fig. 44: overlaid are the valley-pixels which correspond to a valley, step-up, ridge chain when processing the image from left to right, and the ridge-pixels that correspond to a ridge, step-down, valley chain when processing the image from right to left. (the use of direction-information is valid since we control the lighting). Our method produces results that are clearly superior to those obtained using the Canny edge detector as shown in Fig. 44.

Pattern Recognition, Phase-Congruency

Researchers: Veit U B Schenk1,2 and Mike Brady1
1 Department of Engineering Sciences, University of Oxford
2 Laboratory of Computational Engineering, Helsinki University of Technology

The aim of this project is to compute phase-congruency by automatically selecting the range of scales over which a locally one-dimensional feature exists. Our method is based on the use of local energy computed in a multi-resolution steerable filter framework. We observe the behaviour of phase over scale to determine both the type of the underlying features and the optimal range of scales over which they exist. This additional information can be used to provide a more complete description of image-features which can be utilized in a variety of applications that require high-quality low-level descriptors.

The problem with existing phase-congruency methods (the best existing method is P. Kovesi's PC implementation) is that they compute phase-congruency over all scales which leads to incorrect and spurious responses. As an example, see the signal in Fig. 45 and the corresponding PC output on the bottom left in Fig. 45. This is clearly not what a human observer would consider the features in the image. The output on the bottom right in Fig. 45 is that of our method.

Figure 45a
Figure 45b Figure 45c

Figure 45: Top: Synthetic signal with variety of locally one-dimensional features (edges, ridges, valleys). Bottom, left: PC map after postprocessing (non-maximum suppression and hysteresis thresholding). Note the noisy response in bottom left quadrant. Furthermore, only edges are detected. Bottom, right: our method: Ridge (black) and valley (white) feature points overlaid onto original image.

Our approach is based on the use of local energy for feature detection. At each location in the image we compute an energy response, which can be used to obtain an energy-amplitude and a phase-angle f. Since we are interested in the energy response and phase-angle at each image feature independent of its orientation, we interpolate the exact response at the orientation hl of each image-point through the use of steerable filters. To determine the correct range of scales over which to compute phase-congruency, we track the precise, i.e. sub-pixel contours of phase over scale and to label a location in the image as 'interesting' if phase is congruent over a minimum number of scales. Furthermore, we record the start and end scale over which fis congruent. This allows us to provide a rich feature description which could e.g. be used to group features in a meaningful way and remove outliers robustly.

In the two images at the top of Fig. 46 the ridges found in an image of a fingerprint are highlighted. The left image shows the output of our method method (for clarity, the edges and valleys were not marked). Despite the noise-levels and variation in width, the exact centres of the ridges have been marked correctly. This means, not only can we detect the ridges, but we can also describe it in terms of width, orientation etc. The right image shows the output of PC. As with the other examples, the edges dominate most other features. Additionally, because the features are relatively closely spaced, there is significant interference between neighbouring features, leading to a high level of spurious, noisy responses.

Figure 46a  Figure 46b
Figure 46c  Figure 46d

Figure 46: Top: Fingerprint. Bottom: Writing on floor.

The two images at the bottom of Fig. 46 shows the image of a piece of writing on a floor. Note how the width of the letters gets narrower towards the top of the image (rear of the scene). On the left we see the result of our method. Despite this considerable variation in width of the lines, all letters were detected correctly. The image on the right shows the output of hysteresis thresholded PC. Once again, where lines are broad enough to have distinct edges, the edges dominate the broad lines.