Algorithm representation Use case
Authors: PatriziaAsirelli, SuzanneLittle, MassimoMartinelli, OvidioSalvetti
Index
Contents
1. Problem
The problem is that algorithms for image analysis are difficult to manage, understand and apply, particularly for non-expert users. For instance, a researcher needs to reduce the noise and improve the contrast in a radiology image prior to analysis and interpretation but is unfamiliar with the specific algorithms that could apply in this instance. In addition, many applications require the processes applied to media to be concisely recorded for re-use, re-evaluation or integration with other analysis data. Quantifying and integrating knowledge, particularly visual outcomes, about algorithms for media is a challenging problem.
2. Solution
Our proposed solution is to use an algorithm ontology to record and describe available algorithms for application to image analysis. This ontology can then be used to interactively build sequences of algorithms to achieve particular outcomes. In addition, the record of processes applied to the source image can be used to define the history and provenance of data.
The algorithm ontology should consist of information such as:
- name;
- informal natural language description
- formal description
- input format
- output format
- example media prior to application
- example media after application
- goal of the algorithm
- ...
To achieve this solution we need:
- a sufficiently detailed and well-constructed algorithm ontology;
- a core multimedia ontology;
- domain ontologies and
- the underlying interchange framework supplied by semantic web technologies such as XML and RDF.
The benefits of this approach are:
- modularity through the use of independent ontologies to ensure usability and flexibility;
- …
3. State of the Art and Challenges
Currently there exists a taxonomy/thesaurus for image analysis algorithms we are working on (1) (2) but this is insufficient to support the required functionality. We are collaborating on expanding and converting this taxonomy to an OWL ontology.
The challenges are:
- to articulate and quantify the ‘visual’ result of applying algorithms;
- to associate practical example media with the algorithms specified;
- to integrate and harmonise the ontologies;
- to reason with and apply the knowledge in the algorithm ontology (e.g. using input and output formats to align processes).
4. Possible Applications
The formal representation of the semantics of algorithms enables recording of provenance, provides reasoning capabilities, facilitates application and supports interoperability of data. This is important in fields such as:
- Smart assistance to support quality control and defect detection of complex, composite, manufactured objects;
- Biometrics (face recognition, human behaviour, etc.)
- The composition of web services to automatically analyse media based on user goals and preferences;
- To assist in the formal definition of protocols and procedures in fields that are heavily dependent upon media analysis such as scientific or medical research.
These are applications that utilise media analysis and need to integrate information from a range of sources. Often recording the provenance of conclusions and the ability to duplicate and defend results is critical.
For example, in the field of aeronautical engineering, aeroplanes are constructed from components that are manufactured in many different locations. Quality control and defect detection requires data from many disparate sources. An inspector should understand the integrity of a component by acquiring local data (images and others) and combining it with information from one or more databases and possibly interaction with an expert.
5. Example
Problem:
- Suggest possible clinical descriptors (pneumothorax) given a chest x-ray.
Hypothesis of solution :
- 1) Get a digital chest x-ray of patient P (image A). 2) Apply on image A a digital filter to improve the signal-to-noise ratio (image B). 3) Apply on image B a region detection algorithm. This algorithm segments image B according to a partition of homogeneous regions (image C). 4) Apply on image C an algorithm that 'sorts' according to a given criterion the regions by their geometrical and densitometric properties (from largest to smallest, from darkest to clearest, etc.) (array D). 5) Apply on array D an algorithm that searching on a database of clinical descriptors detects the one that best fits the similarity criterion (result E).
However, we should consider the following aspects:
- step 2) Which digital filter should be applied on image A? We can consider different kinds of filters (Fourier, Wiener, Smoothing, etc. ) each one having different input-output formats and giving slightly different results. step 3) Which segmentation algorithm should be used? We can consider different algorithms (clustering, histogram, homogeneity criterion, etc.). step 4) How can we define geometrical and densitometric properties of the regions? There are several possibilities depending on the considered mathematical models for describing closed curves (regions) and the grey level distribution inside each region (histogram, Gaussian-like, etc.). step 5) How can we define similarity between patterns? There are multiple approaches that can be applied (vector distance, probability, etc.).
Each step could be influenced by the previous ones.
Figure 1: Segment of Algorithm Ontology
Goal: to segment the chest x-ray image (task 3)
A segmentation algorithm is selected. To be most effective this segmentation algorithm requires a particular level of signal-to-noise ratio. This is defined as the precondition (Algorithm.hasPrecondition) of the segmentation algorithm (instanceOf.segmentationAlgoritm). To achieve this result a filter algorithm is found (Gaussian.instanceOf.filterAlgorithm) which has the effect (Algorithm.hasEffect) of improving the signal-to-noise ratio for images of the same type as the chest x-ray image (Algorithm.hasInput). By comparing the values of the precondition of the segmentation algorithm with the effect of the filter algorithm we are able to decide on the best algorithms to achieve our goal.
6. Interoperability aspects
Two types or levels of interoperability to be considered:
- 1) low-level interoperability, concerning data formats and algorithms, their transition or selection aspects among the different steps and consequently the possible related ontologies (algorithm ontology, media ontology); 2) high-level interoperability, concerning the semantics at the base of the domain problem, that is how similar problems (segment this image; improve image quality) can be faced or even solved using codified 'experience' extracted from well-known case studies
In our present use case proposal we focused our attention mainly on the latter.
Considering for instance the pneumothorax example, this can be studied starting from a specific pre-analyzed case in order to define a general reference procedure: what happens if we have to study a pneumothorax case starting from an actual arbitrary image of a patient ? Applying simply the general procedure will not give in general the right solution because each image (i.e. each patient) has its own specificity and the algorithms have to be bound to the image type. Thus, the general procedure is not the one which fits for any case because the results depend on the image to be processed. And also in the better case, the result would be supervised and it would be necessary to apply another algorithm to improve the result itself. High-level interoperability would involve also a procedure able to take trace of a specific result and how it has been obtained starting from a particular input.
The open research questions that we are currently investigating relate to the formal description of the values of effect and precondition and how these can be compared and related. The interoperability of the media descriptions and ability to describe visual features in a sufficiently abstract manner are key requirements.
7. References
- (1)
An Infrastructure for MultiMedia Metadata Management Patrizia Asirelli, Massimo Martinelli, Ovidio Salvetti, SWAMM2006, Edinburgh.
- (2)
Call for a Common Multimedia Ontology Framework Requirements Patrizia Asirelli, Massimo Martinelli, Ovidio Salvetti,Harmonization of Multimedia Ontologies activity 2006.