=Paper=
{{Paper
|id=Vol-2710/paper20
|storemode=property
|title=An ASP Approach for Arteries Classification in CT-scans
|pdfUrl=https://ceur-ws.org/Vol-2710/paper20.pdf
|volume=Vol-2710
|authors=Francesco Fabiano,Alessandro Dal Palù
|dblpUrl=https://dblp.org/rec/conf/cilc/FabianoP20
}}
==An ASP Approach for Arteries Classification in CT-scans==
https://ceur-ws.org/Vol-2710/paper20.pdf
An ASP Approach for Arteries Classification
in CT-scans?
Francesco Fabiano1 and Alessandro Dal Palù2
1
Department of Mathematics, Computer Science and Physics,
University of Udine, Via delle Scienze 206, 33100 Udine, Italy
francesco.fabiano@uniud.it
2
Department of Mathematical Physical and Computer Sciences,
University of Parma, Parco Area delle Scienze 53/A, 43124, Parma, Italy
alessandro.dalpalu@unipr.it
Abstract. Automated segmentation of CT scans is the first step in the
pipeline for the interpretation and identification of potential patholo-
gies in human organs. Several methods based on Machine Learning are
currently available, even if their precision is still outperformed by med-
ical doctors. In this field there are some intrinsic limitations to ML ap-
proaches, such as the cost and time to acquire high quality annotated
scans for training; a considerably high variability of organs morphol-
ogy due to age, health conditions, genetics; acquisition noise. This pa-
per outlines a new methodology based on Answer Set Programming,
which returns reliable, easy-to-program and explainable interpretations.
In particular, we focus on the CT scan analysis and retrieval of tree-like
structure, corresponding to main blood vessels (arteries) arrangement.
The structure is compared to the knowledge base of vessels contained
in anatomy text-books. The mapping of vessels names is computed by
an ASP program. This preliminary step produces a robust input to a
reasoner for the multi-organ labeling and localization problem.
Keywords: Answer set programming · CT scan · Image processing ·
Blood vessels classification
1 Introduction
In Italy, according to the registry of tumor [1], there have been 373 thousands
new diagnosis of malign cancer in 2018. The survival rate at 5 years is still very
low, e.g., 20% for liver tumours and only 8% for pancreas neoplasia. Unfortu-
nately, while surgery is the only curative treatment, a small subset of patients are
diagnosed at a sufficiently early stage such that surgery is still a viable option,
mainly because at such stage cancer is often asymptomatic.
The screening process typically involves three main categories of examina-
tions: ultrasound (US), computed tomography (CT) scans and magnetic reso-
nance (MR). They are performed in this specific order and in case of detected
?
Copyright ©
2020 for this paper by its authors. Use permitted under Creative
Commons License Attribution 4.0 International (CC BY 4.0).
2 F. Fabiano and A. Dal Palù
anomalies, the next examination is prescribed. Such investigations are ordered
by increasing running cost, increasing sensitivity and decreasing accessibility.
Usually CT scans show a very good sensitivity for cancer, but in case of small
tumours (less than 2 cm) sensibility and specificity often drop because cancer is
still indistinguishable from healthy tissue. Moreover, radiologist experience and
training make a difference in spotting smaller tumours. Consequently, the diag-
nosis is very challenging, and an early stage tumour can hide behind acquisition
noise, even if other diagnostic modalities (i.e., MR) could highlight the problem.
In recent years, several lines of research have been dedicated to support the
radiologists’ work and to help them in processing and assessing the amount
of data coming from CT scans. The goal is typically to train a system that
suggests potential abnormalities during the experts’ analyses. In Section 2.2 a
short overview is provided. The automated support for diagnosis is a challenging
process, because of a combination of unique domain-specific features:
– Acquisition noise: radiologists train their eyes to selectively remove noise
from the images and to capture the tiniest shadow that could be associated
to tumours;
– Patients anatomy: compared to text-books, abdominal organs are subject
to a high variability in terms of size, shape, position, ageing, genetics, etc.;
– Annotated models: the cost for the creation of clean, complete and anno-
tated model to be fed to automatic training requires some hours for a single
scan. For effective training a large set of cases is needed;
– Need for an explanation: a radiologist can support its diagnosis with a
set of deductions coming from the observation of CT scans. This should be
provided by the automated process as well, as mentioned in [9].
Machine learning approaches do not yet outperform human experts, as op-
posed to other fields of AI applications, partly because of the above mentioned
issues. We argue that such scenario will not drastically mutate in the future
and therefore a different methodology could be more suitable and should be
investigated.
Our project is about the development of a software that could help radiolo-
gists with the detection of early stage tumors and to avoid delayed diagnosis and
treatment. The key idea is to build a system that relies on medical knowledge
(anatomy and radiology) and reasons on it. Constraint programming [14] and
Answer Set Programming [5] are the type of technologies suitable for this task.
In particular, they produce a solution model that is compatible with a knowl-
edge base and an input instance. Moreover, they can provide a high level proof
that can be interpreted by experts, for both model improvement and diagnosis
support.
The challenging goal is to build Logic Programming (LP) programs that
embed the reasoning tasks that radiologists activate during the interpretation
of a scan. Typically, they refer to the text-book knowledge and they map it to
the patient at hand. Differently from atlas based approaches, where a model is
stretched to fit the instance, radiologist aggregate low level features found in the
An ASP approach for arteries classification in CT-scans 3
scan and combine them according to a high level reasoning. As an example, many
high level properties are retained among all human beings: liver is connected to
aorta through the same set of vessels connections, despite their size, length and
placement. In such scenario, liver identification can be easily tracked by following
the correct junctions along the vessel network.
In general, radiologists interleave different types of activities during the vi-
sualization of scans: low level features and landmarks recognition in the scan,
localization and labeling of organs and analysis of organs features. The process is
often performed by looking at a single 2D scan slice at a time and then jumping
among neighbor slices, creating an animation motion that helps in the removal
of noise and in visualizing and highlighting 3D features. Usually, the 3D models
reconstructions from raw data, available in all scan visualizer software, are not
suitable for cancer diagnosis.
Our expected result is to develop a software that could warn a radiologist
about some potential issues, in the attempt to reduce false negative CT exams.
The analysis could provide insightful information about relationships between
organs and suggest whether the patient is a candidate for surgical treatment.
Finally, the software should be integrated into the Picture Archive and Commu-
nication System (PACS)[10], which is the standard for handling medical imaging
data, in order to load it seamlessly in the radiologist workflow.
This paper presents the preliminary models and results achieved so far. Sec-
tion 2 covers the essential topics discussed in the paper. We shortly depict the
main pipeline for the complete tool in Section 3 and we focus on the arteries de-
tection and classification, namely the problem of assigning the anatomical name
to each vessel in the scan. In Section 3.1 we briefly discuss the vessel extraction
and in Section 3.2 we present an ASP model for the vessels’ labelling. We show
some preliminary results in Section 4 and we conclude in Section 5.
2 Background
In this section we review the basic notions that are covered by the project. We
briefly review CT scans, some examples in automated organ recognition and
some basics of Answer Set Programming.
2.1 CT scan
Computer Assisted Tomography (in short CT) scan [8] is a well established
X-ray based acquisition procedure for a general evaluation of pathologies and
traumas. A patient’s body is acquired through a sequence of X-ray images that
are shot from different positions such that they are orthogonal to a central axis
(ideally placed from feet to the head). Each image shows the cumulative absorp-
tion of X-rays caused by body’s content along a specific point of view, as seen
in common 2D X-rays shots. Given the CT scanner controlled setup, a set of
acquisitions can provide information about each single position in the body: a
deconvolution procedure is run to determine the radiometric absorption of each
4 F. Fabiano and A. Dal Palù
voxel (volume element). Typically, the size of a voxel is 1 mm3 . Such volumetric
information is arranged in a 3D matrix, where each cell contains a scalar number
which corresponds to the radiometric absorption of that specific voxel. The unit
of measure is the HU (Hounsfield Unit). Different chemical elements, as well as
different body structures, show different X-ray absorption. Therefore, 3D images
can be used to observe organs, vessels, bones etc. Some structures show similar
intensity or absorption levels and a trained radiologist is able to discriminate
finer details in order to assess potential abnormalities. For example, typical tu-
mours are less dense than healthy tissues and therefore they absorb less X-rays.
This fact can be visualized on a 3D image as a darker area compared to the
neighborhood, assuming to depict values with shades of gray ranging from black
(low absorption, e.g., air) to white (high absorption, e.g., bones).
Radiological images are saved with a standard file format called DICOM
[6]. This image format is uncompressed and it contains 16 bit of information for
each voxel (volume element). Each image usually provides a range of around 3000
distinct values among voxels. Since human vision is capable of distinguish much
less variability (especially on a gray scale), an image may hide some relevant
piece of information that is not visible to the eyes, even when enhancing tools
are used by post processing software. Furthermore, CT images are affected by
intrinsic noise related to the acquisition process and deconvolution of density,
which may interfere with finer analysis.
2.2 Related work
Artificial Intelligence, ranging from vision to machine learning, has been applied
to CT scans, given the valuable richness of information and the high demand
for increased accuracy in interpretation and diagnosis. The overall goal is not
to substitute the radiologist, but to provide them with a tool that can assist
their interpretation process, by highlighting regions of attention and presenting
reasons that support the warning.
Starting from low level vision problems, organ segmentation (see [15, 21, 18]
for some examples and [11] for a survey) is a fundamental problem, where a
program is asked to return a binary matrix, where the value 1 is assigned to
voxels that belong to a specific organ/tissue. The extension of the request to
multi-organ segmentation is rather trivial, while its implementation becomes
more complex but it takes advantage of mutual classification choices. The state of
the art methods lacks from satisfactory precision (up to 86% of volume correctly
classified for pancreas), since the boundaries of organs are often mis-classified.
Unfortunately, such regions are often the place where cancer can grow from (e.g.,
the tail of the pancreas) and radiologists are still able to outperform the tools.
The circulatory system (including arteries and veins) can be identified by
techniques similar to organ segmentation, adapted to the line-shaped structures
[20, 12, 17]. In order to ease the identification of tiniest details, typical analyses
require a contrast medium to be ingested by the patient before the scan. Built
on top of feature extraction problem, an interesting goal is to correctly label
An ASP approach for arteries classification in CT-scans 5
each vessel with its medical name. This can help in referencing the area of
investigation and it can also help surgical preparation.
On the high-level end, another fundamental problem is direct cancer detec-
tion (e.g., [2]) customized for a selected organ. In this case, starting from a
correct organ segmentation, the 3D voxels are analyzed in terms of texture and
other features, typically by neural networks and classifiers.
2.3 ASP
A general program P in the language ASP is a set of rules r of the form:
a0 ← a1 , . . . , am , not am+1 , . . . , not an
where 0 ≤ m ≤ n and each element ai , with 0 ≤ i ≤ n, is an atom of the
form p(t1 , . . . , tk ), p is a predicate symbol of arity k and t1 , . . . , tk are terms
built using variables, constants and function symbols. Negation-as-failure (naf)
literals are of the form not a, where a is an atom. Let r be a rule, we denote with
h(r) = a0 its head, and B + (r) = {a1 , . . . , am } and B − (r) = {am+1 , . . . , an } the
positive and negative parts of its body, respectively; we denote the body with
B(r) = {a1 , . . . , not an }. A rule is called a fact whenever B(r) = ∅; a rule is a
constraint when its head is empty (h(r) = false); if m = n the rule is a definite
rule. A definite program consists of only definite rules.
A term, atom, rule, or program is said to be ground if it does not contain
variables. Given a program P , its ground instance is the set of all ground rules
obtained by substituting all variables in each rule with ground terms. In what
follows we assume atoms, rules and programs to be grounded. Let M be a set of
ground atoms (false ∈ / M ) and let r be a rule: we say that M |= r if B + (r) 6⊆ M
−
or B (r) ∩ M 6= ∅ or h(r) ∈ M . M is a model of P if M |= r for each r ∈ P .
The reduct of a program P w.r.t. M , denoted by P M , is the definite program
obtained from P as follows: (i) for each a ∈ M , delete all the rules r such that
a ∈ B − (r), and (ii) remove all naf-literals in the the remaining rules. A set of
atoms M is an answer set [5] of a program P if M is the minimal model of P M .
A program P is consistent if it admits an answer set.
We will make use of ASP to describe a model which will allow to classify the
vessels extracted from the CT-scans. In fact, thanks to the declarative nature of
ASP, it is possible to define concise and accurate anatomical rules (that follows
“rigid” patterns) that allow a precise labelling even in presence of errors or
uncertainty often produced by the acquisition noise.
3 The methodology outline
Our system has been designed to take advantage of the best technologies for
each of the three phases is composed of. It starts with a filtering process, in
order to attenuate acquisition noise, and a low level feature extraction. The
second phase, based on Logic Programming (LP), labels each body part in the
6 F. Fabiano and A. Dal Palù
scan by reasoning on the set of features. Finally, organ evaluations can take place
inside predicted organs volumes (here, original scan data are used in place of the
filtered version for improved detection precision).
Our vision is to build a system that is based, in the second phase, on LP.
We believe that such technology proposes some distinctive advantages that can
outperform other approaches. The other two phases already show promising
results in the literature.
The main advantage of LP is the capability of including a knowledge base,
which can be build from anatomy textbooks and from radiologists interviews
about their empirical interpretation procedures. Such knowledge can be trans-
lated into a set of clear rules that drive the search of a model matching the
set of patient’s low level features. For example, a rule can state that a specific
artery extends on a specific area and it branches from another artery. A low-level
feature can be a tubular shape with its interconnections. Since vessels form a
tree-like structure, the process of matching boils down to a constrained graph
coloring problem.
Rather than training a classifier, the presence of a knowledge base allows to
i) interact with Medical Doctors on a simple and natural language like level;
ii) integrate the model with information extracted from already existing medical
ontologies [3, 16]; iii) receive an explanation in terms of used rules to justify the
answers; iv) consequently, update and refine the rules in a scientist-in-the-loop
process; v) avoid to build a system that invests its training time for implicitly
learning the anatomical general rules directly from low-level features. In partic-
ular, information retrieval from ontologies could allow us to extract anatomical
information regarding specific vessels (through specific queries). The extracted
piece of information, associated to the anatomy of the vessel (e.g., its average
length or radius) and/or the nomenclature of some of its component, will be
then integrated to our knowledge base. As already said, thanks to the declara-
tive nature of the model, this integration would be relatively easily achieved.
Our system’s interpretation phase mimics the same mental procedure a ra-
diologists follows when she/he observes a CT scan. We interviewed radiologists
during some scans interpretations and asked them to report on the logics behind
their actions and findings. In particular, the procedure appears to be stratified
from a coarse to fine approach. There is a preference in ruling out geometric
properties first (low-level features) and combine them to identify organs and
pathologies. Such strategy allows to decouple feature extraction from the rea-
soning phase. Therefore, off the shelf algorithm from computer vision can be
employed and next specific LP programs can reason about features. In popular
machine learning approaches the two steps are often merged together.
The first radiologist action is to localize main landmarks and to find a refer-
ence in the body. Even if organs position, size and shape can individually differ,
there are some structural properties that are always constant (or more precisely,
there is a set of known structural conformations that occur with some distribu-
tion among population). Vessel organization and structure possess this property
and they are exploited as a 3D map that gives directions to organs. The correct
An ASP approach for arteries classification in CT-scans 7
classification of arteries (which are more visible compared to veins, even with-
out a contrast drug) allows to reach main organs and unlock further deductions
about neighborhood, boundaries etc. Here, radiologists use a global approach
that takes advantage of the whole scan, starting from some safe landmarks. This
phase resembles a constrained graph coloring, which merges radiometric prop-
erties of organs, anatomy information and low level features extracted from the
scan.
We give a brief description of filtering and feature extraction in Section 3.1
and we focus on the the arteries classification problem in Section 3.2. Our future
plan is to extend the LP analysis to the multi-organ classification phase.
3.1 Filtering and feature extraction
In the literature, filtering is fundamental to remove acquisition noise and com-
pensate for spurious interference (e.g. a titanium implant) [19, 13]. Total varia-
tion is a rather effective filtering technique and it is anisotropic and edge pre-
serving [7], so that shapes and boundaries are maintained at the correct position
and contrast. We implemented an interleaved Total Variation and median filter
in order to enhance arteries shape for the goals of our paper.
Unlike [12, 20], where contrast medium in the arteries allows a simple thresh-
olding on the image, we opted for a finer analysis. For each voxel we compute
the principal axis (main eigenvector) in density arrangement and connect voxels
that are oriented along compatible and strong 1D arrangements. Such procedure
returns pieces of reliable tubular fragments that are merged in a bottom up pro-
cess. The ones that are also connected to the thoracic Aorta (the main artery
connected to the heart), are the candidates for labeling. Such set of arteries are
managed as a forest of trees that branch from the Aorta. Additional features are
added to tree branches, e.g. estimated diameter and body quadrant spanned.
Figure 1, on the left, depicts a slice of the CT scan, where voxels values are
plotted with a rainbow palette. Each voxel’s principal direction is printed with
short red lines centered at density local barycenter. It can be seen that clusters
of coherent lines are positioned along artieries (dark green color regions). In the
same Figure on the right, the local cues are merged and tracked. The resulting
yellow lines cover the arteries barycenters. The vertical green line depicts the
Aorta.
3.2 ASP vessels classification
We focus now on the automated process that examines the graph produced by
the feature extraction phase and associates the largest subset of arcs to the
corresponding anatomical names. We introduce an Answer Set Programming
model that, exploiting anatomical rules and relations, performs a labeling of the
main arteries that separate from the thoracic Aorta. This is a minimal test-
bed domain that is sufficient to contain the general issues in finding the correct
labeling. Nevertheless, the program can be extended to cover additional regions
with the effort of coding new set of modular rules. Since all the rules can be
8 F. Fabiano and A. Dal Palù
Fig. 1. Detection of voxels 1D directions (left) and vessel tracking (right)
expanded and modified (thanks to the nature of declarative programming), we
focus on the structure of the program rather than the accuracy of the rules of
knowledge base in use.
Given the presence of possible errors due to acquisition noise, filtering and
extraction of low-level features, the ASP model needs to identify the best clas-
sification while allowing the presence of both missing and incorrect information.
For example, some major artery could not be detected because the junction with
Aorta is outside the scan and/or some set of voxels could resemble an important
vessel while only being a cluster of acquisition noise or a surface of an organ.
Let us note that in this proof of concept, the set of rules in use is based
onto anatomical relationships retrieved from atlas depictions. Some work will be
dedicated to enrich such information thanks to a critical review by radiologists.
In particular, we focus on the set of arteries that separate from the Aorta.
Branching of such arteries along sub-trees, except for the branches of the celiac
trunk, are not yet considered.
Domain Knowledge Let us present the organization of knowledge as extracted
by the procedure described above.
We prepare some facts that constitute the knowledge base. Such knowledge
base covers all the vessels we are interested in and that are going to be assigned
or discarded by the ASP model. In particular, the factual domain knowledge is
formed of three main different types of facts
– m art(ID, Z, A, R): it describes a main artery vessel, i.e. a vessel that
separates from the Aorta ;
– b art(ID, R): it describes a bifurcation artery vessel, i.e. any vessel that
branches from a main artery vessel;
– edge(ID1, ID2): it encodes the tree parent-child relationship between two
connected arteries.
The parameters of the predicates have the following meaning:
– ID/ID1/ID2: the unique id associated to a single vessel;
– Z: an integer that contains the position along the z axis (i.e. the slice number)
where a connection takes place. Intuitively, a higher value is closer to the
head and a lower number is closer to feet;
An ASP approach for arteries classification in CT-scans 9
– A: the angle, in degrees, formed by the vessel when it separates from the aorta
(where the 0 corresponds with left side of the body and increases clockwise);
– R: the radius, in voxels, of the vessel at the separation from the Aorta.
The domain knowledge is automatically extracted. In case of additional geomet-
rical properties, the procedure can be extended to produce such data.
The model The ASP model objective is to associate the vessels, identified
through the domain knowledge, to their anatomical description. The program
also needs to discern between vessels that represents actual anatomical features
from the ones that are false positives.
To perform an accurate labeling we created a model comprised of anatomical
rules that describe some fundamental properties that help the characterization of
a specific label. In particular, several properties associated to each single label are
stored: i) the relative (w.r.t. the other vessels) z-height of a vessel; ii) its radius;
iii) its branching direction angle; iv) its number of entering/exiting edges; and
v) its interconnections with other vessels.
To achieve an optimal classification, we search for a model that verifies the
highest number of rules. The model is reinforced by the presence of multiple
properties for each vessel and the knowledge base uncertainty, errors and miss-
ing information can be handled as well. The program needs to be functional
even when some major piece of information is missing (e.g., the edge between
the Aorta and one of its main branches), and that is why we chose an optimiza-
tion problem on the number of rules rather than imposing strict constrains on
labeling.
Let us present a simplified version of the ASP model. For the sake of read-
ability we show only two arteries’ description. The classification of the remaining
ones follows the same pattern with according anatomical rules.
First of all, let us start by introducing some predicates that are used to
identify anatomical characteristics (i.e., arteries’ radius and direction) with dif-
ferent degrees of precision. Not all the predicates are included for the sake of
readability.
rad small (R) :- rad(R), R > 0, R ≤ 20.
rad big (R) :- rad(R), R > 20.
rad 1 (R) :- rad(R), R > 0, R ≤ 5.
rad 2 (R) :- rad(R), R > 5, R ≤ 10.
···
rad 8 (R) :- rad(R), R > 40.
quad 1 (A) :- angle(A), A > 0, R ≤ 90.
···
quad 4 (A) :- angle(A), A > 270. R ≤ 360.
semiquad 1 (A) :- angle(A), A > 0, A ≤ 45.
···
semiquad 8 (A) :- angle(A), R > 315. A ≤ 360.
10 F. Fabiano and A. Dal Palù
where rad(1..60) and angle(1..360) are facts.
Intuitively the predicates rad small(R) and rad big(R) are used to classify
the radius in two main groups to perform a first partition of the vessels. Then,
thanks to predicates, rad {1/2../8}(R) it is possible to refine this characteri-
zation as in the model of the celiac trunk artery. The predicates related to the
direction angle follow the same principle: the predicates quad {1/2/3/4}(A) give
a coarse classification of the angles while the predicates semiquad {1/2../8}(A)
refine it.
We present now the model of the celiac trunk (referred to as celiac) and
of the left gastric (referred to as gast) arteries. While the former is a branch of
the Aorta (and is therefore a m art) the latter is a b art being a bifurcation of
the celiac trunk itself. As before, we present a simplified version of the model.
p b art (ID, R ) :- id(ID), rad(R), b art in(ID, R).
p m art (ID, Z, A, R ) :- id(ID), height(Z), angle(A), rad(R),
m art(ID, Z, A, R).
artery (ID, N) :- id(ID), name(N), b art(ID, , N).
artery (ID, N) :- id(ID), name(N), m art(ID, , , , N).
m art (ID, Z, A, R, N) :- art gen(ID, N), name(N), p m ar(ID, Z, A, R),
N = celiac, quad 1(A), rad big(R).
conf r (celiac, 0) :- m art( , , A, , celiac), semiquad 2(A).
conf r (celiac, 1) :- m art( , , , R, celiac), rad 6(R).
conf r (celiac, 2) :- m art(ID, , , , celiac), edge(aorta, ID).
conf r (celiac, 3) :- m art(ID1, , , , celiac), b art(ID2, , gast),
edge(ID1, ID2).
conf r (celiac, 4) :- m art( , , , Z1, celiac),
m art( , , , Z2, sup mese), Z1 > Z2.
conf r (celiac, 5) :- m art( , , , Z1, celiac),
m art( , , , Z2, inf mese), Z1 > Z2 + 30.
b art (ID, R, N) :- art gen(ID, N), name(N), p m ar(ID, Z, A, R),
N = gast, rad big(R).
conf r (gast, 0) :- m art( , , , R, celiac), rad 6(R).
conf r (gast, 1) :- b art(ID2, , gast), m art(ID1, , , , celiac),
edge(ID1, ID2).
conf r (gast, 2) :- b art(ID2, , gast), K = 1,
K = #count{ID2 : edge(ID1, ID2)}.
Where the predicates id(ID/ID1/ID2) and height(Z/Z1/Z2) are extracted
from the domain knowledge.
The general idea behind the presented model is to generate, for each artery
fact in the knowledge base (m art and b art), a predicate that associates the
id of the artery to a name. This first association follows some loose anatomical
rules that associate the artery labels only to vessels that respect such rules.
An ASP approach for arteries classification in CT-scans 11
That is why predicates m art and b art only use the less precise radius and
angle descriptors (i.e., rad {big/small} and quad {1/.../4}). If a vessel does
not satisfy such general rule, it is surely not involved in such label. When the IDs
are associated to the names, the program checks which of the various confidence
rules (conf r) are satisfied for a certain artery. These sets of satisfied rules will
be then used to give a score to each model instantiation; the more rules are
satisfied, the more the labeling is optimal. Let us show how this optimization
problem is encoded in our ASP program.
0{art gen(ID, N) : name(N)}1:- id(ID).
rule count(K):- K = #count{N, R : conf r(N, R)}.
#maximize{K : rule count(K)}.
These lines of code tell the solver Clingo [4] to select the generation of predicates
art gen such that the various associations ID-name satisfy the highest number
of confidence rules. Line 0 {art gen(ID,N) : name(N)} 1 allows to skip some
association ID-name because, as already said, the knowledge base could miss the
description of all the vessels.
4 Results
The results of the features extraction on a filtered CT scan (Figure 1) have
been converted into facts of the knowledge base for the ASP model presented in
Section 3.2. As we already said, the model is comprise of rules extracted from
atlas by non medical experts and is, therefore, still not completely accurate.
Our preliminary test of our model focuses on labeling the thoracic aorta, its
main branches and some of the sub-arteries of such branches. We modelled a
total of 20 arteries.
The model correctly classified the Aorta and its main branches. On the other
hand the classification of the sub-arteries is not as accurate, since we did not
include a large set of rules in the model. However, the knowledge coming from
the extracted vessels is richer and we believe further information can be exploited
and used for labelling the whole set of arteries.
Moreover, the features extraction has not been properly tuned. We prefer to
keep some spurious arteries rather than missing some true positives. Therefore,
wrong edges predicates are present, thus increasing the number of candidate
vessels that can be labeled as sub-arteries.
All the experiments were performed on a 2.20GHz Intel Core i7-8750H ma-
chine with 16 GB of memory and with Ubuntu 18.04.5 LTS. The ASP program
was executed exploiting the multi-thread (eight threads in parallel) capabili-
ties of Clingo. The average number of found models is 15, while the average
running times of the program were 0.06 and 124.75 seconds to find the op-
timal model and to conclude the search, respectively. We also measured the
accuracy = correctly labeled arteries
total number of arteries for the optimal model. As we already men-
tioned, we were able to perform the complete test on a single CT scan, obtain-
ing an accuracy of 70%. It is important to notice that the accuracy restricted
12 F. Fabiano and A. Dal Palù
to the main Aorta branches was 87.5%. The global accuracy is lower because
some sub-arteries are unclassified and some mis-classified, because of the limited
knowledge input to the model. The results of the classification are summarized
in Table 1.
artery type label artery type label artery type label
aorta main 3 inf. mesent. main 3 2nd lumbar R main 3
celiac main 3 suprarenal R main 3 2nd lumbar L main 3
gastric bif. 7 suprarenal L main 3 3rd lumbar R main 3
splenic bif. − renal R main 3 3rd lumbar L main 3
hepatic bif. 7 renal L main 3 4th lumbar R main 3
pancreatic bif. 7 1st lumbar R main − 4th lumbar L main 3
sup. mesent. main 3 1st lumbar L main −
Table 1. The result of the ASP classification. The field type is used to distinguish
between main branches of the Aorta (main) and sub-trees of the main branches (bif.).
The symbols 3, 7 and − identify a correctly classified, a mis-classified and an unclas-
sified artery, respectively.
In Figure 2 we depict the Aorta (the large vertical red pipe) and branching
arteries, with a different color associated to each edge. Labelled edges are tagged
with the computed name, while sub-branches are often given a not assigned label.
Fig. 2. Two views of labelled artieries
An ASP approach for arteries classification in CT-scans 13
5 Conclusion
This paper presents a Declarative Programming methodology for CT scan au-
tomated interpretation. We focus on arteries detection and classification and we
introduced an ASP model to label the vessels. This model relies on anatomical
rules to identify the best association of detected vessels with their anatomi-
cal name. The implemented ASP program allows to identify the main arteries
that branch out from the Aorta and some of their bifurcations. Our preliminary
results show that the methodology is viable. More work will be dedicated to
increase the knowledge base on the complete set of thoracic arteries, to extract
a larger set of descriptors and to tune the labelling to different CT scans.
The program contains a set of anatomical rules that are easily modifiable;
currently, we populate the rules with simple spatial relationships derived from
anatomical atlases. This is a key feature that allows, in future versions, to in-
tegrate the experience of radiologists in the model, making it more accurate.
Moreover, we presented a version of the program with only “positive” rules:
that is, rules that, if activated, contribute to the support of a desired property.
The program can be easily expanded to also introduce “negative” rules that
penalize certain model’s instantiations, when activated. We plan to differentiate
weights associated to rules, reflecting the relevance of certain properties, from
anatomical or empirical viewpoint. Moreover, in a future version of the model,
we plan to also add dependencies between the confidence rules. This last three
future works will need supervision of expert radiologists that could help us in
recognizing both “negative” anatomical rules and the weight of the confidence
rules.
Finally, being the model based on declarative programming, it is possible to
interface with tools that would parse the output of the model in natural lan-
guage. This will allow to produce an explanation for the labeling and confidence
rules choices. Having explainable AI techniques [9] is, in fact, a desiderata when
introducing automated tools in environments where the health of the patients is
taken into consideration. Introducing tools that explain the results will allow a
more confident usage of the program from the medical operators and an easier
error pruning/detection.
Acknowledgements
The authors would like to thank the GNCS 2019 project Logic programming for
early detection of pancreatic cancer and Medical Doctors Mirko D’Onofrio and
Nicolò Cardobi (University of Verona) for providing CT scan data and useful
discussions.
References
1. AIRTUM, G.I.: Inumeri del cancro in italia: Intermedia editore (2018)
14 F. Fabiano and A. Dal Palù
2. Chu, L.C., Park, S., Kawamoto, S., Wang, Y., Zhou, Y., Shen, W., Zhu, Z., Xia, Y.,
Xie, L., Liu, F., et al.: Application of deep learning to pancreatic cancer detection:
Lessons learned from our initial experience. Journal of the American College of
Radiology 16(9), 1338–1342 (2019)
3. Deshpande, P., Rasin, A., Brown, E.T., Furst, J., Montner, S.M., Armato III,
S.G., Raicu, D.S.: Augmenting medical decision making with text-based search
of teaching file repositories and medical ontologies: Text-based search of radiol-
ogy teaching files. International Journal of Knowledge Discovery in Bioinformatics
(IJKDB) 8(2), 18–43 (2018)
4. Gebser, M., Kaminski, R., Kaufmann, B., Schaub, T.: Clingo = ASP + control:
Preliminary report. CoRR abs/1405.3694 (2014)
5. Gelfond, M., Lifschitz, V.: The stable model semantics for logic programming. In:
ICLP/SLP. vol. 88, pp. 1070–1080 (1988)
6. Graham, R.N., Perriss, R.W., Scarsbrook, A.F.: Dicom demystified: a review of
digital file formats and their use in radiological practice. Clinical radiology 60(11),
1133–1140 (2005)
7. Grasmair, M., Lenzen, F.: Anisotropic total variation filtering. Applied Mathemat-
ics & Optimization 62(3), 323–339 (2010)
8. Herman, G.T.: Fundamentals of computerized tomography: image reconstruction
from projections. Springer Science & Business Media (2009)
9. Holzinger, A., Biemann, C., Pattichis, C.S., Kell, D.B.: What do we need to build
explainable ai systems for the medical domain? arXiv preprint arXiv:1712.09923
(2017)
10. Hood, M.N., Scott, H.: Introduction to picture archive and communication systems.
Journal of Radiology Nursing 25(3), 69–74 (2006)
11. Kardell, M.: Automatic segmentation of tissues in ct images of the pelvic region.
master thesis (2014)
12. Kitasaka, T., Kagajo, M., Nimura, Y., Hayashi, Y., Oda, M., Misawa, K., Mori,
K.: Automatic anatomical labeling of arteries and veins using conditional random
fields. International Journal of Computer Assisted Radiology and Surgery 12(6),
1041–1048 (2017)
13. Ritschl, L., Bergner, F., Fleischmann, C., Kachelrieß, M.: Improved total variation-
based ct image reconstruction applied to clinical data. Physics in Medicine & Bi-
ology 56(6), 1545 (2011)
14. Rossi, F., Van Beek, P., Walsh, T.: Handbook of constraint programming. Elsevier
(2006)
15. Roth, H.R., Farag, A., Lu, L., Turkbey, E.B., Summers, R.M.: Deep convolutional
networks for pancreas segmentation in ct imaging. In: Medical Imaging 2015: Image
Processing. vol. 9413, p. 94131G. International Society for Optics and Photonics
(2015)
16. Rubin, D.L.: Creating and curating a terminology for radiology: ontology modeling
and analysis. Journal of digital imaging 21(4), 355–362 (2008)
17. Trentin, C., Faggiano, E., Conti, M., Auricchio, F.: An automatic tool for thoracic
aorta segmentation and 3d geometric analysis. In: 2015 9th International Sym-
posium on Image and Signal Processing and Analysis (ISPA). pp. 60–65. IEEE
(2015)
18. Wang, Y., Zhou, Y., Shen, W., Park, S., Fishman, E.K., Yuille, A.L.: Abdomi-
nal multi-organ segmentation with organ-attention networks and statistical fusion.
Medical image analysis 55, 88–102 (2019)
An ASP approach for arteries classification in CT-scans 15
19. Zeng, G.L., Li, Y., Zamyatin, A.: Iterative total-variation reconstruction ver-
sus weighted filtered-backprojection reconstruction with edge-preserving filtering.
Physics in Medicine & Biology 58(10), 3413 (2013)
20. Zhang, W., Liu, J., Yao, J., Summers, R.M.: Automatic anatomical labeling of
abdominal arteries for small bowel evaluation on 3d ct scans. In: 2013 IEEE 10th
international symposium on biomedical imaging. pp. 210–213. IEEE (2013)
21. Zhou, Y., Xie, L., Shen, W., Fishman, E., Yuille, A.: Pancreas segmentation in ab-
dominal ct scan: a coarse-to-fine approach. arXiv preprint arXiv:1612.08230 (2016)