Automated segmentation of CT scans is the rst step in the pipeline for the interpretation and identi cation of potential pathologies in human organs. Several methods based on Machine Learning are currently available, even if their precision is still outperformed by medical doctors. In this eld there are some intrinsic limitations to ML approaches, such as the cost and time to acquire high quality annotated scans for training; a considerably high variability of organs morphology due to age, health conditions, genetics; acquisition noise. This paper 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.
In Italy, according to the registry of tumor [
The screening process typically involves three main categories of examinations: ultrasound (US), computed tomography (CT) scans and magnetic resonance (MR). They are performed in this speci c 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). 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 speci city often drop because cancer is still indistinguishable from healthy tissue. Moreover, radiologist experience and training make a di erence in spotting smaller tumours. Consequently, the diagnosis 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-speci c 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
annotated model to be fed to automatic training requires some hours for a single
scan. For e ective 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 [
Machine learning approaches do not yet outperform human experts, as opposed to other elds 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 di erent methodology could be more suitable and should be investigated.
Our project is about the development of a software that could help
radiologists 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 [
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. Di erently from atlas based approaches, where a model is stretched to t the instance, radiologist aggregate low level features found in the 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 identi cation can be easily tracked by following the correct junctions along the vessel network.
In general, radiologists interleave di erent types of activities during the visualization 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
Communication System (PACS)[
This paper presents the preliminary models and results achieved so far. Section 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 detection and classi cation, namely the problem of assigning the anatomical name to each vessel in the scan. In Section 3.1 we brie y 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
In this section we review the basic notions that are covered by the project. We brie y review CT scans, some examples in automated organ recognition and some basics of Answer Set Programming. 2.1
Computer Assisted Tomography (in short CT) scan [
Radiological images are saved with a standard le format called DICOM
[
Arti cial 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 [
The circulatory system (including arteries and veins) can be identi ed by
techniques similar to organ segmentation, adapted to the line-shaped structures
[
On the high-level end, another fundamental problem is direct cancer
detection (e.g., [
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) = fa1; : : : ; amg and B (r) = fam+1; : : : ; ang the positive and negative parts of its body, respectively; we denote the body with B(r) = fa1; : : : ; not ang. 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 de nite rule. A de nite program consists of only de nite 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 2= M ) and let r be a rule: we say that M j= r if B+(r) 6 M
or B (r) \ M 6= ; or h(r) 2 M . M is a model of P if M j= r for each r 2 P .
The reduct of a program P w.r.t. M , denoted by P M , is the de nite program
obtained from P as follows: (i) for each a 2 M , delete all the rules r such that
a 2 B (r), and (ii) remove all naf-literals in the the remaining rules. A set of
atoms M is 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 de ne 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
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 ltering 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 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 ltered 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 translated 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 speci c artery extends on a speci c 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 classi er, 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 [
Our system's interpretation phase mimics the same mental procedure a radiologists 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 ndings. In particular, the procedure appears to be strati ed from a coarse to ne approach. There is a preference in ruling out geometric properties rst (low-level features) and combine them to identify organs and pathologies. Such strategy allows to decouple feature extraction from the reasoning phase. Therefore, o the shelf algorithm from computer vision can be employed and next speci c LP programs can reason about features. In popular machine learning approaches the two steps are often merged together.
The rst radiologist action is to localize main landmarks and to nd a reference in the body. Even if organs position, size and shape can individually di er, there are some structural properties that are always constant (or more precisely, there is a set of known structural conformations that occur with some distribution among population). Vessel organization and structure possess this property and they are exploited as a 3D map that gives directions to organs. The correct classi cation of arteries (which are more visible compared to veins, even without 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 properties of organs, anatomy information and low level features extracted from the scan.
We give a brief description of ltering and feature extraction in Section 3.1 and we focus on the the arteries classi cation problem in Section 3.2. Our future plan is to extend the LP analysis to the multi-organ classi cation phase. 3.1
In the literature, ltering is fundamental to remove acquisition noise and
compensate for spurious interference (e.g. a titanium implant) [
Unlike [
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
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 testbed domain that is su cient to contain the general issues in nding the correct labeling. Nevertheless, the program can be extended to cover additional regions with the e ort of coding new set of modular rules. Since all the rules can be expanded and modi ed (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, ltering and extraction of low-level features, the ASP model needs to identify the best classi cation 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 di erent 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; { 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 geometrical properties, the procedure can be extended to produce such data. The model The ASP model objective is to associate the vessels, identi ed 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 speci c 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 classi cation, we search for a model that veri es 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 missing 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 optimization problem on the number of rules rather than imposing strict constrains on labeling.
Let us present a simpli ed version of the ASP model. For the sake of readability we show only two arteries' description. The classi cation 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 different degrees of precision. Not all the predicates are included for the sake of readability.
rad small (R) :- rad(R); R > 0; rad big (R) :- rad(R); R > 20: rad 1 rad 2 rad 8 quad 1 quad 4 (R) :- rad(R); R > 0; (R) :- rad(R); R > 5; (R) :- rad(R); R > 40: (A) :- angle(A); A > 0; (A) :- angle(A); A > 270: R semiquad 1 (A) :- angle(A); A > 0; semiquad 8 (A) :- angle(A); R > 315: A
R R R R A 20: 5: 10: 90: 360: 45: 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 rst partition of the vessels. Then, thanks to predicates, rad f1/2../8g(R) it is possible to re ne this characterization as in the model of the celiac trunk artery. The predicates related to the direction angle follow the same principle: the predicates quad f1/2/3/4g(A) give a coarse classi cation of the angles while the predicates semiquad f1/2../8g(A) re ne 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 simpli ed 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; artery (ID;
N) :- id(ID); name(N); b art(ID; ; N):
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; conf r (gast; 0) conf r (gast; 1) conf r (gast; 2)
R; N) :- art gen(ID; N); name(N); p m ar(ID; Z; A; R);
N = gast; rad big(R): :- m art( ; ; ; R; celiac); rad 6(R): :- b art(ID2; ; gast); m art(ID1; ; ; ; celiac);
edge(ID1; ID2): :- b art(ID2; ; gast); K = 1;
K = #countfID2 : edge(ID1; ID2)g: 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 rst association follows some loose anatomical rules that associate the artery labels only to vessels that respect such rules. That is why predicates m art and b art only use the less precise radius and angle descriptors (i.e., rad fbig/smallg and quad f1/.../4g). 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 con dence rules (conf r) are satis ed for a certain artery. These sets of satis ed rules will be then used to give a score to each model instantiation; the more rules are satis ed, the more the labeling is optimal. Let us show how this optimization problem is encoded in our ASP program.
0fart gen(ID; N) : name(N)g1:- id(ID):
rule count(K):- K = #countfN; R : conf r(N; R)g:
#maximizefK : rule count(K)g:
These lines of code tell the solver Clingo [
The results of the features extraction on a ltered 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 classi ed the Aorta and its main branches. On the other hand the classi cation 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 machine 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) capabilities 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 nd the optimal model and to conclude the search, respectively. We also measured the accuracy = ctoortarelcntluymlabebreleodf aarrtteerriieess for the optimal model. As we already mentioned, we were able to perform the complete test on a single CT scan, obtaining an accuracy of 70%. It is important to notice that the accuracy restricted to the main Aorta branches was 87:5%. The global accuracy is lower because some sub-arteries are unclassi ed and some mis-classi ed, because of the limited knowledge input to the model. The results of the classi cation are summarized in Table 1.
artery aorta main celiac main gastric bif. splenic bif.
hepatic bif. pancreatic bif. sup. mesent. main
In Figure 2 we depict the Aorta (the large vertical red pipe) and branching arteries, with a di erent color associated to each edge. Labelled edges are tagged with the computed name, while sub-branches are often given a not assigned label.
This paper presents a Declarative Programming methodology for CT scan automated interpretation. We focus on arteries detection and classi cation 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 anatomical 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 di erent CT scans.
The program contains a set of anatomical rules that are easily modi able; currently, we populate the rules with simple spatial relationships derived from anatomical atlases. This is a key feature that allows, in future versions, to integrate 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 di erentiate weights associated to rules, re ecting 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 con dence 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 con dence 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
language. This will allow to produce an explanation for the labeling and con dence
rules choices. Having explainable AI techniques [
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 Nicolo Cardobi (University of Verona) for providing CT scan data and useful discussions.