Information Technology Reference
In-Depth Information
knowledge, it makes sense to use pre-processing and analysis techniques of 3D
medical images suitable for the specific nature of this problem. In the research
work, attempts were made to find such methods of extracting and describing fea-
tures of medical images that would ignore the individual features characteristic for
the patient examined, but instead be geared towards extracting and correctly repre-
senting morphological features significant for understanding the pathology por-
trayed in the image. Only correctly identified elements of the image and their
interrelations as well as the suitably selected components of the descriptions of
these elements can form the basis for writing the linguistic description of the im-
age, which would then, at the parsing stage, enable the semantics to be analysed
and symptoms of the disease to be detected. The above elements of the 3D de-
scription, treated as letters of the alphabet (symbols) later used to build certain
language formulas, must in particular be geared towards detecting lesions, thus al-
lowing these lesions not only to be located, but also their essence to be interpreted
and their medical significance defined.
4 Parsing Languages Generated by Graph Grammars
The use of graph grammar to describe 2D or 3D images is mentioned in many scien-
tific publications [10][16][18][20]. On the contrary, publications dealing with the
syntactic analysis of 3D images are sparse. This is due to the computational com-
plexity of the problem of parsing which for the overwhelming majority of graph
grammar classes is an NP-complete problem [3][16][18]. As the methodology of
recognising a specific type of images should be usable in practical applications, the
grammar used for the description and then the recognition (classification) should en-
sure effective parsing. In this study, an ETPL(k) (Embedding Transformation-
preserved Production-ordered k-Left nodes unambiguous) graph grammar has been
proposed because this class offers a strong descriptive capacity and a known, effec-
tive parsing algorithm of a multinomial O(n
2
) complexity [3][16][18]. These gram-
mars constitute a sub-class of edNLC (edge-labelled directed Node-Label
Controlled) graph grammars, which represent a given image using EDG (Indexed
Edge-unambiguous Graph) graphs [3][16][18]. ETPL(k) grammars generate IE
graphs (indexed edge-unambiguous) - graphs with oriented and labelled edges as
well as indexed vertices, allowing images to be unambiguously represented without
deformations. However, distortions can sometimes occur at the image pre-
processing state (e.g. picture primitives or their interrelations are incorrectly
located), in consequence prohibiting the further analysis of such a case. This is be-
cause a standard parser treats such an image as one not belonging to the language
generated by the given graph grammar. This problem can be solved by defining a
certain probabilistic model for the recognised image using random IE graphs, as
proposed in publication [16].
The most difficult job, particularly for graph grammars, is to design a suitable
parser. In a structural analysis of graph representations, this parser automatically
provides the complete information defining the 3D topology of the analysed
graph. The difficulty in implementing a syntactic analyser stems from the lack of
ready grammar compilers like those available for context-free grammars [20], and
Search WWH ::
Custom Search